Fast invariant matching using template decomposition and synthesis

• US 20040208374A1
• Filed: 04/16/2003
• Published: 10/21/2004
• Est. Priority Date: 04/16/2003
• Status: Active Grant

• Current Assignee: Nikon Corporation
• Original Assignee: Shih-Jong J. Lee
• Inventors: Oh, Seho, Lee, Shih-Jong J.
• Granted Patent: US 7,110,603 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A fast decomposition and synthesis invariant matching method receives an input image and a pattern template. The input image and pattern template image are used to create a match result output. A refined invariant match uses the initial match result and the pattern template to create a refined invariant match result. The fast decomposition and synthesis invariant pattern search method performs pattern decomposition and synthesis learning to create a pattern search recipe that is used by an invariant pattern search and synthesis method to generate the match result. The pattern search recipe includes template component invariant profiles, component weights, and allowable partial pattern configurations. The invariant matching method supports partial pattern match.

This invention decomposes a template into multiple compact shaped components and performs search using separate rotation and scale invariant profiles for each component. It then synthesizes the search results for the complete template or partial template using the component search results. This invention can be directly generalized to three-dimensional or higher dimensional invariant pattern search and can achieves greater speed and accuracy than the prior art methods. Therefore, it can be used in applications such as 3D medical imaging, dynamic medical imaging, confocal microscopy, live cell assays in drug discovery, or ultrasound imaging.

Claims

1. A fast decomposition and synthesis invariant matching method comprises the steps of:

a) Input an image;

b) Input a pattern template;

c) Perform fast decomposition and synthesis invariant pattern search using the input image and the pattern template to create a match result output;

d) Perform refined invariant match using the match result and the pattern template to create a refined invariant match result output.

2. The method of claim 1 wherein the fast decomposition and synthesis invariant search step further comprises the following steps

a) Perform pattern decomposition and synthesis learning using the pattern template to create a pattern search recipe output;

b) Perform invariant pattern search and synthesis using the pattern search recipe and the input image to create a match result output.

3. The method of claim 2 wherein the pattern decomposition and synthesis learning step further comprises the following steps

a) Perform pattern decomposition using the pattern template to create a pattern decomposition result output;

b) Perform pattern search recipe creation using the pattern decomposition result and the pattern template to create a pattern search recipe output.

4. The method of claim 2 wherein the invariant pattern search and synthesis step further comprises

a) Perform invariant profile matching using the pattern search recipe and the input image to create an invariant profile matching result images output;

b) Perform match synthesis using the invariant profile matching result images and the pattern search recipe to create a match result output.

5. The method of claim 4 wherein match synthesis comprises a partial pattern matching step.

6. The method of claim 1 wherein the refined invariant match includes an affine transformation using the match result values.

7. A pattern decomposition and synthesis learning method comprises the steps of:

a) Input a pattern template;

b) Perform pattern decomposition using the pattern template to create a pattern decomposition result output;

c) Perform pattern search recipe creation using the pattern decomposition result and the pattern template to create a pattern search recipe output.

8. The method of claim 7 wherein the pattern decomposition method uses at least one location selection criterion.

9. The method of claim 7 wherein the pattern search recipe creation step further comprises

a) Perform decomposition component invariant profile generation using pattern template and the pattern decomposition result to create a template decomposition component invariant profiles output;

b) Perform Pattern decomposition configuration generation using the pattern decomposition result to create a decomposition component weights and allowable partial pattern configuration output.

10. The method of claim 9 wherein the decomposition component invariant profile generation uses circular contours.

11. The method of claim 10 wherein the circular contours are approximated by regular- shaped patterns.

12. The method of claim 9 wherein the decomposition component weights are learned automatically using a set of learning images.

13. A fast decomposition and synthesis invariant search method comprises the steps of:

a) Input an image;

b) Input a pattern template;

c) Perform pattern decomposition and synthesis learning using the pattern template to create a pattern search recipe output;

d) Perform invariant pattern search and synthesis using the pattern search recipe and the input image to create a match result output.

14. The method of claim 13 wherein the pattern decomposition and synthesis learning step further comprises the following steps

a) Perform pattern decomposition using the pattern template to create a pattern decomposition result output;

b) Perform pattern search recipe creation using the pattern decomposition result and the pattern template to create a pattern search recipe output.

15. The method of claim 13 wherein the invariant pattern search and synthesis step further comprises the following steps

a) Perform invariant profile matching using the pattern search recipe and the input image to create an invariant profile matching result images output;

b) Perform match synthesis using the invariant profile matching result images and the pattern search recipe to create a match result output.

16. The method of claim 15 wherein match synthesis comprises a partial pattern matching step.

17. An invariant pattern search and synthesis method comprises the steps of:

a) Input an image;

b) Input a pattern search recipe containing template decomposition component invariant profiles and decomposition component weights and allowable partial pattern configuration;

c) Perform invariant profile matching using the template decomposition component invariant profiles and the input image to create an invariant profile matching result images output;

d) Perform match synthesis using the invariant profile matching result images and the decomposition component weights and allowable partial pattern configuration to create a match result output.

18. The method of claim 17 wherein the invariant profile matching step further comprises the following steps

a) Perform invariant profile generation using the input image to create an invariant profiles output;

b) Perform at least one component specific invariant profile matching using the invariant profiles and template decomposition component invariant profiles to create at least one component specific invariant profile matching result image output.

19. The method of claim 18 wherein the component specific invariant profile matching step includes matches over different scales.

20. The method of claim 17 wherein the match synthesis step further comprises integration and synthesis steps.

21. The method of claim 20 wherein the integration step further comprises the following steps

a) Perform an integration 0 using the invariant profile matching result images for all components to create a first integration image output;

b) Perform an integration 1 using the invariant profile matching result images for all but the 0^th component to create a second integration image output.

22. The method of claim 20 wherein the synthesis step further comprises

a) Perform a first synthesis using the first integration image to create a first synthesis matching locations output;

b) Perform a second synthesis using the first synthesis matching locations to create a second synthesis matching locations output;

c) Perform a third synthesis using the first synthesis matching locations and the second synthesis matching locations to create a third synthesis matching locations output.

23. The method of claim 22 wherein the third synthesis step determines the rotational angle and the scale of each of the third matching locations.

24. The method of claim 17 wherein the match synthesis comprises a partial pattern matching step.

25. The method of claim 24 wherein the partial pattern matching step further comprises the following steps

a) Perform a complete pattern match synthesis using the invariant profile matching result images to create a complete match result output;

b) Perform at least one partial pattern configuration specific pattern match synthesis using the invariant profile matching result images to create at least one partial pattern configuration specific match result output;

c) Perform grouping using the complete match result and the at least one partial pattern configuration specific match result to create an overall match result output.