Path: news.mathworks.com!not-for-mail
From: "Jake " <whodaman230000@hotmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Video Compression - Motion Estimation HELP!!!!!
Date: Wed, 1 Apr 2009 19:14:01 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 33
Message-ID: <gr0edp$hpp$1@fred.mathworks.com>
Reply-To: "Jake " <whodaman230000@hotmail.com>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1238613241 18233 172.30.248.35 (1 Apr 2009 19:14:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 1 Apr 2009 19:14:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1784106
Xref: news.mathworks.com comp.soft-sys.matlab:529488


Like most students i have never used matlab. My professors approach is to just throw us into it without even explaining it. Is there anyone that knows how to do this or can provide any help????

ps - i am a computer engineering major so this is not my field, just a class i am required to take!


Project Description:

&#8226;	Design and implement the full search motion estimation and at least one fast motion estimation method (preferably &#8216;conjugate directions search&#8217;) for video compression.  
&#8226;	Compare the computational load as well as the quality of both the motion estimation algorithms. 

Use a sequence of first 5 frames of a avi video. 

Your report should include the following:
&#8226;	A thorough discussion of your implementation, the simulation results, the video images reconstructed by using motion compensated macroblocks. 
&#8226;	You should also provide a visual representation of motion vectors.  
&#8226;	The comparison of the full search motion estimation and a fast motion estimation method of your choice must include MAD or MSE values and computational load (number of multiplications, additions, comparison).

(a) Exhaustive Search Block Matching Algorithm:
In Exhaustive Search (ES), every possible displacement within a rectangular search window is attempted.  The displacement that produces the minimum distortion is chosen as the motion vector.  As shown in Figure 1, ff the maximum search range in either direction is w (assuming a square search), (2w+1)2 possible values exist for the motion vector.  
For ES, the distortion measure must therefore be calculated and compared (2w+1)2 times.  The resulting motion vector will be the one that minimizes the distortion within the search range.  The cost of minimizing the distortion in ES is high computational intensity.  For example, for a maximum displacement of w = 6, the matching criteria must be evaluated (2x6+1)2 = 169 times.  If MAD is chosen as the distortion criteria, and the macroblock size is 8x8, each macroblock requires 169x128 = 21,632 additions and 169 comparisons.  For an image size of 352x288, the 1,584 macroblock motion vectors need to be calculated (assuming no motion detection). Therefore, a total of: 21,632x1,584 = 34,265,088 additions and 169x1,584 = 267,696 comparisons need to be performed for each frame. If we assume a frame rate of 30 frames/second, there are over 1 G additions and 8 M comparisons per second, for a 
frame size of 352x288. The high computational requirements of ES make it unacceptable for many real time image sequence coding applications. 

(b) Conjugate Directions Search:
An alternate algorithm referred to as Conjugate Directions Search (CDS) requires lesser computations than the full search algorithm.  It is based on the assumption that the energy of the prediction error is monotonically decreasing towards the optimum motion vector in the search range, which is observed to be common in many fast search algorithms.    Figure 2 shows an example of a Conjugate Directions Search.  
CDS requires a maximum of 3+2w searches over the search range, where w is the maximum displacement. For a maximum displacement of w = 6, the matching criteria must be evaluated 3+2x6 = 15 times. For MAD as the distortion criteria and 8x8 block size, each macroblock requires 15x128 = 1,920 additions and 15 comparisons.  This is significantly lower than the 21,632 additions and 169 comparisons required by the ES algorithm. For an image of size 352x288, the 1920x1584 = 3,041,280 additions and 15x1584 = 23,760 comparisons need to be performed for each frame.
If we assume a frame rate of 30 frames/second, we have over 91 M additions/second and fewer then 713 k comparisons/second.   
While the CDS algorithm significantly reduces the computational complexity as compared to the ES algorithm, it does not always find the optimal motion vector within the search range  - it may get stuck in a local minimum of the prediction error energy.

c) Modified Logarithmic Search:
Another efficient fast search algorithm is the Modified Logarithmic Search (MLS).  Figure 3 shows an example of a Modified Logarithmic Search.  
The MLS algorithm is very efficient; it has been shown that it requires a maximum of 2 + 7log2(w) searches, where w is again used as the search range. For a maximum displacement of w = 6, the matching criteria must be evaluated 2 + 7log2(6) = 20 times.
For MAD as the distortion criteria, each 8x8 block requires 20x128 = 2,560 additions and 20 comparisons.  For an image of size 288x352, the 2,560x1,584 = 4,055,040 additions and 20x1,584 = 31,680 comparisons need to be performed for each frame. If we assume a frame rate of 30 frames/second, we have over 121M additions/second and 950K comparisons/second. 
MLS is unable to search all of the locations at the boundaries of the search window, hence it does not always result in the optimum motion vector within the search window.  However, its performance is very good for smaller displacements.