Image analysis – Image transformation or preprocessing – Correlation
Reexamination Certificate
2001-01-26
2004-04-13
Tran, Phuoc (Department: 2621)
Image analysis
Image transformation or preprocessing
Correlation
C382S305000, C708S424000
Reexamination Certificate
active
06721462
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates to an image processing unit for performing an arithmetic operation between a reference image and a search image. Description of the Related Art Hitherto, there is known an apparatus for continuously tracking an object moving in a picture plane photographed by a television camera or a video camera. Such an apparatus for tracking a moving object is widely applicable to the fields as set forth below, for example:
(1) visualization of movement measurement and movement vector of non-contact
(2) automation of monitor and observation
(3) automatic recognition of gesture, expression and one's eyes
(4) camera control of movie photography and sport relay broadcasting
(5) control of mobile robot and autonomic traveling car
In the event that the above-mentioned apparatus is used to recognize a position of a moving object, there is adopted a scheme that a pattern, which is the same as a pattern represented by a reference image or the similar pattern to the pattern represented by the reference image, is searched from a search image. For determination as to whether the pattern is identical or similar, there is often used an arithmetic method referred to as a correlation arithmetic operation.
FIG. 1
is an explanatory view useful for understanding a principle of a movement tracking processing by a correlation arithmetic operation.
A search image, which is derived through an image sensor
11
equipped with a television camera and a video camera, is converted by an A/D converter
12
into a search image represented by digital data, and then stored in a search image memory
13
. On the other hand, a reference image memory
14
stores therein a reference image which is set up fixedly beforehand or cut out from a past search image.
The search image and the reference image are read out from the search image memory
13
and the reference image memory
14
, respectively, in accordance with address information generated from an address generator
15
, and then transferred to a correlation arithmetic unit
16
. In the correlation arithmetic unit
16
, a correlation arithmetic operation, which will be described later, is performed, so that correlation values associated pixels of the search image thus obtained are fed to a correlation value peak position detector
17
to detect a peak position of the correlation value. The peak position has an identical or similar to the pattern of the reference image on the search image. The peak position detected by the correlation value peak position detector
17
is outputted to the exterior in form of information representative of a position of a moving object on the search image at the present time, and is fed back to the address generator
15
. That is, the peak position detected by the correlation value peak position detector
17
is transmitted to the address generator
15
so that a search can be performed on a certain area taking the peak position (the position of the moving object on the search image at the present time point) detected at the present time, when the position of the moving object on the search image at the subsequent time is searched.
FIG. 2
is a view representative of a pixel division of a reference image.
FIG. 3
is a view showing an example of a pattern on the reference image.
FIG. 4
is a view representative of a pixel division of a search image.
FIG. 5
is a view showing an example of a pattern on the search image.
FIG. 6
is an explanatory view useful for understanding a correlation arithmetic processing between the reference image and the search image.
FIG. 7
is a typical illustration showing a distribution of correlation values.
Here, for the purpose of simplification, it is assumed that the reference image is of 8×8 pixels as shown in
FIG. 2
, and a pixel value of a pixel of coordinates (i, j) is expressed by X (i, j). In a similar fashion to this, it is assumed that the search image is of 16×16 pixels as shown in
FIG. 4
, and a pixel value of a pixel of coordinates (i, j) is expressed by Y (i, j).
Here, as shown in
FIG. 6
, a partial area image (here, typically, a partial area image area taking coordinates (m, n) as the center) of the same size as the reference image is cut out from the search image, and the correlation value D (m, n) is computed in accordance with the following formula (1).
D
(
m
,
n
)
=
∑
i
=
0
7
∑
j
=
0
7
{
Y
(
m
+
i
,
n
+
j
)
×
X
(
i
,
j
)
}
∑
i
=
0
7
∑
j
=
0
7
(
X
(
i
,
j
)
)
2
∑
i
=
0
7
∑
j
=
0
7
(
Y
(
m
+
i
,
n
+
j
)
)
2
(
1
)
where the denominator of the formula (1), that is, the parts set forth below are quantities referred to as norm of the reference image and norm of the search image, respectively.
∑
i
=
0
7
∑
j
=
0
7
(
X
(
i
,
j
)
)
2
,
∑
i
=
0
7
∑
j
=
0
7
(
Y
(
m
+
i
,
n
+
j
)
)
2
This arithmetic operation is sequentially performed while m and n are altered in the range of m=0 to 7, and n=0 to 7, respectively, as shown in FIG.
6
. Thus, a distribution of the correlation values as shown in
FIG. 7
is determined. Detection of the peak position of the correlation values makes it possible to detect a position wherein a pattern, which is identical or similar to the pattern (cf.
FIG. 3
for example) of the reference image, exists on the search image (cf.
FIG. 5
for example).
The formula (1) is representative of a correlation arithmetic operation referred to as a so-called normalized correlation. According to the conventional technology, however, there is a need to prepare a very large scale circuit to execute the normalized correlation arithmetic operation.
In view of the foregoing, Japanese Patent Laid Open Gazettes Hei. 5-114028 and Hei. 5-189570 disclose a technology of reducing a scale of a circuit for performing the normalized correlation arithmetic operation. The technology disclosed the above-referenced Gazettes is to compress a two-dimensional image to a one-dimensional image through producing a projection histogram or addition of intensity values to an x-direction or a y-direction, so that an arithmetic operation for the normalized correlation is performed on the one-dimensional image. Thus, it is possible to greatly reduce a circuit scale since it is sufficient that the normalized correlation is performed on the one-dimensional image. However, there is a possibility that information is dropped in the process in which two-dimensional image is compressed to the one-dimensional image, and thus there is a possibility that accuracy of a position detection of a moving object is lowered.
Further, there is known a so-called SAD(Sum of Absolute Difference), instead of the normalized correlation of the formula (1), in which the correlation arithmetic operation is performed in accordance with the following formula (2).
D
(
m
,
n
)
=
∑
i
=
0
7
∑
j
=
0
7
&LeftBracketingBar;
Y
(
m
+
i
,
n
+
j
)
-
X
(
i
,
j
)
&RightBracketingBar;
(
2
)
where m=0~7, n=0~7
As a circuit for performing the SAD, it is possible to use a circuit which is greatly smaller in a circuit scale as compared with a circuit for performing the normalized correlation.
In case of the SAD, when the pattern of the search image is completely coincident with the pattern of the reference image, there is obtained D(m, n)=0. Thus, a position of the minimum peak value of D(m, n) obtained through the formula (2) is detected.
However, the SAD brings about great degradation in arithmetic accuracy when luminance of the search image is varied (for example, the moving object enters the shade), and thus in general the SAD involves a problem that it is greatly poor in a position detection ability for the moving object as compared with the normalized correlation. Accordingly, it is restricted to an especial case such as under condition that luminance of the search image is constant that accuracy of the same degree as the normalized correlation is ensure
Okabayashi Keiju
Sawasaki Naoyuki
Fujitsu Limited
Staas & Halsey , LLP
Tran Phuoc
LandOfFree
Image processing unit 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 processing unit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing unit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220189