Olivier Augereau
email: augereau@labri.fr

Nicholas Journet

Jean-Philippe Domenger

Semi-structured document image matching and recognition

Keywords: document image matching, interest points selection, geometric transformation estimation, document image retrieval

This article presents a method to recognize and to localize semi-structured documents such as ID cards, tickets, invoices, etc. Object recognition methods based on interest points work well on natural images but fail on document images because of repetitive patterns like text. In this article, we propose an adaptation of object recognition for image documents. The advantages of our method is that it does not use character recognition or segmentation and it is robust to rotation, scale, illumination, blur, noise and local distortions. Furthermore, tests show that an average precision of 97.2% and recall of 94.6% is obtained for matching 7 different kinds of documents in a database of 2155 documents.

INTRODUCTION

This work takes place in an industrial context where thousands of document images are digitized daily. Document images include payrolls, bills, information letters, mails, etc. Some examples are displayed in figure 1. The objective is to recognize and to localize semi-structured documents. A document is semi-structured if some information are at the same place in every document of the same type. As we can see in figure 2, documents can have geometric variations such as rotations or uniform zooms but also missing information or strong local distortions related to noise, deformation, cropping, stains, etc. The problem is to recognize and to extract parts of document images. This issue has been addressed in the context of natural images. Proposals have been made to align images, [START_REF] Yang | Alignment of challenging image pairs: Refinement and region growing starting from a single keypoint correspondence[END_REF] to search logos 2 or to create panoramas. [START_REF] Brown | Automatic panoramic image stitching using invariant features[END_REF] All these techniques use interest point detectors such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] or SURF. [START_REF] Bay | Speeded-up robust features (surf)[END_REF] For document images retrieval, these techniques have never been used. As pointed out by Uchiyama and Saito 6 the methods based on interest point such as SURF fail to handle poorly textured objects or repetitive binary patterns such as text. A study of document image retrieval can be found in Doermann survey. [START_REF] Doermann | The indexing and retrieval of document images: A survey[END_REF] We will briefly expose new document image retrieval techniques. Agam et. al [START_REF] Agam | Content-based document image retrieval in complex document collections[END_REF] address the problem of content-based image retrieval in the context of complex document images. Their context is typically the same as ours. The documents are printed, sometimes modified by handwriting and could contain graphics, tables and other non-textual elements. Usually, only OCR is used for retrieval and the authors suggest to also use structural context and non-textual information. In order to do this, many preprocessing are done with Abbyy's SDK [START_REF]Ocr, icr, omr and linguistic software[END_REF] and others packages: noise removal, skew correction, document layout segmentation, etc. The main drawback of this methodology is that each preprocessing step can generates and accumulates errors. For example, document segmentation is a very complex task and Abbyy's SDK has difficulties on multi-oriented and multi-sized documents, 9 images and graphics recognition [START_REF] Clausner | Scenario driven in-depth performance evaluation of document layout analysis methods[END_REF] and complex documents such as historical documents. [START_REF] Antonacopoulos | Historical document layout analysis competition[END_REF] The benefits of our method is that it does not need any segmentation or preprocessing and it is robust to noise and geometrical transformation.

Takeda et al. [START_REF] Takeda | Real-time document image retrieval for a 10 million pages database with a memory efficient and stability improved llah[END_REF] introduces a real time method based on interest points to find a given query image in a 1-million document database. Extracted points are the centers of the words so text has to be segmented and letters must be grouped effectively. According to the authors of this method, it implies that when illustrations, tables or other elements than machine printed text are present in documents, results are less good. Therefore, pictures, tables, logos and handwritten text are frequently present in our context, so this technique is unsuitable for our purpose.

Hull et al. [START_REF] Hull | Paper-based augmented reality[END_REF] present a document retrieval method based on N-grams. The number of characters of each word is computed. For example the 3-grams of "structured document image matching" will be : "10 -8 -5" and "8 -5 -8", because the number of letters of "structured", "document", "image" and "matching" are respectively 10, 8, 5 and 8. Horizontal and vertical n-grams are combined. As Takeda's technique, the drawback of this method is that it is used only for mainly text document.

The methods of Takeda and Hull can not be applied to our complex document images. Furthermore, these techniques do exact retrieval while we want to do non-exact retrieval, i.e. when user show a train ticket, he wants to retrieve all similar train tickets and not only this particular one.

Rusiñol and Lladós 14 as well as Jain and Doermann [START_REF] Jain | Logo retrieval in document images[END_REF] introduce logo retrieval techniques in document images. These two methods are both based on interest points (respectively SIFT and SURF) and geometrical consistency which is very close to standard object recognition technique.

We propose to extend a standard object recognition technique in order to use it for the retrieval of document images. At first we will show that a standard object recognition method is not performing on document images because of repetitive patterns. An average precision of 17.0% is obtained. Thus, this standard method needs to be adapted for the specific case of document image matching. Then we will present our main contribution, which is an object recognition algorithm adapted for document images. We improve a standard object recognition based on SURF for matching document images and obtained an average precision of 97.2%, which allows this technique to be used by digitizing companies.

STANDARD OBJECT RECOGNITION ON DOCUMENT IMAGES

In this section, a standard object recognition is tested in order to show that the technique has to be improved in order to be usable for document image matching. The standard proposed methodology is inspired by the Lowe 4 's one. The methodology can be seen on figure 3. Initially, for each type of researched document, a query image is given by user. Interest points are extracted with SURF 5 on all images. Interest points of the query image are matched with each image of the database by using FLANN, 17 a fast and approximative nearest neighbor algorithm. Finally, the 4-parameter transformation that matches the query with an image of the database is estimated with a method based on RANSAC. [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] According to Lowe, if at least 3 matches validate the geometric transformation, the object is considered to be present. So, the geometric matrix is used for localization only if document is recognized, i.e. 3 matchings validate the transformation. In the next sub-sections a brief explanation of each step of standard object recognition is exposed.

Interest points extraction and description

Interest points are extracted and described for all images. Interest points are detected using SURF. An integral image 5 is used in order to speed up calculations, then interest points are found on high intensity variation zones in image I by using the Hessian matrix:

H(I(x, y)) = ∂ 2 I ∂x 2 ∂ 2 I ∂x∂y ∂ 2 I ∂x∂y ∂ 2 I ∂y 2
Each point is then described with SURF features. This step is based on Haar wavelet and provides a 64dimension vector, an orientation and a scale value for each point. A difficulty is that document images have a lot of interest points. On average, each document image of our database have 9647 interest points.

Matching interest points

Each interest point of the query image is then matched to the most similar interest point of the images of the database by computing euclidean distance between the 64-dimensional vectors. The position information is not used here. The complexity of k-NN (nearest neighbor) is quadratic as a function of the number of points. Using KD tree for vector comparison improves research time in low dimensions. Silpa-Anan & Hartley 19 suggest to use multiple randomized kd-trees in order to speed up k-NN research. FLANN provides an implementation of this algorithm where multiple trees are built in 5 random dimensions. Because there are a lot of matchings, two filters such as in SIFT 4 are applied. Firstly, if the 2nd NN is too close to the 1st NN (in 64-dimension space) the matching is considered to be wrong. Secondly, each matching votes for an orientation and a scale using Hough with coarse bins. Only matchings who has voted for the majority are kept. Figure 4 shows the importance of the filtering step.

Geometric transformation estimation

The aim of this step is to split the set of matchings between good matchings (inliers) and mismatchings by using RANSAC algorithm. In order to estimate the 4-parameter transformation matrix M between the query image and the image to compare, the most representative transformation among all matchings is searched. The matrix M has the following shape :

M.   x y 1   =   s.cos(θ) -sin(θ) T x sin(θ) s.cos(θ) T y 0 0 1   .   x y 1  
The RANSAC algorithm is composed of two main steps. 1) The smallest subset needed to estimate the geometric transformation is randomly selected. 2) Other elements validating the transformation (inliers) are searched. If there is not enough inliers, the algorithm returns in 1), otherwise the model is validated. If no model is validated after M AX IT ER trials, the algorithm is stopped. M AX IT ER is empirically set to 200. If M AX IT ER is too low, the best set of inliers could be missed and if it is too high, it will slow down the execution time. Another threshold is fixed in RANSAC : DIST V ALID. It is the maximum distance between the expectation position of matching given by the transformation and the real position of matched point. This value represents the checking process tolerance. Since the geometric transformation is supposed to be linear, the value should not be too high. However, we are working on relatively large images, because A4 documents scanned at 200 dpi are about 1654 pixels x 2339 pixels. We have experimentally determined DIST V ALID to 10 pixels. This value allows some tolerance to low distortion. If this value is increased too much, the risk of false detection will be increased too. Figure 4 shows the impact of RANSAC on matchings.

Finally, if at least t inliers are validated, the document is considered to be present in the image. We chose t = 3, according to Lowe advice.

Recognition performance

The recognition performance of standard object detection has been tested on a database composed of 2155 images scanned by Gestform * digitizing company. There are 3 main image categories: identity documents, expense reports and human resource documents. All images are digitized at 200 dpi and automatically binarized by scanners. Documents are distributed in 381 classes such as passports, residence cards but also taxi receipts, hotel invoices, lunch vouchers, from severals companies. We focus only on 7 classes representing 46% of the documents of the database. These 7 classes are : French identity cards, French passports, "S.N.C.F." train tickets, "Bordereau" which is an overview of expense report, "Challenger" restaurant tickets, "Orange" invoices and "American Express" receipt of a company. For each of this 7 types of document, a query image is randomly taken. These example images are displayed in figure 5. Then, each of the 7 query images are matched to each * www.gestform.com images of the database. The objective is to recognize which images of the database contain the same document as the query image. ,c) packing slip "Bordereau", d) train ticket "SNCF", e) "passport", f) invoice "Orange" and g) receipt "American".

All tests have been performed with an Intel Core 2 Duo, 2 GHz. The results of test 1 are displayed in table 1. It shows recall, precision, average time used for image matching and the number of extracted points with SURF. This table clearly shows the limits of standard object recognition applied to document images. Performances in terms of precision are extremely poor, an average of 17.0% is obtained. Most of documents are mis-detected because of the amount of points extracted and the difficulty of making good matchings. They are so many mismatching that a consensus of 3 matchings is obtained on most images. It could be pointed out that the number of interest points extracted impacts the precision of the matching. The conclusion of this test is that standard object recognition can not be applied to document images without any adaption of the methodology. Matching results show that spatial and geometric constraints have to be strengthen in order to limit the number of mismatchings. Furthermore, we want to reduce the number of interest points used to describe example of each class in order to reduce time processing and the probabilities of mismatchings.

OBJECT RECOGNITION ADAPTED TO DOCUMENT IMAGES

We propose two main contributions in order to drastically improve recognition performances. The first idea is to decrease the number of interest points in query images in order to decrease processing time and improve performance of the methodology. In order to do this, we propose to select relevant interest points by analyzing similarities of interest points between a query image and several other images of the same type.

Then, because there are many pattern repetition such as text in document images, we propose to change RANSAC algorithm in order to add spacial and geometrical constraints for decreasing the amount of mismatchings. The schema of the adapted process is presented in figure 6.

Adapted RANSAC

The algorithm 1 describes precisely our adaptation of RANSAC algorithm for validating matchings. Let S Q be the set of points of the query image matched to S D , the set of points of the image of the database. The 4-parameter transformation matrix M is used to find the set of inliers I. After adapted RANSAC, the document is detected only if there are at least t = 8 inliers (in opposition to standard detection where t = 3 according to Lowe). Adapted RANSAC allows to greatly improve precision due to geometrical constraints and slightly improve time processing because many mismatching are now ignored.

Algorithm 1 Adapted RANSAC INPUT SQ, SD OUTPUT I, M SI ← ∅, iter ← 0 while iter < M AX IT ER do Let PQ1 & PQ2 be 2 points randomly selected in SQ. Let PD1 & PD2 be the matchings of PQ1 & PQ2 in SD if (|| -----→ PQ1PQ2|| < M IN N ORM )||(|| -----→ PD1PD2|| < M IN N ORM ) then iter ← iter + 1 continue end if Let Mt be the current transformation matrix Let It be the current set of inliers Mt ← transf o( -----→ PQ1PQ2, -----→ PD1PD2) It ← ∅ for each PQi ∈ SQ\{PQ1, PQ2} do Let PDi be the matching of PQi in SD skip = f alse for each Ij ∈ It do if (|| -----→ PQjPQi|| < M IN DV ALID)||(|| -----→ PDjPDi|| < M IN DV ALID) then skip = true break end if end for if skip then continue end if P ′ Qi ← Mt[PQi] if || -----→ PDiP ′ Qi || < M AX DIST then It ← It ∪ -----→ PDiP ′ Qi end if end for if Card(It) > Card(I) then I ← It, M ← Mt end if iter ← iter + 1 end while return I, M

Interest point selection

Because there are many interest points, processing time is long and probabilities of mismatchings are high. In order to decrease the number of interest points, we take five additional query images for each type. For one document type, each five images are matched to the first query. The matching is done by using the adapted RANSAC methodology giving 5 sets of inliers. The union of points used in the first query for matching these 5 others query are the final selected interest points. The figure 8 shows the difference between before and after interest point selection.

PERFORMANCES OF ADAPTED DOCUMENT IMAGE OBJECT RECOGNITION

Application and results on a real database

The same database is used as in section 2.4, in order to show improvement of results with our method. The same tests are performed and results are detailed in table 2. By using adapted RANSAC and interest point selection, on average, precision is multiplied by a factor 5.7 and processing time is divided by 2.0. Globally, the recall has slightly decreased in comparison with the first test. In test 1, the precision was extremely low and recall extremely high since almost all documents were wrongly detected. In test 2, presented in current section, the precision is greatly increased. The slight decrease of recall is widely balanced by the large increase of precision.

The precision is quite good but some false detections are still done because some different documents are too similar or have similar parts with the query image. Figure 9 shows examples of false detections. "Challenger" are restaurant tickets, the 6 wrong matchings of this document happen with other restaurant tickets with the same design. "Orange" are mismatched with 3 "Air France" tickets because a large word is matched. Another example of mismatching is the logo "American express" (labelled as an invoice) which is mismatched with the same logo "American Express" within a document labelled as account statement.

If the precision has to be improved, global geometrical constraints have to be straightened. Instead of taking only t = 8 minimum inliers for validating the transformation, t can be increased. The drawback is that the recall ) is mismatched with another restaurant ticket a2). The "Orange" invoice b1) is mismatched with "Air France" tickets b2). The "American" invoice is mismatched with an account statement c2).

will drop-off if t is too high and it does not prevent inliers to be matched locally. In order to do this, we advise to increase the threshold M IN DV ALID. In this case, the minimum distance for validating a new inlier will be increased. But if M IN DV ALID is too high, noisy documents will no longer be detected. Figure 10 shows examples of a good matching for each of the 7 types of documents.

Application and results on a noisy semi-synthetic database

Tests of the SURF robustness for scale changes, rotations, blur, illumination changes and affine transformations have already been made in Juan & Gwun study. [START_REF] Juan | A comparison of sift, pca-sift and surf[END_REF] Document images are prone to a certain kind of noise due to digitizing operation. This noise could be synthesized by using Kanungo model. [START_REF] Kanungo | Global and local document degradation models[END_REF] In this subsection, we want to show that our system is robust to this frequent noise. This noise synthesizes bad scanner resolution or bad document image quality. In such case, OCR have extremely bad results.

The same database as in previous sections is used here. All images of the database have been degraded with random strength of Kanungo noise from factor 0 (not degraded) to factor 9 (highly degraded). The figure 11 shows an example of different strengths of Kanungo noise.

The table 3 shows that even with noisy documents, our system is still efficient. We can notice that the precision surprisingly increase for 2 types of documents "Challenger" and "Orange". The explanation is that the mismatched documents are no longer retrieved by the system due to noise. These documents were mismatched in test 2 with the minimum number of required matchings.

CONCLUSION AND PERSPECTIVES

Identification of semi-structured document images is done very accurately using the method described in this article. The main advantages of this method is that it can guarantee a very high recall and precision, it does not need any segmentation, it is robust to deformation and can scale to any semi-structured documents. User just need to provide one example of image to retrieve other documents. But this method is limited to semi-structured documents, i.e. documents which have some similar parts in similar places. In the case of application to images that contain text, the problem of repeated pattern is mainly caused by letters. If documents are mismatched, thresholds can be increased in order to strengthen constraints. But if documents have similar parts, user must be aware that documents will be matched together with this techniques. So it will not be possible to distinguish sub-types of documents.

The main perspective is to improve processing time. This could be done by using lighter descriptors like those used by Nakai et al. [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF] or Rusignol and Llados. [START_REF] Rusinol | Logo spotting by a bag-of-words approach for document categorization[END_REF] Another idea is to integrate in our methodology the use of bags of visual words [START_REF] Valle | Advanced Techniques in CBIR: Local Descriptors, Visual Dictionaries and Bags of Features[END_REF] or bag of region [START_REF] Vieux | Content based image retrieval using bag-of-regions[END_REF] to associate a confidence measure to a decision in order to quickly reject wrong image matchings.

The second perspective is to analyze further interest point selection, because it has a strong influence on performances of the system recognition.

Figure 1 .

 1 Figure 1. Images from dataset. In these examples there are train, airplane and restaurant tickets, invoices, identity documents and one human resource document.

Figure 2 .

 2 Figure 2. Examples of degraded images. Documents are rotated, cropped, folded, and also have stains and noise.

Figure 3 .

 3 Figure 3. Standard process in 4 steps. 1) Interest point are extracted and described for all images. 2) Each query image is matched with each image of the database. 3) The geometric transformation is estimated for each matching. 4) If the number of matched points is superior to the threshold t, the document is recognized and localized in the image of the database.

4

 4

Figure 4 .

 4 Figure 4. Document matching. a) There are 7687 matchings. b) After filtering, there are 235 matching. c) After RANSAC there are 40 matchings. The transformation found have following parameters : rotation = 5.665 degree, scale = 1.003, horizontal translation = 801.7 pixels and vertical translation = 108.3.

Figure 5 .

 5 Figure5. Examples of 7 models: a) identity card "ID", b) restaurant ticket "Challenger", c) packing slip "Bordereau", d) train ticket "SNCF", e) "passport", f) invoice "Orange" and g) receipt "American".

Figure 6 .

 6 Figure 6. All steps of the adapted process. Standard RANSAC is replaced by adapted RANSAC. The point selection is added in order to decrease the number of interest points of query images.

  In this adapted version, two new thresholds appear: M IN N ORM and M IN DV ALID. M IN N ORM is used to not calculate the transformation matrix from a vector which norm is too small as it may induce a distorted result. The second threshold M IN DV ALID is used to validate matchings only if they are not too close to each other. These two thresholds can avoid the wrong matchings as the ones displayed at figure 7. M IN N ORM and M IN DV ALID have been empirically fixed to 5 pixels. These thresholds have been validated by tests performed on documents of different sizes. The thresholds are not sensitive but must be set to a minimum value in order to avoid problems such as those of the figure 7.

Figure 7 .

 7 Figure 7. Example of wrong matchings avoided with adapted RANSAC. In a) 6 distant points are matched to 2 similar points. In b) 3 close points are matched to another set of 3 close points. Related transformation is estimated with points that are too close and validated by another points that are very close too. In all cases, there are too many matchings in too small space. Adapted RANSAC forbids such matchings.

Figure 8 .

 8 Figure 8. Interest point selection. Gray circles are printed on images for each interest point. Above, example images without point selection, there are a lot of interest points. Below, example images with feature selection, there are less interest points. Interest points are not selected randomly, they are selected if they are present in another document of the same type. We can see that interest points of variable parts are not selected such as : b) the picture of an ID card, c) the signature of a passport, d) the name of towns in a train tickets and d) the destination address in an invoice. The number of selected points is detailed in table 2.

Figure 9 .

 9 Figure 9. Examples of mismatchings. The query document "Challenger" a1) is mismatched with another restaurant ticket a2). The "Orange" invoice b1) is mismatched with "Air France" tickets b2). The "American" invoice is mismatched with an account statement c2).

Figure 10 .Figure 11 .

 1011 Figure 10. Examples of good matchings. Matching of each 7 queries with a document of the database.

Table 1 .

 1 Recall, precision and average execution time per image for each document type. Standard detection produces a lot of wrong detections, so the precision is very low. Time processing and precision are linked to the number of interest point extracted on the queries.

	Type	Nb images Nb interest points Recall Precision Time / image
	Id cards	483	7687	0.996	0.419	2.9 s
	Passport	89	10059	1.00	0.117	3.9 s
	SNCF tickets	35	4934	1.00	0.0502	2.4 s
	Bordereau	229	751	0.991	0.464	1.3 s
	Challenger	58	1573	1.00	0.137	1.6 s
	Orange	58	14741	1.00	0.0366	5.0 s
	American	41	8714	0.951	0.0266	2.8 s

Table 2 .

 2 Number of selected points, recall, precision and average execution time per image for each document type. Adapted detection with point selection drastically improves precision and time processing.

	Models	Nb images Nb points Nb selected pt. Recall Precision Time / image
	Id cards	483	7687	306	0.919	1.00	1.01 s
	Passport	89	10059	1284	0.978	1.00	1.14 s
	SNCF tickets	35	4934	1846	0.971	1.00	1.58 s
	Bordereau	229	751	281	0.900	1.00	1.06 s
	Challenger	58	1573	626	1.00	0.879	1.15 s
	Orange	58	14741	4444	1.00	0.951	2.30 s
	American	41	8714	3017	0.853	0.972	1.49 s

Table 3 .

 3 Number of selected points, recall and precision for each document type. Performance on a noisy database are slightly lower but still good. Information in brackets represents the evolution of performances in comparison with test 2 (original database with no additional noise).

	Models	Nb images Nb points Nb selected pt.	Recall	Precision
	Id cards	483	7687	306	0.830 (-0.089)	1.00
	Passport	89	10059	1284	0.978	1.00
	SNCF tickets	35	4934	1846	0.971	1.00
	Bordereau	229	751	281	0.721 (-0.179)	1.00
	Challenger	58	1573	626	1.00	0.983 (+0.104)
	Orange	58	14741	4444	0.983 (-0.017)	1 (+0.049)
	American	41	8714	3017	0.659 (-0.09)	0.964 (-0.003)

Acknowledgment

We thank Gestform company for its involvement and Mr. Jean-Marc Nahon, director of computer science studies of the company. All images were provided by Gestform.