Mahmoud Soua
email: soua.mahmoud@esiee.fr

Rostom Kachouri
email: rostom.kachouri@esiee.fr

Mohamed Akil
email: mohamed.akil@esiee.fr

A NEW HYBRID BINARIZATION METHOD BASED ON KMEANS

Keywords: Scanned documents, binarization, Kmeans, OCR

The document binarization is a fundamental processing step toward Optical Character Recognition (OCR). It aims to separate the foreground text from the document background. In this article, we propose a novel binarization technique combining local and global approaches using the clustering algorithm Kmeans. The proposed Hybrid Binarization, based on Kmeans (HBK), performs a robust binarization on scanned documents. According to several experiments, we demonstrate that the HBK method improves the binarization quality while minimizing the amount of distortion. Moreover, it outperforms several well-known state of the art methods in the OCR evaluation.

INTRODUCTION

Document binarization is an important pre-processing for image analysis especially Optical Character Recognition (OCR) [START_REF] Xiu | Whole-Book Recognition, Pattern Analysis and Machine Intelligence[END_REF]. It tries to separate the foreground text from the background. In general, approaches that deal with binarization are categorized in two main classes: global and local [START_REF] Stathis | An evaluation technique for binarization algorithms[END_REF]. Principally, global methods are based on histogram, classification and clustering approaches. In the histogram category, Rosenfeld and Kak [START_REF] Rosenfeld | Digital Picture Processing[END_REF] select one threshold from the histogram of 2D document. They assume that gray values of each object are located around each histogram peak. Another well-known method is the Iterative Global Thresholding (IGT) [START_REF] Kavallieratou | A binarization algorithm specialized on document images and photos[END_REF]. It is composed of two phases executed iteratively. Firstly, the average color of the image is computed and subtracted from the image. Then, a histogram stretching is performed, in such way that the remaining pixels take up all of the gray-scale tones. The main drawback of histogram methods is the inaccurate detection of peaks caused by noise [START_REF] Glasbey | An Analysis of histogram-based thresholding algorithm, Graph[END_REF]. In the classification approaches, Otsu [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF] is a very popular technique [START_REF] Martn | Analysis tools for gray level histograms[END_REF]. It finds an automatic threshold that reduces the interclass variance between foreground and background. Many clustering methods are reported in the binarization litterature. The Fuzzy C-means (FCM) [START_REF] Duda | Pattern Classification and Scene Analysis[END_REF] is one of the most efficient algorithms [START_REF] Stathis | An evaluation technique for binarization algorithms[END_REF]. It sets the image pixels into the correspondent foreground or background cluster. The membership degree of each pixel is computed according to a relatively complex fashion. Less complex [START_REF] Ghosh | Comparative Analysis of K-Means and Fuzzy C-Means Algorithms[END_REF], the Kmeans algorithm [START_REF] Lloyd | Least square quantization in PCM[END_REF] clusters pixels according to a distance computation. According to the litterature, Kmeans is a simple and flexible clustering method [START_REF] Pritesh | A Survey on K-mean Clustering and Particle Swarm Optimization[END_REF] that can be employed in binarization [START_REF] Stathis | An evaluation technique for binarization algorithms[END_REF]. In general, global binarization methods are efficient when they are applied to documents with uniform illumination. However, degraded documents, including stains, and uneven contrast, are not well processed by global methods [START_REF] Valizadeh | An adaptive water flow model for binarization of degraded document images[END_REF]. To overcome this problem, local methods are used to binarize degraded documents. For example, Niblack [START_REF] Niblack | An Introduction to Digital Image Processing[END_REF] computes a threshold based on the mean and the standard deviation of small neighborhood around each pixel. Actually, the Niblack method identifies the text regions correctly as foreground, however, it tends to produce a large amount of noise in non-text regions. Sauvola [START_REF] Sauvola | Adaptive document image binarization[END_REF] improves Niblack by using the dynamic range of image gray-value standard deviation. In case of low separation between foreground and background, the result is degraded significantly. Wolf [START_REF] Wolf | Extraction and recognition of artificial text in multimedia documents[END_REF] outperforms Sauvola by maximizing the local contrast. However, performance degradation arises if there is a sharp change in background gray values across the image. Recently, Sauvola Ms kx [START_REF] Lazzara | Efficient Multiscale Sauvolas Binarization[END_REF] was proposed as an improvement to Sauvola. It begins with data sub-sampling. Then, binarization is performed at different scales. It should recognize that, local methods provide an adaptive solution since the binarization decision varies according to the properties of each document area. Local methods may introduce some noise like artefacts due to the local areas treatments. To improve the binarization quality, some recent works combine local and global approaches [START_REF] Stathis | An evaluation technique for binarization algorithms[END_REF]. They perform an efficient local binarization while reducing the noise as the global one do [START_REF] Greenleaf | Local-Global Image Binarization reconstructing the cellular structure of polymer foam materials[END_REF]. For example, Gabara [START_REF] Gabarra | Combining global and local threshold to binarize document of images[END_REF] uses local thresholding technique based on global edge detection. Hybrid IGT (HIGT) [START_REF] Sokratis | A hybrid binarization technique for document images[END_REF] applies the IGT global binarization [START_REF] Kavallieratou | A binarization algorithm specialized on document images and photos[END_REF] on the whole image then, reapplies it only on noisy areas. In most cases, the hybrid methods improve binarization quality on degraded documents.

In this context, we propose in this paper an adaptive method which we term Hybrid binarization based on Kmeans (HBK) to binarize scanned documents. Our method performs the Kmeans algorithm on local areas to get an improved re-sult. Then, it employs a global technique to enhance local binarization. Performed experiments show that HBK is a robust binarization method. The obtained binarization allow to achieve higher OCR quality. The organization of the paper is shown as follow. Firstly, the Kmeans algorithm is presented in Section 2. We describe our proposed HBK method in Section 3. Next, in Section 4, experimental results are discussed. Finally, conclusion is drawn in Section 5.

KMEANS CLUSTERING

Kmeans [START_REF] Lloyd | Least square quantization in PCM[END_REF] is one of the most popular unsupervised clustering algorithms, mainly used for data mining [START_REF] Singh | Evolving limitations in Kmeans algorithm in data mining and their removal[END_REF] and image processing [START_REF] Isa | Adaptive fuzzy moving Kmeans clustering algorithm for image segmentation[END_REF]. Regarding the image processing context, Kmeans aims to partition all pixels in the image into k distinct clusters. Each cluster is represented by a single centroid.

Fig. 1. The process flow of Kmeans

The Kmeans process flow is shown in Figure 1 and described as follow. In the first stage, the centroids number and values are initialized depending on the application. We note by C = {C 0 , C 1 , ..., C i , ..., C k-1 } the set of k input centroids. Afterward, the distances between centroids and pixels are computed to measure their similarity. For better clustering quality, the Euclidean distance is generally employed [START_REF] Cha | Comprehensive Survey on Distance/Similarity Measures between Probability Density Functions[END_REF]. Given a centroid C i and a pixel P j the related Euclidean distance is defined as:

d(C i , P j ) = (C R i -P R j ) 2 + (C G i -P G j ) 2 + (C B i -P B j ) 2 (1
) Where C i and P j are represented in the RGB color space by:

C i = (C R i , C G i , C B i ) T and P j = (P R j , P G j , P B j ) T , know- ing that i ∈ [0, k -1], j ∈ [0, N p -1]
and N p is the total number of pixels in the image. Next, the labeling stage sets the membership of pixels to the closest centroids according to the minimum computed distances. In addition, the pixel values and number in each cluster i are added respectively to the corresponding accumulator Accu = {Accu 0 , Accu 1 , ..., Accu i , ..., Accu k-1 }, and counter Count = {Count 0 , Count 1 , ..., Count i , ..., Count k-1 } variable sets, with

Accu i = (Accu R i , Accu G i , Accu B i ) T . Finally, in the k centroid updating stage, each centroid C i , i ∈ [0, k -1]
is re-estimated by computing the average assigned pixels to the corresponding cluster i. This process is done based-on the previous computed accumulators and counters. The distance computation, the labeling and the centroid updating stages are repeated until overall pixels are firmly assigned and centroid are no longer being changed. Before each iteration, accumulators and counters are reset to zero. In next section, we describe our proposal which is based fundamentally on the Kmeans algorithm.

PROPOSED METHOD : HYBRID BINARIZATION BASED ON KMEANS (HBK)

As a hybrid approach, our proposed binarization method performs higher local binarization robustness and reduces the possible appearing artifacts by using global correctness. In the rest of the paper we call this method HBK. Global and local phases of the HBK method are shown in Figure 2. Considering the binarization context, two initial centroids are employed. We note by C G = {C G0 , C G1 } the global centroid set. We initialize C G0 and C G1 with black and white Algorithm 1 HBK(Img)

1: C G0 ← (0, 0, 0) T , C G1 ← (255, 255, 255) T 2: while C Gi (ite) = C Gi (ite -1), i ∈ [0, 1] do 3: for bl ∈ [0, N b -1] do 4: Kmeans(bl, C G ) 5: Reset(Accu G , Count G ) 6: for i ∈ [0, 1] do 7: Accu Gi ← Accu Gi + Accu Lbl,i
Eq.2 8:

Count Gi ← Count Gi + Count Lbl,i 9:
end for 10:

end for 11:

C Gi ← Accu Gi Count Gi , i ∈ [0, 1]
Eq.3 12: end while values. Thus, C G0 = (0, 0, 0) T and C G1 = (255, 255, 255) T design respectively the background and the foreground clusters. The document is divided into blocks of equal sizes. Each block includes two local centroids given the set

C L = {(C L0,0 , C L0,1 ), (C L1,0 , C L1,1 ), ..., C Lbl,i , ..., (C LN b-1,0 , C LN b-1,1 )}, with C Lbl,i = (C R Lbl,i , C G Lbl,i , C B Lbl,i ) T given that i ∈ [0, 1], bl ∈ [0, N b -1].
In the beginning, each local centroid is initialized with the corresponding global one:

C Lbl,0 = C G0 and C Lbl,1 = C G1 , bl ∈ [0, N b -1].
In addition, each block has two local accumulators and counters given respectively by the sets Accu L and Count L : Accu L = {(Accu L0,0 , Accu L0,1 ), (Accu L1,0 , Accu L1,1 ), ..., Accu Lbl,i , ..., (Accu LN b-1,0 , Accu LN b-1,1 )}and

Count L = {(Count L0,0 , Count L0,1 ), (Count L1,0 , Count L1,1 ), ..., Count Lbl,i , ..., (Count LN b-1,0 , Count LN b-1,1 )} with Accu Lbl,i = (Accu R Lbl,i , Accu G Lbl,i , Accu B Lbl,i ) T where i ∈ [0, 1] and bl ∈ [0, N b -1].
As stated in line 4, the Kmeans algorithm is applied across all blocks in the scanned document. When the Kmeans process on each block converges, all the local accumulators are gathered into a global one:

Accu G = {Accu G0 , Accu G1 } with, Accu Gi = (Accu R Gi , Accu G Gi , Accu B Gi ) T , i ∈ [0, 1]
. Line 7 states for the global accumulators compute. This process is performed by one addition per each color component as stated in Eq.2:

Accu Gi =       Accu R Gi + Accu R Lbl,i Accu G Gi + Accu G Lbl,i Accu B Gi + Accu B Lbl,i       , i ∈ [0, 1], ( 2
) bl ∈ [0, N b -1]
Similarly, local counters of each block are accumulated into global ones given by Count G = {Count G0 , Count G1 }. Finally, global accumulators Accu G are devided by the correspondent counters Count G to compute the C Gi new centroids as shown in Eq.3:

C Gi =       C R Gi C G Gi C B Gi       =       Accu R Gi Count Gi Accu G Gi Count Gi Accu B Gi Count Gi       , i ∈ [0, 1] (3)
If the global convergence is reached, the HBK algorithm stops, else it reiterates and local centroids of each block are reset with the computed global ones C G0 and C G1 . In the next section, we demonstrate that our method gives satisfying binarization quality thanks to the local approach.

EXPERIMENTAL RESULTS

In the following subsections, we present the employed dataset. Then, we demonstrate the efficiency of our proposed HBK method while reducing the distortion criterion. Finally, we compare our proposal to several state of the art methods in term of OCR evaluation.

The LRDE Document Binarization Dataset (LRDE-DBD)

In our experiments, we evaluate our HBK method on the LRDE-DBD1 database [START_REF] Lazzara | Efficient Multiscale Sauvolas Binarization[END_REF]. It is composed of French text documents extracted from "Le Nouvel Observateur 2 " magazine. The provided dataset is composed of images with A4 format and 300-dpi resolution. Evaluation tests were performed on 125 scanned documents.

Distortion criterion-based evaluation

In general, to evaluate the efficiency of Kmeans clustering, the sum of cluster distortions is usually employed as a performance indicator [START_REF] Al-Daoud | New methods for the initialization of clusters[END_REF][START_REF] Pena | An empirical comparison of four initialization methods for the Kmeans algorithm[END_REF]. Given an image with N p pixels, we note by C (p i ) the Kmeans associated centroid of one pixel p i , with i ∈ [0, N p -1]. The distortion criterion measure is defined by Eq.4:

distortion = 1 N p i=0 |p i -C (p i )| 2 (4)
For comparison reason, we implement a simple Kmeans binarization method that we term Global Binarization Kmeans (GBK). In this method, a single Kmeans is performed over the whole image. Keeping the goal of the binarization context, initial centroids of both GBK and HBK are set to the RGB values C G0 = (0, 0, 0) T and C G1 = (255, 255, 255) T . To evaluate the clustering performances of these two methods, we measure the distortion criterion of GBK and HBK binarization on the LRDE-DBD database. The obtained result demonstrates that the HBK improves nearly 3x the distortion measure compared to GBK. Indeed, the treatment of Kmeans on small areas, gives local optimal distortions that minimizes the global one. We can come to the conclusion that our approach improves the binarization quality while reducing distortion in employed Kmeans clustering. In the next section, we perform an OCR evaluation to measure the HBK binarization efficiency.

OCR-based evaluation

Optical Character Recognition (OCR) is a process by which text characters contained in an image can be recognized. The binarization quality has a direct influence on the OCR result. In this context, the Tesseract 3.02 OCR [START_REF] Smith | An Overview of the Tesseract OCR Engine[END_REF] is used. Actually, we compare the character recognition rate of our HBK approach against seven well-ranked binarization methods [START_REF] Lazzara | Efficient Multiscale Sauvolas Binarization[END_REF][START_REF] Sauvola | Adaptive document image binarization[END_REF][START_REF] Wolf | Extraction and recognition of artificial text in multimedia documents[END_REF][START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF][START_REF] Niblack | An Introduction to Digital Image Processing[END_REF][START_REF] Lelore | Super-resolved binarization of text based on the FAIR algorithm[END_REF][START_REF] Fabrizio | Text segmentation in natural scenes using toggle-mapping[END_REF] on the LRDE-DBD documents. Table 1 shows the OCR recognition rate of the evaluated methods. The first observation to be noted from this table, is that the OCR results are very close: The recent Sauvola Ms kx gives an acceptable OCR rate by scoring 89% of accuracy. It ensures well text binarization but in some document areas, artifacts may appear leading to character miss-recognition. In the other side, the proposed HBK method gives the best OCR rate scoring 91% of accuracy thanks to its proper binarization re-Table 1. OCR Accuracy evaluation of HBK and seven wellranked binarization methods.

Methods

Images OCR Accuracy (%) HBK Scanned 91 Sauvola Ms kx [START_REF] Lazzara | Efficient Multiscale Sauvolas Binarization[END_REF] Scanned 89 Wolf [START_REF] Wolf | Extraction and recognition of artificial text in multimedia documents[END_REF] Scanned 88 Sauvola [START_REF] Sauvola | Adaptive document image binarization[END_REF] Scanned 87 Lelore [START_REF] Lelore | Super-resolved binarization of text based on the FAIR algorithm[END_REF] Scanned 85 Otsu [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF] Scanned 84 Niblack [START_REF] Niblack | An Introduction to Digital Image Processing[END_REF] Scanned 80 TMMS [START_REF] Fabrizio | Text segmentation in natural scenes using toggle-mapping[END_REF] Scanned 73 sults. Indeed, in the HBK method, the local binarization gives robust binarization quality and the global approach eliminates the artifacts generated by the local approach.

CONCLUSION

Binarization is an important pre-processing step for optical character recognition (OCR). In this paper, we proposed a new hybrid binarization method based on the Kmeans clustering algorithm. We show that HBK performs robust binarization while minimizing the amount of distortion. Several experiments are performed on real magazine documents. The proposed HBK method outperforms several state of the art methods in the OCR-based evaluation while scoring 91% of accuracy. In future work, we intend to adapt the block sizes with kind of text in order to ensure multiscale binarization. In the other side, we note that the HBK method is highly adapted to parallel processing thanks to the no-dependency between image blocks. For this, we plan to use a parallel architecture in order to accelerate the HBK execution time.

Fig. 2 .

 2 Fig. 2. The HBK method: global and local phases Firstly, in the local phase, the input image (scanned document) is divided into N b blocks. Then, the Kmeans algorithm is applied in each block. Afterward, the global phase gathers the obtained Kmeans results from each block iteratively and performs a correctness loop until convergence. More details of the HBK method are described in Algorithm 1.Considering the binarization context, two initial centroids are employed. We note by C G = {C G0 , C G1 } the global centroid set. We initialize C G0 and C G1 with black and white

Fig. 3 .

 3 Fig. 3. Accumulated distortion computed from the obtained binarization results of GBK and HBK methods

Copyright(c)

EPITA and Development Laboratory (LRDE) with permission from Le Nouvel Observateur. LRDE-DBD is available online on the web site: http : //www.lrde.epita.f r/cgibin/twiki/view/Olena/DatasetDBD 2 Le Nouvel Observateur. Issue 2402, November 18-24, 2010 and available on the website: http : //tempsreel.nouvelobs.com


Rostom Kachouri
email: rostom.kachouri@esiee.fr

Mohamed Akil
email: mohamed.akil@esiee.fr

Hardware design to accelerate PNG encoder for binary mask compression on FPGA

Keywords: PNG encoder, Prediction, LZ77, Huffman, binary masks, Hardware design, FPGA

PNG (Portable Network Graphics) is a lossless compression method for real-world pictures. Since its specification, it continues to attract the interest of the image processing community. Indeed, PNG is an extensible file format for portable and well-compressed storage of raster images. In addition, it supports all of Black and White (binary mask), grayscale, indexed-color, and truecolor images. Within the framework of the Demat+ project which intend to propose a complete solution for storage and retrieval of scanned documents, we address in this paper a hardware design to accelerate the PNG encoder for binary mask compression on FPGA. For this, an optimized architecture is proposed as part of an hybrid software and hardware co-operating system. For its evaluation, the new designed PNG IP has been implemented on the ALTERA "Arria II GX EP2AGX125EF35" FPGA. The experimental results show a good match between the achieved compression ratio, the computational cost and the used hardware resources.

I. INTRODUCTION

Within the framework of the Demat+1 project, we aim to propose a complete solution for storage and retrieval of scanned documents. In this context, the intended paperless application to achieve have to transmit the scanned documents with a low-bandwidth network to a computer cloud. The overall idea consist to partition the source document into three layers: a foreground layer, a background layer, and a binary mask [START_REF] Bottou | High quality document image compression with djvu[END_REF], and then to use different compression strategies for the same document. In literature, the often used taxonomy distinguishes two categories of image compression format: the lossless compression formats and the lossy ones [START_REF] Chilowicz | Une synthse sur les formats usuels d'images numriques fixes[END_REF]. The lossless compression formats perform compression on the image matrix. It is worth noting that the transformation between a raw format and the lossless compression one is bijective [START_REF] Randers-Pehrson | Portable Network Graphics) Specification Version 1.2[END_REF], [START_REF]Graphics Interchange Format (GIF) specification[END_REF]. Which means that when decompressing a lossless compressed image, the original image is restored, and it is a 100% identical copy of the original. On the other side, the lossy compression formats achieve better compression rate at the cost of image degradation [4], [START_REF]JPEG 2000 Image Codecs Comparison[END_REF]. A quantification stage is applied in this case on the frequency transform of the image 2 . We note that the foreground and background layers which contain, respectively, the color information of the text and the original background of the image can be compressed via a lossy compression format like JPEG [4] for example. By against, the binary mask, where the text, and possibly pieces of thin strokes when they exist, are located is necessarily subjected to a nondestructive compression. One of the most interesting lossless compression formats is PNG (Portable Network Graphics). In fact, it provides a portable, legally unencumbered, wellcompressed, well-specified standard for lossless bitmapped image files [START_REF] Randers-Pehrson | Portable Network Graphics) Specification Version 1.2[END_REF]. To respond to real-time constraints, aimed to be respected by the SagemCom company, we expect in this paper to accelerate the employed PNG encoder for binary mask compression through a hardware implementation. Indeed, while compare with software encoding, parallel processing is the most significant feature of high efficiency. Front of a custom development, based on ASIC technology, the capacity and performance of current FPGAs are such that they present a much more realistic alternative than they have been in the past. Effectively, FPGAs allow a rapid soft reconfiguration of on chip hardware. Moreover, with a sufficient number of parallel operations, FPGAs can offer better performance-price and power dissipation than state of the art microprocessors or DSPs. Many implementations of lossy and lossless image compression encoders and decoders were performed on reconfigurable FPGA circuits [START_REF] Sanjeevannanavar | Efficient design and FPGA implementation of JPEG encoder using verilog HDL[END_REF], [START_REF] Daryanavard | FPGA implementation of JPEG-LS compression algorithm for real time applications[END_REF], [START_REF] Huang | Hardware design for accelerating PNG decode. Electron Devices and Solid-State Circuits[END_REF]. In this paper, we discuss a hardware accelerated implementation of the PNG encoder for binary mask compression on FPGA. An optimized architecture is proposed as part of an hybrid software and hardware co-operating system. For its evaluation, the new designed PNG IP has been implemented on the ALTERA "Arria II GX EP2AGX125EF35" FPGA. The experimental results show a good match between the achieved compression ratio, the computational cost and the used hardware resources. The paper is organized as follows: first we present briefly the PNG encoder in section II. The performed PNG encoder optimizations, in order to well-ensure binary mask compression, are provided in section III. Section IV describe the proposed hardware design to accelerate the optimized PNG encoder on FPGA. Then, the obtained experimental results are discussed in section V. Finally, section VI concludes the discussion.

II. PNG ENCODER

The PNG format is very simple, where each PNG file is composed out of a signature3 and chunks4 . A valid PNG file consists at least of an IHDR chunk, one or more IDAT chunks, and an IEND chunk [START_REF] Randers-Pehrson | Portable Network Graphics) Specification Version 1.2[END_REF]. A minimal PNG file might look as shown in figure 1. The PNG encoder [START_REF] Randers-Pehrson | Portable Network Graphics) Specification Version 1.2[END_REF] is principally composed of two main stages, namely a prediction step followed by a compression step. Indeed, PNG uses prediction in order to increase redundancy and therefor enhancing its compression rate. The prediction errors are then compressed using the Deflate algorithm [START_REF] Peter | Deflate Compressed Data Format Specification version 1.3[END_REF]. Deflate is a lossless compression method which uses a combination of the LZ77 algorithm [START_REF] Ziv | A Universal Algorithm for Sequential Data Compression[END_REF] and Huffman coding [START_REF] Huffman | A Method for the Construction of Minimum-Redundancy Codes[END_REF]. Deflate is independent of CPU type, operating system, file system and character set, and hence can be used for interchange [START_REF]Deflate Specification[END_REF]. The illustrated flowchart in figure 2 shows the involved steps in the PNG encoder. In the following, we detail the different performed optimizations of the PNG encoder in order to well-ensure binary mask compression. To meet the standard defined by the format, the PNG file formatting can not be modified and remains unchanged regardless of the type of compressed data.

III. PROPOSED OPTIMIZATIONS OF PNG ENCODER FOR BINARY MASK COMPRESSION

A. Prediction stage

One of the key-features of PNG is the ability to chose out of five predictors (filters) for the predictive coding, namely: None (0), Sub (1), Up (2), Average (3) and Paeth (4). These filters are completely lossless and are applied to the raw image data before it is compressed and written to the output file. Every scan line of the image is preceded by a byte indicating the number of the used predictor among the five filter types. PNG format do not impose any contrainte on the type of filter to use. In addition, filters do not have the same effectiveness on the used data. Therefore, the PNG prediction stage consists to determine which filter allows a better data compression. A suggestion in the PNG specification is to apply every filter to each scan line, compress it and check the size. This is not very fast but it is easy to implement and this approach results in the best possible compression ratio. On the other hand, the None filter is recommended for images of bit depth less than 8 [START_REF] Randers-Pehrson | Portable Network Graphics) Specification Version 1.2[END_REF]. For low-bit-depth grayscale images, particularly the binary masks in our case (only 1 bit depth), it may be a net win to transmit all scan lines unmodified; it is just necessary to insert the filter type byte "0" before the data.

In this context, we conducted a study to determine the best filter to use in this work. For this, we examined the impact of each filter on the compression rate of a panel of binary masks. Indeed, one filter may be more effective than all the others. In such case, we implement only the corresponding filter in the proposed hardware design in place of the whole prediction stage. Figure 3 illustrates the obtained sizes in kilobytes of the PNG coded binary masks. For all images, a single filter is used each time. For comparison reason, the standard PNG prediction is also used, and noted by Pred.

Fig. 3. Efficiency of various PNG prediction filters through a panel of binary masks

According to this study, we can deduce the efficiency of each filter depending on the obtained compression rates. Indeed, we can observe in figure 3 that both Sub and Average filters are less suitable to the treated masks. The Paeth filter and the standard PNG prediction are also excluded in our case. They have a high complexity degree and a great need for memory resources while they conducts to similar PNG compression results as the remaining filters. Finally, the choice between Up and None filters is to not apply any filtering because, based on the conducted study, these two filters have almost the same compression results. This choice guarantees a competitive compression results while significantly simplifying our implementation. Hence, we maintain only the None filter in our hardware design, which amounts to not filter masks before Deflation.

B. Compression stage

After prediction, the coded pixel data is stored in a bitstream which is subsequently deflated. As mentioned above, the Deflate algorithm [START_REF] Peter | Deflate Compressed Data Format Specification version 1.3[END_REF] is a combination of LZ77 [START_REF] Ziv | A Universal Algorithm for Sequential Data Compression[END_REF], [START_REF] Deutch | [END_REF] and Huffman coding [START_REF] Huffman | A Method for the Construction of Minimum-Redundancy Codes[END_REF]. It uses a variably sized sliding window and sorted hash tables to identify data patterns and compresses them using Huffman coding. We discuss in this section the optimizations made of the Deflate algorithm for binary mask compression.

1) LZ77 (Hash function): LZ77 [START_REF] Ziv | A Universal Algorithm for Sequential Data Compression[END_REF] finds duplicated arbitrary sequence of bytes in the input data. The second occurrence of a string5 is replaced by a pointer to the previous one, in the form of a pair <length, backward distance>, corresponding respectively to the length of the redundancy and the distance separating the two redundant strings. Distances are limited to 32 kilobytes, and lengths are limited to 258 bytes. When a string does not occur anywhere in the previous 32 kilobytes, it is emitted as a sequence of literal bytes. For this, linked lists are created to quickly find the redundant strings in dictionary and research is done by triplets of bytes to ensure a minimum compression rate. Depending on the available memory resources and the desired performance, the PNG compression can be carried out using various hash functions. For each string of three new bytes, a new hash value is computed based on the previous one and stored in hash table. As exposed by equation 1, the general formula of the possible hash functions remains the same, only the size of the final result and the shift made during the computation may change.

H = ((h << shift len) XOR C) AND (2 hash len -1) (1)

With

H : hash value of the new triplet. h : hash value of the previous triplet. C : last byte of the new triplet. shift len : shift bit number. hash len : hash bit number.

In the PNG specification [START_REF] Randers-Pehrson | Portable Network Graphics) Specification Version 1.2[END_REF], shift len and hash len are respectively equals to 6 and 15. Thus, computed hash values are coded on 15 bits (see table I), and the used hash table has a 32 kilobytes size. The standard used hash function, named in the following Hash 15, is given by equation 2:

H = ((h * 40 16 ) XOR C) AND 7F F F 16 (2)
With a view to optimize the needed memory resources and speed up the hash value computations, more adapted hash functions can be considered to treat binary masks. The greater the hash len value is low, less is the required memory resources. However, fewer bits has the drawback of increasing the execution time. A statistical study to compute the triplets of bytes occurrence commonly encountered in binary masks was conducted. Based on the results of this study, two new hash functions Hash 10 and Hash 8 with respectively 10 and 8 bits hash len are proposed. Hash 10 and Hash 8 formulas are shown respectively by equations 3 and 4:

H = ((h * 10 16 ) XOR C) AND 3F F 16 (3)
H = ((h * 8 16 ) XOR C) AND F F 16 (4)
Given that H, h and C in equation 2, 3 and 4 follow the same notation used in equation 1.

A summary of shift len and hash len values of the studied hash functions is provided in table I. We note that, the obtained compression rates corresponding to Hash 8 and Hash 10 (equation 3 and 4) remain acceptable (see table III). However, a comparative study shows that Hash 10 provides a better compromise between runtime and compression rate. In addition, it still reducing significantly the needed memory resources (dictionary memory size becomes 1 kilobyte < 2 10 > instead of 32 kilobytes < 2 15 >). Moreover, when coupled with optimal parameters6 , the selected hash function Hash 10 allows to further speed up the final hardware design.

2) Huffman coding: Huffman coding [START_REF] Huffman | A Method for the Construction of Minimum-Redundancy Codes[END_REF] is an entropy encoding algorithm used for lossless data compression. The principle of this coding is to use fewer bits for strings which appear more often in data stream and more bits for the less frequently ones. To avoid conflicts of code, Huffman coding respect the prefix property. That means there is no bit-sequence encoding which can be the prefix of any other bit-sequence. Many variations of Huffman coding exist, some of which use a Huffman-like algorithm, and others of which find optimal prefix codes. In the PNG specification [START_REF] Randers-Pehrson | Portable Network Graphics) Specification Version 1.2[END_REF], the compressed data within the LZ77 data stream is stored as a series of blocks, each of which can represent LZ77-compressed data encoded with custom or fixed Huffman codes. Custom Huffman code is computed dynamically based on the appearance frequency of the strings in the data stream. This kind of coding contributes, generally, to the improvement of the achieved compression rates. However, this is at the cost of system slowdown and implementation complexity. By against, as shown in table II, fixed Huffman code are obtained according to a static lookup table specific to the standard. A comparative study of performance time, computational complexity and compression rate was conducted using respectively custom and fixed Huffman coding for PNG compression of binary masks. To strengthen the choice of the selected hash function Hash 10, all three evaluated hash functions are employed in this study. Table III presents the obtained compression rates of this study. We note that the difference between the average compression rates, obtained with custom and fixed Huffman coding, is very insignificant. Indeed, against an average compression rate around "0.89" obtained with custom Huffman coding, fixed one leads to achieve "0.8689". Therefore, in order to speed up computing and reduce needed memory resources, we chose to implement the fixed Huffman coding. 20minutes 300 0,85 0,7992 0,7993 0,7993 facture 002-recto 0,88 0,8652 0,8650 0,8650 facture 002-verso 0,97 0,9552 0,9550 0,9552 facture 012-recto 0,92 0,8999 0,8999 0,8999 facture 012-verso 0,88 0,8467 0,8467 0,8467 facture 062-recto 0,89 0,8710 0,8707 0,8708 facture 062-verso 0,98 0,9744 0,9744 0,9744 journal 07-recto 0,82 0,7856 0,7857 0,7857 journal 07-verso 0,81 0,7777 0,7779 0,7779 magazine 02-verso 0,81 0,7893 0,7893 0,7893 mobilesmag 300 0,91 0,8789 0,8789 0,8789 plaquette 0,99 0,9839 0,9838 0,9838 Average 0,89 0,8689 0,8689 0,8689

Furthermore, for the used panel of binary masks and regardless of the used hash functions (Hash 15, Hash 10, and Hash 8), the obtained compression rate with the fixed Huffman coding are almost invariable. So, it is obvious that Hash 10, and Hash 8 have no effect on the compression rate, however they reduce the amount of used memory compared to the Hash 15 function. As mentioned in section III-B1, Hash 10 provides a better compromise between compression rate, runtime and used memory ressources, and therefore maintained in our design.

IV. ACCELERATED PNG ENCODER HARDWARE DESIGN

Based on the described optimizations in the previous section, the proposed hardware design in this work is a part of an hybrid software and hardware co-operating system.

As shown in figure 4 7 , the PNG encoder design gathers a hardware implementation on FPGA and an external processor running a C program. These two elements have distinct roles:

• The Hardware implementation on FPGA performs data compression: optimized Deflate algorithm (no prediction, Hash 10, and fixed Huffman coding), • The external processor ensures the formatting of compressed data: issuance of PNG file header, the header of the IDAT chunks and the ancillary chunks. It launches also the PNG compression of masks.

In the following, we present the proposed hardware design to accelerate the PNG encoder on FPGA. Particularly the Input/Output, the Data, and the Hash managers, and the Data coder modules are described. The developed C code to ensure the software part is not described in this paper.

A. Input/Output manager

This module receives control signals from the processor (software part of the proposed design). Having the necessary informations 8 for the proper operation of the IP, it manages the inputs and outputs of the PNG encoder hardware part. Indeed, the Input/Output manager ensures an entry point of our design by collecting and filtering the incoming data, and an exit point by putting in shape the compressed data before transmission to the external system.

For each new incoming byte of uncompressed image, it updates four byte values (adler32) to be transmitted, sequentially, byte by byte to the LZ77 module. The Input/Output manager performs also the filtering of data, discussed at section III-A. We recall that in this work the used filter is the None one. Thus, byte "0" is just added in the beginning of each line. Finally, paging module is used to group compressed data by 32-bit words to send the output. Figure 5 7 shows an overview of the Input/Output manager module.

B. Data manager

The data manger module plays a central role within the proposed design. It allows to manage memories in which the redundancy research is made. For this, two memories are instantiated in the data manager memories block:

• window: contains the data dictionary on which the redundancy research is made,

• lookahead: contains the next bytes in the image that we look for matches in the window memory. We use in our design a dictionary memory of 1024 bytes (due to the use of the Hash 10 function, see section III-B1) and a lookahead memory of 256 bytes. However, various configurations can be seen in the context of improving system performance. Figure 6 7 shows an overview of the data manager module. The data manager memories block manages window and lookahead memories. Addresses of reading and writing are computed automatically based on the performed actions (update, redundancy research).

The len calc block compares all received data from the data manager memories to determine the redundancy lengths. For the same triplet of bytes, only the maximum length of the obtained redundancies and the corresponding position thereto are stored.

The controller of the data manager module cares about its proper operation but also acts as a master for the hash manager module (see following subsection IV-C). The main actions of the data manager ctrl block are:

• Obtain research positions from hash manager,

• Start and stop redundancy researches,

• Update window and lookahead Memories,

• Order the update of the hash manager module.

C. Hash manager

The hash manager module manages, essentially, the two used hash tables trieur and pointeur:

• Trieur: this table is addressed according to the hash values of the triplets to index. It stores the position of the last occurrences of each hash value. These positions point elements of the pointeur hash table,

• Pointeur: each cell of this Through the received order from data manager, hash manager module can update hash tables or perform researches thereto. Figure 7 7 shows an overview of the data manager module.

The hach calc block receives the triplet of bytes to encode byte by byte throw the data in input signal. It ensures the computation of the corresponding hash value according to the employed Hash 10 function.

D. Data coder

It may be difficult to achieve a hardware coding according to the provided tables in the deflate method [START_REF] Peter | Deflate Compressed Data Format Specification version 1.3[END_REF]. using lookup tables.

To obtain the codes corresponding to lengths and distances so this module uses a sequential method to determine the range of values in which are the distance and length. The algorithms used are described below. For evaluation, the proposed PNG IP has been implemented on the FPGA board ALTERA: "Arria II GX EP2AGX125EF35". Only simple formatting tasks were deported on the NIOS processor. In order to optimize the data path of the LZ77 module and obtain an optimal compression speed, two parameters were identified and assessed: MaxSearch and MinLength. They respectively indicate maximum number of searches to do and the length of the minimum redundancy to extract. Les courbes illustres par les figures 9 et 10 reprsentent des factures verso (triangles verts), recto (carrs rouges) et rectoverso, indiqu par All dans la lgende des courbes, (losanges bleus). Souvent, les faces recto des factures contiennent plus de donnes que celles du verso. Ceci explique, comme le montre les figures 9 et 10, l'augmentation du nombre de cycles de compression P N G dans le cas des faces recto et leur faible taux de compression par rapport aux faces verso.

Les rsultats obtenus montrent que M inLength = 50 pour toutes valeurs de M axSearch assure de meilleurs temps d'excution c'est--dire moins de cycles de calcul (voir figure 9). Toutefois, des valeurs plus faibles de M axSearch acclre le processus de compression. En effet, la rduction de la longueur minimale permet de trouver des redondances plus rapidement. De plus, limiter le nombre de recherches maximal permet d'interrompre les recherches assez longues sans avoir pour autant un grand impact sur les taux de compression dans

VI. CONCLUSION

This paper presented an optimized design of PNG encoder, with the aim of accelerating the binary mask compression on FPGA. Firstly, the PNG encoder was studied and obtained compression rates on binary masks were assessed. According to this study, a set of optimization was introduced namely the non use of the prediction stage, the proposition of a new hash function and the choice of the more suitable Huffman coding. As a part of an hybrid co-operating system, we proposed a new hardware design of the optimized PNG encoder. The experimental results was conducted on the "Arria II GX EP2AGX125EF35" ALTERA FPGA board.

The experimental results show

A good match between achieved compression rate and consumption in terms of computational costs, memory area and number of used logic elements.

Fig. 1 .

 1 Fig. 1. Minimal PNG File

Fig. 2 .

 2 Fig. 2. Overview of the PNG encoder

Fig. 4 .

 4 Fig. 4. Overview of the proposed P N G encoder design

Fig. 5 .

 5 Fig. 5. Input/Output manager Overview

Fig. 6 .

 6 Fig. 6. Data manager Overview

Fig. 7 .

 7 Fig. 7. Hash manager Overview

Figure 8 7

 8 Figure 8 7 shows an overview of the data manager module.

Fig. 8 .

 8 Fig. 8. Data coder Overview

Fig. 9 .

 9 Fig. 9. Average Clock Cycles of the proposed P N G encoder architecture according to combinations of M axSearch and M inLength parameters Un panel de factures recto-verso a t utilis pour les tests. Les masques binaires de ces factures sont extraits, en 150 ppp, l'aide de la mthode de segmentation en couches fond/forme DjV u [7]. Les rsultats de compression P N G de ces masques, obtenus avec l'architecture propose, sont illustrs par les figures 9 et 10. Ces deux figures affichent respectivement les nombres de cycles moyens et les taux de compression moyens de l'architecture P N G propose en fonction d'un ensemble de combinaisons des paramtres M axSearch et M inLength. Les exprimentations sont ralises en utilisant six valeurs de M ax -Search : 50, 100, 150, 200, 250 et 300 et trois valeurs de M inLength : 50, 150 et 250.

Fig. 10 .

 10 Fig. 10. Average compression rate of the proposed P N G encoder architecture according to combinations of M axSearch and M inLength parameters

TABLE I .

 I

	SHIFT LEN AND HASH LEN VALUES OF THE STUDIED HASH
		FUNCTIONS
	hash function	shift len	hash len
	Hash 8	3 ==> (2 3 = 816)	8 ==> (2 8 -1 = F F16)
	Hash 10	4 ==> (2 4 = 1016)	10 ==> (2 10 -1 = 3F F16)
	Hash 15	6 ==> (2 6 = 4016)	15 ==> (2 15 -1 = 7F F F16)

TABLE II .

 II STATIC HUFFMAN LOOKUP TABLE

	Input byte values	Number of bits	Fixed Huffman Codes
	0 -143	8	[ 00110000 .. 10111111 ]
	144 -255	9	[ 110010000 .. 111111111 ]
	256 -279	7	[ 0000000 .. 0010111 ]
	280 -287	8	[ 11000000 .. 11000111 ]

TABLE III .

 III PNG COMPRESSION RATES ACCORDING TO CUSTOM AND FIXED HUFFMAN CODING AND USING THREE DIFFERENT HASH FUNCTIONS

			Compression rates
	Images	Huffman Hash	Custom Hash 15	Hash 15	Fixed Hash 10	Hash 8

  table contains the position of the next occurrence of the hash value originally pointed to by the trieur hash table. Stored values in this table are therefore pointers to other cells in the same table.

Demat+ is a project established between the SagemCom company and the ESIEE P aris engineering school.

JPEG [4] uses the discrete cosine transform, and JPEG2000[START_REF]JPEG 2000 Image Codecs Comparison[END_REF] uses the wavelet transform.

The PNG file signature consists of eight bytes: <0x89 0x50 0x4e 0x47 0x0d 0x0a 0x1a 0x0a>.

A chunk consist of four fields: <Length, Chunk Type, Chunk Data, and CRC>.

String here must be taken as an arbitrary sequence of bytes, and is not restricted to printable characters.

Parameters refer to the maximum number of searches to do "MaxSearch" and the length of the minimum redundancy to extract "MinLength".

The used color code in these figures is: Purple ==> Control Elements, Orange ==> Logical Elements, and Green ==> Memory Blocks.

Based on image dimensions received from the processor, lines and columns counters are used by the Input/Output manager module to determine if the entire image was read.

ACKNOWLEDGMENT

The authors would like to thank Mr. Jérôme Berger, image and signal processing engineer at SagemCom company and Mr. Geoffroy Marpeau engineer at ESIEE P aris, they are very kind and patient.


Rostom Kachouri

Christian Medina

Mohamed Akil

GAMMA CORRECTION ACCELERATION FOR REAL-TIME TEXT EXTRACTION FROM COMPLEX COLORED IMAGES

Keywords: OCR, Scene Text, Complex Images, Text Extraction, Gamma Correction, Real-time

Text extraction from complex colored images involves the suppression of unwanted background while keeping text features. Imaging devices are almost omnipresent and the unrestricted conditions of the images present new challenges for real-time OCR systems. The recently proposed Gamma Correction Method [1] is a robust and good quality method for text extraction in complex colored images. However it requires a large amount of computing resources and is not well suited for real-time applications. In this paper we propose an efficient acceleration of the GCM to drastically reduce its execution-time, while preserving the text extraction quality. Experimental results on ICDAR dataset show that our approach is effective and can reach a speedup of up to 11.430.

INTRODUCTION

Optical character recognition (OCR) consists of several steps to extract information from text contained in digital images. The OCR process can be divided in segmentation, binarization and recognition. The segmentation procedure isolates text features in the image, the binarization outputs a binary image of the detected segment and the recognition step recognizes each individual character present in the binary image. The domain of application for OCR is wide and image sources abundant. The ubiquitous presence of devices capable of producing digital images demands quicker and more efficient text extraction algorithms for applications like traffic sign interpretation, automatic object inspection, detection of vehicle license plates, document retrieving, hand written text interpretation, video indexing among others. Examples of sources of text extraction images are digital reproductions of books, maps, documents, manuscripts, newspapers and document collections.

Scenes captured by imaging devices are diverse in characterization and can be grouped in three main categories: Document text images, caption text images and scene text images. Text extraction in these cases are widely studied and rely generally on edge detection, morphological filters, Wavelet trans-form, thresholding, DCT based high pass filter among others [START_REF] Sumathi | Survey on various apporoaches of text extraction in images[END_REF].

However in scene text images, where text appears within the imaged environment, the extraction of text becomes more challenging. This is due to the unrestricted conditions encountered in colored scenes and text presented in multiple sizes, fonts, distortions, partial occlusions within complex backgrounds. Existing methods related to this problems are based on applying adaptive color reduction (ACR), Principal Component Analyzer (PCA) and Self-Organized Feature Map (SOFM) [START_REF] Strouthopoulos | Text extraction in complex color documents[END_REF]. Zhan et al. uses multiscale wavelet features and SVM classifier [START_REF] Zhan | A robust split-andmerge text segmentation approac for images[END_REF]. Other methods propose Globally Matched Wavelet Filters (GWM) with fisher classifiers [START_REF] Kumar | Text extraction and document image segmentation usign matched wavelets and mrf model[END_REF] and a method insensitive to orientation, size and noise [START_REF] Babu | Text extraction from heterogeneous images using mathematical morphology[END_REF]. Zhang et al. proposed a method based on link energies [START_REF] Zhang | Text detection using edge gradient and graph spectrum[END_REF].

Among the most recent text extraction methods for scene text images Sumathi et al. proposes the Gamma correction Method (GCM) [START_REF] Sumathi | Automatic text extraction from complex colored images using gamma correction method[END_REF]. This method consists of a procedure to partially or completely suppress the heterogeneous background whilst preserving text features. The quality of the results of the GCM proves that it is well suited for demanding applications. On the other hand, the computing resources required by the GCM are considerable and its integration to a real-time OCR system presents difficulties. In this paper we propose an acceleration to the GCM that reduces the execution time and needed resources but conserves the quality of the results.

In the following, section 2 deals with the GCM, then we describe the proposed acceleration process in section 3. In section 4 we present the obtained experimental results and finally we conclude in section 5.

TEXT EXTRACTION BASED ON GAMMA

CORRECTION METHOD (GCM) [START_REF] Zhang | Text detection using edge gradient and graph spectrum[END_REF] The gamma transform, expressed in equation 1, is an operator that depends on the parameter γ. Where γ < 1 results in a whiter image and γ > 1 results in a darker image than the original. The original image is described by the instance of γ = 1.

q(i, j) = p(i, j)

1 γ (1)
The GCM [START_REF] Sumathi | Automatic text extraction from complex colored images using gamma correction method[END_REF] transforms the input image to gamma-transformed images using a range of γ from 0.1 to 10.0 with increments of 0.1, resulting in 100 different gamma values. Thus a total of 100 gamma-transformed images have to be computed and for each image three features are calculated as described in below.

Two textural features derived from the Gray-Level Co-Occurrence Matrix (GLCM) are used to characterize each gamma-transformed image. Haralick [START_REF] Haralick | Textural features for image classification[END_REF] proposed in 1973 the GLCM matrix and a set of 14 textural features while working in the surface classification of aerial and early satellite images. The GCM only uses two textural features: Energy (equation 2), also called Angular Second Moment (ASM), which measures the smoothness of the image and Contrast (equation 3), which measures local gray level variation.

Energy = 1 4 Σ α Σ Ng i=1 Σ Ng j=1 p(i, j) R 2 (2) Contrast = 1 4 Σ α Σ Ng-1 n=0 n 2 Σ |i-j|=n p(i, j) R (3)
Where p(i, j) is the value of the reference pixel, α is an angle value and R is a normalization term. The number of possible Gray-level values N g in the image is usually 256. The texture features should be equal for an image A and a rotated version of A called B. In order to comply with this requirement, texture features are interpreted using the average of the features computed from four possible GLCM α angles belonging to the set {0, 45, 90, 135}.

The threshold value is calculated using Otsu's Threshold [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF]. The algorithm aims to separate the foreground and background pixels by minimizing the intra-class variance σ i separated by a threshold value t defined in equation 4.

σ 2 w (t) = w 1 (t)σ 2 1 (t) + w 2 (t)σ 2 2 (t) (4)
This value is computed directly from the gamma-modified image. Table 1 its corresponding Otsu's Threshold value. All gamma values are considered to have equal probability of being selected by the GCM algorithm as the best gamma-transformed image to threshold. The selected image can be identified by its unique gamma value, this value is called selected gamma value, SGV. figure 1 illustrates the GCM result from a sample image that belongs to the ICDAR data set [START_REF]Text in scene images[END_REF]. However, the resources needed to compute the 100 gamma transformed images and the Co-occurrence Matrix features are very large and the overall execution time to select the SGV is excessively high. For example the execution time of GCM on the input image in figure 1(a) is 2.13019 seconds, which is not well suited for a real-time system but has an effective result, shown in figure 1(c).

In the following section we propose an acceleration to the GCM that will allow to keep the quality of the results and dramatically reduce the computation time.

ACCELERATED GCM (AGCM)

We propose an acceleration of the previously described Gamma Correction Method, that we will call in the following AGCM. The AGCM uses the same input and evaluation parameters used by the GCM. Instead of analyzing the parameters of the whole set as individual values with the same probability of being the selected gamma value, the accelerated method predicts a sub-range of values where the selected gamma is expected to be found by the GCM. The AGCM uses a set rules derived from a behavioral analysis of parameter values. This approach was inspired from the fact that similar images will lead necessarily to similar evaluation parameters and eventually to the same SGV.

Behavioral study of the parameters used in the GCM

A behavioral study of the energy, contrast and Otsus threshold curves and the selected gamma value was conducted and allowed the identification of important facts which are the basis to build the relations between parameter behaviors and subranges of the gamma values.

Figure 2 shows plots of the entire set of contrast, energy and Otsu's threshold values computed by the GCM. Notice that the energy and threshold curves are plotted according to the left y-axis scale and the contrast curve is plotted according to the right y-axis scale. The Continuous curves in figure 2 show the plot with the 100 values computed by the GCM. Depending on the shape of the contrast curve each image was classified as either increasing, decreasing or stable. The presence of peaks and abrupt changes in the curve were also taken in account. Abrupt changes are called discontinuities since they represent a dramatic change in the visual perception of the resulting image. These curves show in a clear way the behavior of the features and allow us to extract relations between the curve and the SGV, not by numerical criteria but rather by the shape of the curve. These relations are presented in the following sub-section.

Derived behavioral rules

As mentioned above, the contrast curve is the main factor (first order feature) of influence on the gamma value region. Other factors (second order features) that must be evaluated in a second stage are high energy values and Otsu's Threshold peaks. We present a description of the main behaviors and their relation to the SGV.

The contrast curve has three main behaviors: Always increasing, decreasing or stable. An always increasing curve (see figure 2(a)) has an optimal gamma value of 10.0 and are generally images without many variations or features. A decreasing curve has, in general, the optimal gamma value near its peak point. The peak of a decreasing curve is always located in the range of γ = [0.9 -3.5]. (see figure2(b)). A stable curve (see figure 2(c)) denotes an image that is more influ-enced by second order features than by the contrast curve behavior.

The energy curve is always increasing. Energy is usually low at low-gamma values and has a tendency to increase at the end of the curve. Initial and final energy values that do not comply with the previous statement influence in the estimated gamma value. A flat curve is the result of a text image or alike.

The threshold curve is always decreasing since the increase in gamma renders the image darker (lower pixel values). A peak in the curve is direct evidence of the transition of a significant sized block from bright to dark values.

The relations of curve behaviors and SGV can be used to predict a sub-range of gamma values that contain the SGV. In addition, a sampled curve can produce a simplified, but reliable, version of the feature curves while avoiding the calculation of values that are not candidates for the SGV. In the following we explain the computation and use of this sampled curve.

Curve Sampling

We propose to compute the parameter values (contrast, energy and Otsu's threshold) at particular sampling points. The sampled gamma value points are: γ = [0.1, 1.0, 2.0, 2.5, 5.0, 7.5, 10.0]. These values were chosen from the regions that contain the gamma values that define the behavior of the parameter curves so that the entire curve can be reliably classified.

The sampled curves can be compared in figure 2 Sampled curves against the Continuous curves. We can see that the extracted feature behavior is completely preserved.

Gamma Sub-Range Prediction

The relations provided by the behavioral study can be applied in order to predict the gamma value sub-range. These relations are formalized in the flow chart presented in figure 3. The flow chart has 6 possible branches numbered from Return 1 to Return 6. These returns can be grouped in 3 main branches. the contrast curve is always increasing: Return 1. The contrast curve is always decreasing: Return 2 and 3. The contrast curve is stable: Return 4, 5 and 6.

By examining the results from the GCM we can notice that certain type of images always get a particular selected gamma value. For example images that present a smooth background or an image that is mostly dark with a small light feature will always lead to a γ sel = 10.0, while images with a clear text feature and a heterogeneous background usually have a selected gamma value that belongs to the middle section of all the considered values but its never located in the upper or lower bounds of the range.

In particular cases the estimated gamma value by the AGCM may be different from the GCM computed gamma (See figure 2, stable case). The experiments presented in the following section prove that this difference between the two SGV allow to improve the quality of the obtained results.

RESULTS

For evaluation purposes, the ICDAR Reading Text in Scene Images dataset [START_REF]Text in scene images[END_REF] was used as input to benchmark the AGCM. The set contains 113 complex color images with text. The GCM and AGCM were coded using C++ and executed under Windows 7 running in an Intel R i3 CPU at 3.07 GHz.

The gamma sub-range prediction of the AGCM dramatically improves the execution-time of the method while preserving the quality of the GCM results. As expected, the AGCM output contains the same quality of the GCM results, making it robust and reliable (figure 4, first and second images). The behavioral rules of the sub-range prediction algorithm can sometimes lead to a better binarization than the GCM. An example of this case is presented in the third image of figure 4. This is mainly due to the analysis of peaks in the energy and threshold curves.

Figure 5 presents the superposed execution-times of the GCM and AGCM over the ICDAR image set [START_REF]Text in scene images[END_REF]. The execution-time of the AGCM can not be generalized in a fraction of the GCM's execution-time because the gamma sub-range prediction size is variable from 0.1 (Return 1 and 6) to 2.0 (Return 4). This makes that the number of gamma-modified images that have to be calculated and features analyzed is variable, while the GCM always analyses 100 images. In spite of this variability, the execution-time of AGCM presents an average speedup s = T GCM /T AGCM of 4.456 and in best cases a speedup of 11.430 (from the dataset execution-times presented in figure 5). These results are significant and encouraging for the integration of the AGCM method to a real-time system.

CONCLUSION

This paper has introduced the GCM as a robust method for the segmentation and binarization of text features in complex color images. We presented a behavioral study of the curves generated by the analyzed textural features and an effective sample method that retains the behavior of the curves. Together they reduce dramatically the execution-time of the entire process while keeping the good results of the original method. This improvement renders the AGCM more suitable for its integration in real-time applications. Further improvement of the execution time can be done by a parallelized version of the algorithm.

Fig. 1 .

 1 Fig. 1. GCM Results: (a) Original image, (b) Gamma Transformed Image with SGV = 5.5, (c) Output image [1].

Fig. 2 .

 2 Fig. 2. Image classifications and the corresponding feature curves: (a) Original images, (b) Continuous feature curves, (c) Sampled feature curves. Contrast curve (Red), Energy (blue), Otsus's threshold (green) and SGV (vertical magenta line).

Fig. 3 .

 3 Fig. 3. Flow chart to predict the gamma values sub-range. Where c = contrast, e = energy, o = Otsu's Threshold.

Fig. 4 .

 4 Fig. 4. Comparison of the GCM and AGCM results.

Fig. 5 .

 5 Fig. 5. Comparison of the GCM (blue) and the AGCM (red) execution-times for a set of 113 images.

Table 1 .

 1 shows an example of the computed values. A set of 3 rules estimates which gamma-transformed image will suppress the largest amount of background while keeping the text features. The background suppression and binarization is done by thresholding the selected image using First

	Gamma	Energy	Contrast Otsu's Threshold
	0.1	0.005508 20.2623	0.902344
	0.2	0.002021 67.5451	0.820313
	0.3	0.001264 127.710	0.750000
	...
	9.8	0.463231 361.558	0.332031
	9.9	0.474122 359.967	0.328125
	10.0	0.485401 358.094	0.339844

and last three values of features from the gamma transformed images computed by the GCM from the input image presented in figure

1

(a).