System and method to facilitate pattern recognition by deformable matching

• US 6,785,419 B1
• Filed: 12/22/2000
• Issued: 08/31/2004
• Est. Priority Date: 12/22/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jojic, Nebojsa, Simard, Patrice
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/748,564
• Time in Patent Office: 1,348 Days
• Field of Search: 382/106, 382/190-197, 382/207, 382/209, 382/215-220, 382/276-280, 382/160, 382/224-225, 382/248-253
• US Class Current: 382/197
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method to facilitate pattern recognition or matching between patterns are disclosed that is substantially invariant to small transformations. A substantially smooth deformation field is applied to a derivative of a first pattern and a resulting deformation component is added to the first pattern to derive a first deformed pattern. An indication of similarity between the first pattern and a second pattern may be determined by minimizing the distance between the first deformed pattern and the second pattern with respect to deformation coefficients associated with each deformed pattern. The foregoing minimization provides a system (e.g., linear) that may be solved with standard methods.

Claims

1. A method to facilitate pattern recognition between a first pattern and a second pattern, comprising

applying to spatial derivative of the first pattern a substantially smooth deformation field having deformation coefficients to deform the first pattern and form a deformation component of the first pattern, the substantially smooth deformation field for the first pattern further comprises a displacement component for each dimension of a space associated with the first pattern, the displacement component having associated deformation coefficients;

aggregating the first pattern and the deformation component of the first pattern to define a first deformed pattern; and

determining a minimum distance between the first deformed pattern and the second pattern relative to the deformation coefficients for the first pattern.

2. The method of claim 1 further comprising the step of applying a deformation cost function to the deformation coefficients for the first pattern to favor smooth deformation in the step of determining a minimum distance.

3. The method of claim 2, wherein the deformation coefficients are computed by minimizing the cost function.

4. The method of claim 1 further comprising applying a pattern cost factor to at least the first pattern to selectively weight different aspects of the first pattern in the step of determining a minimum distance.

5. The method of claim 1 further comprising applying a deformation component cost factor to penalize large deformations in the step of determining a minimum distance.

6. A computer-readable medium having computer-executable instructions for performing the steps of claim 1.

7. A method to facilitate pattern recognition between a first pattern and a second pattern, comprising:

applying to the first pattern a substantially smooth deformation field having deformation coefficients to deform the first pattern and form a deformation component of the first pattern, the deformation field for the first pattern being parameterized by functional basis vectors and by the deformation coefficients for the first pattern,

aggregating the first pattern and the deformation component of the first pattern to define a first deformed pattern;

determining a minimum distance between the first deformed pattern and the second pattern relative to the deformation coefficients for the first pattern, and

applying a second smooth deformation field to the second pattern to form a second deformation component that is added to the second pattern to define a second deformed pattern, the second deformation field being parameterized by functional basis vectors and deformation coefficients associated with the second pattern, the minimum distance being determined as a function of the first deformed pattern and the second deformed pattern.

8. The method of claim 7, wherein the deformation fields for each of the first and second patterns include wavelet basis vectors and respective deformation coefficients.

9. The method of claim 8, wherein the respective deformation coefficients for the first and second patterns have substantially opposite values.

10. A method to facilitate pattern recognition between a first pattern and a second pattern, comprising:

applying to a spatial derivative of the first pattern a substantially smooth deformation field having deformation coefficients to deform the first pattern and form a first deformation component;

the substantially smooth deformation field for the first pattern further comprises a displacement component for each dimension of a space associated with the first pattern, and the displacement component has associated deformation coefficients,

adding the first deformation component and the first pattern to define a first deformed pattern;

determining the deformation coefficients for the first pattern that minimize a distance between the first deformed pattern and the second pattern; and

using the determined deformation coefficients to evaluate a distance between the first deformed pattern and the second pattern.

11. A method to facilitate pattern recognition between a first pattern and a second pattern, comprising:

applying to a spatial derivative of the first pattern a substantially smooth deformation field having deformation coefficients to deform the first pattern and form a first deformation component, the substantially smooth deformation field for the first pattern is parameterized by functional basis vectors and by the deformation coefficients for the first pattern;

adding the first deformation component and the first pattern to define a first deformed pattern;

determining the deformation coefficients for the first pattern that minimize a distance between the first deformed pattern and the second pattern; and

applying a second smooth deformation field to the second pattern to form a second deformation component that is added to the second pattern to define a second deformed pattern, the second deformation field being parameterized by functional basis vectors and deformation coefficients associated with the second pattern, the distance being determined between the first deformed pattern and the second deformed pattern relative the deformation coefficients for the first and second patterns.

12. The method of claim 11, wherein the deformation fields for each of the first and second patterns include wavelet basis vectors and respective deformation coefficients.

13. The method of claim 12, wherein the respective deformation coefficients for the first and second patterns have substantially opposite values.

14. The method of claim 12, further comprising determining the respective deformation coefficient by minimizing cost associated with deforming the first and second patterns.

15. A method to facilitate pattern recognition between a fit pattern and a second pattern, comprising

applying to the first pattern a substantially smooth deformation field having deformation coefficients to deform the first pattern and form a first deformation component;

adding the first deformation component and the first pattern to define a first deformed pattern;

determining the deformation coefficients for the first pattern that minimize a distance between the first deformed pattern and the second pattern;

using the determined deformation coefficients to evaluate a distance between the first deformed pattern and the second pattern; and

applying a deformation cost function to the deformation coefficients for the first pattern to favor smooth deformation in the step of determining a minimum distance.

16. The method of claim 15 further comprising applying a deformation component cost factor to penalize large deformations in the step of determining a minimum distance.

17. A method to facilitate pattern recognition between a first pattern and a second pattern, comprising

applying to the first pattern a substantially smooth deformation field having deformation coefficients to deform the first pattern and form a first deformation component;

adding the first deformation component and the first pattern to define a first deformed pattern;

determining the deformation coefficients for the first pattern that minimize a distance between the first deformed pattern and the second pattern;

using the determined deformation coefficients to evaluate a distance between the first deformed pattern and the second pattern; and

applying a pattern cost factor to at least the first pattern to selectively weight different aspects of the first pattern in the step of determining a minimum distance.

18. A computer-readable medium having computer-executable instructions for:

applying to the first pattern a substantially smooth deformation field having deformation coefficients to deform the first pattern and form a first deformation component, the substantially smooth deformation field for the first pattern is parameterized by functional basis vectors and by the deformation coefficients for the first pattern,

adding the first deformation component and the first pattern to define a first deformed pattern;

determining the deformation coefficients for the first patterns that minimize a cost functionally related to a difference between the first deformed pattern and the second pattern,

employing the determined deformation coefficients to evaluate the cost between the first deformed pattern and the second pattern; and

applying a second smooth deformation field to the second pattern to form a second deformation component that is added to the second pattern to define a second deformed pattern, the second deformation field being parameterized by functional basis vectors and deformation coefficients associated with the second pattern, the respective deformation coefficients for the first and second patterns being determined by minimizing a cost functionally related to a difference between the first deformed pattern and the second deformed pattern.

19. A method to facilitate pattern recognition between a first pattern and a second pattern, comprising the steps of:

applying to the first pattern a substantially smooth deformation field having first deformation coefficients to deform the first pattern and form a first deformation component;

adding the first pattern and the first deformation component to define a first deformed pattern;

applying to the second pattern a substantially smooth deformation field having second deformation coefficients to deform the second pattern and form a second deformation component;

adding the second pattern and the second deformation component to define a second deformed pattern; and

determining a minimum distance between the first deformed pattern and the second deformed pattern relative to the first and second deformation coefficients.

20. The method of claim 19, wherein the deformation fields for each of the first and second patterns include low frequency wavelet basis vectors and respective deformation coefficients.

21. The method of claim 19, wherein the respective deformation coefficients for the first and second patterns have substantially opposite values.

22. A computer-readable medium having computer-executable instructions for:

applying to the first pattern a substantially smooth deformation field having first deformation coefficients to deform the first pattern and form a first deformation component;

adding the first pattern and the first deformation component to define a first deformed pattern;

applying to the second pattern a substantially smooth deformation field having second deformation coefficients to deform the second pattern and form a second deformation component;

adding the second pattern and the second deformation component to define a second deformed pattern; and

determining a minimum distance between the first deformed pattern and the second deformed pattern relative to the first and second deformation coefficients, whereby the determined minimum distance provides a measure of similarity between the first and second patterns.

23. A system to measure similarity between first and second patterns comprising:

a first deformation system that applies a substantially smooth deformation field to deform the first pattern and provide a first deformation component, the deformation field having deformation coefficients, the deformation system applies the deformation field to a spatial derivative of the first pattern to derive the deformation component of the first pattern, the substantially smooth deformation field for the first pattern further comprises first and second vector components corresponding to respective first and second displacement components, each of the first and second vector components having associated deformation coefficients;

an aggregation system that aggregates the first deformation component and the first pattern to derive a first deformed pattern; and

a minimization system that minimizes a distance between the first deformed pattern and the second pattern relative to the deformation coefficients.

24. The system of claim 23, the deformation system further applies a second substantially smooth deformation field to the second pattern to form a second deformation component, the deformation system adding the second deformation component to the second pattern to define a second deformed pattern, the second deformation field being parameterized by functional basis vectors and deformation coefficients associated with the second pattern, the minimization system determining a minimum distance as a function of the first deformed pattern and the second deformed pattern.

25. The system of claim 24, wherein the deformation fields for each of the first and second patterns include wavelet basis vectors and respective deformation coefficients.

26. The system of claim 25, wherein the respective deformation coefficients for the first and second patterns are determined to have substantially opposite values.

27. A system to measure similarity between first and second patterns, comprising:

a first deformation system for applying a substantially smooth deformation field to deform the first pattern and provide a first deformation component, the substantially smooth deformation field having deformation coefficients;

an aggregation system for aggregating the first deformation component and the first pattern to derive a first deformed pattern;

a minimization system for minimizing a distance between the first deformed pattern and the second pattern relative to the deformation coefficients, and

a deformation cost function that imposes a cost functionally related to the deformation coefficients to selectively weight different parts of the deformed pattern.

28. The system of claim 27 further comprising a deformation cost function for constraining large elastic deformations.

29. The system of claim 27, the minimized distance comprises at least one cost function, the deformation coefficients being computed by minimizing the cost function.

30. A system to measure similarity between first and second patterns, comprising:

a first deformation system that applies a substantially smooth deformation field to deform the first pattern and provide a first deformation component, the substantially smooth deformation field having deformation coefficients;

an aggregation system that aggregates the first deformation component and the first pattern to derive a first deformed pattern;

a minimization system that minimizes a distance between the first deformed pattern and the second pattern relative to the deformation coefficients, and

a pattern cost function to selectively weight different aspects of the first pattern.