Method for generating a graph lattice from a corpus of one or more data graphs

Abstract

A document recognition system and method, where images are represented as a collection of primitive features whose spatial relations are represented as a graph. Useful subsets of all the possible subgraphs representing different portions of images are represented over a corpus of many images. The data structure is a lattice of subgraphs, and algorithms are provided means to build and use the graph lattice efficiently and effectively.

Description

BACKGROUND[0001]The present exemplary embodiments relate generally to computer vision and more specifically document recognition which is an application for computer vision. They find particular application in conjunction with computer vision applications, such as clustering, classification, retrieval, and repeated structure finding, and will be described with particular reference thereto. However, it is to be appreciated that the present exemplary embodiments are also amenable to other like applications.[0002]Recent years have seen a surge in bag-of-words approaches to image categorization. Under such approaches, objects and scenes are modeled as large vectors of relatively simple feature measurements. An issue is the information captured by a feature. Features have traditionally been purely appearance-based features, which measure local shape and texture properties. However, a recent trend has aimed at extracting information in spatial relationships among features measurements sam...

AI Technical Summary

Benefits of technology

[0007]A document recognition system and method, where images are represented as a collection of primitive features whose spatial relations are represented as a graph. Useful subsets of all the possible subgraphs representing different portions of images are represented over a corpus of many images. The data structure is a lattice of subgraphs, and algorithms provided to build and use the graph lattice efficiently and effectively.

Problems solved by technology

An issue is the information captured by a feature.

Subgraph matching poses certain difficulties.

First, it is known to be exponentially expensive.

Nonetheless, subgraph matching has been limited to relatively small subgraphs due to a second difficulty.

This is that noise and variability cause observed graphs to deviate from ideal models.

This demands the use of inexact graph matching techniques, which drastically increases matching cost and largely removes the advantages of attributed graph matching because possible matches of differently-labeled nodes must now be explored.

Similar to image categorization, the difficulties noted with subgraph matching also pose problems for image retrieval and detection of repeated structure.

Namely, image noise and variability make it difficult to quickly and efficiently perform the matching necessary for carrying out said tasks.

Images