Thread Subject:

Video Compression - Motion Estimation HELP!!!!!

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:

• Design and implement the full search motion estimation and at least one fast motion estimation method (preferably ‘conjugate directions search’) for video compression.
• 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:
• A thorough discussion of your implementation, the simulation results, the video images reconstructed by using motion compensated macroblocks.
• You should also provide a visual representation of motion vectors.
• 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.

"Jake " <whodaman230000@hotmail.com> wrote in message <gr0edp$hpp$1@fred.mathworks.com>...
> 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:
>
> • Design and implement the full search motion estimation and at least one fast motion estimation method (preferably ‘conjugate directions search’) for video compression.
> • 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:
> • A thorough discussion of your implementation, the simulation results, the video images reconstructed by using motion compensated macroblocks.
> • You should also provide a visual representation of motion vectors.
> • 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.

TL;DR

What's your actual question, or is this another April Fool's Day homework request?

On Apr 1, 3:14=A0pm, "Jake " <whodaman230...@hotmail.com> wrote:
> Like most students i have never used matlab. My professors approach is to=
 just throw us into it without even explaining it.
[homework problem snipped]
---------------------------------------------------------------------------=
--------------------
Jake:
It looks like that is your approach towards us also! (except
conversely, because most people here know MATLAB but not motion
estimation.)
Sorry I can't help you with this...
Looks like a challenging problem even for someone who knows MATLAB.
You'd best start off with a MATLAB programming tutorial or ask your
professor.

"Michael" <michaelmorris1984@gmail.com> wrote in message <gr0j7h$67$1@fred.mathworks.com>...
> "Jake " <whodaman230000@hotmail.com> wrote in message <gr0edp$hpp$1@fred.mathworks.com>...
> > 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:
> >
> > • Design and implement the full search motion estimation and at least one fast motion estimation method (preferably ‘conjugate directions search’) for video compression.
> > • 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:
> > • A thorough discussion of your implementation, the simulation results, the video images reconstructed by using motion compensated macroblocks.
> > • You should also provide a visual representation of motion vectors.
> > • 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.
>
> TL;DR
>
> What's your actual question, or is this another April Fool's Day homework request?


not a joke, just need help on how to do it or even begin to do it! Like I said I have never used matlab before!

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <e3a5d241-ab7a-4e01-b7f0-4ac5e96edbca@r33g2000yqn.googlegroups.com>...
> On Apr 1, 3:14=A0pm, "Jake " <whodaman230...@hotmail.com> wrote:
> > Like most students i have never used matlab. My professors approach is to=
> just throw us into it without even explaining it.
> [homework problem snipped]
> ---------------------------------------------------------------------------=
> --------------------
> Jake:
> It looks like that is your approach towards us also! (except
> conversely, because most people here know MATLAB but not motion
> estimation.)
> Sorry I can't help you with this...
> Looks like a challenging problem even for someone who knows MATLAB.
> You'd best start off with a MATLAB programming tutorial or ask your
> professor.

already tried that, professor is no help...sadly this is how they teach you in school.

"Jake " <whodaman230000@hotmail.com> writes:

> 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:
>
> • Design and implement the full search motion estimation and at
> least one fast motion estimation method (preferably ‘conjugate
> directions search’) for video compression. • 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.

[snip remainder of homework assignment]

The first thing to do is to learn the basics of MATLAB. Use the
"getting started" portion of the documentation. If this is beyond your
skills or background in the time allowed, you might consider dropping
the class and/or complaining to the department that the course has
a prerequisite of some programming background, which was not fairly
advertised.

Then, learn about motion estimation, and how one implements the various
types of motion estimation. Start with some pseudocode, or at least get
clear in your mind what specific math operations you need to perform.

Then, start writing some MATLAB code that does this. If you get stuck
with the code, or it produces results you don't expect, then post back
here with your code and your specific issues.

By the way the assignment doesn't mention MATLAB. Why not use C or C++
or some other language that you are already familiar with?

-Peter

Peter Boettcher <boettcher@ll.mit.edu> wrote in message <muy3acp972n.fsf@G99-Boettcher.llan.ll.mit.edu>...
> "Jake " <whodaman230000@hotmail.com> writes:
>
> > 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:
> >
> > • Design and implement the full search motion estimation and at
> > least one fast motion estimation method (preferably ‘conjugate
> > directions search’) for video compression. • 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.
>
> [snip remainder of homework assignment]
>
> The first thing to do is to learn the basics of MATLAB. Use the
> "getting started" portion of the documentation. If this is beyond your
> skills or background in the time allowed, you might consider dropping
> the class and/or complaining to the department that the course has
> a prerequisite of some programming background, which was not fairly
> advertised.
>
> Then, learn about motion estimation, and how one implements the various
> types of motion estimation. Start with some pseudocode, or at least get
> clear in your mind what specific math operations you need to perform.
>
> Then, start writing some MATLAB code that does this. If you get stuck
> with the code, or it produces results you don't expect, then post back
> here with your code and your specific issues.
>
> By the way the assignment doesn't mention MATLAB. Why not use C or C++
> or some other language that you are already familiar with?
>
> -Peter

thanks, ive already tried everything, and i cant really drop the class cause its almost the end of the sem. It has to be done in matlab, that is one thing he mentioned in class.

"Jake " <whodaman230000@hotmail.com> wrote in message <gr0edp$hpp$1@fred.mathworks.com>...
> 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:
>
> • Design and implement the full search motion estimation and at least one fast motion estimation method (preferably ‘conjugate directions search’) for video compression.
> • 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:
> • A thorough discussion of your implementation, the simulation results, the video images reconstructed by using motion compensated macroblocks.
> • You should also provide a visual representation of motion vectors.
> • 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.


Does anyone have any idea on how to do this????

"Jake " <whodaman230000@hotmail.com> wrote in message <gr0edp$hpp$1@fred.mathworks.com>...
> 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:
>
> • Design and implement the full search motion estimation and at least one fast motion estimation method (preferably ‘conjugate directions search’) for video compression.
> • 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:
> • A thorough discussion of your implementation, the simulation results, the video images reconstructed by using motion compensated macroblocks.
> • You should also provide a visual representation of motion vectors.
> • 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.


Does anyone have any idea on how to do this????

On Apr 3, 1:34 am, "Jake " <whodaman230...@hotmail.com> wrote:
> "Michael" <michaelmorris1...@gmail.com> wrote in message <gr0j7h$6...@fred.mathworks.com>...
> > "Jake " <whodaman230...@hotmail.com> wrote in message <gr0edp$hp...@fred.mathworks.com>...
> > > 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:
>
> > > •   Design and implement the full search motion estimation and at least one fast motion estimation method (preferably ‘conjugate directions search’) for video compression.  
> > > •   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:
> > > •   A thorough discussion of your implementation, the simulation results, the video images reconstructed by using motion compensated macroblocks.
> > > •   You should also provide a visual representation of motion vectors.  
> > > •   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.
>
> > TL;DR
>
> > What's your actual question, or is this another April Fool's Day homework request?
>
> not a joke, just need help on how to do it or even begin to do it! Like I said I have never used matlab before!

am doing almost the exact same project and i have no clue what to do,
i too never used matlab, if you managed to do it, you can really help
out..

deadline is due in few days.. -.-

 > am doing almost the exact same project and i have no clue what to do,
> i too never used matlab, if you managed to do it, you can really help
> out..
>
> deadline is due in few days.. -.-

Deadline past and i didn't do so bad

I attached a rar file, compressed the module folder.

 (link: http://www.mediafire.com/?3lkwwk7ex6eessh )

it includes a paper (DSP image processing.prop.docx) that was sort of the outcome of my research, and many other very useful research papers.

It also has (code) folder which is the code i mainly depended on (by Aroh), and my modifications on it folder called (mk)

thanks alot to Aroh Barjatya at Utah State University.

hope this helps