Fast implementation of recursive diamond search
First Claim
1. A method for block matching between a first frame and a second frame, comprising:
- performing a first search for a matching block in the first frame using a search pattern centered at a first center point;
from points in the search pattern centered at the first center point, determining a best point that produces a close match in the first search;
if the best point does not produce a match satisfying a criterion;
storing the first center point in an array;
setting the best point as a second center point;
performing a second search for the matching block in the first frame using the search pattern centered at the second center point, wherein said performing the second search comprises;
for each point in the search pattern centered at the second center point, at least approximating distances to center points stored in the array;
excluding any point in the search pattern centered at the second center point that has at least one distance less than a threshold;
performing the second search for remaining points in the search pattern centered at the second center point.
3 Assignments
0 Petitions
Accused Products
Abstract
A method for block matching includes performing a first search for a matching block in a frame using a search pattern centered at a first center point and determining a best point that produces a close match. If the best point does not produce a match satisfying a criterion, the method further includes storing the first center point in an array, setting the best point as a second center point, and performing a second search using the search pattern centered at the second center point. Performing the second search includes (1) at least approximating distances between (a) points in the search pattern centered at the second center point and (b) center points stored in the array; (2) excluding any point that has at least one distance less than a threshold; and (3) performing the second search for remaining points in the search pattern centered at the second center point.
-
Citations
9 Claims
-
1. A method for block matching between a first frame and a second frame, comprising:
-
performing a first search for a matching block in the first frame using a search pattern centered at a first center point;
from points in the search pattern centered at the first center point, determining a best point that produces a close match in the first search;
if the best point does not produce a match satisfying a criterion;
storing the first center point in an array;
setting the best point as a second center point;
performing a second search for the matching block in the first frame using the search pattern centered at the second center point, wherein said performing the second search comprises;
for each point in the search pattern centered at the second center point, at least approximating distances to center points stored in the array;
excluding any point in the search pattern centered at the second center point that has at least one distance less than a threshold;
performing the second search for remaining points in the search pattern centered at the second center point. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method for block matching in motion estimation, comprising:
-
performing a first search for a matching block in a frame using a first search pattern centered at a first center point;
from points in the first search pattern centered at the first center point, determining a first best point that produces a close match in the first search;
if the first best point does not produce a match satisfying a first criterion;
storing the first center point in an array;
setting the first best point as a second center point;
performing a second search for the matching block in the frame using the first search pattern centered at the second center point, wherein said performing the second search comprises;
for each point in the first search pattern centered at the second center point, at least approximating distances to center points stored in the array;
excluding any point in the first search pattern centered at the second center point that has at least one distance less than a threshold;
performing the second search for remaining points in the first search pattern centered at the second center point;
if the first best point produces a match satisfying the first criterion;
setting the first best point as the second center point;
performing a third search for the matching block in the frame using a second search pattern centered at the second center point;
from points in the second search pattern centered at the second center point, determining a second best point that produces a close match in the third search;
storing the second best point for motion estimation;
if the first best point produces a match satisfying a second criterion, storing the first best point for motion estimation.
-
Specification