Diplomarbeit im Fach Informatik
Rheinisch-Westfälische Technische Hochschule Aachen
Lehrstuhl für Informatik VI
Prof. Dr.-Ing. H. Ney

Features for Image Retrieval

vorgelegt von:Thomas Deselaers
Matrikelnummer 218894
Gutachter:
Prof. Dr.-Ing. H. Ney
Prof. Dr. T. Seidl
Betreuer:
Dipl.-Inform. D. Keysers

Hiermit versichere ich, dass ich die vorliegende Diplomarbeit selbständig verfasst und keine
anderen als die angegebenen Hilfsmittel verwendet habe. Alle Textauszüge und Grafiken, diesinngemäß oder wörtlich aus veröffentlichten Schriften entnommen wurden, sind durch Referenzen gekennzeichnet.

Aachen, im Dezember 2003

Thomas Deselaers

Acknowledgements
The present work originates from my work as student researcher at the Chair of Computer
Science VI of the RWTH Aachen University of Technology, where I have been a member of theimage recognition group since July 2001. I would like to thank Prof. Dr.-Ing. Hermann Ney
for the interesting possibilities at this department and the chance to attend the conference“25th Pattern Recognition Symposium” in Magdeburg.
Furthermore, I would like to thank Daniel Keysers for the helpful suggestions, discussions
and assistances this work received. His ideas and suggestions were a great help.
I would like to thank Prof. Dr. Thomas Seidl as well, who kindly accepted to attend the work.
Also, I would like to thank the other student members of the image recognition group at the
Chair of Computer Science VI – Christian Gollan, Tobias Kölsch, Philippe Dreuw, and Ilja
Bezrukov – for many discussions, helpful tips and comments.
Also I would like to thank Diego Biurrun, Stefan Jacobs, and Arne Mauser for proof reading
the manuscript.
And of course special thanks go to my parents for all the possibilities they gave me and arestill giving to me and to my girl friend Daniela for supporting me while doing this work.

Contents
1 Introduction

1

2 Basic principles
2.1 Basic Principles for Image Retrieval . . . . . . . . . . . . . . . . . . . . . . .
2.2 Basic Principles for Image Clustering . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 k-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 LBG-Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Basic Principles for Classification . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
4
5
6
7
9

3 State of the Art in Content-Based Image Retrieval
3.1 Related Work in Content-Based Image Retrieval . . . . . . . . . . . . . . . .
3.2 Related Work in Clustering of Images . . . . . . . . . . . . . . . . . . . . . .
3.3 Related Work in Object-Recognition and Classification of Images . . . . . . .

11
11
13
14

4 Features for Content-Based Image Retrieval
4.1 Image Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Color Histograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Invariant Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Invariant Features by Integration . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Invariant Feature Histograms . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 Invariant Feature Vectors . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 Invariant Fourier Mellin Features . . . . . . . . . . . . . . . . . . . . .
4.5 Gabor Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6 Tamura Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Global Texture Descriptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.8 Local Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.9 Histograms of Local Features . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.10 Region-Based Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.11 PCA Transformed Features . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.12 Correlation of Different Features . . . . . . . . . . . . . . . . . . . . . . . . .

17
17
18
19
20
23
24
24
25
27
29
30
31
32
32
33

5 Comparing Features
5.1 Histogram Comparison Measures . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Bin-by-Bin Comparison Measures . . . . . . . . . . . . . . . . . . . . .
5.1.2 Cross-Bin Comparison Measures . . . . . . . . . . . . . . . . . . . . .
5.2 Comparing Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35
35
35
37
40

i

5.2.1 Euclidean Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Tangent Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.3 Image Distortion Model . . . . . . . . . . . . . . . . . . . . . . . . . .
Comparing Images Based on Local Features . . . . . . . . . . . . . . . . . . .
5.3.1 Direct Transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 Local Feature Image Distortion Model . . . . . . . . . . . . . . . . . .
Comparing Region-Based Descriptions of Images . . . . . . . . . . . . . . . .
5.4.1 Integrated Region Matching . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2 Quantized Hungarian Region Matching . . . . . . . . . . . . . . . . .
Other Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40
40
41
42
42
42
42
43
43
44

6 Applications
6.1 Content-Based Image Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Grouping of Visually Similar Images . . . . . . . . . . . . . . . . . . . . . . .
6.3 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45
45
46
46

7 Databases
7.1 Corel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 WANG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Corel Subset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4 IRMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5 CalTech Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.6 UW Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.7 ZuBuD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.8 MPEG-7 Test Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.9 Google . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.10 COIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49
49
49
50
51
51
52
53
54
54
55

8 Results
8.1 Performance Evaluation for Content-Based Image Retrieval . . . . . . . . . .
8.2 Results for Content-Based Image Retrieval . . . . . . . . . . . . . . . . . . . .
8.2.1 Comparison of Different Distance Functions . . . . . . . . . . . . . . .
8.2.2 Comparison of Different Features . . . . . . . . . . . . . . . . . . . . .
8.2.3 Image Retrieval Using Different Databases . . . . . . . . . . . . . . . .
8.3 Performance Evaluation for Clustering Visually Similar Images . . . . . . . .
8.4 Results for Clustering Visually Similar Images . . . . . . . . . . . . . . . . . .
8.4.1 Clustering the Google Images . . . . . . . . . . . . . . . . . . . . . . .
8.4.2 Clustering the WANG & COIL Images . . . . . . . . . . . . . . . . . .

57
57
59
60
65
68
76
76
77
77

9 Conclusion and Perspectives

81

A Software Documentation
A.1 FIRE Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Clustering Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.3 Feature Extraction Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85
85
86
88

B Additional Tables

95

5.3

5.4

5.5

ii

List of Tables
2.1

Symbols used in this work.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

4.1

Monomials used for invariant feature vectors. . . . . . . . . . . . . . . . . . .

24

8.1 Error rates on WANG and IRMA-1617 using different comparison measures. .
8.2 Error rates using time warp distance on IRMA-1617. . . . . . . . . . . . . . .
8.3 Error rates for the IRMA-1617 database using different comparison measures.
8.4 Error rates using region based features for the WANG database. . . . . . . .
8.5 Comparison of error rates on IRMA-1617 for local features and IDM. . . . . .
8.6 Error rates using different features for the WANG database. . . . . . . . . . .
8.7 Error rates using different features for the IRMA-1617 database. . . . . . . .
8.8 Error rates using partially rotation invariant feature histograms. . . . . . . .
8.9 Results for different training situations on the IRMA-3879 database. . . . . .
8.10 Error rates obtained on the IRMA-1617 database. . . . . . . . . . . . . . . .
8.11 Results for different training situations for the WANG and UW databases. . .
8.12 Error rates for the WANG and Corel subset database. . . . . . . . . . . . . .
8.13 Error rates for WANG subsets. . . . . . . . . . . . . . . . . . . . . . . . . . .
g for the MPEG-7 databases. . . . . . . . . . . . . . . . . . . . . . . . . .
8.14 Rank
8.15 Error rates for ZuBuD using different methods. . . . . . . . . . . . . . . . . .
8.16 Equal error rates on the CalTech database. . . . . . . . . . . . . . . . . . . .
8.17 Results for clustering WANG. . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.18 Results for clustering COIL. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61
61
64
64
65
66
66
68
70
71
72
73
73
74
75
76
79
79

A.1 Available dissimilarity measures. . . . . . . . . . . . . . . . . . . . . . . . . .

89

B.1
B.2
B.3
B.4
B.5

95
97
99
99
100

Error rates for different features on WANG database. . . . . . . . . . . . . . .
Error rates for different features on IRMA-1617 database. . . . . . . . . . . .
Error rates for different features on IRMA-3879 database . . . . . . . . . . .
Error rates for different dissimilarity measures on WANG database. . . . . . .
Error rates for different dissimilarity measures on IRMA-1617 database. . . .

iii

iv

List of Figures
2.1
2.2

Content-based image retrieval. . . . . . . . . . . . . . . . . . . . . . . . . . .
Linde Buzo Gray clustering. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
7

4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9

Examples of bin-assignment functions. . . . . . . . . . . . . . . . . . . . . . .
Calculation strategy for invariant integration. . . . . . . . . . . . . . . . . . .
The rel-function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Creation of RST-invariant features. . . . . . . . . . . . . . . . . . . . . . . . .
Example images for texture properties. . . . . . . . . . . . . . . . . . . . . . .
Extraction of local features. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Classification using local features. . . . . . . . . . . . . . . . . . . . . . . . . .
Creation of local feature histograms. . . . . . . . . . . . . . . . . . . . . . . .
Example segmentations of images. . . . . . . . . . . . . . . . . . . . . . . . .

19
22
23
26
27
30
31
32
33

5.1
5.2
5.3
5.4
5.5

Three histograms with pairwise identical bin-by-bin distances. . . . . . . . . .
Time warp distances. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Examples of alignment graphs. . . . . . . . . . . . . . . . . . . . . . . . . . .
Deformation constraints for time warp distance. . . . . . . . . . . . . . . . . .
Region alignments for the quantized Hungarian region region matching. . . .

35
39
39
40
44

6.1
6.2

Screenshot of FIRE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Screenshot of the clustering application. . . . . . . . . . . . . . . . . . . . . .

47
48

7.1 Example images from the Corel database. . . . . . . . . . . . . . . . . . . . .
7.2 One example image from each of the 10 classes of the WANG database. . . .
7.3 Example images from the Corel subset. . . . . . . . . . . . . . . . . . . . . .
7.4 One image from each of the six IRMA-1617 classes. . . . . . . . . . . . . . . .
7.5 Several images from class “chest” from the IRMA-1617 database. . . . . . . .
7.6 Examples of the CalTech datasets. . . . . . . . . . . . . . . . . . . . . . . . .
7.7 Examples from the UW database with annotation. . . . . . . . . . . . . . . .
7.8 Examples from ZuBuD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.9 Example images from the MPEG-7 test set. . . . . . . . . . . . . . . . . . . .
7.10 The first five results for five image searches on Google in March 2003. . . . .
7.11 All objects from the COIL-100 database. . . . . . . . . . . . . . . . . . . . . .
7.12 The 20 objects from the COIL-100 database. . . . . . . . . . . . . . . . . . .

50
50
51
52
52
53
53
54
54
55
56
56

8.1
8.2
8.3

60
62
63

Correlation of performance measures scaled to [−100, 100]. . . . . . . . . . . .
P R graphs for WANG and IRMA-1617 using different distance functions. . .
Different parameters for the time warp distance. . . . . . . . . . . . . . . . .
v

8.4 P R graphs for WANG and IRMA-1617 . . . . . . . . . . . . . . . . . . . . .
8.5 Results from Multi-dimensional scaling for WANG features. . . . . . . . . . .
8.6 Results from Multi-dimensional scaling for IRMA features. . . . . . . . . . .
8.7 Class wise P R-graphs for the six IRMA classes. . . . . . . . . . . . . . . . . .
8.8 Graph of Recall vs NR for the MPEG-7 database. . . . . . . . . . . . . . . .
8.9 Results from Google image search for query “cookies”, unprocessed. . . . . .
8.10 Results from Google image search for query “cookies”, processed. . . . . . . .
8.11 Results from Google image search for the query “aircraft”, processed. . . . .

vi

67
68
69
71
74
77
78
78

Chapter 1

Introduction
The growing amount of digital images caused by the more and more ubiquitous presenceof digital cameras and, as a result, the many images on the world wide web confronts theusers with new problems. Images are a fundamental part of our daily communication. The
German saying “Ein Bild sagt mehr als tausend Worte” (literally: “A picture says more thana thousand words.”) reflects this. The huge amount of pictures digitally available is not
manageable by humans any more [Chen & Wang 02]. A person searching for a picture in a
database of 100 images will probably find what she searches for quite fast by just viewing theimages or small versions of the images (thumbnails). If a thousand, ten thousand, or even more
images are involved, the task becomes boring and interminable [Markkula & Sormunen 98].
Computers might be able to help here in the same way as they already do for searchingtext documents. A well-established example for text retrieval is the Internet search engine
Google. Entering some keywords often helps finding related documents from the vast amountof documents available on the Internet. Google also offers a possibility to search for images,
but the way the search is performed does not always lead to satisfactory results.
One way to search in image databases is to create a textual description of all the images
in the database and use the methods from text-based information retrieval to search basedon the textual descriptions. Unfortunately, this method is not feasible. On the one handannotating images has to be done manually and is a very time-consuming task and on theother hand images may have contents that words cannot convey. Due to the rich content
of images and the subjectivity of human perception no textual description can be absolutely
complete and 100% correct [Siggelkow 02]. For example it is difficult to cover the complete
spirit of Da Vinci’s Mona Lisa in words or the mood of a sunset at the seaside. Similarityof images depends on the user and the context of the query. In a general image databasea radiograph might only be labeled as “radiograph” whereas this obviously is not sufficient
within a medical database consisting of different types of radiographs only.
Apparently, other methods to search and index images are needed. A broad variety of
applications requires searching for images: in medical applications many images are produced
and a physician might search for similar images to learn about treatments of former patientsand their outcomes [Petrakis & Faloutsos+ 02]. A journalist might look for an image toillustrate an article [Markkula & Sormunen 98]. All these examples confront us with thesame problem: The search is not an exact search like in traditional databases (e.g. thephysician asks the database for the treatment of a patient with a certain name) but instead,the search is imprecise. That is, we are looking for similar entries from the database. Similar1

(this imprecise criterion) has to be precisely defined to enable an automatic search process.
In fact it is possible to reason precisely about imprecise data [Subrahmanian & Tripathi 98].
Some of the areas mentioned allow for or even require the inclusion of special domain
knowledge to obtain suitable results. Other tasks are too general to find special domain
knowledge [Smeulders & Worring+ 00]. To retrieve general image data from an unrestricted
image database no special knowledge can be applied, but to retrieve similar faces it is possible
and recommendable to include domain-knowledge.
In this work a focus is set on features for image retrieval. That is, we investigate thedevelopment of representations that allow searching for images similar to a given image. Thesefeatures also open up new perspectives in other fields. The features investigated here are used
for the tasks of classification and for clustering images into visually similar groups. Many
features that were used in image retrieval before are exemplified and compared.
The main contributions of this work are quantifieable examinations of a wide variety ofdifferent features and different distance measures and a method to compare different contentbased image retrieval systems. The method is an extension of the method proposed in[Müller & Müller+ 01]. We implemented a system using the features and distance measures
examined for classification and a system to cluster images according to their visual appearance. To achieve these goals, a flexible and easily extensible content-based image retrieval
system was developed as well as a program to cluster images.
The remainder of this document is organized as follows: Chapter 2 presents the tasks
investigated and introduces the underlying principles. Chapter 3 gives a survey of image
retrieval techniques and systems available to give an idea of what has already been achievedin this field and to present the methods used. In Chapter 4 we introduce different featurestested in the context of this work. The features are the first step towards a definition ofsimilarity. We present the preprocessing that is applied to the images to make it possible
to compare them. Chapter 5 introduces a variety of distance measures to compare features.
Together, the two Chapters define different ways to measure similarity. In Chapter 6 we
present the applications built on top of the features and the distance measures. Chapter 7
presents the databases used to test the applications. These databases are mainly used forimage retrieval, but also some new and interesting results for classification and clustering
have been achieved. Chapter 8 presents an approach to evaluate the performance of image
retrieval systems and clustering algorithms. Results for the three applications are given. For
the image retrieval and clustering task the results are based on the proposed measures andfor the classification task error rates are given. Finally, we conclude this work in Chapter 9
and propose further research.

2

Chapter 2

Basic principles
This chapter introduces the fundamentals for the tasks investigated in this work, gives a
broad overview on the methods used, and presents some notations used in the remainder ofthis document.

2.1

Basic Principles for Image Retrieval

Image retrieval is the task of searching for images from an image database. The query to the
database can be of various types as depicted in Figure 2.1.
Query-by-text: The user gives a textual description of the image he is looking for.
Query-by-sketch: The user provides a sketch of the image she is looking for.
Query-by-example: The user gives an example image similar to the one he is looking for.
In this work we focus on the query-by-example approach. Formally, query-by-example canbe defined as follows:
Let B be the image database with B := {Xn | n = 1 . . . N } where Xn is an image
represented by a set of features: Xn := {Xnm | m = 1 . . . M }. Because a query Q is also an
image, we have Q := {Qm | m = 1 . . . M }. To query the database, a dissimilarity measure
D(Q, Xn ) is calculated for each n as
D(Q, Xn ) :=MX

wm · dm (Qm , Xnm ) for n = 1 . . . N.

m=1

From these D(Q, Xn ), scores S(Q, Xn ) = e−D(Q,Xn ) are calculated and the image Xn withn = argmaxn0 {S(Q, Xn0 )} is returned. Here,PN dm is a distance function or dissimilarity measure
and wm ∈ R is a weight. For each dm , n=1 dm (Qm , Xnm ) = 1 holds.
By adjusting the weights wm it is possible to emphasize properties of different features.
For example to search for an image of a sunset the colors in the image might be very important,
but to search for images of zebras texture is a very important feature.
In image retrieval an interaction with the user is given in most cases and this interaction
allows the user to control the search and maybe help to come to good results faster. One
widely used approach in information retrieval is relevance feedback. That is, after an initial
search the user is presented with the set of results. Naturally, some of the results match3

querydatabase

resulttext query:”dinosaur”

Figure 2.1: Content-based image retrieval.

the query and some do not. Now the user marks good results as relevant and bad results as
irrelevant.
It has been shown that relevance feedback is extremely useful in information retrieval tasks
and some good results have been achieved in image retrieval as well [Müller & Müller+ ]. We
have to distinguish between two different types of relevance feedback: just positive relevance
feedback or positive and negative relevance feedback. Negative relevance feedback can improve
the results strongly, but may lead to bad results if too much negative feedback is given.
+
Formally, feedback can be seen as follows: Let Q+ = {Q+
1 , . . . , QN + } be the set of positive−
query images and Q− = {Q−
1 , . . . , QN − } be the set of negative query images. Then, for eachof the positive and for each of the negative query images we calculate the scores for each of
the database images and calculate
−

+

+

−

S(Q , Q , Xn ) =

N
X

S(Q+
n0 , Xn ) +

n0 =1

N
X


1 − S(Q−n0 , Xn )n0 =1

for each of the database images. Finally, the database images with highest score are returned.
When using relevance feedback it is important not to use too many negative examples
since this might cause problems [Müller & Müller+ ]: Selecting too many negative examples
can inhibit important features from positive examples to be taken into account.

2.2

Basic Principles for Image Clustering

Another task in the context of searching pictures arises from the following situation: Many
image databases index the images by text which can be found in the context of the image4

or has been created manually to annotate the image. In this case image retrieval is reduced
to text retrieval. Probably the best established example for this method is the Google image
search. This image search engine crawls the web, saves thumbnails of the images found, andindexes them using the text from their context, e.g. captions or surrounding texts. Searchingfor an image by text confronts the user with a new problem: many words are ambiguous andsearching for them results in different types of images. Searching with Google image search for
the word “cookie” results in at least three different types of images: images of edible cookies,
screenshots of programs dealing with cookies in the context of the Internet, and images notconcerned with cookies at all. Even when searching for words with less ambiguity nearly
always two groups of images are returned: one meeting the requirements and an unsuitableone. To solve this problem we propose to take the results obtained by the textual retrieval
method and regroup them using methods from computer vision to present a more conveniently
ordered set of results to the user. That is, the images returned are reordered to form groupsof visually similar images. An application reordering its input images in such a manner is
described in Chapter 6.2.
The idea of grouping data into clusters is not a new one, but has been a research topic
for a long time in different contexts. A detailed overview can be found in [Jain & Dubes 88].
To describe this situation more precisely, we give the following formal definition: Let A bea set of observations to be clustered: A = {Xn | n = 1 . . . N }. This data is to be partitioned
00
into a set of clusters U = {uSc | c = 1 . . . C} such that uc = {Xn0 | n = 1 . . . Nc } withC0
uc ∩ uc0 = ∅ for all c 6= c and c=1 uc = A. This partitioning should have the property that
only similar observations are in each cluster uc . Here, similar means that a given distancemeasure d(Xn , Xn0 ) is small for observations Xn and Xn0 from the same cluster but large forobservations from different clusters.
To meet these requirements, many algorithms have been proposed. In this work two
different algorithms are used. The k-means clustering is probably the simplest cluster algorithm based on the squared error criterion. The LBG-Clustering-Algorithm can be seen as
an extension of the k-means algorithm.

2.2.1

k-Means Clustering

The k-means algorithm is a very popular method to partition data. Its objective is to find C
mean vectors µ1 , . . . , µC , one for each cluster for a given C. The basic idea of this iterative
clustering algorithm is to start with an initial randomly chosen partition and assign patterns
to the clusters such that the squared error
0

2

e =

Nc
C X
X

d(Xn(c) , µc )2

c=1 n=1(c)

is reduced, where Xn is the n-th pattern belonging to the c-th cluster, µc is the mean vector
for the c-th cluster, and d is a distance function comparing images.The k-means clustering
algorithm works as follows:
1. Select an initial partition with C clusters.
2. Generate a new partitioning by assigning each pattern Xn to its closest cluster center µc .
0That is, the cluster center µc with c = argminC
c0 =1 d(Xn , µc ) where d is a dissimilarity
measure.
5

3. Compute new cluster centers µ1 , . . . , µC as the centroids of the clusters.
4. Repeat step 2 and 3 until a stopping criterion is reached.
In step 1 the initial partition can be formed by first specifying a set of C seed points. Thisinitial partition could be the first C points X1 , . . . , XC ∈ A or uniformly distributed points
in the pattern space. In step 2 the distances between each of the observations and each of
the cluster centers is calculated and then for each point the nearest cluster center is chosen.
In step 3 the center µc for each cluster is reestimated by determining the mean of the cluster
members. The second and the third step are repeated until a convergence criterion is met.
The k-means algorithm is easily implemented and has a time complexity of O(nC) for
each iteration. A major drawback with this algorithm is that it is sensitive to the selectionof the initial partition and may converge to a local minimum of the criterion function.

2.2.2

LBG-Clustering

The LBG-clustering algorithm has been proposed by [Linde & Buzo+ 80] and can be seen as
an extension of the fuzzy k-means algorithm. Initially, the data is described by one Gaussian.
Then this density is iteratively split until a criterion is reached. This criterion might be e.g.
“the variance is below a certain threshold” or “there are less than a certain number of observations in a cluster”. After each split, the densities are reestimated for several iterations similar
to the k-means algorithm. Instead of the fuzzy memberships we use maximum approximation
for the cluster memberships. This clustering algorithm works as follows:
1. Estimate the initial Gaussian density.
2. Split each density into two parts if it fulfills some split criterion.
3. Generate a new partitioning by assigning each pattern Xn to its closest cluster centerµc . That is, the cluster center µc with c = argminc0 d(Xn , µ0c ) where d is a dissimilarity
measure.
4. Compute new cluster centers µ1 , . . . , µC as the centroids of the clusters.
5. Repeat step 3 and 4 until an optimum value for the error criterion is reached.
6. Repeat from step 2 until some criterion or the maximum number of splits is reached.
In step 1 the mean µ and the variance σ 2 of the data is estimated (cp. Figure 2.2(a)).
In step 2 each density meeting a criterion is split into two densities (cp. Figure 2.2 (b)).
Several split criterions are possible: split all clusters, split only the cluster with the highest
number of members, or split only the cluster with the highest variance. In practice splitting
all clusters has proven to work best for most of the cases. Splitting can be done in various
manners: Disturbing the mean by a constant value µ 7→ {µ0 = µ − , µ00 = µ + }, disturbing
the mean by multiples of theµ 7→ {µ0 = µ − µ, µ00 = µ + µ}, disturbing the 0 mean itself
200mean by the variance µ 7→ µ = µ − σ , µ = µ + σ 2 . These methods have shown not towork for histograms since histograms are normalized and these methods break the normalization.
n Thus, for histograms weo propose to split the means by addition and subtraction:+−
000µ 7→ µ = µ − µ, µ = µ + µ . The sign of the disturbance factor is changed after halfof the entries of µ. That is, µ has D entries, and µd is the d-th entry: µ0d = µd + cµ for6µ(a) step 1, initial
Gaussian

−ε µ
+ε

µ1
µ2

(b) step 2, split
the mean µ by (c) steps 3-5,
reestimation(d) result

Figure 2.2: Linde Buzo Gray clustering.

D0
d = 1, . . . b D
2 c and µd = µd − cµ for b 2 c + 1, . . . , D. The variance σ is just copied in the
split σ 7→ {σ 0 , σ 00 }. In step 3 the distances between each of the observations and each of
the cluster centers is calculated and then for each point the nearest cluster center is chosen(cp. Figure 2.2 (c)). For the calculation of the distances the variances are taken into account.
After this step clusters with less members than a certain threshold are removed. In step 4 thecenter µκ for each cluster is reestimated by determination of the mean of the cluster members(cp. Figure 2.2 (d)). Steps 3 and 4 are repeated until a convergence criterion is met. These
two steps are exactly the same as in the k-means algorithm. When the criterion is met it isdecided whether the clusters are split again. If not, the algorithm terminates.
A main benefit here is that the number of clusters is found automatically and is not
required to be given by the user as in the k-means algorithm. Experience shows that thisalgorithm often yields better partitions than the simple k-means algorithm.

2.3

Basic Principles for Classification

The task of image classification is to assign class labels to images. Classification is needed for
optical character recognition and for face recognition for example. Usually a large amountof training data is available and the classification process is based on this training data. A
classification system assigns a class label k ∈ {1, . . . , K} to an observation. To classify animage X a decision rule r is applied:r : RD 7→ {1, . . . , K},r(X) = k

For this decision rule, the image X is represented by features. One possibility is to use thepixel values of the image directly as features. Other possibilities are explained in Chapter 4.
One possibility to define the decision rule r is to determine the class for every possible
observation and store it, thus converting the classification problem into a search problem.
This approach is usually infeasible since the amount of possible observations is simply toolarge. Consider 16 × 16 images where each pixel can have a gray value from the range 0 to
255. Then, 25616×16 different observations are possible.
A more feasible possibility is to use a set of labeled training observations {X1 , . . . , XN }with labels {k1 , . . . , kN } to define the decision rule by a discriminant function g(X, k):7

r(X) = argmax{g(X, k 0 )}.
k0

In this work the classification is always performed using the nearest neighbor (NN) rule.
That is, an image is classified to be from the same class as the closest image from the training
corpus according to a given distance measure. To realize this classification rule the discriminant function gNN is chosen as:1, if k = argmin min {D(X, Xk0 n )}n=1,...,Nk0k0gNN (X, k) =0, else
For many applications it is recommendable to use other discriminant functions as several
works show [Schölkopf 97, Keysers & Och+ 02, Dahmen & Hektor+ 00, Ney 99] but in thiswork we only consider the nearest neighbor rule as there is a very close connection between
classification using this rule and image retrieval as explained in Chapter 8.1.

8

2.4

Notation

This section is a reference for the symbols used in the context of this work.
Table 2.1: Symbols used in this work.
SymbolBXQd (·, ·)

Description
database of N images B={Xn | n = 1 . . . N }image represented by M features X = {Xm | m = 1 . . . M }N0 × N1 image with gray value X(n0 , n1 ) at position X(n0 , n1 )query image represented by M features Q = {Qm | m = 1 . . . M }dissimilarity function comparing two features

A
U
uc
ε

set of N images to be clustered A = {Xn | n = 1 . . . N }partitioning of A into C clusters U = {uc | c = 1 . . . C}(c)cluster with Nc0 members uc = {Xn | n = 1 . . . Nc0 }disturbance factor for density splits

K
kn
r
g

number of classes
class of image Xndecision rule
discriminant function

H
S
Sm
Hm
Vm
qm

histogram with M binsfeature space of the histogram, partitioned into M regions S mregion belonging to the m-th bin
empirical probability for any point falling into S mvalue belonging to the m-th bin, e.g. center of S mmembership function of the m-th bin

F (X)feature calculated from the image X invariant with respect totransformation g from a group of transformations G
function mapping images to single values
2-D Fourier transform of the image X(n0 , n1 )f (X) : X 7→ R
X (u0 , u1 )9

10Chapter 3

State of the Art inContent-Based Image Retrieval
In content-based image retrieval many disciplines are combined. On the one hand there areimage recognition and pattern analysis which try to describe the images in a way that makes
it possible to distinguish between similar and dissimilar images. On the other hand there is
the database part which tries to store the images and features to allow for efficient access tothe data. This work is only concerned with the first part. The database and indexing part,which is a research area of its own, is not considered here. The remainder of this chapter
presents an overview on the systems and methods available for content-based image retrieval
to give an idea of what has already been achieved in this field. Finally, we give references toclassification systems and works dealing with the clustering of visually similar images. Since
only some of the works presented here give quantitative, comparable results, results are notpresented here. Instead, results from these works are given in Chapter 8 in comparison to theresults obtained in the context of this work.

3.1

Related Work in Content-Based Image Retrieval[Smeulders & Worring+ 00, Rui & Huang+ 99, Fend & Siu+ 03] give overviews on the technical achievements in the field of content-based image retrieval. They review the processing
applied to images for retrieval and discuss features extracted from images for searching. They
also review different distance and similarity measures for different types of features. Finally,
they give summaries about possible system architectures and the database techniques used.
Also these surveys list image retrieval systems available and introduce the methods used.
One of the first content based image retrieval systems available was the QBIC system(Query By Image Content) from IBM [Faloutsos & Barber+ 94]. The QBIC system uses
three types of features: color histograms to describe the color distribution, a moment based
shape feature to describe shapes, and a texture descriptor based on contrast, coarseness, anddirectionality to account for textures. This system also uses database technology to handle
the high dimensionality of the data. The system is available online1 .
A very popular content-based image retrieval system is the BlobWorld system, which
has been developed at the University of California, Berkeley. This system is presented in1

http://wwwqbic.almaden.ibm.com

11

[Carson & Thomas+ 99, Carson & Belongie+ 02]. The system uses image features which are
extracted using segmentation of images. This segmentation is done using an EM-style algorithm clustering the image pixels using color, texture, and position information. To query the
database the user selects a region from an image and the system returns images containing
similar regions. BlobWorld is available online2 .
A system which has strongly influenced this work is the SIMBA(Search IMages By Appearance) system [Siggelkow 02, Siggelkow & Schael+ 01, Siggelkow & Burkhardt 97]. Thissystem uses features invariant against rotation and translation (cp. Chapter 4.3) accounting
mainly for color and texture. By a weighted combination the user can adapt the similarity
measures according to his needs. SIMBA is available online3 .
[Squire & Müller+ 99] present an approach for content-based image retrieval which is oriented towards the methods used in textual information retrieval. They propose a very highdimensional space (dimensionality: 80 000) of binary features and an inverted file to allow
for efficient access. The features they use are a color histogram in HSV space and a set ofGabor coefficients. A weighting of different features is done depending on the number of occurrences in images. This approach is realized in the image retrieval system VIPER (Visual
Information Processing for Enhanced Retrieval)4 and it is freely available5 under GNU Public
License (GPL) as GIFT (GNU Image Finding Tool). Since it is freely available this system isalso used in other institutions and is currently extended to a medical image retrieval system.
The CIRES system [Iqbal & Aggarwal 02] uses a color histogram with 15 bins as color
features, Gabor features as texture representation. Additionally image structures like line
crossings and line junctions are extracted from the images. These structures enhances theretrieval performance because structures of this type usually are found in man-made objects.
They also show that this approach leads to a performance increase for images containing
man-made objects. CIRES is available online6 .
[Wang & Li+ 01] propose another approach to increase image retrieval performance. The
authors claim that preclassification improves retrieval results. They propose to preclassify
images into semantic categories like graph/photograph, textured/non-textured which are relatively simple to classify. After this classification they return images belonging to the same
semantic categories only. Apart from this, region-based features similar to the approach in
BlobWorld are used, but the region descriptions of the images are matched automatically.
This system is available online7 .
Efforts in the area of image retrieval are also made for medical applications. The IRMA
(Image Retrieval in Medical Applications) project [Lehmann & Güld+ 03] is a cooperationof the Department of Diagnostic Radiology, the Department of Medical Informatics, and theLehrstuhl für Informatik VI of the Aachen University of Technology (RWTH Aachen). Aimof the project is the development and implementation of high-level methods for content based
image retrieval with prototypical application to medico-diagnostic tasks on a radiologic image
archive8 .
Other image retrieval systems are available, but it is beyond the scope of this work to2

http://elib.cs.berkeley.edu/photos/blobworld/
http://simba.informatik.uni-freiburg.de4
http://viper.unige.ch5
http://www.gnu.org/software/gift/gift.html
6
http://amazon.ece.utexas.edu/ qasim/research.htm
7
http://wang.ist.psu.edu/
8
http://www.irma-project.org
3

12

present them all. They mainly differ in the features and the search structures they use. In
Chapter 4 we present a selection of features and many of them have been used for image
retrieval before.
A common problem in image retrieval is the performance evaluation. It is difficult tocompare the available systems, because no common performance measure for image retrieval isestablished and even constructing a performance measure is difficult since the success or failureof an image query strongly depends on the requirements of the user. In Chapter 8 we focus
on this problem and introduce and extend an approach proposed by [Müller & Müller+ 01].
In this context a serious problem is the nonexistence of a standard database for comparisonof different image retrieval systems. This problem is not directly addressed here but results
are presented for a wide variety of different databases.

3.2

Related Work in Clustering of Images

In [Iyengar & Lippman 98] the authors propose to use clustering techniques to allow for efficient access to large image databases. More efficient access is important, since due to thesize of large image databases, querying becomes expensive even if the images are represented
in a compact manner. With clustering, the task of retrieval is decomposed into a two stage
process. In the first step an appropriate cluster is selected and in the second step the best
matches from this cluster are returned. They compare a clustering technique which uses
relative entropy to techniques using the Euclidean norm.
[Käster & Wendt+ 03] propose to use image clustering techniques to allow for faster searching in image databases. They compare different clustering techniques to find out which suits
the task of clustering images best.
In [Saux & Boujemaa 02a, Saux & Boujemaa 02b] the authors propose to use image clustering to give a good overview of an image database to help a user find a sought image faster.
To cluster this images, they estimate the distribution of image categories and search the best
representative for each cluster. They represent images by a high-dimensional feature vector
and propose a new clustering algorithm which they compare to other clustering techniques.
[Berkhin 02, Jain & Murty+ 99, Jain & Dubes 88] give general information about clustering of data and the evaluation of results. In [Linde & Buzo+ 80] a new clustering algorithm
based on the EM algorithm is proposed and a method to avoid the problem of finding an initial
partition by iterative splitting of an initial Gaussian describing all data points is introduced.
[Starik & Selding+ 03] describe a method to cluster images into meaningful classes using
a segmentation technique to compare the images. The segmentation is done using centroid
models common to all images in the set and for clustering the information bottleneck algorithm
is used to cluster the images based on the result of the segmentation.
[Barnard & Forsyth 01, Barnard & Duygulu+ 01] present a method to combine the advantages of clustering images based on image features with the advantages of clustering images
based on textual description. Using this combination improves the results strongly as was
empirically tested in this works.
In [Deselaers & Keysers+ 03a] preliminary results of this work are presented. A combination of methods from computer vision and data mining is proposed to improve the userfriendliness of text-based image search engines.
13

3.3

Related Work in Object-Recognition andClassification of Images

In this section some approaches to object recognition in images are presented. At the
moment it is not yet possible to retrieve images from a database with arbitrary scenes
based on the objects contained in the images, but this is an objective for future research[Smeulders & Worring+ 00]. Here an overview of approaches for object recognition with a focus on object recognition in complex scenes like they usually can be found in general images
is given.
A broad overview about the methods used in pattern analysis and classification is given
in [Duda & Hart+ 01]. Since object recognition is a special case of pattern recognition thisbook gives a good introduction into this topic.
In [Fergus & Perona+ 03] the authors present a method to learn and recognize object classmodels from unlabeled and unsegmented scenes. Objects are modeled as flexible constellationsof parts. For all aspects of the objects a probabilistic representation is used.
[Deselaers & Keysers+ 03b] propose to use local representations to recognize multiple objects in one scene. Local representations, as proposed, convey some properties that are highly
important for the task of multi object recognition: They are inherently invariant with respect
to translations and they can cope well with partial occlusions. [Kölsch 03] describes and investigates variations to the methods of local representations which are of interest for thesetasks.
In [Keysers & Motter+ 03] the authors propose a holistic statistical model for automatic
object training and recognition in complex scenes. That is, no local decisions about object
boundaries, segmentation, or object transformations are taken. Instead, all pixels in the given
scene are explained using an appearance based approach. Details about the statistical model
as applied to medical images can be found in [Keysers & Dahmen+ 03].
In [Frey & Jojic 03] a statistical model for automatic training of invariant object models
is introduced. The authors propose the use of transformed mixtures of Gaussians to learn
representatives of transformed objects from unsegmented data.
[Keysers 00] describes approaches to invariant object recognition. Translations considered
are mainly affine transformations. [Gollan 03] considers a broader class of, especially nonlinear, transformations for object recognition. Both approaches obtain state of the art resultsin optical character recognition and radiograph classification.
In [Reinhold & Paulus+ 01] the authors present an appearance-based approach for the
localization and classification of 2-D objects situated in heterogeneous background. Localfeatures are derived from wavelet multiresolution analysis by statistical density functions. In
addition to the object model, the background is modelled by a uniform distribution. That is,
one density function is given to describe all possible backgrounds. It is experimentally shownthat this model is well suited for the addressed recognition task.
[Obdrzalek & Matas 03] describe an approach to invariant object recognition using local
representations normalized with respect to affine transformations. The local representations
are taken from regions where certain shapes are detected and the subimages are normalizedwith respect to certain transformations. Discrete cosine transform is applied to the local
representations to reduce the memory usage.
[Duygulu & Barnard+ 02] use the same features as the image retrieval system BlobWorldand proposes to use methods from machine translation for object recognition. For the transla14

tion, the image features are considered as source language and the image description as target
language.
[Barnard & Forsyth 01, Barnard & Duygulu+ 01, Barnard & Duygulu+ 02] present a statistical method to learn the relationship between image features and textual annotations.
The annotations are used for minimally supervised object training from an annotated image
database and full automatic object recognition.

15

16

Chapter 4

Features forContent-Based Image Retrieval
The basic idea of content-based image retrieval is not to rely on textual descriptions of image
content. Instead, a set of features is used that allows the user to find images that are visuallysimilar to a presented query image. Here “similar” may mean different things. A radiologist,
for example, may have different criteria of similarity than a journalist. Obviously, thesedifferent needs cannot be fulfilled by exactly the same method. To allow for these different
demands different descriptions of the images are needed. Different features may account fordifferent properties of images. Some works divide the used features into different groups, e.g.
color features, texture features, and shape features. Most of the features are indeed membersof two or more of these groups. Therefore, we do not distinguish between these groups offeatures a priori but instead try to show which features have similar properties using anempirical correlation analysis.
In the remainder of this chapter a variety of features describing different properties ofimages is described which allow the user to search for images taking into account thesedifferent properties is given.

4.1

Image Features

The most direct approach to query for images is to compare the images directly. That is, thepixel values of the image itself or the pixel values of a scaled version are compared directly tothe corresponding values of other images. For many applications this approach is not feasible
as it is not clear which pixels from the one image correspond to which pixels in the otherimage. In optical character recognition this method is suitable when the symbols are alreadysegmented since a letter to be recognized will probably be similar to another observation of
the same letter when the letters are of equal size and contained at the same position in theimage. Research about this and improved methods for finding possible pixel alignments arepresented in [Gollan 03].
In addition to taking the pixel values themselves several extensions are possible. Filters
and transformations can be applied to the image to give a more compact representation or toaccount for certain properties of the image, e.g. Sobel filters are applied to emphasize edges
and discrete cosine transformation or PCA transformation are applied to give a more compact
representation.
17

4.2

Color Histograms

A histogram is a way to approximate the distribution of a random variable. It is also a simple
approach to give a description of an estimated density.
The feature space S is partitioned into M regions S m , m = 1, . . . , M . Usually theseregions form a regularly spaced grid, i.e. the regions S m are hypercubes of the same size, but
this is not a requirement. Formally:

S

m

⊂S

M
[

with
and

Sm = S

m=1
m

S

0

∩ Sm = ∅(4.1)∀m 6= m0

(4.2)

The empirical probability for data points falling into one of these regions is determinedby counting. Let K m be the number of data points in region S m from a total of N points,
then the empirical probability Hm for any data point x to be from this region is given bym
Hm = P (x ∈ S m ) = KN .
To create a color histogram the color space has to be divided into regions. For example,
the widely used 24 bit RGB color space contains 224 regions. A histogram containing as
many histogram bins would be too large to be dealt with efficiently. To reduce the amountof memory needed the feature space is quantized. Here, it is required to find a good tradeoff between loss of precision and memory requirement. For gray images, the situation issomewhat better because gray images usually contain 256 different gray levels only. 256 bins
are still a manageable amount of data. After partitioning the feature space, for each region
the number of pixels from this region is counted to calculate the empirical probabilities.
A problem with histograms is the discontinuity [Siggelkow 02]. That is, slightly changing
the image might change the bin assignments and thus the resulting histogram completely.
To overcome this problem fuzzy histograms can be used. The goal of fuzzy histograms is
to remove the discontinuous bin assignment of the traditional histogram. The membershipfunction qm (x) for bin m of a discontinuous histogram is defined asZ+∆
qm (x) =g(x − V m + z)dz−∆

where each bin starts at position V m − ∆ and ends at position V m + ∆ with g(x) = δ(x)where δ(x) is the Kronecker Delta.
That is, only one of the M membership functions is not zero for each point x. The
assignment is discontinuous at the boundaries of the membership functions and due to this
discontinuouity very small variations can cause jumps in the assignments.
[Siggelkow 02] proposes a modified histogram with a continuous bin assignment function.
In Figure 4.1(a) a continuous bin-assignment function with(1
for x < 0
2 (x + ∆)g(x) = ∆ 1− ∆2 (x − ∆) for x >= 0
is shown. In Figure 4.1(b) the standard discontinuous bin assignment function is shown
Nearly the same effect can be achieved by creating the normal discontinuous histogram first
and then smoothing it, for example by convolution with a Gauss filter.
18

qm

qm

1

1
qm

qm+1

qm

qm+1

Sm

S m+1

0

0

x

x
Sm

S m+1

(a) example membership function for fuzzy
histogram(b) membership function for normal histogram

Figure 4.1: Examples of bin-assignment functions.

4.3

Invariant Features

An invariant feature is a feature calculated from an image that is invariant with respect tocertain transformations, i.e. it does not change when these transformations are applied tothe image. The transformations considered here are mainly translation, rotation, and scaling.
In the remainder of this section we consider gray images only, but the methods are easily
extensible to color images.
Formally, an image X is an N0 ×N1 matrix of values X (n0 , n1 ), that can e.g. be interpreted
as gray values. Considering affine transformations that transform a coordinate system intoanother coordinate system such that the point (n0 , n1 ) in the transformed coordinate systemis (n00 , n01 ) in the original coordinate system as    0 
tn0
n0
a11 a12
=
+ 0 ,
t1
n1
n01
a21 a22
an image X can be transformed into another image X 0 with X 0 (n0 , n1 ) = X(n00 , n01 ). Let gbe the transformation with X 0 = gX then we are looking for a feature F (X) invariant withrespect to the transformation g, that is, F (X) = F (gX).
The set of images which can be obtained from one image by any valid transformation
g is called an equivalence class and all images from one equivalence class should yield thesame invariant feature F (X). Details about further requirements for invariant features canbe found in [Siggelkow 02].
To construct invariant features, three approaches are available:
Normalization. The goal of image normalization is to find a distinctive representation forany equivalence class of images. That is, each image X from an equivalence classis mapped to the same representation. For example, normalization with respect totranslation on gray value images can be achieved easily by calculating the center ofgravity of the gray values of the image and translating this center of gravity to theimage center.
19

Differential approach. Invariants may be obtained by solving partial differential equations.
Various types of differential invariants have been used for shape-descriptors e.g. curvature and torsion [Brill & Barrett+ 92]. A small set of differential invariants may containall the essential information about the curve. This approach is theoretically interesting,but segmentation is needed since the contours of the segments are processed. Segmentation is usually not possible in common image retrieval as complete image understandingis needed for a perfect segmentation. Also, in practice the differential equations involved
become complex and hard to solve, though using a priori knowledge can help to reduce
the number of necessary partial derivatives [Squire & Caelli 00].
Integral approach. The construction of invariant features is possible by integration over
the transformation group [Schulz-Mirbach 95]. That is, all possible transformed images
are considered and an integral over all these images is carried out. This approach is
described in more detail in the following sections.

4.4

Invariant Features by Integration

To create features invariant to certain transformations an integral over all transformed images
is calculated [Siggelkow 02]. That is, all possible transformations of the image are considered,
to each of these images a certain function is applied, and the integral over these functions is
calculated. This integral is invariant with respect to the transformations considered.
Let X be a gray value image, X (n0 , n1 ) the gray value at position (n0 , n1 ) and let g ∈ G bea transformation from the group of transformations G. Then gX is the image X transformed
by g such that X(n00 , n01 ) = gX(n0 , n1 ). Let f be a function from an image to a real number:
f : X 7→ R, then F (X) withZ
F (X) =f (gX) dg
g∈G

is invariant with respect to any transformation from G.
For example to create a translation invariant feature for an image X of size N0 × N1 thefollowing can be calculated:
1
F (X) =N0 N1

ZN0 ZN1f (gn0 ,n1 X) dt1 dt0
t0 =1 t1 =1This method is easily extensible to affine transformations. An affine transformation transforms the coordinate system of a point (n0 , n1 ) by
 0    n0
a11 a12
n0
t
=
+ 0
0
n1
a21 a22n1
t1
In the following consider the group of Euclidean motion is considered, that is the groupof rotations and translations Gr,t and the group of rotation, scaling, and translation Gr,s,t .
A transformation rotating the image by ϕ and translating it by (t0 , t1 ) can be expressed
as affine transformation as follows. The point (n0 , n1 ) is transformed to the point (n00 , n01 )with 0    n0
cos ϕ − sin ϕ
n0
t
=
+ 0 .
0
n1
sin ϕ cos ϕ
n1
t1
20

To obtain a feature invariant against these translations integration over t0 , t1 and ϕ is necessary. In practice, the parameters are discretizedN

F (X) =

N

R

0 X
1 X


X
1
f gt0 ,t1 , 2πr X
R
N0 N1 Rt0 =1 t1 =1 r=1

and a function f is selected. Choosing e.g. f (X) = X (1, 0) · X (0, 2) leads to the following
expression which is evaluated:


N1 X
N0 X
R
X
2πr
1
2πr
X cos
F (X) =
+ t0 , sin+ t1
N0 N1 RR
R
t0 =1 t1 =1 r=1


2πr
2πr
·X −2 sin
+ t0 , 2 cos+ t1
RR
The same applies for extension to scaling. Here, the transformation can be expressed as
the coordinate transformation given by    0
n0
cos ϕ − sin ϕ
t
n0
=s
+ 0
0
sin ϕ cos ϕn1
n1t1
where s is the scaling factor. Choosing f as above f (X) = X (1, 0) · X (0, 2) and selecting a
set S = {s1 , . . . , sn } of scale factors this leads to

N0 X
N1 X
R X 
X
1
2πr
2πr
F (X) =
+ t0 , s sin+ t1
X s cos
N0 N1 R|S|R
R
t0 =1 t1 =1 r=1 s∈S


2πr
2πr
·X −2s sin+ t0 , 2s cos+ t1
RR
For the calculation of perfectly scale invariant features it is necessary to consider all
possible scalings of an image. That is, the image has to be scaled from the size where thefunction’s support is larger than the image (here: image size 2 × 2 pixels) up to the size where
the function f (X) is completely contained in one pixel (here: pixel size 2 × 2 pixels). Thisrequirement leads to a large amount of scalings to be considered.
In many applications it is desired to consider features not completely invariant to rotation
but only invariant to rotation to a certain degree. In optical character recognition rotation
invariance is a problem since using completely rotation invariant features makes e.g. “6” and“9” indistinguishable which is not wanted. Using the approach presented here, it is notpossible to create features invariant to a certain degree of rotation because considering somerotations only does not lead to the same features for rotated images. Nevertheless we tried
to obtain partially rotation invariant features by integrating over sectors of a circle instead ofintegrating over complete circles and present the results of these experiments in Chapter 8.
For the calculation of these features it is not necessary to really transform the image using
all the transformations from the transformation groups, but it is possible to calculate thefeatures more directly. This fact can be seen from the equations above and the calculation
strategy as depicted in Figure 4.2. Instead of transforming the image using all transformations,the inverse transformations are applied to the function f and then this function is applied to
21

P

1
· |G|

F (X)

Figure 4.2: Calculation strategy for invariant integration.

the untransformed image. For the case of translation and rotation the sum over the rotation
angle r is calculated for each point of the image and then these sums are summed up (cp.
Figure 4.2).
To speed up this process further, it is possible to approximate the exact invariant featureusing Monte Carlo integration. This method allows to get an invariant feature with a given
precision at a very high probability. Instead of integrating over all positions of the image
the integration is carried out over a fixed number of positions and thus it is possible tocreate an algorithm which can extract an invariant feature in a fixed time. Details about thisapproximation method can be found in [Siggelkow 02, Siggelkow & Schael 99].
Now we come to the issue of choosing an appropriate f (X). f (X) is a function f : X 7→ R.
This function can be of various types. Monomial and relational functions are considered. The
first kind of functions to be considered are monomials:
f (X) =

J
Y

(j)

(j)

X(n0 , n1 )j=1

Using this type of functions it is possible to construct complete feature sets for finite transformation groups [Siggelkow 02].
As a first example consider the trivial monomial f (X) = X(0, 0). Using this function to
obtain the invariant feature F (X) yields simply the mean gray value. For other monomials
we obtain average results of products calculated on certain constellations of pixels under all
possible rotations and translations. For monomials with small support the result is very similar to the mean gray value. Using monomials of different support size allows us to construct
features capturing information of different resolutions from an image. In practice monomialsof the typev
u JuY(j) (j)Jf (X) = t
X(n0 , n1 )j=1

22

rel(x)

1.0
0.5
x
-c

c

Figure 4.3: The rel-function.

are used to not distort the range of the results and to keep the result within the same range
as the original image values. Since the monomial functions are very sensitive to illumination
changes another type of functions for the invariant features was proposed: Relational functions[Schael 01] have been used for texture representation in the same framework of integrational
invariants. Features obtained using relational functions are robust to illumination changes incontrast to features obtained using monomial kernels. The according function f (X) is defined
as
 



(1) (1)(2) (2)f (X) = rel X n0 , n1 − X n0 , n1
with


1

1
rel(x) = 2c(c − x)0

if x ≤ −c
if − c < x ≤ c
if c < x(cp. Figure 4.3)

(1) (1)
The rel-operator maps the relations between the gray values of the pixel X n0 , n1and(2) (2)the pixel X n0 , n1 . In practice, we do not add up the resulting values for the different
rotations but create a 3-bin “fuzzy” histogram of these values. This histogram counts theamount of pixels that are brighter, equal, and darker than the first pixel. The resulting
invariant feature is not completely invariant against changes of brightness but is still robust
to monotonic gray value transformations.
The approach of integration over the transformation group thus yields features invariant
against a given group of transformations and is easily extensible to other transformations.
A problem is that the invariant feature only consists of one value per gray value image
respectively three for an RGB image, and this is not rich enough to discriminate between
different images. To solve this problem, two approaches are available.

4.4.1

Invariant Feature Histograms

The first approach to solve the problem of insufficient data in the invariant feature is basedon the idea of replacing one or more of the integrals by histogramization. In fact, any commutative operator preserves the invariance property and the sum and histogramization are only
practical examples. Thus it is possible to predetermine the dimensionality of the information
23

Table 4.1: Monomials used for invariant feature vectors.
pp3
X(0, 0) pX(0, 0)X(0, 1)
X(0, 0)X(0, 1)X(0, 1)
p3
X(0, 0)X(0, 1)X(0, 2)pX(0, 0)X(0, 2)
p3
X(0, 0)X(0, 4)
X(0, 0)X(0, 1)X(0, 4)
..
..
.p
.p
3
X(0, 0)X(0, 32) p
X(0, 0)X(0, 1)X(0, 32)
3
X(0, 0)X(0, 2)X(0, 1)..
.p3
X(0, 0)X(0, 2)X(0, 32)..
.p3
X(0, 0)X(0, 32)X(0, 32)
gathered and the computational complexity remains unchanged. The histogram HF is givenbyR
N0 ,N11 X 
HF (X) = histf gt0 ,t1 , 2πr X
R
t0 =1,t1 =1 R
r=1Note that using the function f (X) = X (0, 0) results in a simple color histogram as describedin Section 4.2.
In practice, for RGB images we create 3-dimensional histograms with six, seven, or eight
splits in each dimension. This results in histograms of 216, 343, or 512 bins respectively. For
gray images histograms with 64, 128 or 256 bins are created.

4.4.2

Invariant Feature Vectors

Another approach to solve the problem of insufficient data in the invariant feature is tocalculate various different invariant features using different functions f . This approach results
in a vector V = (v1 . . . vN ) of invariant features with vn = Fn (X) and the fn are functions
from a set of functions {f | f : X 7→ R}.
The calculation of invariant feature vectors is computationally expensive. The complexity
is increased by factor N in comparison to the calculation of an invariant feature or invariant
feature histogram.
In practice we use vectors with 44 different monomial functions. The functions used arelisted in Table 4.1. Thus 44 dimensional vectors for gray images and 132 dimensional vectors
for RGB images are obtained.

4.4.3

Invariant Fourier Mellin Features

It is well known that the amplitude spectrum of the Fourier transformation is invariant
against translation. Using this knowledge and log-polar coordinates it is possible to createa feature invariant with respect to rotation, scaling, and translation [Reddy & Chatterji 96,
Dahmen & Hektor+ 00], of which a short overview is given here.
The discrete Fourier transformation X (u0 , u1 ) of a 2D discrete image X (n0 , n1 ) ∈ RN ×N
24

is defined asNN

2πi(u0 n0 +u1 n1 )1 X X
NX (u0 , u1 ) = 2
X (n0 , n1 ) e−N

n0 =1 n1 =1√

with i = −1 and u0 , u1 = 0, 1, . . . , N − 1.
Let f (n0 , n1 ) be a function with the Fourier transform F (u0 , u1 ), then:
“
”


(0)
(0)
−2πi n0 u0 +n1 u1
(0)
(0)
0
0
• f (n0 , n1 ) = f n0 − n0 , n1 − n1
⇒ F (u0 , u1 ) = F (u0 , u1 ) · e• f 0 (n0 , n1 ) = f (βn0 , βn1 ) ⇒ F 0 (u0 , u1 ) = β12 F uβ0 , uβ1• f 0 (n0 , n1 ) = f (n0 cos α + n1 sin α, −n0 sin α + n1 cos α)⇒ F 0 (u0 , u1 ) = F (u0 cos α + u1 sin α, −u0 sin α + u1 cos α).
Using these 3 properties it is possible to derive the following characteristics of the amplitude spectrum A (u0 , u1 ): It is invariant with respect to translation, inverse-variant withrespect to scaling and variant with respect to rotation. Thus, features based on the amplitude
spectrum of an image are translation invariant. By transforming the rectangular coordinates(u0 , u1 ) of A (u0 , u1 ) to polar coordinates (r, θ) and using a logarithmic scale for the radial
axis, image scales and rotations become shifts in the log-polar representation Â of A. Thus theamplitude spectrum of Â is invariant with respect to rotation, scaling and translation. From
the amplitude spectrum of Â we extract 15 × 25 features considering the symmetry which isin fact a low-pass filtering. That is, we take the values around the direct current such thatno symmetrical values are taken. Thus, a 375-dimensional feature vector is taken. For thecoordinate transformation from rectangular to log-polar coordinates a B-spline interpolation
is used.
The whole process is shown in Figure 4.4. Two images are Fourier transformed, thenconverted to log-polar coordinates, and then again Fourier transformed. It can be seen thatthe resulting features are identical as the differnce is 0 in all positions.

4.5

Gabor Features

Gabor filters are a well known technique for texture analysis and have been used in several
works [Park & Jin+ 02, Zhang & Wong+ 00, Iqbal & Aggarwal 99] before. In this work we
use the approach presented in [Palm & Keysers+ 00, Keysers 99] where the HSV color space(hue, saturation, value) is used. Hue and saturation are represented as one complex value inthe images. Here a short overview of the proposed method is given.
For texture analysis, frequency elements, as obtained by Fourier transformations, are an
important part of an image but the simple Fourier transform discards all spatial information.
To retain spatial information, the windowed Fourier transform (WFT) is used and results
in a spatial/frequency representation of the image. For this purpose, the image X(n0 , n1 ) is
multiplied by the window function w(n0 , n1 ) and then the Fourier transform is applied:
Z ∞




(0) (0)(0)(0)
X n0 , n 1 , u 0 , u 1=
X (n0 , n1 ) w n0 − n0 , n1 − n1 e−2πi(u0 n0 +u1 n1 ) dn0 dn1
−∞
“
” 
“
”
  

(0)
(0)
(0)
(0)
−2πi u0 n0 +u1 n1
2πi u0 n0 +u1 n1(0) (0)(0) (0)= e
X n0 , n 1 ∗ w n0 , n 1 e
“
”
(0)
(0)
−2πi u0 n0 +u1 n1

= e

(0)

(0)

[X ∗ mu0 ,u1 ] (n0 , n1 ).
25

Figure 4.4: Creation of RST-invariant features: A rotation example. Note thatthe image rotation becomes a vertical shift in the log-polar plane[Dahmen & Hektor+ 00].

(0)

(0)

Here u0 and u1 are the horizontal and vertical frequencies respectively and (n0 , n1 ) is the
position in the image where the frequencies are determined. The WFT is a convolution of
the image with the filter mu0 ,u1 . For texture analysis, spatial and frequency locations aredesired but with respect to the uncertainty principle of the Fourier transform a good trade off
between these two goals has to be found. The Gabor transformation uses a Gaussian function
as the optimally concentrated function in the spatial as well as in the frequency domain. Here,
non-isotropic Gaussians of the form
− 12

„

n02
0 +n021λ2«

10e2πif n0e 2σ2πσ 2 λ
2 2
0
2 2
02
Mf,ϕ (u0 , u1 ) = e−2π σ [(u0 −f ) λ +u1 ]pwith the center frequency f = u20 + u21 and the rotated coordinates (n00 , n01 ) = (n0 + cos ϕ +n1 sin ϕ, −n0 sin ϕ + n1 cos ϕ) are used. λ1 is the aspect ratio.
Due to the convolution theorem the filter interpretation of the Gabor transform allows theefficient computation of the Gabor coefficients Gf,ϕ (n0 , n1 ) by multiplication of the Fouriertransformed image X (u0 , u1 ) with the Fourier transform of the Gabor filter Mf,ϕ (u0 , u1 ) andapplication of the inverse Fourier transform:
mf,ϕ (n0 , n1 ) =Gf,ϕ (n0 , n1 ) = F F T −1 {X (u0 , u1 ) · Mf,ϕ (u0 , u1 )}Since the correlation of information between the spectral bands is not integrated in the
RGB color space it is proposed to use a special interpretation of the HSV color space.
A complex representation of the H and S color channel is used with b(n0 , n1 ) = S(n0 , n1 ) ·eiH(n0 ,n1 ) and the V layer is used as gray value image. These two image planes are Gabortransformed using a set of 25 Gabor filters accounting for different scales and directions. Thatis, in total 50 Gabor transformations are done, 25 for the V color channel and 25 for the b
26

(a)

(b)

(c)

(d)

(e)

(f)

Figure 4.5: Example images for texture properties: a) high coarseness b) low coarseness c) high contrast d) low contrast e) directed f) not directed. (Images
from [Graczyk 95])

color channel as a combination of the H and the S color channel. It is advantageous to use
the convolution theorem as given above, which allows to calculate the coefficients efficiently.
After this process 50 Gabor coefficients for each pixel have been extracted which is a hugeamount of data. To make this data manageable the 50 dimensional Gabor feature vector is
extracted for a limited set of pixels only. Those pixels with high local variance are selected
since we consider these pixels as important for the content of the image. This selection still
results in a large set of 50 dimensional vectors. Since it is not possible to create a histogramof 50 dimensional data due to the high dimensionality, first a possibility to represent the 50
dimensional Gabor feature vectors more compactly is created.
To obtain this representation, first the set of 50 dimensional Gabor vectors is extracted
from all images from the database, then a partitioning of this set of Gabor feature vectors iscreated with a fixed number of clusters using one of the clustering algorithms introduced in
Chapter 2.2. Finally, for each image a histogram from the cluster memberships of its Gaborfeature vectors is created. The clustering algorithms allow us to obtain a different number ofclusters and thus differently sized histograms.
Other approaches to use Gabor features for image retrieval work very similar to theapproaches for local features. Details about this are presented in Section 4.8.

4.6

Tamura Features

In [Tamura & Mori+ 78] the authors propose six texture features corresponding to humanvisual perception: coarseness, contrast, directionality, line-likeness, regularity, and roughness.
They make experiments to test the significance of the features. They found the first three
features to be very important. That is, these correlate strongly with the human perception.
Examples to illustrate the meaning of these features are given in Figure 4.5. These three
features, coarseness, contrast, and directionality, are defined as follows:
Coarseness The coarseness gives information about the size of the texture elements. The
higher the coarseness value is, the rougher is the texture. If there are two different
textures, one macro texture of high coarseness and one micro texture of low coarseness,the macro texture is considered. The essence of calculating the coarseness value is to use
operators of various sizes. A large operator is chosen when a coarse texture is present
27even if there is a micro-texture and a small operator is chosen when micro texture ispresent only. The coarseness measure is calculated as follows:
1. For every point (n0 , n1 ) calculate the average over neighborhoods. The size of theneighborhoods are powers of two, e.g.: 1 × 1, 2 × 2, 4 × 4, . . . , 32 × 32:
22k 22k
1 XX Ak (n0 , n1 ) = 2k
X n0 − 2k−1 + i, n1 − 2k−1 + j
2
i=1 j=1

2. For every point (n0 , n1 ) calculate differences between the not overlapping neighborhoods on opposite sides of the point in horizontal and vertical direction:
Ekh (n0 , n1 ) = Ak n0 + 2k−1 , n1 − Ak n0 − 2k−1 , n1
and





Ekv (n0 , n1 ) = Ak n0 , n1 + 2k−1 − Ak n0 , n1 − 2k−1

3. At each point (n0 , n1 ) select the size leading to the highest difference value:
S (n0 , n1 ) = argmax max Ekd (n0 , n1 )
k=1...5 d=h,v

4. Finally take the average over 2S as a coarseness measure for the image:N

Fcrs =

N

0
1
X
1 X
2S(n0 ,n1 )N0 N1

n0 =1 n1 =1

Contrast In the narrow sense, contrast stands for picture quality. More detailed, contrast
can be considered to be influenced by the following four factors:• dynamic range of gray-levels• polarization of the distribution of black and white on the gray-level histogram• sharpness of edges• period of repeating patterns.
The contrast of an image is calculated by
Fcon =

σ
α4 z

with

α4 =

µ4
σ4

P 0 PN1
4
where µ4 = N01N1 N
n0 =1
n1 =1 (X(n0 , n1 ) − µ) is the fourth moment about the meanµ, σ 2 is the variance of the gray values of the image, and z has experimentally been
determined to be 14 .
Directionality Not the orientation itself but presence of orientation in the texture is relevant
here. That is, two textures differing only in the orientation are considered to have thesame directionality.
28

To calculate the directionality the horizontal and vertical derivatives ∆H and ∆V are
calculated by convolution of the image X(n0 , n1 ) with the following 3 × 3 operators
respectively−1 0 1−1 −1 −1
−1 0 100
0−1 0 1
1
1
1
and then for every position (n0 , n1 )θ=π∆V (n0 , n1 )+ tan−1
2∆H (n0 , n1 )is calculated. These values are then histogramized in a 16 bin histogram HD and the
directionality can be calculated as the sum of second moments around each peak fromvalley to valley.
To be able to use these features for image retrieval, they are slightly changed. For each ofthese three features a per-pixel value is desired. To achieve per-pixel values, only the steps 1
to 3 are done in the calculation of the coarseness, resulting in a coarseness measure per pixel.
The contrast is calculated in 13 × 13 neighborhoods for each pixel and the directionality
is calculated pixelwise, too: Instead of the derivative filters, a Sobel filter is used and θ is
calculated for each pixel denoting the direction of the area around this pixel. Now, threevalues are available for each pixel. One denoting the coarsenss, one denoting the contrast,
and one denoting the directionality for the neighborhood of the pixels. These values are usedin two different ways. First, we consider these values to be an RGB image and save it as suchand second, a 3 dimensional histogram is created from these values.
A second reason for changing this method is that [Tamura & Mori+ 78] do not makecompletely clear how to calculate the global directionality measure. The QBIC system[Faloutsos & Barber+ 94] uses these features and the authors write that they also altered
the processing steps slightly to obtain histograms describing the texture of the image.

4.7

Global Texture Descriptor[Terhorst 03] describes a texture descriptor to characterize complete images. The descriptor
consists of five parts, where each part models different properties of the texture of the image.
The parts are
Fractal dimension measures the roughness or the crinkliness of a surface. In this work it
is calculated using the reticular cell counting method[Rao 90, Haberäcker 95].
Coarseness characterizes the grain size of an image. Here it is calculated depending on thevariance of the image.
Entropy is a measure of unorderedness or information content in an image. Entropy is awell-known measure from information theory.
Spatial gray-level difference statistics (SGLD) This statistics describes the brightness
relationship of pixels within neighborhoods. It is also known as co-occurrence matrix
analysis [Zucker & Terzopoulos 80, Haralick & Shanmugam+ 73].
29

Figure 4.6: Extraction of local features.

Circular Moran autocorrelation function measures the roughness of the textures. For
the calculation a set of autocorrelation functions is used. [Gu & Duncan+ 89].
In this work we obtain a 43 dimensional vector consisting of one value for the fractal
dimension, one value for the coarseness, one value for the entropy and 32 values for the
SGLD statistics, and 8 values for the circular Moran autocorrelation function. Details about
the computation and the background can be found in [Terhorst 03]

4.8

Local Features

Local features are small square images taken from the original images. It is known, that
local features can yield good results in classification tasks. Details about this can be foundin [Paredes & Perez-Cortes+ 01, Kölsch 03]. Local features have some interesting properties
for image recognition, e.g. they are inherently robust against translation. In the remainder ofthis section we briefly summarize how local features are used for classification and how thismethod is adopted for image retrieval.
Local features are small square images taken from the original image. Local representations might be of size 15 × 15, 17 × 17 or larger. Many local features are extracted from one
image. The number of local features extracted per image varies, but usually is between 100
and 1000. The positions from which the local features are extracted are usually determined by
local variance of the gray values. That is, we assume that positions with high local varianceare of some importance for the content of this image and thus extract a local feature fromthese positions. The feature extraction is depicted in figure 4.6.
The classification process with local features is a two step process: The training phase andthe testing phase. In the training phase, local features are extracted from all of the training
images, resulting in a huge amount of local features. To reduce the amount of data a PCA
30

Training images

Test image

Extraction of local features

Extraction of local features

PCA
Creation of k-NN
dimensionality KD-treeclassification
reduction

PCA
dimensionality
reduction

directvotingFigure 4.7: Classification using local features.

dimensionality reduction is applied where each local feature is reduced to be 40 dimensional.
Then a KD tree is created from these local features to allow faster searching in the testing
phase.
To classify a test image, first the local features are extracted in the same way as in the
training phase, then the same PCA dimensionality reduction is applied. This step results ina set of local features. Each of these local features is then used to query the KD tree from thetraining phase for its nearest neighbors. That is, each of the local features is classified. These
classification results are then used to obtain the global classification result by direct voting.
The whole classification process is depicted in Figure 4.7. Detailed research on variationsof this method is reported in [Kölsch 03].

4.9

Histograms of Local Features

Using histograms of local features is motivated by the fact that for image retrieval good
response times are required and this is hard to achieve using the huge amount of data incorporated in approaches using local feature queries. Here the amount of data is reduced byestimating the distribution of local features for each of the images.
To give an estimation of the distribution we create histograms of the local features. This
is not possible in a straightforward manner, because even after the PCA dimensionality reduction the data still is 40 dimensional and even if each dimension is split into two bins only,a 240 bin histogram would emerge which is not feasible. To circumvent this problem we apply
a two step processing:First a clustering algorithm is applied to a reasonably large set of local features. The
obtained partitioning allows us to represent all local features by a cluster number, thus discretizing the local features by using a code book. To create a local feature histogram for animage, the local features are extracted and for each of the local features the cluster representing it best is determined. Then a histogram of these cluster memberships is created.
This process allows adjusting the amount of data easily. By creating many cluster centersa large histogram is yielded and by creating only a few cluster centers smaller histograms areyielded. The histogram has the same number of bins as the partitioning has clusters. This
process is depicted in Figure 4.8.
31

Images

Extraction of local features Clustering

Clusters

Local Feature Histograms

Figure 4.8: Creation of local feature histograms.

4.10

Region-Based Features

Another approach to represent images is based on the idea to find image regions whichroughly correspond to objects in the images. To achieve this objective, the image is segmented into regions. The task of segmentation has been thoroughly studied [Pal & Pal 93]
but most of the algorithms are limited to special tasks because image segmentation is closely
connected to image understanding. Nevertheless, image segmentation is used in many applications and some image retrieval systems use image segmentation techniques [Wang & Li+ 01,
Carson & Thomas+ 99].
Here we propose an image segmentation algorithm closely related to the methods fromthe BlobWorld system [Carson & Thomas+ 99].
To segment an image we represent it as a set of pixels where each pixel is represented as afeature vector of 8 dimensions. The 8 dimensions are the R, G, and B value of the pixel, thecoarseness, the contrast, and the directionality calculated for the pixel (cp. Section 4.6) andthe x and y position of the pixel. Given this set of pixel vectors LBG-clustering is applied(cp. Section 2.2.2) and a partitioning of the pixels is obtained. From this partitioning a newimage is created, where each pixel value is the number of the cluster to which it has been
assigned. To this image a post processing algorithm is applied to delete noise. That is, amaximum vote filter over k × k windows with k = 5, 10, or 15 is applied to the image.
Given this partitioning, the average color, the average coarseness, the average contrast
and the average directionality for each of the regions is calculated and saved together withthe size of the regions. In Figure 4.9 some example images with different segmentations are
given. The regions are depicted in their average color.
To compare images based on region descriptions, special comparison methods have to
be used because images might contain different numbers of regions. Some approaches tocomparing region based image descriptors are described in Chapter 5.4. A similar approachto segmentation has been proposed in [Carson & Thomas+ 99] and the feature extraction
code is freely available1 .

4.11

PCA Transformed Features

Principal component analysis (PCA) (also known as Karhunen-Loève Transformation) is amethod for dimensionality reduction. Assuming data is high-dimensional it aims at reducing1

http://elib.cs.berkeley.edu/photos/blobworld/

32

Figure 4.9: Example segmentations of images with varying number of regions andvarying k for smoothing

the number of features. Unnecessary features, for example, might be strongly correlated withother features or constant. Feature reduction is a common problem in many branches ofscience like psychology and mathematics.
Principle component analysis is an unsupervised approach to extract the appropriate
features from the data. To achieve this, first the D-dimensional mean vector µ and the
D × D covariance matrix Σ are computed from the full data set. Then the eigenvectors andthe eigenvalues are computed. In this work, the calculation of eigenvectors and eigenvalues
is done using Singular Value Decomposition (SVD). The eigenvalues and eigenvectors are
sorted according to decreasing absolute eigenvalue. Let v1 be the eigenvector with eigenvalue
λ1 , v2 with eigenvalue λ2 , . . . , vD with eigenvalue λD . Then the k eigenvectors with largest
eigenvalues are chosen to form a k × D matrix A. Using this matrix, the data vectors areprojected to a k-dimensional subspacex0 = A(x − µ).
This method can be applied to any type of data and we use it to reduce the dimensionalityof the local features, the raw pixel data, as well as the different types of histograms.

4.12

Correlation of Different Features

Since we described several different types of features, we are faced with the problem of selecting
an appropriate set of features to use for a concrete image retrieval task. Obviously, there aresome similarities between different features. To detect these, we propose to create a distancematrix of a database using all the features available, that is, for each image all distances to all33other images are calculated. For a database of N entries with M features each, an N 2 × M
matrix D is created. From this matrix the covariance Σ is calculated as
Σi,j = E (Di Dj − E(Di Dj ))where Di and Dj denotes the distances between the i-th and j-th features respectively. From
this M × M covariance matrix the correlation matrix R is calculated as
Ri,j = pΣi,j.
Σi,i Σj,j

The entries from this correlation matrix can be interpreted as similarities of different features.
A high value Ri,j means a high similarity in the distances calculated by features i and j,
respectively. This similarity matrix R can be converted easily to a dissimilarity matrix D by
Di,j = 1 − |Ri,j |and then visualized using multi-dimensional scaling.
Multidimensional scaling seeks a representation of data points in a lower dimensional space
while preserving the distances between data points as good as possible. In this case the data
is presented in a 2 dimensional space though it is easily possible to extend this methods tohigher dimensions.
Many different possibilities to obtain such representations exist. These methods differ inthe way they define which distances are being preserved. A basic version of multidimensional
scaling is contained in PCA dimensionality reduction. There, the best possible projection
into a subspace is searched. In this work a MatLab library which is freely available2 is used
for multi-dimensional scaling.

2

http://www.biol.ttu.edu/Strauss/Matlab/matlab.htm

34

Chapter 5

Comparing Features
In Chapter 4 we introduced several different features to represent images in order to beable to decide whether two images are similar or not. In this chapter we introduce different
dissimilarity measures to compare features. That is, a measure of dissimilarity between two
features and thus between the underlying images is calculated.

5.1

Histogram Comparison Measures

Many of the features presented are in fact histograms (color histograms, invariant feature
histograms, texture histograms, local feature histograms, and Gabor feature histograms). As
comparison of distributions is a well known problem, a lot of comparison measures have been
proposed and compared before [Puzicha & Rubner+ 99].

5.1.1

Bin-by-Bin Comparison Measures

Bin-by-bin comparison measures for histograms can usually be computed very fast but due
to the fact that they only compare bin-wise they cannot account for similarities between theunderlying values of the bins. For example in Figure 5.1 the histograms a) and b) have thesame distance as the histograms a) and c), but obviously a) and b) should be more similar ifthey were gray value histograms.
In the following, dissimilarity measures to compare two Histograms H and H 0 are proposed.
Each of these histograms has M bins and Hm is the value of the m-th bin of histogram H.
a)

b)

c)

123456712345671234567m
m
m
Figure 5.1: Three histograms with pairwise identical bin-by-bin distances althougha) and b) should be more similar than e.g. a) and c).

35

Minkowski Distances
Minkowski Distances are a group of distance functions defined by
! p1
M
X


p
0
dp H, H 0 =Hm − Hm.
m=1

The well known and widely used Euclidean distance is d2 and has been proposed for computing
dissimilarity scores between images. These distances are easily computable in O(M ). This
group of distances is not restricted to histograms. Other frequently used distances from thegroup of Minkowski distances are d1 , which is known as Manhattan distance, and d∞ , known
as maximum distance.
Histogram intersection
Histogram intersection [Swain & Ballard 91] is a distance measure specially developed to compare histograms. It is intuitively motivated by calculating the common part of two histograms.
It explicitly neglects features occurring in one histogram only. It is given by
M
 X

0
d∩ H, H 0 =min Hm , Hm
m=1

and can be seen as a generalization of d1 since when comparing histograms with the samebins the following holds:d1 (H, H 0 )d∩ H, H 0 = 1 −2
Relative Deviation
Relative Deviation gives the deviation between two histograms.
qP
M
0 2

m=1 (Hm − Hm )0
drd H, H = q
qP
PM
M
2
2
1
0
m=1 Hm +m=1 Hm2
Relative Bin Deviation
The Relative Bin Deviation is the bin-wise deviation between two histograms.
q
M
0 )2
X
(Hm − Hm0p
drbd H, H =
q
2
0 2
m=1 1
H
+
H
m
m
2
χ2 -DistanceThe χ2 -distance is a formal method to determine whether two distributions differ. To compare
two histograms, we calculate:dχ2 H, H

0



=

M
X
Hm − H 0

m

m=1

36

Hm + Hm.x

Kullback-Leibler Divergence
The Kullback-Leibler divergence, which has its roots in information theory, is defined byM
 X
HmdKL H, H 0 =Hm log 0 .
Hm
m=1

It measures how inefficient it would be to code one histogram using the other. A problem
with the Kullback-Leibler divergence is that it is neither symmetric nor numerically stable.
Jensen Shannon Divergence
The Jensen Shannon divergence, also referred to as Jeffrey divergence, is an empirical extension of the Kullback-Leibler divergence. It is symmetric and numerically more stable. It is
given byM
 X
dJSD H, H 0 =Hm log
m=1

0
2Hm
2Hm
0
+
H
log
.
m
0
0 +H
Hm + Hm
HmmFidelity Based Distance Measures
Another measure of distance between probability distributions is the so called fidelity. The
fidelity is also known as Bhattacharyya distance in image processing:
M p
p
 X
0
dF H, H 0 =
Hm Hm
m=1

In [Nölle 03] the author proposes to use the following distance measures and points out thatseveral of them are metrics:
dF H, H 0
= 1 − dF H, H 0pd√1−F H, H 0 =1 − dF (H, H 0 )dlog(2−F ) H, H 0 = log 2 − dF H, H 0
2
arccos dF H, H 0
darccos F H, H 0 =πqdsin F H, H 0 =1 − d2F (H, H 0 )

5.1.2



Cross-Bin Comparison Measures

Since the distance measures described so far neglect similarities between different bins of thehistograms, even small changes in color or lighting conditions may lead to major changes inhistogram distances. The measures described in the remainder of this chapter are developed
to overcome this problem. Similarities between the underlying values represented by different
bins are taken into consideration.
37

Quadratic Forms
Quadratic Forms are capable of considering the similarities between different bins by incorporating a matrix A = (Am,n ) with Am,n denoting the dissimilarity between the bins mand n.
Let H and H 0 be the histograms represented as vectors, then the Quadratic form can becalculated as qd H, H 0 = (H − H 0 )T · A · (H − H 0 ).
A high dissimilarity between the underlying values of different bins Hm and Hn0 is denoted bya high value Am,n , thus differences between these bins are taken into account stronger than
0 and H 0 where A 0 0 is a low value. A common setting for thedifferences between bins Hmm ,nn0
Am,n isd2 (V m , V n )Am,n = 1 −dmax
where d2 (V m , V n ) is the Euclidean distance between the values represented by bins m and n
respectively and dmax = maxm,n d2 (V m , V n ) [Faloutsos & Barber+ 94].
Earth Movers Distance
The Earth Movers Distance (EMD) [Rubner & Tomasi+ 98] reflects the minimal amount ofwork that has to be performed to transform one distribution into the other by shifting portionsof the distribution between bins. This is a special case of the transportation problem.
That is, computing the EMD requires a transportation problem to be solved. The EMD
dEM D (H, H 0 ) between the histograms H and H 0 is calculated as
Pi,j di,j gi,j0dEMD (H, H ) = P
.
gi,j
i,j

Here di,j denotes the dissimilarity between bin i andP
bin j and gi,j ≥ 0 is the optimal flow
between the two distributions such that the total cost i,j di,j gi,j is minimized. The following
constraints have to be taken into account for all i, j:
Xgi,j ≤ Hj0
i

X

gi,j

≤ Hi

gi,j

= min(Hi , Hj0 )

j

X
i,j

A major advantage of the EMD is that each image may be represented by a histogram withindividual binning.
Time Warp Distance
The time warp distance is deduced from the non-linear time alignment in speech recognition.
In speech recognition time alignment is necessary to account for different speaking rates, tobe able to determine the word and phoneme borders and to account for breaks in spoken
38

a)

b)

c)

123456789
123456789
123456789mmm
Figure 5.2: Time warp distances: T H a , H b = 6, T (H a , H c ) = 16, T H b , H c = 22
in contrast to Euclidean distance, which is 46.9 for all three combinations.

(a) alignment graph between histograma and b from Figure 5.2.

(b) alignment graph between histograma and c from Figure 5.2.

Figure 5.3: Examples of alignment graphs.

language. Time alignment can be done linearly, that is, if the signals are of different lengths,
the shorter one is stretched and then the alignment is done element wise. This method does
not work well, to cope with this problem, a non-linear time alignment function has to be
introduced. Non linear time alignment can be seen as an optimization problem: The optimal
path, minimizing the differences between the two sequences has to be found. The searchof the optimal path is done with dynamic programming. Details about this method can befound in [Ney 99].
We propose to use this method of aligning two different sequences to align histograms.
Brightening or darkening an image shifts its histogram and changing the contrast stretches
or compresses the histogram. Using the optimization method from non-linear time alignment
it is possible to account for these operations. That is, a shifted histogram should not have ahigh distance to the original histogram. An example of different histograms and the distances
between them is given in Figure 5.2. Three histograms are compared. Two of them are very
similar and the third is completely different. The calculated bin-by-bin distance measures are
pairwise identical. The calculated time warp distances reflect the similarities. Two examplealignment graphs are given in Figure 5.3.
The time warp distance is the minimal distance between two histograms of all possible
39

(a) (0, 1, 2) model(b) (−1, 0, 1) model

Figure 5.4: Deformation constraints for time warp distance.

alignments given some deformation constraints. For the time warp distance it is possible toselect certain parameters. A penalty for a distortion can be selected and different distortion
restrictions can be used. In this work we consider two different deformation constraints
known as (0, 1, 2)-standard model and (−1, 0, 1)-model and each deformation is given thesame penalty. The allowed distortions for these two models are depicted in Figure 5.4. For
the time warp distance it is required that neighboring bins are similar and that the bins areordered. That is, the similarity of a bin to other bins lowers with the distance in the histogram
between the bins.

5.2

Comparing Images

Comparing images directly, that is comparing the values of the pixels of the image directly isquite often used in object recognition. Different methods have been proposed to do this anda selection of these methods is presented here and can be used in the image retrieval system
which evolved from this work.

5.2.1

Euclidean Distance

Probably the most common approach to compare images directly is the Euclidean distance orother distances from the group of Minkowski distances. To be able to compare images usinga Minkowski distance, the images have to be of the same size which can be achieved easily
with scaling algorithms. The Euclidean distance has been used successfully e.g. in opticalcharacter recognition and has been extended by different methods.

5.2.2

Tangent Distance

Image objects are usually subject to affine transformations, such as scaling, translation, androtation. The Euclidean distance is not able to account for such transformations if they are
not part of the training corpus. Tangent distance [Keysers & Macherey+ 01] is an approach
to incorporate invariance with respect to certain transformations into a classification system.
Here, invariant means that image transformations that do not change the class of the image
should not have a large impact on the distance between two images.
40Let X ∈ RD be a pattern and t(X, α) denote a transformation of X that depends on aparameter L-tuple α ∈ RL . We assume that t does notchange class membership (for smallα). The manifold of all transformed patterns MX = t(X, α) : α ∈ RL ⊂ RD now offers
new possibilities for distance calculations. The distance between two patterns X and Q canbe defined as the minimum distance between the two manifold MX and MQ , which is truly
invariant with respect to the regarded transformations:dt (X, Q) = min

α,β∈RL||t(X, α) − t(Q, β)||2

Since the distance calculation between these manifolds is a hard non-linear optimization
problem it is necessary to find optimization techniques. In this case optimization is done usingf This subspace is spanned by a set of tangent vectors
a tangent subspace approximation M.
Xl that are the partial derivatives of the transformation t with respect to the parameters
αl . Thus, the transformation t(X, α) can be approximated using a Taylor expansion around
α = 0. The set of points consisting of all linear combinations of the tangent vectors Xl in thegX . This is a first-order approximation of MX .
point X forms the tangent subspace M
The use of linear approximation allows to calculate the distances as a solution of a leastsquare problem or projections into subspaces. Both are computationally inexpensive operations.
In optical character recognition the use of six affine derivatives and one derivative accounting for line thickness yields very good results. In other domains (e.g. radiograph recognition)line thickness is replaced by brightness.

5.2.3

Image Distortion Model

The image distortion model has been investigated earlier at the Lehrstuhl für Informatik IV of
the RWTH Aachen [Keysers & Dahmen+ 03] and further research is presented in [Gollan 03].
The image distortion model is an easily implemented method allowing for small local deformations of an image. Each pixel is aligned to the pixel with the smallest squared distancefrom its neighborhood. These squared distances are summed up for the complete image to
get the global distance. To compare a query image Q with a database image X, d(Q, X) is
calculated as
didm (Q, X) =

N0 X
N1
X
n0 =1 n1 =1

n0 +w

min
0

n1 +w

min
0

n0 =n0 −w n1 =n1 −w

 0
d Q(n0 , n1 ), X(n00 , n01 )Here w is the warp range, that is the radius of the neighborhood in which a pixel may bechosen for alignment and d0 is a pixel distance comparing the image pixels Q(n0 , n1 ) andX(n00 , n01 ). This method can be improved strongly by enhancing the pixel distance d0 tocompare sub images instead of single pixels only:
ω
ω
X
X

2
d0 Q(n0 , n1 ), X(n00 , n01 ) =Q(n0 + x, n1 + y) − X(n00 + x, n01 + y)x=−ω y=−ωFurther improvement is achieved by using derivatives instead of the images directly. Intuitively, the use of derivatives makes the image distortion model align edges to edges andhomogeneous areas to homogeneous areas.
In [Gollan 03] further methods for aligning images are proposed, but these are not considered due to the high computational complexity.
41

5.3

Comparing Images Based on Local Features

The method how local features are used for classification (cp. Section 4.8) is not directlytransferable to image retrieval. In classification, for each class there is one large set of local
features, but in image retrieval there is usually no class information. The aim is to find themost similar images.
To use local features for image retrieval at least three different methods are applicable: 1.
direct transfer, 2. local features on a per image basis, 3. histograms of local features.

5.3.1

Direct Transfer

The method used in classification with local features is transferable to image retrieval. For
this, local features are extracted from each of the database images, the PCA dimensionality
reduction is applied and the KD tree is created. To query the database for an image, we
extract the local features from the query image and apply the same PCA dimensionality
reduction. Then the KD tree is queried for each of these query local features and for each of
the database images we count how many of its local features have been found as a nearest
neighbor to one of the query local feature. Finally the images from the database with thehighest number of votes are returned. This method is equivalent to the method used inclassification if each image is considered to constitute its own class.

5.3.2

Local Feature Image Distortion Model

Another possibility to use local features for image retrieval is based on the idea to take into
account the distances between the local features from the images. That is, we calculate a
distance d (Q, Xn ) between the image Xn and the query image Q represented by their sets oflocal features {xn1 . . . xnM } and {q1 . . . qK } respectively.
To calculate the distance dlf (Q, Xn ) comparing the images Xn and Q we try to explain
each of the local features from the query image Q using the local features from image Xn .
That is, for each of the local features qk from the query image, the nearest neighbor x̂nm is
searched from the set of local features {xn1 . . . xnM }, the distances d(qk , x̂nm ) are calculated,and summed up to get the distance between the original images X and Q:
dlf (Q, Xn ) =KXd(qk , x̂nm )k=1

This method is closely related to the image distortion model (cp. Section 5.2.3) without
any deformation constraints. The IDM considers all possible subimages and here only a subset
is considered.

5.4

Comparing Region-Based Descriptions of Images

To compare images based on the regions occuring in the images the distance measures described up to here are not applicable since different images might contain a different numberof regions and even if the images do have the same number of regions it is not obvious how
to compare them: which region in the one image corresponds to which region in the otherimage is not clear, an appropriate alignment has to be found.
42Different approaches to comparing regions based descriptions of images have been proposed. In the BlobWorld system [Carson & Belongie+ 02] the user has to select a region andthen images containing similar regions are searched. Here, the user gives additional information to the system. Since we want a full-automatic system, this approach is not applicable.

5.4.1

Integrated Region Matching

An approach called integrated region matching (IRM) [Wang & Li+ 01] leads to good results.
The IRM finds a matching from one set of regions to the other and is then able to compute a
dissimilarity score. To find this matching, the IRM allows a region in one image to be matchedwith several regions in another image. Assume that image 1 and image 2 are represented byregion sets R1 = {r1 , . . . , rm } and R2 = {r10 , . . . , rn0 }. First an m × n distance matrix between
these two region sets is computed. To compute the distance between the region sets R1 andR2 , first a matching of all regions from image 1 to the regions of image 2 is created. To
create this matching, significances si and s0i respectively for each of the regions are calculated
as fraction of the size of the region to the complete image. These significances denote theimportance of the region in the image and a significance is assigned to each region alignment
to denote the importance of this alignment with respect to the complete matching. Finally,
the distance d(R1 , R2 ) is calculated asXdirm (R1 , R2 ) =si,j di,ji,jwhere di,j is the distance between the regions ri and rj0 and si,j is the according significance.
The matching is created in a greedy manner. That is, the regions that fit well are matchedfirst: Assume di,j is the smallest distance between any two regions, then the region pair ri
and rj0 is matched next. Then the significances of both regions are decreased by the minimumof these two significances:si ← si − min{si , sj }s0j ← s0j − min{si , s0j }.

The process ends when there is no si , s0j 6= 0 left, that is, the regions of image 1 are completely
matched to the regions of image 2, where each region might be partially matched to different
regions of the other image.
This matching has the following advantages: It is easily computable and if the images
compared are identical, the resulting distance is 0 because only identical regions are matched.

5.4.2

Quantized Hungarian Region Matching

Due to the greedy method, IRM does not always lead to the best result. Finding the best result
is much more complicated, but with some quantization of the significances of the regions, it ispossible to convert this matching problem into an assignment problem, which is computablein O(n3 ), where n is the number of regions, using the Hungarian algorithm.
For the Hungarian algorithm to be applicable, a square distance matrix is required, but
two images may have different numbers of regions. Also the Hungarian algorithm creates
one-by-one alignments. As this constraint is not required and to create a square distancematrix the region descriptions the images are split such that each image is described by a
43

r1
r10
r2
r3

r20

Figure 5.5: Region alignments for the quantized Hungarian region region matching.

total of 50 regions. In this step the region sizes (and thus the significances) are quantized to
be multiple of 0.02. Thus, after the splitting, each image is described by a set of 50 region
descriptions, where each description is of size 0.02.
Given these descriptions of two images, a 50 × 50 distance matrix D is created with di,jis the distance between the regions ri from image 1 and rj0 from image 2. To this matrix
the Hungarian algorithm is applied resulting in the best possible one-by-one matching fromthe 50 regions from image 1 to the 50 regions from image 2. Intuitively, each of the initialregions from image one is partially mapped to one or more regions from image 2. This
matching process is depicted in Figure 5.5. The image on the left hand is described by three
regions. The image on the right hand is described by two regions. Each of these region sets
is subdivided into 50 region descriptors and for the 50 region descriptors from image 1 theperfect matching to the 50 region descriptors from image 2 is found.
Given this matching, the quantized Hungarian region matchin distance is calculated bysumming up the single distances as in the IRM
Xdqhrm (R1 , R2 ) =si,j di,ji,jto obtain the total distance between image one and image two. Here, si,j is set to 0.02.

5.5

Other Features

Up to here, we presented methods to compare histograms, images, region based descriptions,and local feature representations of images. Some features do not belong to any of thesecategories like PCA transformed features, invariant feature vectors and global texture features.
To compare these features, we propose to use the Euclidean distance or the Mahalanobis
distance to account for different domains of vector elements. Let Q be the N -dimensional
vector for the query image and X be the N -dimensional vector for the database image to becompared, then the Mahalanobis distance between X and Q is calculated as the result fromthe quadratic form
 q
0
dM Q, X = (Q − X)T · Σ−1 · (Q − X),
where Σ−1 is the inverted covariance matrix.
44

Chapter 6

Applications
This chapter gives an overview of the applications developed in this work and the techniques
used. Since the aim of this work is to evaluate the quality of different features for image
retrieval, we developed a large variety of feature extraction tools. Details about these tools
can be found in Appendix A.
Here, we present the applications that use the features. Since the main goal was to evaluate
features for image retrieval, the focus was put on the development of an image retrieval systemcapable of using all the features described in Chapter 4. Additionally, an application capableof clustering images according to similarities between certain features was developed.

6.1

Content-Based Image Retrieval

As the aim was to develop a content-based image retrieval system to test different types offeatures and dissimilarity measures, the main goal in the development was to create a highly
flexible system capable of dealing with a large number of different features. To achieve theseobjectives the Flexible Image Retrieval Engine (FIRE) was developed. FIRE is a suite of two
programs. A server and a web client which is to be run on a web-server. The server itself canbe run on any computer.
If a query is performed from the web-interface the client sends the filename of the image
to be queried to the server, the server loads this image and the features extracted for it andthen compares these features to all the images from the database using the selected distancemeasures. Then the server sends the query result to the client, which presents the result to theuser. In addition to the images resulting from the query some query performance measures
are calculated and also presented to the user. Details about these performance measures arepresented in Section 8.1.
After a query has been performed, the user may mark some of the results as “good”
or “bad” and use these to query again. This is also known as relevance feedback and may
improve the query result strongly [Müller & Müller+ ]. Two versions of the query interface
are available: one very simple interface which provides only the basic functions and a moresophisticated interface where nearly all settings of the server can be changed easily.
Apart from this interactive mode, several options to test the query performance of theimage retrieval system have been implemented. For example, it is possible to query a databasewith each of its images in a leaving-one-out manner. That is, the database is queried witheach image and the remaining images are used to calculate performance measures. The results
are averaged over the whole database.
45

A screenshot of the web interface is given in Figure 6.1. At the top the settings for thequery can be adjusted . It is a list of the features available for the database. For each feature
the distance measure and the weight used can be modified. Also the number of results to beshown can be changed. In the Section “Results” the results are shown. The top-left imageis the query image and the other images are its nearest neighbors. For each image some
information is given: The image filename, the textual description, the class (if available), anda score. Also, the results may be marked as “good” or “bad” to allow for relevance feedback
queries. Below the results a PR-graph is shown if available and some other performance
evaluation measures are given as well. At the bottom random images are given to allow for
new queries.

6.2

Grouping of Visually Similar Images

Image databases based on textual annotation are still quite common. A major drawbackof this method is that annotations, the textual descriptions, are often ambiguous. Google
recently offers a way to search for images based on textual information found in the context
of images. For example, the search for “cookie” results in four different types of images:
images of edible cookies or images of people eating cookies, screen-shots of programs dealing
with cookies in the context of the Internet, and images not concerned with cookies at all.
Even for words with less ambiguity nearly always two groups of images are returned: One
group of images meeting the requirements and one group of images not suitable. To improve
this situation we propose to use methods from computer vision to help the user reach hisgoals faster and more comfortably. Improvement can be achieved by using the features used
for image retrieval examined in Chapter 4 in combination with clustering methods explainedin Section 2.2.
An application providing these capabilities was developed, and additionally a small web
interface for demonstration purposes has been created. The application provides access tonearly all features and distance functions introduced in Chapters 4 and 5 and LBG-clusteringor k-means clustering can be chosen. In Figure 6.2 a screenshot of the application is given.
At the top the used clusteralgorithm is selected. Below, the settings for the k-means andthe LBG clustering algorithm can be selected. Also, the dissimilarity measure used and the
database to be clustered can be selected. At the moment the 100 words Google image search
was queried about are available here. Below this, the features to be taken into account canbe selected. When all settings are chosen according to the user’s preferences, the clustering
is started by hitting the “cluster” button. After the clustering process is finished the results
are shown. Under the results the output of the clustering program is given for debugging
purposes.

6.3

Classification

An extra application for classification is not necessary. Due to the strong connection between
classification and image retrieval (cp. Section 8.1) all experiments concerning classification
have been done using the FIRE framework in performance evaluation mode. The performance
evaluation mode calculates the average precision for the first results over the performed queries
P (1) and this is exactly the recognition rate of a nearest neighbor classifier. From thisfollows that the error rate of a nearest neighbor classifier NN-ER can be calculated as NNER= 1 − P (1). This allows for using all the features presented in Chapter 4 for classification.
46

Figure 6.1: Screenshot of FIRE.

47

Figure 6.2: Screenshot of the clustering application.

48

Chapter 7

Databases
In this chapter we present the databases used to test the applications developed. Databases
used for image retrieval as well as databases where clustering was applied and databases defining a classification task are introduced. Results other groups obtained using these databases
are given along with the results we obtained on these databases in Chapter 8.

7.1

Corel

The Corel database is a large database of photographs of different scenes. It is widely usedin the field of content-based image retrieval, but comparison based on this database is very
difficult because the size of the database is enormous and different groups use different subsetsof this database. The size of the database used varies between 30 000 in the BlobWorld systemand 200 000 in the SIMPLIcity system. A subset of approximately 45 000 images was used forthe experiments done during the course of this work. The images are 384 × 256 or 256 × 384
pixels each.
The database is annotated, but the annotation has been done by different persons andthe quality of the annotation varies strongly between different images. Due to this, it is
not possible to use any direct approach for performance evaluation. Some example images
and their annotations are given in Figure 7.1. This figure shows that the annotations isquestionable. In one image there is a mistake in the annotation (“perfomer” instead of“performer”) and in another image there is one word written in two different ways (“grouper”,“growper”). The annotation of the database consists of 184 988 words in total, 13 811 different
words. That is, each image has 6.27 words of annotation in average, the maximum numberof annotating words is 15 and the minimum is 1. That is, we have a corpus nearly 14 000
classes where each image is member of 6 classes in average.

7.2

WANG

The WANG database is a subset of the Corel database of 1000 images which have been
manually selected to be a database of 10 classes of 100 images each. The images are subdivided
into 10 classes such that it is almost sure that a user wants to find the other images from a class
if the query is from one of these 10 classes. This is a major advantage of this database because
due to the given classification it is possible to evaluate retrieval results. One example of eachclass can be seen in Figure 7.2. This database was also used for classification experiments.
49Young Tibetan
Women, Eastern
Tibet
people womenmountainTiger Growper
Hiding In Coral
tiger grouper fishcoralMarket Along
Niger River
Maca-Plaid Skirt 1
people market foodpeople woman
plaid

Addax
addax grass tree

Nevada Falls
waterfall trees rock

The Grand Finale,
Winners One AndAllpeople stage
perfomers

Manhattan From
New Jersey
buildings
downtown
high-rises

Figure 7.1: Example images from the Corel database.

africabeach

monuments

buses

dinosaurs

elephants

flowers

horsesmountainsfood

Figure 7.2: One example image from each of the 10 classes of the WANG database.

This database was used extensively to test the different features because the size of thedatabase and the availability of class information allows for performance evaluation as can beseen in Section 8.1.
This database was created by the group of professor Wang from the Pennsylvania State
University and is available for download1 . Since this database is a subset of the Corel database,the images are of size 384 × 256 or 256 × 384 pixels as well.

7.3

Corel Subset

To have another corpus where performance evaluation is easily possible we created a databasesimilar to the WANG database. 1000 images from 10 classes were selected from the Corel
database. One example image for each class is shown in Figure 7.3.
1

http://wang.ist.psu.edu/

50

gardensubseaplantsbirds

royal guards

irelandmodelsskiingsurfingsunsets

Figure 7.3: Example images from the Corel subset.

7.4

IRMA

IRMA (Image Retrieval in Medical Applications) is a database of currently 3879 medical
radiographs, but it is still growing. In the future the database will consist of at least 10 000
images. The images were collected in a cooperation between the Department of Diagnostic
Radiology, the Department of Medical Informatics, and the Lehrstuhl für Informatik VI of
the Aachen University of Technology (RWTH Aachen) as part of the IRMA project2 . For along time the database consisted of 1617 images only and until now all experiments have been
done using this older database. Here, we give all results for both of these databases to be able
to compare them to older results, as this work is the first to experiment with the new 3879
images database. The 3879 images are divided into a train database of 2832 images and atest database consisting of 1016 images. Some images are left out since they are not classified.
For classification, this database can be used either as a 26 classes task or as an 8 classes task.
The 26 classes are a refinement of the 8 classes. The older 1617 images databases consistedof 6 classes. One example from each of these classes is shown in Figure 7.4. This database isbasis of a very difficult task since images from the same class often are very different as can beseen in Figure 7.5. The images have been labelled by radiologists [Güld & Schubert+ 03] andthus allow for performance evaluation in image retrieval tasks. The classes describe the body
region of the image. The six classes are “abdomen”, “skull”, “chest”, “limbs”, “breast”, and“spine”. The 8 classes are “abdomen”, “skull”, “chest”, “lower limb”, “upper limb”, “pelvis”,“breast”, and “spine”. The 26 classes are a further refinement. Since this database is notfreely available, only results from participants of this project are available.

7.5

CalTech Datasets[Fergus & Perona+ 03] use different datasets for unsupervised object training and recognitionof objects. They classify whether an object is contained in the image or not. For this purpose
they have several sets of images containing certain objects (motorbikes, airplanes, cats, cars,
and leaves) and a set of arbitrary images not containing any of these objects. For performance
evaluation of the image retrieval system some of their data sets were used. Most of the images
2

http://www.irma-project.org

51

Figure 7.4: One image from each of the six IRMA-1617 classes: “abdomen”, “skull”,“chest”, “limbs”, “breast”, and “spine”.

Figure 7.5: Several images from class “chest” from the IRMA-1617 database.

are actually color images but for the experiments the images are converted to gray scale. For
classification, each of this datasets is split into disjunct training and a testing sets. The
database is freely available online3 .
We use the motorbikes, the airplanes, and the faces, as well as the backgrounds. Example
images are provided in Figure 7.6. For our experiments the given partition of the data intotraining and testing set was used. The training set was used as database in the image retrieval
system and the testing set was used to query the system.

7.6

UW Database

The UW database consists of 1109 pictures. The images are photographs and have beencreated by the computer science department of the University of Washingten. The images areof different sizes, from 640×480 up to 883 × 589. There is no class information of the images
but most of the images are annotated. The images which have not been annotated before
were annotated in the course of this work. Additionally, the images are grouped in categories,
e.g. “springflowers”, “barcelona”, and “iran”. In total there are 18 categories. Some example
images with annotation are shown in Figure 7.7. The annotation consists of 6368 words from353 different words. In average, each image has 5.74 words of annotation. The maximum
number is 22, and the minumum is 1. The database is freely available4 .
34

http://www.robots.ox.ac.uk/˜vgg/data/index.html
http://www.cs.washington.edu/research/imagedatabase/52

motorbikes

airplanes

faces

backgrounds

Figure 7.6: Examples of the CalTech datasets.

buildings clouds
mountain people
sand skyovercast sky house
car sidewalk structbushes flowers
peoplebench car houselantern trees
windowmosque tiles people
sky cartrees bushes
overcast skybuilding postbuildings fountaingrass lantern sky

partially cloudy
sky hills trees
grasses groundhousesHusky Stadium
north stands
people football
field track players
on the fieldnoticeable white
stripes scrimmage

Figure 7.7: Examples from the UW database with annotation.

7.7

ZuBuD

The “Zurich Buildings Database for Image Based Recognition”(ZuBuD) is a database which
has been created by the Swiss Federal Institute of Technology in Zürich and is described in
more detail in [Shao & Svoboda+ 03b, Shao & Svoboda+ 03a].
The database consists of two parts. A main part consisting of 1005 images of 201 houses,
5 of each house and a query part of 115 images. Each of the query images contains one of thehouses from the main part of the database. All pictures are of size 640 × 480. The picturesof each house are taken from different viewpoints and some of them are also taken under
53

(a)

(b)

Figure 7.8: a) A query image and the 5 images from the same house in the ZuBuDdatabase b) 6 images of different houses in the ZuBuD-database.

Figure 7.9: Example images from the MPEG-7 test set.

different weather conditions and with two different cameras. To give a more precise idea of
this database some example images are shown in Figure 7.8. The ZuBud database is freely
available on the Internet5 .

7.8

MPEG-7 Test Set

The MPEG-7 Test set is a database of 2343 color images of size 376x256 or 256x376. It is
not very widely used in image retrieval systems since it is not freely available. To our knowledge only the SIMBA system [Siggelkow & Schael+ 01] uses this database. The databaseconsists of photographs from various scenes. A large amount of the images are courtesy of
the Department of Water Resources, California, USA. Some example images are depicted in
Figure 7.9
In [Siggelkow 02] a set of 15 images was selected and for each of these images the relevant
images have been selected manually from the database. For each of the 15 images between 3
and 14 images were selected as relevant. Quantitative results for queries using this knowledge
about relevances are given and are compared to the methods presented here in Chapter 8.

7.9

GoogleTo test the clustering approach we created a new database of Google image search6 results byquerying Google image search with 100 English words and saving the first 120 thumbnails thesearch returned. This yielded a database of 12 000 images from 100 classes. In Figure 7.10
56

http://www.vision.ee.ethz.ch/ZuBuD
http://images.google.com

54aircraftcatcookiesmouse

television

Figure 7.10: The first five results for five image searches on Google in March 2003.

the first five results for five different queries in google are presented. The saved images are ofdifferent sizes, the smallest image is 26 × 14 and the largest image is 150 × 150. The database
was created in March 2003 and thus reflects the results from this date.

7.10

COIL

The Columbia Object Image Library (COIL) database is a well known database for image
object recognition. Two different COIL databases are available: COIL-20 [Nene & Nayar+ b],
which contains gray images from 20 objects, and COIL-100 [Nene & Nayar+ a] which contains
color images from 100 objects. Both databases consist of images taken from different 3Dobjects viewed from varying positions. Each image contains a single object subject to different
illumination conditions. In COIL-100 there are 72 images from each object of size 128×128
pixels. All objects used for the COIL-100 database are depicted in Figure 7.12. The COIL
databases are freely available7 .
To be able to compare our results to results obtained by [Käster & Wendt+ 03], we use
the subset of 20 objects of COIL-100 semantically matching the COIL-20 database. These 20
objects are depicted in Figure 7.12.

7http://www1.cs.columbia.edu/CAVE/research/softlib/

55

Figure 7.11: All objects from the COIL-100 database.

Figure 7.12: The 20 objects from the COIL-100 database corresponding to the objectsof the COIL-20 database.

56

Chapter 8

Results
In this chapter the results for the image retrieval task, for the clustering task, and for classification tasks are presented. The results for image retrieval and classification are described in
one section as these tasks are closely related. To be able to compare different image retrieval
results, first a set of performance measures is introduced. For the tasks where comparable results from other works are available, these results are presented in this section and comparedto the results obtained here.

8.1

Performance Evaluation forContent-Based Image Retrieval

In [Müller & Müller+ 01] the authors investigate the possibilities of performance evaluation incontent-based image retrieval. Since there is no common standard for performance evaluation
for this task they propose a suitable set of performance measures for content-based image
retrieval. Their work is based on the performance evaluation methods used at the Text
REtrieval Conference (TREC). In this work this set of performance measures is adapted andextended by further performance measures. Also the correlation of different performancemeasures is analyzed.
The major problem in performance evaluation of content-based image retrieval systems isthat neither a standard test database nor a standard performance measure is available. Thus,in early reports of content-based image retrieval systems, the results are often restricted to thepresentation of retrieval results of one or more example queries, which is easily used to give apositive impression of the abilities of a system. Obviously, this is neither an objective nor aquantitative measure and it is impossible to compare systems based on example results alone.
Apparently, an objective, quantitative performance measure is needed. The other problem isthat no standard database is available for content-based image retrieval. That is, many image
retrieval systems use different databases to present their results. Due to this it is impossible
to compare the performance of different systems even if quantitative results are given.
In textual information retrieval, several performance measures are well established and it
is reasonable to adapt some of them for content based image retrieval. Probably the mostcommonly used performance measures in information retrieval are the precision P and the57

recall R defined as
P

=

R =

Number of relevant documents retrieved
Total number of documents retrieved
Number of relevant documents retrieved
Total number of relevant documents

These two values are often combined into a so called P R-graph. These figures show how
many relevant and irrelevant documents are contained in the top ranked documents. P Rgraphs are described e.g. in [Schäuble 97] and are created in several steps: In the first step
it is assumed that the user inspects the n first documents of the ranked list. So for everyn = 1 . . . N precision Pn and the recall Rn is calculated. This results in a sawtooth curve
because considering one additional image may raise the precision or lower it. In the next step
this sawtooth curve is converted into a monotonic curve by setting
Pk := max{Pi | i ≥ k}.
This process can be interpreted as looking only at the locally optimal answer sets for which
recall and precision cannot be improved simultaneously by inspecting further documents. In
the last step the P R-graphs of different queries can be combined by calculating the arithmetic
means of precision values corresponding to the same recall value. That is, some recall values
are selected, the precision values corresponding to these values are calculated for each queryand averaged. In the context of this work, the P R-graph is always evaluated for 11 recall
values: R = 0.0, 0.1, 0.2 . . . 0.9, 1.0.
Since P R-graphs do not contain all the desired information and it is not clear how tocompare image retrieval systems looking at graphs, [Müller & Müller+ 01] propose to enhance
the P R-graph with a set of other performance measures that are defined in the following:] P (20) , P (50) , P (NR ), R (P = 0.5) , R (100). We propose to enlarge this set
Rank1 , Rank,
by some further performance measures: P (P = R) , P (1), NN-ER, and P R-area. In thefollowing, the performance measures proposed are explained briefly:
Rank1 . rank at which the first relevant image is retrieved^ normalized average rank of relevant images
Rank.
] = 1
Rank
N NR

NR
X
n=1

NR (NR − 1)
Ri −
2

!

where Ri is the rank of the ith relevant retrieved image and NR is the total numberof relevant images. This measure is 0 for perfect performance and approaches 1 asperformance drops. For random retrieval its expected value is 0.5.
P (20) , P (50) , P (NR ). precision after 20, 50 and NR images retrieved
R (P = 0.5) , R (100). recall at Precision P = 0.5 and Recall after 100 images retrieved
P (P = R). precision where Recall equals Precision
PR-area. the area below the P R-graph58

P (1). precision of the first image retrieved; Averaged over a whole database this is thesame as the recognition rate of a nearest neighbor classifier using the same features anddistance measures. Thus, the error rate of a nearest neighbor classifier can be calculated
as NN-ER= 1 − P (1).
Given this set of performance measures it is possible to compare content-based image
retrieval systems quantitatively given a database where the relevance of the images is knownwith respect to some queries. Usually relevances of images are not known, thus it is notpossible to calculate these measures for queries.
Databases where relevances are known are, for example, the IRMA database and the
WANG database. In both cases, classes are given and we can assume that a user querying
with an image from one class is looking for other images from the same class. For the
WASH database, relevances are not directly clear and assumptions have to be made to extract
relevances from the descriptions of the images. We assume that an image is relevant withrespect to a query image if the descriptions of the images contain identical words. To makethis relevance estimation more robust to inconsistencies in annotations the porter stemmingalgorithm [Porter 80] is used. This algorithm removes word endings leading to the same result
e.g. for “house” and “houses”. This stemming is important since annotation was done by
several persons in most cases. After stemming is performed, the intersection of the sets ofwords is calculated and if there is one stemmed word in both of the descriptions, we assume
that the images are relevant with respect to each other.
To be able to compare the performance of image retrieval system more easily it would
be preferable to have a single performance measure. Since all the measures are supposed tomeasure the quality of the retrieval system in one way or another it is obvious to assume
a strong correlation. However, to our knowledge so far no quantitative analysis for thisassumption was made. Here we present such an analysis using the WANG and the IRMA
databases. A correlation matrix for a selection of performance measures is given in Figure 8.1.
This matrix shows that the performance measures are indeed strongly correlated and thus tocompare image retrieval systems it should be sufficient to use only one performance measure.
A very strong correlation can be seen between the neighboring values from the P R-graph.
Values not so strongly correlated to the other measures are R(P = 0.5) and P (R = 1). Thisis due to the fact that both values do not reflect the quality of the first images retrieved but,
especially P (R = 1), consider the last images retrieved. For a user searching for images it isusually more important to find suitable images fast than to find the last suitable image. If
a more detailed analysis is needed or a specified property of a system needs to be measured
it is advisable to consider more or all of these performance measures. In this work, the error
rate (ER) is selected as performance measure to compare the different settings as it is a wellestablished performance measure in classification tasks and the average absolute correlationfrom P (1) to the other performance measures is 0.83.

8.2

Results for Content-Based Image Retrieval

Since we investigated a lot of features and a lot of distance functions we are interested in thediscrimination performances of these: Which features/dissimilarity measures lead to goodresults and which do not.
First, different distance measures for the different types of features are compared. Afterwards different features are compared using the best distance measures according to the
59

100

ER
P(50)
R(P=0.5)
R(100)
Rank1

P(
50
)
R
(P
=
.5
)
R
(1
00
)
R
an
k1
R]
an
k
P(
R
=
P)
P
R
-a
re
a
P(
R
=
0)
P(
R
=
0.
1)
P(
R
=
0.
5)
P(
R
=
0.
9)
P(
R
=
1)

ER

)
P(
1

P(1)

-100

94

62

94

-91

-90

86

90

98

95

83

73

31

100

-94

-62

-94

91

90

-86

-90

-98

-95

-83

-73

-31

100

57

91

-88

-87

77

81

93

93

73

62

14

100

48

-58

-54

55

58

61

48

55

52

21

100

-96

-97

94

96

97

95

92

84

50

100

99

-94

-95

-96

-86

-92

-85

-54

100

-97

-97

-96

-88

-95

-89

-59

100

99

92

85

99

95

72

100

95

88

98

94

67

100

94

89

81

42

100

82

72

31

100

96

76

100

81

]
Rank
P(R=P)
P R-area
P(R=0)
P(R=0.1)
P(R=0.5)
P(R=0.9)P(R=1)

100

Figure 8.1: Correlation of performance measures scaled to [−100, 100].

experiments before. The experiments are done on the WANG and the IRMA-1617 corpus
since the size and the given classification allow for extensive performance evaluation. The
insights obtained on these databases are later transferred to other image retrieval tasks.

8.2.1

Comparison of Different Distance Functions

In this section different dissimilarity measures for the different types of features are compared experimentally and the performance for the different types of features is quantitatively
measured. The experiments were done using the WANG and the IRMA-1617 corpus. First
comparison measures for histograms, then the different distance measures for images, the different methods to compare images based on local features, and finally the different comparison
measures for region based descriptions of images are analyzed and compared.
Different Comparison Measures for Histograms
Exemplary results (error rates) obtained using different comparison measures for histograms
are shown in Table 8.1 for the WANG database and for the IRMA-1617
database. For thep
WANG database an invariant feature histogram with f (X) = X(4, 0) · X(0, 8) was used
and for the IRMA database a local feature histogram with 512 bins of 5 × 5 local features wasused. Complete tables can be found in Appendix B in Tables B.4 and B.5. Corresponding
P R graphs are shown in Figure 8.2. The results show that L1 distance, χ2 distance andJensen Shannon divergence yield very similar results and clearly outperform the widely used
Euclidean distance.
Since the time warp distance was not investigated before, the results obtained using thetime warp distance with different parameters are presented here in more detail. The time
warp distance has three parameters: different models for the deformation constraints are60

Table 8.1: Error rates [%] on WANG and IRMA-1617 using different comparison
measures.pFor the WANG database an invariant feature histogram withf (X) = X(4, 0) · X(0, 8) and for the IRMA-1617 database a local feature histogram was used.
WANG
Distance measure
JSD
χ2
L1
Euclidean

IRMA-1617
Distance measure ER[%]
L1
8.3
χ2
9.1
JSD
9.3
Euclidean
14.2

ER[%]
15.9
16.5
18.4
28.3

Table 8.2: Error rates [%] using time warp distance on thepIRMA-1617 database withan invariant feature histogram with f (X) = X(4, 0) · X(0, 8). The lastcolumn gives the corresponding error rate without warping.
Distance
L1
L2

ER[%]
34.7
41.1

base ER[%]
35.6
42.4

available, the underlying local distance can be varied, and the deformation penalty can bevaried.
In Figure 8.3 the results for different parameter settingspfor the time warp distance areshown comparing invariant feature histograms with f (X) = X(4, 0) · X(0, 8). This type ofhistogram does not lead to good results for the IRMA database but the time warp distanceis not applicable to every type of histogram as it requires an ordering of the bins (cp. Section
5.1.2), e.g. the time warp distance is not applicable to local feature histograms. Figure 8.3(a)gives error rates for different penalties and different deformation constraints using an L1 typedistance and Figure 8.3(b) gives error rates using different penalties and different deformation
constraints using an L2 type distance. The results improve using the time warp distance. In
both cases the choice of the deformation model is not very important but the penalty isa sensitive parameter. In both cases the deformation penalty has to be within a certain
range to obtain good results. If the penalty is chosen too low (e.g. “penalty=0”), the results
are quite bad, due to the fact that unsimilar histograms can be aligned too good. The
fact that L1 distance outperforms Euclidean distance was observed earlier in this work forhistograms. Both graphs show that the time warp distance improves the results compared tothe underlying base distance. The best error rates in comparison to the error rates obtainedwith the base distances are given in Table 8.2.
Different comparison measures for images
For comparing images directly, the Euclidean distance, the image distortion model, and thetangent distance were proposed. Table 8.3 shows results for these three comparison measures
for the WANG and IRMA-1617 databases.
The results show that in both cases the image distortion model yields the best and thesimple Euclidean distance the worst results. However, it can be seen clearly that taking the
61

1
L1
χ2
JSD
EuclideanPrecision

0.8
0.6
0.4
0.2
0
0

0.2

0.4

0.6

0.8

1

Recall(a) P R graphs for IRMA-1617 using different distance measures.

1
L1
χ2
JSD
EuclideanPrecision

0.8
0.6
0.4
0.2
0
0

0.2

0.4

0.6

0.8

1

Recall(b) P R graphs for WANG using different distance measures.

Figure 8.2: P R graphs for WANG and IRMA-1617 using different distance functions.

images into consideration for retrieval is advisable for the IRMA task but not advisable for
the WANG task. This leads us to the conclusion that taking into account the images asfeatures directly is suitable in more specialized tasks, like the IRMA task, whereas it is notsuitable in less restricted tasks as the WANG task. We assume that this is due to the fact
62

43
L1
time warp L1 (-1,0,1)
time warp L1 (-1,0,1),penalty=0
time warp L1 (0,1,2)
time warp L1 (0,1,2), penalty=04241
error rate

40
39
38
37
36
35
34
1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

penalty(a) Error rate vs. penalty for L1 base distance.

46
L2
time warp L2 (-1,0,1)
time warp L2 (-1,0,1), penalty=0
time warp L2 (0,1,2)
time warp L2 (0,1,2), penalty=0

error rate

45
44
43
42
41
1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

penalty(b) Error rate vs. penalty for L2 base distance.

Figure 8.3: Different parameters for the time warp distance on p
the IRMA-1617 corpus
with an invariant feature histogram with f (X) = X(4, 0) · X(0, 8).

that the IRMA images usually contain one object (e.g. arm, leg, skull) from a limited set ofobjects (body regions) whereas most images from the WANG corpus contain several objects
with varying positions and the variation in the appearance of different objects from the same63

Table 8.3: Error rates [%] for the IRMA-1617 database using different image comparison measures.
MethodEuclidean
IDM with thresholding
Tangent distanceTangent distance with thresholding

IRMA
17.7
6.7
[Keysers & Dahmen+ 03] 13.1
[Keysers & Dahmen+ 03] 11.1

WANG
55.1
[Gollan 03] 22.1
53.7-

Table 8.4: Error rates [%] using region based features and different comparison measures for the WANG database.
comparison measure
IRM
RM

ER[%]
55.30
49.80

type is very high. (e.g. old fashioned bus vs. modern red bus, children playing on the beachvs. beach without any person).
Different comparison measures for region based descriptions of images
In Section 5.4 we proposed two methods for comparing region based descriptions of images.
Table 8.4 gives the results for these two methods using region based descriptions for the
WANG database. The region matching method using the Hungarian algorithm and thus
obtaining the perfect matching between the region descriptions is clearly better than thegreedy integrated region matching. Nonetheless, these error rates are not satisfactory andprobably are so bad due to the fact that segmentation still is an unsolved problem.
Different comparison measures for local features
In Section 5.3 we proposed three different methods for comparing images based on local
features. Here we compare results for these methods and additionally compare the results to
those obtained using the image distortion model with differently sized pixel windows.
Table 8.5 shows error rates for the IRMA database for different settings for local features
as well as for the image distortion model. We consider this comparison interesting since inboth cases subimages are compared. The image distortion model usually compares relatively
small subimages and takes deformation constraints into account. The local feature based
approaches usually compare relatively large subimages and no deformation constraints are
considered. In the usual local feature based approaches even alignments across images of thesame class are allowed. We present the results for histogram representation of local features(cp. Section 4.9). The results show that using stronger constraints the results get better withsmaller subimages: the weakest constraints are in the method labeled “lf-l1o”. “lf-l1o” is thecommon local feature approach without any constraints. For each local feature the nearest
neighbor from the large set of database local features is searched and it is counted how many
local features from which class are found. In the decision process it is not important fromwhich image the local feature originates. The method labeled “glfd” incorporates slightly
stronger constraints, which is the direct transfer from local features to image retrieval. Here,64

Table 8.5: Comparison of error rates [%] on IRMA using local features and image
distortion model.
local features

Methodlf-l1o
glfd
lfd

19×19
13.0
26.0
26.8

5×5
28.8
22.9
23.1

3×3
31.7
32.8
28.4

image distortion model

IDM (sobel)
IDM

13.3
11.5

8.7
11.4

6.7
12.7

local feature histogramswith 64 bins
with 128 bins
with 256 bins
with 512 bins
with 1024 bins

30.2
28.0
24.6
-

11.6
10.1
9.5
9.3
10.1

14.3
12.6
29.9
17.7
23.2

for each local feature its nearest neighbor is searched from the huge set of database local
features and it is counted for each of the database images how many of its local features
are found. In the end the image is classified to be from the same class as the image withthe highest count. This method is equivalent to the common local feature approach if each
image is considered to constitute its own class, since alignments within other images from thesame class are not allowed anymore. Even stronger constraints are taken into account for the
method labeled “lfd”. Here, each local feature is forced to map to a local feature from theother image. That is, the comparison is image-wise. Comparing two images, for each local
feature from the query image its nearest neighbor from the set of local features from thisparticular database image is searched. The strongest constraints are considered for the image
distortion model (label “IDM”). Here the subimages from the query image are matched tosubimages from a database image from a certain range of positions. That is, the subimages are
not allowed to be matched to subimages too far away from the initial position in the images.
The results show that dropping constraints about global relationships of images requires more
information. That is, for the image distortion model each alignment is somehow related to
the neighboring alignments and thus it is not necessary to regard large subimages whereas
the local feature approach with an high amount of local information in each subimage works
quite well without the global constraints. Intuitively, the local features need a high amountof local information to recover the lack of global information, or the missing knowledge about
position in the local feature approach is recovered from a high amount of information of theneighborhoods.

8.2.2

Comparison of Different Features

In the last section we examined different comparison measures for the different types offeatures, in this section different features are compared using suitable comparison measures.
Results for the WANG and the IRMA-1617 database are presented. The results are given as
error rates and P R-graphs. The experiments were done in a leaving-one-out manner. Thatis, each image from the database was selected as query image and the nearest neighbor form
65

Table 8.6: Error rates [%] using different features for the WANG database.
Featurep
inv. feat. histogram f (X) = X(4, 0) · X(0, 8)
color histogram
Tamura histogram
local feature histogram 256
image of size 32×32

Distance measure
JSD
JSD
JSD
JSD
Euclidean

ER[%]
15.9
17.9
31.0
32.5
55.1

Table 8.7: Error rates [%] using different features for the IRMA-1617 database.
Featureimage of size 32×X
local feature (5×5) histogram 512
32×32
Tamura histogram
inv. feat. histogram f (X) = rel(X(0,0) − X(0, 4))pinv. feat. histogram f (X) = X(0, 0) · X(0, 2)
Fourier Mellin feature

Distance Measure
IDM Sobel
JSD
Euclidean
JSD
JSD
JSD
Euclidean

ER[%]
6.7
9.3
17.7
19.3
22.6
29.2
53.1

the remaining images was searched.
Exemplary results (error rates) we obtained using different features and suitable comparison measures are shown in Table 8.6 for the WANG database and Table 8.7 for the IRMA-1617
database. Complete tables can be found in Appendix B in Tables B.1 and B.2 for reference.
The results show that different tasks require completely different features. For the IRMA
database the best results are obtained using the image pixels as features as opposed to the
WANG database where these features yield poor results. Vice versa, the invariant feature
histograms yield very good results on WANG but perform poorly on IRMA. Figure 8.4 shows
the corresponding P R graphs.
Since it is often desired to create features invariant with respect to a certain amount oftransformation only, we implemented an “invariant” feature histogram considering only a sector of the circle for integration. It has to be noted that according to the theory this approach
does not lead to partially rotation invariant features (cp Section 4.4, p. 4.4). Results using different sectors are given in Table 8.8 and approve the theory that it is not feasible
to use thesepfeatures. For these experiments invariant feature histograms with f (X) = X(4, 0) · X(0, 8)
were used and the tests were performed on the WANG database.
As it is well known that combinations of different methods lead to good results [Kittler 98],
an objective is to combine the presented features. However, it is not obvious how to combine
which features. To analyze the characteristics of features and which features have similar
properties, we perform a correlation analysis as described in Section 4.12. The resulting
graphs from multidimensional scaling are shown in Figure 8.5 and Figure 8.6 for WANG
and IRMA-1617 respectively. The points in these graphs denote the different features. The
distances between the points denote the correlations of the features. That is, points very close
together denote features that are highly correlated and points farther away denote featureswith different characteristics.
66

1

p
X(4, 0) · X(0, 8)
Color Histogram
Tamura Histogram
LF Histogram 256
32x32

InvFeatHisto f (X) =Precision

0.8
0.6
0.4
0.2
0
0

0.2

0.4

0.6

0.8

1

Recall(a) P R graphs for WANG database using different features.

1

p
InvFeatHisto f (X) = X(0, 0) · X(0, 2)
InvFeatHisto f (X) = rel(X(0, 0) − X(0, 4))
LF(5x5) histogram 512
Fourier Mellin Feature
Tamura histogram
32x32 IDM Sobel
32x32 Euclidean

Precision

0.8
0.6
0.4
0.2
0
0

0.2

0.4

0.6

0.8

1

Recall(b) P R graphs for IRMA-1617 database using different features.

Figure 8.4: P R graphs for WANG and IRMA-1617 corresponding to error rates inTables 8.6 and 8.7.

The graphs show that there is a clear clustering of features. Both graphs have a large
cluster of invariant feature histograms with monomial kernel function. They result frominvariant feature histograms using different monomial kernel functions and histogram settings.
67

Table 8.8: Error rates [%] using invariant feature
p histograms with partial rotation for
the WANG database with f (X) = X(4, 0) · X(0, 8).
angle
360◦
270◦
180◦
90◦

ER[%]
15.9
16.1
16.2
16.6

image features
inv. feat. histograms
inv. feat. vectors
texture features
Gabor histograms
LF histograms
color histograms
inv. feat. histograms (X-X)
region features

Figure 8.5: Results from Multi-dimensional scaling for WANG features.

Also, the graphs show clusters of local features, local feature histograms, and Gabor feature
histograms. The different texture features do not form a cluster. This suggests that theydescribe different textural properties of the images and that it makes sense to use them incombination.

8.2.3

Image Retrieval Using Different Databases

In this section we present results obtained using weighted combinations of features for different
databases. To obtain comparative results we optimize the settings on a given training database
and test the settings using a given testing database.
68

image features
inv. feat. histograms
inv. feat. vectors
texture features
Gabor histograms
LF histograms
LF
Fourier Mellin
aspect ratio

Figure 8.6: Results from Multi-dimensional scaling for IRMA features.

IRMA database
The IRMA-3879 corpus is a good example to show how parameters are optimized and tested:
We optimize the settings on the training database using a leaving one out evaluation and use
these settings to classify the test database. Table 8.9 presents results for different training andtest situation. The first column gives a description of the used training method. Here “IDM
Sobel” means that no training was done at all, but the only used features are images scaled
to the height 32 and compared using the image distortion model with Sobel values. Also, for“wi = 1.0” no training was done, but all extracted features are used with equal weights. In
the remaining lines the settings were optimized on the training data using a greedy algorithm:“wi ∈ {0, 1}” means that the features were weighted with either 0 or 1, this is also known
as feature selection. “wi ∈ {1, . . . , 10}” offers more flexibility the weights can be any integer
between 0 and 10. The second column gives error rates for the training data. The parameters
were optimized with respect to this error rate. It is interesting that the image distortion
model alone is better than a combination of all features. It can be seen that the performanceincreases as the degree of freedom increases. The third column gives error rates for the testing
data. The fact that better error rates on the training data implicate better error rates on thetesting data shows that the parameters are not overfitted to the training data. Where ranges
are given several parameter settings obtained identical best results on the training data andthe ranges denote the varying error rates on the testing data for these different settings. The
table also shows that feature selection only is not sufficient to increase the recognition rate
but more flexibility is needed here. In both cases where more flexibility was given, the results
are improved in comparison to the base line result using the image distortion model alone.
69

Table 8.9: Results for different training and testing situations on the IRMA-3879
database. (Ranges in the last column denote different parameter settings
with optimal result on training data.)
Training
IDM Sobel
wi = 1.0
wi ∈ {0, 1}
wi ∈ {0, . . . , 10}

L1O ER[%] on
training data
7.5
9.2
7.5
6.6

ER[%]
test data
7.2
9.1
7.3-9.1
6.3-7.0

Note that this base line result in fact is very good as exactly this method obtains nearly thebest results for the smaller IRMA-1617 corpus.
For these experiments the following features were available: 32×32 thumbnails comparedwith Euclidean distance, 32×X thumbnails compared with image distortion model distance,
two different Tamura texture histograms compared with Jensen Shannon divergence, Tamura
texture images compared with Euclidean distance, three different invariant feature histogramswith monomial kernels compared with Jensen Shannon divergence, one invariant feature histogram with relational kernel compared with Jensen Shannon divergence, invariant feature vectors compared with Euclidean distance, global texture descriptors compared with Euclidean
distance, and image sizes compared with Euclidean distance. In Table B.3 the error rates forall of these features are given for the 8 classes and for the 26 classes task.
To be able to compare these results to the results obtained earlier on the smaller IRMA1617 database, Table 8.10 gives error-rates for this database together with results publishedin other works results obtained in this work are given in the lines labeled with “Feature
selection”. For these experiments a set of 36 different features for each image was used. The
features used were selected in a greedy manner. That is, first each feature was tested apart,
then the best of these features was taken, and all other features were tested together withthis feature, and so forth.
Using this method to optimize the parameters for the leaving-one-out classification, leads
to an error rate of 4.8% on the IRMA-1617 corpus which is the best obtained error rate so far.
To check whether these parameter set is overfitted to the data, we also applied this method
in an eight-fold cross validation experiment. That is, we trained the used feature set on seveneighth of the data and classified the remaining eighth using these parameters. The error
rate of 6.1% shows that the parameters were overfitted to the data. Nonetheless, the resultof 6.1% is an improvement in comparison to the error rate obtained with image distortion
model alone. Bootstrap method [Efron & Tibshirani 93] showed that this is an improvementon the 11% level.
For these experiments the following features were available: four different Gabor histograms, twelve different local feature histograms, ten different invariant feature histogramswith monomial kernel, one invariant feature vector, one invariant feature histogram with relational kernel, two different thumbnails of the image, Gabor features, two different types of
local features, two different Tamura texture feature histogram, a Tamura texture image, a
global texture descriptor, the image size, and a Fourier Mellin feature.
Further analysis of the results for the IRMA-1617 corpus has been done. Figure 8.7
shows the P R-graphs for the 6 IRMA-1617 classes apart. The graphs show that the retrieval
70

Table 8.10: Error rates [%] obtained on the IRMA-1617 database.
MethodPseudo 2D hidden Markov model
Image distortion model
Local features & tangent distance
Extended tangent distanceER[%][Gollan 03][Gollan 03][Kölsch 03][Keysers 00]

Feature selection (cross validation)

5.3
6.7
7.4
8.0
6.1

1
abdomenlimbs
breast
skull
chest
spine

Precision

0.8
0.6
0.4
0.2
0
0

0.2

0.4

0.6

0.8

1

RecallFigure 8.7: Class wise P R-graphs for the six IRMA classes.

performance for an image is class dependent. Different factor have an impact on this. First,
different types of images may be differently hard to distinguish, e.g. the difference between
a skull and a hand image image is quite clear whereas the difference between spine and an
abdomen images is not so obvious. Another very important factor is the size of the classes.
Given a query image from a larger class, the probability to find images from the same class ishigher than for a smaller class. In this database the class “chest” contains 43% of the images,
and the class “abdomen” contains only 7% of the images.
WANG database and UW database
Similar experiments to those performed on the IRMA databases were carried out using the
WANG database and the UW database (cp. Sections 7.2 and 7.6). That is, we optimized theparameters for the one database and tested this setting on the second database. Results forthese experiments are given in Table 8.11.
The lines in this table denote the parameter trainings performed. The first line “wi = 1.0”
means that all features available were used with equal weights. The second line means thatthe features used were selected from the MDS graph in Figure 8.5 such that the features are71

Table 8.11: Results for different training situations for the WANG and UW
databases.
Training on
wi = 1.0
MDS graph

ER[%]
WANG
12.7
16.0

ER[%]
UW
12.2
13.9

WANG
WANG (sel)(9.9)(10.9)

13.5
13.8

UW database
UW database (sel)

15.1
16.2

(9.4)
(10.2)as different as possible. In this case we selected 32×32 thumbnails, local feature histograms,
invariant feature histogram with monomial and relational kernel, global texture descriptors,
region features, and Tamura texture histograms. The lines “WANG” and “UW database”
give the error rates for experiments where the parameters were optimized on the databases
and the lines “WANG (sel)” and “UW database (sel)” give error rates for experiments where
the parameters were optimized on the databases but the weights were restricted to 0 and 1.
The results show that in both cases (transfer from WANG to UW database and vice versa)
the parameters are overfitted to the training data for all training cases. When optimizing thesetting on the WANG database, either with selection or unrestricted, the error rate improves
strongly compared to the error rate when just using all features with equal weights, but theerror rate on the UW database deteriorates strongly. The same applies to the case when
optimizing the parameters on the UW database and testing on the WANG database. Thisshows that this training overfits the parameters to the training data. This overfitting is soclearly due to the fact that these two databases are not very similar and thus need different
settings.
For these experiments the following features were available for both databases: five invariant feature histograms with monomial kernel with different settings, one invariant feature
histogram with relational kernel, an invariant feature vector, a 32 × 32 thumbnail, local features of size 19 × 19 from the 32 × 32 thumbnails, local feature histograms with 128 and 256
bins, the global texture descriptor, a Tamura texture histogram and a region description of
the images.
WANG database and COREL subset
Since the databases WANG and UW database differ quite strong in their characteristics wealso tried to transfer trained parameters from WANG to the COREL subset (cp. Section 7.3).
Results for these experiments are given in Table 8.12. The line “wi = 1.0” gives results where
all available features were used with equal weights. The lines “WANG” and “Corel subset”
give results for parameters optimized on these databases respectively. From these results it
can be seen that it is possible to transfer the features and weightings for image retrieval fromone database to another if the databases are adequately similar because for both trainingcases the results not only improve on the training database but also on the testing database72

Table 8.12: Error rates [%] for different training situations for the WANG and Corelsubset databases.
Training on
wi = 1.0

ER[%]
WANG
13.3

ER[%]
Corel subset
21.7

WANG
Corel subset(12.0)
13.2

21.6(20.5)

Table 8.13: Error rates [%] for different training situations for the WANG subsets.
Training on
wi = 1.0

WANG even
14.4

WANG odd
17.4

query odd on even
16.4

WANG even
WANG odd(10.6)
13.2

16.4(13.2)

14.8

query even on odd
13.6

12.8

in comparison to the case where all features were used with equal weights.
For these experiments the following features were available: two different invariant feature
histograms with monomial kernel, an invariant feature histogram with relational kernel, an
invariant feature vector, and a Tamura feature histogram.
To emphasize the fact that the settings for image retrieval are transferable from one task
to another if the databases are sufficiently similar, an experiment with even more similar
databases was done. We subdivided the WANG database into 2 parts of 500 images each,one part consisting of all images with even numbers, the other consisting of images with
odd numbers. Thus, each of these parts consisted of 10 classes with 50 images in each class.
Results for different training situations with the WANG subsets are given in Table 8.13. The
top line gives results for the case that all features are used with equal weights, the other twolines give the results for training of the weights on the two parts of the database. The firsttwo columns show the error rates if leaving one out is used on the databases, the other twocolumns give the error rate if one database is used to query the other. That is, classifying
one database using the other as training data. In all cases training of the parameters on
one database improves the results for the other database and for both query experiments incomparison to the case where all features are used with equal weights. Thus it is suitable
to optimize parameters for the database if the expected query images are similar to thosecontained in the database.
For these experiments the following features were available: five different invariant feature
histograms with monomial kernel, an invariant feature histogram with relational kernel, an
invariant feature vector, local feature histograms with 128 and 256 bins, 32 × 32 thumbnailsof the images, a global texture descriptor, a Tamura texture feature histogram, and a region
descriptor of the images.
73

1
0.8
0.6
0.4
wi = 1.0
p MDS selection
InvFeatHisto f (X) = X(4, 0) · X(0, 9)
InvFeatHisto & relFeatHisto

0.2
0
5

10

15

20

25

30

35

40

45

50

Figure 8.8: Graph of Recall vs NR for the MPEG-7 database.

^ for the MPEG-7 database for different
Table 8.14: Average normalized ranks Rank
settings.
Methodp
InvFeatHisto f (X) = X(4, 0) · X(0, 8)
InvFeatHisto & relFeatHistowi = 1.0
MDS selection

^
Rank
0.040
0.034
0.032
0.032

MPEG-7 database
For the MPEG-7 database a set of 15 images was selected in [Siggelkow 02] and for each ofthese images the set of relevant images was manually determined. For these experiments it
does not make sense to give precision values as the low number of images from each group(between 3 and 14) lets the values decrease very fast. Also, to give error rates is not suitable
for a test set of 15 images only. Additionally, the error rate is 0% due to the fact that thequery images are contained in the database.
For comparison of different methods we give a graph of Recall plotted vs. the number^ in Table 8.14. The
of images returned in Figure 8.8 and average normalized ranks Rank
results show that the base method,p using an invariant feature histogram with monomial kernel
alone (“InvFeatHisto f (X) = X(4, 0) · X(0, 8)”), can be improved by adding other features.
To use the invariant feature histogram with relational kernel additionally (“InvFeatHisto& relFeatHisto”) improves the results strongly. To use all available features (“wi = 1.0”)
improves the result further and to use a reasonable feature set (“MDS selection”) yields thebest result. The experiments using only the invariant feature histograms were presented in[Siggelkow 02] and were repeated for this work to be able to compare them.
74

Table 8.15: Error rates [%] obtained on the ZuBuD database using different methods.
L1O ER[%] on
training data

Method[Shao & Svoboda+ 03a]
[Obdrzalek & Matas 03]
wi = 1.0
Weights optimized on training data

7.3
(3.9)

ER[%]
13.9
0.0
15.7
10.4

For all these experiments, available features were: two invariant feature histograms withmonomial kernels different settings, an invariant feature histogram with relational kernel, an
invariant feature vector, the global texture descriptor, 32 × 32 thumbnails, and the Tamura
feature histogram. For the MDS selection one invariant feature histogram with monomial
kernel, the invariant feature histogram with relational kernel, the Tamura feature histogram,and the global texture descriptor were used. The thumbnails were not used as they did not
obtain good results for the WANG database and the second invariant feature histogram was
not used as one invariant feature histogram should be enough. Probably it would be possible
to obtain even better results when training the weights on this data but this would result ina parameter set valid for exactly this task only.
ZuBuD database
As the ZuBuD database is subdivided into a training and a testing database, it is easily possible to train and test parameters. Comparison results are presented in [Shao & Svoboda+ 03a]using local invariant feature descriptors and in [Obdrzalek & Matas 03] using local affine
frames. The comparison results are given together with our results in Table 8.15. The line
“wi = 1.0” gives error rates for the case that all features extracted are used with equal
weights and the line “Weights optimized on training data” shows results where the feature
weightings were optimized for the training data using a leaving-one-out approach. The results
are better than those presented in [Shao & Svoboda+ 03a] but worse than those presented
in [Obdrzalek & Matas 03]. In [Obdrzalek & Matas 03] the settings are optimized on thisdatabase as they tested various parameters and only one parameter setting obtains this results.
CalTech database
Another task which is closely related to content based image retrieval is the classification ofcomplex scenes. One such task is the CalTech database (cp. Section 7.5). Here, three different
tasks are considered, each consisting of a two class decision problem whether the object ofinterest is depicted in the image or not. In Table 8.16 we present results we obtained using thefeatures presented in this work without incorporation of special domain knowledge or complex
models like those proposed in [Fergus & Perona+ 03] and [Weber 00]. The results show thateach of the three tasks can be solved better with a combination of simple features thanwith a complex model. This implies that the task can be regarded as “too easy” for complex
recognition tasks as the global image similarity is already sufficient to obtain very good results.
75

Table 8.16: Equal error rates [%] on the CalTech database.
Method32×32[Weber 00][Fergus & Perona+ 03]
Tamura feature
combination of features

airplanes
24.0
32.0
9.8
1.6
0.8

faces
15.0
6.0
3.6
3.9
1.6

motorbikes
17.4
16.0
7.5
7.4
8.5

The line “32×32” gives an absolute baseline error rate. This error rate was obtained using
a nearest neighbor classifier for images scaled to 32×32 pixels. The line “Tamura feature”
gives the error rate for a nearest neighbor classifier using only the Tamura texture histogram
and the line “combination of features” uses a combination of Tamura features and invariant
feature histograms.
In [Fei-Fei & Fergus+ 03] experiments on the same data are made, yielding error rates
slightly worse than those presented in [Fergus & Perona+ 03] but the amount of used training
data was reduced enormously. Here, the authors use one to five training images only.

8.3

Performance Evaluation for
Clustering Visually Similar Images

Evaluation of clustering algorithms is a task which was addressed before. A common way
to measure the quality of a partitioning of a data set is the Rand index [Jain & Dubes 88,
Saporta & Youness 02]. It is based upon the number of pairs from the same class belonging
to the same cluster. The Rand index is a number between 0 and 1 where 0 means that theclustering is bad, and 1 means that the clustering is identical to the original partition.
To calculate the Rand index, it is necessary to calculate the contingency table. That is,given two partitionings P = {p1 , . . . , pN } and P 0 = {p01 , . . . , p0M } the M × N matrix C with
Cnm = |pn ∩ p0m | is calculated. Given this matrix the Rand index R is computed ashi P Cn•  P C•m 
C
−
1/
2
2
2
2
n m
 h n i m
R= 
 P Cn•  P Cn•  P C•m 
1 P C•m+− 1/ C222
2
2
2
P P Cnm mwith Cn• =

P
m

8.4

Cnm , C•m =

n

P

n

m

Cnm , and C is the number of images clustered.

nResults for Clustering Visually Similar Images

In this section we present the results we obtained with the clustering application. For the
Google database we present some exemplary results. For this database it is not possible togive quantitative results as we do not have information which images have to be in a cluster
together. To give quantitative and comparable results we also applied the algorithms to the
WANG and the COIL database.
76

Figure 8.9: Results from Google image search for query “cookies”, unprocessed.

8.4.1

Clustering the Google Images

Figure 8.10 shows the result of clustering the 20 first results from Google image search queried
with “cookie”. Cluster 1 contains only images with people, cluster 2 contains images of ediblecookies and some drawings, cluster 3 contains images not fitting into any other cluster, andcluster 4 contains screenshots. Though the partitioning is not a perfect one, as cluster 3
contains images which could be from the other clusters, it is obviously an improvement overan unsorted display as depicted in Figure 8.9.
Figure 8.11 shows the result of clustering the first 25 results from Google image search
queried with “aircraft”. Also here, visually similar images are together in one cluster.

8.4.2

Clustering the WANG & COIL Images

To be able to quantify the results from clustering images we chose the WANG database,where we know the reference partitioning into 10 clusters and the COIL-100 database which
is divided into 100 classes. To compare our results to the results from other groups we also
take a 20 class subset of COIL-100 database (cp. Section 7.10).
In both cases the results improve strongly by adding features. Another interesting results
is that the results from the LBG clustering algorithm are better than those obtained using kmeans clustering, though LBG clustering is provided with less information about the numberof clusters. This is very clear for the complete COIL-100 database. We assume that the
k-means algorithm is sensitive to the initial partition. Thus, the LBG clustering algorithm
seems more robust when using a high number of clusters. Another remarkable result is thefact that our methods outperform the results presented in [Käster & Wendt+ 03] though theytested a lot of parameter settings for each of their algorithms and the results cited are the best
results obtained in their work. That is, the parameters used are trained on the testing data for
their work. Whereas our methods were not specially optimized to the task. The only settingchanged was the number of clusters for k-means, the number of splits for LBG clusteringand the features used as shown in the tables. For the k-means algorithm the correct number
77

cluster 1

cluster 2cluster 3

cluster 4

Figure 8.10: Results from Google image search for the query “cookies” clustered using
the LBG clustering algorithm.

cluster 1cluster 2cluster 3

cluster 4cluster 5

Figure 8.11: Results from Google image search for the query “aircraft” clusteredusing the k-means clustering algorithm.

of cluster centers was given, and for the LBG clustering the number of splits was set to theminimum allowing for the right number of clusters. These results leads us to the conclusion
78

Table 8.17: Results for clustering WANG.
Database
WANG

Method/Feature

Rand-Index
LBG k-means(1) Invariant feature histogram(2) Relational invariant feature histogram(3) Tamura histogram

0.46
0.22
0.25

0.47
0.24
0.27

(1) & (2)(1) & (3)(1) & (2) & (3)

0.43
0.48
0.57

0.53
0.54
0.58

Table 8.18: Results for clustering COIL.
Database
COIL 20

Method/Feature

Rand-Index

Results from other works[Käster & Wendt+ 03] k-Means[Käster & Wendt+ 03] CLARA[Käster & Wendt+ 03] PAM[Käster & Wendt+ 03] hierarchical

0.53
0.54
0.55
0.62

(1) Invariant feature histogram(2) Relational invariant feature histogram(3) Tamura histogram

LBG
0.64
0.53
0.45

k-means
0.67
0.63
0.63

(1) & (2)(1) & (3)(1) & (2) & (3)

0.83
0.83
0.79

0.74
0.76
0.82

(1) Invariant feature histogram(2) Relational invariant feature histogram(3) Tamura histogram

0.53
0.48
0.51

0.67
0.63
0.63

(1) & (2)(1) & (3)(1) & (2) & (3)

0.54
0.65
0.64

0.74
0.76
0.82

COIL 100that the features presented are well suited to this task.

79

80

Chapter 9

Conclusion and Perspectives
Conclusion
In this work a broad variety of features for content-based image retrieval was presented,
investigated, and experimentally evaluated. This work gives a review of features proposed forimage retrieval and refines several of them. An emphasis was placed on the invariant feature
histograms. All the features presented were used for content-based image retrieval on a wide
variety of databases to evaluate the different discrimination performances of these features.
For the first time, quantitative results are given for a wide variety of databases using different
image retrieval methods. Experiments to determine the optimal set of features for different
image retrieval tasks were carried out and the characteristics of the different features wereanalyzed using an empirical correlation analysis.
For the invariant features we investigated the extension to scaling and to partially rotation
invariant features. Both extensions did not improve the retrieval performance, which is inaccordance with the theoretical prediction.
To analyze the features various dissimilarity measures were implemented, refined, andtested, as different features require different comparison methods. As well as a large amountof features was introduced and presented, we gave a broad overview of different comparison
measures for the different types of features.
An important part of this work was the implementation of a flexible image retrieval system,
capable of managing large amounts of different features and distance measures. The system isa fully automatic system, that is, it is presented with a query image and without any further
information the query is evaluated.
To measure the performance of the system an appropriate performance measure had to be
determined. Several different performance measures were evaluated and compared using anempirical correlation analysis. This analysis showed that most of the performance measures
are indeed highly correlated and thus the error rate was selected as performance measure
to compare the different image retrieval setups since it is a well known method in object
recognition and it is easily computable.
The experiments showed that the connection between image retrieval and image recognition is in fact a very close one. All the methods that improve the results in the one task
also improve the results in the other task. On the one hand, the high flexibility of the image
retrieval system implemented allowed for using many of the classification methods known forimage retrieval. On the other hand, the features proposed for image retrieval were used for81

classification.
The experiments show that the selection of features for an image retrieval task strongly
depends on the images involved. One important aspect is to use a selection of features
accounting for the different properties of the images as there is no feature capable of covering
all aspects of an image. The experiments show that for color images of a general type (e.g.
photographs of arbitrary scenes) a combination of the following features is suitable:• invariant feature histograms• Tamura texture histogram• local features or local feature histograms• Gabor features
For gray images from a more limited domain (e.g. radiographs) the invariant features do not
obtain good results but instead the pixel values of the images are very important.
Experiments to find a good feature set revealed that it is suitable to search for an optimal
set of weightings and features if the training database is very similar to the testing databaseused for the actual retrieval task. However, this is not suitable to search for an optimal setting
when the databases differ significantly. In this case it is best to calculate a reasonable set offeatures and use all of these with equal weight.
Application of the presented features is not limited to image retrieval tasks, but the insights are adaptable to other tasks as well, for example for classification. Another application
where the features were used is clustering of visually similar images. Since many image searchengines are based on text retrieval, these image search engines are not suitable for all tasks.
With the methods presented, it is possible to enhance the results from text based image
search engines. We presented an approach to improve text based image search engines using
the proposed features and some clustering algorithms. That is, given a set of images, thefeatures are extracted and a clustering algorithm is applied to present the user with a set ofimages that can be browsed more easily.
We investigated the connection between local features and the image distortion modeland found that local features recover the lacking restriction with respect to deformation
constraints by a higher amount of local information. This was proven experimentally for the
local feature approach with very small local features and for the image distortion model withlarge subimages.

Perspective
At this point of the work, still some questions remain unanswered and many ideas remain
untested and need to be investigated. It would be interesting to see the results of other image
retrieval systems using the same databases. One step in this direction is already in progressas the authors of the GNU Image Finding Tools (GIFT) are experimenting with the IRMA
database in the context of the MedGIFT project.
Another desired application is to use the methods presented to accelerate and ease thetask of classification of images to be included into the IRMA database. Here, the images to
be classified by radiologists are taken as query images to the already classified images andthe nearest neighbors for those are returned together with their classification to allow theradiologist selecting the best fit and refine the classification if necessary.
82

As the image retrieval system as it is realized now has to keep all data necessary for the
retrieval process in memory the size of the database to search is restricted by the amount ofmemory available. For the future, database support is desirable.
A future aim for content-based image retrieval surely is to go from appearance based image
retrieval to semantics based image retrieval. That is, the images should be retrieved based on
the objects contained in the scenes, the acts depicted or, if necessary, e.g. the names of thepersons shown. For semantic retrieval a complete understanding of the images is necessary.
Similar demands for image understanding techniques are in the task of automatic annotation. Here the objective is to take a picture and automatically generate a textual descriptionof its contents. To get a satisfactory result, image understanding is necessary as well.
From the fact that most of the works cited are from the last five years and image retrieval
as it is understood now, is a quite new area of research it can be seen that content-based
image retrieval is an active area of research. The still increasingly growing amount of digitally
available pictures will enforce further research.
Another very important task is the creation of a well-documented standard test databasefor content-based image retrieval and fixed testing criteria to be able to compare different
image retrieval systems in a quantitative way as it is already common in textual information
retrieval for years. A first starting point for this is given in this work, but further research,larger databases, and better annotations and relevance criteria still have to be found.
For the analysis of complex scenes some of these features offer possibilities to be integrated
into a holistic model as proposed in [Keysers & Dahmen+ 03].

83

84

Appendix A

Software Documentation
In this chapter we give an overview of the software developed in the context of this work. Firsta list of software which has been used to create the software, the data, and this document isgiven and then we introduce the software developed.
In the course of this work many freely available programs have been used: Linux as
operating system, X and sawfish window manager as graphical desktop environment, gcc
compilers and python to write programs, libpng and libjpeg for reading image files, libANN
for efficient approximative nearest neighbor search, GetPot for parsing of command lines, qiv,
xv, ImageMagick and The Gimp for viewing and manipulating images, Emacs, XEmacs and
Vim for writing programs, scripts, and this thesis, and LATEX and xfig for typesetting thisthesis. In the following a list of the software developed in the context of this work is given
together with a short description for each program.

A.1

FIRE Framework

FIRE (Flexible Image Retrieval Engine) is a framework for content based image retrieval. It
consists of a server part implemented in C++ and a client part implemented in python. The
server and the client communicate over network sockets by a simple line-oriented protocol.

fire
The server of fire can work in different modes. The most important mode is server mode.
In server mode, a client is able to connect via network socket to the server and change its
settings and retrieve images from a database. Other modes available are distance file mode,
performance evaluation mode, and query performance evaluation mode.
In distance file mode a file with all distances between all image pairs from the databaseis created. This is necessary for efficient searching of the best parameter set. In performance
evaluation mode, the system queries itself in a leaving one out manner for each image from thedatabase and returns the results, calculates performance evaluation measures and averages
those over all images. In query performance evaluation mode the retrieval performance for agiven setting is measured with query images that are not contained in the database.
Invocation of fire is done as follows:
fire (-s | -perf | -distanceFile <filename> | -qperf) [options]with85

-s [port] starts fire in server mode. By default the socket 12960 is used, but a different
port can be specified.
-distanceFile <filename> starts fire in distance file mode. The distance file is written to
the specified file.
-perf starts fire in performance evaluation mode.
-qperf starts fire in query performance evaluation mode.
For each of these modes the following options are available. In some cases some options are
obligatory:-filelist <filename> specifies the file list describing the database to be loaded by fire
(obligatory in distance file mode, performance evaluation mode, and query performance
evaluation mode).
-results <number> specifies the number of results returned for each query (default: 9).
-distN <distname> sets the distance measure used for the N-th file (N starting with 0,
obligatory in distance file mode, performance evaluation mode, and query performance
evaluation mode for at least one N, otherwise no useful result is obtained). For a list ofavailable distance measures see Table A.1.
-weightN set the distance measure used for the N-th file (N starting with 0, defaults to 1 if
N-th distance is set, 0 otherwise).
-queryFileList <filename> to specify the file list describing which files to use in query performance evaluation mode (obligatory in query performance evaluation mode, ignored
otherwise).
-ROCoutfile <filename> if specified, in query performance evaluation mode, a file with
distances to nearest neighbors from each class is written for each query. This is necessary
to obtain ROC (Receiver Operating Characteristic) curves. (ignored in any mode apartfrom query performance evaluation mode).

fire.py and fireadm.py
fire.py and fireadm.py are web front ends to the fire server. Both are implemented inpython as cgi-scripts and communicate with the server using a TCP socket. The difference
between fire.py and fireadm.py is that the latter allows for changing several parameters as
the used distances, the used weights, the used database, and the number of results. Default
server, default port, and directory for temporary data can be modified easily by changing
some variables in the program.

A.2

Clustering Framework

The clustering framework is a set of two programs to cluster images into visually similargroups. There is a main program written in C++ and a small web front end written inpython executing the main part.
86

clustertest
clustertest is the main clustering program. It reads images from a database and clusters
them. clustertest takes the following parameters:-c <clusteralgorithm> to select the cluster algorithm used. em and kmeans are available
at the moment.
-d <distancemeasure> to select the distance measure used to compare images and to compare images with cluster centers. For a list of available distance measures see Table A.1.
-h to give a short help
-dummy if this parameter is given, no input data is read, but some data is generated andclustered. This is convenient to test cluster algorithms-jf <filename> if this parameter is given, the specified text file containing the data isread. The file has to be an ASCII file of very simple format used at the Lehrstuhl
für Informatik 6 for internal data.
-rgb <filename> if this parameter is given, the specified filelist is read. If additionally the-suffix option is given, only a subset of the available feature files is read.
-suffix=<suffix1:suffix2:...:suffixN> using this parameter it is possible to specify thefeatures used from a database description file.
-noAnalyse by default, a set of cluster performance evaluation measures is computed. If thisparameter is used, this analysis is omitted.
-testAnalyser if this parameter is specified, after clustering and giving the performance
evaluation measures some test cases for the performance measures are generated andanalyzed.
-noRearrange by default, after clustering the data is rearranged such that the data points
are sorted by distance to the cluster center. If this parameter is specified this step isomitted.
Parameters only applicable if -c em is given-splitMode <split mode> selects the split mode. Available options: allSplit(default),
largestSplit, varianceSplit.
-disturbMode <disturb mode> selects the center disturb mode. Available options:varianceDisturb (default), meanDisturb, meanDisturb2, and constDisturb.
-poolMode selects the averaging mode for the cluster variances.
Available options: clusterPooling, dimensionPooling, and noPooling (default).
-dontSplitBelow <number> specifies the smallest cluster size which may be split. If a cluster
has less members than this, it is not split (default: 10).
-iter <number> specifies the number of reestimation iterations between two splits (default: 10).
87

-minObs <number> specifies the number of data points which have to be in a cluster. If thecluster has less members it is deleted (default: 4).
-maxSplit <number> specifies the maximum number of splits (default: 4).
-stopWithNClusters <number> if this option is set, the algorithm stops splitting when thespecified number of clusters is reached.
-epsilon <value> specifies the epsilon used for disturbing the cluster centers (default: 0.1).
Parameters only applicable if -c kmeans is given-nOfClusters <number> specifies the number of clusters to be calculated (default: 10).
-iterations <number> specifies the number of reestimation iterations (default: 10).

cloogluster.py
cloogluster.py is a very simple web front end for clustertest. It reads a list of available
databases and provides a graphical interface to clustertest. clustertest is started and theoutput is parsed to present the clusters to the user in a convenient way.
Nearly all options of clustertest can be accessed easily from this interface. Paths andenvironment setup can easily be adjusted.

A.3

Feature Extraction Tools

In this section the programs developed for feature extraction are briefly described. All the
programs are able to read jpeg and png image files when images are loaded and read gzipped
text files when text files are read.

extractColorHistoextractColorHisto is a program to create simple color or grey histograms from images.
extractColorHisto is invoked by:
extractColorHisto [-steps <number>](-pseudocolorhisto|-greyhisto|-mdcolorhisto) filename
The options mean:-steps <number> specifies the number of bins for the resulting histogram.
-mdcolorhisto specifies that the given image is read as color image and a multi dimensional
histogram is created. The value of -steps specifies the number of steps per dimension
here, i.e. -steps 8 results in a 512 bin histogram from an RGB image.
-pseudocolorhisto specifies that the image is read as color image, and one histogram iscreated for each color layer. -steps specifies the number of bins per color layer here.
-greyhisto specifies that the image is read as gray value image. A gray value histogramwith the number of bins specified by -steps is extracted.
The output is written to a file with the same name as the input file concatenated with.pseudomdhisto, .greyhisto, or .mdhisto, respectively.
88

Table A.1: Available dissimilarity measures.
Symbold2 (·, ·)d1 (·, ·)dJSD (·, ·)dKLD (·, ·)dχ2 (·, ·)dhis (·, ·)dEM D (·, ·)dtw (·, ·)dtw (·, ·)dlf (·, ·)dt (·, ·)drd (·, ·)drbd (·, ·)dt (·, ·)dqhrm (·, ·)dirm (·, ·)df (·, ·)dF (·, ·)d√1−F (·, ·)dlog(2−F ) (·, ·)darccos F (·, ·)dsin F (·, ·)didm (·, ·)didm (·, ·)Description
Euclidean distance
L1 distance
Jensen Shannon divergence
Kullback-Leibler divergenceχ2 -distancehistogram intersection
earth movers distancetime warp distance with Euclidean
time warp distance with L1
local feature distancetangent distance
relative deviation
relative bin deviation
tangent distance for histograms
quantized hungarian region matching
greedy region matching
integrated region matching
fidelity
fidelity based distance measurefidelity based distance measurefidelity based distance measurefidelity based distance measurefidelity based distance measure
image distortion model
image distortion model (with Sobel)
vote counting for local features

Identifier
euclidean
l1
jsd
kld
chisquarehistogramintersection
emd
timeshift
timeshiftl1
localfeatures
tangent
reldevrelbindev
histotangentdist
regiondistv2
irm
fidelity
oneminusfidelity
sqrtoneminusfidelity
log2minusfidelity
arccosfidelity
sinoneminusfidelity
idmdistanceidmsobelgloballocalfeaturedistance.

extractTamuraTextureFeature
extractTamuraTextureFeature extracts Tamura texture features as described in Section 4.6.
It is invoked byextractTamuraTextureFeature [options](-color|-grey) <filename>
Available options are:-suffix <suffix> to specify a suffix for the output file (default: .tamurafeature)-saveTextureImages to specify that the texture image is saved. By default it is not saved.
-textureimagesuffix to specify the suffix for the texture image file. (default: .tamura.png).
The -color and -grey switches select whether the input image is read as color or grey image.
The output histogram is written to a file with the same name as the input file concatenatedwith the suffix.
89

extractaspectratio
extractaspectratio is a program to write the size of the image to a file. Invocation is done
withextractaspectratio [options] -file <filename>
Available options are:-suffix <suffix> to specify a suffix for the output file (default: .ar)
The file given with -file is read as image and the size is written to a file with the same nameconcatenated with the given suffix.

extractglobaltexturefeature
extractglobaltexturefeature is a program to extract the texture feature described in
Section 4.7. Invocation is done by
extractglobaltexturefeature [options] (-color|-grey) <filename>
Available options are:-suffix <suffix> to specify a suffix for the output file (default: .globtexturefeat)The file given by <filename> is read as color or gray image depending on the option andthe output is written to a file with the same name concatenated with the suffix. The mainpart of this program is courtesy of the IRMA project and was developed by Boris Terhorst[Terhorst 03].

extractinvariantfourierfeature
extractinvariantfourierfeature is a program to extract a Fourier Mellin feature as described in Section 4.4.3. The experiments have not been done with this program, but with an
implementation in MatLab offering higher flexibility. Invocation of this program is done by
extractinvariantfourierfeature -file <filename>
The given file is read as gray image, the Fourier Mellin transformation is applied and theresult is written to a file with the same name concatenated with .fouriermellin.

extractinvfeathisto
extractinvfeathisto extracts invariant feature histograms as described in Section 4.4.1.
Invocation is done by
extractinvfeathisto [options] (-frgb|-fgrey|-rel) <filename>
Available options are:-suffix <suffix> to specify the suffix of the output file. (default: .rgbfeat if -frgb,.greyfeat if -fgrey, and .relhisto if -rel.
90-featurefunction <featurefunction> to specify the feature function used. Available feature functions arep• X01X20 uses f (X) = X(0, 1) · X(2, 0) (default).
p• X01X100 uses f (X) = X(0, 1) · X(10, 0).
• X01-X100 uses f (X) = X(0, 1) − X(10, 0).
p• hsvparse*:X1=x1 :Y1=y1 :X2=x2 :Y2=y2 uses f (X) = X(x1 , y1 ) · X(x2 , y2 )for HSV images.
p• parse*:X1=x1 :Y1=y1 :X2=x2 :Y2=y2 uses f (X) = X(x1 , y1 ) · X(x2 , y2 ).
• parse3x:X1=x
p1 :Y1=y1 :X2=x2 :Y2=y2 :X3=x3 :Y3=y3
uses f (X) = 3 X(x1 , y1 ) · X(x2 , y2 ) · X(x3 , y3 ).
• parse-:X1=x1 :Y1=y1 :X2=x2 :Y2=y2 uses f (X) = X(x1 , y1 ) − X(x2 , y2 ).
-steps <steps> specifies the number of steps for the created histogram. This is the numberof steps per dimension. That is, for a color image a histogram with <steps>3 bins iscreated and for gray images <steps> bins are created.
-samples <samples> specifies the number of samples taken for Monte Carlo integration. If
not specified integration is not done by Monte Carlo integration but exact.
-scalingStart <value> specifies the smallest scale factor to use.
(default: 1.0=original size).
-scalingMulti <value> specifies the factor by which the scale factor is multiplied each
iteration (default: 1.1).
-scalingStop <value> specifies the largest scale factor to use (default: 1.0=original size).
-rotationAngle <value> specifies the rotation angle for integration. (default: 360=fullcircle)With -frgb the input image is read as color image and a multi dimensional histogram iscreated, with -fgrey the input image is read as gray image and a one dimensional histogramis created. With -rel color or gray does not matter and a three dimensional histogram iscreated of the relational histograms. To obtain scale invariant features, the image size and thefeature function used have to be considered. It is necessary to choose the scaling parameterssuch that the smallest image considered is smaller than the support size of the function, andfor the largest image considered it is necessary, that one pixel is larger
p than the support sizeof the function. Let X be an image of size 384 × 256, and let f (x) = X(4, 0) · X(0, 8). The
image has to be scaled from 8 × 8 up to the eightfold of its original size: 3072 × 2048.

extractinvfeatvec
extractinvfeatvec is a program to extract invariant feature vectors as described in Section 4.4.2. It is invoked byextractinvfeatvec [options] (-cvec|-gvec) <filename>.
Available options are91

-suffix <suffix> to specify a suffix for the output file(default: .colorinvfeatvec/.greyinvfeatvec)-samples <samples> specifies the number of samples taken for Monte Carlo integration. If
not specified integration is not approximative but exact.
-cvec specifies that the image is read as color image, -gvec specifies that the image is readas gray image. Depending on this the resulting vector has a different number of entries: 44
for grey images and 132 for color images.

extractlfv2
extractlfv2 is a program to extract local features from images. It is invoked byextractlfv2 [options] (-color|-gray) -img <filename>
Available options are-winsize <number> specifies the size of the extracted local features. A value of n results inlocal features of size (2n + 1) × (2n + 1).
-threshold <value> specifies the variance threshold to determine which local features are
extracted.
-nOfFeatures <number> specifies the number of local features to be extracted. If this isspecified, the option -threshold is ignored.
-subsampling <number> specifies the step size between two pixels considered. By default
this is 1 which means, that each pixel is considered.
-images if this is set, the local features are additionally saved as PNG images (default: notset).
-padding if this is set, the image is padded to be large enough to allow local feature to be
extracted from each pixel. If this is not set local features are only extracted from thecenter points (default: not set).
-suffix <suffix> this specifies the suffix for the output file containing the local features as
text.

em-segmentation
em-segmentation is the program to create region features as described in Section 4.10. It is
invoked byem-segmentation [options] -file <filename>
Available options are-suffix <suffix> to specify the suffix of the file where the region features are written to(default: .regions).
-maxSplits <int> to specify the number of splits done in LBG clustering (default: 3)92

-iter <int> to specify the number of reestimation iterations between two splits (default:
10).
-minObs <int> to specify the minimal number of observations in a cluster. If a cluster
contains less observations it is deleted (default: 4).
-epsilon <double> to specify the epsilon used for splitting (default: 0.1).
-disturbMode <disturbMode> to specify the way of disturbing means while splitting. Available modi are: varianceDisturb (default), meanDisturb, meanDisturb2, constDisturb.
-poolMode <poolMode> to specify if and how variances are pooled in the cluster process.
Available options: clusterPooling, dimensionPooling, and noPooling (default).
-d <distance> to specify the used distance to compare pixel features (default: euclidean).
For a list of available distance measures see Table A.1.
-smoothRange <int> to specify the size of the smoothing operator in post processing
If this program is started, a segmentation is created and some data about the segments is
saved to an output file. The output file has the same name as the input image concatenatedwith the given suffix. Additionally an image showing the regions is saved with the same nameconcatenated with .png.

blobworld-matlab source
From http://elib.cs.berkeley.edu/photos/blobworld/ it is possible to download the sourcesof the BlobWorld feature extraction. This is a MatLab program and we used it to generatethese features. Additionally a small program to convert the resulting MatLab files to a simple
text-based format has been developed.

lf-pcalf-pca is the program to apply the PCA dimensionality reduction to a set of files with local
features or gabor features. It is invoked by
lf-pca [options] <filelist>
where <filelist> specifies the list of files containing local features to be processed. Available
options are:-transform <filename> this options specifies that the PCA matrix does not have to be
estimated but is loaded from the specified file.
-saveto <filename> this options specifies, that the PCA matrix has to be estimated andafterwards is saved to the specified file. This cannot be used together with -transform.
-outDim <number> specifies the dimensionality of the output data.
When this program is started, normally all files from the file list are read, the mean andthe covariance matrix from this data is estimated and transformed for PCA transformation
using singular value decomposition (SVD). Then the data is read again and transformed using
the matrix. The transformed data is saved into files with the same name as the input files
appended with .pca.
93

dbpcatransformdbpcatransform is a program to apply PCA dimensionality reduction to nearly any type offeature. It is invoked withdbpcatransform -toDim <dim> -filelist <filelist>
When the program is started it reads all files specified in the file list, calculates the covariancematrices and the means for the different types of features, transforms these using SVD andtransforms the specified files. The output files are written to files with the same names as the
input files concatenated with .pca.

gaborizegaborize is the program to extract Gabor features as described in Section 4.5. It is invokedbygaborize [options] filename
Available options are-numpha <number> to specify the number of different phases used (default: 5).
-numfreq <number> to specify the number of different frequencies used (default: 5).
-threshold <value> to specify the local variance threshold for feature extraction(cp. extractlfv2)-winsize <number> to specify the window size for local variance calculation(cp. extractlfv2)-all to extract all gabor features. If this is specified -threshold, -winsize, and-nOfFeatures is ignored.
-nOfFeatures <number> to specify the number of gabor features extracted.
Overrides -threshold.
-color or -grey To specify whether the image is a color or a gray image.
When the program is started the specified image is read, and Fourier transformed. Thenthe Fourier transform is multiplied with different filters and retransformed. From these images
the Gabor feature vectors are extracted and saved to a file with the same name as the input
file with .gaborfeatures appended.

94Appendix B

Additional Tables
Table B.1: Error rates for different features on WANG
database. A selection from this table is presented and explained in Section 8.2.2.
Featurep
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = pX(4, 0) · X(0, 8) scaling
3
InvFeatHisto f (X) = p
X(2, 0) · X(4, 4) · X(0, 8)
3
InvFeatHisto f (X) = X(2, 0) · X(4, 4) · X(0, 8)
Color Histogramp
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = pX(0, 1) · X(2, 0)
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = pX(0, 1) · X(10, 0)
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = X(4, 0) · X(0, 8)
Color Histogramp
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = pX(0, 1) · X(2, 0)
InvFeatHisto f (X) = pX(0, 1) · X(10, 0)
InvFeatHisto f (X) = pX(0, 0) · X(30, 30)
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = X(0, 0) · X(30, 30)
PseudoMDColor Histogram
PseudoMDColor Histogram
Tamura Histogram
Tamura Histogram
LF Histogram 256
LF Histogram 256
LF Histogram 128
p
InvFeatHisto f (X) = X(0, 1) − X(10, 0)
LF Histogram 128
continued on next page95

Distance
JSD
JSD
JSD
L1
JSD
L1
JSD
L1
JSD
JSD
JSD
L1
L1
L1
L1
JSD
L1
L1
JSD
L1
JSD
L1
JSD
L1
JSD
JSD
L1

ER
15.9
16.1
16.4
16.4
17.9
18.2
18.3
18.4
19.9
19.9
20.0
21.0
21.3
23.2
25.1
25.2
25.5
27.8
27.8
29.0
31.0
32.1
32.5
34.2
35.9
36.5
37.0

Feature
LF Histogram 64
p
InvFeatHisto f (X) = pX(0, 0) · X(4, 0)
InvFeatHisto f (X) = X(0,p0) · X(4, 0)
InvFeatHisto PCA(f (X) = X(4, 0) · X(0, 8))
LF Histogram 64
PCA(Color Histogram)
ColorInvFeatVec
InvFeatHisto f (X) = X(0, 1)
p− X(10, 0)
PCA(InvFeatHisto f (X) = pX(0, 1) · X(10, 0))
PCA(InvFeatHisto f (X) = pX(0, 1) · X(2, 0))
PCA(InvFeatHisto f (X) = X(4, 0) · X(0, 8))
Gabor Histogram 256p
PCA(InvFeatHisto f (X) = X(0, 0)X(30, 30))
Gabor Histogram 128p
PCA(InvFeatHisto f (X) = pX(4, 0) · X(0, 8))
PCA(InvFeatHisto f (X) = pX(4, 0) · X(0, 8))
PCA(InvFeatHisto f (X) = X(0, 2) · X(4, 4) · X(8, 0)
Gabor Histogram 256
PCA(PseudoMDColor Histogram)
Global texture feature
Gabor Histogram 128
Gabor Histogram 64
Gabor Histogram 64
Regions (max 4, smooth 5)
32x32
Regions (max 8, smooth 10)32x32, gray
Regions (max 4, smooth 10)
PCA(Tamura histogram)
PCA(ColorInvFeatVec)
PCA(32x32)p
PCA(InvFeatHisto f (X) = pX(0, 0) · X(4, 0))
PCA(InvFeatHisto f (X) = X(0, 1) − X(10, 0))
PCA(Global texture feature)
local features

96

Distance
JSD
JSD
L1
Euclidean
L1
Euclidean
Euclidean
L1
Euclidean
Euclidean
Euclidean
JSD
Euclidean
JSD
Euclidean
Euclidean
Euclidean
L1
Euclidean
Euclidean
L1
L1
JSD
irm
Euclidean
irm
Euclidean
irm
Euclidean
Euclidean
Euclidean
Euclidean
Euclidean
Euclidean
glfd

ER
37.2
37.7
38.9
39.0
40.7
43.7
44.9
46.9
47.7
47.8
47.8
48.2
49.3
49.9
50.2
50.7
51.0
51.2
51.3
51.4
51.7
51.8
52.8
54.3
55.1
55.3
56.1
56.1
56.3
56.7
62.5
68.8
71.5
73.3
87.5

Table B.2: Error rates for different features on IRMA-1617
database. A selection from this table is presented and explained in Section 8.2.2.
Feature32x32
LF(5x5) histogram 512
LF(5x5) histogram 256
LF(5x5) histogram 128
LF(5x5) histogram 64
LF(3x3) histogram 256
LF(3x3) histogram 128
LF(19x19)
LF(3x3) histogram 64
LF(3x3) histogram 512
32x32
Tamura histogram
Gabor features
Tamura histogram
32x32 Tamura histogram
InvFeatHisto f (X) = rel(X(0, 0) − X(0, 4))
LF(5x5)LF(5x5)LF(3x3) histogram 1024
Gabor histogram 256
LF(19x19) histogram 256
32x32 Tamura image
Gabor histogram 256
Gabor histogram 128
Gabor histogram 256
Gabor histogram 256
LF(19x19)
InvFeatHisto f (X) = rel(X(0, 0), X(4, 0))
Gabor histogram 128
LF(19x19) histogram 128
LF(3x3)LF(5x5)p
InvFeatHisto f (X) = X(0, 0) · X(0, 2)
Gabor histogram 64 p
InvFeatHisto f (X) = pX(0, 0) · X(0, 2)
InvFeatHisto f (X) = X(0, 0) · X(4, 0)
LF(19x19) histogram p
64
InvFeatHisto f (X) = X(0, 0) · X(4, 0)
Image size
Gabor histogram 64continued on next page

97

Distance
IDM Sobel
JSD
JSD
JSD
JSD
JSD
JSD
lf-l1oJSD
JSD
Euclidean
JSD
glfd
L1
L1
JSD
glfd
lfd
JSD
JSD
JSD
Euclidean
JSD
JSD
JSD
L1
glfd
L1
L1
JSD
lfd
lf-l1o
JSD
JSD
L1
JSD
JSD
L1
Euclidean
L1

ER
6.7
9.3
9.5
10.1
11.6
11.7
12.6
13.0
14.3
17.7
17.7
19.3
20.6
20.9
21.3
22.6
22.9
23.1
23.2
24.4
24.6
24.6
25.4
25.6
25.7
25.8
26.4
26.9
27.0
28.0
28.4
28.8
29.2
29.3
29.9
30.1
30.2
30.3
30.4
30.4

Featurep
InvFeatHisto f (X) = pX(0, 0) · X(0, 8)
InvFeatHisto f (X) = X(0, 0) · X(0, 8)
LF(3x3)p
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = pX(0, 0) · X(0, 32)
InvFeatHisto f (X) = pX(4, 0) · X(0, 8)
InvFeatHisto f (X) = X(0, 0) · X(0, 16)
LF(3x3)p
InvFeatHisto f (X) = pX(0, 0) · X(0, 16)
InvFeatHisto f (X) = pX(0, 0) · X(0, 32)
InvFeatHisto f (X) = pX(0, 1) · X(2, 0)
3
InvFeatHisto f (X) = p
X(0, 2) · X(4, 4) · X(8, 0)
3
InvFeatHisto f (X) = X(0, 2) · X(4, 4) · X(8, 0)
InvFeatVector
Fourier Mellin Feature

98

Distance
JSD
L1
lf-l1o
JSD
L1
L1
JSD
glfd
L1
JSD
L1
JSD
L1
Euclidean
Euclidean

ER
31.0
31.2
31.7
31.9
32.1
32.1
32.2
32.8
33.0
33.9
38.1
41.5
44.2
52.9
53.1

Table B.3: Error rates for training and classification task for different features on
IRMA-3879 database.
FeatureDistance

Image 32×32
RelFeatHisto
InvFeatHisto
InvFeatHisto (scaling)
Image size
InvFeatVec
Tamura Histogram
Tamura Image
small Tamura Histogram

Euclidean
JSD
JSD
JSD
JSD
Euclidean
JSD
Euclidean
JSD

L1O ERon training data
8 classes 26 classes
16.7
17.9
20.2
19.5
39.7
38.6
39.5
39.0
33.2
57.3
82.4
82.3
19.0
18.6
23.8
25.5
21.5
22.9

ER
test with train
8 classes 26 classes
20.8
21.7
24.9
25.4
44.2
43.3
43.8
44.0
38.8
63.8
98.9
98.8
23.1
23.3
26.4
27.1
25.4
27.0

Table B.4: Error rates for different dissimilarity measures
on WANG database forpinvariant feature histogram with f (X) = X(4, 0) · X(8, 0). A selecitonof this table is presented and explained in Section 8.2.1.
Disssimilarity measuredlog(2−F ) (·, ·)d√1−F (·, ·)d√1−F (·, ·)dJSD (·, ·)dχ2 (·, ·)drbd (·, ·)dhis (·, ·)d1 (·, ·)drd (·, ·)dt (·, ·)d2 (·, ·)darccos F (·, ·)dsin F (·, ·)dKLD (·, ·)

99

ER
15.6
15.6
15.6
15.9
16.5
17.4
18.4
18.4
25.6
27.6
28.3
31.5
31.5
78.4

Table B.5: Error rates for different dissimilarity measures on IRMA-1617 database for
local feature histograms of 5 × 5 local features with 512 bins. A selectionof this table is presented and explained in Section 8.2.1.
Dissimilarity measuredhis (·, ·)d1 (·, ·)dχ2 (·, ·)dJSD (·, ·)dlog(2−F ) (·, ·)d√1−F (·, ·)d√1−F (·, ·)drd (·, ·)drbd (·, ·)d2 (·, ·)dtw (·, ·)darccos F (·, ·)dsin F (·, ·)dKLD (·, ·)

100

ER
8.3
8.3
9.1
9.3
9.5
9.5
9.5
11.7
12.0
14.2
14.2
45.8
45.8
74.1

Bibliography[Barnard & Duygulu+ 01] K. Barnard, P. Duygulu, D. Forsyth. Clustering Art. Proc. Computer Vision and Pattern Recognition, Vol. 2, pp. 435–439, Kauai, Hawai, Dec. 2001.
[Barnard & Duygulu+ 02] K. Barnard, P. Duygulu, D. Forsyth. Modeling the Statistics of
Image Features and Associated Text. Proc. Document Recognition and Retrieval, Electronic
Imaging, San Jose, CA, Jan. 2002.
[Barnard & Forsyth 01] K. Barnard, D. Forsyth. Learning the Semantics of Words and Pictures. Proc. International Conference on Computer Vision, Vol. 2, pp. 408–415, Vancouver,
Canada, July 2001.
[Berkhin 02] P. Berkhin. Survey of Clustering Data Mining Techniques. Technical report,
Accrue Software, San Jose, CA, 2002.
[Brill & Barrett+ 92] M. Brill, E. Barrett, P. Payton. Projective Invariants for Curves in
Two and Three Dimensions, chapter 9 in Geometric Invariance in Computer Vision, pp.
193–214. MIT Press, 1992.
[Carson & Belongie+ 02] C. Carson, S. Belongie, H. Greenspan, J. Malik. Blobworld: Image
Segmentation Using Expectation-Maximization and its Application to Image Querying.
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 8, pp. 1026–
1038, Aug. 2002.
[Carson & Thomas+ 99] C. Carson, M. Thomas, S. Belongie, J. M. Hellerstein, J. Malik.
Blobworld: A System for Region-Based Image Indexing and Retrieval. Proc. International
Conference on Visual Information Systems, pp. 509–516, Amsterdam, The Netherlands,
June 1999. Springer Verlag.
[Chen & Wang 02] Y. Chen, J. Z. Wang. Region-Based Fuzzy Feature Matching Approachto Content-Based Image Retrieval. IEEE Transactions on Pattern Analysis and MachineIntelligence, Vol. 24, No. 9, pp. 1252–1267, Sept. 2002.
[Dahmen & Hektor+ 00] J. Dahmen, J. Hektor, R. Perrey, H. Ney. Automatic Classification of Red Blood Cells using Gaussian Mixture Densities. Proc. Bildverarbeitung für die
Medizin, pp. 331–335, Munich, Germany, March 2000.
[Deselaers & Keysers+ 03a] T. Deselaers, D. Keysers, H. Ney. Clustering Visually Similar
Images to Improve Image Search Engines. Proc. Informatiktage 2003 der Gesellschaft für
Informatik, to appear, Bad Schussenried, Germany, Nov. 2003.
101

[Deselaers & Keysers+ 03b] T. Deselaers, D. Keysers, R. Paredes, E. Vidal, H. Ney. Local
Representations for Multi-Object Recognition. Proc. DAGM 2003, Pattern Recognition,
25th DAGM Symposium, Vol. 2781 of Lecture Notes in Computer Science, pp. 305–312,
Magdeburg, Germany, Sept. 2003. Springer Verlag.
[Duda & Hart+ 01] R. O. Duda, P. E. Hart, D. G. Stork. Pattern Classification. John Wiley& Sons, New York, NY, 2nd edition, 2001.
[Duygulu & Barnard+ 02] P. Duygulu, K. Barnard, N. de Freitas, D. Forsyth. Object Recognition as Machine Translation: Learning a Lexicon for a Fixed Image Vocabulary. Proc.
European Conference on Computer Vision, Vol. 9, pp. 97–112, Copenhagen, Denmark, May
2002.
[Efron & Tibshirani 93] B. Efron, R. J. Tibshirani. An Introduction to the Bootstrap. Chapman & Hall, New York, 1993.
[Faloutsos & Barber+ 94] C. Faloutsos, R. Barber, M. Flickner, J. Hafner, W. Niblack,
D. Petkovic, W. Equitz. Efficient and Effective Querying by Image Content. Journalof Intelligent Information Systems, Vol. 3, No. 3/4, pp. 231–262, July 1994.
[Fei-Fei & Fergus+ 03] L. Fei-Fei, R. Fergus, P. Perona. A Bayesian Approach to Unsupervised One-Shot Learning of Object Categories. Proc. International Conference on Computer
Vision, Vol. 1, pp. 1134–1141, Nice, France, Oct. 2003.
[Fend & Siu+ 03] D. Fend, W. Siu, H. Zhang, editors. Multimedia Information Retrieval andManagement – Technological Fundamentals and Applications. Springer Verlag, 2003.
[Fergus & Perona+ 03] R. Fergus, P. Perona, A. Zissermann. Object Class Recognition by
Unsupervised Scale-Invariant Learning. Proc. Conference on Computer Vision and Pattern
Recognition, pp. 264–271, Blacksburg, VG, June 2003.
[Frey & Jojic 03] B. J. Frey, N. Jojic. Transformation-Invariant Clustering Using the EM
Algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 25,
No. 1, pp. 1–17, Jan. 2003.
[Güld & Schubert+ 03] M. Güld, H. Schubert, M. Leisten, B. Plodowski, B. Fischer, D. Keysers, T. Lehmann, B. Wein. Automatische Kategorisierung von medizinischem Bildmaterial
in einen multi-axialen mono-hierarchischen Code. Proc. Bildverarbeitung für die Medizin,
pp. 388–392, 2003.
[Gollan 03] C. Gollan. Nichtlineare Verformungsmodelle für die Bilderkennung. Diploma
thesis, Lehrstuhl für Informatik VI, RWTH Aachen, Aachen, Germany, Sept. 2003.
[Graczyk 95] C. Graczyk. Vision Texture, March 1995.
http://www-white.media.mit.edu/vismod/imagery/VisionTexture/vistex.html.
[Gu & Duncan+ 89] Z. Q. Gu, C. N. Duncan, E. Renshaw, M. A. Mugglestone, C. F. N.
Cowan, P. M. Grant. Comparison of Techniques for Measuring Cloud Texture in RemotelySensed Satellite Meteorological Image Data. Radar and Signal Processing, Vol. 136, No. 5,
pp. 236–248, Oct. 1989.
102

[Haberäcker 95] P. Haberäcker. Praxis der Digitalen Bildverarbeitung und Mustererkennung.
Carl Hanser Verlag, München, Wien, 1995.
[Haralick & Shanmugam+ 73] R. M. Haralick, B. Shanmugam, I. Dinstein. Texture Features
for Image Classification. IEEE Transaction on Systems, Man, and Cybernetics, Vol. 3,
No. 6, pp. 610–621, Nov. 1973.
[Iqbal & Aggarwal 99] Q. Iqbal, J. Aggarwal. Using Structure in Content-Based Image Retrieval. Proc. International Conference Signal and Image Processing, pp. 129–133, Nassau,
Bahamas, Oct. 1999.
[Iqbal & Aggarwal 02] Q. Iqbal, J. Aggarwal. CIRES: A System for Content-Based Retrieval in Digital Image Libraries. Proc. International Conference on Control, Automation,
Robotics and Vision, pp. 205–210, Singapore, Dec. 2002.
[Iyengar & Lippman 98] G. Iyengar, A. Lippman. Clustering Images Using Relative Entropy
for Efficient Retrieval. Proc. Workshop on Very Low bitrate Video Coding, Urbana, IL, Oct.
1998.
[Jain & Dubes 88] A. K. Jain, R. C. Dubes. Algorithms for Clustering Data. Prentice Hall,
1988.
[Jain & Murty+ 99] A. K. Jain, M. N. Murty, P. J. Flynn. Data Clustering: A Review. ACM
Computing Surveys, Vol. 31, No. 3, pp. 264–323, March 1999.
[Keysers & Dahmen+ 03] D. Keysers, J. Dahmen, H. Ney, B. Wein, T. Lehmann. Statistical
Framework for Model-Based Image Retrieval in Medical Applications. Journal of Electronic
Imaging, Vol. 12, No. 1, pp. 59–68, Jan. 2003.
[Keysers & Macherey+ 01] D. Keysers, W. Macherey, J. Dahmen, H. Ney. Learning of Variability for Invariant Statistical Pattern Recognition. Proc. European Conference on Machine Learning, Vol. 2167 of Lecture Notes in Computer Science, pp. 263–275, Freiburg,
Germany, Sept. 2001. Springer Verlag.
[Keysers & Motter+ 03] D. Keysers, M. Motter, T. Deselaers, H. Ney. Training and Recognition of Complex Scenes using a Holistic Statistical Model. Proc. DAGM 2003, Pattern
Recognition, 25th DAGM Symposium, Vol. 2781 of Lecture Notes in Computer Science, pp.
52–59, Magdeburg, Germany, Sept. 2003. Springer Verlag.
[Keysers & Och+ 02] D. Keysers, F. J. Och, H. Ney. Efficient Maximum Entropy Training for
Statistical Object Recognition. Proc. Informatiktage 2002 der Gesellschaft für Informatik,
pp. 342–345, Bad Schussenried, Germany, Nov. 2002.
[Keysers 99] D. Keysers. Texturanalyse von Farbbildern mit Gaborfiltern. Studienarbeit,
Institut für Medizinische Informatik, RWTH Aachen, Aachen, Germany, 1999.
[Keysers 00] D. Keysers. Approaches to Invariant Image Object Recognition. Diploma thesis,
Lehrstuhl für Informatik VI, RWTH Aachen, Aachen, Germany, June 2000.
[Kittler 98] J. Kittler. On Combining Classifiers. IEEE Transactions on Pattern Analysis
and Machine Intelligence, Vol. 20, No. 3, pp. 226–239, March 1998.
103

[Kölsch 03] T. Kölsch. Local Features for Image Classification. Diploma thesis, Lehrstuhl für
Informatik VI, RWTH Aachen, Aachen, Germany, Nov. 2003.
[Käster & Wendt+ 03] T. Käster, V. Wendt, G. Sagerer. Comparing Clustering Methods
for Database Categorization in Image Retrieval. Proc. DAGM 2003, Pattern Recognition,
25th DAGM Symposium, Vol. 2781 of Lecture Notes in Computer Science, pp. 228–235,
Magdeburg, Germany, Sept. 2003. Springer Verlag.
[Lehmann & Güld+ 03] T. Lehmann, M. Güld, C. Thies, B. Fischer, K. Spitzer, D. Keysers,
H. Ney, M. Kohnen, H. Schubert, B. Wein. The IRMA Project – A State of the Art Reporton Content-Based Image Retrieval in Medical Applications. Proc. Korea-Germany Joint
Workshop on Advanced Medical Image Processing, pp. 161–171, 2003.
[Linde & Buzo+ 80] Y. Linde, A. Buzo, R. Gray. An Algorithm for Vector Quantization
Design. Proc. IEEE Transactions on Communications, Vol. 28, pp. 84–95, Jan. 1980.
[Markkula & Sormunen 98] M. Markkula, E. Sormunen. Searching for Photos - Journalists’
Practices in Pictorial IR. Proc. Electronic Workshops in Computing – Challenge of Image
Retrieval, pp. 1–13, Newcastle, UK, Feb. 1998.
[Müller & Müller+ ] H. Müller, W. Müller, S. Marchand-Maillet, D. M. Squire. Strategies for
positive and negative Relevance Feedback in Image Retrieval.
[Müller & Müller+ 01] H. Müller, W. Müller, D. M. Squire, S. Marchand-Maillet, T. Pun. Performance Evaluation in Content-Based Image Retrieval: Overview and Proposals. Pattern
Recognition Letters (Special Issue on Image and Video Indexing), Vol. 22, No. 5, pp. 593–
601, 2001. H. Bunke and X. Jiang Eds.
[Nene & Nayar+ a] S. A. Nene, S. K. Nayar, H. Murase. Columbia Object Image Library(COIL-100). Technical Report 6, Department of Computer Science, Columbia University,
New York, NY, 96.
[Nene & Nayar+ b] S. A. Nene, S. K. Nayar, H. Murase. Columbia Object Image Library(COIL-20). Technical Report 5, Department of Computer Science, Columbia University,
New York, NY, 96.
[Ney 99] H. Ney. Mustererkennung und Neuronale Netze. Script to the Lecture on Pattern
Recognition and Neural Networks Held at RWTH Aachen, 1999.
[Nölle 03] M. Nölle. Distribution Distance Measures Applied to 3-D Object Recognition – A
Case Study. Proc. DAGM 2003, Pattern Recognition, 25th DAGM Symposium, Vol. 2781 of
Lecture Notes in Computer Science, pp. 84–91, Magdeburg, Germany, Sept. 2003. Springer
Verlag.
[Obdrzalek & Matas 03] S. Obdrzalek, J. Matas. Image Retrieval Using Local Compact DCTBased Representation. Proc. DAGM 2003, Pattern Recognition, 25th DAGM Symposium,
Vol. 2781 of Lecture Notes in Computer Science, pp. 490–497, Magdeburg, Germany, Sept.
2003. Springer Verlag.
[Pal & Pal 93] N. R. Pal, S. K. Pal. A Review on Image Segmentation Techniques. Pattern
Recognition, Vol. 26, No. 9, pp. 1277–1294, Nov. 1993.
104

[Palm & Keysers+ 00] C. Palm, D. Keysers, T. Lehmann, K. Spitzer. Gabor Filtering ofComplex Hue/Saturation Images for Color Texture Classification. Proc. International Conference on Computer Vision, Pattern Recognition, and Image Processing, Vol. 2, pp. 45–49,
Atlantic City, NJ, Feb. 2000.
[Paredes & Perez-Cortes+ 01] R. Paredes, J. Perez-Cortes, A. Juan, E. Vidal. Local Representations and a Direct Voting Scheme for Face Recognition. Proc. Workshop on Pattern
Recognition in Information Systems, pp. 71–79, Setúbal, Portugal, July 2001.
[Park & Jin+ 02] M. Park, J. S. Jin, L. S. Wilson. Fast Content-Based Image Retrieval Using
Quasi-Gabor Filter and Reduction of Image Feature. Proc. Southwest Symposium on Image
Analysis and Interpretation, pp. 178–182, Santa Fe, NM, April 2002.
[Petrakis & Faloutsos+ 02] E. Petrakis, C. Faloutsos, K. Ip, D. Lin. ImageMap: An Image
Indexing Method Based on Spatial Similarity. IEEE Transactions on Knowledge and Data
Engeneering, Vol. 14, No. 5, pp. 979–987, Sept. 2002.
[Porter 80] M. Porter. An Algorithm for Suffix Stripping. Morgan Kaufmann, San Francisco,CA, 1980.
[Puzicha & Rubner+ 99] J. Puzicha, Y. Rubner, C. Tomasi, J. Buhmann. Empirical Evaluation of Dissimilarity Measures for Color and Texture. Proc. International Conference on
Computer Vision, Vol. 2, pp. 1165–1173, Corfu, Greece, Sept. 1999.
[Rao 90] A. R. Rao. A Taxonomy for Texture Description and Identification. Springer Verlag,
1990.
[Reddy & Chatterji 96] B. S. Reddy, B. Chatterji. An FFT-Based Technique for Translation,
Rotation and Scale invariant Image Registration. IEEE Transactions on Image Processing,Vol. 5, Aug. 1996.
[Reinhold & Paulus+ 01] M. Reinhold, D. Paulus, H. Niemann. Appearance-Based Statistical Object Recognition by Heterogenous Background and Occlusions. Proc. DAGM 2001,
Pattern Recognition, 23rd DAGM Symposium, number 2191 in Lecture Notes in Computer
Science, pp. 254–261, Munich, Germany, Sept. 2001. Springer Verlag.
[Rubner & Tomasi+ 98] Y. Rubner, C. Tomasi, L. J. Guibas. A Metric for Distributions with
Applications to Image Databases. Proc. International Conference on Computer Vision, pp.
59–66, Bombay, India, Jan. 1998.
[Rui & Huang+ 99] Y. Rui, T. Huang, S. Chang. Image Retrieval: Current Techniques,
Promising Directions and Open Issues. Journal of Visual Communication and Image Representation, Vol. 10, No. 4, pp. 39–62, April 1999.
[Saporta & Youness 02] G. Saporta, G. Youness. Comparing Two Partitions: Some Proposals
and Experiments. Proc. Conference on Computational Statistics, Berlin, Germany, Aug.
2002.
[Saux & Boujemaa 02a] B. L. Saux, N. Boujemaa. Unsupervised Robust Clustering for Image
Database Categorization. Proc. International Conference on Pattern Recognition, Vol. 1,
pp. 259–263, Aug. 2002.
105

[Saux & Boujemaa 02b] B. L. Saux, N. Boujemaa. Unsupervised Categorization for Image
Database Overview. Proc. Recent Advances in Visual Information Systems / International
Conference on Visual Information System, Vol. 2314 of Lecture Notes in Computer Science,
pp. 163–174, Hsin-Chu, Taiwan, March 2002. Springer Verlag.
[Schael 01] M. Schael. Texture Defect Detection Using Invariant Textural Features. Proc.
DAGM 2001, Pattern Recogntion, 23rd DAGM Symposium, Lecture Notes in Computer
Science, pp. 17–24, 2001.
[Schölkopf 97] B. Schölkopf. Support Vector Learning. Oldenbourg Verlag, Munich, Germany,
1997.
[Schäuble 97] P. Schäuble. Multimedia Information Retrieval, chapter 1.6 Evaluation Issues,
pp. 22–32. Kluwer Academic Publishers, 1997.
[Schulz-Mirbach 95] H. Schulz-Mirbach. Invariant Features for Gray Scale Images. Proc.
DAGM – Symposium – ”Mustererkennung”, pp. 1–14, Sept. 1995.
[Shao & Svoboda+ 03a] H. Shao, T. Svoboda, T. Tuytelaars, L. V. Gool. HPAT Indexing for
Fast Object/Scene Recognition Based on Local Appearance. Proc. Conference on Imageand Video Retrieval, pp. 71–80, Urbana-Champaign, IL, July 2003.
[Shao & Svoboda+ 03b] H. Shao, T. Svoboda, L. van Gool. ZuBuD – Zurich Buildings
Database for Image Based Recognition. Technical Report Technical Report No. 260, Computer Vision Lab, Swiss Federal Institute of Technology, Switzerland, Zurich, Switzerland,
April 2003.
[Siggelkow & Burkhardt 97] S. Siggelkow, H. Burkhardt. Local Invariant Feature Histograms
for Texture Classification. Technical Report 3, University of Freiburg, Institute for Computer Science, 1997.
[Siggelkow & Schael 99] S. Siggelkow, M. Schael. Fast Estimation of Invariant Features. Proc.
DAGM – Symposium – Mustererkennung, Informatik aktuell, pp. 181–188, Bonn, Germany,
Sept. 1999.
[Siggelkow & Schael+ 01] S. Siggelkow, M. Schael, H. Burkhardt. SIMBA — Search IMages By Appearance. Proc. DAGM 2001, Pattern Recognition, 23rd DAGM Symposium,
Vol. 2191 of Lecture Notes in Computer Science, pp. 9–17, Munich, Germany, Sept. 2001.
Springer Verlag.
[Siggelkow 02] S. Siggelkow. Feature Histograms for Content-Based Image Retrieval. Ph.D.
thesis, University of Freiburg, Institute for Computer Science, Freiburg, Germany, 2002.
[Smeulders & Worring+ 00] A. W. M. Smeulders, M. Worring, S. Santini, A. Gupta, R. Jain.
Content-Based Image Retrieval: The End of the Early Years. IEEE Transactions on
Pattern Analysis and Machine Intelligence, Vol. 22, No. 12, pp. 1349–1380, Dec. 2000.
[Squire & Caelli 00] D. M. Squire, T. M. Caelli. Invariance Signatures: Characterizing Contours by Their Departures from Invariance. Computer Vision and Image Understanding,Vol. 77, No. 3, pp. 284–316, March 2000.
106

[Squire & Müller+ 99] D. M. Squire, W. Müller, H. Müller, J. Raki. Content-Based Queryof Image Databases, Inspirations from Text Retrieval: Inverted Files, Frequency-Based
Weights and Relevance Feedback. Proc. Scandinavian Conference on Image Analysis, pp.
143–149, Kangerlussuaq, Greenland, June 1999.
[Starik & Selding+ 03] S. Starik, Y. Selding, M. Wermann. Unsupervised Clustering of Images Using their Joint Segmentation. Technical Report 37, Leibniz Center for Research in
Computer Science, Jerusalem, Israel, June 2003.
[Subrahmanian & Tripathi 98] V. Subrahmanian, S. Tripathi, editors. Multimedia Information Systems, chapter 5, Image Databases. Kluwer, July 1998.
[Swain & Ballard 91] M. J. Swain, D. H. Ballard. Color Indexing. International Journal ofComputer Vision, Vol. 7, No. 1, pp. 11–32, Nov. 1991.
[Tamura & Mori+ 78] H. Tamura, S. Mori, T. Yamawaki. Textural Features Corresponding
to Visual Perception. IEEE Transaction on Systems, Man, and Cybernetcs, Vol. SMC-8,
No. 6, pp. 460–472, June 1978.
[Terhorst 03] B. Terhorst. Texturanalyse zur globalen Bildinhaltsbeschreibung radiologischer Aufnahmen. Research project, RWTH Aachen, Institut für Medizinische Informatik,
Aachen, Germany, June 2003.
[Wang & Li+ 01] J. Z. Wang, J. Li, G. Wiederhold. SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries. IEEE Transactions on Pattern Analysis andMachine Intelligence, Vol. 23, No. 9, pp. 947–963, Sept. 2001.
[Weber 00] M. Weber. Unsupervised Learning of Models for Object Recognition. Ph.D. thesis,
California Institute of Technology, Pasadena, CA, 2000.
[Zhang & Wong+ 00] D. Zhang, A. Wong, M. Indrawan, G. Lu. Content-Based Image Retrieval Using Gabor Texture Features. Proc. Pacific-Rim Conference on Multimedia, pp.
392–395, Sydney, Australia, Dec. 2000.
[Zucker & Terzopoulos 80] S. W. Zucker, D. Terzopoulos.
Finding Structure in CoOccurrence Matrices for Texture Analysis. Computer Graphics and Image Processing,Vol. 12, pp. 286–308, Dec. 1980.

107

Indexχ2 , 36
Bhattacharyya, 37
cross-bin, 37
earth movers, 38
Euclidean, 36, 38, 40, 44
Mahalanobis, 44
Manhattan, 36
matrix, 43
Minkowski, 36
quadratic form, 38
tangent, 40
time warp, 38
dynamic programming, 39

L1 distance, 36
P R-area, 60
P (1), P (20), P (50), P (NR ), 60
P (P = R), 60
R (P = 0.5), R (100), 60
χ2 distance, 36] 60
Rank1 , Rank,
rel-operator, 23
k-means, 5affine transformation, 20alignment, 39
Bhattacharyya distance, 37
bin-by-bin comparison measure, 35–37
BlobWorld, 11, 14, 32, 43

earth movers distance, 38
entropy, 29
Euclideandistance, 36, 40
motion, 20

CalTech database, 54
circular moran autocorrelation function, 30
CIRES, 12classification, 7, 14, 49
cloogluster, 46
clustering, 46
co-occurrence matrix, 29
coarseness, 27, 29
COIL database, 57
color histogram, 18
content-based image retrieval, 3
contingency table, 78
contrast, 28
convolution theorem, 26
Corel database, 51
correlation, 61
cross-bin comparison measure, 37

fidelity, 37
Flexible Image Retrieval Engine, 45
Fourier Mellin transformation, 24
fractal dimension, 29
fuzzy histogram, 18
Gaborfeature histogram, 27
features, 25
filter, 25
GIFT, 12
global texture descriptor, 29
Googledatabase, 56
image search, 5differential approach, 20
directionality, 28
discriminant function, 8
distance
L1 , 36

histogram, 18
color, 18
comparison measures, 35–40
fuzzy, 18108

Gabor features, 27intersection, 36
invariant feature, 23
local feature, 31
Tamura feature, 29
human perception, 1
Hungarian algorithm, 43

principal component analysis, PCA, 32
QBIC, 11, 29
quadratic form, 38
query-byexample, 3sketch, 3text, 3image
clustering, 5comparison measures, 40–41
distortion model, 41
retrieval, 3integrated region matching, IRM, 43
invariant feature, 19
differential approach, 20
histogram, 23
integral approach, 20
normalization, 20
vector, 24
IRMA, 12
database, 53

Rand index, 78
regionalignment, 44
based features, 32
description, 32
matching
integrated, 43
with quantization, 43
relational function, 23
relativebin deviation, 36
deviation, 36
relevance feedback, 3, 45
negative, 3, 45
positive, 3, 45Jensen Shannon divergence, 37

SIMBA, 12
SIMPLIcity, 12, 32, 43
spatial gray-level difference statistics, 29

Karhunen-Loève transformation, 32
kernelmonomial, 23
relational, 23
Kronecker Delta, 18
Kullback-Leibler divergence, 37

Tamura feature, 27
coarseness, 27
contrast, 28
directionality, 28
tangent distance, 40
test data, 7time warp distance, 38
train data, 7

LBG-clustering, 6, 32
local features, 30
histogram, 31
log-polar coordinates, 25
Mahalanobis distance, 44Manhattan distance, 36
Minkowski distance, 36
monomial, 22Monte Carlo integration, 22
MPEG-7 test set, 56
multidimensional scaling, 34

UW database, 54
VIPER, 12
WANG database, 51
Zurich Building database, 55

nearest neighbor, 8
NN-ER, 60
normalization, 19109