KR20020001502A - Stereo disparity decision apparatus and method - Google Patents

Abstract

PURPOSE: A stereo displacement determining device and a method using sequential parallel processing are provided to determine stereo displacement by repeatedly calculating the similarity between a reference window of a reference image and a detection window of a detection image having the same shape as that of the reference window using sequential parallel sharing structure. CONSTITUTION: First, the similarity between a reference window and a detection window which is positioned within a predetermined detection distance from the reference window and has the same shape as that of the reference window is repeatedly calculated using matching pixel counts representing similar bright pixel counts of detection windows including pixels corresponding to the reference window. Then, the stereo displacement between the reference window and the detection window, which similarity is maximized, is determined using the matching pixel counts to the reference pixel, thereby determining the stereo displacement between detection images.

Description

Stereo disparity decision apparatus and method using sequential parallel processing

The present invention relates to digital image processing, and more particularly, to an apparatus and method for determining stereo displacement using a sequential parallel structure for two pixels in different images.

Stereo displacement estimation is an area where active research is being conducted in the field of three-dimensional or stereo vision. Stereo displacement refers to an offset or displacement between one pixel in a reference image and another pixel in a searched image, and each pixel corresponds to the same point in physical space. The reference image and the search image are images viewed by the left eye and the right eye, respectively. In order to determine a pixel in the search pixel that matches a given pixel in the reference image, the coordinates for the pixels in the two images must first be set. Then, the similarity between the pixels in the window of constant size centered on a given pixel (i.e., the reference pixel) in the reference image and the pixels in the window of the same size centered in the pixels of the search image considered to be the corresponding points. Calculate A pixel having the maximum similarity in the searched image is regarded as a pixel matched with the reference pixel. For each pixel of the reference image, similarity is obtained for all candidate corresponding pixels within the search range, and a displacement map of the reference image is generated. At this time, the candidate correspondence pixel is limited to a pixel on the same horizontal line as the reference pixel by applying the "epipolar constraint condition", thereby making the displacement map much simpler.

1 is a diagram illustrating registration by epipolar constraint. In order to find the corresponding point of the center displayed pixel in the reference image in the search image, the similarity between the window centered on the reference pixel and the window centered on the candidate corresponding pixel in the search image is moved while moving the window in the search image along the horizontal line in the search area. Calculate A candidate search pixel having a maximum similarity in the search image is regarded as a pixel matched with the reference pixel. The displacement between the matched pixel and the reference pixel becomes a stereo displacement with respect to the reference pixel.

Here, Epipolar Constraint means that the origin of the camera's magnetic field relative to the reference coordinate system is at the same distance and the coordinates corresponding to the height are the same in order to obtain advantages such as shortening the image processing time. You get an image, which is called an epipolar constraint. In other words, in order to obtain a left and right (stereo) image, the center axis of the camera is parallel and the height of the image, that is, the y coordinate is the same. This epipolar constraint is described in UR Dhond and JK Aggarwal, "Structure from Stereo-A Review", IEEE Trans. Syst. Man Cybern., Vol. 19, no. 6, pp. 1489-1510, Nov./ Dec. 1989.).

Methods of calculating similarity for determining matching pixels include Sum of Squared Differences (SSD) and Sum of Absolute Differences (SAD) methods for viewing brightness differences between pixels, and Normalized Cross Correlation (NCC) methods for viewing correlations. have. Similarity measurement methods, such as SSD, SAD, and NCC, depend on the brightness value of a search pixel given the effect of one search pixel on the displacement map. Therefore, as shown in FIG. 2, a phenomenon called "boundary overreach" occurs in which the displacement boundary line of the region where the brightness change between the pixels is large extends to the region where the brightness change is small, and thus is incorrect at the boundary of the object. There is a problem of generating a displacement value.

An object of the present invention devised to solve the above problems is to accumulate the number of matching pixels (Window Matching Count: WMC) having similar brightness in the matching window without using the pixel brightness value of the search area directly, and to sequentially By measuring the degree of similarity by processing, to provide a stereo displacement determination apparatus and method using a sequential parallel processing that does not occur the boundary of the boundary in the stereo displacement estimation.

1 illustrates a registration constrained to an epipolar constraint;

2 is a diagram illustrating a performance comparison between the SAD method according to the prior art and the WMC method according to the present invention;

3 is a diagram illustrating a redundant operation inherent in the WMC similarity measuring method;

4 is a schematic diagram illustrating a method of measuring WMC similarity with duplicate calculations removed;

5 is a block diagram illustrating a stereo displacement determining apparatus using sequential parallel processing according to an embodiment of the present invention;

6 is an operation flowchart of a stereo displacement determination method using sequential parallel processing according to an embodiment of the present invention;

7 is a view showing the internal structure of the strip calculator shown in FIG.

8a to 8b are views showing the internal structure of the S-unit shown in FIG.

9A to 9B illustrate an operation state of a strip operator, for example, when a right image is a reference image, a left image is a search image, and Wx = Wy = 11, Sr = 63, d = 0 to 63, and wx = wy = 5 To illustrate the drawings,

10 is a view showing the internal structure of the S-buffer shown in FIG.

11 is a view illustrating an internal structure of an S-register shown in FIG. 10;

12 is a view for explaining the operating state of the S-buffer,

13 is a view for explaining the operating state of the multiplex of the S-buffer,

14 is a view showing the internal structure of the WMC-unit shown in FIG.

15 is a view showing the internal structure of the WMC-buffer shown in FIG.

16 is a view showing an internal structure of the WPC-update unit shown in FIG. 5;

17 is a view showing an internal structure of the Max_WMC selector shown in FIG. 5;

18 is a view showing an internal structure of the parallel maximum selector shown in FIG. 17;

19 is a view showing an internal structure of the comparison selector shown in FIG. 18;

FIG. 20 is a diagram illustrating an internal structure of a Comp unit shown in FIG. 18.

※ Explanation of code about main part of drawing ※

100: S-buffer

200: WMC-processor

210: strip calculator

220: WMC-Unit

230: WMC-buffer

240: Max_WMC selection unit

250 control unit

260: WMC update unit

In order to achieve the above object, a stereo displacement determining apparatus using a sequential parallel processing according to the present invention satisfies an epipolar constraint for a reference window having a constant size centering on one reference pixel of a reference image and the reference pixel. A pixel whose difference in brightness between pixels of the reference window and pixels of the search window at a position corresponding to each other for all the pixels of the search window having the same size as the reference window centered on another point of the search image is equal to or less than a threshold value Count the number of them to measure similarity and determine stereo displacement.

The stereo displacement determining apparatus includes: a strip calculator which receives the reference image and the search image and calculates S values of the reference vertical column of the reference image and all search vertical columns in the search range of the search image in parallel;

An S buffer for receiving and storing S values calculated in parallel in the strip calculator;

A WMC unit which receives S values of the reference vertical column and the search vertical columns from the S buffer and calculates WMC values of a reference window centered on the reference pixel of the reference image and all search windows within the search range of the search image; ;

The Max-WMC selector outputs the largest WMC value among the WMC values of the reference window and all the search windows obtained from the WMC unit, and sets the positional difference between the reference pixel and the center pixel of the search window as a stereo displacement. It is characterized by.

In addition, the stereo displacement determination method using the sequential parallel processing according to the present invention is a reference window of a constant size centered on any one reference pixel of the reference image, and the other of the search image satisfying the epipolar constraint with respect to the reference pixel By counting the number of pixels whose difference in brightness between pixels of the reference window and pixels of the search window at a position corresponding to each other for all the pixels of the search window having the same size as the reference window centered on a point Measure similarity and determine stereo displacement.

The stereo displacement determining method includes: a strip calculating step of receiving the reference image and the search image and calculating S values of the reference vertical column of the reference image and all search vertical columns in the search range of the search image in parallel;

A WMC calculating step of receiving W values calculated in parallel in the strip calculating step and calculating WMC values of a reference window centered on the reference pixel of the reference image and all search windows within a search range of the search image;

And a Max-WMC output step of outputting the largest WMC value among the WMC values of the reference window and all the search windows as the maximum WMC value, and setting the positional difference between the reference pixel and the center pixel of the search window as stereo displacement. do.

Hereinafter, an apparatus and method for determining stereo displacement using sequential parallel processing according to an embodiment of the present invention will be described with reference to the accompanying drawings.

In the present invention, the window matching count (WMC) is used to measure the similarity of each of the reference window in the reference image and each of the plurality of search windows in the search image. In this case, the effect of one pixel on the similarity is the same regardless of the brightness value, so that accurate results can be obtained even at the boundary of the image. The WMC calculates from the number of window pixels in one image (pixels in which another pixel corresponding to the pixel has a similar brightness value). The WMC calculates from the number of pixels of a window in one image, that is, pixels in other images corresponding to the pixels have similar brightness values.

When the reference window and the search window satisfy the epipolar constraint, the reference window centered on the pixel R (x, y) located at (x, y) in the reference image and (x + d, y) in the search image The WMC (x, y, d) value between the search windows centering on the pixel L (x + d, y) may be expressed by Equation 1 below.

here, Where Y _R (x, y) and Y _L (x + d, y) represent the brightness values of the pixels R (x, y) and L (x + d, y), respectively, and W is the R of the reference image. or (x, y) or a matching area that is a pixel area of size (Wx × Wy), which is a set of pixels centered on L (x + d, y) of the searched image. Th is also a predefined threshold. That is, in the above equation 1, when P (x, y, d) has similar pixel brightnesses for the respective positions R (x, y) and L (x + d, y) in the left and right images, 1, If not similar, it means that it has a value of zero. The displacement value for the pixel at the right image R (x, y) position is the d value at which this value becomes the maximum after obtaining WMC (x, y, d) for all the search ranges (d = 0 to Sr).

3 is a diagram illustrating a redundant operation inherent in the region-based WMC similarity measuring method. When the epipolar constraint is satisfied, the amount of calculation for determining the WMC value for all the pixels of the reference image is a massive amount proportional to {(Ix × Iy) × (Wx × Wy) × Sr}. Here, (Ix × Iy) represents the size of the image, (Wx × Wy) represents the size of the window, and Sr represents a search range. The reason for this large amount of computation is due to the redundant computation inherent in the domain-based WMC method. This is shown in FIG. 3. That is, as shown in Figure 3, if the WMC value between the two points R (x, y) and L (x + d, y) is determined, R (x + 1, y) and L (x + 1 + d In determining the WMC value between, y), the calculations corresponding to the overlapping parts (hatched parts) in the two horizontally displaced windows will be redundant calculations. This large amount of redundancy can be eliminated by using a buffer to store the result of the operation, and the overall amount of computation can be reduced to an amount proportional to (Ix × Iy) × Sr, which is not affected by the size of the window.

4 is a diagram illustrating a WMC value calculation method in which duplicate calculations are eliminated, and only pixels of a reference image are shown. In general, WMC (x, y, d) can be obtained by Equation 2 below.

Here, S (·) can be obtained as shown in Equation 5 below, and for x larger than wx in Equation 2, WMC (x, y, d) is WMC (x-1, y calculated in the previous step). It can be calculated | required from (d) as follows. This equation (3) is shown in FIG. 4.

WMC (x, y, d) = WMC (x-1, y, d) + S (x + wx, y, d) -S (x-1-wx, y, d)

That is, WMC (x, y, d) subtracts S (x-1-wx, y, d) of the front vertical column from WMC (x-1, y, d), and S (x + wx, y) of the rear vertical column. by adding d). In Equation 2 and Equation 3 above, wx and wy represent distances from the center of the window to the boundary in the horizontal and vertical directions, respectively, and are expressed as Equation 4 below.

The above S (x, y, d) is a value of P (x, y + i, d) (where i is from -wy to wy) for each pixel forming a vertical column centered on the pixel (x, y). Addition is calculated, and this is expressed as equation (5).

Here, P (x, y + i, d) is 1 if the brightness value of the R (x, y + i) pixel is similar to the brightness value of the L (x + d, y + i) pixel as shown in Equation 1. Otherwise, it has a value of zero. By repeating the above process for y greater than wy, the process repeated by (Iy-wy) is performed.

In order to estimate the stereo displacements for the reference image and the search image, first, a registration window (R (x, y), L () centered on R (wx, wy) and L (wx + d, wy) according to equation (5) x + d, y), where x is 0 to Wx, y is 0 to Wy, and d is 0 to Sr, and S (x, wy, d) representing the similarity between vertical columns is first calculated. That is, for each x value, the S value (S (x, wy, 0), S (x, wy, 1), S (x, wy, 2),.) Of the vertical column by the search range (Sr + 1). .., S (x, wy, Sr)) The obtained S values are stored in an S buffer of size Wx × (Sr + 1). Each size of the S buffer represents a similarity value between vertical columns. Is a rounded up integer.

In Equation 2, WMC (x, y, d) is a similarity between R (x, y), which is a pixel of the x-th column of the reference image, and a registration window centered on pixel coordinates L (x + d, y) of the searched image. It can be obtained by accumulating the matching S (x + i, y, d) between vertical columns by accumulating from i = −wx to wx in the WMC buffer and adding all of them. For x values greater than wx, WMC (x, y, d) is WMC (x-1, y, which is the WMC for the previous pixel in the same row that was stored in the WMC buffer, as shown in equations 3 and 4 can be calculated by using d).

That is, add S (x + wx, y, d), the S value for the vertical column that is newly added to the window, to S (x-wx-1, y, the S value for the vertical column excluded from the window. By subtracting d, it is easy to calculate WMC (x, y, d) for the current window. Similarly, when calculating the value of WMC (x, y, d) for y value greater than wy, the displacement value is obtained by repeating the above process.

In summary, after initializing the S buffer with the S value for the vertical columns centered on each pixel of the (wy) th row, and initializing the WMC buffer with the WMC value for the (wx) th pixel of one row, Other WMC values can be obtained without using redundant operations by Equation 3. At this time, the search displacement of each pixel should be the same. If the pixel having the maximum value among the WMC matching results for each pixel of the searched image within the searched range for the pixel R (x, y) of the reference image is L (x + d _max , y), d _max is R (x , y) is the stereo displacement for.

FIG. 5 is a block diagram illustrating a WMC stereo displacement measuring apparatus in which duplicate calculations are removed according to an embodiment of the present invention. In this embodiment, the case where the window size Wx × Wy is 11 × 11 and Sr is 63 will be described as an example. A threshold Th for determining whether two pixels are similar to pixel values of the reference and search images is input, and a horizontal sync signal Hsync and a vertical sync signal Vsync are input. Further, the maximum WMC (x, y, d) and the displacement DM (x, y) values at that time are output from the pixel R (x, y) of the reference video.

The WMC stereo displacement measuring device includes a WMC processor 200 and an S-buffer 100. The WMC processor 200 includes a strip operator 210, a WMC unit 220, a WMC buffer 230, a WMC updater 260, a maximum WMC selector 240, and a control unit 250. It is composed.

The strip operator 210 calculates Sr + 1 S values in parallel for the search range for each reference pixel R (x, y) including Sr + 1 S-units and stores them in the S buffer 100. . The WMC unit 220 reads the S value calculated by the strip calculator 210 from the S-buffer 100, calculates the WMC (x, y, d) value, and stores the SMC value in the WMC buffer 230. The WMC updater 260 obtains the updated WMC value, and the maximum WMC selector 240 receives the WMC value for the pixel R (x, y) from the WMC updater 260 to obtain the largest WMC (x, y). , d) value is selected, and the displacement at that time is output as a DM (x, y) value.

The internal circuit of each component will be described later in detail.

6 is an operation flowchart illustrating a WMC stereo displacement extraction method of a similarity measuring apparatus using sequential parallel processing as shown in FIG. 5.

In this algorithm, the brightness intensity of the reference pixel R (x, y) and the search pixel L (x, y) (where x = 0 to Ix-1, y = 0 to Iy-1) is input to the reference image and the search image. And stored in an external memory (not shown). In addition, the size of the matching window Wx and Wy (where Wx and Wy are odd) and the search range Sr are input to this algorithm. In addition, the algorithm outputs displacement index DM (x, y) (where x = wx to Ix-wx-Sr, y = wy to Iy-wy) indicating a stereo displacement containing displacement for each pixel. do.

Each process is as follows.

First, y is initialized to wy (S501). Here, wy is the same as Equation 4 above. After initializing the y value, the vertical string S (x, y, d) value is calculated in the range x = 0 to Wx and d = 0 to Sr, and the result is stored in the S buffer (S502). The S (·) value can be obtained using Equation 5 above. The S value stored in the S buffer indicates the similarity with respect to Wy, the size corresponding to the vertical column of the matching window, and is stored in Sr × Wx buffers.

In step S503, the condition for the range of y to obtain the WMC (x, y, d) value is checked. If y = ly-wy-1, all algorithms are terminated because WMC (·) is obtained for all images. If y = ly-wy-1, since there is a part to be obtained WMC (·), it proceeds to the next step (S504).

In step S504, the x value is initialized to wx, and in step S505, the condition for the range of the x value is checked. That is, if x is less than or equal to lx-wx-Sr, there is a part to obtain WMC (·) in the row, so proceed to step S507. If x is greater than lx-wx-Sr, increase y by one. (S506), the flow returns to step S502.

Next, the d value and the maximum WMC (Max_WMC) value are initialized (S507). In step S508, the range of the d value and the range of the x value are checked again. If x is less than or equal to lx-Sr-wx, the next step (S510) is performed. If the condition of step S508 is not satisfied, the value of x is increased by one (S509), and the process returns to step S505.

In step S510, it is checked whether x is less than or equal to wx, and if x is greater than wx, the process proceeds to step S511 to obtain the WMC (·) value of the current step by referring to the WMC (·) value in the previous step, and x is wx. If less than or equal to, the flow advances to step S515 to calculate the serial WMC (·) value. In step S515, the above equation 2 is applied to obtain a WMC (·) value, and the flow proceeds to step S516. In step S511, it is checked whether x is less than lx-Sr-wx. If x is less than lx-Sr-wx, Equation 3 is applied to obtain a WMC (·) value, and the process proceeds to step S516, where x is lx-Sr. If it is not less than -wx, the value is set to 0, and the process proceeds to step S516.

On the other hand, if the WMC (·) currently obtained in step S516 is greater than the currently stored maximum WMC value Ma_WMC, the currently obtained WMC (·) value is stored at the maximum WMC value, and the d value at that time is stored in DM (x, y). (S517). Then, d is increased by one (S518), and the flow proceeds to step S508.

Hereinafter, each component of the stereo displacement determining apparatus using the sequential parallel processing described above with reference to FIG. 5 will be described in more detail.

7 shows the internal structure of the strip calculator 210. The strip operator 210 is composed of (Sr + 1) S-units 211, 212. These S-units 211 and 212 are P (x, y) as shown in Equation 1 for pixel values R (x, y) and L (x + d, y), where d is 0 to Sr. d) calculates the S value of the vertical column by performing the operation, accumulating the resultant P (x, y, d) with respect to Wy, the vertical size of the registration window, and then calculating the S value of the S-buffer ( 100).

8A to 8B show the internal structure of the S-units 211 and 212, respectively.

The S-unit 211 obtains an S value that is similarity between the reference vertical column and the search vertical column having d = 63. The S-unit 211 has a serial / parallel converter 211a for converting the brightness values of each pixel of the search vertical column sequentially into the S-unit 212 and providing them to the S-unit 212. The absolute value calculator 211b which calculates the difference of the brightness value of each pixel of a column, and the comparator 211c which compares the result value of the absolute value calculator 211b with a threshold, and outputs 0 if the result value is large, and 1 if the threshold value is large. ) And an adder 211d for accumulating the resultant values of the comparator 211c for each pixel of the corresponding vertical column, and a cumulative value (4bit) of the adder 211d, and outputting the buffers to the S-buffer 100. A flip flop 211e is included.

Similarly, the S-unit 212 is an element that obtains S values of the reference vertical column and the search vertical column of d = 62 to 0, respectively. The S-unit 212 receives the brightness values of the parallel search column transmitted through the S-unit 211 or the front S-unit 212 and transfers the brightness values of the search vertical column to the next S-unit. A parallel / serial converter 212a for sequentially outputting values, a difference absolute value calculator 212b for obtaining a difference between brightness values of pixels forming a search vertical column to be compared with a reference vertical column, and a difference absolute value calculator 212b The comparator 212c outputs 0 when the result value is large and 1 when the threshold value is large, and an adder 212d that accumulates the result value of the comparator 212c for each pixel of the vertical column. And a D flip flop 212e which buffers the accumulated value (4 bits) of the adder 212d and outputs the buffered value to the S-buffer 100.

These S-units obtain S values of the reference vertical column and the search vertical column in a systolic array method, which will be described with reference to FIGS. 9A to 9B. 9A to 9B illustrate an operation state of a strip operator, for example, when a right image is a reference image, a left image is a search image, and Wx = Wy = 11, Sr = 63, d = 0 to 63, and wx = wy = 5 Figure is for explaining.

First, the brightness values of 11 pixels forming one vertical column are sequentially input to the S-unit 211. The serial / parallel converter of the S-unit 211 converts the brightness values of 11 pixels in parallel to one another. It is made up of vertical columns of and passes this parallel data to the next S-unit.

In order to find the S values of all d values for the first reference vertical column, the first calculation (1st Calculation) as shown in FIG. 9A is performed from the 64th calculation (64th Calculation). When the search image is sequentially inputted from the first vertical column L ₀ to the 64th vertical column L ₆₃ , the first input vertical column is sequentially shifted to the next S-unit, and when the 64th search vertical column L ₆₃ is input, FIG. 9A. The 64th Calculation step of. When the 64th search vertical column is input, the first reference vertical column R ₀ is input at the same time, and each S-unit obtains an S value. The process of obtaining S values for each S-unit has been described with reference to FIGS. 8A to 8B.

From the next 65th calculation step, the search vertical column and the reference vertical column are simultaneously input, and the reference vertical column R _i and the search vertical column L _{i + Sr} are simultaneously input to obtain an S value in each S-unit. Each S-unit finds the S value of the reference vertical column R _i and each of the search vertical columns L _{i + d} having d = 0 to 63.

In the final calculation step, the reference vertical columns R _last-63 and the search vertical column L _last are inputted, and the search vertical columns R _last-63 and each of the search vertical columns L _last-63 to L _last with d = 0 to 63 and Find the S value of.

As described above, the S values of the reference vertical sequence and the search vertical sequence which are sequentially obtained are stored in the S buffer. FIG. 10 is an internal structure diagram of the S-buffer 100 of FIG. 5, and FIG. 11 is S of FIG. 10. It is an internal structure diagram of the register 110.

The S-buffer 100 is composed of all (Wx + 1) S-registers 110, Wx MUX 120, and one counter 130. Sr + 1 4-bit values into which the WMC values for Wy + 1, the vertical size of the matching window output from the respective S-units 211 and 212 in the strip operator 210, are input in parallel, are inputted. 110). These values are shifted in the direction of the arrow by the S-register 110 in accordance with the system clock. The size of the entire S-register 110 is 4 * (Sr + 1) * (Wy + 1), and the output value for the vertical size (Wy + 1) of the matching window is (Wx + 1) by the 6-bit counter. ) Output. By doing so, the WMC value for one matching window is obtained, and the WMC value can be obtained continuously.

An operation state of the S-buffer will be described with reference to FIG. 12. Each block in FIG. 12 briefly shows an S-register. This S-buffer receives the S value of the reference vertical column and each search vertical column of d = 0 to 63 in a systolic array manner and provides it to the WMC unit.

The S value (1st Strip [0] [0:63]) between the reference vertical column R0 obtained in the 64th calculation step (see FIG. 9A) of the strip calculator and the search vertical columns in all d ranges is shown in FIG. As shown in (a), it is input to S-register 11 (110e). Next, as shown in (b) of FIG. 12, the S value (2nd Strip) between the reference vertical column R1 obtained in the 65th calculation step (see FIG. 9B) of the strip calculator and the search vertical columns in all d ranges. [1] [1:64]) is input to the S-register 11, and the 1st Strip [0] [0:63] previously input is shifted to the S-register 10110d. The state in which ten S values are input in this manner is shown in FIG. 12C, and the state in which eleven S values are input is shown in FIG. 12D.

The sum of all the first values of the S values between any reference vertical column stored in the S-registers and the search vertical columns in all d ranges will be the WMC value when d = 0, that is, 1st Strip [0]. ] [0], 2nd Strip [1] [1], 10th Strip [9] [9], and 11th Strip [10] [10] are added to give WMC (wx, y, 0). Then, adding 1st Strip [0] [1], 2nd Strip [1] [2], 10th Strip [9] [10], 11th Strip [10] [11], the value of WMC (wx, y, 1) do. Also, WMC (wx + 1, y, 0) is added to S (wx + wx + 1, y, d) in WMC (wx, y, 0) as shown in Equation 3 above, and S (wx-wx , y, 0) can be found by subtracting.

To this end, the multiplexer of the S-buffer sequentially selects S values stored in the S-registers and outputs them to the WMC unit, as shown in FIG. During the (Sr + 1) counts that are passed from the S-buffer to the WMC unit, no input is passed to the Strip operator. After the (Sr + 1) clocks, data is input to the base and search images in the strip operator.

The WMC unit receives the S values of the sequentially input vertical columns and sequentially obtains the matching values for the windows, which are transferred to the WMC buffer. The WMC value sent to the WMC buffer is written to the WMC register, and this value is used as a value for calculating the updated WMC value in the WMC-updater. On the other hand, the maximum value of the WMC input to the Max-WMC selector is selected and output as a stereo displacement value.

14, 15, and 16 are internal structural diagrams of the WMC-unit 220, the WMC-buffer 230, and the WMC-update unit 260 shown in FIG. The WMC-unit 220 is a component that performs step S515 of the flowchart of FIG. 6, and calculates WMC values for Sr + 1 d values when x = wx and outputs them to the WMC-buffer 230. The WMC-unit 220 consists of five 4-bit adders, three 5-bit adders, three 6-bit flip-flops, one 6-bit adder and one 7-bit adder. Of the 11 4-bit strips output through the S-buffer multiplexer, 10 4-bit strips are input to each of the 4-bit adders, and four of the five 4-bit adders are each output to the 5-bit adder. The output value of the other 4 bit adder and the other 4 bit input value are input to the other 5 bit adder. The output of the 5-bit adder is input to the 6-bit flip-flop for synchronization, and the synchronized 6-bit output from the 6-bit flip-flop is input to one 6-bit adder and the 7-bit adder, respectively, so that the final WMC (x, y, d ) Is obtained, and this WMC (x, y, d) value is stored in the WMC buffer 230.

The WMC-buffer 230 stores the WMC value from the WMC-unit 220 and the output value of the WMC-updater 260 in a register via MUX, and is used as an input to the WMC-updater 260. Step S514 of the flowchart of FIG. 6 is performed by this WMC buffer and WMC updater.

The WMC-updater 260 is composed of (Sr + 1) subtractors and adders, performs an operation corresponding to Equation 3, and performs an operation S514 of the flowchart of FIG. Performs an operation on + wx, y, d) -S (x-1-wx, y, d) and adds this value to the previous WMC result. Where S (x + wx, y, d) and S (x-1-wx, y, d) are the output values from the S-buffer 100, respectively.

That is, the subtractor subtracts S (x-1-wx, y, d) from the previous WMC results (AccDin0, AccDin1, ..., AccDin63), and the adder subtracts the result of the subtractor and S (x + wx, y). By adding d, new WMC (x, y, d) is obtained.

17 is an internal structure diagram of the Max_WMC selector 240 as illustrated in FIG. 5, and FIG. 18 is an internal structure of the parallel maximum selector 241 illustrated in FIG. 17. The Max_WMC selector 240 is composed of (Sr + 1) MUXs and a parallel maximum selector 241, and compares and selects the maximum WMC (x, y, d) values within a search interval, Output the DM (x, y) value. The parallel maximum selector 241 consists of four Comp units 241-1 and a comparator 241-2, and selects the maximum WMC value between the matched windows in the search interval of (Sr + 1), and then Output location information.

FIG. 19 is an internal structural diagram of the comparison selector 241-2 shown in FIG. 18 and 20 is an internal structural diagram of the Comp unit 241-1 shown in FIG. Comp unit 241-1 is composed of comparison selectors 241-2 and registers, and outputs the maximum WMC value and its position information for 16 7-bit inputs. Each of the comparison selectors 241-2 outputs the position of the maximum matching window and the maximum WMC (x, y, d) value simultaneously for (Sr + 1) search intervals. The value output through the last comparison selector in this way is the maximum WMC value and displacement at that time for a given pixel R (x, y).

The Max_WMC selector of FIG. 17 selects the sequentially calculated WMC values and parallel WMC values calculated in parallel through MUX, and the parallel maximum selector selects the maximum WMC value and the displacement value by comparing the maximum WMC value among these values. Output The parallel maximum selector consists of four Comp units and three comparison selectors and registers. The comparison selector of FIG. 19 compares the WMC comparison value via a comparator and determines the displacement value d via MUX. The comparator simply compares the magnitudes of the two input values, outputs a large value, and produces a signal to determine the displacement value. Comp Comp selectors and registers are used to compare the magnitude of the input WMC values and select the displacement d value with the largest WMC value.

While the invention has been described above based on the preferred embodiments thereof, these embodiments are intended to illustrate rather than limit the invention. It will be apparent to those skilled in the art that various changes, modifications, or adjustments to the above embodiments can be made without departing from the spirit of the invention. Therefore, the protection scope of the present invention will be limited only by the appended claims, and should be construed as including all such changes, modifications or adjustments.

As described above, according to the present invention, by accumulating the number of matching pixels (Window Matching Count: WMC) having similar brightness in the matching window without directly using the pixel brightness value of the search area, and measuring the similarity by sequential parallel processing. In the stereo displacement estimation, the boundary overpass does not occur.

Claims (12)

A reference window having a constant size centering on one reference pixel of the reference image, and a search window having the same size as the reference window centering on another point of the search image satisfying an epipolar constraint with respect to the reference pixel An apparatus for measuring similarity and determining stereo displacement by counting the number of pixels whose difference in brightness between a pixel of a reference window and a pixel of a search window at a position corresponding to each other for all pixels of the pixel is equal to or less than a threshold value. A strip calculator which receives the reference image and the search image and calculates S values of the reference vertical column of the reference image and all search vertical columns in the search range of the search image in parallel; An S buffer for receiving and storing S values calculated in parallel in the strip calculator; A WMC unit which receives S values of the reference vertical column and the search vertical columns from the S buffer and calculates WMC values of a reference window centered on the reference pixel of the reference image and all search windows within the search range of the search image; ; The Max-WMC selector outputs the largest WMC value among the WMC values of the reference window and all the search windows obtained from the WMC unit, and sets the positional difference between the reference pixel and the center pixel of the search window as a stereo displacement. Stereo displacement determination device using a sequential parallel processing, characterized in that. The method of claim 1, And a WMC updating unit for calculating a WMC value between the next reference window and the search windows using the WMC value output from the WMC unit and the S value output from the S buffer. Device. The method of claim 1, wherein the strip calculator, One first S-unit and at least Sr second S-units connected in parallel, Search vertical columns input from the outside are sequentially shifted to the first S-units to the Sr second S-units, and each S-unit is each pixel of the corresponding search vertical column and each pixel of the reference vertical column. By calculating the S value of the reference vertical column and the search vertical column using the brightness difference between and The first S-unit obtains an S value between the reference vertical column and the search vertical column having d = 63, and the second S-unit obtains an S value between the reference vertical column and the search vertical column having d = 62 to 0, respectively. Stereo displacement determination device using a sequential parallel processing, characterized in that. The method of claim 3, wherein the first S-unit, A serial / parallel converter for converting the brightness values of each pixel of the search vertical column into a second S-unit at a later stage by converting them in parallel; A difference absolute value calculator for obtaining a difference between brightness values of the pixels in the reference vertical column and the search vertical column; A comparator for comparing the result value of the difference calculator with a threshold and outputting 0 if the result value is large and 1 if the threshold value is large; An adder that accumulates the result of the comparator for each pixel of the vertical column, and And a D flip-flop that buffers the accumulated value of the adder and outputs the S-buffer to the S-buffer. The method of claim 3, wherein the second S-unit, Receives the brightness values of the search vertical column in the parallel state transmitted through the first S-unit or the second S-unit at the front end, transfers them to the second S-unit at the rear end, and converts the brightness values of the search vertical column to the serial state. Parallel to serial converter, A difference absolute value calculator for obtaining a difference between brightness values of pixels constituting the search vertical column to be compared with the reference vertical column; A comparator for comparing the result value of the difference calculator with a threshold and outputting 0 if the result value is large and 1 if the threshold value is large; An adder that accumulates the result of the comparator for each pixel of the vertical column, and And a D flip-flop that buffers the accumulated value of the adder and outputs the S-buffer to the S-buffer. The method of claim 2, wherein the S-buffer, A horizontal size (Wx) +1 S-register of the matching window that sequentially receives Sr + 1 S values output from the strip operator, and shifts sequentially; Horizontal size (Wx) multiplexers of the matching window for receiving and multiplexing the output values of the Wx + 1 S-registers, and And a counter for counting S values input to the S-register and outputting a multiplexing control signal to the multiplexer. The method of claim 6, wherein the WMC-unit, And an adder which receives the S values multiplexed and output from the multiplexer and adds all of them and outputs a WMC value. The method of claim 6, wherein the WMC-update unit, A subtractor which subtracts the S value of the first vertical column of the previous matching window from the WMC value (WMC (x-1, y, d)) of the previous matching window output from the WMC-unit, and the result value of the subtractor and the current definition And an adder for adding the S value of the rearmost vertical column of the chorus to output the WMC value of the current matching window. A reference window having a constant size centering on one reference pixel of the reference image, and a search window having the same size as the reference window centering on another point of the search image satisfying an epipolar constraint with respect to the reference pixel A method for measuring similarity and determining stereo displacement by counting the number of pixels whose difference in brightness between a pixel of a reference window and a pixel of a search window at a position corresponding to each other for all pixels of the pixel is equal to or less than a threshold value, A strip calculating step of receiving the reference image and the search image and calculating S values of the reference vertical column of the reference image and all search vertical columns in the search range of the search image in parallel; A WMC calculating step of receiving W values calculated in parallel in the strip calculating step and calculating WMC values of a reference window centered on the reference pixel of the reference image and all search windows within a search range of the search image; And a Max-WMC output step of outputting the largest WMC value among the WMC values of the reference window and all the search windows as the maximum WMC value, and setting the positional difference between the reference pixel and the center pixel of the search window as stereo displacement. Stereo Displacement Determination Using Sequential Parallel Processing. The method of claim 9, wherein the strip operation step, Obtaining a number of pixels whose brightness difference between each pixel of the reference vertical column of the reference image and each pixel of the search vertical column of the searched image corresponding to each pixel of the reference vertical column is equal to or less than a threshold value and setting the S value of the registration window as an S value; A stereo displacement determination method using sequential parallel processing. The method of claim 9, wherein the WMC calculation step, And if the registration window is the front window in the x-axis direction of the reference image, determining the WMC value of the registration window by using the following equation. [Equation] Here, wy is {vertical size (Wy) -1} / 2 of the matching window. The method of claim 9, wherein the WMC calculation step, If the registration window is not the front window in the x-axis direction of the reference image, the stereo displacement determination method using the sequential parallel processing characterized in that to obtain the WMC value of the registration window using the following equation. [Equation] Here, wx is {horizontal size (Wy) -1} / 2 of the matching window and wy is {vertical size (Wy) -1} / 2 of the matching window.