Image analysis – Image transformation or preprocessing – Image storage or retrieval
Reexamination Certificate
2000-07-21
2003-11-11
Mariam, Daniel G. (Department: 2721)
Image analysis
Image transformation or preprocessing
Image storage or retrieval
C382S191000, C382S209000, C358S403000, C707S793000
Reexamination Certificate
active
06647157
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an image search apparatus and method for searching for a desired image (image data), and a computer readable storage medium.
BACKGROUND OF THE INVENTION
Conventionally, various techniques for searching for image data of similar images (to be simply referred to as images hereinafter) have been proposed. Especially for a texture image, a scheme that uses Fourier transformation in extraction of features of the texture image is known (R. Bajcsy, “Computer description of Textured Surfaces”, Proc. 3rd Int. Conf. on Artificial Intelligence, pp. 572-579, 1973), and an image search apparatus that uses this scheme can be proposed.
The feature extraction method of a texture image using Fourier transformation will be briefly explained below. In this scheme, the two-dimensional Fourier transform of an input image f(x, y) is computed by:
F
(
i
,
j
)
=
∑
x
=
1
n
∑
y
=
1
n
f
(
x
,
y
)
ⅇ
-
2
π
-
1
(
ⅈ
x
+
j
y
)
/
n
(
1
)
and, a power spectrum p that indicates the magnitude of the frequency component of the image f is computed by:
p
(
i, j
)=|
F
(
i, j
)|
2
(2)
(where i and j are natural numbers (the same applies to the following description))
At this time, the power spectrum p which indicates the magnitude of the frequency component of the image f and is computed by equation (2) is adjusted so that zero frequency matches the center of spectrum, by replacing the first and third quadrants, and the second and fourth quadrants in the four quadrants of the two-dimensional coordinate system which includes the image f(x, y), and is defined by orthogonal X- and Y-axes.
When the power spectrum p′ that has been adjusted as described above undergoes polar coordinate conversion, a sum total p(r) of components the frequency of which is r, and a sum total p(&thgr;) of frequency components in the &thgr; direction are respectively computed by:
p
(
r
)
=
∑
i
=
0
n
-
1
∑
j
=
0
n
-
1
p
(
i
,
j
)
,
i
2
+
j
2
=
r
2
(
3
)
p
(
θ
)
=
∑
i
=
0
n
-
1
∑
j
=
0
n
-
1
p
(
i
,
j
)
,
tan
-
1
(
j
/
i
)
=
θ
(
4
)
(where r is the distance from the origin, and &thgr; is the angle the polar axis of the polar coordinate system makes with r (the same applies to the following description))
According to the distribution of p(&thgr;) computed by equations (4), the directionality of texture of the image f(x, y) can be determined. This directionality recognition exploits the fact that if the input image has directionality &thgr;, a peak appears on the power spectrum at the angle &thgr;.
The number of peaks included in this power spectrum and their magnitudes are detected, and as a result of detection, if the number of peaks is 1, “unidirectionality” is determined, if the number of peaks is 2, “bidirectionality” is determined, and if three or more peaks are included, “no directionality” is determined.
However, upon applying the aforementioned feature extraction method to image search, the following problems remain unsolved.
(1) Directionality determination based on peak detection cannot be done unless the sum total for the entire space of the power spectrum p is computed, as indicated by equations (4). For this reason, the time required for automatic computations using an apparatus such as a computer is problematic, and an apparatus having high computation processing capability to some extent must be adopted, resulting in high total cost.
(2) When similarity between two input images is determined by comparing the directionalities of the two images, a method of normalizing the distributions of power spectra of the two images, and comparing the power spectra of the two images after normalization may be normally used. In this case, the same problem as in (1) is posed, resulting in poor practicality.
(3) Even when an input image has three or more directionalities in practice as a result of determining its directionality, “no directionality” is determined, as described above.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of the aforementioned problems, and has as its object to provide an image search apparatus and method, which accurately search for an image with high precision within a practical required time, and a computer readable storage medium.
In order to achieve the above object, an image search apparatus according to the present invention is characterized by the following arrangement.
That is, an image search apparatus comprises power spectrum computation means for computing a two-dimensional power spectrum of an input image by computing a two-dimensional Fourier transform of the image, standard deviation matrix generation means for segmenting the two-dimensional power spectrum computed by the power spectrum computation means into a plurality of blocks on a two-dimensional coordinate system, computing standard deviations of power spectrum components in units of blocks, and generating a matrix of the generated standard deviations, feature amount computation means for computing sums of the standard deviations as feature amounts in units of directions by making the matrix generated by the standard deviation matrix generation means using predetermined mask patterns which are prepared in advance in units of directions of interest and correspond to a pattern of the matrix, feature determination means for determining a directionality of the image on the basis of the feature amounts computed by the feature amount computation means, storage means for classifying and storing the image and the feature amounts computed by the feature amount computation means on the basis of the directionality determination result of the feature determination means, and image search means for searching for a similar image on the basis of the feature amounts and determination result stored in the storage means.
For example, the standard deviation matrix generation means generates the matrix of the standard deviations for blocks corresponding to first and second quadrants of the two-dimensional coordinate system of the plurality of segmented blocks.
For example, the mask patterns in units of directions of interest are multi-valued masks which are weighted to have the directions of interest thereof as peaks.
For example, the image search means computes a similarity between a query image designated as a query and another image by considering, as vectors, feature amounts which are stored in the storage means in correspondence with the query image and the other image as a similar image candidate, and are computed in units of directions of interest, and computing an inner product of the vectors.
In order to achieve the above object, an image search method according to the present invention is characterized by the following arrangement.
That is, an image search method comprises the power spectrum computation step of computing a two-dimensional power spectrum of an input image by computing a two-dimensional Fourier transform of the image, the standard deviation matrix generation step of segmenting the two-dimensional power spectrum computed in the power spectrum computation step into a plurality of blocks on a two-dimensional coordinate system, computing standard deviations of power spectrum components in units of blocks, and generating a matrix of the generated standard deviations, the feature amount computation step of computing sums of the standard deviations as feature amounts in units of directions by making the matrix generated in the standard deviation matrix generation step using predetermined mask patterns which are prepared in advance in units of directions of interest and correspond to a pattern of the matrix, the feature determination step of determining a directionality of the image on the basis of the feature amounts computed in the feature amount computation step,
Shiiyama Hirotaka
Tojo Hiroshi
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Mariam Daniel G.
LandOfFree
Image search apparatus and method 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 search apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image search apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3151184