Shape Analysis and Retrieval of Multimedia Objects

by Safar, Maytham H.; Shahabi, Cyrus

• ISBN13: 9781402072529
• ISBN10: 140207252X
• Format: Hardcover
• Copyright: 2002-11-01
• Publisher: Kluwer Academic Pub

Summary

With the explosive growth of Multimedia Applications, the ability to index/retrieve multimedia objects in an efficient way is challenging to both researchers and practitioners. A major data type stored and managed by these applications is the representation of two dimensional (2D) objects. Objects contain many features (e.g., color, texture, and shape) that have meaningful semantics. From those features, shape is an important feature that conforms with the way human beings interpret and interact with the real world objects. The shape representation of objects can therefore be used for their indexing, retrieval and as similarity measure. The object databases can be queried and searched for different purposes. For example, a CAD application for manufacturing industrial parts might intend to reduce the cost of building new industrial parts by searching for reusable existing parts in a database. Regarding an alternative trademark registry application, one might need to ensure that a new registered trademark is sufficiently distinctive from the existing marks by searching the database. Therefore, one of the important functionalities required by all these applications is the capability to find objects in a database that match a given object. Traditional books on computer vision and informational retrieval are too general, and they do not provide advanced or specific information regarding shape analysis and recognition. Shape Analysis and Retrieval of Multimedia Objects provides a comprehensive survey of the most advanced and powerful shape retrieval techniques used in practice today. In addition, this monograph addresses key methodological issues for evaluation of the shape retrieval methods. Shape Analysis and Retrieval of Multimedia Objects is designed to meet the needs of practitioners and researchers in industry, and graduate-level students in Computer Science.

Table of Contents

List of Figures	ix
List of Tables	xiii
Preface	xv
Outline	xvi
Acknowledgements	xvii
Contributing Authors	xxi
Introduction	xxiii
Shape Representation	xxvi
Why MBC?	xxvi
MBC for Similarity Queries	xxvii
MBC for Spatial Queries	xxviii
Part I Image Shape Representation
Image Description Techniques	3	(6)
Shape Representation Methods	4	(5)
Image Similarity Measures	9	(4)
Similarity Measures	9	(4)
Image Shape Features	13	(6)
MBC Features	15	(4)
Alternative Image Description Techniques	19	(12)
Fourier Descriptors Method	20	(1)
Grid Based Method	21	(3)
Rotation Normalization	22	(1)
Scale Normalization	23	(1)
Delaunay Triangulation Method	24	(1)
MBC-TPVAS Method	25	(6)
Part II Query Types and Index Structures
Shape Similarity Matching Queries	31	(12)
2D Similarity Queries	32	(3)
Full Match	33	(1)
Approximate Match	33	(1)
Match with a Specified Transformation	34	(1)
Match with Unspecified Transformation	35	(1)
Partial Match	35	(1)
2D Similarity Queries with MBC	35	(8)
Exact Match Shape Retrieval - EM	36	(1)
RST Shape Retrieval	37	(3)
Similarity Shape Retrieval - SIM	40	(3)
Spatial Queries	43	(20)
Spatial Queries with MBC	43	(2)
Topological Relations	45	(12)
Topological Relations using MBC	47	(4)
Special Cases of Topological Relations	51	(1)
MBCs of objects overlap	52	(4)
MBCs of objects are equal	56	(1)
Direction Relations	57	(6)
Cone-Based Direction Relations	57	(6)
Multidimensional Index Structures	63	(18)
Point Access Methods (PAMs)	65	(1)
Spatial Access Methods (SAMs)	65	(5)
The Tree-Based Indexing Methods	66	(1)
Index Evaluation Parameters	67	(3)
MBC Index Structures	70	(11)
INaive Index Structure	72	(1)
Itpas Index Structure	73	(2)
Ivas Index Structure	75	(1)
Itpvas Index Structure	76	(5)
Part III Selected Topics
Observations on MBC and MBR Approaches	81	(4)
Sphere Index for MBCs	81	(1)
Complex Queries	82	(3)
Evaluation Framework	85	(10)
Accuracy	86	(1)
Cost	87	(1)
Robustness to Noise	87	(1)
Robustness to Boundary Points Selection	88	(3)
Support of Different Query Types	91	(3)
Human Perception	94	(1)
MBC Optimization Techniques	95	(10)
Optimized MBC Computation Algorithm	95	(4)
Phase Values Trends of Fourier Transform	99	(6)
Appendix	105	(12)
Appendix: Cost Analysis of Index Structures	106	(1)
MBC Algorithm	106	(1)
Index Cost Analysis	107	(2)
Appendix: Spatial Relations with MBR	109	(1)
Topological Relations Using MBRs	109	(1)
Direction Relations Using MBRs	110	(4)
Appendix: Computation and Storage Cost Analysis	114	(1)
Grid Based Method	114	(1)
Fourier Descriptors Method	114	(1)
Delaunay Triangulation Method	115	(1)
MBC-TPVAS Method	115	(2)
Bibliography	117	(10)
Topic Index	127