Image matching method using direction sensitivity and vector smoothing functions for correcting matches

• US 5,406,642 A
• Filed: 04/06/1993
• Issued: 04/11/1995
• Est. Priority Date: 12/23/1988
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Maruya, Makoto
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/044,077
• Time in Patent Office: 735 Days
• Field of Search: 382/34, 382/30, 382/16, 382/41, 382/42, 382/44, 358/136
• US Class Current: 382/218
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

In a block matching method, a successive one of segmented blocks of a first image is superimposed on a portion of a second image, and a correlation is detected therebetween. The superimposed block is successively moved by a small amount and correlations are repeatedly detected for different locations of the successively moved block. A maximum value of the correlations is detected and a vector representing the location of the block of the maximum correlation is stored into a memory as a match between a block of the first image and a portion of the second image. The process is repeated for the remaining blocks of the first image to create a map of the matching vectors in the memory. Direction sensitivity functions and vector smoothing functions are derived from the segmented blocks for respectively correcting the stored matching vectors. In a preferred embodiment, prior to the successive movement of the block, a first direction sensitivity function is derived from the block and a second direction sensitivity function from the corresponding portion of the second image. Correlation is detected between these functions and the block is successively rotated by a small angle, and the derivation of these functions and the detection of correlations therebetween are repeated to detect a maximum correlation. The orientation of the block is set to the angle of the the maximum correlation. A gradient method is employed for deriving optimum values for correcting the stored vectors.

Claims

1. A method for matching first and second images located on an image plane using a processor, said first and second images being segmented into a plurality of blocks, comprising the steps of:

a) retrieving a segmented block of the first image and a segmented block of the second image from a first memory;

b) superimposing the segmented block of the first image on the segmented block of the second image using the processor;

c) detecting a correlation between the superimposed block of the first image and the segmented block of the second image using the processor;

d) moving the superimposed block of the first image by a predetermined amount in the image plane and representing a location of the superimposed block with respect to a reference point of the image plane by a vector;

e) repeating the steps c) and d) to produce a plurality of said correlations and a plurality of said vectors;

f) detecting a maximum of said correlations and storing the vector associated with the maximum correlation into a second memory as a matching vector;

g) repeating the steps (a) to (e) to create a map of the matching vectors in a second memory; and

h) replacing each of said matching vectors in a second memory with a correction vector which minimizes a sum of a direction sensitivity function of said block and a smoothing function of said block, said direction sensitivity function being represented by a squared value of second order of a differential equation of luminance distribution of said block.

2. A method as claimed in claim 1, wherein said direction sensitivity functions are represented by:

##EQU5## where, A represents each of said segmented blocks, f is a luminance value of each of said blocks, n is an integer, θ

is the angle of orientation of each of said blocks on said image plane, and ∂

f/∂

n is a derivative of the luminance value of each of said blocks in a direction of said angle.

3. A method as claimed in claim 2, wherein the sum of the direction sensitivity function of the block and the smoothing function of the block is represented by:

##EQU6## where, i is an integer in the range between l and N, where N represents a total number of said segmented blocks, b_i represents the matching vector associated with a block A_i of said first image, r_i represents a vector variable for said block A_i, C₀, C₁ and C₂ are constants, Θ

_i is the angle of orientation of said matching vector b_i and ∇

is Hamilton operator, and the step (g) further includes the steps of;

g1 varying said r_i vector until said function decreases to a minimum; and

g2) replacing said matching vector b_i with the r_i vector which is obtained by the step g1) when said function reaches said minimum.

4. A method for matching first and second images located on a common image plane, said first image being segmented into a plurality of blocks, comprising the steps of:

a) superimposing a successive one of said segmented blocks on a portion of the second image;

b) deriving a first direction sensitivity function from the superimposed block of said first image and a second direction sensitivity function from said portion of the second image;

c) detecting a first correlation between said first and second direction sensitivity functions;

d) rotating said superimposed block by a predetermined angle with respect to said portion of said second image;

e) repeating the step (c) and (d) to produce a plurality of said first correlations for different angles of orientations of the successively rotated block;

f) detecting a maximum of said first correlations;

g) setting the orientation of said block to the angle at which the maximum first correlation is detected;

h) detecting a second correlation between the block of the step (g) and a corresponding portion of said second image;

i) moving said block by a predetermined amount in said plane and representing the location of the moved block with respect to a reference point of said image plane by a vector;

j) repeating the steps (h) and (i) to produce a plurality of said second correlations and a plurality of said vectors;

k) detecting a maximum of said second correlations and storing one of said vectors associated with the maximum second correlation into a memory as a matching vector;

l) repeating the steps (a) to (k) to create a map of the matching vectors in said memory; and

m) replacing each of said matching vectors in said memory with a correction vector which minimizes a sum of said first direction sensitivity function and a smoothing function of said block, said direction sensitivity function being represented by a squared value of second order of a differential equation of luminance distribution of said block.

5. A method as claimed in claim 4, wherein said first direction sensitivity function is represented by:

##EQU7## and said second direction sensitivity function is represented by;

##EQU8## where, A represents each of said segmented blocks, B represents each of said portions on which said block A is superimposed, f is a luminance value of each of said blocks A and said portion B, n is an integer, θ

is the angle of orientation of each of said blocks on said image plane, and ∂

f/∂

n is a derivative of the luminance value of each of said blocks and each of said portions of the second image in a direction of said angle.

6. A method as claimed in claim 5, wherein the sum of the first direction sensitivity function and the smoothing function is represented by:

##EQU9## where, i is an integer in the range between 1 and N, where N represents a total number of said segmented blocks, b_i represents the matching vector associated with a block A_i of said first image, r_i represents a vector variable for said block A_i, C₀, C₁ and C₂ are constants, Θ

_i is the angle of orientation of said matching vector b_i and ∇

is Hamilton operator, and the step (m) further includes the steps of;

m1) varying said vector r_i until said function decreases to a minimum; and

m2) replacing said matching vector b_i with the vector r_i which is obtained by the step (m1) when said function reaches said minimum.

7. A method for matching first and second images located on an image plane, comprising the steps of:

(a) segmenting the first image into a plurality of blocks;

(b) storing the segmented first image in a first memory;

(c) storing a second image in the first memory;

(d) superimposing a successive one of the segmented blocks on a portion of the second image;

(e) detecting a correlation between the segmented block and the portion of the second image upon which the segmented block is superimposed;

(f) displacing the segmented block in the image plane over the second image by a predetermined amount after a correlation has been detected and representing a location of the block with respect to a reference point of the image plane by a vector which is associated with the detected correlation;

(g) repeating steps (c) and (d) to produce a plurality of correlations and a plurality of vectors;

(h) detecting a maximum correlation from among the plurality of correlations and storing the vector associated with the maximum correlation into a second memory as a matching vector;

(i) repeating steps (b) to (f) to create a map of the matching vectors in the second memory; and

(j) replacing each of the matching vectors in the memory with a correction vector which minimizes a sum of a direction sensitivity function of the block and a smoothing function of the block, the direction sensitivity function defining a squared value of a second order of a differential equation of luminance distribution of the block and the smoothing function defining the degree of smoothness of the correction vector.