Hierarchical method and system for pattern recognition and edge detection

• US 7,738,705 B2
• Filed: 06/23/2005
• Issued: 06/15/2010
• Est. Priority Date: 06/30/2004
• Status: Expired due to Fees

• Current Assignee: Stefano Casadei
• Original Assignee: Stefano Casadei
• Inventors: Casadei, Stefano
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US11/167,042
• Publication Number:
  US 20060002609A1
• Time in Patent Office: 1,818 Days
• Field of Search: 382/187, 382/190, 382/209, 382/219, 382/278
• US Class Current: 382/181
• 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 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 model instances in an input signal, the method comprising the steps of:

storing in a long-term memory a hierarchical collection of models, wherein;

the instances of each model are represented by an ensemble of patterns;

a non primitive pattern, defined on a domain and representative of an instance of a non-primitive model from said hierarchical collection has a fragmentation comprising a clique of local patterns; and

wherein

each local pattern, defined on a sub-domain of said domain, is representative of a local model from said hierarchical collection and provides an approximate representation of said non-primitive pattern within said sub-domain;

generating, by a processing means, a plurality of descriptors wherein each of said descriptors specifies an estimated pattern representative of an instance of a model detected in said input signal;

storing said descriptors in a short-term memory;

extracting from said short-term memory, by said processing means, a clique of descriptors which specifies a clique of estimated patterns;

selecting a model to be recognized from said hierarchical collection; and

generating, by said processing means, and by using said clique of descriptors as auxiliary descriptors, a new descriptor that specifies a new pattern, wherein said new pattern has a fragmentation given by said clique of estimated patterns and is representative of an instance of said model to be recognized.

2. The method of claim 1, wherein:

each pattern is represented by a multidimensional parameter value;

said fragmentation of said non-primitive pattern is obtained according a fragmentation rule for said non-primitive model which specifies a decomposition of the domain of said non-primitive pattern into a fixed clique of local domains and assigns a local model from said hierarchical collection to each one of said local domains;

said fragmentation rule specifies a validity region such that an interference signal, given by the difference between said non-primitive pattern and said local pattern in said sub-domain, is sufficiently small whenever the multidimensional parameter value representing said non-primitive pattern belongs to said validity region;

a sufficient number of fragmentation rules is provided for said non-primitive model so that any pattern of said non-primitive model is represented by a multidimensional parameter value belonging to the validity region of at least one fragmentation rule.

3. The method of claim 1, wherein said non-primitive pattern is a weighted sum of component patterns representative of instances of component models from said hierarchical collection, and wherein any one of said component patterns has a small interference signal inside the domain of any other one of said component patterns.

4. The method of claim 1, further comprising the step of adding said new descriptor to said short-term memory if a discrepancy measure associated to said new descriptor is sufficiently low.

5. The method of claim 1, further comprising the step of removing from said short-term memory any subsumed descriptor belonging to said clique of descriptors if a discrepancy measure of said new descriptor is sufficiently low relative to a discrepancy measure of said subsumed descriptor.

6. The method of claim 1, further comprising the step of:

searching said short-term memory for a pair of descriptors consisting of a subsumed descriptor and a subsuming descriptor;

removing said subsumed descriptor if a discrepancy-plus-complexity measure of said subsuming descriptor is sufficiently low relative to a discrepancy-plus-complexity measure of said subsumed descriptor.

7. The method of claim 1, wherein said model to be recognized is selected before said extracting step and said extracting step comprises the step of searching said short-term memory for descriptors which can be used as auxiliary descriptors for the estimation of said model to be recognized.

8. The method of claim 1, wherein said model to be recognized is selected after said extracting step and said model to be recognized is selected by searching said hierarchical collection for models which can be estimated by using said clique of descriptors as auxiliary descriptors.

9. The method of claim 1, further comprising the steps of selecting, by said processing means, a domain to examine from a pre-defined collection of domains and wherein:

the domain of said new descriptor is substantially equal to said domain to examine;

the union of the domains of said clique of descriptors contains a substantial portion of said domain to examine; and

said model to be recognized is selected among the models of said hierarchical collection which can be estimated by using said clique of descriptors as auxiliary descriptors.

10. The method of claim 9, wherein two or more descriptors are generated whose domains are substantially equal to said domain to examine, and wherein said two or more descriptors specify instances of two or more distinct models from said hierarchical collection.

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

storing a hierarchical collection of descriptor generators in said long-term memory;

executing, by said processing means, one of said descriptor generators on a plurality of said patterns, to yield a plurality of predicted descriptors; and

comparing one of said predicted descriptors with a descriptor stored in said short-term memory and representative of a model instance detected in said input signal.

12. The method of claim 11, wherein some of said predicted descriptors are generated during an off-line stage.

13. The method of claim 11, wherein some of said predicted descriptors are generated by said step of generating a new descriptor, to produce feedback signals utilized by an optimization algorithm that refines a multidimensional parameter value associated to said new descriptor.

14. The method of claim 1, wherein:

said input signal is an input image, the domain of said patterns are two-dimensional image regions;

said hierarchical collection comprises a plurality of polynomial models and a centered step-edge model;

said non-primitive model is said centered step-edge model;

said clique of local patterns includes a cubic edge pattern;

said model to be recognized is said centered step-edge model;

said clique of descriptors includes a cubic-edge descriptor calculated from said input image; and

said new pattern is a step-edge pattern estimated by utilizing said cubic-edge descriptor as auxiliary descriptor.

15. The method claim 14, wherein:

said hierarchical collection further comprises a junction model and a non-centered step-edge edge model;

a first junction pattern has a fragmentation comprising a local centered step-edge pattern;

a second junction pattern has a fragmentation comprising a local non-centered step-edge pattern.

16. The method of claim 15, wherein an interference signal between said first junction pattern and said local centered step-edge pattern is expressed as a sum of wedge patterns.

17. The method of claim 1, wherein said input signal is an input image, said hierarchical collection comprises a plurality of polynomial models, a centered step-edge model and a non-centered step-edge model, and wherein said extracting a clique of descriptors, said selecting a model to be recognized and said generating a new descriptor are performed during a plurality of iterations, wherein:

in a first iteration, said clique of descriptors comprises a polynomial edge descriptor and said model to be recognized is said centered step-edge model;

in a second iteration, said clique of descriptors comprises a second polynomial edge descriptor and a constant-gradient descriptor whose domain is on one side of the domain of said second polynomial edge descriptor, and said model to be recognized is said non-centered step-edge model;

in a third iteration, said clique of descriptors comprises a third polynomial edge descriptor, a second and third constant-gradient descriptors whose domains are on opposite sides of said third polynomial edge descriptor, and said model to be recognized is said centered step-edge model.

18. An apparatus to recognize model instances in an input signal, comprising:

means for storing a hierarchical collection of models and a plurality of descriptors, wherein;

the instances of each model are represented by an ensemble of patterns;

a non-primitive pattern, defined on a domain and representative of an instance of a non-primitive model from said hierarchical collection has a fragmentation comprising a clique of local patterns; and

wherein

each local pattern, defined on a sub-domain of said domain, is representative of a local model from said hierarchical collection and provides an approximate representation of said non-primitive pattern within said sub-domain;

and said apparatus further comprising processing means adapted to;

generate said plurality of descriptors, wherein each of said descriptors specifies an estimated pattern representative of an instance of a model detected in said input signal;

extract from said storing means a clique of descriptors which specifies a clique of estimated patterns;

select a model to be recognized from said hierarchical collection; and

generate, by using said clique of descriptors as auxiliary descriptors, a new descriptor that specifies a new pattern, wherein said new pattern has a fragmentation given by said clique of estimated patterns and is representative of an instance of said model to be recognized.

19. The apparatus of claim 18, wherein

said input signal is an input image, the domain of said patterns are two-dimensional image regions, said hierarchical collection comprises a plurality of polynomial models, a centered step-edge model, a non-centered step-edge model, and a junction model;

a first junction pattern has a fragmentation comprising a centered step-edge pattern,

a second junction pattern has a fragmentation comprising a non-centered step-edge pattern; and

wherein

an interference signal between said first junction pattern and said centered step-edge pattern is expressed as a sum of wedge patterns.

20. A computer readable medium for use in an apparatus to recognize model instances, the computer readable medium containing:

encoded data representing a hierarchical collection of models, wherein;

the instances of each model are represented by an ensemble of patterns;

a non primitive pattern, defined on a domain and representative of an instance of a non-primitive model from said hierarchical collection has a fragmentation comprising a clique of local patterns; and

wherein

each local pattern, defined on a sub-domain of said domain, is representative of a local model from said hierarchical collection and provides an approximate representation of said non-primitive pattern within said sub-domain;

the computer readable medium farther containing instructions to perform a plurality of steps comprising;

generating a plurality of descriptors wherein each of said descriptors specifies an estimated pattern representative of an instance of a model detected in said input signal;

storing said descriptors in a short-term memory;

extracting from said short-term memory a clique of descriptors which specifies a clique of estimated patterns;

selecting a model to be recognized from said hierarchical collection; and

generating, by using said clique of descriptors as auxiliary descriptors, a new descriptor that specifies a new pattern, wherein said new pattern has a fragmentation given by said clique of estimated patterns and is representative of an instance of said model to be recognized.