Block-matching motion estimator for video coder

• US 5,200,820 A
• Filed: 04/26/1991
• Issued: 04/06/1993
• Est. Priority Date: 04/26/1991
• Status: Expired due to Term

• Current Assignee: Shingo Limited Liability Company
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Gharavi, Hamid
• Primary Examiner(s): Peng, John K.
• Application Number:
  US07/692,279
• Time in Patent Office: 711 Days
• Field of Search: 338/105, 338/135, 338/136
• US Class Current: 375/240.12
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/231 using full search
• 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 method and apparatus (110) for performing block-matching motion estimation in a video coder is disclosed which estimates the motion vector associated with each block of pels in the current coding frame. The motion vector for each block in the current frame is estimated by searching through a larger search window in the previous frame for a best match. At each possible shift position within the search window a pel-by-pel comparison (304) is made between the intensity of the pels in the block in the current frame and the corresponding pels in the previous frame. Each pel is classified as either a matching pel or a mismatching pel depending upon the pel difference and a threshold (306). The number of matching pels at each possible shift position is counted (307) and the motion vector is determined from the shift position that yields the maximum number of matching pels.

Claims

1. A method of estimating the frame-to-frame motion of a block of pels in a video frame comprising the steps of:

(a) comparing the pels in the block in a current frame with pels in a corresponding block in a previous frame;

(b) determining from each comparison whether each pel is a matching pel or a mismatching pel;

(c) counting the number of matching pels or the number of mismatching pels;

(d) repeating steps (a) through (c) for a predetermined number of blocks that surround the corresponding block in the previous frame; and

(e) estimating the relative motion of the block between its position in the current frame and its position in the previous frame in response to the position of the block in the previous frame at which the number of matching pels is highest or the number of mismatching pels is lowest.

2. A method of estimating the frame-to-frame motion of a block of pels in a video frame comprising the steps of:

(a) comparing the pels in the block in a current frame with pels in a block within a search window in a previous frame that surrounds the position of the block in the current frame;

(b) determining from each comparison whether each pel is a matching pel or a mismatching pel;

(c) counting the number of matching pels or the number of mismatching pels;

(d) repeating steps (a) through (c) for each block within the search window in the previous frame; and

(e) estimating the relative motion of the block between its position in the current frame and its position in the previous frame in response to the position of the block in the previous frame at which the number of matching pels is highest or the number of mismatching pels is lowest.

3. A method of estimating the frame-to-frame motion of a block of pels in a video frame comprising the steps of:

(a) comparing the intensity of the pels in the block in the current frame with the intensity of pels in a block within a search window in a previous frame that surrounds the position of the block in the current frame;

(b) determining that each pel is a matching pel if the difference between intensities is less or equal to a threshold and is a mismatching pel if the difference is greater than a threshold;

(c) counting the number of matching pels or the number of mismatching pels;

(d) repeating steps (a) through (c) for each block within the search window in the previous frame; and

(e) estimating the relative motion of the position of the block in the current frame from its position in the previous frame in response to the position of the block in the previous frame at which the number of matching pels is highest or the number of mismatching pels is lowest.

4. The method of claim 3 wherein the threshold is a predetermined value.

5. The method of claim 3 wherein the threshold is determined by the fullness of a buffer which stores the coded differences between the intensities of the pels in the block in the current frame and the intensities of the pels in the particular block in the previous frame at which the number of matching pels has been determined to be highest or the number of mismatching pels has been determined to be the lowest.

6. Apparatus in a video coder for estimating the frame-to-frame motion of a block of pels in a video frame comprising:

means for pel-by-pel comparing the pels in the block in the current frame and the pels in a block in a previous frame;

means for determining from each comparison whether each pel is a matching pel or a mismatching pel;

means for counting the number of matching pels or the number of mismatching pels;

means for selecting another block of pels in the previous frame for pel-by-pel comparison with the block in the current frame; and

means for estimating the relative motion of the position of the block in the current frame from its position in the previous frame in response to the block in the previous frame at which the number of matching pels is highest or the number of mismatching pels is lowest.

7. Apparatus in a video coder for estimating the frame-to-frame motion of a block of pels in a video frame comprising:

means for forming a search window in a previous frame that surrounds the position of the block of pels in the current frame for which motion it to be estimated;

means for pel-by-pel comparing the pels in the current frame with pels in a block within said search window in the previous frame;

means for determining from each comparison whether each pel is a matching pel or a mismatching pel;

means for counting the number of matching pels or the number of mismatching pels;

means for selecting another block of pels within the search window for pel-by-pel comparisons; and

means for estimating the relative motion of the block in the current frame from its position in the previous frame in response to the block in the previous frame in the search window at which the number of matching pels is highest or the number of mismatching pels is lowest.

8. Apparatus in a video coder for estimating the frame-to-frame motion of a block of pels in a video frame comprising:

means for forming a search window in a previous frame that surrounds the block of pels in the current frame for which motion is to be estimated;

means for pel-by-pel comparing the intensity of the pels in the block in the current frame and the intensity of pels in a block within the search window in the previous frame;

means for determining from each comparison that a pel is a matching pel if the difference between intensities is less than or equal to a threshold and is a mismatching pel if the difference is greater than said threshold;

means for counting the number of matching pels or the number of mismatching pels;

means for selecting another block of pels within the search window for pel-by-pel comparisons; and

means for estimating the relative motion of the block in the current frame from its position in the search window in the previous frame in response to the block within the search window at which the number of matching pels is highest or the number of mismatching pels is lowest.

9. Apparatus in accordance with claim 8 wherein said threshold is a constant.

10. Apparatus in accordance with claim 8 wherein said threshold is adjustable.

11. A video encoder comprising

motion estimating means for generating estimates of the frame-to-frame motion of each block of input pels in a current video frame;

video coding means for coding the differences between the input pels in the current video frame and motion compensated pels from a previous frame; and

multiplexing means for multiplexing these coded pel differences and the estimates of the frame-to-frame motion of each block of input pels from the current video frame;

wherein said motion estimating means comprises

means for forming for each block of input pels a corresponding search window in a previous frame that surrounds the position of the block of input pels;

means for pel-by-pel comparing the intensities of the pels in one input block in the current frame with the intensities of the pels in a block within the corresponding search window in the previous frame;

means for determining from each comparison that each pel is a matching pel if the difference between intensities is less than or equal to a threshold and is a mismatching pel if the difference is greater than said threshold;

means for counting the number of matching pels or the number of mismatching pels;

means for selecting another block of pels within that same search window for pel-by-pel comparisons; and

means for estimating the relative motion of the input block in the current frame from its position within its corresponding search window in the previous frame in response to the block in the previous frame at which the number of matching pels is highest or the number of mismatching pels is lowest.

12. A video encoder in accordance with claim 11 wherein said threshold is a predetermined constant.

13. A video encoder in accordance with claim 11 further comprising buffer means connected to the output of said multiplexer.

14. A video encoder in accordance with claim 13 where said threshold is determined by the fullness of said buffer means.