Moving quantity detection apparatus and method

[0002] The present invention relates to a moving quantity detection apparatus and a method for correctly detecting a moving quantity of a block between a plurality of time sequential images.

[0003] In the background art, a CCD image (charge coupled device) camera inputs an outdoor image to a computer. Data transmission from the camera to the computer is executed at a speed such as 30 frames per second according to the NTSC standard. Therefore, even if the ability of the computer increases, the input speed of the images does not increase and realization of control of high speed equipment according to the image information is difficult.

[0004] On the other hand, a new type of sensor using a sensitive variable element is disclosed in Japanese Patent disclosure PH6-139361. This element speeds-up the image processing circuit. A result of simple image processing is outputted as a rate of 100 frames per second. However, this image processing circuit is an analog version and processable calculation is relatively simple. For example, in an interactive game of gesture input type, a movement of the object is detected by using an artificial retina chip of (32×32) pixels. This movement information is insufficient for complex image processing with respect to precision and the number of frames per second.

[0005] Recently, a smart vision-sensor has been developed. In this sensor, the image is processed by using a digital circuit and simple image processing such as labelling of the area and calculation of the center of gravity is rapidly executed. However, the emphasis of this sensor is its parallel processing ability by unit of line. Therefore, it is difficult to precisely extract the moving vector of an area in two-dimensional space. In following explanation, the moving vector is called a “moving quantity”.

[0006] Furthermore, recently, a super parallel-fast visual information processing system was developed. In this system, the sensor includes a digital processing circuit, and it is possible to pursue the area in a two-dimensional image at a speed of 1000 frames per second. However, this system is designed to execute all image processings using only neighboring calculations. Therefore, if the complexity and moving speed of the object increases, a calculation result of sufficient precision is not obtained.

[0007] In the near future, the sensor to which the above-mentioned digital processing circuit is loaded will be more developed. As a result, the image processing result for a image or a gray image will be outputted at a speed of 1000 frames per second. Accordingly, a method to rapidly and correctly detect the moving quantity of an area from a plurality of time series images that is loadable to the sensor to rapidly input and process the plurality of time series images is desired.

[0008] It is an object of the present invention to provide a moving quantity detection apparatus and a method to precisely detect the moving quantity of each area from a plurality of images in case the sensor inputs the plurality of images in a time series.

[0009] According to the present invention, there is provided a moving quantity detection apparatus, comprising: an image input means for inputting a plurality of images in a time series at a predetermined interval; a full size image processing means for dividing one image into a plurality of blocks with a predetermined size, and for calculating each evaluation value between a particular block on the one image and each neighboring block corresponding to the particular block on a time serial image; a reduced image processing means for reducing the plurality of images by a predetermined reduction ratio, for dividing one reduced image corresponding to the one image into a plurality of blocks as the predetermined size, and for calculating each evaluation value between a particular block on the one reduced image and each neighboring block corresponding to the particular block on the other reduced image corresponding to a multiple of the predetermined interval for the predetermined reduction ratio; and a moving quantity detection means for evaluating the correspondence value by unit of each neighboring block for the time sequential image and the other reduced image, for selecting the neighboring block whose evaluation value is highest of all neighboring blocks, and for calculating a relative distance between the particular block on the one image and the one neighboring block on the time serial image as a moving quantity.

[0010] Further in accordance with the present invention, there is also provided a moving quantity detection method, comprising the steps of: inputting a plurality of images in a time series at a predetermined interval; dividing one image into a plurality of blocks with a predetermined size; calculating each evaluation value between a particular block on the one image and each neighboring block corresponding to the particular block on the time serial image; reducing the plurality of images by a predetermined reduction ratio; dividing one reduced image corresponding to the one image into a plurality of blocks as the predetermined size; calculating each evaluation value between a particular block on the one reduced image and each neighboring block corresponding to the particular block on other reduced image corresponding to a multiple of the predetermined interval for the predetermined reduction ratio; evaluating the correspondence value by unit of the each neighboring block for the time sequential image and the other reduced image; selecting one neighboring block whose evaluation value is highest from the each neighboring block; and calculating a relative distance between the particular block on the one image and the one neighboring block on the time serial image as a moving quantity.

[0011] Further in accordance with the present invention, there is also provided a computer readable memory containing computer readable instructions, comprising: input of a plurality of images in a time series at a predetermined interval; instruction means for causing a computer to divide one image into a plurality of blocks with a predetermined size; instruction means for causing a computer to calculate each evaluation value between a particular block on the one image and each neighboring block corresponding to the particular block on the time serial image; instruction means for causing a computer to reduce the plurality of images by a predetermined reduction ratio; instruction means for causing a computer to divide one reduced image corresponding to the one image into a plurality of blocks as the predetermined size; instruction means for causing a computer to calculate each evaluation value between a particular block on the one reduced image and each neighboring block corresponding to the particular block on the other reduced image corresponding to a multiple of the predetermined interval for the predetermined reduction ratio; instruction means for causing a computer to evaluate the correspondence value by unit of the each neighboring block for the time sequential image and the other reduced image; instruction means for causing a computer to select one neighboring block whose evaluation value is highest of all the neighboring blocks; and instruction means for causing a computer to calculate a relative distance between the particular block on the one image and the one neighboring block on the time serial image as a moving quantity.

[0012] FIG. 1 is a block diagram of the moving quantity detection apparatus according to the present invention.

[0013] FIGS. 2A, 2B, and 2C are schematic diagrams of two time series images and the moving quantity between the two time series images.

[0014] FIG. 3 is a flow chart of processing of a image memory section in FIG. 1.

[0015] FIG. 4 is a flow chart of the processing of a moving quantity detection section in FIG. 1.

[0016] FIGS. 5A and 5B are schematic diagrams of a particular block of one image and a search area of previous image.

[0017] FIGS. 6A and 6B are schematic diagrams of a relation between a basis image time and a comparison image time by unit of reduction ratio.

[0018] FIGS. 7A, 7B and 7C are schematic diagrams of a full size image, ½ reduced image, ¼ reduced image and each corresponding table of the moving quantity and the evaluation value.

[0019] FIG. 1 is a block diagram of the moving quantity detection apparatus according to the present invention. The moving quantity detection apparatus detects the moving quantity of an area shown in a plurality of time series images, which includes an image input section 12, an image memory section 14, and a moving quantity detection section 16.

[0020] The image input section 12 inputs the plurality of images in a time series at a predetermined interval. The image includes a background and a moving object. The plurality of images are stored in the image memory section 14 in time order. In this case, the image input section 12 takes a photograph of various kinds of objects by using a fixed or a moving sensor and rapidly inputs the time series images at a rate of several hundreds or several thousands images per second. Examples object imaged includes a car, a road, and a billboard. It is not necessary to attach a special color or mark to these objects in order to detect them.

[0021] The image memory section 14 stores the plurality of time series images inputted by the image input section 12 and supplies the plurality of time series images to the moving quantity detection section 16 as weeded. The moving quantity detection section 16 utilizes the plurality of images transferred from the image memory section 14. In this case, the moving quantity detection section 16 divides each image into a plurality of blocks of a predetermined size (lattice condition), and detects a moving quantity of the block between a plurality of time series images.

[0022] Next, a processing of the moving quantity detection apparatus is explained in detail. FIGS. 2A, 2B, and 2C are schematic diagrams of the images processed by the moving quantity detection apparatus 10. In this case, assume that a moving car on the road is regarded as a moving object and this moving object is viewed by a camera placed on a tower aside the road or another car moving ahead of the moving object. FIG. 2A is an input image at time (t) and FIG. 2B is another input image at time (t+1). FIG. 2C is the difference between the image of FIG. 2A and the image of FIG. 2B. These images are input in a time series by the image input section 12.

[0023] In general image processing, the images are obtained at a rate of 30 layers per second. If a moving quantity of the object between images is large and a fast moving object is pursued, a wide search area is necessary to be set on the image. However, in this image processing section 12, the images can be rapidly obtained at a rate of 1000 layers per second. When rapidly obtaining images, the search area to pursue the object is set at a small size. For example, if the object moving almost 1 pixel per {fraction (1/1000)} second is taken by the camera as a video rate, the search area is set on the image at “±33 pixels”. However, if the images are obtained at 1000 layers per second, the search area is set on the image at “±2 pixels” and the search processing is rapidly executed. In the following explanation, assume that a moving quantity of the object between the time series images is below 2 pixels. In this case, obtaining images by unit of {fraction (1/1000)} pixel as the time series image is called a sampling along a time direction.

[0024] The images rapidly inputted by the image input section 12 are stored in the image memory section 14. FIG. 3 is a flow chart of the processing of the image memory section 14. First, the input image itself (full size image) is stored in a time series. Then, each input image is reduced as a reduction ratio “2^−M”. This reduction of the full size image is called a transformation along a space direction.

[0025] “M” is a positive integer to be set according to the ability of image processing and memory quantity. As a reduction method, the full size image is first divided into a plurality of blocks of N×N pixels as matrix condition. In case of ½ reduction, both the vertical length and the horizontal length of the full size image are reduced by ½ while each pixel size and each block size does not change. Therefore, the number of blocks of the reduced image is decreased as ¼ in comparison with the full size image. Then, these reduced images are stored in correspondence with the full size image. The reduction ratio may be arbitrarily set according to the ability of image processing or memory quantity.

[0026] FIG. 4 is a flow chart of the processing of the moving quantity detection section 16.

[0027] (1) Basic Method

[0028] First, the image is divided into a plurality of blocks of N×N pixels as a matrix condition. Then, the strength or density of the edge in each block is calculated. Each block is determined to correspond to an area on the time serial image (next or previous image), according to the edge feature in each block.

[0029] Actually, by threshold processing, any block containing no strong edge element is excluded from the candidate blocks for the corresponding search because search processing of the corresponding area is impossible. Next, the candidate block for the corresponding search is examined to determine how to move between the input image and next (or previous) image. FIG. 5A shows an example of a particular block on the image (t) as the candidate for corresponding search. FIG. 5B shows an example of an area to be searched on the image (t+1) for the particular block. In this case, the moving quantity of the object between time series images is below 2 pixels. Therefore, if the left upper coordinate of the particular block on the image (t) is (i, j) as shown in FIG. 5A, the left upper coordinate of the search area on the image (t+1) is (i−2, j−2) as shown in FIG. 5B. In this case, as for a faster moving object, a wider search area is set. If the moving quantity is below 2 pixels, the particular block of the image (t) corresponds to the block whose evaluation value is highest in the area of the image (t+1). The evaluation value is calculated as a sum of the absolute value or square of difference of gray value or color value between each pixel in the particular block of the image (t) and corresponding pixel in a block of the image (t+1). For example, in case the evaluation value is a sum of square of difference of intensity degree, a block whose following value is minimum in the search area is regarded as the corresponding area. $D\left(k,l;-2\leqq k\leqq 2,-2\leqq l\leqq 2\right)=\frac{1}{N^2}\sum _j\sum _i{\left(I_t\left(i,j\right)-I_{t-1}\left(i+k,j+1\right)\right)}^2$

[0030] In this case, if the evaluation value as the minimum is below a threshold, the relative distance between a position of the particular block on the image (t) and a position of the corresponding block on the image (t+1) is calculated as the moving quantity. In this way, the moving quantity is respectively calculated between two time series images (t˜t+1), (t+1˜t+2) . . . (t+(n−1), t+n). Then, these moving quantities are accumulated from the first time series image (t) and the last time series image (t+n). As a result, the moving quantity at the interval of the video rate ({fraction (1/30)} second) longer than {fraction (1/1000)} second is totally calculated.

[0031] (2) A Method for Using the Reduced Image

[0032] In above-mentioned method (1), a local search for a corresponding block is repeated at short intervals ({fraction (1/1000)} second) between two time series images, and a total moving quantity at a long interval ({fraction (1/30)} second) from the first time series image to the last time series image is calculated. Therefore, the effect of noise are included in the total moving quantity. In the present invention, the moving quantity of the particular block is thus stably calculated by using a ½ reduced image and a ¼ reduced image stored in the image memory section 14.

[0033] FIG. 6A shows a table between the basis image time and comparison image time for each reduction ratio. FIG. 6B shows a schematic diagram of a pair of use images for each reduction ratio. In the same way as in method (1) for the full size image, the moving quantity is respectively calculated for a ½ reduced image and a ¼ reduced image. If a corresponding block is correctly determined for the particular block, the moving quantity between ½ reduced image (t−1) and ½ reduced image (t) is ½ the moving quantity between the full size image (t−1) and the full size image (t). In the same way, the moving quantity between ¼ reduced image (t−1) and ¼ reduced image (t) is ¼ of the moving quantity between the full size image (t−1) and the full size image (t). Conversely, the moving quantity between the ½ reduced image (t−2) and the ½ reduced image (t) is equal to the moving quantity between the full size image (t−1) and the full size image (t). The moving quantity between ¼ reduced image (t−4) and ¼ reduced image (t) is equal to the moving quantity between the full size image (t−1) and the full size image (t). In this case, the evaluation value described in the method (1) is used.

[0034] In short, the evaluation value of the reduced image between a predetermined interval corresponding to the reduction ratio is calculated by unit of the moving quantity. The evaluation value of the full size image between the image input interval is calculated by unit of the moving quantity. A total evaluation value is accumulated for the reduced image and the full size image by unit of the moving quantity. The predetermined interval corresponding to the reduction ratio is an interval between the present input timing and former input timing whose moving quantity of the reduced image is equal to the moving quantity of the full size image between the present input timing and just before input timing.

[0035] Concretely speaking, as shown in FIG. 6B, for a ½ reduced image an evaluation value (H2) of the moving quantity between timing (t−2) and timing (t) is used because this moving quantity is equal to the moving quantity of the full size image between timing (t−1) and timing (t). In the same way, a ¼ reduced image evaluation value (H4) of the moving quantity between timing (t−4) and timing (t) is used. These evaluation values (H2) (H4) are added to the evaluation value (H1) of the full size image by unit of the moving quantity. The moving quantity whose total evaluation value is highest of all total evaluation values is selected from each moving quantity. If the reduced image is divided into a plurality of blocks having the same block size as the full size image, one block in a ½ reduced image is equivalently four blocks in the full size image as shown in the left side of FIGS. 7A, 7B. Thus, one block in the ½ reduced image covers four times the area of one block in the full size image. In the same way, one block in a ¼ reduced image is equivalently sixteen blocks in the full size image as shown in left side of FIGS. 7A, 7C. Thus, one block in the ¼ reduced image covers sixteen times the area of one block of the full size image.

[0036] For example, as shown in FIG. 7A, assume that a moving quantity of two particular blocks “A” and “B” between a previous image (t−1) and a present image (t) is decided. If the moving quantity is below “±2 pixels”, candidates for the moving quantity are “(1, 1) (1, 0) (1, −1) (0, 1) (0, 0) (0, −1) (−1, 1) (−1, 0) (−1, 1)”. In this case, the following evaluation values are calculated by unit of the candidate of the moving quantity for each block “A” and “B” (i=1˜9: number of candidates).

[0037] e_Ai: evaluation value of block A between two full size images (t−1) (t) shown in FIG. 7A.

[0038] e_Bi: evaluation value of block B between two full size images (t−1) (t) shown in FIG. 7A.

[0039] e_Ai′: evaluation value of block A′ between two ½ reduced images (t−2) (t) shown in FIG. 7B.

[0040] e_Bi : evaluation value of block B′ between two ½ reduced images (t−2) (t) shown in FIG. 7B.

[0041] e_i″: evaluation value of block A″ (B″) between two ¼ reduced images (t−4) (t) shown in FIG. 7C.

[0042] The above evaluation values (H1), (H2), and (H3) are accumulated by unit of the candidate of the moving quantity for each block. As shown in right side of FIGS. 7A, 7B, 7C, a sum of the evaluation values by unit of candidate of the moving quantity is calculated for the block “A”. $\begin{array}{cc}\mathrm{S1}=e_{\mathrm{A1}}+e_{\mathrm{A1}}^{\prime }+e_1^{″},\text{:}& \text{For the moving quantity}\left(1,1\right)\\ \mathrm{S2}=e_{\mathrm{A2}}+e_{\mathrm{A2}}^{\prime }+e_2^{″},\text{:}& \text{For the moving quantity}\left(1,0\right)\\ \mathrm{S3}=e_{\mathrm{A3}}+e_{\mathrm{A3}}^{\prime }+e_3^{″},\text{:}& \text{For the moving quantity}\left(-1,0\right)\\ ⋮& ⋮\end{array}$

[0043] If one sum “S1” is the maximum value in all sums, the moving quantity of the block “A” between the two full size images (t−1) (t) is determined to be “(1, 1)”.

[0044] In same way, a sum of the evaluation values by unit of candidate of the moving quantity is calculated for the block “B”. $\begin{array}{cc}\mathrm{T1}=e_{\mathrm{B1}}+e_{\mathrm{B1}}^{\prime }+e_1^{″},\text{:}& \text{For the moving quantity}\left(1,1\right)\\ \mathrm{T2}=e_{\mathrm{B2}}+e_{\mathrm{B2}}^{\prime }+e_2^{″},\text{:}& \text{For the moving quantity}\left(1,0\right)\\ \mathrm{T3}=e_{\mathrm{B3}}+e_{\mathrm{B3}}^{\prime }+e_3^{″},\text{:}& \text{For the moving quantity}\left(-1,0\right)\\ ⋮& ⋮\end{array}$

[0045] If one sum “T3” is the maximum value in all sums, the moving quantity of the block “B” between the two full size images (t−1) (t) is determined to be “(−1, 0)”.

[0046] In the above-mentioned method (2), when the object is moving at a constant speed, the full size image may be reduced as 1/8 reduction ratio or 1/16 reduction ratio. In short, the assumption that the object is moving at a constant speed is necessary. However, if the time series images are rapidly inputted at an interval “{fraction (1/1000)} second”, the object is regarded as a moving object of local constant speed.

[0047] The reduction of the image represents an enlargement of the corresponding block size. By using various size blocks, the moving quantity is obtained from a processed result of the most suitable size block. In short, by accumulating the evaluation values of the various size blocks, the moving quantity is stably selected. In general, the moving quantity decreases in proportion to the reduction of the image size. In the present invention, a resolution degree along the time direction is changed in synchronization with the reduction ratio. As a result, the moving quantity is fixed regardless of the reduction ratio. Accordingly, by accumulating the evaluation value for each reduced image (each reduction ratio) by unit of fixed moving quantity, the most suitable moving quantity is stably selected.

[0048] A memory can be used to store instructions for performing the process described above. Such a memory can be a CD-ROM, floppy disk, hard disk, magnetic tape, semiconductor memory, and so on.

[0049] Other embodiments of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with the true scope and spirit of the invention being indicated by the following claims.