# Introduction

e can recognize different human beings by looking at their faces. To identify an individual, we look at his external face characteristic .We can recognize many faces after several years of separation by comparing their faces outlines characteristics [1,2].

The evolution of computer science aided the researchers to recognize human beings from their faces by using different techniques in the field of image processing and clustering [3,4,5].

Clustering is a grouping of data into clusters of similar objects. Each cluster consists of objects that are similar to each other and dissimilar with the objects of other clusters. Clustering technique represents many data by few clusters and hence, it models data by its cluster in spite of losing certain fine details [6]. The proposed algorithm is clustering algorithm that uses concepts of the graph theory. It classifies the given data into many disjoint clusters by represent each cluster by a tree, and these trees construct a forest (partition). Practically this algorithm is applied to classify the face image of each person of the studied data in one tree. We notice that there is small rate of error in the clustering of the studied data.


# II.

Clustering techniques [5,6,7] Clustering is the classification of given objects into groups (clusters), or more precisely, partitioning of the data set into subsets (clusters) so that the data in each cluster shares some common features, after proximity according to some defined distance measures. Clustering plays an important role in our life, since we encounter a large number of data needed to logical interpretation. This interpretation can be done by classifying these data into a set of categories or clusters. There are many different ways to express and formulate the clustering problems. As a consequence, the obtained results and their interpretations depend strongly on the used way.

The clusters type as follows:

? Exclusive (hard) cluster so that every object must belong to only one cluster. ? Overlapping (fuzzy) cluster so that one object may fall into several clusters. ? Probabilistic clusters so that an object belongs to each cluster with certain probability. ? Hierarchical clusters such that there is a crude division of objects into groups at high level that is further refined into finer level.

The proposed algorithm uses some terms and definitions of the graph theory. The clustering of the given objects depends on the real structure of these objects. In fact, some of the studied objects may be roots of the trees (clusters) that construct a forest (partition) which contains all these objects such that these objects are distributed into different disjoint trees of that forest according to some conditions. If an object y attracts another object x in order to be in same tree then y is called the classifier of x .The attraction process between the studied elements may be as follow:

? Each root of any tree must be the classifier of its successors (children). ? In general, each vertex of any tree is the classifier of its successors (children). ? For each vertex x, there is only one classifier (father). ? There is no classifier for the root of any tree.

? If x, y are two vertices at the same level, then neither

x is classifier of x, nor y is classifier of x.


# III.

Neighborhood [8,9]   Neighborhood operation plays an important role in clustering techniques and digital image processing. The proposed method used the neighborhood operation through its implementation.

There are many ways to express the neighborhood term .We notice in the literature three types of the neighborhood operation: K_nearest neighbor, ??_nearest neighbor, and adaptive neighbor. Adaptive_neighborhood means that we must use an adaptive threshold such each individual of the studied population must have its specific adaptive threshold . In fact, using a constant threshold for all the studied individual in the clustering techniques many give good clustering results, but these results may not be the best. This especially, in case there where a real structure of the studied data that contains many groups that distributed in small regions while some other groups, were located in large regions, the adaptive neighborhood aids to give the best clustering.

In general, the adaptive neighborhoods must be used when the distribution of the studied individuals are not uniformly distributed in the plan (space).

IV.


# Some Concepts of Graph Theory

The following terms and definitions will be used in the proposed algorithm.

1. Graph: A graph G (V, E), consists of two sets V and E. V is a finite non empty set of vertices, E is a set of pairs of vertices, these pairs are called edges (arcs) of the graph There are two types of graphs:-? Undirected graph in which any pair of vertices represents an edge by using unordered pairs. The pairs (v1, v2) and (v2, v1) represent the same edge. ? Directed graph in which each edge is represented by a directed pair such that (v1, v2). Thus, for the ordered pair (v1, v2) there exist only one directed arc from the vertex v1 to the vertex v2.

2. Tree: A tree is a directed graph which has the following properties: ? It has a special vertex R called the root of the tree. R has no precedent vertex (father) and it has one or many successors (children). ? There is no cycle in each vertex of the tree, and there is no cycle between its other vertices. ? It has one or many terminal vertices, such that each one has only one precedent (father) and it has never successors (children). These vertices are called the leaves of the tree. ? Each an intermediate vertex (neither root nor leaf) must have only one precedent and one or many successors.

? There is never connection between the vertices in the same level of the tree. 3. Forest: A forest is the union of the disjoint trees concerned the studied data. 4. Isolated vertex: An isolated vertex is any vertex in the graph which does not connect with any other vertices of the graph. Thus, isolated vertex has never neighborhood

V.


# Graph representation of the proposed method

Each individual of the studied population is represented by a vertex and between any two vertices (except the isolated vertices) there exits an edge according to some conditions. In order to classify the given data, we must compute the adaptive neighborhood for each vertex. The vertices which have never neighborhood are supposed as isolated vertices in the forest. Each no isolated vertex is either a root, a leaf, or an intermediate vertex.

The root is a special vertex which has not classifier (father) and may have one or many successors (children), each leaf of a tree has one classifier and it has never successors, while each vertex which is neither root nor leaf must have one classifier (father) and may have one or many successors. At the end of the execution of the proposed algorithm, some disjoint trees will be noticed and each tree represents its specific cluster.


# VI.


# Related works

In the literature, many papers was found in the field clustering of the human face images. The following are samples of clustering methods that are using the neighborhood operation:

? A clustering algorithm is proposed with some assistant algorithms to classify many different human face images with different rotation angles. It gives good results with small ratio of error [12]. ? Another clustering algorithm was applied to classify some important parts of the human face images by using some important parts (regions) of the human face images. It was noticed that using eyes_ parts gives good clustering results. These results are better than using either the noses_ parts or the mouths _chins_ parts in clustering the same images [13].

VII.


# The proposed method

The basic idea of this method is to use the terms of the tree concepts to classify the individuals of the studied population. Each resulted cluster from this method represents a tree, and all the obtained trees will construct a partition (forest) where these trees are disjoint trees. An element y of the studied population is called the classifier of the element x if y attracts x, and the two elements must belong to the same tree.

The following terms and definitions will be used in the construction of the proposed algorithm.

? E is the studied population(human face images) ? d(x,y) is the Euclidean distance between the two individuals x , y of the set E ? ?? is the proposed constant threshold .

? ?? ?? (x)={ y/y ?? E, d(x,y) < ??) is the set of the neighborhood of the x w.r.t the constant threshold ??. ? Den(x) =cardinal (V (x)) is the density of x (number of neighborhood of x w.r.t the constant threshold ??.

? ?? (x)= ??*den(x), is the adaptive threshold corresponding the individual x.
? V * (x)=V ?? (x) (x)={ y/y E, d(x,y) < ?? (x)
) , is the adaptive neighborhood of x w.r.t the adaptive threshold ??(x) .

? Den * (x) =den ?? (x) (x) =cardinal (V * (x)), is the adaptive density of x w.r.t ?? (x). 


# Algorithm implementation a) Expermintal Results

We applied the proposed algorithm on many selected human face images which were chosen from the ORL database and contains (600) human face images concerning 60 persons with (10) face image for each person [14]. The implementation has been achieved using matlab version 8: 1. The algorithm was firstly implemented on the 1 st hundred human face images of the ORL database by using a constant threshold (9.958) and from this constant threshold we extract the adaptive threshold and the adaptive neighborhood for each image. We secondly used the same approach for the remain hundreds of ORL database. Figure [1] shows a sample of the results of our algorithm on the 1 st hundred of the ORL database images.

No. of cluster Images of the Tress(clusters) 1  Table 1 : Compression between the results of experiments 3. Two types of errors have been noticed: ? In few cases, face images for more than one person are lied in same cluster. This occurred for the most resemblance persons as shown in cluster (5) of figure [1]. ? The face images of some person were partitioned in two clusters. This occurred when we use a small value for the constant threshold as shown in clusters (3,4) of figure [1].

We conclude the following for the proposed algorithm:

1. It's an automatic algorithm since it does not need to give the number of the resulted clusters a priori. In fact the obtained results simulate the real structure of the applied data. 2. It's a hard clustering algorithm since its clustering results are such that the face images of each person will be in the same tree (cluster). 3. Using adaptive threshold is better than using constant threshold. 
![Author ? : Computer Science Dept. -Education College-Thi-Qar University.](image-2.png "")
![K_nearest neighbors mean that for each individual of the studied population, we must propose a positive integer k which determines the k individual which must be the nearest for any given individual.? ??_nearest neighbors mean that for each individual of the studied population this individual is supposed as a center of a circle (ball) of radius ??, then the ??_nearest neighbor of that individual are all the individuals of the studied population whose locations are either inside or on this circle (ball).](image-3.png "?")
![Algorithm Pretreatment For each x ?? E, do the following: ? Determine its adaptive neighborhood V * (x) ? Compute its adaptive density den * (x) 2. Construction of forest trees If (den * (x) =1) then X is supposed as an isolated individual in the graph. Else y V * (x) , y ? x , compute the following: ? ?? xy =(den * (x)-den * (y))/d(x,y) ? ?? x = min ?? xy , y V * (xSearch for an element w in V * (x) such that ?? xw = ?? x Take w as the classifier of x (if there are many w such that ?? xw = ?? x then choose one of them randomly ) Else Define the following sets: ? T={ y/y V * (x), and ?? xy =0}, where T= at the beginning of the execution. ? F= {z ? T, and x is the classifier of z}. ? M=T-F. If (M ? ) then Determine a such that d(x, a) =min (d(x,y), y ?? M, take a as the classifier of put x and a at the same tree . Else X is a root of a tree End if End if VIII.](image-4.png "")
12![Figure 1 : Sample of clustering result by applying the proposed algorithm on the 1 st hundred images of the ORL database 2. The same technique was used with all the data of the ORL data. Fiqure [2] shows a sample of the obtained results by using the proposed algorithm on the images of ORL(600 images)](image-5.png "Figure 1 :Figure 2 :")
4![It's an effective clustering algorithm, since it gives a good clustering results with small rate of error and it taken a reasonable execution time for all the experiments.](image-6.png "4 .")
		
		
			

				


* 
	
		Matching of Face in a Camera Image and Document Photographs
		
			VStarovoitov
		
		
			Samal
		
		
			Sankur
		
		
			1997
			Min, Belarus
		
		
			Institute of Engineering Cybernetic Suraganora
		
	




* 
	
		Finding Face Features
		
			ICraw
		
		
			D
		
		
			ABeautt
		
	
	
		proc.2 nd Europ Conf. on Computer Vision
				.2 nd Europ Conf. on Computer Vision
		
			1992
			
		
	




* 
	
		Computer Recognition of Human Face
		
			T
		
	
	
		Based and Styttgrat
		
			1977
		
	




* 
	
		
			RCGonzalez
		
		
			Wintz
		
		Digital Image Processing
				
			Addision -Wesely Publishing company
			2002
		
	




* 
	
		Data Clustering Review
		
			AKJain
		
		
			MNMurty
		
		
			PJFlynn
		
	
	
		ACM Computing Survey
		
			3
			1999
		
	




* 
	
		Comparison Between Data Clustering Algorithms
		
			AbbasOsama Abu
		
	
	
		International Arab Journal of Information Technology
		
			5
			3
			2008
		
	




* 
	
		Clustering with k-nearest Neighbors Threshold of Edge Detection
		
			ZChen
		
		I. J. C. P. R. Koyoto
		
			1978
		
	




* 
	
		Cluster Analysis
		
			MMooi
		
		
			Sarstedt
		
		
			2011
			Spring-Verlag Berlin idelberg
		
	




* 
	
		An Atternative Definination for Neighborhood of a Point
		
			JFO ' Callachan
		
	
	
		IEEE, Trans. Computer
		
			24
			1975
		
	




* 
	
		Graphs and Their Uses
	
	
		New Yourk, Random House and the L.W., Spring Company
				
			1978
		
	
	Ore Oystein




* 
	
		Applied Graph Theory
		
			WKChen
		
		
			1971
			North. Holland Publ
			Amsterdam
		
	




* 
	
		Clsutering of Human Face Image with Different Rotation Angles
		
			TJassim
		
		
			KadhemMSarsoh
		
		
			Hashem
		
	
	
		Thi-Qar Journal
		
			3
			2007
		
	




* 
	
		Effects of Facial Segments Features on Human Face Classification
		
			TJassim
		
		
			Saraoh
		
	
	
		Journal of Basreh Researches / Sciences
		
			34
			1
			2007