Chuping Liu Julien Lamoureux Yuxin Wang Yunan Xiang
Many applications can be implemented with FPGA, such as control systems, multimedia system and digital signal processing (DSP). Among these applications, a branch of DSP, image processing is a hot topic today. In this application note, image indexing will be introduced and a histogram-indexing algorithm for it will be discussed in detail.
With the extensive use, especially with the Internet, of digital images and video sequences in various applications, (e.g., digital libraries, remote sensing, scientific visualization, medicine, and multimedia systems), image and video indexing techniques have recently become very important.
A few years ago, the techniques of representation and retrieval of visual media were mainly text-based (or keyword-based) approaches due to deep influence of database technique at that time. However, it is difficult or nearly impossible to describe features of an image clearly with text. In order to provide a natural way to retrieve visual data, content-based visual query techniques are being developed which index the visual features of the images. The content of an image may be comprised of several visual features. Such features include patterns, colors, textures, and shapes of image objects, as well as related layout and location information. A histogram retrieval algorithm, based on image’s color content, will be discussed in the following sections.
Figure 1 Block diagram of principal of image indexing
The objective of image indexing is to retrieve similar images from an image database for a given query image (i.e., a pattern image). Each image has its unique feature, such as color, intensity, shape, location and texture, etc, as mentioned in last section. Hence image indexing can be implemented by comparing their features, which are extracted from the images. Figure 1 shows a typical image indexing system. There are 3 modules in the system. Each original image is fed into an “input module” and has its feature extracted there. The features extracted from all the original images form a feature database. In the “query module”, the query image’s feature is extracted in the same way as the original images. In the “retrieval module”, the feature of the query image is compared with each of the features in the database, and images that are most similar to the query image are retrieved at last.
A histogram is a method used to describe the frequency distribution of a digital signal. Histograms are composed of multiple bins, with each bin corresponding to a range of values. The value of each bin is obtained by summing the occurrences of digital signal samples whose values fall in the domain of that corresponding bin. For example: An 8-bit gray-level picture is composed of N total pixels whose intensity values can range from 0 to 255. Using a 16-bin intensity histogram, with even bin intervals of 16 (here, the bin interval may be variable from 1 to 256), the image’s intensity frequency distribution can be plotted as shown below (see Fig.2). The corresponding value of each bin bk, (0£k£15), is the number of of pixels nk, whose intensity value fall in the range of bin bk, i.e.:
Figure 2 A histogram example
A color histogram of an image is actually comprised of 3 histograms. Assume that the color of any pixel may be represented in terms of component R(red), G(green), B(blue) values, then a color histogram may be defined, each of whose bins corresponds to a range of those values for each of the components. It denotes the joint probabilities of the intensities of RGB. The color histogram is computed by discretizing the colors within the image and counting the number of pixels of each color.
Figure 3 Color histograms (a) three channel color flower image (b) histogram for each channel in (c) histograms. Dotted lines indicate average channel values.
The euclidean distance between two color histograms h and g is given by
In this distance formula there is only comparison between the identical bins in the respective histograms. Two different bins may represent perceptually similar colors but are not compared cross-wise. All bins contribute equally to the distance.
Comparing histograms is only one of many ways in which image indexing can be implemented. The histogram implementation has strengths as well as weaknesses. Histograms perform well when the orientation and location of objects within an image do not need to be considered. Histograms are also suitable when comparing textured images and other images that are not particularly amenable to segmentation.
When the location and orientation of the images to be compared is considered important, histograms implementations perform poorly because they do not retain any information regarding location and orientation. Another problem of retrieval by image example occurs when the query and target image containing instances of the same object(s) are recorded under different imaging or lighting conditions. Moreover, histograms tend to produce many false positions (rankings) when the image database is very large.
1. B. Furht et al, Video and Image Processing in Multimedia System, Kluwer Academic
2. J.R. Smith, Integrated Spatial and Feature Image Systems: Retrieval, Analysis and compression, http://disney.ctr.columbia.edu/jrsthesis/thesissmall.html .
3. M.D. Marsicoi et al, Indexing pictorial
documents by their content : a survey of current techniques, Image and Vision Computing 15 (1997) 119-141
4. J.R. Smith et al, Tools and Techniques for Color Image Retrieval, http://www.ctr.columbia.edu/~jrsmith/html/pubs/tatfcir/color.html
5. Tim Bensler, Eric Chan, Data Compression Co-processor Final Report, http://www.ee.ualberta.ca/~elliott/ee552/projects/1999_w/dataCompression/
6. F. Idris et al, Image and video indexing using vector quantization, Machine Vision and Applications (1997) 43-50