3. Teoretiske begrep
3.1 Tillit
Gustavo Botelho de Souza and Aparecido Nilceu Marana
Instituto de Biociˆencias, Letras e Ciˆencias Exatas (IBILCE) / Faculdade de Ciˆencias (FC) Universidade Estadual Paulista “J´ulio de Mesquita Filho” (UNESP)
S˜ao Jos´e do Rio Preto / Bauru - SP - Brazil E-mail: [email protected], [email protected]
Abstract—Nowadays, the visual pattern recognition task has been automated, in particular to address the vast amount of digital images available, benefiting applications from many areas such as biometrics, content-based image retrieval and medical diagnosis. The main features that can be analyzed from a given digital image are color, texture and shape. In this work1, three new shape descriptors are proposed, which make use of statistical values extracted from the Hough space in order to characterize the shape of objects in digital images. Experiments conducted over some public and popular image databases showed that the new methods are very accurate and fast when compared with other important shape descriptors of the literature.
Keywords-HTS; HTSn; HTSh; Shape Analysis; Hough Trans- form; Image Analysis; Pattern Recognition.
I. INTRODUCTION
Human beings have an extremely powerful ability to deal with images. During evolution, humans developed highly sophisticated neural and cognitive systems dedicated to the recognition of visual patterns [2]. With the advent of com- putation, researchers and companies around the world began to study techniques to automate such process, given the wide variety of applications. Three basic features that can be analyzed from a digital image in order to obtain information about its content are color, texture and shape.
According to Costa and J´unior [3], shape can be defined as a set of connected points, either in a discrete or continuous space, that presents a distribution pattern. The analysis of the shape of objects in digital images is an important source of information to the computer systems dedicated to the visual pattern recognition task, since, despite of being very discriminative, the shape, in many cases, is the only feature that can be analyzed accurately due to, e.g.. the low “quality” of the images.
The shape analysis is indispensable for applications from many areas, such as: biometrics, in automatic people recog- nition systems; medicine, in medical diagnosis assistance systems (tumor identification, cell counting, analysis of the changes and deformations in anatomic structures, chromo- somes analysis); electronic documents analysis, in CBIR (Content-Based Image Retrieval) and OCR (Optical Character Recognition) systems; physics, in systems dedicated to the
1M.Sc. dissertation [1].
macroscopic bodies movement analysis and in systems that work with microscopic images; engineering, in automation systems, robotic and remote sensing; among others [3].
In this work, we propose three new shape descriptors that use statistic values obtained from the Hough space [4] in order to characterize the shapes of objects in digital images. The Hough spaces, as shown in Fig. 1, are quite similar when they are calculated from boundary points of similar objects and very different when calculated from boundary points of distinct objects. Experiments conducted over traditional and public image databases showed that the proposed methods, besides of presenting algorithms with linear complexity, are very accurate when compared with important shape descriptors of the literature.
Fig. 1. Hough spaces (top) of some silhouettes from the MPEG-7 CE-1 Part B [5] database (bottom). The Hough spaces (accumulator matrices) are visually represented by grayscale images. The darker the pixel in the image, the lower the value in the respective position of the accumulator matrix.
II. HTS: HOUGHTRANSFORMSTATISTICS
A new shape description method, called HTS (Hough Trans- form Statistics), which is based on the Hough transform [4], is proposed in this work. The Hough transform was originally proposed by Paul Hough [6] in 1962 and improved later by Duda and Hart [4]. In this transform, each element in the image is represented in the ρ-θ parameter space (Hough space) through Eq. 1:
Considering θ ∈ [0◦; 180◦[, each straight line segment in the x-y space of the image corresponds to a unique point in the ρ-θ parameter space. On the other hand, each point in the image, with its (x, y) coordinates, is represented by a sinusoidal curve in the Hough space. Sinusoids that represent collinear points of the image in the ρ-θ space have a common intersection point,(ρ0, θ0), which represents, in this space, the straight line segment of the image to which the given points belong [4].
Based on this understanding, given the segmented boundary of an object in an image, points that belong to straight line segments in the boundary tend to present high number of sinusoids intersections (peaks) in some positions along their correspondent sinusoidal curves in the Hough space, while points belonging to curved regions of the boundary do not tend to present those peaks along their correspondent sinusoids (the number of intersections is more homogeneously distributed along their sinusoidal curves in the parameter space). The HTS method uses this information in order to characterize the shape of the object in the image under analysis.
The proposed method, like other shape descriptors, presents three phases: Preprocessing (boundary segmentation); Feature Extraction; and Matching. As explained in [1], the HTS shape descriptor has an algorithm with linear complexity, unlike the BAS (Beam Angle Statistics) [7] method, a very important shape descriptor of the literature that inspired the HTS formu- lation, which has an algorithm with quadratic complexity. A. Feature Extraction Phase
Given the segmented boundary of the object in the image under analysis, each boundary point is represented by a sinusoidal curve in the ρ-θ parameter space (an accumulator matrix, with180 columns and a fixed number of rows, with all elements initially set to zero). The sinusoidal curves in the ρ–θ space are calculated based on Eq. 1, using the coordinates x and y of the corresponding boundary points and varying the θ parameter from0◦to179◦. During this process, the positions (ρ, θ) of the accumulator matrix corresponding to the points of each sinusoid are incremented by one.
After representing all sinusoids in the Hough space, it is associated with each boundary point p, by following its respective sinusoidal curve (σ) in the parameter space, a histogram with the number of other sinusoids that intersect σ at each position (this is done just by verifying the values stored in the respective accumulator matrix positions). Each bin of the histogram associated with p indicates the number of other boundary points that are collinear to p in a given boundary straight line segment.
Points belonging to straight line segments in the boundary tend to present peaks in some positions of their corresponding histograms, while points of curved regions of the boundary tend to present histograms with values more homogeneously distributed. In Fig. 2 are shown the histograms associated with four boundary points of two similar objects (same class - bells) from the MPEG-7 CE-1 Part B [5] image dataset. As can be seen, boundary points that belong to large and relatively
straight segments of the boundary (points C and D) present protuberant peaks in their histograms while other boundary points (like A and B) present histograms without significant peaks. Histogram - Point A 0 5 10 15 20 25 30 35 40 45 50 0102030405060708090100110120130140150160170 θ Valu es O b se rve d Histogram - Point B 0 5 10 15 20 25 30 35 40 45 50 0102030405060708090100110120130140150160170 θ Valu es O b se rve d Histogram - Point C 0 5 10 15 20 25 30 35 40 45 50 0102030405060708090100110120130140150160170 θ Valu es O b se rve d Histogram - Point D 0 5 10 15 20 25 30 35 40 45 50 55 0102030405060708090100110120130140150160170 θ Valu es O b se rve d A C B D V alues O bs er ved θ Histogram – Point C θ Histogram – Point A V alues O bs er ved
Histogram – Point B Histogram – Point D
V alues O bs er ved θ θ V alues O bs er ved
Fig. 2. Histograms associated with four boundary points of two similar objects (same class - bells) from the MPEG-7 CE-1 Part B [5] image database.
After these steps, are associated, with each boundary point p, the mean and standard deviation of its respective histogram (the histograms of the boundary points are, then, discarded). Points belonging to boundary straight line segments are likely to present higher standard deviations than other boundary points since their histograms, as explained, tend to present peaks. As in the BAS [7] method, given an initial boundary point (the top leftmost point, for instance) and by following the boundary clockwise, two 1D functions are built, based on the mean and standard deviation values associated with the boundary points. Fig. 3 shows the 1D functions obtained for some objects. As one can see, objects of the same class present similar functions while objects of distinct classes present very different functions. Funções HTS - Maçã 2 0 2 4 6 8 10 12 14385 127 169 211 253 295 337 379 421 463 505 547 589 631 673 715 757 799 841 Ponto de Borda V a lo r Média Desvio Padrão Funções HTS - Sino 0 2 4 6 8 10 12 173145217289361433505577649721793865937 1009 1081 1153 Ponto de Borda V a lo r Média Desvio Padrão Funções HTS - Quadrado 0 5 10 15 20 25 30 35 40 178155232309386463540617694771848925 1002 1079 1156 1233 Ponto de Borda V a lo r Média Desvio Padrão Funções HTS - Maçã 1 0 2 4 6 8 10 12 1316191 121 151 181 211 241 271 301 331 361 391 421 451 481 511 541 571 601 631 661 Ponto de Borda V a lo r Média Desvio Padrão
HTS Functions – Square HTS Functions – Apple 1
HTS Functions – Apple 2 HTS Functions - Bell
V a lu e V a lu e V a lu e V a lu e
Boundary Point Boundary Point
Boundary Point Boundary Point M D P Standard Deviation Mean M D P Standard Deviation Mean M D P Standard Deviation Mean M D P Standard Deviation Mean
Fig. 3. Functions obtained for a square and for some silhouettes from the MPEG-7 Part B [5] database. It is possible to note that objects of the same class (apples) present similar functions while objects of distinct classes present very different functions.
It is also possible to observe, in Fig. 3, that the standard deviation function for the square silhouette has four peaks. These peaks correspond to the four vertices of the square: since
they belong to two large boundary straight line segments, they present histograms with two protuberant peaks, and, based on this, high standard deviations associated with them. The other boundary points belong to only one large boundary straight line segment and then, present high standard deviations but lower than the ones of the vertices. Besides this, since the four boundary straight line segments (sides of the square) have the same size, the standard deviations of the four vertices are approximately the same. Due to the same reason, the standard deviations of the other boundary points, as can be seen, are also almost the same.
After finding the 1D functions for a given object, they are sampled in k equally spaced positions in order to generate its feature vector. Each position of the feature vector contains two values: the mean and standard deviation sampled from the functions at a given position.
B. Matching Phase
Given two feature vectors, they are matched using the L1 distance. The mean values in the first feature vector are compared with the mean values in the second one, while the standard deviation values of the first feature vector are compared with standard deviation values of the second:
L1(s, r) = N X i=1
[|sim− rim| + |sid− rid|] (2)
where s and r correspond to the feature vectors, simand rim are the mean values stored in the si and ri positions of the vectors, and sid and rid correspond to the standard deviation values stored in the si and ri positions of the vectors. N represents the length of the feature vectors.
In order to classify an unknown object, its feature vector is matched with the database feature vectors (that represent the previous known objects). The test object is, then, identified as belonging to the same class of the most similar object of the database (with the feature vector that produced the minimum L1 distance).
III. HTSN: HOUGHTRANSFORMSTATISTICS-
NEIGHBORHOOD
A modification in the Feature Extraction phase of the HTS method improved considerably its accuracy. Basically, instead of only observing the values stored in respective positions of the Hough space (accumulator matrix) while following the sinusoidal curve of a given boundary point in order to build its histogram, in this modified version of the HTS, the values stored in the adjacent matrix positions of each sinusoid point are also considered: the final value observed for a given sinusoid position (to be stored in a histogram bin) corresponds to the sum of the value in the respective matrix position with the values stored in the eight adjacent positions of the matrix (3 × 3 neighborhood system centered at the given sinusoidal curve position).
This modification is justified since, once using a discrete space (accumulator matrix) to represent a continuous parame- ter space, many approximations are necessary in the sinusoidal
curves calculation process. Due to this reason and as observed in some tests conducted, some sinusoids do not pass exactly over the positions of the parameter space that represent the boundary straight line segments to which their correspondent boundary points belong: sometimes they pass over adjacent positions of the Hough space.
As observation, this new version of the HTS method was called HTSn (Hough Transform Statistics - neighborhood). In [1], it is possible to observe a graphical example that illustrates de difference in the histograms construction step in the HTS and HTSn methods. The HTSn descriptor also has an algorithm with linear complexity [1].
IV. HTSH: HOUGHTRANFORMSTATISTICS-HISTOGRAMS
A third version of the HTS descriptor, which also presented excellent results, was proposed and called HTSh (Hough Transform Statistcs - histograms). In this method, the shape of the object under analysis is characterized using the proper histograms of the boundary points (their mean and standard deviation values are not calculated).
After associating a histogram to each boundary point (like in the original HTS method), k equally spaced boundary points are sampled from the boundary of the object, given an initial boundary point (the top leftmost point, for instance) and by following the boundary clockwise. Then, the feature vector of the unknown object is built by storing the histograms of the sampled points, each histogram in a feature vector position. A graphical example of the feature vector construction process by the HTSh method is shown in [1].
Given two feature vectors (of two objects), they are matched in order to find their similarity degree (distance). The matching is performed by comparing the pairs of histograms (one from each feature vector) in respective positions of the vectors. This comparison is carried out using the Canberra distance, as shown in Eq. 3: C(a, b) = 179 X i=0 |ai− bi| |ai| + |bi| (3)
where a and b correspond to the histograms being matched. The final distance between two feature vectors corresponds to the sum of the costs Ci (with i= 1, 2, ..., k) resulting from the comparison of all the k pairs of respective histograms. As in the HTS method, in order to classify an unknown object, its feature vector is matched with the database feature vectors. The test object is, then, identified as belonging to the same class of the most similar object of the database (lowest final distance). As shown in [1], the HTSh method also presents an algorithm with linear complexity.
V. EXPERIMENTS, RESULTS ANDDISCUSSION
The three methods proposed in this work [1] were evaluated, in terms of accuracy and processing time, over some traditional image databases. Their performances were compared with the results obtained by some important shape descriptors of the literature: BAS (Beam Angle Statistics) [7], MFD (Multiscale
Fractal Dimension) [8], TS (Tensor Scale) [9], Fourier [10] and CS (Contour Salience) [11]. The experiments were conducted on a Macintosh Power Mac G5 computer with a PPC970 2.0 GHz (two cores) processor, 4 GB of RAM memory and Debian 6.0.4 as the operating system. The shape descriptors proposed in this work were implemented in the C program- ming language, the same language used by other researchers to implement the descriptors of the literature evaluated [8].
A. Experiment 1 - Kimia-216 database
Kimia-216 [12] is a public image database, traditionally used in experiments with shape descriptors. The Kimia- 216 [12] dataset contains 216 images: 18 classes of objects, 12 images per class. In each image there is a black silhouette of an object drawn on a white background (similar to the ones exhibited in Fig. 2 and Fig. 3). The images of this database have almost the same size (few hundreds of rows per few hundreds of columns).
In order to compare the performances of the shape descrip- tors tested, their Precision-Recall and Multiscale Separability curves were built. These curves are often used in the analysis of the performances of shape descriptors. The higher the curve, the better the method.
Fig. 4a shows the Precision-Recall curves obtained. As one can see, the four best methods were: HTS, HTSn, HTSh and BAS [7]. The Precision-Recall curves of the HTS and HTSn descriptors were slightly inferior (but very close) to the BAS [7] one. The HTSn method obtained better results than the HTS descriptor and, for high Recall values, it presented better Precision results even than the BAS [7] method. The HTSh method presented better results than BAS [7] for a large interval of Recall values. Besides all this, these four best methods presented similar Precision rates for low Recall values (from0 to 0.25). This is an important fact since many applications, like CBIR systems, work, generally, in this region of the curve: with high Precision rates even with low Recall values. In these systems, usually, it is more important to return the maximum number of relevant objects in the limited set returned by a query, than to retrieve all the relevant objects of the database (in this case, the query may also return many non-relevant objects until find the last relevant element).
The Multiscale Separability curves of these four best meth- ods are shown in Fig. 4b. The three proposed descriptors (HTS, HTSn and HTSh) presented much better results than the BAS [7] method. The HTSh descriptor presented the best performance.
The four best methods (HTS, HTSn, HTSh and BAS [7]) spent, in the Feature Extraction phase, i.e., extracting the features of the 216 images of the database, respectively, 9, 11, 11 and 11 seconds. In the Matching phase (performing the 216 · 216 matchings) these methods spent, respectively, 6, 6, 901 and 72 seconds. The HTS and HTSn descriptors are faster than the BAS [7] method, especially in the Matching phase, since they have algorithms with lower complexity. The HTSh descriptor, despite of also presenting an algorithm with
0.0 0.2 0.4 0.6 0.8 1.0 1.2 0.08 0.17 0.25 0.33 0.42 0.50 0.58 0.67 0.75 0.83 0.92 1.00 Pr eci si on Recall Precision-Recall BAS HTSh HTSn HTS MFD TS Fourier CS (a) 0.0 0.2 0.4 0.6 0.8 1.0 1.2 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Separabil ity Search Radius Multiscale Separability HTSh HTS HTSn BAS (b)
Fig. 4. (a) Precision-Recall curves for the Kimia-216 [12] database obtained by the compared methods: BAS, HTSh, HTSn, HTS, MFD, TS, Fourier and CS. (b) Multiscale Separability curves for the Kimia-216 [12] database obtained by the four best methods in terms of Precision-Recall results: HTSh, HTS, HTSn and BAS.
linear complexity, performs many histograms matchings, being slower than the BAS [7] method in the Matching phase. B. Experiment 2 - MPEG-7 Part B database
The MPEG-7 CE-Shape-1 Part B [5] database is another important and public image dataset. This database contains 1400 images (70 classes of objects, 20 images per class). In each image there is a white silhouette of an object drawn on a black background (some examples of these images are shown in Fig. 2 and Fig. 3). The MPEG-7 Part B [5] dataset is more challenging than the Kimia-216 [12] database since, besides of presenting more images and classes, the images have high variable sizes and there are drastic rotation, translation, scale, deformation and noise transformations applied to the silhouettes. There is also a high intraclass variability and high interclass similarity.
The HTS, HTSn and HTSh descriptors as well as the same methods of the literature were evaluated over this database and their Precision-Recall and Multiscale Separability curves were built. Fig. 5a shows the Precision-Recall curves obtained and Fig. 5b shows the Multiscale Separability curves.
The BAS, HTS, HTSn and HTSh methods obtained the best Precision-Recall results again. The performance of the
BAS [7] descriptor was slightly superior to the results obtained by the three proposed methods. As one can observe, the HTSh descriptor was superior to HTS and HTSn.
In terms of Multiscale Separability, the HTSh method obtained the best result. The HTSn descriptor presented a relatively equivalent curve to BAS [7] while the HTS curve was slightly inferior.
0.0 0.2 0.4 0.6 0.8 1.0 1.2 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 Pr ecis ion Recall Precision-Recall BAS HTSh HTSn HTS MFD TS Fourier CS (a) 0.0 0.2 0.4 0.6 0.8 1.0 1.2 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Separabil it y Search Radius Multiscale Separability HTSh BAS HTSn HTS (b)
Fig. 5. (a) Precision-Recall curves for the MPEG-7 Part B [5] database obtained by the compared methods: BAS, HTSh, HTSn, HTS, MFD, TS, Fourier and CS. (b) Multiscale Separability curves for the MPEG-7 Part B [5] database obtained by the four best methods in terms of Precision-Recall