A graph lattice approach to maintaining and learning dense collections of subgraphs as image features

Abstract

Effective object and scene classification and indexing depend on extraction of informative image features. This paper shows how large families of complex image features in the form of subgraphs can be built out of simpler ones through construction of a graph lattice–a hierarchy of related subgraphs linked in a lattice. In lieu of error-tolerant graph matching, the approach achieves robustness through exact graph matching on many overlapping and redundant subgraphs. Efficiency is gained by exploitation of the graph lattice data structure. Additionally, the graph lattice enables methods for adaptively growing a feature space of subgraphs tailored to observed data. We develop the approach in the domain of rectilinear line-art, specifically for the practical problem of document forms recognition. We demonstrate two approaches to using the subgraph features. Using a bag-of-words feature vector we achieve essentially single-instance learning on a benchmark forms database, following an unsupervised clustering stage. Further performance gains are achieved on a more difficult data set using a feature voting method and feature selection procedure.