PATENT DOCUMENT

Abstract:
Disclosed is a stereo image matching method for re-creating 3-dimensional spatial information from a pair of 2-dimensional images. The conventional stereo image matching method generates much noise from a disparity value in the vertical direction, but the present invention uses disparity information of adjacent image lines as a constraint condition to eliminate the noise in the vertical direction, and compress the disparity by using a differential coding method to thereby increase a compression rate.

Full Description:
CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    This application is a divisional application of U.S. patent application Ser. No. 11/032,253 filed on Jan. 10, 2005, which claims priority of Korea Patent Application No. 10-2004-72531 filed on Sep. 10, 2004, in the Korean Intellectual Property Office, the disclosures of which are incorporated herein by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    (a) Field of the Invention 
         [0003]    The present invention relates to a stereo image matching method and system using image multiple lines. More specifically, the present invention relates to a systolic architecture based stereo image matching method and system for multiple epipolar stereo image matching. 
         [0004]    (b) Description of the Related Art 
         [0005]    The stereo image matching method represents a method for re-creating 3-dimensional spatial information from a pair of 2-dimensional images. As shown in  FIG. 1 , the stereo image matching method indicates a method for finding left and right pixels corresponding to the same position of (X, Y, Z) in the 3-dimensional space on image lines on the left image epipolar line and the right image epipolar line. In this instance, a disparity of “d” for the conjugate pixel pair is defined to be d=x r −x i . The disparity has distance information, and a geometrical distance calculated from the disparity is referred to as a depth. Hence, 3-dimensional distance information and shape information on an observation space can be measured by calculating the disparity in real-time from an input image. 
         [0006]    An article of “Structure from stereo” by Umesh R. Dhond and J. K. Aggarwal from a Review, IEEE Transactions on Systems, Man, and Cybernetics, 19(6):553-572, November/December 1989 discloses the basic concept, and a US published application of No. 2002-0025075 discloses a stereo image matching realization system. 
         [0007]    In the above-noted prior art as shown in  FIG. 12 , much noise is generated in the vertical direction since the image lines g ml  and g mr  on the m th  right and left epipolar lines are independently calculated. That is, the disparity in the vertical direction on the disparity image is not accurately displayed because of an influence of noise. When the left image of  FIG. 13A  and the right image of  FIG. 13B  are input, the image with much noise is displayed as shown in  FIG. 13D . 
       SUMMARY OF THE INVENTION 
       [0008]    The present invention provides a stereo image matching method for reducing vertical disparity noise. 
         [0009]    In the present invention, the disparity of image lines is used. 
         [0010]    In one aspect of the present invention, a stereo image matching system using image lines comprises: an image processor for converting images input by first and second cameras into digital signals, and outputting first and second pixel data; and an image matcher for determining a predetermined cost from the first and second pixel data on the same epipolar line, tracking a first decision value for determining the predetermined cost, and using the first decision value estimated from the first and second pixel data to output a second decision value. 
         [0011]    The first and second pixel data are pixel data of left and right image lines on the same epipolar line. 
         [0012]    The image matcher may comprise: a first input buffer and a second input buffer for respectively arranging the first and second pixel data, and outputting them; and a processing element array for receiving the first and second pixel data from the first and second input buffers, and tracking the first and second decision values. 
         [0013]    The processing element array may comprise: a plurality of first image registers for sequentially receiving the first pixel data; a plurality of second image registers for sequentially receiving the second pixel data; and a plurality of processing elements for receiving the first and second pixel data from the first and second registers, and tracking the first and second decision values. 
         [0014]    The processing element transmits and receives costs and activation signals to/from adjacent processing elements. 
         [0015]    The activation signal may comprise a multi-line processing activation signal for calculating a multi-line cost: and a backward processing activation signal of adjacent processing elements. 
         [0016]    The processing element may comprise: a forward processor for determining a cost from the first and second pixel data and the multi-line processing activation signal, and calculating the first decision value for representing the determined cost; a stack for storing the first decision value; and a backward processor for using the first decision value on the adjacent epipolar line and the backward processing activation signal and calculating the second decision value. 
         [0017]    Costs of cost registers of forward processors excluding the 0 th  forward processor are established to be maximum when the forward processors are reset. 
         [0018]    Input orders of the first and second pixel data input to the first and second image registers are different according to the condition whether image lines on the epipolar lines corresponding to the input first and second pixel data are odd or even in the images. 
         [0019]    In another aspect of the present invention, a stereo image matching method using image lines, comprises: receiving left and right pixel data from left and right cameras; arranging left and right pixel data of image lines on epipolar lines, and sequentially outputting them to a plurality of first and second image registers; allowing the forward processors to determine predetermined costs from the left and right pixel data output by the first and second image registers and track a first decision value for determining the costs; and allowing the backward processors to output a second decision value which is an optimal decision value from the first decision value for the adjacent image line, wherein the forward processors and the backward processors are concurrently performed. 
         [0020]    In still another aspect of the present invention, a stereo image matching method using image lines comprises: receiving left and right pixel data from left and right cameras; arranging left and right pixel data of image lines on epipolar lines, and sequentially outputting them to a plurality of first and second image registers; allowing the forward processors to determine predetermined costs from the left and right pixel data output by the first and second image registers and track a first decision value for determining the costs; and allowing the backward processors to output a second decision value which is an optimal decision value from the first decision value for the adjacent image line, wherein the backward processors are performed after the forward processors are performed, and the forward processors and the backward processors can be performed at high speed due to the pipeline architecture. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0021]    The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate an embodiment of the invention, and, together with the description, serve to explain the principles of the invention: 
           [0022]      FIG. 1  shows a stereo image matching diagram of the prior art; 
           [0023]      FIG. 2  shows a block diagram of a stereo image matching system according to a first exemplary embodiment of the present invention; 
           [0024]      FIG. 3  shows a block diagram of a multi-line stereo image matcher of the stereo image matching system according to a first exemplary embodiment of the present invention; 
           [0025]      FIG. 4  shows a block diagram of an input buffer shown in  FIG. 3 ; 
           [0026]      FIG. 5  shows a detailed block diagram of the multi-line stereo image matcher of  FIG. 3 ; 
           [0027]      FIG. 6  and  FIG. 7  show a forward processor and a backward processor of  FIG. 5  respectively; 
           [0028]      FIG. 8  and  FIG. 9  respectively show a flowchart for the stereo image matching system according to the first exemplary embodiment to process pixel data of an even image line and a flowchart for the stereo image matching system to process pixel data of an odd image line; 
           [0029]      FIG. 10  shows a forward processing and backward processing flowchart in the stereo image matching method according to a second exemplary embodiment of the present invention; 
           [0030]      FIG. 11  shows a stereo image matching method according to an exemplary embodiment of the present invention; 
           [0031]      FIG. 12  shows a conventional stereo image matching method; 
           [0032]      FIG. 13A  and  FIG. 13B  show a left image and a right image respectively; and 
           [0033]      FIG. 13C  and  FIG. 13D  show results of processing the images of  FIG. 13A  and  FIG. 13B  using the method of  FIG. 11  and  FIG. 12 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0034]    In the following detailed description, only an exemplary embodiment of the invention has been shown and described, simply by way of illustration of the best mode contemplated by the inventor(s) of carrying out the invention. As will be realized, the invention is capable of modification in various obvious respects, all without departing from the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not restrictive. To clarify the present invention, parts which are not described in the specification are omitted, and parts for which similar descriptions are provided have the same reference numerals. 
         [0035]    A stereo image matching method and system using a plurality of image lines according to exemplary embodiments of the present invention will be described with reference to drawings. 
         [0036]    A stereo image matching system using image lines according to a first exemplary embodiment of the present invention will be described with reference to  FIGS. 2 to 7 . 
         [0037]      FIG. 2  shows a block diagram of a stereo image matching system according to a first exemplary embodiment of the present invention.  FIG. 3  shows a block diagram of a multi-line stereo image matcher of the stereo image matching system according to the first exemplary embodiment of the present invention.  FIG. 4  shows a block diagram of an input buffer shown in  FIG. 3 .  FIG. 5  shows a detailed block diagram of the multi-line stereo image matcher of  FIG. 3 .  FIGS. 6 and 7  show a forward processor and a backward processor of  FIG. 5  of the diagram respectively. 
         [0038]    As shown in  FIG. 2 , the stereo image matching system comprises a left camera  110 , a right camera  120 , an image processor  200 , a multi-line image matcher  300 , and a user system  400 . The left and right cameras  110  and  120  take left and right images of a subject, and transmit the image signals to the image processor  200 . The image processor  200  converts the left and right image signals into digital signals, and outputs the same. The multi-line image matcher  300  calculates a decision value from the digital image signals provided by the image processor  200 , and outputs a disparity value. The user system  400  receives a distance image caused by the disparity value output by the multi-line image matcher  300 , and uses it for subsequent processes. 
         [0039]    Referring to  FIG. 3 , the multi-line image matcher  300  includes two input buffers  310 , a processing element array  320 , and an encoder  330 . The input buffers  310  respectively receive left image signals and right image signals (pixel data), rearrange the pixel data according to a control signal, and output the rearranged pixel data. The processing element array  320  uses disparity values of adjacent image lines to find the disparity of the input pixel data, and the encoder  330  converts the disparity values into an appropriate format and outputs result signals. 
         [0040]    The multi-line image matcher  300  sequentially receives pixel data of left and right images on the epipolar lines, calculates a disparity value, and outputs the disparity value, and this process of outputting the disparity value is repeatedly performed for the image lines on the epipolar lines of a pair of images. 
         [0041]    Referring to  FIG. 4 , the input buffer  310  of  FIG. 2  includes a multiplexer  311 , two line buffers  312  and  313 , a demultiplexer  314 , two address generators  315  and  316 , and a controller  317 . The multiplexer  311  outputs the pixel data to one of the line buffers  312  and  313  according to control by the controller  317 . The two address generators  315  and  316  select data to be output from among the data stored in the line buffers  312  and  313  according to control by the controller  317 . The demultiplexer  314  selects one of the pixel data output by the line buffers  312  and  313  and outputs the same according to control by the controller  317 . 
         [0042]    Referring to  FIG. 3  and  FIG. 5 , the processing element array  320  of  FIG. 2  includes N/2 left image registers  321  (I 2  to I N/2 ), N/2 right image registers r N/2−1  to r 1 , N forward processors  323  (fp 1  to fP N ), N backward processors  324  (bp 1  to bP N ), and N stacks  325 . The forward processors  323 , the backward processors  324 , and the stacks  325  form processing elements which are provided in a linear array format up to the designated maximum disparity, and each of which exchanges information with adjacent processing elements and processes it in parallel. The above-noted configuration allows a full-speed operation irrespective of a number of processing elements. 
         [0043]    Pixel data on the left image epipolar line are input to the left image register I 1  through the input buffer  310  according to a sync signal, and the pixel data input to the left image register I 1  are sequentially shifted to the subsequent left image registers I 2  to I N/2 . In a like manner, pixel data on the right image epipolar line are input to the right image register r N/2  through the input buffer  310 , and the pixel data input to the right image register r N/2  are sequentially shifted to the subsequent right image registers r N/2−1  to r 1 . As shown in  FIG. 3 , a left image register I n  and a right image register r n  are formed to correspond to two forward processors fp j  and fp j-1 . 
         [0044]    Referring to  FIGS. 6 and 7 , the j th  processing element (1≦j≦N) in the processing element array  320  of  FIG. 5  will now be described. 
         [0045]    Referring to  FIG. 6 , the forward processor  323  fp j  includes an absolute value calculator  323   a , a multi-line cost memory  323   b , adders  323   c  and  323   d , a multiplexer  323   e , a cost register  323   f , adders  323   g  and  323   h , and a controller  323   i . The forward processor  323  fp j  receives pixel data of the left and right image lines on the epipolar lines according to clock signals t, calculates a decision value, and stores the decision value in the stack  325 . 
         [0046]    The absolute value calculator  323   a  receives pixel data from the left and right image registers  321  and  322 , and uses the absolute value of a difference between the pixel data 
         [0000]    
       
         
           
             
               L 
               n 
             
             ( 
             
               g 
               
                 
                   1 
                   2 
                 
                  
                 
                   ( 
                   
                     t 
                     - 
                     j 
                     - 
                     1 
                   
                   ) 
                 
               
               l 
             
             ) 
           
         
       
     
         [0000]    of the left image and the pixel data 
         [0000]    
       
         
           
             
               R 
               n 
             
             ( 
             
               g 
               
                 
                   1 
                   2 
                 
                  
                 
                   ( 
                   
                     t 
                     + 
                     j 
                     - 
                     1 
                   
                   ) 
                 
               
               r 
             
             ) 
           
         
       
     
         [0000]    of the right image to calculate a matching cost. The multi-line cost memory  323   b  determines a multi-line cost by using activation signals [a j−λ , a j+λ ] for multi-line processing, and outputs the multi-line cost. The multi-line cost memory  323   b  outputs a small cost in the case of an activation signal of a near processing element, and outputs a big cost in the case of an activation signal of a far processing element, which will be described with reference to  FIG. 7 . 
         [0047]    The adder  323   c  adds a cost U j (t−2) which is fed back from the cost register  323   f  and is in advance of two clock signals and a multi-line cost output by the cost memory  323   b , and the adder  323   d  adds a matching cost of the absolute value calculator  323   a  to the value added by the adder  323   c.    
         [0048]    The multiplexer  323   e  concurrently outputs the least cost from among costs U j+1 (t−1)+γ and U j−1 (t−1)+γ which are output by the (j+1) th  forward processor  323  and the (j−1) th  forward processor  323  and are in advance of one clock signal, and an output U j (t−1) of the adder  323   d  according to control by the controller  323   h , and outputs a decision value of V t,j  which represents a path of the least cost. The adder  323   g  adds a multi-line cost of the multi-line cost memory  323   b  to the output of the multiplexer  323   e , and outputs the added result as a cost U j (t) of the current clock signal so that the cost U j (t) may be stored in the cost register  323   f . The adder  323   h  adds an occlusion cost γ to the cost U j (t−2) which is output by the cost register  323   f  and is in advance of two clock signals, and outputs the added result to the adjacent (j+1) th  and (j−1) th  forward processors  323 . 
         [0049]    Referring to  FIG. 7 , the backward processor  324  (bp j ) of  FIG. 5  includes an OR gate  324   a , a one-bit activation register  324   b , a D buffer  324   c , a demultiplexer  324   d , a tri-state buffer  324   e , and a controller  324   f . The backward processor  324  operates the decision value read from the stack  325 , calculates a disparity value, and outputs the disparity value according to clock signals. 
         [0050]    The OR gate  324   a  receives activation signals a j+1 (t−1)δ(1+V t−1,j+1 ) and a j−1 (t−1)δ(1−V t−1,j−1 ) of the adjacent (j+1) th  and (j−1) th  backward processors  324  and an activation signal a j (t)δ(V t,j ) which is fed back from the demultiplexer  324   d . An output of the OR gate  324   a  is stored in the activation register  324   b  as an activation bit value a j (t+2) after two clock signals according to control by the controller  323   f . An output a j (t) of the activation register  324   b  is stored in the D buffer  324   c , and the D buffer  324   c  outputs the activation bit value after k clock signals are counted. As described, the D buffer  324   c  receives the activation bit value and outputs it as a multi-line activation signal which is used to be synchronized with the backward processor when the multi-line activation signal is input to the forward processor  323  for receiving a multi-line processing activation signal. 
         [0051]    The demultiplexer  324   d  demultiplexes the data input by the activation register  324   b  according to the decision value of V t,j  input by the forward processor  323  through the stack  325 , outputs backward processing activation signals a j (t)δ(1−V t,j ) and a j (t)δ(1+V t,j ) to the adjacent backward processor  324 , and feeds the activation signal a j (t)δ(V t,j ) back to the OR gate  324   a . The tri-state buffer  324   e  receives the decision value of V i,j  from the stack  325 , and outputs an optimal decision value of V* t,j  which represents increment/decrement of disparity according to an output by the activation register  324   b . The tri-state buffer  324   e  outputs the input value when the activation bit value a j (t) is given to be 1, and the tri-state buffer  324   e  becomes a high impedance state and outputs no value when the activation bit value a j (t) is not 1. 
         [0052]    The addition of decision values V* t,j  output by the backward processor bp j  produces a disparity value, and since the disparity value is gradually changed depending on the variation of decision values, the compression rate can be increased by a differential-coding compression method. That is, the encoder  330  can output the decision value of V* t,j  without outputting the disparity value added with the decision value of V* t,j . 
         [0053]    The decision value of V* t,j  represents variations of the path to thus have three values of no path variation, upward path-variation, and downward path variation, and hence, the decision value of V* t,j  are represented as 00, 01, and 10 in two bits, and 00 is a dummy bit. Two decision values of V* t,j  and V* t−1,j  require four bits, and in this instance, 0110 and 1001 can be considered to belong to the same case as that of 0000 since 0110 and 1001 have a very rare probability of geometric existence. Therefore, as given in Table 1, the two decision values can be represented in three bits by processing the dummy data and encoding them. Also, flag data are allowed since a number can be assigned as a flag. 
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 V* t, j   
                 V* t−1, j   
                 Outputs 
               
               
                   
               
             
             
               
                 00 
                 00 
                 0 
               
               
                 00 
                 01 
                 1 
               
               
                 00 
                 10 
                 2 
               
               
                 01 
                 00 
                 3 
               
               
                 01 
                 01 
                 4 
               
               
                 01 
                 10 
                 0 
               
               
                 10 
                 00 
                 5 
               
               
                 10 
                 01 
                 0 
               
               
                 10 
                 10 
                 6 
               
               
                 flag 
                 flag 
                 7 
               
               
                   
               
             
          
         
       
     
         [0054]    Referring to  FIG. 8  and  FIG. 9 , a stereo image matching method in the stereo image matching system using plural image lines will be described in detail. The 0 th  to (N−1) th  processing elements are operated in parallel when the clock signals are counted from 0 to 2N in the first exemplary embodiment, and  FIG. 8  and  FIG. 9  will illustrate the j th  processing element for ease of description. 
         [0055]    In order to use the disparity value of the line in the processing element and control the backward processor bp j  and the forward processor fp j  to be concurrently operated in the first embodiment, performance of hardware is differed according to the state in which image lines on the epipolar lines are odd or even from among the total images so as to synchronize the multi-line processing activation signal and the forward processor since the multi-line processing activation signal is differed by the output of the decision value. Therefore, the input buffer  310  differently arranges the order of pixel data depending on whether the index of an image line is odd or even. 
         [0056]    The pixel data of even image lines will be described with reference to  FIG. 8 , and the pixel data of odd image lines will be described with reference to  FIG. 9 . 
         [0057]      FIG. 8  and  FIG. 9  respectively show a flowchart for the stereo image matching system according to the first exemplary embodiment to process pixel data of an even image line and a flowchart for the stereo image matching system to process pixel data of an odd image line. 
         [0058]    The case in which pixel data of an even image line are input will be described with reference to  FIG. 8 . A cost U j (0), jε[1,N] when the processing element is reset at the 0 th  clock (i=0) is given in Equation 1 in step S 810 . 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           0 
                         
                         
                           
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 j 
                               
                               = 
                               0 
                             
                             , 
                           
                         
                       
                       
                         
                           ∞ 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   1 
                 
               
             
           
         
       
     
         [0059]    Referring to  FIG. 5 , the left image register I 1  and the right image register r N/2  sequentially receive left and right image pixel data from the input buffers  311  and  312 , and the left and right image registers I 1  to I N/2  and r 1  to r N/2  shift the pixel data to the adjacent image registers I 1  to I N/2  and r 1  to r N/2  in step S 820 . 
         [0060]    The processing element is differently operated depending on whether the sum (i+j) of the i th  current clock signal and the position j of the processing element is odd or even. The forward processor fp j  processes the pixel data of the current input image line, and the backward processor bp j  reads a decision value processed by the forward processor fp j  from the stack  325  and processes the decision value. It will be defined below that the backward processor bp j  is operated in advance to the forward processor fp j . Accordingly, since the forward processor fp j  can write the decision value on the position which the backward processor bp j  read in the stack  325 , it is allowed for the decision value of a previous line and a decision value of a current line to share a stack. Therefore, the cost and the decision value which are output by the forward processor fp j  of the i th  current clock signal are represented to be U j (i) and V i,j  respectively, and the activation signal and the disparity which are output by the backward processor bp j  are represented to be a j (i+1) and {circumflex over (d)}(i+1) respectively. 
         [0061]    The operation of the above-noted processing element will be described in detail for a case in which the sum of (i+j) is odd and a case in which the sum of (i+j) is even. 
         [0062]    The controller  323   i  of the forward processor fp j  and the controller  324   f  of the backward processor bp j  determine whether the sum of the i th  clock signal and the position j of the processing element is odd or even in step S 830 . 
         [0063]    The controller  323   i  of  FIG. 6  controls to output U j (t−1) as a cost in step S 841  when the sum of (i+j) is found to be odd, and the controller  323   i  controls to output U j (t) as a cost in step S 842  when the sum of (i+j) is found to be even. 
         [0064]    In detail, since the output U j (t−1) of the adder  323   d  of the forward processor fp j  becomes a cost when the sum of (i+j) is odd, the cost U j (i) at the i th  clock signal is generated by adding a difference of left and right pixel data to the cost U j (i−1) at the previous clock signal and adding a multi-line cost thereto. The multi-line cost is given in Equation 2, the controller  323   i  receives a multi-line processing activation signal a j+p (i) calculated by the backward processor  324 , and outputs η|p| when |p| is less than λ, and outputs ηλ when |p| is greater than λ. The multi-line cost is used as a constraint condition for matching since it is calculated and output in consideration of the difference between the position (j+p) of the processing element of the input activation signal a j+p (i) and the position j of the forward processing fp j . 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         p 
                         ∈ 
                         
                           [ 
                           
                             
                               - 
                               λ 
                             
                             , 
                             λ 
                           
                           ] 
                         
                       
                     
                      
                     
                       η 
                        
                       
                          
                         p 
                          
                       
                        
                       
                         
                           a 
                           
                             j 
                             + 
                             p 
                           
                         
                          
                         
                           ( 
                           i 
                           ) 
                         
                       
                     
                   
                   + 
                   
                     η 
                      
                     
                         
                     
                      
                     
                       λδ 
                       ( 
                       
                         
                           ∑ 
                           
                             p 
                             ∈ 
                             
                               [ 
                               
                                 
                                   - 
                                   λ 
                                 
                                 , 
                                 λ 
                               
                               ] 
                             
                           
                         
                          
                         
                           
                             a 
                             
                               j 
                               + 
                               p 
                             
                           
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   2 
                 
               
             
           
         
       
     
         [0065]    where λ is a range in which the multi-line processing activation signal a j+p (i) is transmitted to a near processing element, and η determines a scale of the multi-line cost value. 
         [0066]    The cost U j (i) at the i th  clock signal is given in Equation 3 considering the multi-line cost, and the decision value in this instance is given to be 0. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         U 
                         j 
                       
                        
                       
                         ( 
                         
                           i 
                           - 
                           1 
                         
                         ) 
                       
                     
                     + 
                     
                        
                       
                         
                           g 
                           
                             
                               1 
                               2 
                             
                              
                             
                               ( 
                               
                                 i 
                                 - 
                                 j 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           l 
                         
                         - 
                         
                           g 
                           
                             
                               1 
                               2 
                             
                              
                             
                               ( 
                               
                                 i 
                                 + 
                                 j 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           r 
                         
                       
                        
                     
                     + 
                     
                       
                         ∑ 
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 λ 
                               
                               , 
                               λ 
                             
                             ] 
                           
                         
                       
                        
                       
                         η 
                          
                         
                            
                           p 
                            
                         
                          
                         
                           
                             a 
                             
                               j 
                               + 
                               p 
                             
                           
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                     
                     + 
                     
                       η 
                        
                       
                           
                       
                        
                       
                         λδ 
                         ( 
                         
                           
                             ∑ 
                             
                               p 
                               ∈ 
                               
                                 [ 
                                 
                                   
                                     - 
                                     λ 
                                   
                                   , 
                                   λ 
                                 
                                 ] 
                               
                             
                           
                            
                           
                             
                               a 
                               
                                 j 
                                 + 
                                 p 
                               
                             
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   3 
                 
               
             
           
         
       
     
         [0067]    When the sum (i+j) is even, the output U j (t−1) of the adder  323   g  of the forward processor fp j  becomes a cost. Therefore, the cost U j (i) at the i th  clock signal is given to be a value obtained by adding the multi-line cost of the cost memory  323   b  to the minimum value of U j+1 (i−1)+γ, U j (i−1), and U j−1 (i−1+γ as expressed in Equation 4. The decision value V i,j  is a value for representing a path of the least cost, given in Equation 5. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         min 
                         
                           
                             p 
                             ∈ 
                             
                               [ 
                               
                                 
                                   - 
                                   1 
                                 
                                 , 
                                 1 
                               
                               ] 
                             
                           
                           , 
                           
                             
                               j 
                               + 
                               p 
                             
                             ∈ 
                             
                               [ 
                               
                                 0 
                                 , 
                                 N 
                               
                               ] 
                             
                           
                         
                       
                        
                       
                         { 
                         
                           
                             
                               U 
                               
                                 j 
                                 + 
                                 p 
                               
                             
                              
                             
                               ( 
                               
                                 i 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           + 
                           
                             γ 
                              
                             
                                 
                             
                              
                             
                               p 
                               2 
                             
                           
                         
                         } 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 λ 
                               
                               , 
                               λ 
                             
                             ] 
                           
                         
                       
                        
                       
                         η 
                          
                         
                            
                           p 
                            
                         
                          
                         
                           
                             a 
                             
                               j 
                               + 
                               p 
                             
                           
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                     
                     + 
                     
                       η 
                        
                       
                           
                       
                        
                       
                         λδ 
                         ( 
                         
                           
                             ∑ 
                             
                               p 
                               ∈ 
                               
                                 [ 
                                 
                                   
                                     - 
                                     λ 
                                   
                                   , 
                                   λ 
                                 
                                 ] 
                               
                             
                           
                            
                           
                             
                               a 
                               
                                 j 
                                 + 
                                 p 
                               
                             
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   4 
                 
               
             
             
               
                 
                   
                     V 
                     
                       i 
                       , 
                       j 
                     
                     b 
                   
                   = 
                   
                     
                       arg 
                        
                       
                           
                       
                        
                       min 
                     
                     
                       
                         p 
                         ∈ 
                         
                           [ 
                           
                             
                               - 
                               1 
                             
                             , 
                             1 
                           
                           ] 
                         
                       
                       , 
                       
                         
                           j 
                           + 
                           p 
                         
                         ∈ 
                         
                           [ 
                           
                             0 
                             , 
                             N 
                           
                           ] 
                         
                       
                     
                   
                    
                   
                     { 
                     
                       
                         
                           U 
                           
                             j 
                             + 
                             p 
                           
                         
                          
                         
                           ( 
                           
                             i 
                             - 
                             1 
                           
                           ) 
                         
                       
                       + 
                       
                         γ 
                          
                         
                             
                         
                          
                         
                           p 
                           2 
                         
                       
                     
                     } 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   5 
                 
               
             
           
         
       
     
         [0068]    where 
         [0000]    
       
         
           
             
               
                 arg 
                  
                 
                     
                 
                  
                 min 
               
               x 
             
              
             
               { 
               
                 f 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               } 
             
           
         
       
     
         [0000]    is a function for outputting a parameter x for minimizing f(x). A decision value output by the forward processor for the pixel data of the even image line from among the decision values V i,j  will be denoted by V i,j   b , and a decision value output by the forward processor for the pixel data of the odd image line will be denoted by V a   i,j . 
         [0069]    The decision values V i,j  determined through the steps of S 841  and S 842  are stored in the stack  325 . 
         [0070]    The backward processor bp j  reads a decision value V 2N−i,j   a  processed by the forward processor fp j  from the stack  325 . The output of the activation register  324   b  becomes an activation signal a j (i+1) according to control by the controller  324   f  in  FIG. 7 . That is, the OR gate  324   a  of  FIG. 7  performs an OR operation on an activation signal a j (i)δ(V 2N−i,j   a ) processed by the current backward processor bp j  at the previous clock signal and activation signals a j−1 (i)δ(1−V 2N−i,j−1   a ) and a j+1 (i)δ(1+V 2N−i,j+1   a ) processed by the adjacent backward processors bp j−1  and bp j+1  at the previous clock signal, and outputs a result signal. The result signal becomes an activation signal a j (i+1) at the current clock signal as given in Equation 6. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                       j 
                     
                      
                     
                       ( 
                       
                         i 
                         + 
                         1 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         p 
                         ∈ 
                         
                           [ 
                           
                             
                               - 
                               λ 
                             
                             , 
                             λ 
                           
                           ] 
                         
                       
                     
                      
                     
                       
                         
                           a 
                           
                             j 
                             + 
                             p 
                           
                         
                          
                         
                           ( 
                           i 
                           ) 
                         
                       
                        
                       
                         δ 
                          
                         
                           ( 
                           
                             p 
                             + 
                             
                               V 
                               
                                 
                                   
                                     2 
                                      
                                     
                                         
                                     
                                      
                                     N 
                                   
                                   - 
                                   i 
                                 
                                 , 
                                 
                                   j 
                                   + 
                                   p 
                                 
                               
                               a 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   6 
                 
               
             
           
         
       
     
         [0071]    The tri-state buffer  324   e  receives the decision value V 2N−i,j   a  of the previous line from the stack  325 , and outputs an optimal decision value V 2N−i,j   a  for showing increment/decrement of disparity according to the activation bit a j (i+1) so that the sum of the decision values V 2N−i,j   a  becomes a disparity {circumflex over (d)}(i+1). The tri-state buffer  324   e  outputs a decision value V 2N−i,j   a  when the activation bit a j (i+1) is high (i.e., ‘1’), and the tri-state buffer  324   e  outputs a high-impedance signal so that an output by another backward processor may not be hindered when the activation bit a j (i+1) is low (i.e., ‘0’). Therefore, the disparity {circumflex over (d)}(i+1) is given in Equation 7. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       d 
                       ^ 
                     
                      
                     
                       ( 
                       
                         i 
                         + 
                         1 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         
                           [ 
                           
                             0 
                             , 
                             
                               N 
                               - 
                               1 
                             
                           
                           ] 
                         
                       
                     
                      
                     
                       
                         
                           a 
                           j 
                         
                          
                         
                           ( 
                           
                             i 
                             + 
                             1 
                           
                           ) 
                         
                       
                        
                       
                         V 
                         
                           
                             
                               2 
                                
                               
                                   
                               
                                
                               N 
                             
                             - 
                             i 
                           
                           , 
                           j 
                         
                         a 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   7 
                 
               
             
           
         
       
     
         [0072]    When the i th  current clock signal is not 2N in step S 850 , the i th  clock signal is increased by 1 in step S 860  to repeat the same processes of S 820 , S 830 , S 841 , and S 842 . Hence, the disparity for the pixel data of the current image line is calculated. 
         [0073]    Referring to  FIG. 9 , the case of inputting pixel data of an odd image line will be described. The processing element is reset at the 0 th  clock signal (i=0), and the cost U j (0), jε[1,N] at the reset is given in Equation 1 in step S 910 . 
         [0074]    Referring to  FIG. 4 , the left image register I 1  and the right image register r N/2  sequentially receive pixel data of left and right image lines from the input buffers  311  and  312 , and the left and right image registers I 1  to I N/2  and r 1  to r N/2  shift the pixel data to the adjacent image registers I 1  to I N/2  and r 1  to r N/2  in step S 920 . In this instance, the orders of the left and right image pixel data are rearranged to be 
         [0000]    
       
         
           
             
               g 
               
                 N 
                 - 
                 
                   
                     1 
                     2 
                   
                    
                   
                     ( 
                     
                       i 
                       - 
                       j 
                       - 
                       1 
                     
                     ) 
                   
                 
               
               l 
             
              
             
                 
             
              
             and 
              
             
                 
             
              
             
               
                 g 
                 
                   N 
                   - 
                   
                     
                       1 
                       2 
                     
                      
                     
                       ( 
                       
                         i 
                         - 
                         j 
                         - 
                         1 
                       
                       ) 
                     
                   
                 
                 r 
               
               . 
             
           
         
       
     
         [0075]    In a like manner of  FIG. 8 , it is determined whether the sum (i+j) is odd or even in step S 930 , and when the sum (i+j) is odd, the controller  323   i  of  FIG. 6  controls U j (t−1) to be output as a cost in step S 941 , and when the sum (i+j) is even, the controller  323   i  controls U j (t) to be output as a cost in step S 942 . 
         [0076]    Therefore, since the output U j (t−1) of the adder  323   d  of the forward processor fp j  becomes a cost when the sum (i+j) is odd, the cost U j (i) is given in Equation 8, and the decision value V i,j   a  in this instance is 0. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         U 
                         j 
                       
                        
                       
                         ( 
                         
                           i 
                           - 
                           1 
                         
                         ) 
                       
                     
                     + 
                     
                        
                       
                         
                           g 
                           
                             N 
                             - 
                             
                               
                                 1 
                                 2 
                               
                                
                               
                                 ( 
                                 
                                   i 
                                   - 
                                   j 
                                   - 
                                   1 
                                 
                                 ) 
                               
                             
                           
                           l 
                         
                         - 
                         
                           g 
                           
                             N 
                             - 
                             
                               
                                 1 
                                 2 
                               
                                
                               
                                 ( 
                                 
                                   i 
                                   + 
                                   j 
                                   - 
                                   1 
                                 
                                 ) 
                               
                             
                           
                           r 
                         
                       
                        
                     
                     + 
                     
                       
                         ∑ 
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 λ 
                               
                               , 
                               λ 
                             
                             ] 
                           
                         
                       
                        
                       
                         η 
                          
                         
                            
                           p 
                            
                         
                          
                         
                           
                             a 
                             
                               j 
                               + 
                               p 
                             
                           
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                     
                     + 
                     
                       η 
                        
                       
                           
                       
                        
                       
                         λδ 
                         ( 
                         
                           
                             ∑ 
                             
                               p 
                               ∈ 
                               
                                 [ 
                                 
                                   
                                     - 
                                     λ 
                                   
                                   , 
                                   λ 
                                 
                                 ] 
                               
                             
                           
                            
                           
                             
                               a 
                               
                                 j 
                                 + 
                                 p 
                               
                             
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   8 
                 
               
             
           
         
       
     
         [0077]    When the sum (i+j) is even, the output U j (t−1) of the adder  323   g  of the forward processor fp j  becomes a cost, and accordingly, the cost U j (i) and the decision value V i,j   a  are given in Equations 9 and 10, respectively. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         min 
                         
                           
                             p 
                             ∈ 
                             
                               [ 
                               
                                 
                                   - 
                                   1 
                                 
                                 , 
                                 1 
                               
                               ] 
                             
                           
                           , 
                           
                             
                               j 
                               + 
                               p 
                             
                             ∈ 
                             
                               [ 
                               
                                 0 
                                 , 
                                 N 
                               
                               ] 
                             
                           
                         
                       
                        
                       
                         { 
                         
                           
                             
                               U 
                               
                                 j 
                                 + 
                                 p 
                               
                             
                              
                             
                               ( 
                               
                                 i 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           + 
                           
                             γ 
                              
                             
                                 
                             
                              
                             
                               p 
                               2 
                             
                           
                         
                         } 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 λ 
                               
                               , 
                               λ 
                             
                             ] 
                           
                         
                       
                        
                       
                         η 
                          
                         
                            
                           p 
                            
                         
                          
                         
                           
                             a 
                             
                               j 
                               + 
                               p 
                             
                           
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                     
                     + 
                     
                       η 
                        
                       
                           
                       
                        
                       
                         λδ 
                         ( 
                         
                           
                             ∑ 
                             
                               p 
                               ∈ 
                               
                                 [ 
                                 
                                   
                                     - 
                                     λ 
                                   
                                   , 
                                   λ 
                                 
                                 ] 
                               
                             
                           
                            
                           
                             
                               a 
                               
                                 j 
                                 + 
                                 p 
                               
                             
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   9 
                 
               
             
             
               
                 
                   
                     V 
                     
                       i 
                       , 
                       j 
                     
                     a 
                   
                   = 
                   
                     
                       arg 
                        
                       
                         
                             
                         
                          
                         
                             
                         
                       
                        
                       min 
                     
                     
                       
                         p 
                         ∈ 
                         
                           [ 
                           
                             
                               - 
                               1 
                             
                             , 
                             1 
                           
                           ] 
                         
                       
                       , 
                       
                         
                           j 
                           + 
                           p 
                         
                         ∈ 
                         
                           [ 
                           
                             0 
                             , 
                             N 
                           
                           ] 
                         
                       
                     
                   
                    
                   
                     { 
                     
                       
                         
                           U 
                           j 
                         
                          
                         
                           ( 
                           
                             i 
                             - 
                             1 
                           
                           ) 
                         
                       
                       + 
                       
                         γ 
                          
                         
                             
                         
                          
                         
                           p 
                           2 
                         
                       
                     
                     } 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   10 
                 
               
             
           
         
       
     
         [0078]    The decision value V i,j   a  determined through the steps of S 941  and S 942  is stored in the stack  325 . 
         [0079]    In a like manner of  FIG. 8 , the backward processor bp j  reads a decision value V 2N−i,j   b  processed by the forward processor fp j  from the stack  325  as to an adjacent image line, and outputs an activation bit a j (i+1). The tri-state buffer  324   e  of the backward processor bp j  receives the decision value V 2N−i,j   b  of the previous line from the stack  325 , and outputs an optimal decision value V 2N−i,j   b  for showing increment/decrement of disparity according to the activation bit a j (i+1), and the sum of the decision values V 2N−i,j   a  becomes a disparity {circumflex over (d)}(i+1). The activation bit a j (i+1) and the disparity {circumflex over (d)}(i+1) are given in Equations 11 and 12. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                       j 
                     
                      
                     
                       ( 
                       
                         i 
                         + 
                         1 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         p 
                         ∈ 
                         
                           [ 
                           
                             
                               - 
                               λ 
                             
                             , 
                             λ 
                           
                           ] 
                         
                       
                     
                      
                     
                       
                         
                           a 
                           
                             j 
                             + 
                             p 
                           
                         
                          
                         
                           ( 
                           i 
                           ) 
                         
                       
                        
                       
                         δ 
                          
                         
                           ( 
                           
                             p 
                             + 
                             
                               V 
                               
                                 
                                   
                                     2 
                                      
                                     
                                         
                                     
                                      
                                     N 
                                   
                                   - 
                                   i 
                                 
                                 , 
                                 
                                   j 
                                   + 
                                   p 
                                 
                               
                               b 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   11 
                 
               
             
             
               
                 
                   
                     
                       d 
                       ^ 
                     
                      
                     
                       ( 
                       
                         i 
                         + 
                         1 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         
                           [ 
                           
                             0 
                             , 
                             
                               N 
                               - 
                               1 
                             
                           
                           ] 
                         
                       
                     
                      
                     
                       
                         
                           a 
                           j 
                         
                          
                         
                           ( 
                           
                             i 
                             + 
                             1 
                           
                           ) 
                         
                       
                        
                       
                         V 
                         
                           
                             
                               2 
                                
                               
                                   
                               
                                
                               N 
                             
                             - 
                             i 
                           
                           , 
                           j 
                         
                         b 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   12 
                 
               
             
           
         
       
     
         [0080]    When the i th  current clock signal is not 2N in step S 950 , the i th  clock signal is increased by 1 in step S 960  to repeat the steps of S 920 , S 930 , S 941 , and S 942 . The disparity for the pixel data of the current image line is calculated through the above-described process. 
         [0081]    The stereo image matching method processed by the stereo image matching system according to the first embodiment has been described, which can also be processed by software. A software-based stereo image matching method according to a second exemplary embodiment will be described in which processing elements are performed not in parallel but in series. 
         [0082]      FIG. 10  shows a flowchart for a stereo image matching method according to a second exemplary embodiment of the present invention. 
         [0083]    Referring to  FIG. 10 , processing elements are reset in step S 1010 , and the position j of a processing element to be processed is established to be 0 in step S 1020 , as given in Equation 1. 
         [0084]    The pixel data 
         [0000]    
       
         
           
             
               g 
               
                 
                   1 
                   2 
                 
                  
                 
                   ( 
                   
                     t 
                     - 
                     j 
                     - 
                     1 
                   
                   ) 
                 
               
               l 
             
              
             
                 
             
              
             and 
              
             
                 
             
              
             
               g 
               
                 
                   1 
                   2 
                 
                  
                 
                   ( 
                   
                     t 
                     + 
                     j 
                     - 
                     1 
                   
                   ) 
                 
               
               r 
             
           
         
       
     
         [0000]    and right image lines are input to the forward processor fp j  from the left and right image registers I 1  to I N/2  and r 1  to r N/2  in step S 1030 , it is determined whether the sum (i+j) is odd or even in step S 1040 , and λ and a difference between the position j of the current processing element and the disparity value d old (i) of the previous line are compared in step S 1050 . 
         [0085]    The cost U j (i) is calculated by Equation 13 in step S 1061  when the sum (i+j) is odd and |j−d old (i)| is equal to or less than λ, the cost U j (i) is calculated by Equation 14 in step S 1062  when the sum (i+j) is odd and |j−d old (i)| is greater than λ, and the decision value V i,j  is established to be 0 when the sum (i+j) is odd. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         U 
                         j 
                       
                        
                       
                         ( 
                         
                           i 
                           - 
                           1 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             
                               
                                 
                                   g 
                                   
                                     
                                       1 
                                       2 
                                     
                                      
                                     
                                       ( 
                                       
                                         i 
                                         - 
                                         j 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                   l 
                                 
                                 - 
                               
                             
                           
                           
                             
                               
                                 g 
                                 
                                   
                                     1 
                                     2 
                                   
                                    
                                   
                                     ( 
                                     
                                       i 
                                       + 
                                       j 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 r 
                               
                             
                           
                         
                         ) 
                       
                       2 
                     
                     + 
                     
                       η 
                        
                       
                          
                         
                           j 
                           - 
                           
                             
                               d 
                               old 
                             
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                          
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   13 
                 
               
             
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         U 
                         j 
                       
                        
                       
                         ( 
                         
                           i 
                           - 
                           1 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             
                               
                                 
                                   g 
                                   
                                     
                                       1 
                                       2 
                                     
                                      
                                     
                                       ( 
                                       
                                         i 
                                         - 
                                         j 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                   l 
                                 
                                 - 
                               
                             
                           
                           
                             
                               
                                 g 
                                 
                                   
                                     1 
                                     2 
                                   
                                    
                                   
                                     ( 
                                     
                                       i 
                                       + 
                                       j 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 r 
                               
                             
                           
                         
                         ) 
                       
                       2 
                     
                     + 
                     ηλ 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   14 
                 
               
             
           
         
       
     
         [0086]    In this instance, the cost U j (i) and the decision value V i,j  are calculated in step S 1063  as given in Equations 15 and 16 when the sum (i+j) is even and |j−d old (i)| is equal to or less than λ, and the cost U j (i) and the decision value V i,j  are calculated in step S 1064  as given in Equations 17 and 18 when the sum (i+j) is even and |j−d old (i)| is greater than λ. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       min 
                       
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 1 
                               
                               , 
                               1 
                             
                             ] 
                           
                         
                         , 
                         
                           
                             j 
                             + 
                             p 
                           
                           ∈ 
                           
                             [ 
                             
                               0 
                               , 
                               N 
                             
                             ] 
                           
                         
                       
                     
                      
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   U 
                                   
                                     j 
                                     + 
                                     p 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     i 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 γ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   p 
                                   2 
                                 
                               
                               + 
                             
                           
                         
                         
                           
                             
                               η 
                                
                               
                                  
                                 
                                   j 
                                   - 
                                   
                                     
                                       d 
                                       old 
                                     
                                      
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                 
                                  
                               
                             
                           
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   15 
                 
               
             
             
               
                 
                   
                     V 
                     
                       i 
                       , 
                       j 
                     
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 1 
                               
                               , 
                               1 
                             
                             ] 
                           
                         
                         , 
                         
                           
                             j 
                             + 
                             p 
                           
                           ∈ 
                           
                             [ 
                             
                               0 
                               , 
                               N 
                             
                             ] 
                           
                         
                       
                     
                      
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   U 
                                   
                                     j 
                                     + 
                                     p 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     i 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 γ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   p 
                                   2 
                                 
                               
                               + 
                             
                           
                         
                         
                           
                             
                               η 
                                
                               
                                  
                                 
                                   j 
                                   - 
                                   
                                     
                                       d 
                                       old 
                                     
                                      
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                 
                                  
                               
                             
                           
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   16 
                 
               
             
             
               
                 
                   
                     
                       U 
                       j 
                     
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       min 
                       
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 1 
                               
                               , 
                               1 
                             
                             ] 
                           
                         
                         , 
                         
                           
                             j 
                             + 
                             p 
                           
                           ∈ 
                           
                             [ 
                             
                               0 
                               , 
                               N 
                             
                             ] 
                           
                         
                       
                     
                      
                     
                       { 
                       
                         
                           
                             U 
                             
                               j 
                               + 
                               p 
                             
                           
                            
                           
                             ( 
                             
                               i 
                               - 
                               1 
                             
                             ) 
                           
                         
                         + 
                         
                           γ 
                            
                           
                               
                           
                            
                           
                             p 
                             2 
                           
                         
                         + 
                         ηλ 
                       
                       } 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   17 
                 
               
             
             
               
                 
                   
                     V 
                     
                       i 
                       , 
                       j 
                     
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         
                           p 
                           ∈ 
                           
                             [ 
                             
                               
                                 - 
                                 1 
                               
                               , 
                               1 
                             
                             ] 
                           
                         
                         , 
                         
                           
                             j 
                             + 
                             p 
                           
                           ∈ 
                           
                             [ 
                             
                               0 
                               , 
                               N 
                             
                             ] 
                           
                         
                       
                     
                      
                     
                       { 
                       
                         
                           
                             U 
                             
                               j 
                               + 
                               p 
                             
                           
                            
                           
                             ( 
                             
                               i 
                               - 
                               1 
                             
                             ) 
                           
                         
                         + 
                         
                           γ 
                            
                           
                               
                           
                            
                           
                             p 
                             2 
                           
                         
                         + 
                         ηλ 
                       
                       } 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   18 
                 
               
             
           
         
       
     
         [0087]    The cost U j (i) and the decision value V i,j  are calculated through the steps S 1061 , S 1062 , and S 1063  or S 1064 , and it is determined whether the position j of the current forward processor fp j  is (N−1) th  in step S 1070 . When the position j is not (N−1) th , the position j is increased by 1 in step S 1071 , and the process is repeated from the step of S 1030 . 
         [0088]    When the position j is (N−1) th , that is, when the costs U j (i) and the decision values V i,j  are calculated for the forward processors fp j , it is determined whether the i th  current clock signal is 2N in step S 1080 . When the i th  current clock signal is not 2N, the i th  current clock signal is increased by 1 in step S 1081 , and the process is repeated from the step of S 1020 . When the i th  current clock signal is 2N, that is, when the process of the forward processor fp j  is finished for the clock signals, the backward processor bp j  is processed. 
         [0089]    The backward processor uses the disparity d j  and the decision value V i,d     j    established in the previous stage to calculate the disparity d j−1  in the current stage as given in Equation 19, and update d old (i) with d old (i)=d i  in step S 1110 . 
         [0000]        d   j−1   =d   i   +V   i,d     j     Equation 19 
         [0090]    It is determined whether the i th  current clock signal is 0 in step S 1120 , and when it is not 0, the i th  current clock signal is decreased by 1 in step S 1130 , and the process is repeated from the step of S 1110 . 
         [0091]    According to the exemplary embodiments of the present invention, as shown in  FIG. 11 , image lines g m1   l −g m2   l  and g m1   r −g m2   r  on adjacent plural epipolar lines are received, and the constraint condition between lines in the case of matching stereo images is used to reduce the error of disparity. That is, the difference of the disparity value which is distance data between image lines of disparity images is used to be the constraint condition at the time of matching the stereo images on the assumption that the surface of an object is relatively gentle. Therefore, much noise is eliminated as shown in  FIG. 13C  compared to  FIG. 13D  when the left and right images of  FIG. 13A  and  FIG. 13B  are input. 
         [0092]    While this invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims. 
         [0093]    According to the present invention, the disparity is calculated at a high speed and is encoded with a high compression rate. Further, stable distance images are obtained since noise in the vertical direction is eliminated by using the geometric constraint condition between image lines on the epipolar lines.