A graph lattice approach to maintaining and learning dense collections of subgraphs as image features
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.
- download PDF (881K)
Saund, E. A graph lattice approach to maintaining and learning dense collections of subgraphs as image features. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2013 October; 35 (10): 2323-2339.
Copyright © IEEE, 2013. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.