Image Database Design Based on9D-SPA Representation for Spatial RelationsPo-Whei Huang and Chu-Hui LeeAbstract—Spatial relationships between objects are important features for designing a content-based image retrieval system. In thispaper, we propose a new scheme, called 9D-SPA representation, for encoding the spatial relations in an image. With this representation,important functions of intelligent image database systems such as visualization, browsing, spatial reasoning, iconic indexing, andsimilarity retrieval can be easily achieved. The capability of discriminating images based on 9D-SPA representation is much morepowerful than any spatial representation method based on Minimum Bounding Rectangles or centroids of objects. The similaritymeasures using 9D-SPA representation provide a wide range of fuzzy matching capability in similarity retrieval to meet different user’srequirements. Experimental results showed that our system is very effective in terms of recall and precision. In addition, the 9D-SPArepresentation can be incorporated into a two-level index structure to help reduce the search space of each query processing. Theexperimental results also demonstrated that, on average, only 0.1254 percent  1.6829 percent of symbolic pictures (depending onvarious degrees of similarity) were accessed per query in an image database containing 50,000 symbolic pictures.Index Terms—Image database, spatial relations, similarity retrieval, 9D-SPA, visualization.æ1INTRODUCTIONApictorial database plays an important role in manyapplications including geographical information sys-tems, computer aided design, office automation, medicalimage archiving, and trademark picture registration. Thetraditional approach to image database design is to usetextual descriptions to annotate images and then storeannotations in a text-based data base management system.Searching for desired images is equivalent to searching forthe associated annotations. This approach is too tedious andlabor-intensive. Moreover, the key words used in annota-tions or query descriptions are too subjective and maybecome inadequate, especially when the number of imagesin the database increase tremendously.Content-based image retrieval (CBIR) is the current trendof designing image database systems as opposed to text-based image retrieval [7], [11], [14], [18], [23], [24], [25], [27].The features used in content-based image retrieval can beroughly divided into two categories: the low-level visualfeatures (such as color, texture, and shape) and the high-level features (such as pairwise spatial relationshipsbetween objects). Some examples of content-based imageretrieval systems are QBIC [8], Virage [1], Retrieval Ware[29], VisualSEEK [26], WaveGuide [17], and Photobook [21].They allow users to retrieve similar pictures from a largeimage database based on low-level visual features. On theother hand, there is also a large group of researchersemphasizing image retrieval based on spatial relationshipsbetween objects [3], [4], [5], [10], [15], [16], [20], [22], [28]. Inthis paper, we only concentrate on iconic picture retrievalbased on spatial relations where the number of icons in thedatabase are fixed and each object in a picture must matchan icon.The method of representing images is one of the majorconcerns in designing an image database system. Therepresentation method for an image should capture theknowledge about the image’s content as much as possible.One way of representing an image is to construct asymbolic picture for that image which in turn is encodedinto a 2D-string [5]. The 2D string representation methodopened up a new approach to spatial reasoning, pictureindexing, and similarity retrieval. There are many follow-up research works based on the concept of 2D string suchas 2D C-string [15], [16], and 2D Cþ-string [9].An ideal representation method for symbolic picturesshould provide image database systems with many im-portant functions such as similarity retrieval, visualization,browsing, spatial reasoning, and picture indexing. In thispaper, we propose a new scheme for encoding spatialrelations called 9-Direction SPanning Area (9D-SPA) repre-sentation method. Using the 9D-SPA representation, we caneasily accomplish the following system design goals:1. Iconic pictures can be easily reconstructed from9D-SPA representations for visualization.2. Flexibility and accuracy in similarity retrieval can beachieved at the same time through a set of coarse-to-fine similarity measures.3. The 9D-SPA representation can be incorporated intoan efficient index structure so that the search spacewill be restricted to a relatively small portion of thedatabase for improving retrieval efficiency.1486 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 16, NO. 12, DECEMBER 2004. P.W. Huang is with the Department of Computer Science, NationalChung-Hsing University, Taichung 40227, Taiwan, Republic of China.E-mail: [email protected].. C.H. Lee is with the Department of Information Management, ChaoyangUniversity of Technology, 168 Gifeng E. Rd., Wufeng, Taichung County,Taiwan, Republic of China. E-mail: [email protected] received 20 June 2002; revised 18 Feb. 2004; accepted 18 Feb.2004.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number 116826.1041-4347/04/$20.00 ß 2004 IEEE Published by the IEEE Computer SocietyThe remainder of this paper is organized as follows: InSection 2, previous research works about knowledgerepresentations for spatial relations are discussed. InSection 3, the 9D-SPA representation is introduced. InSection 4, we propose a visualization method for 9D-SPArepresentation. The algorithm of decoding the 9D-SPArepresentation for picture reconstruction is also presentedin this section. Spatial reasoning and interpretation basedon a 9D-SPA representation are presented in Section 5. InSection 6, we define a set of similarity measures for fuzzymatching. We also introduce an index structure based on9D-SPA representation to facilitate image retrieval. Thesimilarity retrieval algorithm is presented in this samesection. The experimental results for demonstrating theefficiency and effectiveness of our approach are presentedin Section 7. Finally, conclusions are given in the lastsection.2OVERVIEW OF SPATIAL KNOWLEDGEREPRESENTATIONBinary spatial relationships between objects have beenidentified as one of the mo st important features