A Content based Shape Retrieval System Soumya Naskar
Ranjan Parekh
School of Education Technology Jadavpur University Calcutta, India
[email protected]
School of Education Technology Jadavpur University Calcutta, India
[email protected]
Abstract—This paper outlines a methodology of building a content based image storage and retrieval system by extracting and querying shape related information from the image and representing them as vectors in a database. The method is based on the popular centroid-radii model, however to make it invariant to rotation this paper proposes comparing the number of radii of specific lengths instead of directly comparing the lengths themselves. The normalization of radii lengths also makes the process invariant to scaling. To represent shapes with holes inside them the method is extended by considering a number of concentric circles centered at the centroid and computing radii histograms for the portion of the shape within each of the circles. The similarity of two shapes are judged by comparing the number of radii in corresponding ranges. The method has been seen to yield an appreciable amount of accuracy.
I.
INTRODUCTION
The last decade has seen a rapid growth in the use of multimedia components in various fields. Application areas like TV productions, video on demand, home entertainment, multimedia, on-line art galleries and museums, architectural and engineering design, medical imaging, geographic information systems, information superhighways and so on, have led to the building up of large digital media repositories all around the world. In this scenario content-based retrieval assumes a fundamental role. An efficient technology for populating, managing and retrieval of media components therefore has become the subject matter of active research all over the world [1]. Initial approaches to content-based retrieval were mainly based on ways to characterize the media components using textual description strings and keywords, manually specified by an operator. The biggest disadvantage was that, since the characterization was done by human beings, they were largely subjective and lacked universality. In recent years research has focused on the means to extract features from media components directly using automatic or semi-automatic procedures requiring little or no human intervention. This paper outlines a methodology of building a content based image storage and retrieval system by automatically extracting and querying shape related information from the image. Shapes of image objects
0-7803-9197-7/05/$20.00 © 2005 IEEE.
are extracted, represented as a set of vectors and stored in a database along with a pointer to the actual image. During a query session, corresponding features from the query image are also extracted and compared with those stored in the database. Based on a pre-defined threshold value, a result list of most similar images are generated. Since shapes can be of any arbitrary nature one of the major challenges is to model them adequately using mathematical vectors. Another challenge is to make the model invariant to translation, rotation and scaling so that even if the shape is transformed the relative location of each point remains unchanged with respect to the other points and hence should be recognizable as the same shape. II.
PREVIOUS RESEARCH EFFORTS
Literature provides a variety of shape representation techniques, most of them being derived from research into computer vision and image analysis while others have been developed specially for image storing. In the case of 2D images, it is a widely accepted fact that most of the information about shape focuses on the outlines of objects; this has led many researchers to focus on the representation of outlines rather than internal points. A.
Grid-based approach Sajjanhar and Lu [2] propose a method which can be used for shape representation and similarity measure. It is called the grid-based method. The shape is mapped onto a grid of fixed cell size, and is justified to the top left corner. The grid is scanned from left to right, and also from top to bottom. A value of 1 is assigned to the cells of the grid which are partially or wholly covered by the shape, and 0 to the cells which are not covered by the shape, obtaining a sequence of 0’s or 1’s. This sequence can be used for shape representation. Naturally, the difference between two different shapes can be computed as the number of cells in the grids which are covered by one shape, but not by the other. Obviously, this representation is invariant to translation but sensitive to rotation and scaling.
1745
B. Turning angles based approach In this method [3], the boundary of a shape can be described by the turning function θ A (s ) . This function measures the angle of the counter-clockwise tangent as a function of the arc-length s, which is measured from a given reference start point O on the polygon’s boundary. θ A (O ) is the angle v which the tangent at the reference point O makes with the reference orientation, e.g., the x-axis. In this way, the turning function θ A (s ) will keep tracking around the boundary, and will increase with left-hand turns and decrease with right-hand turns. Given two polygons, A and B whose turning functions are θ A (s ) and θ B (s ) the difference between them can be defined as the Euclidean distance :
D( A, B) =
¦ (θ
A
(i) − θ B (i)) 2
i
Although the method gives a compact description in the form of a uni-dimensional signal, however, the Euclidean distance defined in the literature is very sensitive to small variations in outlines of the shapes which cause great variations in their TA representations. C. Centroid radii based approach In [4] K L Tan et al. proposes the centroid-radii model for estimating shapes of objects in images. A shape is defined to be an area of black on a background of white. Each pixel is represented by its color (black or white) and its x-y co-ordinates on the canvas. The centroid is located at the position ( X C , YC ) such that X C and YC are, respectively, the average of the x and y co-ordinates for all black pixels. The boundary of a shape consists of a series of boundary points. A boundary point is a black pixel with a white pixel as its neighbor. A radius is a straight line joining the centroid to a boundary point. In the centroid-radii model, lengths of a shape’s radii from its centroid at regular intervals (say angle θ degrees) are captured as the shape’s descriptor. Then, the number of intervals is given by k =360/ș. All radii lengths are normalized by dividing with the longest radius length from the set of radii lengths extracted. Thus, the shape descriptor can be represented as a vector (l 0 , lθ , l 2θ ,..., l ( k −1)θ ) , where liθ , 0 ≤ i ≤ (k-1) is the (i+1)th radius from the centroid to the boundary of the shape. With sufficient number of radii, dissimilar shapes can be differentiated from each other by comparing their shape vectors. One disadvantage of the centroid-radii model is that since radii lengths at corresponding angular separation are directly compared, the order of comparison becomes important. This makes the method non-invariant to rotation. If a shape is rotated by an arbitrary angle, the corresponding radii lengths at equal angular separation (starting from a reference axis) would be different from those in its nonrotated condition and hence would not indicate appreciable levels of similarity.
III.
HISTOGRAM BASED APPROACH
The method proposed in this paper is based on the centroid-radii model. To make the method invariant to rotation, this paper proposes comparing the number of radii of specific lengths instead of directly comparing the lengths themselves. The radii are generated from the centroid by rotating a vector in steps through specific angles. Thereafter the radii lengths are normalized and sorted into ranges. The number of ranges can be chosen arbitrarily small to increase the accuracy of the method. The number of normalized radii within each range is computed and stored as a feature set characterizing the shape. Two shapes could be compared by comparing the number of radii in corresponding ranges to estimate their similarities. Equal or nearly same number of radii in corresponding ranges would indicate a high value of similarity while large differential values would in general indicate large dissimilarities. A. Computing the centroid A shape is assumed to consist of black pixels against a white background. Thus all the black pixels forms part of the shape whose feature is to be extracted. The centroid of the shape is obtained from computing the average of the coordinates of all black pixels. The entire image is scanned from left to right and top to bottom and the pixel values are read sequentially. for i = 1 to h for j = 1 to w read pixel(j,i) where h and w are the height and width of the image in pixels and pixel(j,i) represents the RGB value of the pixel at point (j,i).To identify the black pixels, the RGB components of each pixel is separated and tested whether all are zero. // pixel information is in the format rrggbb (8 bits * 3) red = pixel AND FF0000 green = pixel AND 00FF00 blue = pixel AND 0000FF if (red == 0) AND (green == 0) AND (blue == 0) //black record its coordinates (j,i) The locational values of the black pixels are stored in two arrays X and Y, where X = {x1 , x 2 ..., x k } contains xcoordinates of k black pixels, and
Y = { y1 , y 2 ..., y k }
contains y-coordinates of k black pixels, k = w * h. The coordinates of centroid X C and YC are computed as average of coordinates of all black pixels k
k
i =1
i =1
X C = (¦ xi ) / k and YC = (¦ y i ) / k B. Identifying Boundary Points The black pixels comprise the body of the shape. A boundary pixel is one which has one or more white pixels as neighbours. To identify the boundary pixels each of the black pixels is tested to see whether any of its eight neighbours is white.
1746
// do for all black pixels for i=1 to k // extract RGB value of neighbouring pixels read pixel ( xi ± 1, y i ± 1)
histograms have been obtained, their difference can be measured by the Euclidean distance : N
D( I 1 , I 2 ) =
( xi , y i ) in arrays B x , B y
Because of the representation through a histogram, the original radii are not represented as vectors with angle specifications. This makes the process invariant to rotation since the number of radii in each partition always remains the same irrespective of the orientation of the shape.
// for boundary points
C. Generating the Radii A radius is a straight line joining the centroid to a boundary point. A reference axis e.g. x-axis, is considered, a boundary point on this axis is taken and joined with the centroid. The length of the radius is recorded. Based on a pre-defined number of boundary points to be considered around the perimeter of the shape, say 12, the radii is rotated by an angle (+ve for CCW) θ =30° and the next radii is drawn. The radii is extrapolated until it meets the corresponding boundary point whereupon the coordinates of the second boundary point is also recorded. The process is repeated until all the 12 radii are generated and the coordinates of 12 boundary points are recorded. The distance between the centroid C ( X C ,Y C ) and any boundary point on the periphery of the shape S
X O
P8
P2
• R2
R5
P5
Y
d ( si , c) = ( X C − xi ) 2 − (YC − y i ) 2
P11 •
R11 • P4 R8 • R4
•
( xi , y i ) is given by the relation :
•
R7
P7
P3 •
R3
•C R10 R12 R9 • • P12 P9 • P10 y
R1
•
P1
x
R6 •
P6
Number of Radii
In this way the distances from the centroid to all the 12 sample boundary points on the boundary of the shape may be calculated. The centroid is chosen as the origin of a local coordinate system attached with the shape. Coordinates of all points are translated to the local coordinate system.
5 4
D. Generating the Histogram Let the individual radii lengths be
(n1i − n2i ) 2
i =1
// separate RGB components as before if red AND green AND blue == FF // ( xi , y i ) is a boundary point store
¦
3
R1 , R2 , R3 ,..., Rn where
n is the total number of radii. To make the method invariant
2
to scaling, all the radii lengths are divided by the largest radii Rmax . The normalized radii lengths are
1 0
R R R R r1 = 1 , r2 = 2 , r3 = 3 ,..., rn = n which Rmax Rmax Rmax Rmax are then grouped into N partitions whose ranges are 1 1 2 ( N − 1) [0, ] , [ , ] , ..., [ ,1] and the number of N N N N
.25 .5 .75 1.0 Normalized Ranges Figure 1. Generating the histogram
normalized radii in each partition is plotted in a histogram. The histogram can now be represented by the vector :
N = (n1 , n2 ,..., n N ) where (n1 , n2 ,..., n N ) are the number of normalized
E. The Database The number of fields in the database would correspond to the number of partitions of the histogram. Based on number of partitions N each field would store the number of radii whose normalized length lie within the corresponding ranges. If N is assumed to 4, the database table would be:
distances from the centroid to the boundary points grouped into N partitions. Given two shapes I 1 and I 2 whose
1747
@ID (integer) + Filename (string) + n1 (integer) + n2 (integer) + n3 (integer) + n4 (integer)
