-
The most recent advances in image retrieval show that text-based methods still outperform
content-based ones by approximately 30% [
3
]. Yet the question: ” What sentence can describe an
image” is still being researched by linguists, computer scientists and other academicians. This is
because different people will describe an image quite differently, depending on their interests and
prior knowledge. Some users look at an image in terms of the shape of its components, others the
size, color, texture, orientation or spatial location etcetera . In theory, using the features of an
image as its signature presents the users with a precise and focussed way of describing an image
according to their interests. User satisfaction is enhanced when one is presented with a variety
of ways to define his need. This is because the retrieval engine is customised according to the
selected choice / requirement. This study retrieves images based upon the shape of its components
by using mathematical morphology techniques. Attribute filtering is used to identify subsets of the
image that satisfy the requirements of a particular property or attribute. Forexample, attributes
like moments and length (or width / volume) are useful for spatial and size information
respectively [
10
]. The selected components are then used for further analysis like the formation of a
pattern spectrum. Pattern spectrum has been used to obtain information about the contents and
distribution of an image including it’s spatial location [
10, 9, 5
]. We present the results of using
pattern spectra for content-based image retrieval in large-scale databases. It is an extension of
the method proposed by Urbach et al [
8
] but combined with color information and applied within
the image retrieval context. The objective was to identify the 1000 most similar images from the
20,000 IAPR TC-12 database by using a purely visual, fully automated modality [
2
].
Section 2 briefly describes the theory of our method, the experiments and results are contained
in Section 3 and 4 and Section 5 has the concluding remarks and on-going work.
2
2-D Shape-Size Pattern Spectra
Pattern spectrum is a quantitative description of the contents of an image after the application
of a granulometric operation [
5
]. Granulometry is when an image is successively sieved using
filters of increasing diameters, r, so that information can be obtained about its components that
satisfy the properties of r. A size granulometry obtains the size distribution of an image by using
sieves of increasing sizes herein represented by area. Let X , Y represent an image then the size
granulometry (Γr) is a set of filters {Γr} with r from some totally ordered set Λ (usually Λ ⊂ R
or Z ) satisfying the properties:
Γr(X) ⊆ X
X ⊆ Y ⇒ Γr(X) ⊆ Γr(Y )
Γs(Γr(X)) = Γmax(r,s)(X),
for all r, s ∈ Λ. Equations (1),(2) and (3) define Γr as being anti-extensive, increasing and
idempotent respectively. Attribute openings are size granulometries since they share the same
properties [
1, 10
]. The pattern spectrum, sΓ(X), obtained by applying the size granulometry,
{Γτ }, to a binary image X is defined by [
5
] as:
(sΓ(X))(u) = −
dA(Γr(X))
dr
r=u
where A(X) is the area of X.
Similarly, shape granulometry filters image contents using sieves of different shapes [
8, 9
]. Urbach
and Wilkinson [
9
] defined shape granulometry, of X, as a family of filters, {Φr}, with shape
parameter, r, from some totally ordered set Λ (usually Λ ⊂ R or Z) with the following properties:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
in which tC stands for a scaling of set C by a factor t, and,
Φr(X) ⊆ X
Φr(tX) = t(Φr(X)),
Φs(Φr(X)) = Φmax(r,s)(X),
for all r, s ∈ Λ and t > 0. Equations (5),(6) and (7) define Φr as anti-extensive, scale invariant
and idempotent respectively. Therefore, attribute thinnings are shape granulometries since they
share the same properties including the non-increasing criterion[
8
]. The shape pattern spectrum,
sΦ(X), is obtained by applying the shape granulometry, {Φτ }, to a binary image X and defined
as [
8
]:
(sΦ(X))(u) = −
dA(Φr(X))
dr
r=u
P3
0
P2
0
P1
0
P3
1
P0
0
C0
2
?
peak components
node members
max-Tree
2-D spectrum
this are found in [
8
].
2.0.1
Computing the shape-size pattern spectra
The same method as was used in [
8
] has been adopted for application within CBIR. The max-tree
approach [
6, 7
] was used to implement the attribute thinnings and openings in grey-scale. The
subsets (connected components) of the image are arranged into a tree structure and filtered by
Chk at levels h = 0, 1, 2, 3, the resultant max-tree and corresponding spectrum.
removing the nodes which do not satisfy a given criterion. A max tree is a rooted tree in which
each of its nodes, Chk, at gray-level h corresponds to a peak component, Phk [
6
]. An example is
shown in Figure 1 which illustrates the peak components, P k, of a 1-D signal, the corresponding
h
Let {Γr} be a size distribution with r from some finite set Λr and {Φs} a shape distribution with
s from some index set Λs. If S is the 2-D array that stores the final 2-D spectrum, then each cell,
S(r, s), contains the sum of gray levels of Chk that falls within size class r− and r and shape class
s− and s. The 2-D pattern spectrum is then computed from the max-tree as follows:
• Set all elements of the array S to zero.
• Compute the max-tree according to the algorithm in [
7
].
• As the max-tree is built, compute the area A(Phk) and moment of inertia I(Phk) of each node.
• For each node Chk:
– Compute the size class r from the area A(Phk);
– Compute the shape class s from I(Phk) / A2(Phk);
– Compute the gray level difference δh, between the current node and its parent;
– Add the product of δh and A(Phk) to S(r, s).
3
Experiments
The objective of our experiments was: given a sample image, find as many relevant images as
possible from the IAPR TC-12 photographic collection [
3
]. The procedure that was undertaken is
as follows:
1. Images are first pre-processed by filtering off all components whose area is less than 30% of
the total image size. This was after comparisons with other size ranges indicated that the
discriminative power lies in the large particles. Figure 2 illustrates detailed MAP results
after using different class sizes. It is observed that the smaller particles performed poorer
than the larger ones and that using all particles without any filtering performs worse than
using particles over 30% or 75% of total area.
2. The shape-size pattern spectrum is then extracted from all images including the query
images. The size and shape ranges were between 50, 000 − 172, 800 and 1 − 53 respectively. A
20 by 15 bin histogram which translates into a 1 × 600 array representation per image was
chosen. Additionally, conversion of the images into XYZ and YUV color spaces as well as
grayscale (PGM) was performed. This was to test whether additional information is
captured from the color matrices. Visual analysis showed that unlike YUV and XYZ which
performed worse than the grayscale images, RGB representation improved the results.
3. One of the three topic images was selected as the query image according to what the authors
thought provided the most meaningful retrievals. The list of the chosen topic images is
provided in the appendix.
4. The similarity measure used is the reciprocal of the L1 Norm.
Sim(X, Y ) =
1
P(xi − yi)
(9)
3.1
Submitted Runs
Four runs were submitted:
1. PGM2007 - the shape-size pattern spectrum of the grayscale images are compared.
2. Max2007 - the maximum of red, green and blue bands of the images are compared.
3. Concatenate2007 - the concatenated red, green and blue bands of the images are compared
(a 1 × 1800 array).
4. JSD2007 - same as (3) above but comparison with the Jensen-Shannon divergence [
4
].
We observed that most queries returned images based on their shapes. For example an image of
a hill returns images of hills / mountains. So is the case with images of people, beaches, skies,
buildings etcetera. An image with more buildings than people returns more results of buildings
(some of them without people) than people. A group of people standing in front of a mountain
landscape returns a group of people in front of buildings, mountains or in a city square or anywhere
else. But if the mountains cover a larger percentage of the picture, then the returned results are
more of mountains than people. Similarly, a duck swimming in water returns many images of birds
flying in the sky and hens eating on a road. This is because the shapes of ducks, birds and hens
are similar. The texture of the image also affects the performance of this method. For example,
the image of a bird flying in a clear sky returns many images of birds or aeroplanes flying in the
sky. But the one with a bird flying in a cloudy sky returns pictures of beds, clouds without birds,
mountains covered in snow and some beach pictures. One of the poorest performances was the
meat dishes which returned buildings, landscapes, beds, and people with no food and without
food.
The overall performance of the submitted runs is shown in Table 1. The RGB concatenated
version using L1 Norm produces the best results and improves performance by 23%. As expected,
all methods that incorporate color information perform better than the one without (PGM).
This shows that more information has been obtained from the color matrices and so images with
similar colors are grouped closer together. For example, images taken at night return more black
pictures just as the ones taken in deserts return more brown ones. Interestingly, the images
with two dominant colors seemed to outperform those with only one dominant color or many
colors. Table 1 also gives surprising results that show how the maximum of the RGB bands
using L1 norm outperformed the concatenated version using JSD. This could be due to the loss
of information during normalization. This clearly shows that the use of an appropriate similarity
measure significantly contributes to the performance of our system.
5
Conclusion
This paper uses the shape-size pattern spectrum as the fundamental image signature for
contentbased image retrieval. The pattern spectrum is obtained from the red, green and blue color bands
of the image and compared using the L1-Norm. Our experiments have shown that this results in
very logical and interesting performance although the MAP scores remain low. We believe that
one of the ways of improving the MAP scores is to represent a single topic by the combination of
the three provided sample images. This can be achieved by using relevance learning techniques
already in place. Secondly, the results have shown that textural information, especially within the
background, affects the performance of this system. We intend to incorporate both textural and
spatial information into the pattern spectrum. Other works in progress include identifying the
most appropriate shape parameters, attributes and similarity measures.
Appendix - Selected topic images and corresponding MAP
MAP
0.001
0.0016
0.0703
0.0189
0.1554
0.0192
0.0027
0.0288
0.0002
0.0037
0.0224
0.0033
0.0364
0.0055
0.0001
0.0085
0.001
0.0491
0.0594
0.003
0.0058
0.0029
0.0601
0.1016
0.2525
0.0362
0.0036
0.003
0.0133
0.0007