Exploratory Image Databases: Content-Based Retrieval Academic Press Series in Communications, Networking, and Multimedia EDITOR-IN-CHIEF Jerry D. Gibson Southern Methodist University This series has been established to bring together a variety of publications that represent the latest in cutting-edge research, theory, and applications of modern communication systems. All traditional and modern aspects of communications as well as all methods of computer communications are to be included. The se- ries will include professional handbooks, books on communication methods and standards, and research books for engineers and managers in the world-wide com- munications industry. Books in the Series: Handbook of Image and Video Processing, A1 Bovik, editor The E-Commerce Book, Second Edition, Steffano Korper and Juanita Ellis Multimedia Communications, Jerry Gibson, editor Nonlinear Image Processing, Sanjit K. Mitra and Giovanni L. Sicuranza, editors Introduction to Multimedia Systems, Guarav Bhatnager, Shika Mehta, and Sugata Mitra Exploratory Image Databases, Simone Santini Exploratory Image Database S: Content-Based Retrieval SIM ONE SANTINI University of California La Jolla, California @ ACADEMIC PRESS A Harcourt Science and Technology Company SAN DIEGO/SAN FRANCISCO/ NEW YORK / BOSTON / LONDON / SYDNEY/ TOKYO This book is printed on acid-free paper. (~ Copyright (cid:14)9 2001 by Academic Press All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Requests for permission to make copies of any part of the work should be mailed to the following address: Permissions Department, Harcourt, Inc., 6277 Sea Harbor Drive, Orlando, Florida, 32887-6777. ACADEMIC PRESS A Harcourt Science and Technology Company 525 B Street, Suite 1900, San Diego, CA 92101-4495, USA http://www.academicpress.com Academic Press Harcourt Place, 32 Jamestown Road, London, NWl 7BY, UK Library of Congress Catalog Number: 2001088197 ISBN: 0-12-619261-8 Printed in the United States of America 01 02 03 04 05HP98765432 1 Per ogni problema complesso c'~ una soluzione semplice, ed ~ sbagliata (For every complex problem there is a simple solution, and it's wrong) Umberto Eco, I1 Pendolo di Foucault This Page Intentionally Left Blank Contents Preface xiii Acknowledgments xvii Part I" e.v ~xpxrl fly 0 2toyo~; (Math Came Later) An Eerie Sense of Deja Vu 3 1.1 Characteristics of Visual Information Systems 5 1.2 Query by Example and the Semantic Gap 7 1.3 What Do Users Really Need? 12 1.3.1 User Interaction with Image Archives 17 The Mysterious Case of the Disappearing Semantics 25 2.1 Signs and Meanings 27 2.2 Can Images Lie? 32 2.2.1 What Kind of Signs are Pictures? 39 2.2.2 The Association Between Text and Pictures 41 2.3 The Three Modalities of Signification 46 2.3.1 Linguistic Modality 47 2.3.2 Closed World Modality 48 2.3.3 The User Modality 50 2.4 The Quest for Formalization 51 How You Can Know You Are Right 55 3.1 The Role of Evaluation 56 3.2 Inadequacy of Traditional Evaluation Models 61 3.3 Basic Techniques 63 3.3.1 Measurements of Trial Results 64 3.3.2 Does the Difference Make a Difference? 72 3.4 Contextual Evaluation 91 3.5 Noncontextual Evaluation 96 3.6 Additional Pointers 100 vii viii CONTENTS Part I1: De Re Visiva Principia Geometrica 4 Similarity 105 4.1 Preattentive Similarity 107 4.2 Psychological Models of Similarity 109 4.2.1 The Metric Axioms 110 4.2.2 Alternatives to the Distance Axioms 120 4.2.3 The Feature Contrast Model 123 4.3 Fuzzy Set-Theoretic Similarity 12 7 4.3.1 Fuzzy Features Contrast Model 128 4.3.2 Feature Dependence 136 4.4 Consideration of Geometric Distances 141 4.4.1 Metric and Similarity Structures 143 4.4.2 Variable Metric Structures 149 4.4.3 Distance Algebras 151 4.4.4 Similarity Algebras 156 4.4.5 Algebras for Variable Metric Structures 159 Systems with Limited Ontologies 165 5.1 Features 168 5.2 Color 170 5.2.1 Color Representation 172 5.2.2 The Perception of Colors 181 5.3 Texture 184 5.3.1 The Problem of Scale 185 5.3.2 Statistical Texture Features 188 5.3.3 Gabor Decomposition 190 5.3.4 Quadrature Mirror Filters 191 5.4 Histograms 193 5.4.1 Global Histograms 194 5.4.2 Discriminating Power of Histograms 215 5.4.3 Spatial Histograms 218 5.5 Segmentation 223 5.5.1 Clustering Methods 224 5.5.2 Region Merging and Region Splitting 231 5.5.3 Edge Flow 236 5.6 Shape Description and Similarity 238 5.6.1 The Contents of a Region 239 5.6.2 Region Shape 240 5.6.3 Spatial Relations 246 5.7 Similarity of Region Images 260 CONTENTS ix Systems with General Ontologies 263 6.1 Bases, Frames, and Transforms 265 6.1.1 Periodic Functions and the Fourier Transform 269 6.1.2 Frames 270 6.2 Group Representations and Image Transforms 275 6.2.1 Boundedness Modulo a Subgroup 280 6.2.2 Affine Wavelets 283 6.2.3 Other Wavelet-Generating Groups 289 6.2.4 Discrete Subgroups and Transforms 297 6.2.5 Quadrature Mirror Filters 304 6.3 Measuring the Distance 311 6.3.1 Point Distances 313 6.3.2 General Distances 314 6.3.3 Natural Distances 316 6.3.4 Invariance Properties 320 6.4 Approximate Representations 324 6.4.1 Vector Quantization 324 6.4.2 Quality of Representation 327 6.4.3 Approximate Distance Computation 329 Writing About Images 339 7.1 Automatic Text Analysis 341 7.1.1 Single Term Indexing 342 7.1.2 Term Weighting 347 7.1.3 The Vector Space Model 351 7.2 Latent Semantics 352 7.3 Relevance Feedback 360 7.3.1 Rocchio Algorithm 361 7.4 Evaluation 363 7.4.1 Precision and Recall 365 7.4.2 Other Models 366 7.5 The Relation Between Text and Images 370 7.5.1 Some Truisms on Web Structures 3 70 7.5.2 That is Good, but Where are the Images? 374 7.6 Image-Text Integration 3 77 7.6.1 Visual Dictionary 3 78 7.6.2 Mutual Influence 3 79 Part II1: e cerca e truova e quello officio adempie Algebra and the Modern Query 385 8.1 A First Model of Image Data 387 8.1.1 A Quick Review of Relational Algebra 387