Method and apparatus for reducing the processing time required in motion vector detection

• US 6,160,900 A
• Filed: 02/02/1995
• Issued: 12/12/2000
• Est. Priority Date: 02/04/1994
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Ogawa, Katsuhisa, Miyawaki, Mamoru
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/382,533
• Time in Patent Office: 2,140 Days
• Field of Search: 382/213, 382/236, 382/107, 382/251, 382/253, 348/402, 348/407, 348/413, 348/416, 348/699, 348/208, 348/452, 348/420, 348/409, 348/700, 348/415, 348/443, 348/390
• US Class Current: 382/107
• CPC Class Codes: G01S 3/7865 using correlation of the live video image with a stored image
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• 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 data processing method investigates second data series of a second data group relative to a first data series in a first data group to reduce processing requirements of motion vector detection. The method includes a first step for selecting an area including the second data series of the second data group based on a determination condition as to whether a function of a difference between the first data series and the second data series is within a first desired value and a second step for further selecting other data series in the selected area based on another determination condition as to whether a function of a difference between the other data series in the defined area and the first data series is within a second desired value less than the first desired value.

Claims

1. A method for investigating a second data series, corresponding to a first data series in a first data group, from a second data group including the second data series, said method comprising:

a first selecting step of selecting, from the second data group, a first investigation area;

a first thinning step of thinning out data elements in the first investigation area by a first thin out quantity to thereby provide a plurality of first comparing data series;

a first comparing step of comparing the first data series with each of the first comparing data series by calculating respective differences between data elements in the first data series and respective data elements in each of the first comparing data series, comparing each such difference with a first predetermined value to provide first quantized data, and selecting at least one of the plurality of first comparing data series based on the first quantized data;

a second selecting step of selecting, from the second data group, a second investigation area including the selected first comparing data series and excluding any non-selected first comparing data series;

a second thinning step of thinning out data elements in the second investigation area by a second thinning out quantity to thereby provide a plurality of second comparing data series, the second thinning out quantity being no greater than the first thinning out quantity; and

a second comparing step of comparing the first data series with each of the second comparing data series by calculating respective differences between data elements in the first data series and respective data elements in each of the second comparing data series, comparing each such difference with a second predetermined value not greater than the first predetermined value to provide second quantized data, and selecting a final data series including at least one of the plurality of second comparing data series based on the second quantized data.

2. A method according to claim 1, wherein said method is applied in movement detection of an image.

3. A method according to claim 1, wherein the first data group and the second data group contain respective image data different in time.

4. A method according to claim 3, wherein the image data in each group was obtained from a series of arithmetic operations on adjacent pixels.

5. A method according to claim 1, wherein the first data group and the second data group contain respective image data formed by different lenses.

6. A method according to claim 5, wherein said method produces a distance image.

7. A method according to claim 1, wherein said first comparing step selects the at least one of the plurality of first comparing data series based on a sum of the first quantized data, and wherein said second comparing step selects the final data series based on a sum of the second quantized data.

8. A semiconductor apparatus for investigating a second data series, corresponding to a first data series in a first data group, from a second data group including the second data series, said apparatus comprising:

first selecting means for selecting, from the second data group, a first investigation area;

first thinning means for thinning out data elements in the first investigation area by a first thin out quantity to thereby provide a plurality of first comparing data series;

first comparing means for comparing the first data series with each of the first comparing data series by calculating respective differences between data elements in the first data series and respective data elements in each of the first comparing data series, comparing each such difference with a first predetermined value to provide first quantized data, and selecting at least one of the plurality of first comparing data series based on the first quantized data;

second selecting means for selecting, from the second data group, a second investigation area including the selected first comparing data series and excluding any non-selected first comparing data series;

second thinning means for thinning out data elements in the second investigation area by a second thinning out quantity to thereby provide a plurality of second comparing data series, the second thinning out quantity being no greater than the first thinning out quantity; and

second comparing means for comparing the first data series with each of the second comparing data series by calculating respective differences between data elements in the first data series and respective data elements in each of the second comparing data series, comparing each such difference with a second predetermined value not greater than the first predetermined value to provide second quantized data, and selecting a final data series including at least one of the plurality of second comparing data series based on the second quantized data.

9. A semiconductor apparatus according to claim 8, wherein a circuit structure including said first selecting means, said first thinning means and said first comparing means is the same as a circuit structure including said second selecting means, said second thinning means and said second comparing means.

10. A semiconductor apparatus according to claim 9, wherein said circuit structure operates on digital data and analog data.

11. A semiconductor apparatus according to claim 9, wherein said circuit structure includes an insulating gate type field effect transistor having a plurality of floating gates.

12. A semiconductor apparatus according to claim 8, wherein said apparatus produces a distance image and comprises a distance image processing circuit, a RAM and a determination circuit incorporating said first selecting means, said first thinning means, said first comparing means, said second selecting means, said second thinning means and said second comparing means.

13. A semiconductor apparatus according to claim 8, wherein said first comparing means selects the at least one of the plurality of first comparing data series based on a sum of the first quantized data, and wherein said second comparing means selects the final data series based on a sum of the second quantized data.