Multi-layered real-time stereo matching method and system

• US 20040151380A1
• Filed: 01/22/2004
• Published: 08/05/2004
• Est. Priority Date: 01/30/2003
• Status: Active Grant

• Current Assignee: Postech Foundation
• Original Assignee: Postech Foundation
• Inventors: Jeong, Hong, Park, Sung Chan
• Granted Patent: US 7,545,974 B2
• Time in Patent Office: Days
• US Class Current: 382/217
• 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 system comprising:

a left and a right image acquisition means for obtaining a left and a right image on a spatial area from different position;

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

a multi-layered image matching means 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 so that each pixel in the one scan line matches another pixel in the multiple scan lines in the other digital image.

2. The system of claim 1, wherein the multi-layered image matching means 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.

3. The system of claim 2, wherein the multi-layered image matching means includes:

a plurality of layers for receiving the one scan line in the one digital image and receiving 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

an accumulator for accumulating data fed from the layers to generate the disparity.

4. The system of claim 3, wherein each of the layers has:

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

a second storing means 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.

5. The system of claim 4, wherein each of the forward processors of said each of the layers contains:

a first multiplexor for determining a minimum cost among a recursive cost within said each of the forward processors and two costs fed from an upper and a lower layer of said each of the layers;

a first cost register for storing the minimum cost;

an absolute value calculator for calculating as a matching cost a difference between one of the pixels of the first image storing means and another pixel of the pixels of the second image storing means;

a first adder for adding the matching cost to the minimum cost to generate a first added cost,

a second multiplexor for deciding a minimum cost among the first added cost and two costs fed from an upper and a lower forward processor in said each of the layers;

a second cost register for storing the minimum cost fed from the second multiplexor, wherein the minimum cost is fed back to the first cost multiplexor as the recursive cost and also provided to the upper and the lower layer; and

a second adder for adding the minimum cost stored in the second cost register to an occlusion cost to provide a second added cost to the upper and the lower forward processor.

6. The system of claim 4, 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.

7. The system of claim 3, wherein each of the layers is inputted with pixels of one scan line of the one digital image and pixels of multiple scan lines of the other digital image.

8. The system of claim 5, wherein all the cost registers except a 0-th cost register in the forward processors in said each of the layers is initialized with maximum cost, respectively, and the second storing means is initialized based on the right digital image.

9. The system of claim 5, wherein, if a sum of a processing element number and a forward processing step number is an even number, said each of the forward processors decides a minimum cost among the recursive cost and two added costs obtained by adding the occlusion cost to said two costs fed from the upper and the lower forward processor in said each of the layers, respectively, to provide the minimum cost as a first decision value to a stack, and, if otherwise, said each of the forward processors determines another minimum cost among a cost obtained by adding an absolute pixel difference of the left and the right digital image to the first decision value and two costs of two forward processors of the upper and the lower layer to provide the minimum cost as a second decision value to the stack.

10. The system of claim 6, 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.

11. The system of claim 6, 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.

12. The system of claim 11, 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.

13. The system of claim 11, 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.

14. A multi-layered real-time stereo matching method, the method comprising the steps of:

(b) obtaining a left and a right digital image on a spatial area;

(b) comparing one scan line in one digital image of the left and the right digital image with multiple scan lines in the other digital image in a real-time to match each pixel in the one scan line with a pixel in the multiple scan lines.

15. The method of claim 14, wherein the step (b) includes the steps of:

(b1) determining a path of a minimum cost as a decision value based on pixel data of the one scan line and pixel data of the multiple scan lines;

(b2) calculating a disparity from the decision value;

and

(b3) using the disparity to find a pair of pixels from the left and the right digital image and calculating a distance from the disparity.