UAEMex at ImageCLEF 2016:

Abstract

This paper describes the participation of the (UAEMex) at the ImageCLEF 2016 Handwritten Scanned Document Retrieval Task. We propose to use a skip-character text search method based on Longest Common Subsequence. Our system split all characters in query to find all Longest Common Subsequence in one line of text.

Keywords

• Information Retrieval
• Longest Common Subsequence
• Free Text Search

-

1  

Introduction

This paper describes the free text search method used by UAEMex at the ImageCLEF 2016 [ 3 ] handwritten retrieval task [ 4 ]. The 1st edition of the handwritten retrieval challenge has one task targeted in free text search. Considering transcript text for every character we use a skip-character text search method based on Longest Common Subsequence (LCS) problem. 2  

Fixed Gap Longest Common Subsequence

The problem to extract LCS consists of given two sequences find the length of longest subsequence present in both of them. Given a string, a subsequence of the string can be obtained from the string by deleting none or some symbols [ 2 ] (not necessarily consecutive ones). To extract non-consecutive subsequences, Iliopoulos [ 1 ] proposes a variant to find the LCS, called Fixed Gap Longest Common Subsequence (FGLCS) problem, where a value of k is the fixed gap constraint and the distance between two consecutive matches is required to be limited to at most k+1. Figure 1 shows an example of LCS and FGLCS searching. The proposed method is based on FGLCS search and is divided into three phases. The system is proposed for transcriptions of incomplete or non-existent words. 1.  Delete non-alphabetic characters in transcript file. 2.  Delete line breaks on every segment to get one line segment. 3.  Split line by every char. At first step, each query is divided by a space, and then the FGLCS is searched in the actual segment for every word in the query. •   q = chars in query Every FGLCS is revised to have the same order of words that in the query, in such case, the confidence score is calculated using equation (1). The system considers that a result is relevant if confidence is more than 0.5. •   s = chars in the longest sequence •   c = confidence c = #$ #$% #     (1) We prove confidence threshold with values 0.9, 0.8, 0.7, 0.6 and 0.5. The best confidence threshold was 0.5. 3.4  

Submitted Runs

In this section, the nine free text search runs submitted by UAEMex are presented. Considering bad transcribed words, we change gap value to retrieve more words, however retrieval performance decrease.

Run1: FGLCS search with gap = 0.

Run2: FGLCS search with gap = 1.

Run3: FGLCS search with gap = 2.

Run4: FGLCS search with gap = 3.

Run5: Union of Run1 + Run2.

Run6: Union of Run1 + Run2 + Run3.

Run7: Union of Run1 + Run3.

Run8: Union of Run1 + Run2 + Run3 + Run4. 3.5  

Results

In this section, the results of submitted runs by UAEMex are presented. The results with ‘-’ could not be analyzed. Only the measures based on segments are included, and the ones for bounding boxes were omitted. The presented results are extracted only using the n-best No.20 of the n-best providers by the organizers. The results of the runs in development the following set of four metrics: Global Average Precision (Segm_gAP), Mean Average Precision (Segm_mAP), Global Normalized Discounted Cumulative Gain (Segm_gNDCG) and Mean Normalized Discounted Cumulative Gain (Segm_mNDCG) have been used to evaluate the accuracy of submissions (see Table 1 and Table2). This paper presents results in free text search using LCS. We describe the joint participation of the UAEMex at ImageCLEF 2016 Handwritten Scanned Document Retrieval Task. The proposed method works with words of dictionary and nonexistent words. There are big differences between the results of development set (Table 1) and test set (Table 2).

We assume we got bad results because we only use one n-best file provided by the organizers.

References

1.   C. S. Iliopoulos and M. S. Rahman , “ Algorithms for computing variants of the longest common subsequence problem,” Theoretical Computer Science , vol. 395 , pp. 255 - 267 , ( 2008 )

2.   H. Lin , M. Lu and J. Fang , "An optimal algorithm for the longest common subsequence problem," Parallel and Distributed Processing , 1991 . Proceedings of the Third IEEE Symposium on , Dallas, TX, pp. 630 - 639 ( 1991 ). doi: 10 .1109/SPDP. 1991 . 21820 .

3.   Villegas, M. , Müller , H. , Seco de Herrera, A. , Schaer , R. , Bromuri , S. , Gilbert , A. , Piras , L. , Wang , J. , Yan , F. , Ramisa , A. , Dellandrea , E. , Gaizauskas , R. , Mikolajczyk , K. , Puigcerver , J. , Toselli , A.H. , Sánchez , J.A. , Vidal , E.: General Overview of ImageCLEF at the CLEF 2016 Labs . Lecture Notes in Computer Science. Springer International Publishing ( 2016 )

4.   Villegas, M. , Puigcerver , J. , Toselli , A.H. , Sánchez , J.A. , Vidal , E.: Overview of the ImageCLEF 2016 Handwritten Scanned Document Retrieval Task . In: CLEF2016 Working Notes. CEUR Workshop Proceedings , CEUR-WS.org, Évora, Portugal (September 5-8 2016 ).