Word spotting use a query word image to nd any instances of that word among document images. The obtained list of words is ranked according to similarity to the query word. Ideally, any false positives should only occur in the end of that list. However, in reality they often occur higher up, which decreases the so called mean average precision. It is shown how creating new ranked lists by re-scoring using the top n occurrences in the original list, and then fusing the scores, can increase the mean average precision.
Transcription of large collections of handwritten material is a tedious and costly task. Nevertheless, images of documents can still be made searchable by a technique called keyword spotting, or simply word spotting [GSGN17, LRF+12]. Word spotting can be considered as a special case of image retrieval, where the goal is to nd all instances of the query word in the document image collection at question. When searching in several document images, using a query word in the form of an example image, there are often some false positives in the retrieved list. Therefore ranking is performed so that the words most similar to the query word will appear in the top and the most dissimilar, but still similar enough to be presumed to be correct, will appear in the bottom of the list.
In this paper, methods for improving the ranked list will be evaluated and discussed. The main idea is to take the top n occurrences in the ranked list and then rank it again against each one of them, thus creating n rankings, which then are fused to create a better overall ranking.
Generally, in both information retrieval and object-image retrieval the retrieved result is ranked according to its relevance. Similarly, the retrieved regions supposedly containing the searched word of all the pages are collected and ranked according to their similarity score. This procedure involves pairwise comparison, in which the query word image is compared to all retrieved word images using some scoring function (i.e. computing the distance Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). between feature vectors obtained from the word images) that will give a score, also known as con dence value, for each comparison, i.e. each word image.
Re-ranking usually refers to the procedure of ranking all over again using a more exact method for computing the score. However, in this work, only the situation where the same scoring function is used will be considered, even though there is nothing that prohibits the use of di erent scoring functions. The use of machine learning techniques to train the ranking model is often referred to as "learning to rank" [LLZ09], which includes methods like LambdaMART and LambdaRank, which is based on RankNet [Bur10]. Relevance feedback [Har92] could also be used with the proposed method by letting the user choose the relevant words for ranking and fusion.
Normally, some score normalisation procedure is necessary in order to make scores, which are obtained using di erent scoring functions, e.g. from di erent information retrieval systems, comparable to each other [WCB06]. This is not necessary here, since the proposed algorithm use the same scoring function.
In information retrieval, data fusion [Wu12] is a technique for combining the ranked lists from several retrieval methods [SF95]. It has been noted that the fusion together of document rankings can yield a higher level of relevance than either of the individual methods [Sme98, MS05]. It has also been noted that in general it is better to fuse scores rather than ranks [BP09]. One common technique for score based fusion in information retrieval is CombSUM [BKFS95], where the scores from several lists are simply added together to obtain a new scores. By multiplying this score by the number of lists, i.e. frequency, where the document occurs, combMNZ is obtained [BC17, WH18]. Herein, the average of scores for each instance of the word will be used, since the new score will be used for purging those that fall under a certain threshold
The relevance of documents in an information retrieval system can vary quite a lot and can therefore be considered being fuzzy, while the word found in word spotting is either the correct word or not, and can therefore being considered binary. Of course, there are some exceptions like di erences in spelling or the same word with di erent semantics etc. Nevertheless, it is possible to utilise this fact by taking the top n occurrences in the rst ranking and rank the whole list against each one of them creating n rankings, which then are fused to create a better ranking. 2.1
Rusin~ol et al. [RnL14] propose three di erent techniques for data fusion techniques, where variability in writing style is handled by preforming multiple queries and then combining the results. Louloudis et al. [LKG12] evaluate three techniques based on the rank position. A systematic evaluation of di erent fusion techniques was presented by Pen~a et al. [PnSMVG10]. Wei et al. [WGS15] discuss how query expansion (QE) [AZ12] that produce one ranked list per expanded search, can be subsequently merged to obtain the nal ranked list. Later on, this method will be compared to the proposed method. 3
A learning and segmentation free word spotting engine [HF16, HCV18] was used that search for an example image, referred to as a query word, in one or several document images [HCVA19]. Tentative words that fall below a certain threshold will be discarded as garbage (i.e. a so called negative). It is obviously important to set this threshold so that the negatives are mostly true negatives and the positives are mostly true positives. However, due to the nature of the problem there will often be some false positives as well as false negatives.
Moreover, the matching of the query word and the found tentative words cannot be too precise as some words would be missed, i.e. the recall will be lower. At the same time it cannot be too relaxed so that many false positives will be found, i.e. the precision will be low (these terms are explained under section 4). In the tests presented a rather tight threshold was used to nd mostly true positives, and then perform QE on these, where new searches are performed, using each found word as a query on the same page as the word is found, as well as on the previous and following page. This will ensure that the QE will have enough instances of the word to query on, but not too many as it will increase search time and also increase the risk of nding false positives. Hence, even if this approach uses the same underlying architecture as a previously published approach [VHF19], it is still di erent as that one only used words found on the same page. Nevertheless, QE will increase the recall substantially while still keeping the precision high.
The ranked list will be ranked depending on the similarity to the original query word only. Therefore, the score value can be lower for certain words in the end of the ranked list, than the threshold used in each individual search. This fact can be utilised to purge the end of the list for all words having a score value below or some other threshold depending on the quality of the found words.
The idea behind QE is that the found words contain some variation that will help nding even more words that the single query word could not nd, i.e. the score will be quite di erent depending on the variation. Similarly, the presented consensus ranking utilise this fact and takes the top n words from the resulting list from the QE search and score each of them to the ranked list to create n new ranked lists. Hence, each list is a bit di erent and by fusing them a better ranked list is obtained.
The above approach will therefore be di erent from the one of Wei et al. [WGS15] where the the QE produce several lists, i.e. one ranked list per search. These lists are ranked on the similarity of each query word, that are subsequently merged to obtain the nal ranked list. Each QE will generally not nd exactly the same words and therefore each ranked list will be a bit di erent. When merged, the list will be as complete as possible, but the fusion will depend on how many expanded query searches nds each word. In general, the more queries that end up nding one word the better, since the nal score will be computed from more lists. However, by taking the top n words in the nal list resulting from QE and making n new lists by re-scoring, this problem will not occur. This approach will be referred to as consensus ranking (CR). Nonetheless, one possible drawback with it is that the QE list will be ordered depending on the similarity to the original query word. If this word is not for some reason very representative for the words in the document, then the approach by Wei et al. might be better. Therefore, it will be investigated herein the e ect of utilising their approach to merge the lists resulting from QE and then use the top n words in that list to perform the proposed CR. This approach is later referred to as ML-CR. 4
First as a proof of concept for the proposed algorithm, the ranking of digits in the MNIST data set [LCB10] is performed, which showed good performance even when the top n digit images contains some false positives (see section 5).
Then tests were performed both on the Esposalles data set [RFS+13] and the Bentham data set from the Transcribe Bentham project [MTW11]. Four di erent words were chosen as query words and the initial search was performed on 10 pages for each data set. For each word 6 instances were chosen in order to capture some variance in the handwriting. By comparing all words in the ground truth with every other word, a confusion matrix was obtained containing scores (similarity). For both data sets, the 3 words having highest mean value in each column of the matrix, i.e. being as equal to the others as possible, were therefore considered being representative query words. The 3 words having lowest mean were also used to see how the algorithms involved cope with such situation when the query word is less representative, i.e. more di cult, as it might contain strokes from adjacent lines, being written di erently or having some kind of degradation. Examples of both variants are shown in Figure 1.
(a) The query images Barca (b) The query images "reber". (a) The word Barca has been found on one page in the Esposalles (b) The word aforesaid has been found on one page of the Bentham data set. data set. nds words in the (a) Esposalles data set, and (b) the 4.1
The word spotting algorithm can be evaluated by computing the Precision-Recall curve. Precision is the number of relevant (true positive) objects found divided by the number of all retrieved objects, and Recall is the number of relevant objects found divided by the number of all relevant objects in the set [Pow07]. They are computed as:
P recision = jretrieved \ relevantj
jretrievedj Recall = jretrieved \ relevantj jrelevantj (1) (2)
Many prefer using a single value for easily comparing di erent approaches, such as the mean Average Precision (mAP), which corresponds to the area below the Precision-Recall curve, which is computed using the following equation: mAP =
Pjretrievedj P @n n=1
r(n) jrelevantj where P @n is the precision at the n top-most returned results, and r(n) is a binary function indicating whether the n-th item in the returned ranked list is a relevant object (true positive). (3) 5
5.1
The results from both the proof of concept and applying QE and CR on the Esposalles and the Bentham data sets are reported in this section.
The proposed CR algorithm was used for ranking of digits in the MNIST data set [LCB10], as a proof of concept. Feature vectors were computed (as in [HLV19]) for 2000 images containing 200 images for each digit. The set was divided into two disjoint sets with 100 number of occurrences of each digit in each set. The idea is to rank the images in the second set according to how similar they are to each digit in the rst set. This was done by computing the cosine distance (i.e a score value) and therefore the list contains the nearest neighbours (NN) in a descending scale. The results are shown in Table 1. Here it was chosen to use only a maximum of 12 of the nearest neighbours having a distance equal to or above 0:8. However, it should be noted that as for MNIST this did not prohibit from performing CR using some false positives among the top n images. Actually, it was quite common, with an average of 17:14% for the reported tests, which the low mAP also con rms. Despite this, the CR still increases the mAP with an average of 12:30%, which proves the e ciency and the stability of the proposed algorithm. a bit higher than the threshold = 0:7 for regarding a word as a correct word, in order to be more on the safe side when re-scoring, Both conditions are assuring that the words that are being used for re-scoring are true positives to a high probability. Note, that if the QE do a bad job in the rst place this will not hold. However, as shown in the proof of concept, the CR can usually still improve the ranking, even if some false positives are found among the top n candidates for re-scoring.
The plot in 3 shows the con dence score (or similarity value), where the ranked lists are from QE (magenta), CR (blue), ML (red), CR-ML (yellow). The y axis shows the score and the x axis the position in the list. One can note that the query word used was taken from the same page images since the highest score is 1:0 (which means it nds itself) and then decaying for QE. One can also note that the score for ML is generally higher at the end of the ranked list since it by de nition cannot go below the threshold used both for WS and QE. Nevertheless, the score for CR can be lower since the re-scoring between words can result in low scores even if both are true positives, as they might be rather dissimilar.
(a) "reber" (b) "Barca"
One advantage with the CR and CR-ML is therefore that it is possible to purge the list by removing those under a certain threshold. This will make it easier for a user to investigate the result if obvious false positives are removed. Therefore, the user of a search tool or a transcription tool using word spotting [HV18], only needs to concentrate on a few items (true positives) in the end of the purged list that might be miss ranked and end up scattered among the false positives.
A comparison is shown in Figure 4 and 5 of the output from the word spotting system (WS) 4a and the result of applying fusion through consensus ranking (CR) 4b. The true positives are depicted in green and the false positives in red. Once again the background removal technique has been used. One can note how the miss ranked words are all pushed to the bottom of the list. The ranked list obtained by merging lists (ML) 4c and performing a CR on ML 4c is also shown. One can note how ML generally performs worse than CR. This is due to the fact that was set rather tight in order to avoid false positives. This causes the algorithm to nd fewer correct words in both the WS and in each single search in the QE. However, in general this method leads to both high recall and precision. By lowering the threshold , ML will perform better, with the drawback of having much more false positives in the nals lists.
One can note how CR improves the position of miss ranked words quite a lot, even if the mAP improvement is modest. The results are not always perfect, since the same score function is used both for QE and CR, which cannot be too precise in order to still capture the variation in handwriting. (c) List ranked after merging. list (c) List ranked after merging.
Table 2 show the result (in mAP) of running the di erent algorithms on several di erent words, as explained earlier for the Esposalles data set. Each row shows the average of mAP from using three di erent query words. One can note how QE improves over WS, but also how CR pushes up the mAP. The increase might seem small but in reality the e ect is that the ranked list will contain a longer sequence of true positives and the false positives will be aggregated in the end of the list, instead of being scattered in the middle of the list.
Table 3 shows the e ect of choosing words that give worse results as explained earlier. One can note how the WS performs worse, but that QE still deals with that problem in an elegant way. Generally, CR pushes the mAP up higher. Furthermore, table 4 and Table 5 shows some results for the Bentham data set. The proof of concept showed that the idea generally works very well (the mAP generally improved by 12:30%) even for heavily contaminated sets, such as in the case of the experiment with MNIST where only 10% in the ranked list are true positives. Furthermore, the experiment showed that the proposed consensus ranking still works rather well even when some of the items used for the CR are false positives (in this case, on average 17:14%). Hence, a few false positives does not, in general, make the algorithm fail.
The increases presented in the tables for the Esposalles and the Bentham data sets in section 5, using CR after QE might seem rather low. However, they are important as they reorder the rank so that it will be easier for a human to quickly distinguish true positives fro false positives by a visual inspection, as shown in the presented images in section 5. This will be a useful feature both for semi-automatic transcription [HCV18] as well as for searching non transcribed document images [HCVA19].
One advantage with CR is that it helps to purge what must be false positives to a high degree of certainty. By inspecting Figure 3 and the ranked list in Figure 4 and Figure 5 one can see how CR (the blue curve) suddenly drops rapidly and in the end of that drop there are no true positives anymore. Just a few false positives are found in the drop or above. This drop can be quite obvious as in the case for "reber" or more subtle as for "Barca". Therefore, it is probably better to set a xed threshold for purging than trying to locate the "drop". It seems like the threshold generally could be set equal to or a bit below. Being used in a transcription or a search tool, the threshold could be a parameter set using a slider by the user.
CR will not substantially increase the mAP when there are very few true positives. This is generally not a big problem, since the retrieved ranked list will consequently be very short anyway. For instance "intended" has only 10 occurrences in the Bentham data set that was used herein (the other words have between 12 and 25 occurrences.) and the mAP do not improve as seen in Table 4. In fact, it is already good and could not be improved further since QE found 9 out of 10 occurrences and ranked them on top.
Overall, the time it takes to perform QE is many times longer the time it takes to perform CR, due to the word spotting search per page, and the QE that performs such search on several words per page. Nevertheless, the time it takes to perform CR is not negligible, especially not for when the nal list produced by QE is long, i.e. several hundred words. QE always ends by performing one ranking using the original query word to produce a nal ranked list. CR then performs up to n such rankings and thus adds n times more execution. The fusion itself is almost negligible since it is just averaging scores, compared to the work it takes to match images to compute the scores in the rst place.
One disappointment is that the ML-CR generally did not perform better than CR for the di cult word images. Of course the tests performed here are quite limited and running on larger data sets and also using di erent number for the top n words might turn out to give di erent results. Nevertheless, ML generally performs much worse than CR because of the tight set thresholds in QE that will lower the number of false positives and hence decrease the visual load for the user. 7
The ranking of words found by word spotting is important for tasks like fast transcription or simple searches. The user do not want to be bothered with the many false positives that often are retrieved. Therefore, ranking is very important, pushing the false positives to the end of the list. Moreover, purging the list automatically from the obvious false positives also helps the user. The proposed Consensus Ranking helps the user with both of these aspects. The idea is simply to take the top n words in the list ranked by matching to the query word, and re-score the list using each of these words to re-score again, giving n new lists that can be fused together to obtain a better ranked list. By averaging the scores, a majority of the false positives will generally obtain lower scores than the threshold used for the word spotting itself, and can therefore be purged. [AZ12]
Relja Arandjelovic and Andrew Zisserman. Multiple queries for large scale speci c object retrieval. In British Machine Vision Conference, 2012.
Rodger Benham and J. Shane Culpepper. Risk-reward trade-o s in rank fusion. In Proceedings of the 22Nd Australasian Document Computing Symposium, ADCS 2017, pages 1:1{1:8, New York, NY, USA, 2017. ACM. [BP09]
N. J. Belkin, P. Kantor, E. A. Fox, and J. A. Shaw. Combining the evidence of multiple query representations for information retrieval. Inf. Process. Manage., 31(3):431{448, May 1995.