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

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.

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.

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.

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.

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.

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.

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.

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.

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.