Statistical content block matching scheme for pre-processing in encoding and transcoding

• US 20060188020A1
• Filed: 01/10/2006
• Published: 08/24/2006
• Est. Priority Date: 02/24/2005
• Status: Active Grant

• Current Assignee: MK Systems USA Inc.
• Original Assignee: Ericsson Television Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Wang, Zhicheng Lancelot
• Granted Patent: US 7,983,341 B2
• Time in Patent Office: Days
• US Class Current: 375/240.160
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape

Abstract

Statistical content block matching for video pre-processing, for example in fast motion estimation, uses a second-order distortion criterion for processing steps such as identifying a best reference image portion for comparison with a current image portion. The second-order distortion criterion is a Lagrange-optimized combination of a mean squared error criterion with an entropy criterion. Then a fast motion estimation search advantageously includes performing a diamond search using the second-order distortion criterion to identify a candidate best reference image portion, and performing a nearest neighbor search starting using said second-order distortion criterion to identify the best reference image portion within a search range limited by an adaptive search range cap. A better motion vector can then be calculated.

Claims

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

(A) 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) 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) performing a fast motion estimation search including the steps of;

(i) 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) 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) re-identifying the better reference image portion as the candidate best reference image portion;

(iv) repeating 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 the candidate best reference image portion as the best reference image portion; and

(vi) calculating 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 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 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.

3. The method of claim 2, further comprising the step of:

(C) performing a fast motion estimation search including the steps of;

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

(ii) performing 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 the better reference image portion as the candidate best reference image portion;

(iv) repeating 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 the candidate best reference image portion as the best reference image portion.

4. The method of claim 3, 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.

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 the search range.

6. The method of claim 5, 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.

7. 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.

8. The method of claim 7, 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.

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

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

10. The method of claim 7, 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.

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

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

12. A method of fast motion estimation, comprising the steps of:

selecting a unique 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

using said second-order distortion criterion to perform a motion estimation search.

13. A method of fast motion estimation, comprising the steps of:

performing a first, higher level motion search procedure using a first motion search criterion for identifying a first candidate best reference image portion of a reference image;

performing a second, middle level motion search procedure using a second motion search criterion and said first candidate best reference image portion for identifying a second candidate best reference image portion of the reference image, wherein said second motion search criterion is different from said first motion search criterion;

performing a third, lower level motion search procedure using a third motion search criterion and said second candidate best reference image portion for identifying a third candidate best reference image portion of the reference image, wherein said third motion search criterion is different from said first motion search criterion and said second search motion search criterion; and

calculating a motion vector from the third best reference image portion.

14. A method of fast motion estimation, comprising the steps of:

selecting a distortion criterion for identifying a best reference image portion of a reference image; and

performing a fast motion estimation search to identify the best reference image portion using said distortion criterion, wherein an adaptive motion search range cap is used to dynamically control a search range used in said search and/or to choose a size of a block used in said search; and

calculating a motion vector from the best reference image portion.

15. 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.

16. Apparatus for 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; and

(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.

17. The apparatus of claim 16, further comprising:

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

(i) structure for performing a diamond search starting from said initial reference image portion to identify a candidate best reference image portion;

(ii) structure for performing 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) 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; and

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

18. The apparatus of claim 17, wherein said structure for 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.

19. The apparatus of claim 18, wherein said structure for 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.

20. The apparatus of claim 19, wherein said structure for 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.

21. The apparatus of claim 17, wherein said structure for 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.

22. The apparatus of claim 21, wherein said structure for 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.

23. The apparatus of claim 22, further comprising:

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

24. The apparatus of claim 21, wherein said structure for 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.

25. The apparatus of claim 24, further comprising:

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

26. Apparatus for fast motion estimation, comprising:

structure for selecting a unique 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

structure for using said second-order distortion criterion to perform a motion estimation search.

27. Apparatus for fast motion estimation, comprising the steps of:

structure for performing a first, higher level motion search procedure using a first motion search criterion for identifying a first candidate best reference image portion of a reference image;

structure for performing a second, middle level motion search procedure using a second motion search criterion and said first candidate best reference image portion for identifying a second candidate best reference image portion of the reference image, wherein said second motion search criterion is different from said first motion search criterion;

structure for performing a third, lower level motion search procedure using a third motion search criterion and said second candidate best reference image portion for identifying a third candidate best reference image portion of the reference image, wherein said third motion search criterion is different from said first motion search criterion and said second search motion search criterion; and

structure for calculating a motion vector from the third best reference image portion.

28. Apparatus for fast motion estimation, comprising:

structure for selecting a distortion criterion for identifying a best reference image portion of a reference image; and

structure for performing a fast motion estimation search to identify the best reference image portion using said distortion criterion, wherein an adaptive motion search range cap is used to dynamically control a search range used in said search and to choose a size of a block used in said search; and

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

29. A signal generated by a method of fast motion estimation for video pre-processing, the method comprising the steps of:

(A) 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) 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) performing a fast motion estimation search including the steps of;

(i) 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) 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) re-identifying the better reference image portion as the candidate best reference image portion;

(iv) repeating 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 the candidate best reference image portion as the best reference image portion; and

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

30. A signal generated by a method of fast motion estimation for video pre-processing, the method comprising the steps of:

(A) 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; and

(B) 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.

31. The signal of claim 30, wherein the method further comprises the step of:

(C) performing a fast motion estimation search including the steps of;

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

(ii) performing 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 the better reference image portion as the candidate best reference image portion;

(iv) repeating 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 the candidate best reference image portion as the best reference image portion.

32. The signal of claim 31, 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.

33. The signal of claim 32, 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.

34. The signal of claim 33, 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.

35. The signal of claim 34, 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.

36. The signal of claim 35, 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.

37. The signal of claim 36, wherein the method further comprises the step of:

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

38. The signal of claim 35, 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.

39. The signal of claim 38, wherein the method further comprises the step of:

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

40. A signal generated by a method of fast motion estimation, the method comprising the steps of:

selecting a unique 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

using said second-order distortion criterion to perform a motion estimation search.

41. A signal generated by a method of fast motion estimation, the method comprising the steps of:

performing a first, higher level motion search procedure using a first motion search criterion for identifying a first candidate best reference image portion of a reference image;

performing a second, middle level motion search procedure using a second motion search criterion and said first candidate best reference image portion for identifying a second candidate best reference image portion of the reference image, wherein said second motion search criterion is different from said first motion search criterion;

performing a third, lower level motion search procedure using a third motion search criterion and said second candidate best reference image portion for identifying a third candidate best reference image portion of the reference image, wherein said third motion search criterion is different from said first motion search criterion and said second search motion search criterion; and

calculating a motion vector from the third best reference image portion.

42. A signal generated by a method of fast motion estimation, the method comprising the steps of:

selecting a distortion criterion for identifying a best reference image portion of a reference image; and

performing a fast motion estimation search to identify the best reference image portion using said distortion criterion, wherein an adaptive motion search range cap is used to dynamically control a search range used in said search and/or to choose a size of a block used in said search; and

calculating a motion vector from the best reference image portion.

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

First;

(A) 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;

Second;

(B) 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

Third;

(C) performing a fast motion estimation search including the steps of;

Fourth;

(i) 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;

Fifth;

(ii) 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;

Sixth;

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

Seventh;

(iv) repeating 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 the candidate best reference image portion as the best reference image portion; and

Nineth;

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