JP3103282B2 - Block correlation processor - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a block correlation processing device which enables both a corresponding point search for a small object and a target point search for a large object.

[0002]

2. Description of the Related Art Heretofore, there has been a case where it is desired to capture an environment with a television camera and specify a moving object on a screen. in this case,
One screen is divided into a plurality of blocks, and a correlation operation between any one of the blocks and a partial area of another screen is performed while slightly moving the partial area to obtain a correspondence having the highest correlation value. There is known a block correlation calculation method for determining to which region one block has moved on another screen.

However, in the block correlation operation method, since the convolution operation is performed, the operation time is long, and it is difficult to recognize a moving object in real time. Therefore, various simplified block correlation operation methods for shortening the operation time have been proposed. Among them, the absolute difference sum calculation method is known as a method which is relatively simple and obtains good results.

In this operation method, the brightness value of a pixel belonging to a block composed of an m × n matrix is determined by {D _{i, j} }
(1 ≦ i ≦ m, 1 ≦ j ≦ n), assuming that the brightness value of the pixel belonging to the block to be searched is {H _{i, j} },

(Equation 1) Is calculated.

[0005]

Although the block correlation calculation based on the sum of absolute differences is simplified, the amount of calculation is still large, and in a block correlation calculation of m × n size, one correlation calculation requires M × n for subtraction and absolute value processing
And (m × n-1) additions are required. Then, on the screen to be searched, the block is moved by a predetermined number of pixels in accordance with the resolution, and the sum of the absolute values of the differences is calculated, thereby determining the region of the best match. If the number of movements of this block on the screen to be searched is α, (m × n−
1) The calculation of the sum of absolute differences is required x α times. Further, if an area corresponding to each block obtained by dividing the entire screen into β is obtained, (m × n−1) × α × β sum of absolute difference values is required.

On the other hand, since a corresponding point search in an on-vehicle image processing apparatus requires high speed, one point on one screen is required.
It is necessary to use a hardware block correlator that processes the correlation between one block and the block in the screen to be searched at high speed. By the way, the recognition accuracy of an object is determined by the relationship between the size of the object and the size of the block, and the detection accuracy is highest when the size of the block is approximately twice the size of the object. However, the target of the corresponding point search varies from a large object to a small object. Therefore, in order to increase the detection accuracy irrespective of the size of the object, it is necessary to prepare separate hardware for searching for a corresponding point of a large object and searching for a corresponding point of a small object. Therefore, there is a problem that the hardware becomes large.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problems, and an object of the present invention is to increase the detection accuracy and simplify the device configuration regardless of the size of an object to be recognized. is there.

[0008]

According to the present invention, when one of two screens each having the number of pixels of t.times.s is used as a reference screen and the other is used as a search screen, an arbitrary number of pixels of m.times.n in the reference screen is used. By calculating the correlation value between the image data of each pixel of the reference block and the image data of each pixel of the movable m × n search block assumed on the search screen, This is a block correlation processing device that determines a corresponding area.

This apparatus uses a reference block as a first type reference block, a search block as a first type search block, and a second type reference of an a × b (= k) matrix in which the first type reference block is a unit. Assuming the block as the reference screen, the first
When it is assumed that the second type search block of the a × b (= k) matrix in which the type search block is one unit is movable to the search screen, the k first type reference blocks inherent in the second type reference block and K parallel correlated block correlation calculators each calculating a correlation value between k corresponding first type search blocks existing in the second type search block, and
combining means for calculating the sum of the output values of the k block correlation calculators to calculate the correlation value between the second type reference block and the second type search block; Every time it moves, the second value when the maximum value and the maximum value among the correlation values output from each block correlation calculator are obtained.
A first type maximum value / address holding unit for storing a pixel address of the type search block, and a maximum value and a maximum value of the correlation values output from the synthesizing unit each time the second type search block moves on the search screen. Second type maximum value / address holding means for storing the pixel address of the second type search block when the value is obtained.

[0010] With the above configuration, it is possible to determine the area to be most matched with the first type reference block and the area to be most matched with the second type reference block while moving the second type search block on the search screen.

In the apparatus of another invention, the synthesizing means has a hierarchical structure. That is, the k type 1 reference blocks inherent in the type 2 reference blocks are grouped for each of a plurality of adjacent type 1 reference blocks, and a plurality of adjacent groups among the grouped groups are further classified. When forming a hierarchical structure such that the uppermost layer becomes one group by grouping into upper groups, in each group of each layer, adders for adding output values from lower layers belonging to the group are arranged in a hierarchical structure. For each adder, each time the second type search block moves on the search screen, the second type search when the maximum value and the maximum value of the correlation values output from the adder are obtained The maximum value / address holding means for storing the pixel address of the block is arranged in a hierarchical structure.

[0012] With the movement of the second type search block, when a matrix of an arbitrary size in the second type reference block is set as an intermediate reference block, a corresponding area on the search screen corresponding to the intermediate reference block is determined. it can. With this configuration, it is possible to obtain a corresponding area using a matrix of an arbitrary dimension as a reference block.

Further, according to another invention, when assuming a plurality of second type reference blocks obtained by dividing the entire reference screen, k parallel arranged blocks are provided for each of the second type reference blocks. A correlation calculator, a combining unit, a first type maximum value / address holding unit, and a second type maximum value / address holding unit are provided.

[0014]

According to the first aspect of the present invention, k basic block correlation calculators are arranged in parallel, and the maximum value of each correlation value and the pixel address of the second type search block are held. A synthesizing means for calculating the sum of the output values of the basic block correlation calculator, and holding the maximum value and the pixel address of the second type search block having the maximum value with respect to the synthesized correlation value. I have. Therefore, at the same time when the movement of the second type search block is completed on the search screen,
On the search screen, the areas corresponding to the second type reference block and the k first type reference blocks included in the block are simultaneously determined.

As described above, for the second type reference block, the correlation value obtained for the first type reference block is used without providing a correlation calculator for calculating each pixel. Is extremely simple. or,
On the search screen, when one scan of the second type search block is completed, regions corresponding to the first type and second type reference blocks are obtained at the same time. Also, high-speed recognition becomes possible.

According to the second and third aspects of the present invention, the blocks belonging to the second type reference block have a hierarchical structure, and a correlation value can be output for each hierarchical level. Therefore, also
When one scan of the second type search block is completed on the search screen, an area corresponding to a reference block having an arbitrary size can be determined, and high-speed recognition of target objects of various sizes can be performed. .

Further, according to the third aspect of the present invention, the corresponding area can be determined simultaneously for all of the plurality of blocks divided on one screen.

[0018]

EXAMPLES First Embodiment FIG. 1 shows a pixel configuration on the screen. One screen is t
It is composed of t × s pixels in rows and s columns. That is, the first row has pixels R _{1,1 to} R _{1, s} , the second row has pixels R _{2,1 to} R _{2, s} ,
.., The t-th row is composed of R _{t, 1 to} R _{t, s} . According to the present embodiment, an arbitrary block (hereinafter, referred to as “reference block”) in one screen (hereinafter, referred to as “reference screen”) is displayed in any partial area (hereinafter, referred to as “search screen”). In the following, a search is made to determine whether or not the search block most matches the “search block” (having the same area as the reference block).

In FIG. 1, an m × n pixel area is called a basic block. For example, R _{1,1 to} R _{1, n,} R _{2,1 to} R _{2, n,}
.. M × n pixel areas of R _{m, 1 to} R _{m, n} are basic blocks A
_1,1 . As shown in FIG. 1, on the reference screen, p
.Times.q basic blocks A _1,1, ... A _{p, q} are allocated. Here, t = p × m and s = q × n.

The basic block is the minimum unit of the reference block. In the present embodiment, a search is performed in units of the basic block as a first type search. Therefore, this basic block is also referred to as a type 1 reference block. or,
The area on the search screen that is compared with the first type reference block is called the first type search block. In this embodiment, a =
2, b = 2, k = 4, and an area composed of 2 × 2 type 1 reference blocks is referred to as a type 2 reference block, and an area on the search screen to be collated with this type 2 reference block Is called a second type search block. That is, as shown in FIG. 2, an area composed of four blocks of the first type reference blocks A _1,1, A _1,2, A _2,1, A _2,2 is a second type reference block B _{1. , 1} . As shown in FIG. 2, u × v second-type reference blocks B _1,1, ..., _{Bu, v} are allocated on the reference screen. Here, p = 2 × u and q = 2 × v.

FIG. 3 shows the configuration of the apparatus of this embodiment. The TV camera 60 shoots the environment and converts the video signal to A / D.
Output to the converter 61. The A / D converter 61 converts the gray level of the video signal into 256-level digital data to obtain image data. The image data is stored in the frame memory 71 or 72 via the switch 62. The frame memories 71 and 72 store one frame of image data at addresses corresponding to pixels on the screen corresponding to FIG. The switch 62 switches the output gate according to the synchronization signal output from the control device 64, and
For alternately storing the image data of one screen output from. That is, in a certain control cycle, one frame, that is, image data of a reference screen is stored in the frame memory 71, and the next frame is stored in the frame memory 72.
That is, the image data of the search screen is stored. In the next control cycle, the image data already stored in the frame memory 72 becomes the image data of the reference screen.
The frame memory 71 stores the newly captured image data as image data of the search screen. The switch 62 functions to switch a memory for storing image data for each frame.

Each of the basic block correlation calculators 10 to 40
The image data of the reference screen is input to the X input terminal of
The switch 63 also functions to switch the outputs of the frame memories 71 and 72 like the switch 62 so that the image data of the search screen is input to the input terminal.

Each of the basic block correlation calculators 10 to 40 calculates a correlation value relating to the first type reference block.
It corresponds to four first-type reference blocks existing in one second-type reference block. That is, the basic block correlation calculators 10, 20, 30, and 40 correspond to the first type reference blocks I, II, III, and IV, respectively, as shown in FIG. When outputting the image data of the reference screen, the frame memories 71 and 72 synchronize with the pixel synchronizing signal output from the control device 64, and at the same time, simultaneously operate the first type reference blocks I, II, III and IV.
M × n pixel data D1, _i, D2, _i, D3, _i, D4, _i
Each pixel data can be output, and the
At the same time, each basic block correlation calculator 10, 2
It is configured to be able to input to each X terminal of 0, 30, and 40. Further, the correlation operation is executed by shifting the position of the second type search block by one pixel on the search screen. At this time,
Each of the Y terminals of each of the basic block correlation calculators 10, 20, 30, and 40 has four first first search blocks inherent in the second type search block.
The image data corresponding to the seed search block is configured to be input simultaneously.

Next, one basic block correlation calculator 10
Will be described. The first type and second type search blocks have the same size as the first type and second type reference blocks, respectively. As the second type search block moves one pixel at a time on the search screen, the underlying first type search block also moves. That is, the four first type search blocks move while their relative positional relationship is kept constant.
FIG. 4 shows that the second type search block W is the second type reference block B
_This shows a state in which one pixel has been moved rightward and downward by one pixel with respect to _1,1 . Therefore, each first type search block W1
, W2, W3, and W4 are also moved by one pixel in the lower right direction with respect to the first type reference blocks A _1,1, A _1,2, A _2,1, A _2,2 .

The Y terminal of the basic block correlation calculator 10 is provided with m × x constituting the first type search block W 1 of the search screen.
Image data E1, _{i, j of} n pixels are input. Accordingly, the correlation value L1 which is the result of the block correlation operation of the first type reference block A _1,1 at a certain position of the second type search block W
Is the image data E1, _{i, j of} the first type search block W1 corresponding to the image data D1, _{i, j of} the first type reference block A1, ₁
Is calculated using the following equation.

[0026]

(Equation 2) _Lmax is the maximum value of the sum of absolute differences between the first type reference block and the first type search block. That is, in the case of the best collation, the sum of absolute differences is zero. Therefore, in order to increase the degree of correspondence as the correlation value increases, the correlation value is calculated according to Equation 2.
It was defined like an expression.

Similarly, the basic block correlation calculators 20, 3
0 and 40 are the first type reference blocks shown in FIG.
Perform correlation operation on II, III, IV. The correlation values L1, L2, L3, L4 of these first type reference blocks are configured to be obtained simultaneously. On the other hand, the adder 51 is a device for adding the calculated values of the basic block correlation calculators 10 and 20, and the adder 52 is a device for adding the calculated values of the basic block correlation calculators 30 and 40. The adder 53 is a device for adding the outputs of the adders 51 and 52. Therefore, the output of the adder 53 is the correlation value Z between the second type reference block B _1,1 and the second type search block W.

In this manner, when the second type search block W takes a certain position, the obtained correlation values L1 to L4 of the first type reference block and the correlation value Z of the second type reference block are obtained.
Correspond to the correlation value registers 12, 22, 32, 42, 55 in the comparators 11, 21, 31, 42, 54, respectively.
Is compared with the stored correlation value, and if the correlation value calculated this time is larger than the stored value, the value of the correlation value register is rewritten with the correlation value calculated this time.

Each of the comparators 11, 21, 31, 41, 5
4 is the correlation value calculated this time is the correlation value register 1
When it is determined that the correlation value is larger than the correlation value stored in 2, 22, 32, 42, 55, the determination signal
4 is output. When the determination signal is input, the control device 64 outputs the upper left pixel address G of the second type search block W to the correlation value register corresponding to the comparator that has output the determination signal. Stores the pixel address G as the pixel address of the second type search block W. Note that the pixel addresses of the four first type search blocks are invariable if the pixel address G of the second type search block W is determined. Therefore, it can be determined only by offsetting the address G by each value.

In this way, each correlation value at a certain position of the second type reference block is obtained. Such a correlation value calculation is performed while moving the second type search block W by one pixel on the search screen. When the movement of the second type search block W is completed on the search screen, each of the correlation value registers 12, 22, 32, 42, and 54 stores the maximum correlation value _LMX and the second type search in which the maximum correlation value is obtained. This means that the pixel addresses G1, G2, G3, G4, H of the block W are stored. As a result, a search block that best matches the first type reference block A _1,1, A _1,2, A _2,1, A _2,2 and the second type reference block B _1,1 shown in FIG. It will be detected above. These pixel addresses G1, G2, G3,
G4, H are sent to a post-processing device (not shown) composed of a computer system, and are used for recognition and determination of a moving object.

Next, the control device 64 changes the read address of the reference image data from the frame memory,
The second type reference block is moved to the adjacent second type reference block on the reference screen. Accordingly, the four first type reference blocks also become the four basic blocks constituting the second type reference block after the movement. Then, the search block that matches the most is searched for this reference block.
Hereinafter, similarly, as shown in FIG. 2, the correlation value calculation is executed up to the last second type reference block B _{U, V} on the reference screen.

Thus, the search operation for the image in one frame is completed. In the next control cycle, the switches 62 and 63 are switched, the image data of the next frame is captured as the image data of the search screen, and the image data of the previous frame (the image data of the search screen in the previous control cycle) is changed to the current time. This is image data of a reference screen in a control cycle.

The correlation value for the first type reference block is also calculated in synchronization with the movement of the second type search block on the search screen. For this reason, regarding the collation of the type-1 reference block, the first type-1 reference block belonging to the type-2 reference block around the reference screen is not collated.
There is a seed search block part. Therefore, as shown in FIG. 5, first type and amount corresponding expansion of the search block, and the second type search block W to scan the extended search window on S _e search screen around the outside of the screen May be. At this time, the image data of the search block in the expanded portion may be dummy data having a minimum value or a maximum value, and the output value of the reference block whose correlation value has been calculated for the dummy data may be set to 0. good. Accordingly, the correlation value can be calculated for the first type reference block at the periphery of the screen, and the corresponding area can be obtained.

Second Embodiment This embodiment corresponds to claim 2. In the apparatus having the configuration shown in FIG.
There are, BL _1, ... are the basic building blocks correlation calculator, correspondence between the pixels on the screen are the same as in the first embodiment. AD _1,1, …
Are the adders of the first layer for adding the correlation values output from the two adjacent basic block correlation calculators, AD _2,1,.
Are the adders of the second layer that add the output values of the adjacent adders of the first layer, respectively, and AD _3,1, ... _Are the adders of the adders of the adjacent adders of the second layer, respectively. It is a three-layer adder. Moreover, MA _{1, 1,} ... is the basic block correlation calculator BL _1, ... holding the first layer maximum value / address for storing an address of a second kind search block having the maximum value and the maximum value of the output values of means, MA _2,1, ..., the maximum value of the second layer of the adder AD _2,1, the second layer for storing an address of a second kind search block having the maximum value and the maximum value of values ... outputs of / Address holding means, MA _3,1,
Are maximum value / address holding means of the third layer for storing the maximum value of the value output from the adder AD _3,1, ... Of the third layer and the address of the second type search block having the maximum value.

In this apparatus, since the reference block and the search block have a hierarchical structure, the widest reference block (second type reference block) is determined, and the corresponding second type search block is moved. , A corresponding region for each of a plurality of blocks having a hierarchical structure belonging to the second type reference block can be determined. The area corresponding to each reference block can be determined from the address stored in the maximum value / address holding means of each hierarchy.

Third Embodiment In the apparatus having the structure shown in FIG. 6, the addresses of all the second type search blocks corresponding to all the second type reference blocks which divide the entire reference screen are determined at the same time. Alternatively, a hierarchical structure may be adopted. In this case, each area corresponding to each hierarchically set block of the reference screen can be simultaneously determined without moving the reference block.

[Brief description of the drawings]

FIG. 1 is an explanatory diagram showing a relationship between a first-type reference block and pixels assumed on a reference screen.

FIG. 2 is an explanatory diagram showing a correspondence relationship between a first type reference block and a second type reference block assumed on a reference screen.

FIG. 3 is a block diagram showing the configuration of the first embodiment device.

FIG. 4 is an explanatory diagram showing a method of scanning a second type search block.

FIG. 5 is an explanatory diagram showing a relationship between a reference screen and an extended search screen.

FIG. 6 is a circuit diagram showing a configuration of a second embodiment device.

[Explanation of symbols]

R _{1,1 to} R _1,1 ... pixels A _{1,1 to} A _{p, q} ... type 1 reference block B _{1,1 to} Bu _{, v} ... type 2 reference block 10, 20, 30, 40 ... basic Block correlation calculators 11, 21, 31, 41 ... Comparator (first-type maximum value / address holding means) 12, 22, 32, 42 ... Correlation value register (first-type maximum value / address holding means) 54 ... Comparison Unit (second type maximum value / address holding means) 55 ... correlation value register (second type maximum value / address holding means) 51, 53, 54 ... adder (synthesis means) BL ... basic block correlation calculator MA ... maximum Value / address holding means AD: Adder (combining means)

(56) References JP-A-1-319381 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G06T 7/00 G06T 7/20 G06T 7/60 H04N 5 / 232 H04N 7/32 JICST file (JOIS)

Claims (3)

(57) [Claims] When one of two screens having the number of pixels of t × s is a reference screen and the other is a search screen, each pixel of a reference block having an arbitrary number of pixels of m × n in the reference screen is used. A region corresponding to the reference block is determined on the search screen by calculating a correlation value between the image data and image data of each pixel of a movable m × n search block assumed on the search screen. In the block correlation processing device, the reference block is a first type reference block, the search block is a first type search block, and the second block of the a × b (= k) matrix using the first type reference block as one unit. When assuming a seed reference block on the reference screen and assuming that a second type search block of an a × b (= k) matrix in which the first type search block is one unit can be moved to the search screen, Calculating k correlation values between the k first type reference blocks included in the second type reference block and the k corresponding first type search blocks included in the second type search block; Calculating the correlation value between the second type reference block and the second type search block by calculating the sum of the output values of the k block correlation arithmetic units. Each time the second type search block moves on the search screen, the second value when the maximum value and the maximum value of the correlation values output from the block correlation calculators are obtained. A first type maximum value / address holding unit for storing a pixel address of the seed search block; and a maximum value of the correlation values output from the synthesizing unit each time the second type search block moves on the search screen. Value and maximum value And a second type maximum value / address holding means for storing a pixel address of the second type search block when the first type search block is moved. A block correlation processing apparatus for determining a region to be most matched with a reference block and a region to be most matched with the second type reference block. 2. The method according to claim 1, wherein the synthesizing unit divides the k first type reference blocks included in the second type reference blocks into a plurality of adjacent first type reference blocks, and further groups the k type first reference blocks. When a plurality of groups adjacent to each other are grouped into a higher-level group to form a hierarchical structure such that the uppermost layer becomes one group, in each group of each layer,
Adders for adding output values from the lower layer belonging to the group are arranged in a hierarchical structure, and for each adder, every time the second type search block moves on the search screen, The maximum value / address holding means for storing the maximum value of the output correlation values and the pixel address of the second type search block when the maximum value is obtained is arranged in a hierarchical structure. 2. A corresponding area on a search screen corresponding to an intermediate reference block when a plurality of matrices for dividing the second type reference block are set as an intermediate reference block as the search block moves.
2. The block correlation processing device according to 1. 3. A plurality of said plurality of divided reference screens.
When assuming a second type reference block, for each of the second type reference blocks, the k parallel block block correlation calculators, the synthesizing unit, and the first type maximum value / address holding unit are provided. 3. The block correlation processing apparatus according to claim 1, further comprising a second type maximum value / address holding unit.