Fast high precision matching method

• US 7,463,773 B2
• Filed: 11/26/2003
• Issued: 12/09/2008
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: Nikon Corporation
• Original Assignee: DRVision Technologies, LLC (Danaher Corporation)
• Inventors: Oh, Seho, Lee, Shih-Jong J.
• Primary Examiner(s): Ahmed; Samir A
• Assistant Examiner(s): Bitar; Nancy
• Application Number:
  US10/723,397
• Publication Number:
  US 20050114332A1
• Time in Patent Office: 1,840 Days
• Field of Search: 382/218, 382/151, 382/209, 382/217, 382/291, 382/195, 382/296, 382/117, 382/224, 382/135, 382/219, 382/190, 382/165, 382/287, 382/278, 382/181, 707/6, 707/3, 706/20, 706/25, 706/27
• US Class Current: 382/218
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An initial search method uses the input image and the template to create an initial search result output. A high precision match uses the initial search result, the input image, and the template to create a high precision match result output. The high precision match method estimates high precision parameters by image interpolation and interpolation parameter optimization. The method also performs robust matching by limiting pixel contribution or pixel weighting. An invariant high precision match method estimates subpixel position and subsampling scale and rotation parameters by image interpolation and interpolation parameter optimization on the log-converted radial-angular transformation domain.

Claims

1. A fast high precision matching method comprising the steps of:

a) Input an image;

b) Input a template;

c) Perform initial search using the input image and the template based on a matching function to create an initial search result output containing only matching function values at discrete (x,y) positions;

d) Create high precision matching function by interpolating the matching function values of discrete (x,y) positions making them matching function values of subpixel positions or of invariant high precision parameters;

e) Perform high precision match by high precision matching function maximization directly using the matching function values at discrete (x,y) positions from the step (c), the input image, and the same template from step (b) to create a high precision match result output without image matching wherein the high precision match result output around a pixel position (x,y) is the subpixel values α and

β and

other parameters correspond to the maximum value of the high precision matching function.

2. The method of claim 1 wherein the matching function maximization for the subpixel values or invariant high precision parameters is performed using optimization methods.

3. A fast high precision matching method comprising the steps of:

a) Input an image;

b) Input a template containing pre-calculated template variance parameters;

c) Perform initial search using the input image and the template based on a matching function to create an initial search result output containing only matching function values at discrete (x,y) position;

d) Create high precision matching function by interpolating the matching function values of discrete (x,y) positions making them matching function values of subpixel positions of invariant high precision parameters;

e) Perform high precision match by high precision matching function maximization directly using the matching function values at discrete (x,y) positions from step (c), the input image, and the same template from step (b) to create a high precision match result output without image matching wherein the high precision match result output around a pixel position (x,y) is the subpixel values α and

β and

other parameters correspond to the maximum value of the high precision matching function.

4. A fast high precision projection matching method comprising the steps of:

a) Input a projection profile;

b) Input a template profile;

c) Create high precision matching function by interpolating matching function values at discrete (x,y) positions and samples parameters making them matching function values of subpixel positions or of subsampling parameters;

d) Perform high precision match by high precision matching function maximization using the projection profile, the same template profile from step (b) to create a high precision projection match result output Perform high precision match by high precision matching function maximization directly using the matching function values at discrete (x,y) positions from step (c), the input image, and the same template from step (b) to create a high precision match result output without image matching wherein the high precision match result output around a pixel position (x,y) is the subpixel values α and

β and

other parameters correspond to the maximum value of the high precision matching function.

5. A fast invariant high precision matching method comprising the steps of:

a) Input an image;

b) Input a template;

c) Perform initial search using the input image and the template based on a matching function to create an initial search result output containing only matching function values at discrete (x,y) position;

d) Create high precision matching function by interpolating the matching function values of discrete (x,y) positions making them matching function values of subpixel positions or of invariant high precision parameters;

e) Perform invariant high precision match by high precision matching function maximization directly using the matching function values at discrete (x,y) positions from step (c), the input image, and the same template from step (b) to create an invariant high precision match result output without image matching wherein the high precision match result output around a pixel position (x,y) is the subpixel values α and

β and

other parameters correspond to the maximum value of the high precision matching function.

6. The method of claim 5 wherein interpolating the matching function includes log-converted radial-angular transformation and linear interpolation.