JP3471262B2 - 3D image processing device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus for obtaining a range image from parallax information obtained by inputting a plurality of images taken from different viewpoints and searching for corresponding points of pixels between the images. .

[0002]

2. Description of the Related Art Conventionally, as a method and apparatus for obtaining a range image (depth image) from stereo images taken from different viewpoints, for all pixels on the first image, the points corresponding to each pixel are There is a method in which the distance image is found from the image and the distance image is obtained from the difference (parallax) between the positions of both pixels by the principle of triangulation. As a method of searching for corresponding points, a method of obtaining a correlation value between pixels of both images and associating the most correlated ones is often used.

As a first conventional method of a three-dimensional image processing apparatus using such a method, a stereo system using a DSP of the University of Tsukuba (Noguchi, Ohta, "Multi-view stereo method using DSP", SIG Technical report, PRMU 96-198, pp.
43-50, 1997). This method uses a sum of absolute differences between a neighboring block including a pixel of interest in the first image and a neighboring block including a pixel to be searched in the other image as a correlation value at the time of searching for corresponding points. , Is a method for obtaining a distance image by obtaining parallax information by searching for a pixel having the smallest value of the sum of absolute differences on the other image. In this method, the size of the neighboring block in the corresponding point search processing is fixed to 3 × 3. In addition, a plurality of DSP boards are used for high speed processing.

As a second conventional method, a stereo machine of CMU (Kanede et al., "Development of Video Rate Stereo Machine", Journal of Robotics Society, vol.
2, pp. 261-267, 1997). This method, like the first conventional method, obtains the sum of absolute differences between neighboring blocks including a pixel of interest as a correlation value at the time of searching for corresponding points, and with respect to a plurality of stereo pairs when a plurality of images are used. This is a method of obtaining a distance image by obtaining parallax information by finding a pixel having the minimum value of the correlation value on the other image as a correlation value obtained by further calculating the sum.

[0005]

However, the above-mentioned conventional method has the following problems.

(1) In the corresponding point search, the first conventional method is a method and apparatus in which the size of the neighboring blocks is fixed to 3 × 3, so that it is difficult to execute processing for an arbitrary block size. is there.

(2) In the corresponding point search, in any of the conventional methods, the process of obtaining the absolute difference value is sequentially executed for all pixels. Therefore, when the image size becomes large,
Processing time increases.

(3) In any of the conventional methods, the device is a DSP
Uses multiple boards or dedicated boards, increasing the hardware scale.

(4) When determining the correlation value between neighboring blocks between different images to perform a corresponding point search, the absolute value of the difference for each corresponding pixel between the block areas is obtained, and then the sum thereof is calculated. At the time of obtaining, it is necessary to perform addition processing for each pixel the number of times corresponding to the number of pixels in the block area, and when a large block is set, the number of calculations of addition processing becomes large.

It is an object of the present invention to provide a three-dimensional image processing apparatus which solves the problems that the processing amount in the corresponding point search processing becomes large and the hardware scale becomes large in comparison with the above-mentioned conventional method. It is in.

[0011]

In order to achieve the above-mentioned object, the three-dimensional image processing apparatus of the present invention inputs a plurality of images taken from different viewpoints, and for each pixel of the first image, A device for retrieving the most corresponding pixel positions in images other than the first image, extracting the difference between those pixel positions as parallax information, and obtaining a range image from the parallax information,
Since the pixels to be compared with other images are changed sequentially,
Means for generating an image in which the entire other image is sequentially shifted by one pixel, and means for obtaining, for each pixel of the first image, a correlation value with the pixel at the same position in the shifted other image, Means for accumulating correlation values of a plurality of upper and lower pixels for each pixel to obtain a correlation value of a vertical line block including the pixel and pixels adjacent to the upper and lower sides, and accumulating correlation values of the left and right blocks of the vertical line. Means for obtaining a correlation value of a block including a plurality of pixels in the vicinity of the upper, lower, left, and right sides of the pixel, and disparity information from the image shift amount that minimizes the block correlation value among the other images. A processing block having a means for determining each of the first image is provided for each pixel or a plurality of pixels of the first image, and all processing blocks are controlled so that the processing by each means in each processing block is repeated a predetermined number of times. Then
After the processing is repeated the number of times, a processing sequence control unit that obtains distance information from the disparity information of each processing block,
There is provided a transfer path between the processing blocks capable of simultaneously transferring the image information when shifting the entire image and the correlation values from the upper, lower, left and right for obtaining the correlation value of the block among all the processing blocks.

By providing a processing block capable of simultaneously executing the processing for obtaining the correlation value for all the pixels of the first image and a transfer path capable of transferring vertically and horizontally between the processing blocks at the same time, Since the process of obtaining the correlation value at the time of searching can be performed simultaneously for all pixels, the processing time can be shortened. Further, since the processing block corresponding to all the pixels is provided, the processing for obtaining the correlation value does not depend on the block size, so that the processing for an arbitrary block size can be executed without changing the configuration of the device.

Further, in the process of obtaining the correlation value at the time of searching for the corresponding points, after obtaining the correlation value of the block of the vertical line including the pixels in the upper and lower neighborhoods, the block device of the vertical line obtained in the left and right neighborhoods is accumulated and the vertical line block device By calculating the correlation value of the block including pixels in the left and right neighborhoods, the number of calculation processes (for example, when the block size is MX × MY (MX × MY-1) times) is required according to the number of pixels in the neighboring block area. Instead, it can be executed with a process of less than half (MX + MY-2) times. In this way, the processing time can be shortened. This effect is more effective as the block size is larger.

According to an embodiment of the present invention, an associative memory is provided as the processing block and the transfer path.

As a processing block, an associative memory (CAM), which is memory-based parallel hardware capable of storing pixels at different positions in the left and right images in the same word, is provided in parallel on the memory of the associative memory. By using the arithmetic function and the parallel writing function, it is not necessary to have hardware such as an arithmetic unit for each processing block, and only a sequence control unit for controlling the whole processing is required.
It is possible to reduce the amount of hardware.

[0016]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram of a three-dimensional image processing apparatus according to the first embodiment of the present invention.

The three-dimensional image processing apparatus of this embodiment inputs a left image and a right image, associates the pixels between the left and right images, and obtains parallax information for each pixel to obtain a depth image (distance image). ) Is output.

The left and right corresponding point searching method in this apparatus uses a method of obtaining a correlation value between blocks in the vicinity of pixels on each image and associating the pixels having the highest degree of correlation. An example of the association is shown in FIG. In this example, since the search range can be narrowed down by the position and orientation of the left and right viewpoints, the block AR of the right image is narrowed down to the search range shown in the diagram on the left image, and is on the epipolar line (or near the epipolar line). Only the range is searched. Although the block size is 3 × 3, it can be easily expanded to any size and shape. As the correlation value for searching the left and right corresponding points, for example, the sum of absolute differences between blocks as described below can be used as the correlation value.

In this apparatus, processing blocks PE described later are arranged in a two-dimensional array of NX.times.NY as shown in FIG. The PE array is connected by, for example, four adjacent mesh connections. The number of processing blocks PE is the same as the number of pixels of the image, and one processing block PE is 1 in the left image.
Information on the pixel and one pixel of the right image is stored, and processing such as correlation value calculation described below is performed. Input image size is IX
When it is set to × IY, IX = NX and IY = NY, and a processing block P for performing processing relating to the pixel of coordinates (X, Y).
Let E be PE (X, Y).

As shown in FIG. 1B, one processing block PE has, as a data storage unit 26, a memory for storing pixel data PL of the left image, a memory for storing pixel data PR of the right image, and a difference. Absolute value AD, difference absolute value sum SA
D, memory for storing the minimum past value MSAD, disparity information M
It has a memory for storing D, and a work memory work necessary for calculation as necessary. Further, the absolute difference value calculation unit 22, the absolute difference value sum calculation unit 23, the comparison update processing unit 24.
In the following operation, each data stored in the data storage unit 26 and the data received from the adjacent processing block PE are used for calculation and data update processing.

The image input initialization unit 11 transmits the pixel data of the left image and the right image input to the apparatus to the data reception unit 21 of all processing blocks PE. At this time, the data receiving unit 21 determines that the pixel data of the coordinates (X, Y) is PE
PL (X, Y), PR of the (X, Y) data storage unit 26
The maximum value allowed on the memory of the data storage unit 26 is stored in the past minimum value MSAD.

The absolute difference value calculation control unit 12 includes an instruction receiving unit 2
The absolute value difference calculation unit 2 of all processing blocks PE via
2 for pixel data PL (X, Y), PR (X,
y) absolute difference value AD (X, Y) = | PL (X, Y) −
Let PR (X, Y) | be obtained.

The difference absolute value sum calculation control unit 13 instructs the instruction processing unit 27 to perform processing on all the processing blocks included in the neighborhood of the target processing block PE with respect to the difference absolute value sum operation unit 23 of all the processing blocks PE. The sum of absolute difference values AD of PE (that is, sum of absolute difference values SAD) is calculated. At this time, data transfer with the neighboring processing block PE and addition processing in the processing block PE are controlled.

The comparison / update processing control unit 14 includes a command receiving unit 27.
To the comparison / update processing unit 24 of all processing blocks via the SAD obtained when the value of the counter (explained in the next image data shift control unit 15) is d = i and (0 The past minimum values stored in the obtained MSADs are compared (within ≦ d <i), and the past minimum values MSAD and the disparity information MD are updated based on the comparison result.

The image data shift control unit 15 shifts all the pixel data PR of the right image (or the pixel data PL of the left image) for all the processing blocks PE all at once by the same number of pixels in the same direction. The image data shift control unit 15 has a counter for counting the number of shifts, and the counter value d is the PE array processing unit 20 during the comparison and update process.
Transferred to.

For simplification of the processing, the position and orientation of the camera 10 are determined so that the sight lines of the camera 10 are parallel and the X axes of the image are parallel. At this time, since the epipolar line is horizontal, if the shift amount for the pixel PR (X, Y) is (dX, 0), the processing block PE (X,
The data of Y) is transferred to the processing block PE (X + dX, Y). In order to constantly search only the epipolar line on one image for the corresponding point, the search position is shifted in the X-axis direction by dX.

The above-mentioned difference absolute value calculation, difference absolute value sum calculation, comparison update processing, and image data shift are repeated a predetermined number of times dMAX. Since the search range of the corresponding points is sufficient on the epipolar line and within the range corresponding to the maximum parallax, the predetermined maximum parallax between the left and right images is d.
It should be MAX. The maximum parallax is obtained as a parallax (difference in pixel coordinates) on the left and right images with respect to the object closest to the front in the shooting target area, and the maximum parallax does not change unless the position and orientation of the camera 10 are changed. DM the above process
After AX is repeated, the parallax data reading unit 16 reads the parallax information MD stored in the processing block PE and obtains a distance image from the parallax information.

Specific processing in each processing block PE will be described below. The data receiving unit 21 stores the data sent from another adjacent processing block PE in the data storage unit 26. The data transmission unit 25 sends the data that needs to be transferred in the processing block PE to one adjacent processing block PE.

The difference absolute value calculation unit 22 uses the subtracter and the absolute value processor to calculate the difference absolute value AD (X, Y) = | PL.
(X, Y) -PR (X, Y) | is calculated and stored in the memory AD. Since the processing block PE corresponding to each pixel is provided, the difference absolute value calculation processing is performed on all processing blocks PE.
That is, all pixels can be executed simultaneously.

The difference absolute value sum calculation unit 23 obtains the difference absolute value sum SAD in the neighborhood area by data transfer with the neighborhood processing block PE and addition processing in the processing block PE. When the processing block PE of interest is PE (X, Y) and the processing block PE of the neighboring region is PE (X + i, Y + j), the sum of absolute differences SAD is

[0032]

[Formula 1] Required by. Here, the neighborhood PE of the (X, Y) coordinates
(X + i, Y + j) is, for example, MX × MY as follows.
The processing block PE in the block processing is.

[0033]

[Equation 2] However, the shape and size of the block region can be arbitrary and can be easily implemented in that case as well. Since the processing block PE corresponding to each pixel is provided and the transfer path 30 between the processing blocks PE adjacent to each other is provided, the above-mentioned difference absolute value sum calculation processing is simultaneously executed in all processing blocks PE, that is, all pixels. it can.

A specific method will be described below with reference to FIG. First, SAD and SAD1 are initialized. SAD1 is an intermediate calculation result and is stored in the work memory work. First, SAD1 of the following equation is obtained for vertical line blocks by vertical transfer and addition processing (see FIG. 3).
(1) (2)).

[0035]

[Formula 3] Next, the obtained SAD1 is used to perform transfer and addition processing in the left-right direction to obtain the SAD of the following equation, thereby obtaining the sum of all absolute difference values AD in the MX × MY block (FIG. 3). (3) (4)).

[0036]

[Formula 4] Here, when the absolute difference value AD is transferred, the data can be shifted in the same direction in all processing blocks PE all at once, and since the processing blocks PE corresponding to each pixel are provided, all the processing blocks PE are added all at once. Because it can be processed
The calculation of the sum of absolute differences SAD can be simultaneously executed for all processing blocks PE. Further, since the left and right transfer and the processing block addition processing are performed by using the results of the vertical transfer and the addition processing, 1 is set for all processing blocks PE in the block.
Addition processing is performed for each processing block PE ((MX × MY−
1) requires (steps) times, (MX + MY-
2) The processing amount can be reduced because only one processing step is required.
You can do the same when the block size becomes large,
The larger the block size, the greater the processing effect.

The comparison / update processing unit 24 compares the obtained sum of absolute differences SAD with the stored minimum past value MSAD. If the SAD is smaller than the MSAD, the SAD is stored in the MSAD. The parallax value d is substituted into MD. Since the processing block PE corresponding to each pixel is provided, both the comparison processing and the update processing can be simultaneously executed in all processing blocks PE, that is, all pixels. The command receiving unit 27 receives the command from the image data shift control unit 15 from the image input initializing unit, decodes the command, and activates one of the data transmitting unit 25 from the data receiving unit 21.

The image data shift control unit 15 transfers the pixel data PR of the right image in the processing block PE (X, Y) to the processing block PE (X + dX, Y). Since the processing block PE corresponding to each pixel is provided and the transfer path between adjacent PEs is provided, the shift processing of the image data can be simultaneously executed in all processing blocks PE, that is, all pixels.

As described above, the processing (difference absolute value calculation, difference absolute value sum calculation, comparison update processing, image data shift processing) within each processing block PE is all processing blocks PE.
That is, all pixels can be executed simultaneously.

FIG. 4 is a block diagram of a three-dimensional image processing apparatus according to the second embodiment of the present invention.

The three-dimensional image processing apparatus of this embodiment has a first
Similarly to the embodiment described above, the left image and the right image are input, the pixels are associated with each other between the left and right images, and parallax information for each pixel is obtained to output a depth image (distance image).

In this embodiment, the PE array processing section 20 shown in the first embodiment is composed of an associative memory (CAM) 20 '. The CAM 20 ′ has the same number of words V = MX × NY as the number of pixels of the image, and one word stores information relating to one pixel of the left image and one pixel of the right image (FIG. 5).

The CAM 20 'used here is a two-dimensional PE array type CAM (T. Ikenag) already proposed by Ikenaga et al.
a, T. Ogura, “A Fully-Parallel 1Mb CAM LSI for Real
-TimePixel-Parallel Image Processing ", Ikenaga, Ogura," Massively Parallel 2D Cellular Automata "CAM
² ", IEICE Technical Report, CPSY-ICD-ETS, 1996.). This CAM20 'allocates one pixel to one word, and is arranged and connected logically in a two-dimensional PE array. Various parallel processings can be executed by external control. A concrete parallel processing example is shown in Fig. 6. In Fig. 6 (a), when reference data is input, the search mask has the same value only for the part of 1 bit. Search all words at once,
The processing example of storing the answer in the hit flag is shown. Further, FIG. 6B shows an example in which the input data masked by the write mask is written in parallel only to the word whose hit flag is 1. By combining such parallel search and parallel write functions, CAM2
With 0 ', it is possible to execute arbitrary arithmetic and logical operations such as addition processing in parallel for all words. Since the calculation is performed on the memory, there is no need to have a calculator for calculation. In addition, all words between the upper and lower words can be transferred all at once via the hit flag. Although the two-dimensional PE array type CAM 20 'is described here as an example,
If a normal one-dimensional array type CAM has a function of transferring data between upper and lower words, it can be easily realized by a method similar to the above by allocating pixels and words as shown in FIG. Hereinafter, a specific operation of the embodiment using the CAM having such characteristics will be described.

The 1-word structure of the CAM 20 'stores the same information as in the first embodiment as shown in FIG.
The word functions as one processing block PE. That is, the memory for storing the pixel data PL of the left image, the memory for storing the pixel data PR of the right image, and the absolute difference value A
D, a sum of absolute difference SAD, a memory for storing the past minimum value MSAD, a memory for storing the parallax information MD, and a work memory work required at the time of calculation as necessary.
The calculation of the absolute difference value, the calculation of the difference absolute value sum, and the comparison / update processing are performed by the CAM 20 ′ having a parallel calculation function or the like.
It can be executed on the memory of 20 '.

The overall processing flow is almost the same as in the first embodiment. The image input initialization unit 31 sets the pixel data of the left image and the right image input to the device to the PL of the CAM 20 ′,
It is input to PR and the MAX value (maximum value allowed on the memory of the data storage unit) is stored in the past minimum value MSAD.

The difference absolute value calculation control unit 32 uses the CAM2
Pixel data PL (X, Y) for all the words of 0 ',
PR (X, Y) difference absolute value AD (X, Y) = (| PL
(X, Y) -PR (X, Y) |

The difference absolute value sum control unit 33 controls the CAM 20 '.
The sum of ADs of all the words corresponding to the pixels included in the neighborhood area of the pixel corresponding to the target word (that is, the sum of absolute difference SAD) is calculated for all the words. At this time, word and data transfer corresponding to neighboring pixels,
And controlling the addition processing in the CAM 20 '.

The comparison / update processing control unit 34 determines the CAM 20 '.
For all the words, the SAD obtained when the value of the counter (explained in the next image data shift control unit 35) is d = i in the word, and by that time (0 ≦ d <i (Between), the past minimum value stored in the obtained MSAD is compared, and MSAD and MD are updated based on the comparison result. The image data shift control unit 35 shifts all the pixel data PR of the right image (or the pixel data PL of the left image) for all the words of the CAM 20 ′ all at once by the same number of pixels in the same direction. The image data shift control unit 35 has a counter for counting the number of shifts, and the counter value d (0 ≦ d ≦ dMAX) is transferred to the CAM 20 ′ during the comparison and update process.

For simplification of the processing, the position and orientation of the camera 10 are determined so that the two sight lines of the camera 10 are parallel to each other and both X axes of the image are parallel to each other, as in the first embodiment. At this time, since the epipolar line is horizontal, the pixel PR
If the shift amount for (X, Y) is (dX, 0),
The data of PE (X, Y) is transferred to PE (X + dX, Y). In order to constantly search only the epipolar line on one image for the corresponding point, the search position is shifted in the X-axis direction by dX.

The above-described difference absolute value calculation, difference absolute value sum calculation, comparison update processing, and image data shift are repeated a predetermined number of times dMAX (the same as in the first embodiment). Since the search range of the corresponding points is sufficient on the epipolar line and within the range corresponding to the maximum parallax, the maximum parallax between the left and right images obtained in advance may be set to dMAX. The maximum parallax is calculated as the parallax on the left and right images with respect to the object closest to the front in the shooting target area, and the maximum parallax does not change unless the settings such as the position and orientation of the camera are changed. dMAX
After the repetition, the parallax data reading unit 36 reads the parallax information MD stored in the PE and obtains the distance image from the parallax information. Specific processing in the CAM 20 'will be described below.

The CAM 20 'can transfer data between adjacent words, and can transfer data to a word corresponding to a data neighboring pixel of the word. Also, CAM2
Within 0 ', search processing, write processing, and addition processing can be performed in parallel for all words between arbitrary data in a word. By using these parallel processing functions, first, the absolute difference value for each word AD (X, Y) = | PL (X, Y)
−PR (X, Y) | is calculated and stored in the memory AD. At this time, the CAM can perform retrieval processing, writing processing, and addition processing in all words in parallel, so that all of the subtraction processing, absolute value processing, and writing processing can be executed all at once.

Next, the sum of absolute differences SAD is obtained. Also at this time, the SAD is obtained by means for simultaneously transferring all the words between the words corresponding to the adjacent pixels and the various parallel processing functions of the CAM 20 '. Similarly, the operation of can be executed simultaneously for all words. Similarly, the comparison process and the update process can be simultaneously executed for all words by the parallel processing function of the CAM 20 '.

A specific method will be described below with reference to FIG. First, SAD and SAD1 are initialized. SAD1 is an intermediate calculation result and is stored in the work memory work. First, SAD1 of the following equation is obtained for vertical line blocks by vertical transfer and addition processing (see FIG. 3).
(1) (2)).

[0054]

[Equation 5] Next, the obtained SAD1 is used to perform transfer and addition processing in the left-right direction to obtain the SAD of the following equation, thereby obtaining all the absolute difference values AD in the MX × MY block.
The sum of is calculated (Fig. 3 (3) (4)).

[0055]

[Equation 6] Here, when transferring the absolute difference value AD, CAM2
The parallel transfer function of 0'can shift the data in the same direction all the words at the same time, the word corresponding to each pixel is provided, and the parallel addition function of the CAM 20 'can perform the addition processing for all the pixels at the same time. , The calculation of the sum of absolute differences that requires the transfer and the addition processing in all pixels can be simultaneously executed for all processing blocks PE.

Further, as in the first embodiment, since the left and right transfer and the addition processing are performed by using the results of the transfer and the addition processing in the vertical direction, one processing block PE is added to all the processing blocks PE in the block. Each ((MX × MY-1)
(MX + MY−)
2) The number of processing steps can be reduced, so that the processing amount can be reduced. The same can be done when the block size is large, and the larger the block size, the greater the effect of processing.

Further, in each word, the obtained SA
D is compared with the stored MSAD, and SAD is the MS
If it is smaller than AD, SAD is stored in MSAD and the parallax value d at that time is substituted into MD. Since the word corresponding to each pixel is provided, both the comparison process and the update process can be simultaneously executed in all words, that is, in all pixels.

After that, all the pixel data PR of the right image in PE (X, Y) is transferred to PE (X + dX, Y).
Since the word corresponding to each pixel is provided and the transfer path between adjacent PEs is provided, the shift processing of the image data can be simultaneously executed in all PEs, that is, all pixels.

The above-mentioned processing in each PE (difference absolute value calculation, difference absolute value sum calculation, comparison update processing, pixel data transfer processing) is all executed simultaneously in all words, that is, in all pixels. Also, all of these processes are CAM
Since the operation is performed on the memory 20 ', it is not necessary to have a dedicated arithmetic unit for that purpose, and the amount of hardware can be reduced.

In the devices of the first and second embodiments, 1
Each processing block PE can execute not only one pixel but also a plurality of pixels. When the input image size is IX × IY, the number of processing blocks is NX × NY, and when one processing block PE processes a neighborhood area of a × b pixels, the number of processing blocks PE required is 1 pixel 1
It can be reduced by 1 / (ax) times as compared with the case of PE.

In this case, the data storage unit in each processing block PE needs to have a capacity corresponding to the number of target pixels, but even if each processing unit in the processing block PE has only one, It can be executed in division. The processing time becomes longer, but the amount of hardware can be reduced. Even in this case, the processing in the processing block PE is simultaneously executed in all the processing blocks PE.

In the above embodiment, the sum of absolute differences between neighboring block areas is used as an index for searching the corresponding points of the left and right images.

[0063]

[Equation 7] Was used as the correlation value, but other correlation values can be similarly easily constructed. For example, the normalized correlation value E as shown below
A method of obtaining (X, Y) is also conceivable.

[0064]

[Equation 8] The processing in the processing blocks PE can be simultaneously executed in all the processing blocks PE, and improvement in the accuracy of association can be expected.

In each of the above embodiments, the two images, the left image and the right image, are used as the input images. However, one image is used as a reference image, and the other image is used as the reference image. Targeting different images,
A method to be carried out similarly is also easily conceivable.

For example, as used in the second conventional method, there is a method of obtaining the sum of absolute difference sums using a plurality of stereo pairs obtained for a pixel of interest of one image as a correlation value. .

As another method, the sum of absolute differences between blocks is individually calculated for each stereo pair, the minimum value is searched for, the corresponding point is searched for to obtain the depth information, and then the different stereo for the same pixel is obtained. There is a method of obtaining one depth information for each pixel by integrating the depth information obtained from the pair, for example, obtaining an average value. By using the plurality of pieces of image information in this way, it is possible to improve the estimation accuracy of the parallax information.

[0068]

As described above, according to the first aspect of the present invention, the processing for obtaining the correlation value can be simultaneously executed for all the pixels of the first image, and the processing blocks can be simultaneously moved up and down. Since the transfer path capable of left and right transfer is provided, the processing for obtaining the correlation value at the time of searching for the corresponding points can be simultaneously executed over all pixels, so that the processing time can be shortened. Further, since the processing block corresponding to all the pixels is provided, the processing for obtaining the correlation value does not depend on the block size, so that the processing for an arbitrary block size can be executed without changing the configuration of the device.

Further, in the process of obtaining the correlation value at the time of searching for corresponding points, after obtaining the correlation value of the block of the vertical line including pixels in the upper and lower neighborhoods, the correlation value of the block of the vertical line obtained in the left and right neighborhoods is accumulated. By calculating a block correlation value including pixels in the upper, lower, left, and right neighborhoods, the number of calculation processes according to the number of pixels in the neighboring block area (for example, when the block size is MX × MY (MX × MY−1) times) is calculated. No need, less than half (MX + MY-2) times)
It can be executed by the process of. In this way, the processing time can be shortened. This effect is more effective as the block size is larger.

According to the invention of claim 2, in addition to the effect of claim 1, as processing blocks and transfer paths, memory-based parallel hardware capable of storing pixels at different positions in the left and right images in the same word is used. It is equipped with a certain associative memory (CAM), and by using the parallel operation function and parallel write function on the memory of the associative memory, it is not necessary to have hardware such as an arithmetic unit for each processing block, and overall processing is possible. It suffices to have a sequence control unit for controlling, and the amount of hardware can be reduced.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a three-dimensional image processing apparatus according to a first embodiment of the present invention.

FIG. 2 is a diagram illustrating a corresponding point search method according to the first embodiment of the present invention.

FIG. 3 is a diagram illustrating a calculation procedure of a sum of absolute differences in the first embodiment of the present invention.

FIG. 4 is a configuration diagram of a three-dimensional image processing apparatus according to a second embodiment of the present invention.

FIG. 5 is an image and CAM according to the second embodiment of the present invention.
It is a figure explaining the relationship of a word.

FIG. 6 is a diagram illustrating an example of parallel processing of CAM in the second embodiment of the present invention.

[Explanation of symbols]

10 cameras 11,31 Image input initialization unit 12, 32 Difference absolute value calculation control unit 13, 33 Difference absolute value sum calculation control unit 14, 34 Comparison update processing control unit 15,35 Image data shift controller 16,36 Parallax data reading unit 20 PE array processing unit 20 'CAM 21 Data receiver 22 Difference absolute value calculator 23 Difference absolute value sum calculation unit 24 Comparison update processing unit 25 Data transmitter 26 Data storage 27 Command receiver 30 transfer path

─────────────────────────────────────────────────── ─── Continuation of the front page (58) Fields surveyed (Int.Cl. ⁷ , DB name) H04N 13/00 H04N 7/32 G06F 15/16

Claims (5)

(57) [Claims] 1. A plurality of images taken from different viewpoints are input, and for each pixel of the first image, the most corresponding pixel position in the image excluding the first image is searched and those pixel positions are searched. Is a three-dimensional image processing apparatus that obtains a distance image from the parallax information by extracting the difference as the parallax information, and sequentially changes pixels to be compared with other images.
Means for generating an image in which the entire other image is sequentially shifted by one pixel, and means for obtaining, for each pixel of the first image, a correlation value with the pixel at the same position in the shifted other image, Means for accumulating correlation values of a plurality of upper and lower pixels for each pixel to obtain a correlation value of a vertical line block including the pixel and pixels adjacent to the upper and lower sides, and accumulating correlation values of the blocks on the left and right sides of the vertical line. Means for obtaining a correlation value of a block including a plurality of pixels in the vicinity of the upper, lower, left, and right sides of the pixel, and disparity information from the image shift amount that minimizes the block correlation value among the other images. A processing block having means for determining each of the first image is provided for each pixel or a plurality of pixels of the first image, and all processing blocks are controlled so that the processing by each means in each processing block is repeated a predetermined number of times. , The process is the above After being repeated, a processing sequence control unit that obtains distance information from the disparity information of each processing block, image information when shifting the entire image, and all correlation values from the top, bottom, left, and right to obtain the correlation value of the block are all processed. A three-dimensional image processing apparatus having a transfer path between the processing blocks, which can be simultaneously transferred between blocks. 2. The three-dimensional image processing apparatus according to claim 1, further comprising an associative memory as the processing block and the transfer path. 3. A distance image is output by inputting a first image and another image, associating pixels between the first image and another image, and obtaining disparity information for each pixel. A three-dimensional image processing device, which is a memory for storing pixel data of a first image, a memory for storing pixel data of another image, a memory for storing correlation values, a memory for storing a sum of correlation values, a past minimum value. , A data storage unit including a memory that stores parallax information, a data reception unit that receives data from an adjacent processing block and stores the data in the data storage unit, and pixel data of a first image and another image Calculating the correlation value of, the correlation value calculation unit to be stored in the data storage unit, and the sum of the correlation values of all processing blocks included in the neighborhood area of the processing block,
The correlation value sum calculation unit to be stored in the data storage unit, compares the correlation value sum currently obtained with the past minimum value obtained so far and stored in the data storage unit, and depending on the comparison result. A comparison update processing unit that updates the past minimum value and disparity information in the data storage unit, a data transmission unit that transfers data that needs to be transferred in a processing block to one adjacent processing block, and receives a command, The processing block including a command receiving unit that activates any one of the data receiving unit, the correlation value calculating unit, the correlation value sum calculating unit, the comparison update processing unit, and the data transmitting unit according to the command is the image data. A PE array processing unit arranged corresponding to each pixel of the above, and an instruction for transmitting the pixel data of the input first image and other image to the data receiving unit of the corresponding processing block and instructing data storage To An image input initialization unit that transmits to the command receiving unit of the corresponding processing block, and a correlation value calculation control unit that issues a command to the command receiving unit of all processing blocks to activate the correlation value calculation unit to the command receiving unit. A correlation value sum calculation control unit for issuing an instruction for activating the correlation value sum calculation unit to the instruction receiving units of all processing blocks; and an instruction receiving unit of all processing blocks, An instruction to shift the pixel data of another image by the same number of pixels in the same direction to the comparison and update processing control unit that issues an instruction to activate the comparison and update processing unit to the instruction reception unit and the instruction reception units of all processing blocks And an image data shift control unit that outputs the correlation value calculation control unit, the correlation value sum calculation control unit, the comparison update processing control unit, and the image data shift control unit after repeating each control a predetermined number of times. processing Read parallax information stored in the data storage unit of the lock, the 3D image processing apparatus having the parallax data reading unit to obtain distance information from the parallax information. 4. A distance image is output by inputting a first image and another image, associating pixels between the first image and another image, and obtaining disparity information for each pixel. A three-dimensional image processing device, which has the same number of words as the number of pixels of an image, and each word has pixel data of a first image, pixel data of another image, correlation value, sum of correlation values, minimum past value, An associative memory that stores disparity information; an image input initialization unit that stores the input pixel data of the first image and the other image in the associative memory, and stores a maximum value as a past minimum value in the associative memory. A correlation value calculation control unit that obtains an absolute value of a difference between the first image pixel data and other image pixel data for all words in the associative memory; For pixels included in the neighborhood of the corresponding pixel Correlation value sum calculation control unit for obtaining the sum of correlation values of all the corresponding words, and for all the words of the associative memory, compare the sum of absolute differences at the present time and the past minimum value in the word. , A comparison update processing control unit for updating the past minimum value and disparity information based on a comparison result, and for all words of the associative memory, all pixel data of other images are batched at the same number of pixels in the same direction. After repeating the image data shift control unit for shifting, the correlation value calculation control unit, the correlation value sum calculation control unit, the comparison update processing control unit, and the image data shift control unit, a predetermined number of times. , Reading disparity information stored in each word of the associative memory,
A three-dimensional image processing apparatus having a parallax data reading unit that obtains a distance image from the parallax information. 5. The apparatus according to claim 3, wherein the correlation value is a difference value.