Image analysis – Image transformation or preprocessing – Correlation
Reexamination Certificate
1997-01-14
2001-10-02
Bella, Matthew C. (Department: 2621)
Image analysis
Image transformation or preprocessing
Correlation
C382S103000, C382S170000, C382S236000, C348S169000
Reexamination Certificate
active
06298170
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to image tracking apparatuses, and more particularly to an image tracking apparatus which tracks an image within a local region and is suited for continuously tracking a moving object within an image which is picked up by a television camera or the like.
An image tracking apparatus which tracks an image within a local region (hereinafter simply referred to as a “local region image tracking apparatus”) by tracking a moving object within a picked up image is used in various systems. Examples of such systems are systems which make a non-contact type measurement of motion without the use of an acceleration sensor or visualize motion vectors, systems which make automatic supervision or monitoring, systems which recognize human gesture, expression or line of vision, systems which control cameras when making a movie or broadcasting a sports program, systems which control moving robots or self-controlled vehicles, and systems which track moving objects from a satellite.
FIG. 1
is a system block diagram showing a part of an example of a conventional local region image tracking apparatus. In
FIG. 1
, the local region image tracking apparatus generally includes an image pickup device
501
, an analog-to-digital (A/D) converter
502
, a search image memory
503
, a reference image memory
504
, a correlation computing unit
505
, an address generator
506
, and a correlation value peak position detector
507
.
Analog image data related to an image that is picked up by the image pickup device
501
are converted into digital image data by the A/D converter
502
, and are successively stored in the search image memory
502
. The reference image memory
504
prestores fixed reference image data related to a predetermined object which is to be tracked. The correlation computing unit
505
carries out a correlation computation to obtain a correlation value which indicates the correlation between the image data within the search image memory
503
and the reference image data within the reference image memory
504
. The correlation value peak position detector
507
detects a peak position of this correlation value, that is, a position having a highest correlation within the picked up image. The peak position from the correlation value peak position detector
507
is fed back to the address generator
506
, and the address generator
506
generates a memory address corresponding to the peak position and supplies this memory address to the search image memory
503
and the reference image memory
504
. Accordingly, the peak value of the correlation value is always obtained from the correlation value peak position detector
507
, and it is possible to track the predetermined object within the picked up image in real-time based on this peak position.
In other words, as shown in
FIG. 2
, the correlation computing unit
505
computes the correlation between a reference image (hereinafter referred to as a reference block) R which is a local image within a certain frame f and a candidate block C which is a local image of the same size within another frame g, and repeats this computing operation while changing the position of the candidate block C within a search image (hereinafter referred to as a search block) S. As a result of this correlation computing operation, it is possible to calculate a moving quantity of the reference block R between the two frames f and g from the position of the candidate block C where the correlation value becomes a maximum. By repeating such an operation, it is possible to track the moving object within the picked up image.
The correlation computing operation can be described by the following formula, where “D” denotes a correlation value between the reference block R and the candidate block C, “u, v” denotes a moving quantity of the reference block R that makes the correlation value D a minimum, the reference block R and the candidate block C respectively have a size of m pixels x m pixels, “p, q” denotes a moving quantity of the candidate block C within the search block S as shown in
FIG. 2
, −p≦u, and v≦q.
D
(
u
,
v
)
=
∑
x
=
1
m
∑
y
=
1
m
&LeftBracketingBar;
S
(
u
+
x
,
v
+
y
)
-
R
(
x
,
y
)
&RightBracketingBar;
The above formula calculates the absolute value of the sum of the differences between the two local images. For this reason, the smaller this sum, that is, the smaller the correlation value D, the higher the correlation between the reference block R and the candidate block C.
The correlation computing operation requires a large amount of calculations, and it is desirable for the correlation computing unit
505
to employ a parallel pipeline processing.
FIG. 3
shows an example of the correlation computing unit
505
for m=4. In
FIG. 3
, an operation element is denoted by PE, an adder element is denoted by A, and a delay element such as a flip-flop is denoted by d. The correlation computing unit
505
shown in
FIG. 3
generally includes delay elements
601
through
612
, operation elements
621
through
624
,
631
through
634
,
641
through
644
and
651
through
654
, and adder elements
661
through
664
which are connected as shown.
The delay elements
601
through
612
are provided in order to match timings. Each of the operation elements
621
through
624
,
631
through
634
,
641
through
644
and
651
through
654
calculate the portion of the above described formula within the absolute value signs, and it is assumed for the sake of convenience that the image data of the reference block are stored therein. In other words, the image data of the reference block are stored one pixel at a time in the operation elements
621
through
624
,
631
through
634
,
641
through
644
and
651
through
654
, and by inputting the image data of the search block one pixel at a time from an input line
600
, it is possible to successively output the correlation value D(u, v) from an output line
670
. By using m×m operation elements (4×4=16 in this particular example), it is possible to carry out the process of tracking the moving object within the picked up image at a high speed.
However, the conventional local region image tracking apparatus which uses the correlation computing unit having the construction described above has the following problems.
First, because the size of the reference block is determined by the number of operation elements forming the correlation computing unit, there was a problem in that the size of the reference block is fixed depending on the correlation computing unit used. For example, when the correlation computing unit includes 256 operation elements, the size of the reference block is fixed to 16 pixels×16 pixels. However, if the image pattern to be tracked is relatively large, the reference block having the size of 16 pixels×16 pixels is too small, thereby making it difficult to carry out a satisfactory tracking process. In addition, although it is possible to increase the number of operation elements forming the correlation computing unit in order to increase the size of the reference block, there is a problem in that the scale of the circuit becomes too large in this case.
Second, there is a problem in that the conventional local region image tracking apparatus can only process black-and-white images. As a method of processing a color image, it is conceivable to provide one correlation computing unit in each of three systems for the three primary colors red, green and blue, for example, and adding outputs of the correlation computing units in the three systems. But this conceivable method is problematic in that the scale of the circuit becomes large because of the need to provide one correlation computing unit in each of the three systems.
Third, even if the reference block to be used has a size on the order of 16 pixels×16 pixels, the correlation computing unit requires 256 operation units. As a result, there is a problem in that there is insufficient
Morita Toshihiko
Sawasaki Naoyuki
Bella Matthew C.
Chawan Sheela
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Image tracking apparatus for tracking an image within a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image tracking apparatus for tracking an image within a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image tracking apparatus for tracking an image within a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598085