Browse Prior Art Database

Method for full-search motion estimation without a buffered search window Disclosure Number: IPCOM000029799D
Publication Date: 2004-Jul-13
Document File: 6 page(s) / 107K

Publishing Venue

The Prior Art Database


Disclosed is a method for full-search motion estimation without a buffered search window. Benefits include improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 20% of the total text.

Method for full-search motion estimation without a buffered search window

Disclosed is a method for full-search motion estimation without a buffered search window.  Benefits include improved performance.


              Motion estimation (ME) is the most essential component of video compression. The full search algorithm is the best known method to find the motion vector with the least error. ME implementations must consider their speed because it comprises about 80% of encoding time.

              Conventionally, all algorithms for ME compute the criteria for selected vectors inside buffered search window data. The smallest one is selected. An internal buffer is used for the search window data because the buffered data must be reused. However, buffering requires a hardware buffer and slows down the processing speed. The typical size of the search window buffer is 36 x 46 (2116).

              They are many kinds of criteria for finding the motion vector. The most commonly used one is the sum of absolute difference (SAD) of a vector in a search window.

              The computation for SAD is simple because it repeats subtracting, taking the absolute value, and accumulating. However, the number of required computations is large. Equation 1 is the equation for computing one SAD at (x, y) in a search window if the reference block size is 16 x 16. The value R is the data in reference block and W is the data in the search window. The computations are repeated 256 times to obtain one SAD. Typically, 961 SADs are required to determine the smallest SAD (the motion vector) for a reference block in the P- frame picture. Equation 1 is as follows:


              The computation for one motion vector requires 246,016 subtractions, absolutes, and accumulations. A 720 x 480 video frame requires 1350 motion vectors. Thirty frames are displayed per second.

              The advances in very large scale integration (VLSI) have made it possible to implement a comprehensive block matching algorithm (BMA) in hardware. The process of block matching involves a reference block and a search window. The reference block comes from a block of pixels in the frame to be encoded while the search window is a region of previously coded frame. It is searched and the best match block is selected. Although the search window and reference block are located on different frames, the former is always bigger and covers the latter on the space domain (see Figure 1).

              If the search window size is (M x M) and the reference block size is (N x N), then the full search is ((M - N + 1) x (M - N + 1)) SADs. The best match block has the smallest SAD and the space displacement between the best match block and reference block is the motion vector.

Conventional Full Search for ME