Focused structural document image retrieval in digital mailroom applications

Abstract

Aquesta tesi doctoral presenta un marc de treball genèric per a la cerca de documents digitals partint d'un document de mostra de referencia, on el criteri de similitud pot ser tant a nivell de pàgina com a nivell de subparts d'interès. Combinem la tècnica d'indexació estructural amb correspondències entre parells de regions locals d'interès, on aquestes contenen informació tant estructural com visual, i detallem la combinació adient usada d'aquests dos tipus d'informació per ser usada com a únic criteri de similitud a l'hora de fer la cerca. Donat que l'estructura d'un document està lligada a les distàncies entre els seus continguts, d'entrada presentem un detector eficient que anomenem Distance Transform based Maximally Stable Extremal Regions (DTMSER). El detector proposat és capàs d'extreure eficientment l'estructura del document en forma de dendrograma (arbre jeràrquic) de regions d'interès a diferents escales, les quals guarden una gran similitud amb els caracters, paraules i paràgrafs. Els experiments realitzats proven que l'algorisme DTMSER supera els mètodes de referència, amb l'avantatge de requerir menys regions d'interès. A continuació proposem un mètode basat en parells de descriptors Bag‐of‐Words (BoW) que permet representar el dendrograma descrit anteriorment i resultat de l'algorisme DTMSER. El nostre mètode consisteix en representar cada document en forma de llista de parelles de regions d'interès, on cada parella representa una aresta del dendograma i defineix una relació d'inclusió entre ambdues regions. L'histograma de característiques és generat a partir de les parelles de regions d'interès, de manera que el mètode proposat reflecteix la inclusió de regions. Els experiments realitzats demostren que el nostre mètode supera àmpliament altres variants exteses de BoW com poden ver les convencionals o les espacio‐piramidals. Per tal d'englobar diferents situacions on es pot requerir una la cerca de documents digitals, proposem usar directament parelles de regions d'interès, les quals inclouen informació tant estructural com visual. Amb aquest objectiu introduim en aquest camp tècniques d'indexació estructural per millorar el temps de càlcul de les similituds de parelles de regions. Apliquem la nostra proposta al cas de cerques de pàgines senceres, on té més pes la similitud estructural. Els experiments corresponents mostren que la nostra proposta supera la majoria de mètodes BoW de referència. La nostra proposta presenta un clar avantantge: podem fer cerques de subparts de documents. Apliquem el nostre mètode en la cerca de subparts en dos casos: prioritzant la similitud estructural i mantenint estructura y aparença similars . Els resultats obtinguts en els experiments són excel∙lents en tots dos casos. Donat que el nostre mètode té el valor afegit de ser el primer marc de treball capàs de realizar cerques de subparts, podem afirmar que és mereixedor de formar part de l’estat de l’art en el camp de cerques. També proposem un mètode de verificació de línies per comprovar la consistència espacial dels parells assignats de regions d'interès. Per reduir la càrreca computacional de la nostra proposta definim una simplificació pràctica en dos passos. Primer obtenim candidats a regions d'interès per posteriorment usar‐les per dividir les correspondències entre regions en varis subgrups, i finalment realitzar la verificació de línies en cada grup, i alhora es puleixen les regions d'interès. Els experiments demostren que, en comparació amb el mètode estandar (basat en RANSAC), la nostra proposta de verificació de línies és més exhaustiva i va acompanyada d’una lleugera disminució de precisió, la qual cosa es preferible en determinats casos de cerca.

In this work, we develop a generic framework that is able to handle the document retrieval problem in various scenarios such as searching for full page matches or retrieving the counterparts for specific document areas, focusing on their structural similarity or letting their visual resemblance to play a dominant role. Based on the spatial indexing technique, we propose to search for matches of local key‐region pairs carrying both structural and visual information from the collection while a scheme allowing to adjust the relative contribution of structural and visual similarity is presented. Based on the fact that the structure of documents is tightly linked with the distance among their elements, we firstly introduce an efficient detector named Distance Transform based Maximally Stable Extremal Regions (DTMSER). We illustrate that this detector is able to efficiently extract the structure of a document image as a dendrogram (hierarchical tree) of multi‐scale key‐regions that roughly correspond to letters, words and paragraphs. We demonstrate that, without benefiting from the structure information, the key‐regions extracted by the DTMSER algorithm achieve better results comparing with state‐of‐the‐art methods while much less amount of key‐regions are employed. We subsequently propose a pair‐wise Bag of Words (BoW) framework to efficiently embed the explicit structure extracted by the DTMSER algorithm. We represent each document as a list of key‐region pairs that correspond to the edges in the dendrogram where inclusion relationship is encoded. By employing those structural key‐region pairs as the pooling elements for generating the histogram of features, the proposed method is able to encode the explicit inclusion relations into a BoW representation. The experimental results illustrate that the pairwise BoW, powered by the embedded structural information, achieves remarkable improvement over the conventional BoW and spatial pyramidal BoW methods. To handle various retrieval scenarios in one framework, we propose to directly query a series of key‐region pairs, carrying both structure and visual information, from the collection. We introduce the spatial indexing techniques to the document retrieval community to speed up the structural relationship computation for key‐region pairs. We firstly test the proposed framework in a full page retrieval scenario where structurally similar matches are expected. In this case, the pair‐wise querying method achieves notable improvement over the BoW and spatial pyramidal BoW frameworks. Furthermore, we illustrate that the proposed method is also able to handle focused retrieval situations where the queries are defined as a specific interesting partial areas of the images. We examine our method on two types of focused queries: structure‐focused and exact queries. The experimental results show that, the proposed generic framework obtains nearly perfect precision on both types of focused queries while it is the first framework able to tackle structure‐focused queries, setting a new state of the art in the field. Besides, we introduce a line verification method to check the spatial consistency among the matched key‐region pairs. We propose a computationally efficient version of line verification through a two step implementation. We first compute tentative localizations of the query and subsequently employ them to divide the matched key‐region pairs into several groups, then line verification is performed within each group while more precise bounding boxes are computed. We demonstrate that, comparing with the standard approach (based on RANSAC), the line verification proposed generally achieves much higher recall with slight loss on precision on specific queries.