EP0866409A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Image retrieval apparatus and method
Assignee: Canon Inc
•
Filing: 1998-03-18
•
Granted: —
•
Expires: 2018-03-18
Abstract
Abstract An image feature amount extraction unit segments an image into a plurality of blocks and calculates the feature amount of each block. A feature amount label string generation unit adds a label to each block in accordance with the feature amount acquired for the block and arranges the labels on the basis of a predetermined block sequence to generate a label string. In retrieval, the similarity between the label string of a specified image and that of an image to be compared is calculated, and an image whose similarity exceeds a predetermined value is output as a retrieval result. In this way, similar image retrieval can be performed in consideration of the arrangement of feature amounts of images, and simultaneously, similar image retrieval can be performed while absorbing any difference due to a variation in photographing condition or the like.
Inventors
- 👤 Hirotaka Shiiyama
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-24 16:42
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5838; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
106 words
An image retrieval apparatus characterized by
comprising: addition means (14, S11 - S13) for segmenting an
image into a plurality of blocks and adding a label to a
feature amount acquired in correspondence with each
block; generation means (15, S14) for arranging labels
added by said addition means on the basis of a
predetermined block sequence to generate a label string; storage means (18, 18a, S15, S16) for storing the
label string generated by said generation means in
correspondence with the image; and retrieval means (16, 16a, S22 - S25) for
performing image retrieval on the basis of the label
string stored in said storage means.
Claim 2
Dependent Claim
55 words
The apparatus according to claim 1, wherein the label is unique to each cell obtained by
segmenting a multidimensional feature amount space into
a plurality of cells, and said addition means calculates the feature amount
of each block and adds a label of a cell to which the
calculated feature amount belongs to the block.
Claim 3
Dependent Claim
46 words
The apparatus according to claim 1, wherein the plurality of blocks are obtained by segmenting
the image into a plurality of blocks in horizontal and
vertical directions, and the block sequence used by said
generation means defines an order of obliquely scanning
the plurality of blocks.
Claim 4
Dependent Claim
51 words
The apparatus according to claim 1, wherein the plurality of blocks are obtained by segmenting
the image into a plurality of blocks in horizontal and
vertical directions, and the block sequence used by said
generation means defines an order of scanning the
plurality of blocks in the horizontal or vertical
direction.
Claim 5
Dependent Claim
73 words
The apparatus according to claim 1, wherein said retrieval means comprises arithmetic means (16, S22 - S24) for calculating a
similarity between a label string of a specified image
and a label string of an image to be compared stored in
said storage means, and output means (16, S24 - S26) for outputting, as a
retrieval result, an image to be compared whose
similarity calculated by said arithmetic means exceeds a
predetermined value.
Claim 6
Dependent Claim
72 words
The apparatus according to claim 5, wherein said arithmetic means has a penalty table which
holds a penalty value for a pair of label values,
acquires, with reference to the penalty table, the
penalty value for the pair of label values obtained from
the label string of the specified image and the label
string of the image to be compared, and calculates the
similarity on the basis of the acquired penalty value.
Claim 7
Dependent Claim
45 words
The apparatus according to claim 6, wherein the label is unique to each cell obtained by
segmenting a multidimensional feature amount space into
a plurality of cells, and the penalty value is set on the basis of a
distance between cells represented by two labels.
Claim 8
Dependent Claim
45 words
The apparatus according to claim 6, wherein said arithmetic means further adds a penalty value
corresponding to an excess or deficiency of labels in
calculating the similarity between the label string of
the specified image and the label string of the image to
be compared.
Claim 9
Dependent Claim
27 words
The apparatus according to claim 8, wherein the penalty value corresponding to the excess or
deficiency of labels is acquired on the basis of an
automaton theory.
Claim 10
Dependent Claim
98 words
The apparatus according to claim 1, wherein said retrieval means comprises a first table for registering an image ID group
having label strings generated by said generation means
as keys, arithmetic means (16, S23) for calculating a
similarity between a label string of a specified image
and a label string of an image to be compared stored in
said storage means, and extraction means (S24, S25) for acquiring a label
string whose similarity calculated by said arithmetic
means exceeds a predetermined value and extracting an
image corresponding to the acquired label string with
reference to the first table.
Claim 11
Dependent Claim
25 words
The apparatus according to claim 10, wherein the label string subjected to similarity
calculation by said arithmetic means is a field in the
first table.
Claim 12
Dependent Claim
47 words
The apparatus according to claim 10, wherein the label string subjected to similarity
calculation by said arithmetic means is one of label
strings stored in said storage means, which includes a
predetermined number or more labels similar to those in
the label string of the specified image.
Claim 13
Dependent Claim
70 words
The apparatus according to claim 12, characterized
by further comprising a second table for registering a label string
group of label strings stored in said storage means,
which includes labels as keys, and in that a label string including a predetermined number or
more labels similar to those included in the specified
image is acquired with reference to the second table and
subjected to similarity calculation by said arithmetic
means.
Claim 14
Dependent Claim
110 words
The apparatus according to claim 1, wherein the label string represents a two-dimensional
label matrix, and said retrieval means comprises first matching means (S101 - S112) for making a
label string extracted from a label matrix of a
retrieval specified image in units of rows correspond to
a label string extracted from a label matrix of an image
to be compared in units of rows by DP matching to obtain
a row array of the image to be compared, and second matching means (S113) for obtaining, by DP
matching, a similarity between a row array of the
retrieval specified image and the row array obtained by
said first matching means.
Claim 15
Dependent Claim
25 words
The apparatus according to claim 14, wherein the label string extracted in units of rows has an
array in the horizontal direction of the image.
Claim 16
Dependent Claim
25 words
The apparatus according to claim 14, wherein the label string extracted in units of rows has an
array in the vertical direction of the image.
Claim 17
Dependent Claim
34 words
The apparatus according to claim 14, characterized
by further comprising output means (S24a, S25a) for outputting, as a
retrieval result, an image whose similarity obtained by
said second matching means exceeds a predetermined value.
Claim 18
Dependent Claim
55 words
The apparatus according to claim 14, wherein said first matching means has a table which holds
a penalty value for a pair of labels, and refers to the
table in calculating a distance between the label string
of the retrieval specified image and the label string of
the image to be compared using DP matching.
Claim 19
Dependent Claim
45 words
The apparatus according to claim 18, wherein the label is unique to each cell obtained by
segmenting a multidimensional feature amount space into
a plurality of cells, and the penalty value is set on the basis of a
distance between cells represented by two labels.
Claim 20
Dependent Claim
60 words
The apparatus according to claim 14, wherein said second matching means has a table which holds
a penalty value for a pair of row numbers of the row
array and refers to the table in calculating the
similarity between the row array of the retrieval
specified image and the row array of the image to be
compared using DP matching.
Claim 21
Dependent Claim
92 words
The apparatus according to claim 14, characterized
by further comprising holding means (S121 - S132) for determining a
penalty value associated with a pair of rows on the
basis of the similarity between label strings in a row
direction of the retrieval specified image and holding
the penalty value, and in that said second matching means refers to the penalty
value held by said holding means in calculating the
similarity between the row array of the retrieval
specified image and the row array of the image to be
compared using DP matching.
Claim 22
Dependent Claim
45 words
The apparatus according to claim 18, wherein said first matching means applies a penalty and
constraint according to system expansion/contraction in
label comparison in calculating the similarity between
the label string of the retrieval specified image and
the label string stored in said storage means.
Claim 23
Dependent Claim
28 words
The apparatus according to claim 22, wherein the penalty and constraint according to system
expansion/contraction in label comparison are acquired
on the basis of a DP matching theory.
Claim 24
Dependent Claim
73 words
The apparatus according to claim 18, characterized
by further comprising a first table for registering an image ID group
having label strings generated by said generation means
as keys, and in that said output means acquires a label string whose
similarity calculated by said retrieval means exceeds a
predetermined value, extracts an image corresponding to
the acquired label string with reference to the first
table, and outputs the image as a retrieval result.
Claim 25
Dependent Claim
25 words
The apparatus according to claim 24, wherein the label matrix subjected to similarity
calculation by said retrieval means is a key in the
first table.
Claim 26
Dependent Claim
48 words
The apparatus according to claim 24, wherein the label matrix subjected to similarity
calculation by said retrieval means is one of label
matrixes stored in said storage means, which includes a
predetermined number or more labels similar to those in
the label matrix of the retrieval specified image.
Claim 27
Dependent Claim
70 words
The apparatus according to claim 26, characterized
by further comprising a second table for registering a label matrix
group of label matrixes stored in said storage means,
which includes labels as keys, and in that a label matrix including a predetermined number or
more labels similar to those included in the specified
image is acquired with reference to the second table and
subjected to similarity calculation by said arithmetic
means.
Claim 28
Dependent Claim
104 words
An image retrieval method characterized by
comprising: the addition step (S11 - S13) of segmenting an
image into a plurality of blocks and adding a label to a
feature amount acquired in correspondence with each
block; the generation step (S14) of arranging labels
added in the addition step on the basis of a
predetermined block sequence to generate a label string; the storage step (S15, S16) of storing the label
string generated in the generation step in
correspondence with the image; and the retrieval step (S22 - S25) of performing image
retrieval on the basis of the label string stored in the
storage step.
Claim 29
Dependent Claim
56 words
The method according to claim 28, wherein the label is unique to each cell obtained by
segmenting a multidimensional feature amount space into
a plurality of cells, and the addition step includes calculating the feature
amount of each block and adding a label of a cell to
which the calculated feature amount belongs to the block.
Claim 30
Dependent Claim
46 words
The method according to claim 28, wherein the plurality of blocks are obtained by segmenting
the image into a plurality of blocks in horizontal and
vertical directions, and the block sequence used in the
generation step defines an order of obliquely scanning
the plurality of blocks.
Claim 31
Dependent Claim
51 words
The method according to claim 28, wherein the plurality of blocks are obtained by segmenting
the image into a plurality of blocks in horizontal and
vertical directions, and the block sequence used in the
generation step defines an order of scanning the
plurality of blocks in the horizontal or vertical
direction.
Claim 32
Dependent Claim
73 words
The method according to claim 28, wherein the retrieval step comprises the arithmetic step (S22 - S24) of calculating a
similarity between a label string of a specified image
and a label string of an image to be compared stored in
the storage step, and the output step (S24 - S26) of outputting, as a
retrieval result, an image to be compared whose
similarity calculated in the arithmetic step exceeds a
predetermined value.
Claim 33
Dependent Claim
74 words
The method according to claim 32, wherein the arithmetic step has a penalty table which
holds a penalty value for a pair of label values, and
includes acquiring, with reference to the penalty table,
the penalty value for the pair of label values obtained
from the label string of the specified image and the
label string of the image to be compared, and
calculating the similarity on the basis of the acquired
penalty value.
Claim 34
Dependent Claim
45 words
The method according to claim 33, wherein the label is unique to each cell obtained by
segmenting a multidimensional feature amount space into
a plurality of cells, and the penalty value is set on the basis of a
distance between cells represented by two labels.
Claim 35
Dependent Claim
46 words
The method according to claim 33, wherein the arithmetic step includes further adding a
penalty value corresponding to an excess or deficiency
of labels in calculating the similarity between the
label string of the specified image and the label string
of the image to be compared.
Claim 36
Dependent Claim
27 words
The method according to claim 35, wherein the penalty value corresponding to the excess or
deficiency of labels is acquired on the basis of an
automaton theory.
Claim 37
Dependent Claim
99 words
The method according to claim 28, wherein the retrieval step comprises a first table for registering an image ID group
having label strings generated in the generation step as
keys, the arithmetic step (S23) of calculating a
similarity between a label string of a specified image
and a label string of an image to be compared stored in
the storage step, and the extraction step (S24, S25) of acquiring a
label string whose similarity calculated in the
arithmetic step exceeds a predetermined value and
extracting an image corresponding to the acquired label
string with reference to the first table.
Claim 38
Dependent Claim
25 words
The method according to claim 37, wherein the label string subjected to similarity
calculation in the arithmetic step is a key in the first
table.
Claim 39
Dependent Claim
47 words
The method according to claim 37, wherein the label string subjected to similarity
calculation in the arithmetic step is one of label
strings stored in the storage step, which includes a
predetermined number or more labels similar to those in
the label string of the specified image.
Claim 40
Dependent Claim
70 words
The method according to claim 39, characterized by
further comprising a second table for registering a label string
group of label strings stored in the storage step, which
includes labels as keys, and in that a label string including a predetermined number or
more labels similar to those included in the specified
image is acquired with reference to the second table and
subjected to similarity calculation in the arithmetic
step.
Claim 41
Dependent Claim
112 words
The method according to claim 28, wherein the label string represents a two-dimensional
label matrix, and the retrieval step comprises the first matching step (S101 - S112) of making a
label string extracted from a label matrix of a
retrieval specified image in units of rows correspond to
a label string extracted from a label matrix of an image
to be compared in units of rows by DP matching to obtain
a row array of the image to be compared, and the second matching step (S113) of obtaining, by
DP matching, a similarity between a row array of the
retrieval specified image and the row array obtained in
the first matching step.
Claim 42
Dependent Claim
25 words
The method according to claim 41, wherein the label string extracted in units of rows has an
array in the horizontal direction of the image.
Claim 43
Dependent Claim
25 words
The method according to claim 41, wherein the label string extracted in units of rows has an
array in the vertical direction of the image.
Claim 44
Dependent Claim
35 words
The method according to claim 41, characterized by
further comprising the output step (S24a, S25a) of outputting, as a
retrieval result, an image whose similarity obtained in
the second matching step exceeds a predetermined value.
Claim 45
Dependent Claim
56 words
The method according to claim 41, wherein the first matching step has a table which holds a
penalty value for a pair of labels, and includes
referring to the table in calculating a distance between
the label string of the retrieval specified image and
the label string of the image to be compared using DP
matching.
Claim 46
Dependent Claim
45 words
The method according to claim 45, wherein the label is unique to each cell obtained by
segmenting a multidimensional feature amount space into
a plurality of cells, and the penalty value is set on the basis of a
distance between cells represented by two labels.
Claim 47
Dependent Claim
61 words
The method according to claim 41, wherein the second matching step has a table which holds a
penalty value for a pair of row numbers of the row array
and includes referring to the table in calculating the
similarity between the row array of the retrieval
specified image and the row array of the image to be
compared using DP matching.
Claim 48
Dependent Claim
94 words
The method according to claim 41, characterized by
further comprising the holding step (S121 - S132) of determining a
penalty value associated with a pair of rows on the
basis of the similarity between label strings in a row
direction of the retrieval specified image and holding
the penalty value, and in that the second matching step includes referring to the
penalty value held in the holding step in calculating
the similarity between the row array of the retrieval
specified image and the row array of the image to be
compared using DP matching.
Claim 49
Dependent Claim
46 words
The method according to claim 45, wherein the first matching step includes applying a
penalty and constraint according to system
expansion/contraction in label comparison in calculating
the similarity between the label string of the retrieval
specified image and the label string stored in the
storage step.
Claim 50
Dependent Claim
28 words
The method according to claim 49, wherein the penalty and constraint according to system
expansion/contraction in label comparison are acquired
on the basis of a DP matching theory.
Claim 51
Dependent Claim
74 words
The method according to claim 45, characterized by
further comprising a first table for registering an image ID group
having label strings generated in the generation step as
keys, and in that the output step includes acquiring a label string
whose similarity calculated in the retrieval step
exceeds a predetermined value, extracting an image
corresponding to the acquired label string with
reference to the first table, and outputting the image
as a retrieval result.
Claim 52
Dependent Claim
25 words
The method according to claim 51, wherein the label matrix subjected to similarity
calculation in the retrieval step is a key in the first
table.
Claim 53
Dependent Claim
50 words
The method according to claim 51, characterized in
that the label matrix subjected to similarity
calculation in the retrieval step is one of label
matrixes stored in the storage step, which includes a
predetermined number or more labels similar to those in
the label matrix of the retrieval specified image.
Claim 54
Dependent Claim
70 words
The method according to claim 53, characterized by
further comprising a second table for registering a label matrix
group of label matrixes stored in the storage step,
which includes labels as keys, and in that a label matrix including a predetermined number or
more labels similar to those included in the specified
image is acquired with reference to the second table and
subjected to similarity calculation in the arithmetic
step.
Claim 55
Dependent Claim
113 words
A computer readable memory which stores a control
program for performing image retrieval, characterized in
that said control program comprises: a code for addition processing of segmenting an
image into a plurality of blocks and adding a label to a
feature amount acquired in correspondence with each
block; a code for generation processing of arranging
labels added by addition processing on the basis of a
predetermined block sequence to generate a label string; a code for storage processing of storing the label
string generated by generation processing in
correspondence with the image; and a code for retrieval processing of performing
image retrieval on the basis of the label string stored
by storage processing.
Claim 56
Dependent Claim
113 words
The memory according to claim 55, wherein the label string represents a two-dimensional
label matrix, and the code for retrieval processing comprises a code for first matching processing of making a
label string extracted from a label matrix of a
retrieval specified image in units of rows correspond to
a label string extracted from a label matrix of an image
to be compared in units of rows by DP matching to obtain
a row array of the image to be compared, and a code for second matching processing of obtaining,
by DP matching, a similarity between a row array of the
retrieval specified image and the row array obtained by
first matching processing.
Claim 57
Dependent Claim
59 words
The apparatus according to claim 1, wherein said
retrieval means utilizes DP-matching method, further comprising: setting means for setting width of a matching
window of the DP-matching performed by said retrieval
means, and controlling means for controlling ambiguity of
said retrieval means by changing the width of the
matching window based on the width set by said setting
means.
Claim 58
Dependent Claim
62 words
The method according to claim 28, wherein DP-matching
method is utilized in said retrieval step, further comprising: a setting step of setting width of a matching
window of the DP-matching performed in said retrieval
step, and controlling step of controlling ambiguity of said
retrieval step by changing the width of the matching
window based on the width set in said setting step.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.