Takwa Chihaoui
email: takwa.chihaoui@esiee.fr

Rostom Kachouri
email: rostom.kachouri@esiee.fr

Hejer Jlassi

Mohamed Akil
email: mohamed.akil@esiee.fr

Kamel Hamrouni
email: kamel.hamrouni@enit.rnu.tn

Human Identification System based on the detection of Optical Disc Ring in retinal images

Keywords: Biometrics, retinal images, preprocessing, image enhancement, Optical Disc Ring (ODR) extraction, Scale Invariant Feature Transform (SIFT) descriptors

Retinal identification is being studied as a hot research topic in the biometric field. Many factors such as the poor quality of retinal images and the huge execution time can seriously affect the performance of the retinal identification systems. In this context, in order to compromise the quality and the processing time, this paper presents a human identification system based on a new preprocessing method of retinal images that we call optical Disc Ring detection method. The proposed ODR method consists of three phases: image quality improvement in order to enhance the contrast of input retinal image, the optical disc center detection and the extraction of an interest ring around the detected center which contains the densest retinal information. This proposed method was integrated in an identification system based on SIFT features and evaluated using a subset of the VARIA retinal database. The correct identification rate was found to be 99.89% while the reached execution time is very lower than other existing identification systems.

I. INTRODUCTION

Nowadays, with the advance in technology, biometrics becomes an improved interest for people identification or authentification. Indeed conventional personnel authentification systems based on map ID or password are vulnerable. It is very easy to forge an identity card or to imitate a signature. A solution to these problems has been found in the technology based on biometric authentification. Biometrics is an emerging field of technology using distinguishing and measurable morphological and behavioral characteristics that can be processed to established the automatic recognition and identification of individuals. In fact, behavioral biometrics is based on the analysis of certain behavior of a person such as voice, signature and keystroke. However, morphological biometrics includes fingerprint, palmprint, hand geometry, vein, face, iris, retina and ear. The eye offers the most reliable biometric features which are the iris and the retina [START_REF]Biometrics Consortium homepage[END_REF]. The iris has enjoyed great interest from researchers and many biometric systems based on the iris are installed in secure locations such as airports [START_REF] Yong | Biometric personal identification based on iris patterns 15th ICPR[END_REF]. On the other hand, because of the difficulty of the fundus image acquisition, the retina has not had an important interest in the beginning. As known to be very reliable and difficult to forge, Carelton Simon and Greg Heacok [START_REF] Chandrasheckar | Human recognition System based on Retina Vascular Network Characteristics[END_REF] were interested in the biometrics by the retina and had marketed 2002 by the first prototype of the retina device acquisition. This retina recognition is an automatic method based on a robust and distinctive feature in order to identify individual or verify its claimed identity [START_REF]Christel -Loc TISSE Contribution la vrification biomtrique de personnes par reconnaissance de liris[END_REF]. Indeed, the uniqueness of the retina blood vessels is not easy to replicate or forge; in addition it is free from the surroundings effects. In this context, it can be considered as the most accurate among the unique, universal and time-invariant patterns. However, personal identification systems based on retina can suffer from some problems. On the one hand, due to the acquisition process of the retinography, retinal images often suffer from imperfections such as poor gray level contrast and background intensity variation. These defects can seriously affect features extraction and reduce the retinal identification rate as consequence. On the other hand, the retina has a dense structure of vessel information which increases the execution time of identification systems. In order to overcome these problems, we propose in this paper a new and robust method to preprocess retinal images. It aims principally to improve the quality of input images and reduce the processing time of the identification system. The identification task in the proposed system is based on SIFT description, which is invariant to the affine transformations such as rotation, scale changes and translation. This paper is organized under five sections as follows: Section 2 presents state of the art for retinal image preprocessing. In section 3, the proposed method is explained and its general flowchart is described. Section 4 presents the experimental results and discussion. Finally, conclusion is drawn in last section.

II. STATE OF THE ART

The automatic analysis of retinal images is a difficult task because images taken at standard examinations could contain artifacts and are generally poorly contrasted. Non-uniformity of illumination raises the intensity levels in some regions of an image, while other regions farther away from the optical disc may suffer from a reduction of brightness. In this context, various methods have been proposed in order to improve the quality of retinal images. Existing methods that focus on the preprocessing of retinal images can be generally grouped as: Vessel extraction-based methods and improved quality of retinal image-based methods.

A. Vessel extraction-based methods

For this class, the aim is to obtain a binary image as an input for feature extraction step. For example, in their personal recognition system, Ortega et al. [START_REF] Ortega | Biometric Authentification Using Digital Retinal Images[END_REF] employed a fuzzy circular Hough transform to localize the optical disc in the retina image. They obtain as a result of preprocessing a crease model of the retinal vessels inside the optical disc. This method may give a false detection of optical disc. In order to improve and reduce the false localization of optical disc, Tabatabaee et al. [START_REF] Tabatabaee | A Novel Human Identifier System Using Retina Image and Fuzzy Clustering Approach[END_REF] proposed a biometric system based on a new approach of preprocessing by localizing the optical disc using Haar wavelet and snake model. The most problem of this method is that the optical disc localization strongly depends on the selection of the initial contour active. Indeed, the choice of the initial contour is very important to reduce the false optical disc detection. To avoid the experimental involvement, Farzin et al. [START_REF] Farzin | A Novel Retinal Identification System[END_REF] proposed an automatic preprocessing method based on a local contrast enhancement process. This method consisted of four steps: First, the optical disc of the retina is located using a template matching technique. Therefore, they employed a correlation technique in order to delete undesired brightness effect of the optical disc. Then, a contrast enhancement method based on statistical properties is ensured. Finally,an histogram thresholding is used to obtain a binary image containing blood vessel. The information extracted from the vascular tree is generally incomplete because of the convergence of multiple plies. Also, some micro vascular segments can not be extracted effectively. Hannu Oinonen et al. [START_REF] Hannu Oinonen | Identity verification based on vessel matching from fundus images[END_REF] used the multiscale enhancement approach proposed by Frangi et al. [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF] in order to overcome the problem of lack of some micro vascular information. Then, the p-tile thresholding is applied to extract binary images. The major drawback of this class is that the output binary image may suffer from the discontinuity of some vascular segments which can affect the feature extraction and cause mismatching.

B. Improved quality of retinal image-based methods

This class focuses on the improvement of retinal image without using a binarization process. Marn et al. [START_REF] Marn | A new supervised method for blood vessel segmentation in retinal images by using gray-level and moment invariants-based features[END_REF] proposed a preprocessing method for blood vessel segmentation. It is based on a background homogenizing method. They estimated the background of the retina by a filtering operation with a large arithmetic mean kernel. Xianjing Meng et al. [START_REF] Meng | Retinal Identification Based on an Improved Circular Gabor Filter and Scale Invariant Feature Transform[END_REF] proposed a new system for identifying people by the retina based on an advanced circular Gabor filter tool and the iterated spatial anisotropic smooth method in order to reduce the noise in homogeneous regions. It is an efficient method but it suffers from an important execution time. Hejer Jlassi et al. [START_REF] Hajer | Caractrisation de la rtine en vue de llaboration dune mthode biomtrique didentification de personnes[END_REF] used the top-hat transform with a linear structuring element at different orientations in order to enhance the vascular tree followed by a contrast enhancement as a preprocessing step. The most problem of this category is that is very timeconsuming. In order to overcome these problems, we are going to propose a new preprocessing method which enhance the retinal image and extract the region with the high density of vessel information. Segmentation and binary vessels extraction are not needed in this approach. So, the computational complexity of the image matching algorithm is low compared to other recent identification systems.

III. PROPOSED ODR METHOD

The optical disc is the brightest area in the digital retinal images where blood vessels converge. Its detection is very important since it is the core of vessel information. We propose a method for preprocessing the retinal image that we call ODR method by determining the position of the optical disc, a threestep algorithm is used: fist, the contrast-Limited Adaptative Histogram equalization is applied in order to enhance the entire input image. Then, the sauvola binarisation is employed in order to detect the center of the most brilliant region of the retina. The final step consists of extract a ring interest around the detected center to be served as an input image for SIFT feature generation. The different designed steps are well described in the figure 1.

A. Image quality enhancement

Due to the acquisition process of the retinography, retinal images may present lighting defects and background intensity variation. In our proposal, the adaptive contrast histogram equalization technique [START_REF] Tang | Image enhancement using a contrast measure in the compressed domain[END_REF] is applied to retinal grayscale images to perform the contrast enhancement in order to remove these imperfections. This technique enhances the contrast adaptively across the image by limiting the maximum slope in the transformation function. Instead of applying the histogram equalization on the entire image, it is applied only on small tiles in the image. After that, the neighboring tiles are combined using bilinear interpolation to reduce induced boundaries. Figure 2 illustrates the histograms of the input retinal image an the enhanced one.

B. Optical disc Detection

The optical disc localization follows two steps: First, the Sauvola binarization method [START_REF] Sauvola | Adaptive document image binarization, Pattern Recognition[END_REF] takes the grayscale enhanced image as input to separate brighter regions from dark background. In this algorithm, a threshold T at each pixel is computed with the dynamic range (R) of the standard deviation using the equation (1):

T = m(1 + ks/(R -1)) (1)
Where m and s are respectively the mean and standard deviation of a given window centered on the current pixel and k is a fixed value. At the next step, we compute the Euclidean distance of the binary image. For each pixel in this image, the distance transform assigns a number that is the distance between that pixel and the nearest non zero one in the image. Finally, we compute the minimum of the resultant image and we localize its coordinates (Cx, Cy) which refer to the center of the most brilliant region, ie the optical disc.

C. Interest Ring Extraction around the optical disc

This step aimed to restrict our interest region around the detected center. Vessels around the optical disc are more important for identification purposes because they contain the high density of information. In fact, on one hand inside the optical disc, vessels are less contrasted and noisy. On the other hand, if they are farther from the optical disc, they become thinner and their distribution is more arbitrary. So, we propose to focus on vessels in the neighborhood of the optical disc. We extract a ring centered at the detected center, with radius R1 and R2 (R1 < R2) as an interest region of retinal image. Finally, as shown in figure 3, we extract the rectangle around the biggest circle (R2) to be used as input for feature extraction step. Actually, the choice of R1 and R2 values affects significantly the rate of personal identification. In fact, the bigger R2 value, the higher personal recognition rate is. However, the needed computation time will be high too. So, in this work, an optimal combination of R1 and R2 is chosen through apprenticeship as follow:

R2 = N/2
(2)

R1 = N/6 ( 3
)
Where N is the width of the input retinal image.

IV. EXPERIMENTAL RESULTS AND DISCUSSION

In order to evaluate the efficiency of our proposed preprocessing method, we integrate it into a personal identification system. The assessed system is composed of three main phases: our proposed ODR preprocessing, the Scale Invariant Feature Transform (SIFT) [START_REF] David | Distinctive Image Features from Scale-Invariant Keypoints[END_REF] extraction which extract local descriptors invariant to geometric transformation such as rotation, translation and illumination variations, and the test g2NN of Lowe [START_REF] David | Distinctive Image Features from Scale-Invariant Keypoints[END_REF] feature matching in order to find the number of matched pairs between retinal images. All the experiments are implemented in MATLAB, and performed on a PC with a 3.2 GHz CPU and 4 G Byte memory. The method was applied on the VARIA database [START_REF] Varia | Retinal Images for Authentification[END_REF] which is built for evaluation of retinal recognition systems. This database includes 233 retinal images of 139 different subjects with a resolution of 768 * 584. The images have been acquired over a time span of several years with a TopCop NW-100 model non-mydriatic retinal camera. These images are optic disc centered and have a high variability in contrast and illumination, allowing the system to be assessed in quite hard conditions and simulating a more realistic environment.

To evaluate the efficiency of our proposed ODR based identification system in terms of quality, we compare our proposed system previously described with the same identification system without preprocessing and using the Top-hat Transform method [START_REF] Meng | Retinal Identification Based on an Improved Circular Gabor Filter and Scale Invariant Feature Transform[END_REF].

The Identification Rate curves for these retinal biometric systems using the VARIA database are illustrated in the figure 4. We can see clearly that our system is the most stable one and identifies the higher rates. Table1 shows that our proposed system allows higher identification rate with 99.89% compared to the other methods. [START_REF] Meng | Retinal Identification Based on an Improved Circular Gabor Filter and Scale Invariant Feature Transform[END_REF] 232.13s 99.57%

The identification system without preprocessing step ensures only 98.6% due to the poor quality of input retinal images which generally suffer from low gray level contrast and illumination variations that can affects keypoints extraction and matching. Although applying the top-hat transform [START_REF] Meng | Retinal Identification Based on an Improved Circular Gabor Filter and Scale Invariant Feature Transform[END_REF] as a preprocessing step, the identification rate has been improved from 98.6% to 99.57%, it stills lower than our proposed system. Even if the proposed system improve slightly the identification rate compared to other systems, the most gain is in term of execution time. Indeed, as shown in table 1, it has been seriously reduced from 232.13s in retinal identification system with the Top-hat Transfom method and 42.18s without preprocessing to only 10s with our ODR preprocessing. This reached execution time is essentially due the extraction of the interest ring around the optical disc. This helps to keep the most vessel information while reducing the extraction SIFT keypoints which decreases the processing time of our system.

In Identification mode of biometric system, there is an only error that can influence the obtained performance. This error is called The False Match Rate (FMR). It defines the probability that the system incorrectly matches the input pattern to a non-matching template in the database. In fact, It measures the percent of invalid input identities which are incorrectly assigned to the persons. As this error is little, the system is more efficient [START_REF] Wayman | Error Rate Equations for the General Biometric System[END_REF]. The table 2 illustrates the efficiency of our proposed ODR based system with the less FMR rate compared to other identification systems. Indeed, the FMR of our proposed system reach 4.3 10 -5 which is very low compared to 1.32 10 -4 in the top-hat transfom based system and 1.6 10 -3 in the identification system without prepocessing.

V. CONCLUSION

In this paper, we have presented a robust retinal identification approach based on Optical Disc Interest Ring detection. This method consists of three stages: Image Enhancement, optical disc detection and Interest Ring Extraction around the optical discs center. Conducted experiments prove that the proposed ODR method is suitable for the preprocessing of retinal images in order to reduce the false rate of human identification. In order to evaluate the efficiency of our method, we compare it with the Top-hat Transform. Obtained results show that our ODR preprocessing allows improving the identification performance to reach 99.89% in term of Identification rate, while reducing seriously the total execution time compared to other systems.

Fig. 1 .

 1 Fig. 1. Flow Chart of our ODR method.

Fig. 2 .

 2 Fig. 2. Contrast enhancement results: histogram (a) input image and (b) enhanced image.

Fig. 3 .

 3 Fig. 3. Optical disc Interest Ring detection : (a) The input retinal images, (b) Inhanced images with the localized Interest Ring (R1,R2) and (c) Final results of the proposed ODR method.

Fig. 4 .

 4 Fig. 4. The Identification Rate Curves of retinal Human identification system based on three preprocessing.

Table 1 .

 1 The average processing time and the Accuracy recognition rate of identification system based on different preprocessing methods.

	Preprocessing method	Processing time Accuracy
		(average)	Identification
			rate
	The ODR method	10.3s	99.89%
	Without preprocessing	43.18s	98.6%
	The Top-hat Transform method

Table 2 .

 2 The False Match Rate (FMR) of Identification system based on three preprocessing methods.

	Preprocessing method	False Match Rate
	The ODR method	4.3 10 -5
	The Top-hat Transform method [10]	1.32 10 -4
	Without preprocessing	1.6 10 -3


Mahmoud Soua
email: soua.mahmoud@esiee.fr

Rostom Kachouri
email: rostom.kachouri@esiee.fr

Mohamed Akil
email: mohamed.akil@esiee.fr

Improved Hybrid Binarization based on Kmeans for Heterogeneous document processing

Keywords: OCR, Binarization, Heterogeneous Documents, HBK, Gamma Correction

Nowadays, more and more scanned documents are converted into editable electronic representation. This proceeding relies on the Optical Character Recognition (OCR) tool-chain. Generally, an OCR system is based on the important binarization step that separates character strokes from the background document. In this context, one of more robust binarization methods is the recently proposed Hybrid Binarization based on Kmeans (HBK). It handles effectively scanned documents which includes text on simple background. Nevertheless, in Heterogeneous documents, HBK ends up with some issues when extracting foreground text from complex background images. Moreover, HBK assumes to have a dark foreground against a clear background. Otherwise, it fails to render correct binarization colors. In this paper, we propose to improve the HBK method for handling efficiently Heterogeneous documents. Indeed, our proposal employs a layout analysis process that classify document regions into text and image. Image regions are enhanced with Gamma Correction (GC) before HBK binarization. Text regions are treated directly with HBK, keeping its effectiveness on text with homogeneous background. To ensure a robust and independent color rendering in the binarized documents, we control the labeling polarity of text and background through a pixel density-based technique. According to our experiments on LRDE and ICDAR datasets, we demonstrate that I-HBK outperforms HBK when dealing with Heterogeneous documents in both F-measure and OCR accuracy.

I. INTRODUCTION

Optical Character Recognition (OCR) is a great interest in pattern analysis field. Its goal is to recognize the characters in a document to form a digital text file which can be edited and processed. Binarization, is a common and important first step in OCR systems. It converts the pixel values of document images into two-level representations for text and non-text regions.

Several binarization methods were proposed in the literature [START_REF] Sauvola | Adaptive document image binarization[END_REF]. According to our knowledge, the Hybrid Binarization based on Kmeans (HBK) [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF][1] outperforms state of the art methods such as SauvolaMS kx [START_REF] Lazzara | Efficient Multiscale Sauvolas Binarization[END_REF] and Niblack [START_REF] Niblack | An Introduction to Digital Image Processing[END_REF]. HBK scores a character recognition rate of 91% when performing on magazine documents [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF]. Actually, its hybrid approach ensures a robust binarization on scanned documents including text on homogeneous background. Indeed, it produces a local binarization for characters and decreases artifacts thanks to its global correctness. However, regarding heterogeneous documents including text, drawing and natural scene images, HBK fails to extract correctly text from complex background. Moreover, similar to conventional binarization methods, HBK makes the assumption to have dark foreground against clear background and leads sometimes to generate inappropriate binary document colors. To overcome these limits, we propose in this paper an Improved HBK binarization that we call I-HBK.

To deal with text extraction from complex background, documents can be enhanced to increase the image visibility and details which helps to distinguish characters. In this context, some algorithms perform image enhancement before the binarization step [START_REF] Gilboa | Image enhancement and denoising by complex diffusion processes[END_REF]. For example, we can find the Histogram Equalization [START_REF] Pizer | Adaptive histogram equalization and its variation[END_REF], Low Pass Filter [START_REF] Guillon | Adaptive nonlinear filters for 2D a nd 3D image enhancement[END_REF], High Pass Filter [START_REF] Guillon | Adaptive nonlinear filters for 2D a nd 3D image enhancement[END_REF], Hommorphic Filter [START_REF] Fries | Image enhancement by stochastic homomorphic filtering[END_REF] and image Gamma Correction (GC) algorithms [START_REF] Asadi Amiri | Texture Based Image Enhancement Using Gamma Correction[END_REF]. Compared to the above methods, Gamma correction overcomes effectively the problem of uneven illumination [START_REF] Kaur | A Technique for Enhancement of Gray Image using Local Gamma Correction[END_REF]. In the other hand, the more efficient algorithm employed in the literature to handle the text and the background polarity problem, is the pixel density-based technique [START_REF] Clark | Rectifying perspective views of text in 3D scenes using vanishing points[END_REF].

In the following, we study the binarization process of heterogeneous documents in section 2. Then, we describe our proposed I-HBK method in section 3. Next, in section 4, obtained results are shown and discussed. Finally conclusion is drawn in section 5.

II. HETEROGENEOUS DOCUMENT BINARIZATION

Scanned text documents are categorized into three main kinds: documents with Simple text images, documents with Caption text images and documents with Scene text images [START_REF] Sumathi | A survey on various approaches of text extraction in images[END_REF]. Furthermore, documents with heterogeneous content images can be considered as a fourth kind of scanned documents. It is generally named Heterogeneous Document and includes at least two of the above mentioned document types. Figure 1 Generally extracting text from Scene text images is more challenging than in Caption text ones. For this, we consider in the following only Simple text images and Scene text images to study the performance of robust binarization methods and discuss their limits on Heterogeneous documents. In the literature, our recently proposed Hybrid Binarization based on Kmeans (HBK) [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF][1] outperforms well known binarization methods such as Niblack [START_REF] Niblack | An Introduction to Digital Image Processing[END_REF] and Sauvola [START_REF] Sauvola | Adaptive document image binarization[END_REF]. It ensures high local binarization robustness and reduces the possible appearing artifacts using global correctness. In this binarization method, the input image is divided into equal sized blocks that can be set to small, medium or large according to the used character sizes in the document. Then, the Kmeans clustering algorithm [START_REF] Lloyd | Least square quantization in PCM[END_REF] is applied on each block independently. The global phase gathers the obtained pixel values and number belonging to the related clusters in each block. The algorithm performs a correctness loop until convergence. According to Figure 2-(e,b-*), we can see that HBK provides high binarization quality on Simple text images, where characters are well separated. However, it does not do well on Scene text images with complex background, see Figure 2-(g,b).

To overcome the problem of extracting text from complex background images, some methods enhance the image before the binarization process. In this context, we consider approaches that look for a gamma value to help correct separation between foreground and background. The Gamma Correction Method (GCM) [START_REF] Sumathi | Automatic Text Extraction From Complex Colored Images Using Gamma Correction Method[END_REF] is one of the most robust methods in this field. It aims to suppress non-text background details from scene text images by applying appropriate gamma value. For this, the GCM [START_REF] Sumathi | Automatic Text Extraction From Complex Colored Images Using Gamma Correction Method[END_REF] transforms the input image to gammatransformed images using a range of gamma values from 0.1 to 10.0 with increments of 0.1, resulting in 100 different images. A graylevel co-occurrence matrix for each image is computed to extract contrast and energy. Extracted textural feature measures of co-occurrence matrices with four orientations are averaged and threshold value is computed for each image using the Otsu algorithm [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF]. Finally, Gamma, Contrast, Energy and Threshold values are examined to determine the appropriate value of gamma. Actually, GCM outperforms HBK on Scene text images with complex background and produces an efficient binarization quality Figure 2(g,c). However, according to Figure 2(e,c-*), GCM provides less accurate binarization quality than HBK on Simple text images. Thus, binarized characters are slightly touched due to the gamma transformation process. Scene text Images (ICDAR [START_REF] Karatzas | ICDAR Robust Reading Competition. Document Analysis and Recognition (ICDAR)[END_REF]) HBK [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF] 94.11 50 GCM [START_REF] Sumathi | Automatic Text Extraction From Complex Colored Images Using Gamma Correction Method[END_REF] 93.88 98.38

Simple text images by scoring 94.11% of OCR Accuracy. However, GCM is better than HBK in extracting text from scene text images when reaching 98,38% of OCR rate. Hence, we conclude that GCM and HBK methods can be complementary in Heterogeneous document binarization process.

In an another hand, we note that GCM and HBK methods yield to inverted foreground and background colors on Simple text image (Figure 2-(e,c-**), Figure 2-(e,b-**)) and on Scene text images (Figure 2-(f,c), Figure 2-(f,b)). We illustrate in Table II the effectiveness of the two studied methods. We note by D f and C f respectively dark and clear foreground. Likewise, C f and D b mean respectively dark and clear background.

D f & C b C f & D b - - Single Multiple Single No No Yes No
We observe from the Table II that on single regions HBK and GCM have a cross effectiveness when processing simple or Scene text regions. However, GCM always fails to provide high quality binarization when processing multiple regions. Otherwise, we remind that both HBK and GCM fail in some cases to extract the appropriate foreground and background colors. Considering the previous study, we describe our proposed I-HBK method in the following section.

III. IMPROVED HYBRID BINARIZATION BASED ON KMEANS (I-HBK)

Our proposed I-HBK method aims to improve HBK by providing a better binarization quality and OCR Accuracy on Heterogeneous documents. In this type of documents, the textual information can be included in text or image regions. For this reason, our idea is to benefit from the cross advantages of HBK and GCM on both region types. Indeed processing HBK on text regions and GCM on image regions improves the final binarization quality. As shown in Figure 3, our proposed method includes four major stages. Firstly, a Layout analysis is performed to identify text and image regions. Secondly, a binarization algorithm based on Gamma Correction (GC) is tailored to handle image regions. We name it Gamma Correction-based HBK (GCHBK). Similarly, HBK is performed on text regions. The third stage consists on a Pixel Density-based Technique (PDT), where a foreground and a background color study is performed. Finally, binarized regions are gathered in one single document.

A. Layout Analysis

It is important to recognize accurately whether a document region is text or image to perform the adequate treatment. For this, we perform a layout analysis on the input documents. We use the Page Layout Analysis (PLA) algorithm [START_REF] Smith | An Overview of the Tesseract OCR Engine[END_REF], part of the well known Tesseract engine 3.02 [START_REF] Smith | An Overview of the Tesseract OCR Engine[END_REF]. Actually, the PLA uses bottom-up methods, including binary morphology and Connected Component (CC) analysis, to estimate the type of the CCs. In addition, the method uses some measures to detect the tab-stops of column boundaries, indents, table columns. The column layout of the pages is determined from the detected tab-stops. The column layout constrains the construction of partitions of the page that are then gathered into text regions. A similar process is applied to detect image regions.

B. Binarization stage (HBK and GCHBK)

After extracting regions from the heterogeneous document, we employ the appropriate binarization algorithm to process respectively text and image regions. Indeed, we improve the HBK method processing on image documents by including a pre-processing image enhancement. For this, we use a Gamma Correction approach (GC) that helps to separate foreground Figure 3: Flow diagram of the proposed I-HBK method from complex background in text scene images. Actually, we employ GCM [START_REF] Sumathi | Automatic Text Extraction From Complex Colored Images Using Gamma Correction Method[END_REF] Gamma Correction stage and we replace the Otsu binarization method with the HBK one. According to the literature [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF], binarizing with HBK instead of Otsu is more effective scoring 91% of OCR Accuracy against 84%. We name this approach Gamma Correction-based HBK (GCHBK). Our evaluation of the proposed GCHBK is shown in the experimental results section.

C. Pixel Density-based Technique (PDT)

According to our Knowledge several binarization methods [START_REF] Niblack | An Introduction to Digital Image Processing[END_REF][5] [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF] assume to have a dark foreground against a clear background. Otherwise, they fail to render correct binarization colors. To overcome this problem some methods control the labelling polarity of text and background. For example, Clark [START_REF] Clark | Rectifying perspective views of text in 3D scenes using vanishing points[END_REF] uses a simple decision logic based on the assumption that the background pixel number is greater than the text pixel one. This method fails in case characters are thick and occupy a significant area of the used window technique. So instead of using a window approach, we apply the same concept of pixel density-based technique on the extracted regions. This way, we control the foreground and background color polarity according to Equ 1.

P i = 0 if N Bp > N W p P i else (1)
with P i designs a pixel, i in [0, N Bp + N W p ], and N Bp , N W p are respectively the number of black and white pixels in the studied region. The final reconstitution stage gathered the binarization of the two methods into one single document according to the recorded region coordinates.

IV. EXPERIMENTAL RESULTS

In the following, we evaluate our proposed I-HBK method. Firstly, we introduce the employed materials. Then, we compare the OCR Accuracy of the GCM and our proposed GCHBK technique to show its effectiveness when binarizing scene text images. Following, we evaluate our proposed I-HBK when comparing it with HBK according to Fmeasure and Visual quality. Finally, we study I-HBK using the OCR Accuracy.

A. Materials

The proposed I-HBK method was evaluated on LRDE-DBD 1 [6] and ICDAR 2 [START_REF] Karatzas | ICDAR Robust Reading Competition. Document Analysis and Recognition (ICDAR)[END_REF] datasets. In the following experiments, we fix the HBK block size to 32x32 pixels. According to the literature, this block size gives an acceptable binarization quality [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF]. We use the Fmeasure metric to evaluate the binarization accuracy. In addition, Tesseract 3.02 was employed to perform the character recognition study. Following, we evaluate our GCHBK binarization approach on natural scene images.

B. GCM and GCHBK Evaluation

We evaluate our proposed enhancement of HBK binarization on image documents using the Gamma Correction approach (GC). Indeed, we perform the image enhancement part of GCM then we use HBK as a final binarization process in place of Otsu (see section III-B). Table III accuracy by scoring 85.2%. We explain this result with the fact that HBK method outperforms Otsu in the binarization step. Indeed, the employed hybrid processing strategy takes into account both local and global pixel information to provide efficient binarization result. We provide a visual result in Figure 4. As we can see, characters are better separated using GCHBK.

C. I-HBK evaluation based on Visual quality

Following, we show in Figure 5 the binarization results of HBK, GCHBK and our I-HBK methods when processing a sample Heterogeneous document from the LRDE-DBD dataset. We note that I-HBK gives clearly the best binarization result. HBK produces high binarization quality on text regions. However, it fails in rendering the appropriate colors of text and background because it assumes that text is in dark color Following we evaluate HBK and I-HBK methods on both Simple text images and Heterogeneous documents.

D. Comparison of HBK and I-HBK methods based on analytic analysis

The HBK method is robust binarization method on Simple text images. Following, we demonstrate in Table IV the reliability of I-HBK on LRDE-DBD images that include only text information.

Table IV: Comparison of HBK and I-HBK methods based on Binarization-Accuracy on 125 Simple Text LRDE-DBD images

Methods

FMeasure (%) HBK [START_REF] Soua | A new hybrid binarization method based on Kmeans[END_REF] 98,21 I-HBK 98,84

As expected, I-HBK and HBK have a close Fmeasure result on simple text images. Indeed, the processed documents contain only text regions that include, in most cases, dark text on light foreground. We observe a small improvement as I-HBK handles properly regions with light text on dark background. Thus, text and background colors are rendered correctly thanks to the used pixel density-based technique. In addition, some text regions include non-homogeneous background, on which I-HBK gives better text binarization quality. Next, we demonstrate the effectiveness of our proposal using the OCR Accuracy on Heterogeneous documents.

To process Heterogeneous documents, we choose a set of LRDE-DBD documents including Scene text images. For this purpose, we construct their OCR ground-truth as they are not available in the LRDE-DBD Dataset. Figure 6 shows the OCR accuracy of our proposed I-HBK and HBK methods on these documents. We observe that our I-HBK proposal improves considerably the OCR accuracy of HBK. This is due to the good workload distribution between HBK and GCHBK methods. Furthermore, GCHBK allows to extract well the text in Scene text images contrary to HBK that mixes foreground and background colors. Binarization is an important step in any task of image processing and analysis. Recently we proposed the Hybrid Binarization based on Kmeans method (HBK). To process heterogeneous documents, we proposed in this paper a new binarization method named Improved-HBK (I-HBK). In addition of HBK text binarization, our proposal performs layout analysis scheme, then employs a modified Gamma Correction approach GCHBK to extract text from complex background. In addition, it studies the image regions to control the final color rendering of text and background. According to experiments, we demonstrated that I-HBK outperforms HBK in both FMeasure, and OCR accuracy when processing LRDE and ICDAR documents.

  illustrates an example of Heterogeneous Document that contains both text regions (Figure1-a) and image regions (Figure1-b: Caption text image, Scene text image).

Figure 1 :

 1 Figure 1: Heterogeneous Document: a. Text regions, b. Image regions.

Figure 2 :

 2 Figure 2: Visual binarization: a. Single and Multiple regions of scanned documents, b. HBK results, c. GCM results

Figure 4 :

 4 Figure 4: Binarization quality of GCM and GCHBK on text scene image from ICDAR dataset. a. Original image, b. GCM binarization, c. GCHBK binarization

Figure 5 :Figure 6 :

 56 Figure 5: Visual evaluation of the I-HBK method: a. Original document, b. HBK binarization and c. GCHBK binarization, d. IHBK binarization

Table I :

 I Table I illustrates the OCR Accuracy of HBK and GCM methods for Simple and Scene text images. The obtained results support the previous discussed visual observations. OCR Accuracy (%) of GCM and HBK methods on Heterogeneous documents: Simple and Scene text images

	Methods	Simple text image (LRDE
		[6])
	We can see that, HBK outperforms GCM in processing

Table II :

 II Evaluation summary of HBK and GCM effectiveness on Simple and Scene text images

	Methods	Simple text images	Scene text Image

Table III :

 III compares GCM and our GCHBK technique on ICDAR scene text images. We note that GCHBK provides better character recognition Comparison of GCM and GCHBK methods based on OCR Accuracy for ICDAR scene text images

	Methods	OCR Accuracy (%)
	GCM: GC + Otsu	84.4
	GCHBK: GC + HBK	85.2


Rostom Kachouri
email: rostom.kachouri@esiee.fr

Mahmoud Soua
email: soua.mahmoud@esiee.fr

Mohamed Akil
email: mohamed.akil@esiee.fr

Unsupervised Image Segmentation Based on Local pixel Clustering and Low-Level Region Merging

Keywords: Region based image segmentation, Kmeans clustering, Region agglomeration, Similarity measure, Color, Texture, Over-segmentation, Outlier region

HAL is

I. INTRODUCTION

Heterogeneous image segmentation is a fundamental processing for image description and recognition tasks. It aims to partition the image into homogeneous regions. Subsequently, pixels are assigned to semantic meaningful objects. Several survey papers [START_REF] Luccheseysz | Color image segmentation: A stateof-the-art survey[END_REF], [START_REF] Pal | A review on imagesegmentation techniques[END_REF] cover the major image segmentation algorithms providing high quality results. These algorithms can be categorized into two main approaches [START_REF] Haralick | Survey: image segmentation techniques[END_REF]: Boundary-based and Region-based methods. The first category [START_REF] Ho | Design and analysis of an efficient evolutionary image segmentation algorithm[END_REF] operates on the image edges. Indeed, edges are detected and then linked into contours representing the object boundaries [START_REF] Banu | The Comparative Study on Color Image Segmentation Algorithms[END_REF]. Edgebased methods are very robust handling properly images with significant contrast variation between regions. However, the presence of small gaps in edge boundaries allows merging of dissimilar regions. In addition, they are sensitive to noise which leads often to generate non closed contours [START_REF] Huet | Etude de contours haute-chelle pour la segmentation et la fermeture de contours en prsence de zones textures et ou bruites[END_REF], [START_REF] Banu | The Comparative Study on Color Image Segmentation Algorithms[END_REF]. The second category, representing region-based methods, is more noise immune [START_REF] Banu | The Comparative Study on Color Image Segmentation Algorithms[END_REF] and produces enclosed regions [START_REF] Fonseca | Satellite imagery segmentation: a region growing approach[END_REF]. Methods of this category operate by partitioning groups of dissimilar pixels regarding one or more features such as brightness, color, texture, etc. Then, similar pixels which are neighbors, are grouped together in order to reaches a set of meaningful regions.

As a well known region-based method, Region growing [START_REF] Tang | Color Image Segmentation algorithm Based on Region Growing[END_REF] enlarges gradually areas around starting pixels (seeds) based on a predefined criteria. Nevertheless, in this method user should choose initial seeds within the most homogeneous areas. Hence the inconvenience of this method is the choice of initial seeds. So that obtained results are not always optimal. Unlike Region-growing, the Split and Merge technique [START_REF] Horowitz | Picture Segmentation by a Directed Split and Merge Procedure[END_REF] generates automatically an initial partition of homogeneous regions. Several methods where proposed in this context [START_REF] Kelkar | Improved Quadtree Method for Split Merge Image Segmentation[END_REF], [START_REF] Yufeng | A split and merge algorithm based on grey theory[END_REF], [START_REF] Karim | Pattern based object segmentation using split and merge[END_REF]. For example, the Split and Merge based-quadtree method [START_REF] Kelkar | Improved Quadtree Method for Split Merge Image Segmentation[END_REF] performs the split phase by assuming that the image is an entire block. Then regarding on homogeneity test. Heterogeneous blocks are divided into four sub-blocks. The treatment is stopped for each sub-block which reach homogeneity. In the merge phase, regions are gathered based on predefined similarity criterion and a Region Adjacency Graph (RAG). The main advantage of the Split and Merge methods is the fine subdivision of the image, however, they remain complex due to the tedious split treatments. Otherwise, methods based on pixel clustering, offer less complexity in region-based image segmentation [START_REF] Lloyd | Least square quantization in PCM[END_REF], [START_REF] Banerjee | Satellite image segmentation: A novel adaptive mean-shift clustering based approach[END_REF], [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. More recent developments in this field [START_REF] Hou | Merging dominant sets and DBSCAN for Robust clustering and image segmentation[END_REF] classify the input image pixels into multiple clusters based on their distance from each other [START_REF] Lloyd | Least square quantization in PCM[END_REF], membership function [START_REF] Yang | Image Segmentation By Fuzzy C-Means Clustering Algorithm With A Novel Penalty Term[END_REF], maximum likelihood criterion [START_REF] Dempster | Maximum-Likelihood from In complete Data Via the EM Algorithm[END_REF], etc. In this context, one of the most used methods for color image segmentation is the clustering algorithm Kmeans [START_REF] Ms | An Approach to Image Segmentation using Kmeans Clustering Algorithm[END_REF], [START_REF] Neelambike | Pattern based object segmentation using split and merge[END_REF]. However, the major drawback of methods using this classification algorithm is that user needs to set, in the beginning, the region number. Furthermore, in the agglomeration stage of these methods, different linkage techniques [START_REF] Bien | Hierarchical Clustering with Prototypes via Minimax Linkage[END_REF] can be employed. In the single linkage technique [START_REF] Bien | Hierarchical Clustering with Prototypes via Minimax Linkage[END_REF], the cluster similarity is defined by the shortest distance from any member of a cluster to any member of another one. This method shows a total insensitivity to shape and size of clusters. However it is sensitive to outlier pixels [START_REF] Almeida | Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering[END_REF]. Another technique is the complete linkage [START_REF] Bien | Hierarchical Clustering with Prototypes via Minimax Linkage[END_REF]. It is based on the computation of the greatest distance from any member of a cluster to any member of another cluster. This one is not strongly affected by outlier pixels. However, the complete linkage method can break large clusters, and has trouble with convex shapes [START_REF] Almeida | Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering[END_REF]. The level of complexity may be reduced by using centroid linkage technique [START_REF] Bien | Hierarchical Clustering with Prototypes via Minimax Linkage[END_REF]. Indeed, the distance between two clusters is represented by the distance between their centroids. Whenever two clusters are combined, a new centroid is computed. Nevertheless, it can fail in case of complicated cluster shapes. Indeed, centroids, in such case, do not represent efficiently the clusters [START_REF] Almeida | Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering[END_REF]. It is obvious that each method has its own limitations and advantages. Recent works, try to combine more than one linkage technique to improve the agglomeration results [START_REF] Downs | Clustering methods and their uses in computational chemistry[END_REF], [START_REF] Guha | Cure: an efficient clustering algorithm for large databases[END_REF], [START_REF] Han | Data Mining: Concepts and Techniques[END_REF].

In this paper, a novel region-based segmentation method is proposed. Firstly, the proposed method ensures an unsupervised split stage based on local Kmeans clustering. Obtained primitive regions are merged based on a combination of color and texture features. Different linkage techniques are employed to gather efficiently the similar regions. In case of oversegmentation, a post process is used to suppress the unwanted regions. In fact, our main contributions consist on a offering a full automatic segmentation method. A novel initialization method for the local Kmeans algorithm is proposed. Moreover, different linkage techniques are combined in the merge phase.

In the following, we describe our proposal in section 2. Next, in section 3, obtained results are shown and discussed. Finally conclusion is drawn in section 4.

II. PROPOSED METHOD: UNSUPERVISED IMAGE SEGMENTATION (UIS)

Figure 1: Flow diagram of the proposed Unsupervised Image Segmentation (UIS) method

In this section, we describe the different stages of our Unsupervised Image Segmentation (UIS) proposal. As shown in Figure 1, two main stages are employed. The first one is the split stage where a window based approach is used to perform a local robust Kmeans clustering [START_REF] Lloyd | Least square quantization in PCM[END_REF]. For this end, we divide the image into equal size blocks. The second stage is the merge phase. It consists in agglomerating the regions with both color and texture similarity measure. Many color spaces can be employed. In this work we use the Lab [START_REF] Shamir | Human Perception-based Color Segmentation Using Fuzzy Logic[END_REF] color space for better segmentation results [START_REF] Oliver | Improving Clustering Algorithms for Image Segmentation using Contour and Region Information[END_REF]. To compute distance between pixels in the image, the Euclidian distance [START_REF] Cha | Comprehensive Survey on Distance/Similarity Measures between Probability Density Functions[END_REF] is used. After the merge stage, outlier region remove could be employed in case of over-segmentation. Finally, regions in the segmented image are shown with the color of their centroids to show a more expressive semantic regions. In next subsections, we describe, with more details, our proposed method stages.

A. Split stage

The first stage of our proposal consists in clustering local image blocks using the Kmeans algorithm [START_REF] Lloyd | Least square quantization in PCM[END_REF]. Actually, we employ small data blocks, where the block Width and Height represent respectively a ratio of 25% from the image Width and Height. According to the literature [START_REF] Celenk | Hierarchical color clustering for segmentation of textured images[END_REF] this size ensures that each block have high rate to contain one single semantic meaningful objects. However, it can contain more objects. Actually, we believe that this block size is enough to form two meaningful regions. This region number is shown to be appropriate by our experiments. Therefore, we initialize the local Kmeans with a set of two centroids, noted by C bl = {C bl,0 , C bl,1 }, with bl ∈ [0, N b -1] and N b is the total number of blocks in the image. We consider for that nine pixels in each block as a potential initial centroids. These pixels are located in the border and the middle of the blocks as shown in Figure 2. Actually, among these nine selected pixels, we consider that, at least, one pixel belong to the second region if it exists. Then, based on the used color space, we initialize the local Kmeans in each block with the two most farthest pixels from the nine selected ones. After initialization, each block is clustered with Kmeans until convergence. We note by R = {R 0 , R 1 , .., R k-1 } the set of the obtained regions within all blocks in the image. k is then the total number of regions, and it is equal to at most 2 × N b when each block contains two regions. Generally, k ≤ 2 × N b. the UIS method gives a robust clustering thanks to its good initialization and to the efficient Lab color space use. In the next, we describe the Region Merging stage.

B. Merge stage

In this stage, the employed similarity criterion, are very important to determine which region is similar to which one. In general, the combination of color and texture features provides better segmentation result [START_REF] Zhang | Improving Image Retrieval Performance by using both Color and Texture features[END_REF]. The advantages of both color and texture based segmentation are quite well preserved: we obtain sharp boundaries and homogeneous regions [START_REF] Gut | Edge-Based Robust Image Registration for Incomplete and Partly Erroneous Data[END_REF]. Actually, segmentation purely based on texture gives fuzzy boundaries but usually homogeneous regions [START_REF] Unser | Texture classification and segmentation using wavelet frame[END_REF]. Whereas, segmentation based on color is more sensitive to local variations in color but provides sharp boundaries [START_REF] Mirmehdi | Handbook of Texture Analysis[END_REF]. Many researcher proposed various approaches for texture analysis [START_REF] Bastos | Automatic Texture Segmentation Based on kmeans Clustering and Co-occurrence Features, Systems, Signals and Image Processing[END_REF] , for color analysis [START_REF] Stachowicz | Image segmentation and classification using color features, Video/Image Processing and Multimedia Communications on VIPromCom[END_REF] or both of them [START_REF] Zhang | Improving Image Retrieval Performance by using both Color and Texture features[END_REF], [START_REF] Kavitha | Content Based Image Retrieval Based on Global and Region Content of an Image[END_REF]. In our work, we use both color and texture features in addition to the adjacency criterion.

1) Color Features:

We consider that two regions can be merged only if they are adjacent, and have similar color. For that, as shown in Figure 3, we extract for each region three features: R i,c , R i,dmin , R i,dmax with i ∈ [0, k -1]. Where, R i,c is the computed centroid of the region R i . It defines the 1.

Distance(R i,c , R j,c ) ≤ T hreshold (1)
The idea is that the applied threshold is variable depending on the two considered regions, through the use of the M ax(R i,dmin , R j,dmin ) term. As illustrated in Figure 3, we can see that the two regions R 1 and R 2 (Figure 3 2) Texture Features: We define a coefficient that we call T D (see Equation 2) to consider the Texture Degree of the processed image. To compute TD, we evaluate the ratio between Img dmax and Img dmin as shown in Equation 2.

T D = Img dmax Img dmin (2)
Where Img dmin and Img dmax are the average distance of, respectively, all the R i,dmin and all the R i,dmax in the image

Img, i ∈ [0, k -1].
The final employed threshold is then given by the Equation 3:

T hreshold = M ax(R i,dmin , R j,dmin ) + T D (3)
with i, j ∈ [0, k -1] So, the T D term allows to increase the final threshold value depending on the texture degree of the processed image. Indeed, we note that in low textured image, ∀i ∈ [0, k -1], R i,dmax tends to be equal to R i,dmin (R i,dmax R i,dmin ⇒ T D 1). Otherwise, high textured image, R i,dmax is highly greater than R i,dmin ∀, i ∈ [0, k -1], (R i,dmax R i,dmin ⇒ T D 1).

C. Outlier-Region remove stage It is possible that the merged image contains some outlier regions. Generally, in such case, we talk about oversegmentation. To overcome this problem, we eliminate these small areas by merging them with the appropriate regions. Generally, considering the context of the application, meaningful objects in an image exist within a marge of sizes. Then, it is possible to impose a minimum valid object area for segmented regions [START_REF] Rosito | Robust watershed segmentation using wavelets[END_REF]. Hence, researchers set the maximum pixel number for a valid object region [START_REF] Rosito | Robust watershed segmentation using wavelets[END_REF], [START_REF] Zhang | Extraction of karyocytes and their components from microscopic bone marrow images based on regional color features[END_REF], [START_REF] Karande | Probabilistic Model Based Image Segmentation[END_REF]. In our work, we extract objects in a general purpose context (natural scene, single object). For this, we evaluate the sum of pixel number across the regions from the largest to smallest ones. When the pixel number reachs 60% from the total pixel number, the remaining areas will be considered as outliers. These regions are merged with the bounding ones. We note by (x 1,Ri , x 2,Ri ) and (y 1,Ri , y 2,Ri ) the horizontal and vertical limits of regions R i . For each R i , we note by ∆ X and ∆ Y the measures referring respectively to their Width and Height. They are defined as following:

∆ X (R i ) = x 2,Ri -x 1,Ri , ∆ Y (R i ) = y 2,Ri -y 1,Ri with i ∈ [0, N b]
and N b is the total number of regions. The outlier suppression is shown in Figure 4 and Algorithm 1. Following, we note by O the origin, R o an outlier region and R Ci i ∈ [0, N b] the set of the candidate bounding ones. We study the measures ∆ X and ∆ Y to determine if a given region R Ci bounds R o . Two conditions rise up. Firstly, as shown in Figure 4(a), R o can be totally bounded by an R Ci (Line 4). In this case, these segments are merged together. Secondly, R o can partially be bounded by several regions R Ci (Line 7). Then, R o is merged with the most color similar one. This case is illustrated in Figure 4(b). In the following, we evaluate our proposed UIS method on both Corel 1 [START_REF] Wang | SIMPLIcity: Semanticssensitive integrated matching for picture libraries[END_REF] and Berkeley 2 [START_REF] Verma | A Simple Single Seeded Region Growing Algorithm for Color Image Segmentation using Adaptive Thresholding[END_REF] datasets. Evaluation is performed according to visual accuracy comparison and Liu's factor measuring.

Algorithm 1 Outlier-Region remove stage 1: for i := 0 to k -1 do // R o and R Ci overlapping 2: if (x 1,Ro > x 1,R Ci ) or (x 2,Ro < x 2,R Ci ) or 3: (y 1,Ro > y 1,R Ci ) or (y 2,Ro < y 2,R Ci ) then // R o is totally enclosed in R Ci (Figure 4.a) 4: if (∆ X (R o ) ≤ ∆ X (R Ci )) and 5: (∆ Y (R o ) ≤ ∆ Y (R Ci )) then 6: Merge R o and R Ci // R o is partially included in R Ci (

A. The Liu's factor metric

We employ the Lius'factor metric [START_REF] Liu | Multiresolution Color Image Segmentation IEEE Transaction on pattern analysis and machine intelligence[END_REF] to evaluate the obtained results with our UIS method. The following equation shows the Lius'factor formula.

L(Img) = √ k × ξ 2 i S (R i ) , i ∈ [0, k -1] (4)
where, Img is the segmented image, We note respectively k the final obtained number of regions and S (R i ) the size of the region R i , ie its total number of pixels. ξ i is the sum of the Euclidean distance of each pixel in the region R i between the segmented image and the original one. It defines the region color error. The best image segmentation results are indicated with a small values of L. Generally, images with large color error regions or small regions are penalized.

B. UIS evaluation based on Visual Accuracy and Liu's factor measuring

The Figure 6 illustrates the obtained UIS segmentation results on five image samples from different Corel categories (Figure 6(a)).

As a first observation, it is clear that our UIS method gives efficient segmentation quality. Indeed, it provides the right region delimitation and the correct region number for all illustrated images. Actually, the local Kmeans employment produces a robust clustering by dividing the original image into k primitive regions. In addition, we observe that region contours are well preserved after the split stage (Figure 6(b)). According to Figure 6(c), the merge stage decreases efficiently the region number by connecting similar regions as explained in section 2.2. The obtained region number in this stage is noted by k . At this level, the final segmentation result may be obtained as it is the case of the Dinosaur image. Otherwise, in case of over-segmentation, the outlier regions are suppressed efficiently (Figure 6(d)). k is the final number of regions in the obtained segmented image. Following, we show that we improve the segmentation quality when eliminating the outlier regions. According to the table below, the Liu's coefficient is enhanced in the final segmented image compared to the merged one. Indeed, the less are the image segments small, the lower is the Liu's coefficient and that is prove the efficiency of the UIS method.

For comparison reasons, we evaluate the proposed UIS with the state of the art methods on the well-known Berkeley dataset. Figure 7 illustrates segmentation results of Normalized cuts (NCUTS) [START_REF] Shi | Normalized cuts and image segmentation[END_REF], Dominant Set (DSet) [START_REF] Pavan | Dominant sets and pairwise clustering[END_REF], DSet-DBSCAN [START_REF] Hou | Merging dominant sets and DBSCAN for Robust clustering and image segmentation[END_REF] and our proposed UIS. Results of the compared methods are taken from the literature [START_REF] Hou | Merging dominant sets and DBSCAN for Robust clustering and image segmentation[END_REF]. We observe that NCUTS is not able to avoid the problem of partitioning coherent regions into multiple segments. The same problem is encountered with the DSet method. This because it generates only convex shapes. In the other side, DSet-DBSCAN and UIS can partition the images into meaningful segments. Actually, DSet-DBSCAN extends the clustered DSet regions with the DBSCAN algorithm. Therefore it can handle nonconvex shapes but still generating over-segmentation with the appearance of fiew outlier regions on the final results (Figure 7(c)). Nevertheless, the proposed UIS method processes as well non-convex shapes thanks to the hierarchical merge. In addition, the powerful outlier remove stage decreases considerably the amount of overlapping regions.

Following, we compare our segmentation results with, the Split and Merge [START_REF] Balthasar | [END_REF], Watershed [START_REF] Tang | Color Image Segmentation algorithm Based on Region Growing[END_REF] and Verma [START_REF] Verma | A Simple Single Seeded Region Growing Algorithm for Color Image Segmentation using Adaptive Thresholding[END_REF] methods, using the Liu's factor metric. As shown in Figure 8, our proposed method gives 3× lower Liu's factor values than Wathershed, 2× lower values than Verma and 1.5× lower values than the Split and Merge method.

Figure 2 :

 2 Figure 2: Position of the nine selected pixels in each block

Figure 3 :

 3 Figure 3: Region representation in the Lab color space: a. Basic model, b. Similar regions and c. Dissimilar regions

  (b)) are similar since Distance(R 1,c , R 2,c ) ≤ M ax(R 1,dmin , R 2,dmin ). However R 1 and R 3 (Figure 3(c)) are dissimilar because Distance(R 1,c , R 3,c ) > M ax(R 1,dmin , R 3,dmin ).

Figure 4 :

 4 Figure 4: The two cases of region locations a. Region R 0 totally enclosed in a region R C0 . b. Region R 0 partially included in three regions R C0 , R C1 and R C2 .

Figure 4

 4 R o with the most color similar region R Ci end for As shown in Figure 5, outlier regions designed by arrows (Figure 5(a)) are correctly merged with the bounding and color similar regions in the image (Figure 5(b)).

Figure 5 :

 5 Figure 5: Outlier-Region remove: a. Merged Image, b. Final UIS Segmented Image

Figure 6 :

 6 Figure 6: Segmentation results and obtained region number on the Corel dataset: a. Original Image Samples, b. Local Kmeans splitted Images, c. Merged Images and d. UIS Segmented Images

Figure 7 :Figure 8 :

 78 Figure 7: Segmentation result comparison on the Berkeley dataset: a. NCUTS, b. DSet, c. DSet-DBSCAN and d. Proposed UIS

Table I :

 I Liu's Factor on Corel images

	Image / Stage	Merged Image	Segmented Image
	Elephant	1.53 e -006	7.80 e -007
	Flower	1.52 e -006	9.06 e -007
	Car	1.33 e -006	5.39 e -007
	Furniture	1.44 e -006	6.51 e -007
	Dinosaur	4.88 e -007	4.88 e -007