Method and apparatus for motion estimation in a video signal

• US 5,838,828 A
• Filed: 12/12/1995
• Issued: 11/17/1998
• Est. Priority Date: 12/12/1995
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Masaki, Ichiro, Mizuki, Marcelo M., Chandrakasan, Anantha, Horn, Berthold
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/570,889
• Time in Patent Office: 1,071 Days
• Field of Search: 382/106, 382/107, 382/236, 382/199, 382/200, 382/218, 382/222, 382/27, 348/154, 348/155, 348/407, 348/413, 348/431
• US Class Current: 382/236
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments

Abstract

A method and apparatus for motion estimation in a video signal includes an edge detector for generating present and reference binary edge bit maps and a binary block matcher for receiving the present and reference binary edge bit maps from the edge detector and for generating a motion vector for each of a plurality of blocks in the binary edge bit maps. By using binary edge bit map data to generate motion vectors, computational requirements are reduced. If the apparatus is provided as an integrated circuit, the technique of the present invention reduces cost, power requirements and size of the integrated circuit.

Claims

1. An apparatus for estimating motion of objects between a present image frame and a reference image frame, the apparatus comprising:

an edge detector having a first input port, a second input port, a first output port and a second output port, the edge detector for receiving the present image frame at the first input port, the reference image frame at the second input port and for providing at the first output port a present image binary edge map and for providing at the second output port a reference image binary edge map; and

a binary block matcher having a first input port coupled to the first output port of the edge detector, having a second input port coupled to the second output port of the edge detector and having an output port, the binary block matcher for receiving the present and reference image binary edge maps, each of the present and reference image binary edge maps having a like plurality of blocks, the binary block matcher for comparing each of the plurality of blocks of the present image binary edge map with each of the plurality of blocks of the reference image binary edge map and for generating a motion vector for each of the plurality of blocks of the present image binary edge map.

2. The apparatus of claim 1 wherein, for each of the plurality of blocks, the binary block matcher provides a corresponding current signal representative of a distortion value used to compute the motion vector.

3. The apparatus of claim 2 wherein the binary block matcher further comprises means for summing each of the current signals to provide an output current signal at the output thereof, wherein the output current signal is representative of the motion vector for the present frame.

4. The apparatus of claim 3 wherein the binary block matcher further comprises means for converting the output current signal to an output voltage at the output port of the binary block matcher.

5. The apparatus of claim 1 wherein the binary block matcher comprises a plurality of processing elements, each of the processing elements comprising:

a first register having a first input port and an output port, the first register for receiving a reference image signal on the first input port;

a second register having a first input port for receiving a present image signal and having a first output port;

a third register having a first input port coupled to the output port of the second register and having an output port, the third register for holding the present image signal fed thereto from the second register;

a current source having an output port coupled to an output port of the processing element; and

means, having a first input port coupled to the output port of the first register, having a second input port coupled to the output port of the third register and having an output port coupled to the current source, said means for providing a current signal at the output port of the processing element in response to a first one of the signals from the first or third registers having a predetermined value.

6. The processing element of claim 5 wherein the means for switching comprises:

a logic circuit having a first input port coupled to the output port of the first register, having a second input port coupled to the output port of the third register and having an output port, wherein in response to a first one of the signals from the first or third registers having a predetermined value, the logic circuit provides an output signal having a first value at the output port thereof and wherein in response to the logic circuit providing the output signal having the first value at the logic circuit output port, the current source provides an output current signal at an output port of the processing element.

7. The processing element of claim 6 further comprising a switch having a first terminal coupled to the output port of the logic circuit, having a second terminal coupled to an output port of the current source and having a third terminal coupled to the output port of the processing element, wherein in response to the logic circuit providing the output signal having a first value at the output port thereof, the switch is biased into a first state and in response to the logic circuit providing the output signal having a second value at the output port thereof, the switch is biased into a second state.

8. The processing element of claim 7 wherein:

the first register is provided as a single bit register and the image signal is provided as a single bit signal;

the second register is provided as a single bit register and the reference signal is provided as a single bit signal; and

the third register is provided as a single bit register and in response to a control signal, the second register transfers the single bit signal stored therein to the third register.

9. A processing element for a binary block matcher, the processing element comprising:

a first register having a first input port and an output port, the first register for receiving a reference image signal on the first input port;

a second register having a first input port for receiving a present image signal and having a first output port;

a third register having a first input port coupled to the output port of the second register and having an output port, the third register for holding the present image signal fed thereto from the second register;

a current source having an output port coupled to an output port of the processing element; and

means, having a first input port coupled to the output port of the first register, having a second input port coupled to the output port of the third register and having an output port coupled to the current source, said means for providing a current signal at the output port of the processing element in response to a first one of the signals from the first or third registers having a predetermined value.

10. The processing element of claim 9 wherein the means for switching comprises:

a logic circuit having a first input port coupled to the output port of the first register, having a second input port coupled to the output port of the third register and having an output port, wherein in response to a first one of the signals from the first or third registers having a predetermined value, the logic circuit provides an output signal having a first value at the output port thereof and wherein in response to the logic circuit providing the output signal having the first value at the logic circuit output port, the current source provides an output current signal at an output port of the processing element.

11. The processing element of claim 10 further comprising a switch having a first terminal coupled to the output port of the logic circuit, having a second terminal coupled to an output port of the current source and having a third terminal coupled to the output port of the processing element, wherein in response to the logic circuit providing the output signal having a first value at the output port thereof, the switch is biased into a first state and in response to the logic circuit providing the output signal having a second value at the output port thereof, the switch is biased into a second state.

12. The processing element of claim 11 wherein:

the first register is provided as a single bit register and the image signal is provided as a single bit signal;

the second register is provided as a single bit register and the reference signal is provided as a single bit signal; and

the third register is provided as a single bit register and in response to a control signal, the second register transfers the single bit signal stored therein to the third register.

13. A method of estimating motion of a moving object in a scene comprising the steps of:

(a) generating an edge bit map for each of a reference image frame and a present image frame;

(b) segmenting the reference image frame into a plurality of blocks, each of the blocks including the same number of pixels;

(c) segmenting the present image frame into a plurality of blocks, each of the blocks having including the same number of pixels;

(d) specifying the size of a search window area in the present frame;

(e) changing the relative position between a block of the present image frame and each of the plurality of blocks of the reference image frame within the search window area;

(f) computing a correlation value for each relative position of the block of the present image frame and the plurality of blocks of the reference image frame within the search window area; and

(g) providing a motion vector for each block of the present image frame.

14. The method of claim 13 wherein the step of computing the correlation value includes the steps of:

combining each of the plurality of blocks of the present image binary edge bit map with a corresponding one of the plurality of blocks of the reference image binary edge bit map with exclusive OR logic;

generating an exclusive OR output signal for each of the plurality of blocks combined in the combining step; and

summing the results of the combined blocks of the present image binary edge bit map and the blocks of the reference image binary edge bit map to provide an output value corresponding to the correlation value.

15. The method of claim 14 further comprising the step of comparing the computed correlation value to a threshold correlation value and wherein in response to the computed correlation value being lower than the threshold correlation value, performing the step of ignoring the correlation value and in response to the computed correlation value being greater than the threshold correlation value, performing the step of saving the correlation value.

16. An integrated circuit comprising:

a processing element array comprising a plurality of processing elements, each of the processing elements comprising;

a first register having a first input port for receiving a reference image signal and having an output port;

a second register having a first input port for receiving a present image signal and having a first output port;

a third register having a first input port coupled to the output port of the second register and having an output port, the third register for holding the present image signal fed thereto from the second register;

a current signal source having an output port coupled to an output port of the processing element; and

means, having a first input port coupled to the output port of the first register, having a second input port coupled to the output port of the third register and having an output port coupled to the current signal source, said means for providing a current signal at the output port of the processing element in response to a first one of the signals from the first or third registers having a predetermined value;

a plurality of input registers coupled to a first ones of the plurality of processing elements in a first column of the processing element array;

a first plurality of processing registers coupled to second ones of the plurality of processing elements in a first row of the processing element array;

a second plurality of processing registers, coupled to third ones of the plurality of processing elements in a second row of the processing element array; and

a summing circuit, having a plurality of input ports and an output port, each of the plurality of input ports coupled to a row of processing elements in said processing element array, said summing circuit for receiving a current signal from each row of processing elements and for providing a distortion signal at the output port thereof.

17. The integrated circuit of claim 16 further comprising a comparator circuit for comparing a first distortion signal provided by said summing circuit in response to a first reference image signal being stored in said first register and a second distortion signal provided by said summing circuit in response to a second reference signal being stored in said first register.

18. The integrated circuit of claim 16 wherein the first and second distortion signals are each provided as current signals.

19. The integrated circuit of claim 18 wherein said input register, said first plurality of processing registers and said second plurality of processing registers are provided having a predetermined number of memory elements wherein the number of memory elements is selected to store a number of binary bit image data values corresponding to a maximum expected shift of a present image block relative a reference point in a reference image block.

20. The integrated circuit of claim 19 wherein the means for providing an output current signal comprises a logic circuit having a first input port coupled to the output port of said first register, having a second input port coupled to the output port of said third register and having an output port, wherein:

in response to a first one of the signals from said first or third registers having a predetermined value, said logic circuit provides an output signal having a first value at the output port thereof; and

in response to said logic circuit providing the output signal having the first value at the logic circuit output port, said current signal source provides an output current signal at an output port of said processing element.