Flatted hexagon search method for fast block motion estimation

#1. Field of the Invention

#The present invention relates to a flatted hexagon search method, and more specifically, to a flatted hexagon search method for fast block motion estimation.

#2. Description of the Prior Art

#FIG. 1 is a schematic diagram of a prior art HEXBS algorithm with 10 cavity points in the searching pattern.

#FIG. 2 is a schematic diagram of a prior art HEXBS algorithm with 4 cavity points in the final searching stage.

#FIG. 3 is a schematic diagram of a prior art DS algorithm with 4 cavity points in the searching pattern.

#Please refer to FIGS. 5-9. FIG. 5 is a flow chart for performing a flatted hexagon search (FHS) method according to the present invention. FIG. 6 to FIG. 9 are operational diagrams for performing the flatted hexagon search method in FIG. 5. First of all, as FIG. 6 shows, seven initial check points 31 are selected in the central part of a searching window 30 at the first stage of the search. The seven initial check points 31 are selected over three adjacent rows with six of the initial check points positioned at vertices of a hexagon and one of the initial check points positioned at a center of the hexagon. The initial check points 31 are then checked for a minimum block distortion measure (BDM) point of the seven initial check points 31.

#Please refer to FIG. 7. If the previous check finds that the initial check point 31 at the center of the hexagon is the minimum BDM point of the seven initial check points 31 in FIG. 6, then select four check points 32 adjacent to the initial check point 31 positioned at the center of the hexagon to form a final cross pattern, and search the four check points 32 and the initial check point 31 positioned at the center of the hexagon for a minimum BDM point of the four check points 32 and the initial check point 31 positioned at the center of the hexagon. After the minimum BDM point of the five check points is found, it is then considered as an optimized searching end point. Then a moving vector is generated according to positions of the optimized searching end point and the initial check point 31 positioned at the center of the hexagon in FIG. 7.

#Please refer to FIG. 8. If the minimum BDM point found in FIG. 6 isn't located at the center of the original hexagon, then take the minimum BDM point found in FIG. 6 as a new center point 331 and select three check points 33 (shown as hashed circles) positioned symmetrical to three initial check points closest to the new center point 331 positioned at a vertex of the hexagon with respect to the new center point 331 positioned at the vertex of the hexagon. Then search the check points 33 selected in FIG. 8 and the initial check point 331 at the vertex of the hexagon for a minimum BDM point of the check points 33 and the initial check point 331 at the vertex of the hexagon. If the minimum BDM point is found at the center (i.e. the check point 331) of the new searching pattern, then select four check points adjacent to the check point 331 positioned at the center of the new hexagon to form a final cross pattern as in FIG. 7 and perform the same step as that in FIG. 7 described in the previous paragraph.