Fast invariant matching using template decomposition and synthesis

• US 7,110,603 B2
• Filed: 04/16/2003
• Issued: 09/19/2006
• 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.
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US10/419,913
• Publication Number:
  US 20040208374A1
• Time in Patent Office: 1,252 Days
• Field of Search: 382/209, 382/291, 382/195, 382/296, 382/217, 382/218, 382/117, 382/224, 382/135, 382/219, 382/159, 382/190, 382/165, 382/151, 382/287, 382/278, 382/181, 706/20, 706/25, 706/27, 707/3, 358/1.9
• 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 matching 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.

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 wherein the refined invariant match includes an affine transformation using the match result values.

2. 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 wherein the invariant profile matching step further comprises the following steps

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

ii) 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 wherein the component specific invariant profile matching step includes matches over different scales.

3. 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 wherein the match synthesis step further comprises integration and synthesis steps.

4. The method of claim 3 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.

5. The method of claim 3 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.

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