Abstract

To measure similarity between face shapes, quadrant based vertical distance method is proposed. The face shape curve is divided into 4 quadrants with the centroid of the curve as origin. The face shape curve on each quadrant is represented with a list of the distance of any boundary point on the quadrant to horisontal axis of the same quadrant. The nearest point from vertical axis at each quadrant is choosen as starting point to obtain rotation invariant. This representation aimed to describe dominant characteristic of face shape curve represented by the curvature of curve at upside and downside. To measure similarity between shape representation, a Fuzzy Euclidean distance method is proposed. A zmf membership function is used to map the Euclidean distance of 2 descriptor’s components to certain similarity value [0, 1]. Experimental result on 345 faces shows that quadrant based vertical distance method is more efficient and gives average precision 28% improved than those of the conventional method. This result shows that the proposed method is promising to be used for face retrieval and recognition system.

---

INTRODUCTION

Shape is one of the low level features besides color and texture that is used in a lot of image retrieval systems (Wang and Dai, 2007; Gorbel, 1992; Kunttu et al, 2003; Zhang and Lu, 2003; Lee et al., 2003; McElroy et al., 1995). Shape is important in representing significant regions in image and can be sufficient to recognize objects without other visual cues (Zhan and Roskies, 1972). There are 2 methods to represent shape, region based and contour based (Zhang and Lu, 2003). Among the contour based methods are shape signature and spectral descriptor. Shape signature represent shape based on edge of curve and represented as complex coordinate or centroid distance (Zhang and Lu, 2003). Spectral descriptor represents shape on frequency domain by transform shape signature with Fourier transform or wavelet transform. This representation is more robust to noise and have been implemented on shape analysis (Purcoru, 1998) shape coding (Zhang and Lu, 2003; Lee et al., 2003; Zhan and Roskies, 1972; Toth and Aach, 2003), shape classification (Kunttu et al., 2003; McElroy et al., 1995) and shape retrieval. Besides shape representation, another problem on image retrieval system is how to measure similarity between shape representation. To measure similarity, there are 2 categories of similarity measure, i.e., conventional method based on metric, i.e., distance (Kulkarni, 2007) and fuzzy based method (Tian et al., 1996; Omhover et al., 2004; Chen and Chu, 2005).

Regarding the development of face retrieval system based on shape query, there are 2 problems to address, i.e., shape representation and similarity measure. There are 2 challenges on defining shape representation for face. First, distinction between face shape type is difficult. Second, it is hard to formulate mathematic equation for a face shape type. Although, the distiction between face shape type is difficult, the shape representation should represent face shape type and can be used to distinguish 2 different face shape types. After shape representation is acomplished then similarity measure between shape representation should be defined and must represent similarity as sameness on face shape type. To overcome this problem, quadrant based vertical distance method is proposed. The face shape curve is devided into 4 quadrants with the centroid of curve as the origin. The face shape curve on each quadrant is represented with a list of the distance of boundary point to horisontal axis on the quadrant. The nearest point from vertical axis at each quadrant is choosen as starting point to obtain rotation invariant. This representation describes dominant characteristic of face shape curve represented by the curvature of the curve at upside and downside. To measure similarity between face shape, Fuzzy Euclidean distance method is applied. A zmf membership function is used to map the Euclidean distance of 2 descriptor’s components to a certain similarity value [0, 1]. This approach overcome the drawbacks of centroid to boundary distance-based face shape representation.

CENTROID TO BOUNDARY DISTANCE METHOD

Centroid to boundary distance method can be categorized as shape signature and represent shape as a list of distance from center point to boundary point of face shape curve. This method has been used to represent face shape look from sideview (Liposcak and Loncaric, 1999). Representation of face shape using centroid to boundary distance method is shown at Fig. 1.

Shape representation using centroid to boundary distance method is shown at Fig. 2. Shape is represented by 1-Dimensional function of distance between center point to boundary point. The center point of face shape curve is defined as:

(1)

where, (x_i, y_i) is coordinate of i-th boundary point. Distance between center point to i-th boundary point is defined as:

(2)

 

Fig. 1:	Shape representation with distance to center point method of face shape

 

 

Fig. 2:	Centroid to boundary distance approach

 

where, (x_c, y_c) is center point. This representation is obtained to achieve translation invariance. A point with orientation 180° from the center point is chosen as starting point of shape representation to achieve rotation invariance. To ensure that 1 point from 1 shape representation is compared with the match point from other then an angle based resampling point is accomplish.

There are 2 drawbacks of centroid to boundary distance method that reduce retrieval performance. First, this representation can not describe correctly the dominant characteristic of face shape shown by the curvature of face shape curve at up side and down side. Second, difficulties on identify the position of dominant characteristic of face shape in shape representation make impossible to apply weighting factor on similarity value to improve retrieval performance.

QUADRANT BASED VERTICAL DISTANCE METHOD (PROPOSED)

In order to overcome the drawbacks of boundary to centroid distance method, there are 2 techniques can be implemented. First, To represent dominant characteristic of face shape shown by the curvature of face shape curve at up side and down side then face shape must be represented with vertical lines connect a point at face boundary to a reference horizontal line, i.e., horizontal axis. Second, dividing face shape curve into 4 quadrant ensure that matching between shape representation is conducted in correct postition. This partition also intended to accommodate condition that the left and right fraction of face shape does not always symmetry.

 

Fig. 3:	Quadrant based vertical distance approach

 

 

Fig. 4:	Face shape representation using quadrant based vertical distance method

 

Quadrant also makes possible to implement weighting on similarity value. A Larger weighting factor can be applied to the fractions of face provide major contribution in identify face type (i.e., downside fractions). Approach that bring togather these 2 techniques so called quadrant based vertical distance method.

Quadrant based vertical distance method for shape representation is obtain by the following steps: First, find the centroid of the face shape curve by Eq. 1. 2nd, make horizontal and vertical axis with the centroid as origin. These axis is used to devide face shape curve into 4 quadrant (Fig. 3). Shape representation of each quadrant is obtain by calculate the distance between any boundary point to the horizontal axis. The nearest point from vertical axis at each quadrant is choosen as starting point to obtain rotation invariant. Then, a sequence of distance is stored in a list. Figure 4 shows representation of face shape in quadrant based vertical distance.

SIMILARITY MEASURE

The approach to provide rank to face images based on the shape similarity with respect to the query shape is conducted by comparing the shape representation of face image in database with shape representation of the query. To achieve the goal of retrieval system then similarity value between face shape must be related with sameness in face type.

Fuzzy euclidean distance: Euclidean distance or also considered as Minkowski distance with p = 2 is a common distance measurement. Similarity measure between shape representation x and y is computed by distance function δ(x,y) where, similarity is defined as 1-δ(x,y). Euclidean distance between 2 point is defined as

(3)

where, x and y is feature vector of compared image.

Fuzzy Euclidean distance maps this Euclidean distance to similarity value [0, 1] use advantage of zmf fuzzy membership function. The main idea of this implementation is to map acceptable distance to similarity 1, unacceptable distance to similarity 0 and make smooth transition between 0 and 1. Similarity value by a zmf function is defined as:

(4)

where, x is Euclidean distance between 2 compared element, a and b is extreme of the slope of curve. Graphic representation of zmf function shown in Fig. 5.

Mapping distance to certain similarity value by taking adventage of a zmf function is aimed to resolve fuzzyness of face shape type caused by variation on face shape type. It also aimed to remove affect of the inaccurateness of extraction result caused by fuzzyness of face boundary. Similarity among face shape based on face type is obtained by implementation of fuzzy Euclidean distance function.

Fuzzy similarity measure: Fuzzy similarity measure is applied to obtain global similarity measure between 2 face shape. Fuzzy similarity measure is applied with adjusting weighting factor of each quadrant. Fuzzy similarity between face shape defined by equation:

 

Fig. 5:	a zmf function with [a, b] = [3, 7]

 

(5)

where, w₁, w₂, w₃, dan w₄ is weight factor for quadrant 1, 2, 3 and 4, respectively and w₁ + w₂ + w₃ + w₄ = 1.

Quadrant III and IV is assigned with greater weighting factor than quadrant I and II because the similarity between face shape is dominated by equality of curvature on quadrant III and IV. The assigning small weighting factor on quadrant I and II also aimed to reduce inaccuracy on measurement caused by imprecision of boundary extraction at up side. The difficulties on boundary extraction caused by the face boundary obscured by hair.

RESULTS AND DISCUSSION

To show performance of proposed method, experiment is conducted to compare quadrant based vertical distance-based face shape repesentation using Fuzzy Euclidean distance as similarity measure function (QbVD) and centroid to boundary distance-based face shape representation using Euclidean distance (BtoCD). The experiment is conducted on a database that contains 345 faces from 4 face shape categories (oval, round, triangle and square).

 

Fig. 6:	Screenshot of face retrieval system based on face shape query

 

The experiment is conducted on interface that shown at Fig. 6. The user input the shape query by select the shape from template at ''sinyalemen wajah''. At the next steps, user must choose the extraction method and similarity measure from the combo box "Deskriptor" and Kemiripan, respectively. To start searching user must click button Search on Database.

The testing is performed by using one sample of each category as a query. Ideally, similar image (i.e., image from the same category) should be retrieved in higher ranks. The performance of the system is measured based on computation time and recall precision. Computation time defined as extraction time plus searching time. Recall precision are the most common evaluation measure in information retrieval.

 

Table 2:	Computation time of face retrieval system based on shape query (on millisecond)

 

Fig. 7a-e:	Interpolation of precision recall of each query image 1, 2, 3, 4 and average precision recall

Recall is the fraction of the relevant documents which has been retrieved and precision is the fraction of the retrieved documents which is relevant as define in Equation (Manning et al., 2007):

(6)

(7)

Then to get precision value on eleven standard recall point interpolation is conducted with (Manning et al., 2007):

(8)

where, precision at j-th standard recall is the maximum precision at recall between j-th recall point and (j+1)-th recall point.

To evaluate the retrieval performance of system over all test query, average precision is calculated from precision values at different recall levels. Figure 7 show the interpolation of precission and recall of experimental result. Precision and recall calculated just for top 10 retrieved image.

Figure 7a-d show the interpolation of precision and recall from each query. Differentiation of recall point for each query shows that shape representation is not sufficent yet to represent all face type. Figure 7e shows the average precision recall from over all test query. Average precision of overall query with BtoCD method is 47% and QbVD is 75%. The average precision with QbVD increase 28%. Improvement of average precision shows that the goal of applying similarity measure based on Fuzzy theory is obtained.

This achievement shows that fuzzyness on face shape type caused by variation of face shape can be handled with similarity measure based on Fuzzy theory. Similarity as identical face type can be achieved by mapping distance between 2 compared element of shape representation to similarity value with zmf function.

Table 2 represent the computation time (feature extraction and searching time) of the compared methods. Although, searching time of QbVD-based method increase significantly, the total computation time of QbVD-based still faster then BtoCD-based. This increasing of time consuming by QbVD method caused by 2 steps added on similarity measure, i.e., mapping Euclidean distance to zmf function and applying fuzzy similarity measure. Graphic representation of computation time shown at Fig. 8.

 

Fig. 8:	Computation time of BtoCD-based and QbVD-based method

 

CONCLUSION

Vertical quadrant distance-based face shape representation is proposed to represent the fuzzyness of face shape type. In this method, face shape is represented with 4 list of distance between boundary point to horisontal line from 4 quadrant. To measure similarity between face shape, Fuzzy Euclidean distance method is applied. A zmf membership function is used to map the Euclidean distance of 2 descriptor component to a certain similarity value [0, 1]. Global similarity is obtain using fuzzy similarity measure. Similarity measure achieve by similarity value represent similarity between face shape based on face type. To show performance of the proposed method, comparation with boundary to centroid distance method is done.

Experimental result shows that computation time of vertical quadrant distance method faster then boundary to centroid distance method. The average precision of boundary to centroid distance method achieve 47% and average precision of quadrant based vertical distance method achieve 75%. It can be concluded that quadrant based vertical distance method can describe dominant characteristic of face type and reduce fuzzyness of face type.

The development of system based on the proposed method demonstrates the real applicability of face retrieval system. This result shows that quadrant based vertical distance method improves retrieval performance and can be used as the part of the component based face retrieval system.

ACKNOWLEDGEMENT

The author wish to thank the center of identification of Indonesian Police Office for giving information about identification process of criminal. This research is supported by University of Indonesia Competitive Research Fund.

How to cite this article:

M. Rahmat Widyanto and Binti Solihah . Quadrant Based Vertical Distance Method for Face Shape Representation.
DOI: https://doi.org/10.36478/ijscomp.2009.25.31
URL: https://www.makhillpublications.co/view-article/1816-9503/ijscomp.2009.25.31