Granted Patent B2

US 7,983,341 · App. 11/329,685 · Granted Jul 19, 2011

Abstract

Claims (49)

1. A method of fast motion estimation for video pre-processing, comprising the steps of:

(A) selecting, using a microprocessor, a second-order distortion criterion for identifying a best reference image portion for comparison with a current image portion, said second-order distortion criterion being a Lagrange-optimized combination of a mean squared error criterion with an entropy criterion;

(B) using said second-order distortion criterion to select, using a microprocessor, an initial reference image portion as an initial starting point for a motion estimation search, said initial starting position being chosen based on at least one motion vector from a neighboring image portion; and

(C) performing, using a microprocessor, a fast motion estimation search including the steps of:

(i) performing, using a microprocessor, a diamond search starting from said initial reference image portion using said second-order distortion criterion to identify a candidate best reference image portion;

(ii) performing, using a microprocessor, a nearest neighbor search starting from the candidate best reference image portion using said second-order distortion criterion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within a search range limited by an adaptive search range cap;

(iii) re-identifying, using a microprocessor, the better reference image portion as the candidate best reference image portion;

(iv) repeating, using a microprocessor, said steps (ii) and (iii) until in said step (ii) either (a) the candidate best reference image portion is identified as the better reference image portion so that said second-order distortion criterion cannot be improved, or (b) any further search would exceed the adaptive search range cap;

(v) identifying, using a microprocessor, the candidate best reference image portion as the best reference image portion; and

(vi) calculating, using a microprocessor, a motion vector from the best reference image portion.

2. A method of fast motion estimation for video pre-processing, comprising the steps of:

(A) selecting, using a microprocessor, a second-order distortion criterion for identifying a best reference image portion for comparison with a current image portion, said second-order distortion criterion being a Lagrange-optimized combination of a mean squared error criterion with an entropy criterion; and

(B) using said second-order distortion criterion to select, using a microprocessor, an initial reference image portion as an initial starting point for a motion estimation search, said initial starting position being chosen based on at least one motion vector from a neighboring image portion.

(C) performing, using a microprocessor, a fast motion estimation search including the steps of:

(i) performing, using a microprocessor, a diamond search starting from said initial reference image portion to identify a candidate best reference image portion;

(ii) performing, using a microprocessor, a nearest neighbor search starting from the candidate best reference image portion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within a search range;

(iii) re-identifying, using a microprocessor, the better reference image portion as the candidate best reference image portion;

(iv) repeating, using a microprocessor, said steps (ii) and (iii) until in said step (ii) either (a) the candidate best reference image portion is identified as the better reference image portion so that said second-order distortion criterion cannot be improved, or (b) any further search would exceed the adaptive search range cap; and

(v) identifying, using a microprocessor, the candidate best reference image portion as the best reference image portion.

3. The method of claim 2 , wherein said step of performing a diamond search starting from said initial reference image portion uses said second-order distortion criterion to identify a candidate best reference image portion.

4. The method of claim 3 , wherein said step of performing a nearest neighbor search starting from the candidate best reference image portion uses said second-order distortion criterion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within the search range.

5. The method of claim 4 , wherein said step of performing a nearest neighbor search starting from the candidate best reference image portion uses said second-order distortion criterion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within a search range limited by an adaptive search range cap.

6. The method of claim 2 , wherein said step of performing a nearest neighbor search starting from the candidate best reference image portion uses said second-order distortion criterion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within the search range.

7. The method of claim 6 , wherein said step of performing a nearest neighbor search starting from the candidate best reference image portion uses said second-order distortion criterion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within a search range limited by an adaptive search range cap.

8. The method of claim 7 , further comprising the step of:

(vi) calculating, using a microprocessor, a motion vector from the best reference image portion identified in step (v).

9. The method of claim 6 , wherein said step of performing a nearest neighbor search starting from the candidate best reference image portion identifies either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within a search range limited by an adaptive search range cap.

10. The method of claim 9 , further comprising the step of:

(vi) calculating, using a microprocessor, a motion vector from the best reference image portion identified in step (v).

11. Apparatus for performing fast motion estimation for video pre-processing, comprising:

(A) structure for selecting a second-order distortion criterion for identifying a best reference image portion for comparison with a current image portion, said second-order distortion criterion being a Lagrange-optimized combination of a mean squared error criterion with an entropy criterion;

(B) structure for using said second-order distortion criterion to select an initial reference image portion as an initial starting point for a motion estimation search, said initial starting position being chosen based on at least one motion vector from a neighboring image portion; and

(C) structure for performing a fast motion estimation search including:

(i) structure for performing a diamond search starting from said initial reference image portion using said second-order distortion criterion to identify a candidate best reference image portion;

(ii) structure for performing a nearest neighbor search starting from the candidate best reference image portion using said second-order distortion criterion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within a search range limited by an adaptive search range cap;

(iii) structure for re-identifying the better reference image portion as the candidate best reference image portion;

(iv) wherein the nearest neighbor search and the re-identification are repeated until, in performing the nearest neighbor search, either (a) the candidate best reference image portion is identified as the better reference image portion so that said second-order distortion criterion cannot be improved, or (b) any further search would exceed the adaptive search range cap;

(v) structure for identifying the candidate best reference image portion as the best reference image portion; and

(vi) structure for calculating a motion vector from the best reference image portion.

12. A method of statistical content block matching for video pre-processing, comprising, in the recited order, the steps of:

First: (A) selecting, using a microprocessor, a second-order distortion criterion for identifying a best reference image portion for comparison with a current image portion, said second-order distortion criterion being a Lagrange-optimized combination of a mean squared error criterion with an entropy criterion;

Second: (B) using said second-order distortion criterion to select, using a microprocessor, an initial reference image portion as an initial starting point for a motion estimation search, said initial starting position being chosen based on at least one motion vector from a neighboring image portion; and

Third: (C) performing, using a microprocessor, a fast motion estimation search including the steps of:

Fourth: (i) performing, using a microprocessor, a diamond search starting from said initial reference image portion using said second-order distortion criterion to identify a candidate best reference image portion;

Fifth: (ii) performing, using a microprocessor, a nearest neighbor search starting from the candidate best reference image portion using said second-order distortion criterion to identify either the candidate best reference image portion or a different neighboring reference image portion as a better reference image portion within a search range limited by an adaptive search range cap;

Sixth: (iii) re-identifying, using a microprocessor, the better reference image portion as the candidate best reference image portion;

Seventh: (iv) repeating, using a microprocessor, said steps (ii) and (iii) until in said step (ii) either (a) the candidate best reference image portion is identified as the better reference image portion so that said second-order distortion criterion cannot be improved, or (b) any further search would exceed the adaptive search range cap;

Eighth: (v) identifying, using a microprocessor, the candidate best reference image portion as the best reference image portion; and

Nineth: (vi) calculating, using a microprocessor, a motion vector from the best reference image portion.

Assignments (10)