# INTRODUCTION he recognition of characters from scanned images of documents has been a problem that has received much attention in the fields of image processing, pattern recognition and artificial intelligence. For many years, fuzzy logic and Artificial Neural Networks have been used in a wide range of problem domains: process control (where Fuzzy Controllers have been very popular), management and decision making, operations research, economics and pattern recognition and classification. This paper presents an application of both SOM neural network and fuzzy k-Nearest Neighbor in recognition of handwritten Tifinagh characters. This paper is organized as follows: in section [1] a features extraction method, which is an essential step prior to pattern recognition, is described. Section [2] describes the architecture and the learning mechanism of the SOM neural networks. Section [3] presents the k-Nearest Neighbor algorithm. Section [4] gives results of the application of both SOM and Fuzzy k-NN on Tifinagh handwriting character recognition. # FEATURES EXTRACTION Preprocessing techniques like thinning, slant correction and smoothening are applied. For extracting the features, the Box approach proposed in [1] is used here. This approach requires the spatial division of the character image. The major advantage of this approach stems from its robustness to variation, ease of implementation and high recognition rate. Each character image is divided into L × H boxes so that the portions of character will be in some of these boxes. There could be boxes that are empty (Figure 1(a)). The choice of number of boxes is arrived at by experimentation. Elements of a Normalized Vector that describe the character is obtained by dividing the number of all black pixels present in this box by their total number for each box, (Figure 1 (b)). One can easily see that this characterization is invariant of the character image dimensions. Hence an image of whatever size gets transformed into a vector of L × H predetermined dimensions. # SELF ORGANIZING MAP (SOM) The Self-Organizing Maps, abbreviated SOM, was developed by Professor Teuvo Kohonen in the early 1980s. Self-organizing maps are a special class of artificial neural network, because those are based on competitive learning and the learning itself is unsupervised. Also SOM is considered as a special case in data-mining, it can be applied to both clustering and projecting the data onto a lower dimensional display at the same time. In a SOM network, there is an input layer and an output layer which is usually designed as twodimensional arrangement of neurons that maps n dimensional input to two dimensional (Figure 2). It is basically a competitive network with the characteristic of The algorithm proceeds first by initializing the synaptic weights in the map for the neurons. This can be done by assigning them small values picked from a random number generator; in so doing no prior order is imposed on the feature map. Once the map has been properly initialized, there are three essential processes involved in the formation of the self-organizing map: Competition, cooperation and synaptic adaptation. for j=1,2,?,l (l is the number of output neurons) and select the largest denoted ) ( X i . Maximizing X W T j . is equivalent to minimizing X W j ? [2] then one can have: ( ) X W X i j j ? = min arg ) ((1) The neuron number ) ( X i is called the winning neuron. b) Cooperation 1. i j h , is symmetric and attains its maximum value at the winning neuron i for which i j d , =0. A typical choice of i j h , is the Gaussian function # The amplitude of ? ? ? ? ? ? ? ? = ) ( 2 , 2 2 , ) ( k d i j j i e k h ? (2) ? ? ? ? ? ? ? ? ? = 1 0 ) ( ? ? ? k e k (3) Where 1 ? is the time constant of the algorithm. c) Synaptic adaptation By definition, for the network to be selforganizing (and unsupervised), the synaptic weight vector j W of neuron j in the network is required to change in relation to the input vector X. This change is expressed by the equation as follows: ( ) ) ( ) ( ) ( ) ( ) 1 ( ) ( , k W X k h k k W k W j X i j j j ? + = + ? (4) Where ) (k ? is the learning-rate. The exact form of learning-rate is not important. It can be linear, exponential or inversely proportional. However it should be time varying. In particular, it should start at an initial value 0 ? , and then decrease gradually with increasing time n. This requirement can be satisfied by using an exponential learning-rate, as shown by: ? ? ? ? ? ? ? ? ? =2 # FUZZY K-NEAREST NEIGHBOR Fuzzy kNN is part of supervised learning that has been used in many applications in the field of data mining, statistical pattern recognition, image processing In neurobiology, a neuron that is firing tends to excite neurons in its immediate neighborhood more than those farther away. The same with output neurons in the SOM, a topological neighborhood around the winning neuron i is made and it decay smoothly with lateral distance. Another unique feature of the SOM algorithm is that the size of the topological neighborhood shrinks with time. Let ) ( , k h i j denote the topological neighborhood at time k, centered on the winning neuron i, and j denote a typical neuron of a set of excited (cooperating) neurons around winning neuron i. On can assume that the topological neighborhood i j h , is unimodal function of the lateral distance j i d , , such that it satisfies: and many others. Some successful applications are including recognition of handwriting and satellite image. Fuzzy K nearest neighbor algorithm is very simple. It works based on an unsupervised clustering algorithm like fuzzy k-means algorithm to determine prototypes representing clusters. Then the minimum distance from the query instance to these prototypes is used to determine the K-nearest neighbors. After and basing on membership function we take the neighbor with the maximum membership to be the prediction of the query instance. # a) Fuzzy k-means The Fuzzy k-means clustering algorithm is an improvement of the k-means algorithms. K-Means are the simplest methods of clustering data. The fuzzy Kmeans algorithm uses a set of N unlabeled feature vectors and classifies them into k classes, where k is given by the user. From these N feature vectors, k of them are randomly selected as initial seeds. The feature vectors are assigned to the closest seeds depending on its distance from it and on a given membership function. The mean of features belonging to a class is taken as the new center. The features are reassigned; this process is repeated until convergence. In a fuzzy clustering, a pattern vector can belong to all clusters with different degrees given by a membership function [figure 4]. One can prove that such a function exists [5], and for each cluster i C it is defined as follows: ( ) 2. Compute the degree of membership of all feature vectors j X in all clusters ) ( : 1 , ) , ( / 1 , / 1 ) ( 1 1 1 2 1 1 2 ? ? ? = ? = ? ? m m c X d c X d X f N i m i m i i (6)j i ij i X f C = µ . 3. Compute new cluster prototypes as follows: ( ) ( ) ? ? = = = N j m ij j N j m ij i x c 1 1 µ µ (7) c) Fuzzy K -Nearest Neighbor The Fuzzy k-NN classifiers consist on proximity measures. They are ideally suited for modeling the non parametric distribution on handwritten word recognition data. For a given character X, the fuzzy classifier computes the membership of X in different classes N C C C ,...... , 2 1 . The character X is allocated to the class for which the membership function yields the maximum value. By a learning process (Fuzzy k-mean, k-mean, LVQ ...) we assign a number of prototypes j P for each class i C . After generating the k-Nearest Neighbor prototypes j P for a character (by distance similarity), the degree of membership of the vector X to the class i C : ) ( X i µ , can be calculated as follow: ( ) ( ) ? ? = ? = ? = N i m j k i m j ij i P X d P X d X 1 1 1 2 1 11 2 , / 1 , / ) ( µ µ # RESULTS A java application was developed in order to test and compare those two algorithms. To extract features each, character was divided into boxes, the input layer of the SOM neural network was made of 63 neurons and 35 for the output layer (number of character to recognize), for the fuzzy k-nearest neighbor the fuzziness factor m is equal to 2 and number of neighbors' k is equal to 3. 4. Iterate back and force between (2) and (3) until the memberships or cluster centers for successive iteration differ by more than some prescribed value ?. As there is no standard database available for handwritten Tifinagh characters, a database was created from samples of different writing styles with different sizes. The database also includes some complex samples that are even hard to recognize by careful inspection Figure 5: Samples used for training (figure 5). This database contains 200 samples (about 5 samples per character) divided into two disjoint sets, one for training both SOM and Fuzzy k-NN, and another for testing these two algorithms. The features extraction method used here is scaling invariant, that's why there is always a recognition problem between Tifinagh character and , where 's are mistaken as 's and vice versa. Some other recognition problems are with and , and but not persistent as the first one. Experiments shows that the best results are given by the Fuzzy k-NN where in many cases it success to recognize handwritten characters that SOM # CONCLUSION In this paper two clustering algorithms are presented, Self Organizing Map neural network and the Fuzzy k-Nearest Neighbor. We applied these two algorithms to Tifinagh character recognition. The box approach was used to extract features from the character image. Fuzzy k-NN was more robust and fast than the SOM. 1![Figure 1 : Features extraction](image-2.png "Figure 1 :") ![Computer Science and Technology Volume XI Issue XV Version I self-organization providing a topology-preserving mapping from the input space to the clusters.](image-3.png "") 21![Figure 2 : SOM architecture a) Competition Let](image-4.png "Figure 2 1 =") 2![is another time constant of the SOM algorithm.](image-5.png "2 ?") 3![Figure 3 : example of topological neighbourhoods (Gaussian)](image-6.png "Figure 3") ![Where i c is the center of the class i C , and The parameter m is defined by the user to adjust the fuzziness of the clustering. The hard clustering case is b) Fuzzy K-means algorithm 1. Choose randomly the k prototypes i c .](image-7.png "") ![Computer Science and Technology Volume XI Issue XV Version I Recognition of Tifinagh Characters Using Self Organizing Map And Fuzzy K-Nearest Neighbor obtained by taking m = 1.](image-8.png "") 4![Figure 4 : Membership function](image-9.png "Figure 4 :") © 2011 Global Journals Inc. (US) © 2011 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XI Issue XV Version I ## This page is intentionally left blank Recognition of Tifinagh Characters Using Self Organizing Map And Fuzzy K-Nearest Neighbor 34 * Fuzzy Model Based Recognition of Handwritten Hindi Numerals using bacterial foraging MHanmandlu AVNath ACMishra &V KMadasu 2007 6th IEEE/ACIS ICIS * Neural Networks: a comprehensive fondation &Haykin Simon 1999 Prentice-hall inc New jersey * Comparing SOM neural network with Fuzzy c-means, K-means and traditional hierarchical clustering algorithms AMingoti SLima JO European Journal of Operational Research 2005 * Segnal processing, Image processing and Pattern recognation DSlezak BKang-Junzhong TKim &GKuroda Springer New York * JSagau Logique flou en classification. Techniques de l'Ingénieur , H3638 * September Global Journal of Computer Science and Technology Volume XI Issue XV Version I Recognition of Tifinagh Characters Using Self Organizing Map And Fuzzy K-Nearest Neighbor Engineering and Technology * K-Means-based fuzzy classifier FZheng * A Modified Fuzzy K-means Clustering using Expectation Maximization SNasser RAlkhaldi GVert * Signature pattern recognition using psudo Zernike moments and fuzzy logic classifier PNassery KFaez * Handwritten character recognition using neural network architectures OMatan RKKiang CEStenard BBoser 4th USPS advanced Technology Conference Washington D.C 1990 * A Modified Fuzzy K-means clustering using expectation Maximization SNasser RAlkhaldi &GVert * STheodoridis KKoutroumbas Pattern recognation Elsevier 2009 fort edition * Handwritten Character Recognition Using Multiscale Neural VGanapathy KLLiew 2008