Multi-layered real-time stereo matching method and system

• US 7,545,974 B2
• Filed: 01/22/2004
• Issued: 06/09/2009
• Est. Priority Date: 01/30/2003
• Status: Expired due to Fees

• Current Assignee: Postech Foundation
• Original Assignee: Postech Foundation
• Inventors: Jeong, Hong, Park, Sung Chan
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US10/761,193
• Publication Number:
  US 20040151380A1
• Time in Patent Office: 1,965 Days
• Field of Search: 382/154
• US Class Current: 382/154
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

In a multi-layered real-time stereo matching system with a systolic array, one scan line in one digital image of the left and the right digital image is compared with multiple scan lines in the other digital image of the left and the right digital image in real-time so that each pixel in the one scan line may be matched with a pixel in the multiple scan lines in the other digital image.

Claims

1. A multi-layered real-time stereo matching apparatus comprising:

a left and a right image acquisition unit for obtaining a left and a right image of an object on a spatial area from different positions;

an image processing unit for converting the left and the right image to a left and a right digital image; and

a multi-layered image matching unit, which includes a systolic array, for comparing one scan line in one of the left and the right digital image with multiple scan lines in the other of the left and the right digital image in real-time by using the systolic array so that each pixel in the one scan line matches another pixel in the multiple scan lines in the other digital image,

wherein the multi-layered image matching-unit receives pixels of the one scan line in the one digital image sequentially and receives pixels of the multiple scan lines in the other digital image at a time, and calculates a disparity between one pixel in the one scan line and said another pixel in the multiple scan lines,

wherein the systolic array includes a plurality of layers for receiving pixel data of the one scan line in the one digital image and receiving pixel data of the multiple scan lines in the other digital image one by one, wherein two adjacent layers exchange costs and active signals with each other and the multi layered image matching unit further includes an accumulator for accumulating data fed from the layers to generate the disparity,

wherein each of the layers has;

a first storing unit for storing pixels of the left digital image;

a second storing unit for storing pixels of the right digital image; and

a plurality of forward processors, stacks and backward processors for generating decision values and the disparity obtained from the left and the right digital image based on a clock signal,

wherein each of the backward processors of said each of the layers includes;

an OR gate for logically summing two active bit paths inputted from an upper and a lower backward processor in said each of the layers, two active bit paths inputted from an upper and a lower layer of said each of the layers and a recursive active bit path within said each of the backward processors to generate a logical sum of five active bit paths;

an activation register for storing the logical sum of five active bit paths;

a demultiplexor for demultiplexing the logical sum of five active bit paths based on a decision value fed from the stack; and

a tri-state buffer for outputting the decision value in case the logical sum of five active bit paths in the activation register is high, and

wherein said left and right digital images are left and right images of said object, and wherein matching the pixel in the one scan line with another pixel in the multiple scan lines enables location of the object in said spatial area so that the imprecision in location and direction of, or distortion caused by, said left and right image acquisition unit is prevented.

2. The apparatus of claim 1, wherein an activation register of all layers of which 0-th backward processor has a minimum cost is initialized to be activated and all activation registers of other backward processors are initialized to be inactivated.

3. The apparatus of claim 1, wherein the backward processor accumulates the decision values fed from the tri-state buffer on a step basis to provide an optimized disparity and an optimized layer number.

4. The apparatus of claim 3, wherein the backward processor uses the layer number to search a scan line from multiple scan lines of the other digital image that corresponds to one scan line of the one digital image and uses the optimized disparity to search a pair of pixels, the two pixels corresponding to each other in the right and the left digital image on a backward processing step basis.

5. The apparatus of claim 3, wherein the backward processor initializes the disparity to be 0 on a layer basis and adds on a step basis to the disparity the decision values fed from a backward processor which is located in the layer corresponding to the layer number fed on a step basis during a backward processing and has a processing element number same as the disparity value.

6. The apparatus of claim 1, wherein the imprecision in location and direction of, or the distortion caused by, said left and right image acquisition unit is prevented even though said left and right image acquisition unit are arranged such that the one scan line and the multiple scan lines are not parallel.