Correspondence-between-images detection method and system

• US 6,546,120 B1
• Filed: 08/12/1999
• Issued: 04/08/2003
• Est. Priority Date: 07/02/1997
• Status: Expired due to Term

• Current Assignee: Sovereign Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Etoh, Minoru, Hata, Kouichi
• Primary Examiner(s): Johnson, Timothy M.
• Assistant Examiner(s): Tabatabai, Abolfazl
• Application Number:
  US09/373,408
• Time in Patent Office: 1,335 Days
• Field of Search: 382/107, 382/154, 348/154, 348/155, 348/461, 348/463, 348/42, 348/140, 340/825
• US Class Current: 382/107
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation

Abstract

A correspondence-between-images detection method includes the following three basic steps: (1) Error operation step based on block matching: Block matching is executed by making a search for displacement with the difference absolute sum of intensity errors reaching the minimum from within a comparison image with respect to a block of 16×16 pixels in a reference image. (2) Quadratic error function approximation step with differential operator: Assuming that the block matching result forms a curved surface is parabolic, quadratic error function approximation is executed. (3) Nonlinear iteractive minimization step with respect to planar perspective mapping parameter: The quadratic error function sum on the whole screen is found by executing a sequential recursive step of a Newton'"'"'s method improved for planar perspective mapping parameter.

Claims

1. A method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said method comprising:

(1a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(1b) error function operation step of finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement; and

(1c) nonlinear iteractive minimization step of again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function and executing nonlinear iteractive minimization for the parameter for finding a parameter, said nonlinear iteractive minimization step comprising;

(1c-1) partial differential operation step of finding a first-order partial differential vector and a second-order partial differential matrix concerning the parameter of the sum total or partial sum of the quadratic error functions;

(1c-2) second-order partial differential matrix change step of increasing diagonal elements of the second-order partial differential matrix in response to the degree to which the minimization in each repetition falls below a predetermined expected value; and

(1c-3) parameter change step of multiplying the first-order partial differential vector by an inverse matrix of the modified second-order partial differential matrix for providing a parameter increment or decrement, wherein

each parameter increment or decrement provided by iterating said partial differential operation step, said second-order partial differential matrix change step, and said parameter change step is added sequentially for changing the parameter for executing the minimization.

2. A system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said system comprising:

(2a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(2b) error function operation means for finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement; and

(2c) nonlinear iteractive minimization means for again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function and executing nonlinear iteractive minimization for the parameter for finding a parameter, said nonlinear iteractive minimization means comprising;

(2c-1) partial differential operation means for finding a first-order partial differential vector and a second-order partial differential matrix concerning the parameter of the sum total or partial sum of the quadratic error functions;

(2c-2) second-order partial differential matrix change means for increasing diagonal elements of the second-order partial differential matrix in response to the degree to which the minimization in each repetition falls below a predetermined expected value; and

(2c-3) parameter change means for multiplying the first-order partial differential vector by an inverse matrix of the modified second-order partial differential matrix for providing a parameter increment or decrement, wherein

each parameter increment or decrement provided by iterating said partial differential operation means, said second-order partial differential matrix change means, and said parameter change means is added sequentially for changing the parameter for executing the minimization.

3. A method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said method comprising:

(3a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(3b) error function operation step of finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement;

(3c) linear parameter operation step of again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function, classifying into a linear-minimization-possible parameter with a partial derivative for parameter becoming a linear function and a nonlinear minimization parameter with a partial derivative for parameter not becoming a linear function, and finding only the former by executing linear minimization; and

(3d) all parameter operation step of finding all parameters by executing nonlinear iteractive minimization of the sum total or partial sum of the quadratic error functions with the parameter found by executing said linear parameter operation step as an initial value for the linear-minimization-possible parameter.

4. A system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said system comprising:

(4a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(4b) error function operation means for finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement;

(4c) linear parameter operation means for again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function, classifying into a linear-minimization-possible parameter with a partial derivative for parameter becoming a linear function and a nonlinear minimization parameter with a partial derivative for parameter not becoming a linear function, and finding only the former by executing linear minimization; and

(4d) all parameter operation means for finding all parameters by executing nonlinear iteractive minimization of the sum total or partial sum of the quadratic error functions with the parameter found by said linear parameter operation means as an initial value for the linear-minimization-possible parameter.

5. method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said method comprising:

(5a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(5b) error function operation step of finding for each local area a quadratic error function having a minimum value of zero with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement;

(5c) recursive minimization step of again representing the weighted sum total of the quadratic error functions in a parameter representing a function and executing recursive minimization for the parameter for finding a parameter; and

(5d) weighting resetting step of setting a weight inversely proportional to the value of the quadratic error function in the iteration process of the recursive minimization.

6. A system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said system comprising:

(6a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(6b) error function operation means for finding for each local area a quadratic error function having a minimum value of zero with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement;

(6c) recursive minimization means for again representing the weighted sum total of the quadratic error functions in a parameter representing a function and executing recursive minimization for the parameter for finding a parameter; and

(6d) weighting resetting means for setting a weight indirectly proportional to the value of the quadratic error function in the iteration process of the recursive minimization.

7. A method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said method comprising:

(7a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(7b) error function operation step of finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement;

(7c) error parameter conversion step of again defining the sum total or partial sum of the quadratic error functions in a parameter for defining a function from the relationship between a line mapped and a displacement for determining the value of the quadratic error function; and

(7d) minimization step of minimizing the sum total or partial sum of the quadratic error functions again converted into the parameter for parameter and outputting the minimization parameter as motion between the images.

8. A system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, said system comprising:

(8a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement;

(8b) error function operation means for finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement;

(8c) error parameter conversion means for again defining the sum total or partial sum of the quadratic error functions in a parameter for defining a function from the relationship between a line mapped and a displacement for determining the value of the quadratic error function; and

(8d) minimization means for minimizing the sum total or partial sum of the quadratic error functions again converted into the parameter for parameter and outputting the minimization parameter as motion between the images.