Fourier Descriptors For Shape Based Image Retrieval

Fourier Descriptors For Shape Based Image Retrieval

1. iddartha Raghavendra Mohammed Danish S.Imtiyaz Khan S.Venkateswarlu

   Abstract

   Now-a-days context based image retrieval is a widely using methodology for retrieving images which is associated with the metadata of images i.e., keywords, tags, descriptions of the image. Most of the todays image search engines are using the same methodology of context in their algorithms for retrieving images. Now the goal is to retrieve the images whose content is similar to that of query image. Content-Based Image Retrieval (CBIR) or Query By Image Content (QBIC) is one such methodology which concentrates on the content of the images like shape, color, texture or any other information that can be obtained from the image itself.

   Shape is one of the most important features of Content-based image retrieval. There exists some methods of retrieval based on shape but these methods do not well represent the shape and making matching is difficult with those methods. Fourier Descriptors (FDs) which are made invariant against scale, rotation and translation is one solution for retrieving images based on the shape of the image components.

   Introduction

   Numbers of images captured by digital cameras are being increased gigantically every day. The gigantic growth of image databases is due to the simplicity and convenience of capturing digital images and transmitting them between digital cameras and image databases. These databases cover a broad range of applications in different fields. The storage format of the image data is pretty consistent; but, the valuable and useful retrieval of images from such databases continues to be a considerable challenge.

   For handling immense amounts of stored and exchanged information of images, automatic image-retrieval techniques are necessary. From a database, images are usually retrieved based on either metadata of image or content information of the image. Most of the todays image search engines algorithms are using the metadata method of retrieval which is also known as context based image retrieval for retrieving images. Keywords, tags and other

   textual descriptions of the image form its metadata. But context-based image retrieval techniques have many limitations due to their dependence on manual footnote which is a tedious and error-prone process, especially for large data sets.

   Image Retrieval

   Context Based

   (Tags, Keywords, Description)

   Content Based

   (Color, Shape, Texture)

   Fig: Methods of Image Retrieval

   Content-Based Image Retrieval (CBIR) overcomes the difficulties of context-based image retrieval. This approach to image retrieval relies on the visual content like color, shape and texture of the images rather than on metadata and therefore has the prospective to respond to more specific user queries. The visual contents (any information that can be obtained from the image itself) of the images are extracted and described by feature vectors that form a feature database.

   Color

   Content Based

   Image Retrieval

   Shape

   Texture

   Any other information from the image itself

   Fig: CBIR Classification

   In CBIR system, users provide the retrieval system with some query image. The system then modifies this query image into feature vectors. Then, the system calculates the similarities or differences between the feature vectors of the query image and the feature vectors of the images in the database, and then achieves the retrieval accordingly.

   Among the different features like color, shape and texture, one of the most important low level features of image is shape. Shapes are random 2D figures obtained from edges extracted in images of 3D objects, not just outlines. Shapes are symbolized by a set of points sampled from the shape contours. As far as query image is concerned, shape is simple for users to describe, either by giving example or by sketching. Once images are broken down into individual components, they can be subjugated to facilitate CBIR.

   There exists some methods of retrieval based on shape but these methods do not well represent the shape and making matching is difficult with those methods. Fourier Descriptors (FDs) which are made invariant against translation, scale, rotation and starting point is one solution for retrieving images based on the shape of the image components. Essential information about the contour of the image component can be retained by using Fourier Descriptors. Well representation and well normalization of shapes can be achieved by using Fourier Descriptors.

   Fourier Descriptors

   Fourier descriptors are applied for description of shape of any object found on input image. Invariance to scale, rotation and translation of the experimental object is their main advantage. Thus the description of shape becomes independent of the size of the object and the relative position of the object in the input image. To say clearly, distance between camera and object and the object placement relative to the optical axis of image acquisition system will not affect values of the Fourier Descriptors.

   Fourier Descriptors Calculation:

   Input image must be segmented and boundary of the object must be found out before calculating the Fourier Descriptors. Let and be the coordinates of the nth pixel on the boundary of a given 2D shape, a complex number can be formed as:

   The boundary will be represented as an array of such complex numbers which corresponds to the pixels of the object boundary if the image is placed in the complex plane.

   Now Fourier Descriptors are calculated by combining complex array Fourier transform coefficients. Let , , ,, be the complex array which represents the boundary belonging to the object whose shape is to be described. Now, the kth Fourier transform coefficient of the shape is calculated as:

   where k=0, 1, 2, , N-1.

   The Fourier descriptors are obtained from the sequence by truncating elements and , than by taking the absolute value of the remaining elements and dividing every element of resultant array by | |. In short, the Fourier Descriptors are:

   where k=2, 3, 4, , N-1.

   Properties of Fourier Descriptors

   Translation:

   Idealized translation can be expressed as sum of any complex number F and the every element in the array which contains boundary coordinates. The discrete Fourier transform of such an array can be given as:

   In the above equation the first summation element is equal to the element of non- translated array and the second element is:

   { ,

   ,

   As per above equation translation affects only the value of discrete Fourier transforms first element, and the translation invariance can be acquired just by truncating the first element .

   Rotation:

   Idealized rotation for the angle can be expressed as multiplication of the every element in the array with . The discrete Fourier transform of such an array can be given as:

   For attaining the rotational invariance it is enough to take the absolute value of each element, because | | = 1.

   Scaling:

   Idealized scaling can be expressed as multiplication of the every element in the array with the real constant C. The discrete Fourier transformation of such an array can be given as:

   If observed the above equation, each element of the discrete Fourier transform is multiplied with constant C. Scaling invariance can be achieved by scaling each array element by absolute value of one seleced element form the array. However, as translational invariance is also preferred, scaling cannot be done by using the first array element because its value will alter if we have translated the object. Element is generally preferred for scaling, and scaling is done by dividing every array element by | |.

   When idealized cases of translation, rotation and scaling are considered, all the above depicted properties are exact but if the input images obtained by system are spatially sampled and all the transformations occur before image sampling, the statements made concerning all of the transformations (translation, rotation and scaling) are not exact, but are only approximations. But, in practice this will not root any complications.

   Conclusion

   More progress would be made in the field of Content Based Image Retrieval as time passes. One of the main advantages of the Fourier Descriptors is the opportunity of an automatic retrieval process, instead of the traditional context-based approach, which generally requires very arduous and time-consuming prior footnote of database images. There are different algorithms available for it and Fourier Descriptor is one of the best according to its behavior with Translation, Rotation, Scaling, and Starting Point. The numbers of images are mounting with the jet speed every day and just having the terrific amount of information is not useful if not there are techniques available to efficiently search the related data from it in minimum possible extent. The CBIR technologies have numerous applications in todays life if explored properly. Thus, field of Content Based Image Retrieval & Fourier Descriptors is extremely helpful for realistic causes.

   References:

   1. T.Gokaramaiah, P.Viswanath and B.Eawara Reddy – A Novel Based Hierarchical Retrieval System for 2D Images

   2. Dengsheng Zhang and Guojun Lu – A Comparative Study of Fourier Descriptors for Shape Representation and Retrieval

   3. Dengsheng Zhang and Guojun Lu – A Comparative Study on Shape Retrieval Using Fourier Descriptors with Different Shape Signatures

   4. Content-based Image Retrieval Using Fourier Descriptors on a Logo Database – Andre Folkers and Hanan Samet

   5. Mahesh Maurya, Chitvan Oza, Alok Shah and Sadiya Patel – A Review on Content Based Image Retrieval

   6. Tomislav Petkovi´c and Josip Krapac – Shape description with Fourier descriptors

   7. Akrem Saad El-ghazal – Multi-Technique Fusion for Shape-Based Image Retrieval

   8. Greg Moriy, Serge Belongiez and Jitendra Maliky – Shape contexts enable efficient retrieval of similar shapes

   9. Tyler Karrels – Fourier Descriptors (Properties and Utility in Leaf Classification)

   10. Dengsheng Zhang and Guojun Lu – A Comparative Study on Shape Retrieval Using Fourier Descriptors with Different Shape Signatures

   11. Bryan S. Morse – Shape Description (Contours)

   12. Serge Belongie, Jitendra Malik and Jan Puzicha – Matching Shapes 13 Aditya Vailaya – Shape-based Image Retrieval

1. Mark Handley – Fourier Transforms

2. Rafael C. Gonzalez, Richard E. Woods – Digital Image Processing