Hierarchical optimization method and system for pattern recognition and edge detection

• US 20060002609A1
• Filed: 06/23/2005
• Published: 01/05/2006
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Stefano Casadei
• Original Assignee: Stefano Casadei
• Inventors: Casadei, Stefano
• Granted Patent: US 7,738,705 B2
• Time in Patent Office: Days
• US Class Current: 382/226
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

A method and a system for pattern recognition utilizes an ensemble of reference patterns to represent the possible instances of the models to be recognized; constructs a hierarchy of estimators to simplify and enhance the recognition of the models of interest; approximates complex reference patterns with linear compositions of simpler patterns; fragments complex patterns into local patterns so that interference between the local patterns is sufficiently small for linearization methods to be applicable; constructs estimators during an offline stage to offload calculations from the online signal processing stage; designs model estimators based on optimization principles to enhance performance and to provide performance metrics for the the estimated model instances; generates a hierarchy of reference descriptors during the offline stage, which are used for the design and construction of the model estimators. Specific examples are provided for the recognition of image features such as edges and junctions.

Claims

1. A method to recognize instances of a model in a signal, the method comprising:

providing an ensemble of reference patterns representative of the possible instances of said model;

providing at least one generator of auxiliary descriptors for the recognition of said model;

constructing an estimator for said model able to utilize said auxiliary descriptors;

obtaining a clique of online descriptors relating to said signal;

obtaining an executable generator of descriptors able to utilize said clique of online descriptors;

generating a new descriptor with said executable generator and said clique of online descriptors;

incorporating said new descriptor into a cache of online descriptors;

repeating the last four steps until said executable generator is an estimator for said model and said new descriptor specifies an estimated pattern representative of a recognized instance of said model, or until it is established that no instances of said model are to be found in said signal.

2. The method of claim 1, further comprising the steps of:

simulating, during an offline stage, said generator of auxiliary descriptors on said ensemble of reference patterns, to yield an ensemble of predicted descriptors;

utilizing said ensemble of predicted descriptors as reference descriptors, whereby at least one of said reference descriptors is compared with another descriptor.

3. The method of the previous claim, wherein said generator of auxiliary descriptors is an auxiliary estimator that generates estimated instances of an auxiliary model.

4. The method of the previous claim, wherein said auxiliary model is a local model obtained through a fragmentation procedure, wherein said auxiliary estimator is a local estimator for said local model, and wherein said fragmentation procedure comprises the steps of:

fragmenting the domain of said model into at least one subdomain; and

approximating, in said subdomain, said reference patterns with an ensemble of local patterns.

5. The method of the previous claim, further comprising the steps of:

comparing said reference patterns with said local patterns, to yield interference signals;

performing said fragmentation procedure so that said interference signals are small;

simulating said local estimator on said local patterns, to yield local descriptors;

comparing said reference descriptors with said local descriptors, to yield interference shifts.

6. The method of the previous claim, further comprising:

representing said interference signals as sums over the fragments from said fragmentation procedure;

linearizing said local estimators;

representing said interference shifts as sums over the fragments from said fragmentation procedure, to yield a low valency representation of said interference shifts.

7. The method of the previous claim, wherein said signal is an image, said model is for an edge-junction feature and said reference patterns are sums of wedge patterns.

8. The method of claims 2, further comprising the steps of

creating a node in a dependency graph to represent said estimator;

linking said node to another node representing said generator of auxiliary descriptors;

utilizing said dependency graph to obtain said executable generator.

9. The method of claim 2, wherein said estimator is based on an optimization criterion that minimizes discrepancies between descriptors.

10. The method of claim 4 further comprising the step of inverting a reference map, and wherein said estimator comprises a lookup table stored in a memory.

11. The method of the previous claim, wherein said signal is an image and said model is for a step edge feature.