| T1 | 9.00-13.00 | Peter Stanchev | Image Data Models |
| T2 | 9.00-13.00 | Remco Veltkamp | Shape Matching |
| T3 | 14.00-18.00 | Hanan Samet | Spatial Databases |
| T4 | 14.00-18.00 | Theo Gevers, Alberto del Bimbo, Arnold Smeulders | Image Search Engines |
An Image Data Model is a type of image data abstraction that is used to provide a conceptual image representation. It is a set of concepts that can be used to describe the structure of an image. The process of image description consists of extracting the global image characteristics, recognising the image-objects and assigning a semantic to these objects. Approaches to image data modeling can be categorised based on the views of image data that the specific model supports. There is a lack of standard model for representing the semantic richness of an image. In this tutorial we analyse the existing tools and approaches to image data modeling. The image data can be treated as physical image representation and their meaning as a logical image representation. The logical representation includes methods for describing the image and image-objects characteristics and the relationships among the image objects. Several image data models such as: VIMSYS image data model, model where images are presented as four plane layers, EMIR2- an extended model for image representation and retrieval, AIR - an adaptive image retrieval model are analysed. Detailed technical description of the MPEG-4 standard and MPEG-7 objectives will be also presented.
The purpose of this tutorial is to present methods for describing the tools that summarised the image contents. For each method an algorithm describing the method, a sample application of the method over example images and a program realisation of the method will be shown.
Image data models (VIMSYS, EMIR2, AIR). String language for pattern description (introduction to formal languages, grammars for two or three dimensional pattern description, fuzzy grammars). Special high-dimensional pattern grammars (tree grammars, web grammars, and attributed relational graph). Image segmentation (line detector, multi-gray level thresholding, morphological segmentation, multispectral image segmentation, feature based methods, model based methods (fractal, statistics), edge detection, thinning, skeletonizing). Dimension analysis (centroid, circularity, clustering, compactness, maximum axis, minimum axis, moments, and perimeter). Colour analysis (histogram of intensity of the pixels colour, average red, green, and blue, overall average colour). Texture analysis (coarseness, contrast, directionality, regularity and roughness). Spatial analysis (spatial oriented graph, 2D string, topological set of relations, vector set of relations, metric set of relations). Detailed technical description of the MPEG-4 standard and MPEG-7 objectives
Images are becoming an essential part of the information systems and multimedia applications. The image data model is one of the main issues in the design and development of any image database management system. The data model should be extensible and have the expressive power to present the structure and contents of the image, their objects and the relationships among them. The design of an appropriate image data model will ensure smooth navigation among the images in an image database system. The complexity of the model arises because images are richer in information than text, and because images can be interpreted differently, according to the human perception of the application domain.
Computer science students, researchers, people willing to build his own image database.
Peter L. Stanchev, Ph.D., D.Sc.
Institute of Mathematics and Computer Science, Bulgarian Academy of Sciences
Acad. G. Bonchev St. 8, 1113 Sofia, Bulgaria
E-mail: stanchev@bas.bg
The tutorial will open with an overview of approaches of shape matching, such as tree pruning, generalized Hough transform, geometric hashing, Fourier descriptors, and neural networks. The emphasis of the tutorial is on shape matching from a computational geometry point of view. Computational geometry is the subarea of algorithms design that deals with the design and analysis of algorithms for geometric problems involving objects like points, lines, polygons, and polyhedra. The standard approach taken in computational geometry is the development of exact, provably good and efficient solutions to geometric problems.
We will pay attention to properties of matching techniques with respect to noise and occlusion, the transformation group, and the dissimilarity measure, and efficiency of algorithms.
Many multimedia systems make use of a large collection of images. Retrieving images from a large database by their content, as opposed to external features, has become an important operation. Users are often interested in retrieval by object shape. However, retrieval by shape is still considered one of the most difficult aspects of content-based search. There are close connections between computational geometry and visual information systems, as geometric reasoning is ubiquitous in pattern recognition and shape processing.
The tutorial will open with an overview of approaches of shape matching, such as tree pruning, generalized Hough transform, geometric hashing, alignment method, statistics, deformable templates, relaxation labeling, and Fourier descriptors.
Then we deal with specific techniques for matching of sets of points (1-1 correspondence, n-m matching), curves (open, closed, parameterized, polygonal, and regions (convex, non-convex). We will treat shape representations, dissimilarity measures (Hausdorff, Frechet, area of overlap, and other), and matching algorithms. The focus lies on the provable behavior of the algorithms, and efficiency in terms of time and storage.
We consider different versions of the matching problem: computation of the dissimilarity, deciding if there is a transformation that gives a dissimilarity smaller than a given bound, and finding the transformation that gives the smallest dissimilarity.
The primary audience are people from the field of visual information systems whose research/work involves shape matching, but who are not experts in computational geometry. The tutorial will not assume previous knowledge of computational geometry, but it will assume some acquaintance with fundamental topics in computer science, and in particular in algorithms and data structures.
Possible secondary audience are those who are interested to hear about the systematic study of geometric algorithms, in general and in relation to shape matching.
Remco Veltkamp
Dept. Computer Science, Utrecht University
P.O.Box 80.089, 3508 TB, Utrecht, The Netherlands
email: Remco.Veltkamp@cs.uu.nl
Remco Veltkamp obtained his Ph.D. in 1992 from Erasmus University Rotterdam. >From 1992 he was postdoc at both CWI Amsterdam and the Technical University of Eindhoven. Since 1995 he is assistant professor at Utrecht University in the Computational Geometry group of Prof. Mark Overmars.
His Ph.D. dissertation has been published as a book, and he has written over 30 refereed journal and conference papers on shape matching, shape reconstruction, geometric constraint management, and variational curve and surface design. He was editor of the Eurographics'95 State-of-the-Art proceedings, and chairman and program committee member of various Eurographics Workshops on Programming Paradigms in Graphics.
The work on computational shape processing, such as shape matching and reconstruction, geometric constraints, and curve and surface modeling, is focused on algorithmic design, and is always experimentally verified by software implementations. He is currently the leader of projects on graphics programming, shape matching, and shape indexing, is advisor of projects on shape reconstruction and facial animation, and participates in the ESPRIT IV LTR projects CGAL and GALIA. He has recently given a tutorial on computational geometry in robotics (ICRA'98).
The ability to deal with spatial data is becoming increasingly important in applications in geographic information systems, computer vision, computer graphics, computer vision, image processing, solid modeling, robotics, and cartography. This manifests itself in the need to incorporate this data in existing database management systems. This incorporation must result in the coexistence of the spatial data with the non-spatial data. The result is termed a spatial database. Spatial databases must deal with points, lines, rectangles, regions, surfaces, volumes, and other geometric data, as well as time and non-geometric data (known as attribute data). The implementation of spatial databases involves many issues including a choice among a number of different representations for the underlying data, as well as the types of queries to be supported, In this tutorial we review some of the most recent representations and the type of operations that they are designed to support. This is aided by a spatial data applet which can be found here We also discuss methods of integrating spatial and non-spatial data in conventional database management systems, as well as examine some existing spatial database systems. Many of our examples will be drawn from a family of hierarchical data structures that are based on the principle of divide-and-conquer. The key advantage of these representations is that they provide a way to index into space. In fact, they are little more than multidimensional sorts. They are compact and depending on the nature of the spatial data they save space as well as time and also facilitate operations such as search. A live demonstration will be given of a spatial database management system that employs these concepts.
1. Introduction: Sample queries, Spatial Indexing, Sorting approach, Minimum bounding rectangles, Disjoint cells, Uniform grid, Location-based queries vs feature-based queries, Quadtrees vs pyramids, Space ordering methods.
2. What is a GIS: Typical GIS queries, Typical GIS operations, Examples of GIS, The vector GIS,. The raster GIS, History of GIS.
3. Representing spatial data: Points, Lines, Rectangles, Regions, Surfaces, Volumes, Temporal data.
4. Disk-based file structures for spatial data: R-trees,Grid files, EXCELL.
5. Database issues: Models of database management systems (DBMS), Object-oriented spatial databases.
6. Integration of spatial and non-spatial databases: SYSTEM R, GRAL, GEOQL, PSQL, DASDBS, SAND-1, SAND-2.
7. Operations: Set operations, Spatial selection (windowing), Spatial range queries, Spatial join, Neighbor finding, Nearest object location, Connected component labeling.
8. Example system
9. Future trends
Hanan Samet is a Professor of Computer Science at the University of Maryland, College Park. He is a member of the Computer Vision Laboratory of the Center for Automation Research and also has an appointment in the University of Maryland Institute for Advanced Computer Studies. At the Computer Vision Laboratory he leads a number of research projects on the use of hierarchical data structures for geographic information systems. His research group has developed the QUILT system which is a GIS based on hierarchical spatial data structures such as quadtrees and octree, and the SAND system which integrates spatial and non-spatial data. He received his Ph.D. in Computer Science from Stanford University in 1975. During that time he was a Research Assistant at the Stanford Artificial Intelligence Project. His doctoral dissertation dealt with proving the correctness of translations of LISP programs. Between 1978 and 1980 he was also affiliated with the Information Sciences Institute at the University of Southern California where he worked on an extension of this research. He spent part of 1982 at the National University of Singapore, and part of 1989 at the Basic Research Laboratory of NTT in Tokyo, Japan. In 1992 he was a visiting professor at the University of Pavia in Italy. He has consulted for a number of industrial and government organizations and has conducted numerous short courses and seminars on geographic information systems, spatial data structures, LISP, and artificial intelligence.
He has written over 125 technical publications on the subjects of hierarchical spatial data structures, geographic information systems, image processing, computer graphics, programming languages, artificial intelligence, robotics, and data base management systems. He is considered as an authority on the use and design of hierarchical spatial data structures such as the quadtree for geographic information systems, image processing, and computer graphics. He is an Area Editor of "Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing". He is on the Editorial Board of "Computer Vision, Graphics, and Image Processing: Image Understanding", "Journal of Visual Languages", "Pattern Recognition", "GeoInformatica", "Transactions on GIS", and "Journal of Spatial Cognition and Computation". He is the author of the two books "The Design and Analysis of Spatial Data Structures" and "Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS" published by Addison-Wesley, Reading, MA, 1990. He is a Fellow of the ACM, IEEE, and the IAPR (International Association of Pattern Recognition).
Very large digital image archives have been created and used in a number of applications including archives of images of postal stamps, textile patterns, museum objects, trademarks and logos, and views from everyday life as it appears in home videos and consumer photography. Moreover, with the growth and popularity of the World Wide Web, a tremendous amount of visual information is made accessible publicly. As a consequence, there is a growing demand for search methods retrieving pictorial entities from large image archives. In this tutorial we will give a survey of the most recent developments on image search engines focusing on the following topics:
Color Features: Color provides powerful information for image retrieval. A color survey is given consisting of an introduction to standard color models as well as an overview of best recent work on color invariance. Further, we analyze which color models to use under which imaging conditions. This is useful for applications where no constraints can be imposed on the imaging process and also for applications where sensor parameters are user controlled.
Searching: In the field of pattern recognition, several methods have been proposed that improve classification automatically through experience such as artificial neural networks, decision tree learning, Bayesian learning and k-nearest neighbor classifiers. A survey is given on the most recent developments regarding the use of these classification techniques for image classification.
Indexing: Various methods have been developed for indexing the stored images so that the image retrieval methods can perform efficiently at some additional costs in memory, such as a k-d tree, R-tree or a X-tree, for example. A survey is given of indexing methods in the context of image retrieval.
Visualization and interaction of information content Visualization of the feature matching results is very important and will be addressed. Further, methods are discussed to localize object in images.
Relevance feedback: From the user feed-back giving negative/positive answers, methods can automatically learn which image features are more important. Methods and systems are discussed using relevance feedback for image retrieval.
Survey of image retrieval system: Finally, a survey of existing image retrieval systems is given. The systems are compared with respect to above discussed topics.
Applications: Application are presented in video technology and the search for industrial objects on the basis of pictorial specification.
Engineers and scientists handling large multimedia and video digital databases. Web searching for multimedia information content. Anyone interested in query by example.
Arnold W.M. Smeulders is professor of Computer Science on Multi Media Information Systems. His interest is in image databases and intelligent interactive image analysis, as well as system engineering aspects of image processing. He is director of the computer science research institute and he leads the Intelligent Sensory Information Systems research group at the University of Amsterdam. The 25 person group conducts research for the national science program and industry in image and multimedia databases and computer vision. He is chairman of the Visual Information Systems conference in Amsterdam and program chairman of the IEEE Multimedia conference in Florence. He leads the national initiative for multimedia and is chairman of the Technical Committee on multimedia information of the International Association for Pattern Recognition. He has authored more than 150 papers.
Theo Gevers is assistant professor of Computer Science at the University of Amsterdam, The Netherlands. His main research interests are in the fundamentals of image database system design, image retrieval by content, theoretical foundation of geometric and photometric invariants and color image processing. He has led several (inter)national projects and acts as a reviewer. He is co-organizer of the First International Workshop on Image Databases and Multi Media Search and the Third International Conference on Visual Information Systems. Theo Gevers is a member of the national program steering activities between industry and university. He has published over 30 papers on color image processing, image retrieval and image database design. He has provided a comprehensive image search system available at http://www.wins.uva.nl/research/isis/zomax/.