TY - JOUR

T1 - Large-scale graph indexing using binary embeddings of node contexts for information spotting in document image databases

AU - Riba, Pau

AU - Lladós, Josep

AU - Fornés, Alicia

AU - Dutta, Anjan

PY - 2017/2/1

Y1 - 2017/2/1

N2 - © 2016 Elsevier B.V. Graph-based representations are experiencing a growing usage in visual recognition and retrieval due to their representational power in front of classical appearance-based representations. However, retrieving a query graph from a large dataset of graphs implies a high computational complexity. The most important property for a large-scale retrieval is the search time complexity to be sub-linear in the number of database examples. With this aim, in this paper we propose a graph indexation formalism applied to visual retrieval. A binary embedding is defined as hashing keys for graph nodes. Given a database of labeled graphs, graph nodes are complemented with vectors of attributes representing their local context. Then, each attribute vector is converted to a binary code applying a binary-valued hash function. Therefore, graph retrieval is formulated in terms of finding target graphs in the database whose nodes have a small Hamming distance from the query nodes, easily computed with bitwise logical operators. As an application example, we validate the performance of the proposed methods in different real scenarios such as handwritten word spotting in images of historical documents or symbol spotting in architectural floor plans.

AB - © 2016 Elsevier B.V. Graph-based representations are experiencing a growing usage in visual recognition and retrieval due to their representational power in front of classical appearance-based representations. However, retrieving a query graph from a large dataset of graphs implies a high computational complexity. The most important property for a large-scale retrieval is the search time complexity to be sub-linear in the number of database examples. With this aim, in this paper we propose a graph indexation formalism applied to visual retrieval. A binary embedding is defined as hashing keys for graph nodes. Given a database of labeled graphs, graph nodes are complemented with vectors of attributes representing their local context. Then, each attribute vector is converted to a binary code applying a binary-valued hash function. Therefore, graph retrieval is formulated in terms of finding target graphs in the database whose nodes have a small Hamming distance from the query nodes, easily computed with bitwise logical operators. As an application example, we validate the performance of the proposed methods in different real scenarios such as handwritten word spotting in images of historical documents or symbol spotting in architectural floor plans.

KW - Graph based representation

KW - Graph indexation

KW - Information spotting in Document recognition

U2 - 10.1016/j.patrec.2016.06.015

DO - 10.1016/j.patrec.2016.06.015

M3 - Article

VL - 87

SP - 203

EP - 211

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

SN - 0167-8655

ER -