Refined Weighting Function and Momentum-Directed Genetic search pattern algorithm

• US 20100080298A1
• Filed: 06/24/2009
• Published: 04/01/2010
• Est. Priority Date: 09/30/2008
• Status: Abandoned Application

• Current Assignee: PixArt Imaging Incorporated
• Original Assignee: PixArt Imaging Incorporated
• Inventors: Tsai, Chang-Che, Hang, Hsueh-Ming, Chao, Tzu-Yi
• Application Number:
  US12/490,337
• Publication Number:
  US 20100080298A1
• Time in Patent Office: Days
• US Class Current: 375/240.160
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

A weighting function (WF) is previously provided to model the number of search points of a pattern search. However, WF fails to properly describe the behavior of the genetic pattern search algorithms due to some over-simplifications in their models. Therefore, a refined weighting function (RWF) is provided to more accurately describe both genetic and non-genetic pattern searches. Moreover, based on the understanding to RWF, two momentum-directed genetic search algorithms are further provided. These new algorithms check the possible mutations according to their likelihood to the preceding successful mutations and further accelerate the previous genetic pattern searches.

Claims

1. An adaptive method of performing block motion estimation comprising:

(a) calculating a motion vector related index for a first frame according to a first search pattern;

(b) determining a relationship between the motion vector related index and a predetermined threshold for the first frame; and

(c) selecting a first or a second search pattern algorithms for identifying one or more search blocks in a second frame according to the determined relationship between the motion vector related index and the predetermined threshold for the first frame;

wherein the predetermined threshold is determined by refined weighting functions of the first and the second search pattern algorithms;

wherein the refined weighting functions of the first and the second pattern algorithms are numbers of average search points for the first and the second pattern algorithms searching in the first frame;

wherein block motion estimation is performed adaptively for the second frame.

2. The method of claim 1, wherein the motion vector related index is the motion vector variance, motion vector standard deviations, or other mathematically equivalent or approximate index.

3. The method of claim 1, wherein each of the first and the second search pattern algorithms comprise momentum-directed genetic pattern algorithms.

4. The method of claim 3, wherein the step (c) further comprising:

selecting the first search pattern algorithm for identifying at least one search block in the second frame when the motion vector related index exceeds the predetermined threshold.

5. The method of claim 4, wherein the momentum-directed genetic algorithm of the first search pattern comprises a hexagonal shaped algorithm.

6. The method of claim 3, wherein step (c) further comprising:

selecting the second search pattern algorithm for identifying at least one search block in the second frame when the motion vector related index is equal or less than the predetermined threshold.

7. The method of claim 6, wherein the momentum-directed genetic algorithm of the second search pattern comprises a rhombus shaped algorithm.

8. The method of claim 1, wherein the motion vector related index is determined by analyzing a reference frame.

9. A momentum-directed genetic pattern search method of performing block motion estimation for a frame, the method comprising:

(a) selecting a child point proximate to a parent point according to likelihood of the parent point according to previous successful mutations;

(b) comparing block matching cost of the parent point and block matching cost of the child point; and

(c) setting either the parent point or the child point as a surviving parent point for a successful mutation according to the compared result of the step (b).

10. The method of claim 9, further comprising:

(d) repeating the steps (a) to (c) until all child points proximate to the surviving parent point have been checked and the surviving parent point is still set as the surviving parent point according to the compared result of the step (b) and setting the surviving parent point as a final surviving parent point; and

(e) identifying a motion vector for the frame according to the final surviving parent point.

11. The method of claim 9, further comprising:

(f) identifying a starting point within the frame as the parent point.

12. The method of claim 9, wherein the child point is immediately adjacent to the parent point.

13. The method of claim 9, wherein comparing block matching cost of the parent point and block matching cost of the child point comprises:

comparing a sum of absolute differences of the parent point between a sum of absolute differences of the child point.

14. The method of claim 9, wherein said child point is selected from at most four candidate points.

15. The method of claim 10, further comprising:

(j) determining a direction according to the parent point and the surviving parent point.

16. The method of claim 15, wherein the child points checked in the step (d) are selected according to likelihood of the direction determined in the step (j).

17. A momentum-directed genetic rhombus pattern search method of performing block motion estimation for a frame, the method comprising:

(a) selecting a child point from a perimeter portion of a rhombus centered about a parent point according to likelihood of the parent point according to previous successful mutations;

(b) comparing block matching cost of the parent point and block matching cost of the child point; and

(c) setting either the parent point or the child point as a surviving parent point for a successful mutation according to the compared result of the step (b).

18. The method of claim 17, further comprising:

(d) repeating the steps (a) to (c) until all child points from the perimeter portion of the rhombus centered about the surviving parent point have been checked and the surviving parent point is still set as the surviving parent point according to the compared result of the step (b) and setting the surviving parent point as a final surviving parent point;

wherein the child points are also determined by reference to a rhombus pattern centered about the surviving parent point; and

(e) identifying a motion vector for the frame according to the final surviving parent point.

19. The method of claim 17, further comprising:

(f) identifying a starting point within the frame as the parent point by performing a block matching operation within the frame.

20. The method of claim 17, wherein in the step (c), the child point is selected as the surviving point when the block matching cost of the child point is lower than the block matching cost of the parent point without computing block matching costs of other remaining unchecked child points.

21. A momentum-directed genetic hexagonal pattern search method of performing block motion estimation for a frame, the method comprising:

(a) selecting a child point from a perimeter portion of a hexagon centered about a parent point according to likelihood of the parent point according to previous successful mutations;

(b) comparing block matching cost of the parent point and block matching cost of the child point; and

(c) setting either the parent point or the child point as a surviving parent point for a successful mutation according to the compared result of the step (b).

22. The method of claim 21, further comprising:

(d) repeating the steps (a) to (c) until all child points from the perimeter portion of the hexagon centered about the surviving parent point have been checked and the surviving parent point is still set as the surviving parent point according to the compared result of the step (b) and setting the surviving parent point as a final surviving parent point;

wherein the child points are also determined by reference to a hexagonal pattern centered about the surviving parent point; and

(e) identifying a motion vector for the frame according to the final surviving parent point.

23. The method of claim 21, further comprising:

(f) identifying a starting point within the frame as the parent point by performing a block matching operation within the frame.

24. The method of claim 21, wherein in the step (c), the child point is selected as the surviving point when the block matching cost of the child point is lower than the block matching cost of the parent point without computing block matching costs of other remaining unchecked child points.

25. The method of claim 21, further comprising:

(h) performing a fine searching operation on selected points situated between the parent point and the child points situated on the hexagon perimeter portion.

26. The method of claim 25, further comprising:

(i) ranking the child points according to each weighted sum of block distortions of child points neighboring a corresponding child point; and

(j) selecting a point of the ranked child points having minimal sum of the block distortions of the child points neighboring the point among the child points.

27. The method of claim 25, wherein a number of selected points which are checked in the step (h) is determined by a direction of the motion vector.