Content-based Image Retrieval (CBIR) System

Content-based Image Retrieval (CBIR) System Chapter 1. Introduction Nowadays, in the most of areas it is necessary to work with large amounts of growing visual and multimedia data, at the same time, the number of image and video files on the web is quite big and is still rising very rapidly. Searching through this data is absolutely vital. So, there is a high demand on the tools for image retrieving, which are based on visual information, rather than simple text-based queries. Content-based Image Retrieval (CBIR) consists of retrieving the most visually similar images to a given query image from a database or group of image files. It is a quite useful thing in a lot of areas such as Photography which may involve image search from the large digital photo galleries; Medicine it is used to assist in diagnosis. In most of diseases, their visual characteristics carry diagnostic information and visually similar images correspond to the same disease category. The output of a CBIR system can help to make a decision (Tahmoush, 2007); Military detection of e nemy soldiers or vehicles from screen photographs; Crime prevention it helps police in suspicious peoples identification from large image databases and in image retrieval of crime scene photos (Wen, 2005); Geography frequently used in Geographical information systems (GIS) (Hafiane, 2006) and many others. CBIR has been a subject of intense research over the last 15 years. It is one of the most difficult research areas in multimedia computing and information retrieval. During the research history many different image matching, indexing and retrieval algorithms have been tried. Practice shows that user queries described by visual information are more effective and more precisely meet user needs, than standard text search queries. It is because visual information is closer to the humans perception of the world. 1.1 CBIR Systems Many CBIR systems and tools have been developed to make queries based on visual content. During the 90-ies several notable commercial systems were introduced. IBM developed Query By Image Content (QBIC) system, which lets user to make queries of large image databases based on visual image content properties such as Example images; User-constructed sketches and drawings; Selected color and texture patterns. (Flickner, 1995) Soon after that â€Å"Virage Image Search Engine† of Virage Inc. was developed, which provides an open framework for building systems that explicitly manages image assets by directly representing their visual attributes. (Bach, 1996) Several online content-based web search engines can also be mentioned. â€Å"WebSEEk† developed by Image and Advanced Television Lab, Columbia University. It allows making queries by example and by desired color composition. â€Å"Chabot†, Developed by Department of Computer Science, University of California, which allows to search by colors, but offers limited options such as choosing one dominant color. (Veltkamp, 2002) Global Memory Net (GMNet) was launched for public access in late June 2006. It is a digital library of cultural, historical, and heritage image collections. Among other text-based searching types this web library has a possibility to search by image content. It has two basic options for content based searching. Search by example image, based on its color and shape and by user drawing. For CBIR, GMNet uses SIMPLIcity developed by Prof. James Z. Wang of Penn State University. (Chen 2006) Different CBIR systems use different types of user queries. Typically tools for the content-based image retrieval consist of query statement and a result presentation; this query can be done by providing an example image a sketch, or by choosing desired colors for the image. Results are presented by the top several similar images based on the similarity measure. 1.2 Research Questions Despite the large number of CBIR systems developed, there are still a lot of challenging problems in this area. The important sides that still need to be improved are speed of retrieving, when working with the large databases, accuracy and effectiveness of the retrieved results. So the researchers from multiple disciplines are deeply concerned with these aspects. Comparisons by image content are much more complicated task than by textual data. Generally, content-based image retrievals are based on comparison of image content descriptors that represent visual features of the image. Different features can be used to obtain the image descriptor. To meet specific user needs and in various cases some of them are more effective than others. Sometimes the implementation simplicity is as important as retrieval accuracy and effectiveness. Based on the previous discussion, research questions are the following: What are the basic retrieval techniques? What kind of features are usually used? How the features are obtained from the image? How these features are matched? How the retrieval results are presented to the user? How accurate can be the algorithms, which are relatively easy to implement? 1.3 Objectives The CBIR research often involves two areas computer vision and database systems. The database systems part studies database indexing, searching and retrieval techniques and computer vision part is about image processing, obtaining the image descriptors and image matching. In order to answer the research questions this dissertation focuses on a computer vision part. Image processing and image transformations are used by CBIR systems in order to extract image descriptors. CBIR systems are based on different image features descriptors matching. Some of these systems perform image comparison by multiple features at the same time and some of them use only one feature. In this dissertation we are going to investigate what are the basic techniques used in CBIR systems, which are based on different feature descriptors. We will make a detailed overview of these basic methods. We are also going to implement one of the most effective algorithms in the CBIR field. This is Scale Invariant Feature Transform (SIFT) algorithm (Lowe, 2004) and see how effective and accurate it can be. Chapter 2. Literature Survey 2.1 CBIR systems typical architecture Typical CBIR system has two main functionalities. This is Data insertion and query processing. Data insertion procedures are performed independent of user interaction.   They are applied to all the data. The purpose of this process is to extract visual features from the images in the database. These features are obviously smaller than the actual image and they are then stored for easy comparison reasons, as a characterizers of each image. Query processing starts with user specific request. Request can be done in several ways: By an example image, by giving desired pattern or object, color distribution and etc. Query processing module obtains the visual features from the given request, metric is defined. Then similarity is measured based on the chosen metric and some set of the most similar images are . Features extraction itself involves, selecting the features that have to be extracted, it depends on the type of user query. The feature extracting algorithm is chosen to create the feature vector from the selected features. Eventually, image descriptor is formed which are then used to compare the images. (Torres, 2006) 2.2 Semantic Gap Basically, similarity searching between the images is based on low-level and higher-levels of queries. (Eakins, 1996) Low-Level Similarity in this case visual features to describe the image are primitives such as color, texture and shape. Higher-Levels, Semantic Similarity at higher levels, similarity searching is not based on a simple features. In this case images are described by higher level of semantic attributes. This involves identification of the object types depicted in the image. These two levels of queries form the problem called semantic gap. Semantic gap can be defined in the following way: â€Å"The semantic gap is the lack of coincidence between the information that one can extract from the visual data and the interpretation that the same data has for a user in a given situation.† (Datta, 2008) In another words, images with high low-level feature similarities may still be different in terms of user perception. So similarity by low-level features, not always mean semantic similarity of these images. 2.3 Content Comparison Techniques This dissertation is concerned with low-level similarity features extraction .CBIR for low-level similarity queries needs techniques which can be used to obtain the image content descriptors to compare images based on their color, texture and shape. Color Image content comparison by color is based on matching images by their color distribution. In this case image feature identifies the proportion of pixels of specific color or colors within an image. So one can make color searches by indicating desired concentration of colors or by an example image with desired color distribution and get similar images. Color histograms are widely used to extract the color distribution descriptors from the image. It is a statistic of the color of pixels in the image. First color distribution is represented by appropriate color histogram, and then color vector is formed from that histogram. Lets discuss several color feature extraction histograms. Conventional Color Histogram (CCH) This histogram consists of occurrences of each color in the image. Each pixel is associated to only one its own histogram bin only on the basis of its own color. This color histogram uses the probability mass function of the image pixel intensities. (Suhasini, 2009) Fuzzy Color Histogram (FCH) as an opposite to CCH, in FCH each pixel is associated to all bins of histogram with different degrees of membership depending on color similarity of the pixel. This is done by fuzzy-set membership function. (ferone, 2008) Color Correlogram (CC) color correlogram of an image is a table which is indexed by color pairs, where the d-th entry of (i,j) cell shows the probability of finding the color j at a distance of d from a pixel of color i in the image extracting. Such a feature from the image is tolerant to the changes in appearance of the same scene which can be caused by changing the viewing positions, but color correlogram is more difficult to compute than color histograms. (Huang, 1997) Texture Retrieval by image texture in a similar to color-based feature extraction, but it looks for visual patterns in images rather than colors. So it looks at homogeneity that is not a result of a single color presence or intensity of a pixel value. Sometimes it also provides more spatial information. The most basic method used to extract the texture descriptor from the image is based on Fourier Transform. The initial image is transformed by the Fourier function. As the method works on digital images, Discrete Fourier Transform (DFT) is used. DFT converts images from the spatial domain into the frequency domain, where all the spatial frequencies of the original image are represented. In another words this transformed image shows intensity variations over a number of pixels. Transformed data is grouped to obtain several measures from it. Then descriptor is formed of these measures and is used for comparison. (Nixon, 2007) Shape Shape-based image retrieval comparison looks at shapes of regions within an image and searches for the shapes similar to given as in a query image. Edge and blob detections are important parts for the shape feature extraction. These edges and blobs are points or regions in the image that are either brighter or darker than the surrounding. Several methods are used for shape-based image retrieval, which involve different kind of image filtering and image transformations. One of the most effective algorithms for shape-based image retrieval is Scale Invariant Feature Transform (SIFT) algorithm, which was first developed by David Lowe in 1999, at the University of British Colombia. It takes a single image as an input and returns a set of detected image features. In SIFT algorithm image filtering is based on Gaussian function. After image filtering SIFT uses Difference of Gaussian (DoG) pyramid for blob (keypoint) detection. The image feature descriptor, which is called keypoint descriptor is 128 element feature vector and formed of gradient magnitudes and orientations computed for the area around the identified keypoints. (Lowe, 2004) Chapter 3. Research Method 3.1 Research approach Mathematical methods play key role in the most of CBIR algorithms. Often mathematical solution of the problem is difficult or impossible to implement practically, therefore it is important to assess the method in practice. Thats why Experimental approach will be used in this dissertation. This method of primary research forces to experience and overcome all the difficulties that can appear during the practical implementation of theory. It requires focusing on the details of algorithm and clearly shows advantages and disadvantages of the particular algorithm. It also gives possibility to assess the instruments used in experiment, which are not less important than algorithm itself. In this dissertation, one of the CBIR algorithms for shape-based image retrieval will be implemented for a number of images and the results will be assessed 3.2 Tools and Technologies used This study focuses on the algorithm which involves image processing. It will be implemented under the Microsoft .net framework platform and using GDI+ and C# programming language. .Net framework provides managed interface for GDI+; therefore its relatively easy to process images using this platform. Microsoft Visual Studio .Net will be used as an IDE. This experiment will also show how useful can be .net framework library and C# language for image processing purpose. References: Bach J., Fuler C., Gupta A., Hampapur A., Horowitz B., Humphrey R., Jain R., Shu C., (1996) The virage image search engine: An open framework for image management SPIE Conference on Storage and Retrieval for Image and Video Databases; Chen Ch. Ch. (2006),Using Tomorrows Retrieval Technology to Explore the Heritage: Bonding Past and Future in the Case of Global Memory Net; available at: http://ifla.queenslibrary.org/IV/ifla72/papers/097-Chen-en.pdf last accessed on 24th September 2009 Datta R., Joshi D., Li J. and Wang J. Z. (2008) Image Retrieval: Ideas, Influences, and Trends of the New Age. Eakins J.P. (1996) Automatic image content retrieval are we getting anywhere?Department of Computing, University of Northumbria at Newcastle, available at: http://www.cs.uu.nl/docs/vakken/mir/materials/literature/eakins.pdf last accessed on 24th September 2009 Ferone A., Maddalena L., Petrosino A., (2008) The Enhanced Color Histogram: a way for dealing with uncertainty in CBIR systems, University of Naples Parthenope, Department of Applied Science; Flickner M., Sawhney H., Niblack W., Ashley J., Huang Q., Dom B., Gorkani M., Hafher J., Lee D., Petkovie D., Steele D. and Yanker P.(1995) Query by Image and Video Content: The QBIC System, IBM Almaden Research Center; available at: http://www2.cs.ucy.ac.cy/~nicolast/courses/cs422/ReadingProjects/qbic.pdf last accessed on 24th September 2009; Hafiane A., Chaudhuri S., Seetharaman G., Zavidovique B. (2006) Region-based CBIR in GIS with local space filling curves to spatial representation Huang J., Kumar S. R., Mitra M., Zhu W. J., Zabih R. (1997) Image Indexing Using Color Correlograms, Cornell University; Lowe D. G. (2004), Distinctive Image Features from Scale-Invariant Keypoints, Computer Science Department University of British Columbia; available at: http://people.cs.ubc.ca/~lowe/papers/ijcv04.pdf last accessed on 24th September 2009 Nixon M. S., Aguado A. S. (2007) Feature Extraction and Image Processing, Academic Press; Suhasini P.S., Dr. K. Sri Rama Krishna, Dr. I. V. Murali Krishna (2009) CBIR Using Color Histogram Processing; VR Siddhartha Engineering College; available at: http://www.jatit.org/volumes/research-papers/Vol6No1/13Vol6No1.pdf last accessed on 24th September 2009; Tahmoush D.   Hanan S. (2007)A Web Collaboration System for Content-Based Image Retrieval of Medical imag;available at:http://www.cs.umd.edu/~hjs/pubs/medicalimagepapers/TahmoushSPIE07a.pdf last accessed on 24th September 2009; Torres R. S., Falcà £o A. X. (2006)Content-Based Image Retrieval: Theory and Applications; available at: http://www.dcc.unicamp.br/~rtorres/artigos/journal/torres06rita.pdf last accessed on 24th September 2009; Veltkamp R. C., Tanase M. (2002) Content-Based Image Retrieval Systems: A Survey; Department of Computing Science, Utrecht University; available at: http://give-lab.cs.uu.nl/cbirsurvey/cbir-survey.pdf last accessed on 24th September 2009; Wang J. Z. (2001) SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture Libraries; available at: http://infolab.stanford.edu/~wangz/project/imsearch/SIMPLIcity/TPAMI/wang2.pdf last accessed on 24th September 2009; Wen Ch. Y, Yu Ch. Y., (2005) Image Retrieval of Digital Crime Scene Images, Forensic Science Journal; available at: http://fsjournal.cpu.edu.tw/content/vol4.no.1/06-95-04.pdf last accessed on 24th September 2009.