Point pattern matching method and system as well as picture recognizing method and system using the same

• US 5,259,038 A
• Filed: 10/10/1990
• Issued: 11/02/1993
• Est. Priority Date: 10/13/1989
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Uecker, Darrin R., Sakou, Hiroshi
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): KLOCINSKI, STEVEN
• Application Number:
  US07/595,099
• Time in Patent Office: 1,119 Days
• Field of Search: 382/14, 382/15, 382/16, 382/45, 382/46, 382/23, 382/30, 382/35
• US Class Current: 382/158
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 30/194 References adjustable by an adaptive method, e.g. learning

Abstract

A point pattern matching method and system for use in an object recognizing system for deciding pair combinations between a first group of n points x_j (n: integer of 2 or more) (j: integer between 1 and n) in a K-dimensional space (K: integer of 2 or more) and a second group of n second points x_i (i: integer between 1 and n) in the same space as the K-dimensional space. A total of n² of neurons are provided one for each one of point pair combinations between the first group of points and the second group of points, and, when an output of each of the neurons has a value of substantially "1", it is determined that the point pair combination associated with the neuron is matched, whereas, when the output of the neuron has a value of substantially "0", it is determined that the point pair combination associated with the neuron is not matched.

Claims

1. A point pattern matching method for deciding pair combinations between a first group of n points X_j (where n is an integer of 2 or more) (J:

integer between 1 and n) in a K-dimensional space (K;

integer of 2 or more), and a second group of n second points x_i (i;

integer between 1 and n) in the same space as the K-dimensional space, the method comprising the steps of;

providing a single neuron for each one of point pair combinations between said first group of points and said second group of points to make a total of n² neurons so that each neuron outputs a degree of correspondence between an associated point pair combination;

determining that, when an output of each of said neurons has a value of substantially "1", the point pair combination associated with the neuron is matched, whereas, when the output of the neuron has a value of substantially "0", the point pair combination associated with the neuron is not matched;

connecting said neurons to each other in a neural network, in a manner that each neuron inputs data associated with the output values of the other neurons;

operating the neural network to provide a minimum overall energy of the neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation.

2. A point pattern matching method as set forth in claim 1, wherein said neurons form a Hopfield-type neural network.

3. A point pattern matching method as set forth in claim 1, wherein said determining step includes a step of preparing a first threshold value substantially close to 1 and a second threshold value substantially close to 0, a step of obtaining output values of said neurons indicative of matching degrees in point pair combinations, a step of determining that, when the output value of the neuron exceeds said first threshold value, the point pair combination associated with the neuron is matched, and a step determining that, when the output value of the neuron does not exceed said second threshold value, the point pair combination associated with the neuron is not matched.

4. A point pattern matching method for deciding pair combinations between a first group of n points X_j (n:

integer of 2 or more) (j;

integer between 1 and n) in a K-dimensional space (K;

integer of 2 or more) and a second group of n second points x_i (i;

integer between 1 and n) in the same space as the K-dimensional space, the method comprising the steps of;

providing a single neuron to each one of point pair combinations between said first group of points and said second group of points to make a total of n² neurons so that each neuron outputs a degree of correspondence between an associated point pair combination, the neurons connected to each other in a neural network, in a manner that each neuron inputs data associated with the output values of the other neurons;

determining that when an output of each of the neurons has a value of substantially "1", the point pair combination associated with the neuron is matched and, when the output of the neuron has a value of substantially "0", the point pair combination associated with the neuron is not matched; and

operating the neural network to provide a minimum overall energy of the neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation.

5. A point pattern matching method as set forth in claim 4, wherein said second energy is a cost energy which is defined as said first group of points subjected to a linear transformation with respect to said second points.

6. A point pattern matching method as set forth in claim 5, wherein, when coordinates of said first group of points X_j and coordinates of said second group of points x_i are expressed respectively as (X_j1, X_j2, X_j3, . . . , X_jk) and (x_i1, x_i2, x_i3, . . . , x_ik), said second energy E₂ is given as, ##EQU26## where V is an output of a neuron, where n'"'"' is an integer, where q of x_iq represents a coordinate axis component of a point x_i before being subjected to an affine transformation, such that x_iq represents a q-th coordinate axis component of an i-th point and where a_pq represents an affine transformation coefficient corresponding to x_iq, and where affine transformation coefficients a₁₁, a₁₂, a₁₃, . . . , a_kk and c₁, c₂, c₃, . . . , c_k satisfy the following K equations (p:

integer between 1 and K), ##STR5##

7. A point pattern matching method as set forth in claim 4, wherein said second energy is defined as said first group of points subjected to a transformation which maintains an orthogonal state of said first group of points with respect to said second group of points after said transformation.

8. A point pattern matching method as set forth in claim 4, wherein said second energy is defined as said first group of points subjected to a nonlinear transformation with respect to said second group of points.

9. A point pattern matching method for deciding pair combinations between a first group of n points X_j (n:

integer of 2 or more) (j;

integer between 1 and n) in a two-dimensional space and a second group of n second points x_i (i;

integer between 1 and n) in the same space as the two-dimensional space, the method comprising the steps of;

providing a single neuron to each one of point pair combinations between said first group of points and said second group of points to make a total of n² neurons;

determining that, when an output of each of said neurons has a value of substantially "1", the point pair combination associated with the neuron is matched, whereas, when the output of the neuron has a value of substantially "0", the point pair combination associated with the neuron is not matched;

connecting said neurons to each other in a neural network in a manner that each neuron inputs data associated with the output values of the other neurons; and

operating the neural network to provide a minimum overall energy of the neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation.

10. A point pattern matching method as set forth in claim 9, wherein said neurons form a Hopfield-type neural network.

11. A point pattern matching method as set forth in claim 10, wherein said second energy is a cost energy which is defined as said first group of points subjected to a linear transformation with respect to said second group of points, and, when coordinates of the first group of points x_j and coordinates of the second group of points X_i are expressed respectively as (X_j, Y_j) and (x_i, y_i) said cost energy E₂ is given as:

##EQU27## where V is an output of a neuron, where n'"'"' is an integer, and transformation coefficients a, b, c, A, B and C satisfy, ##STR6##

12. A point pattern matching system for deciding pair combinations between a first group of n points X_j (n:

integer of 2 or more) (j;

integer between 1 and n) in a K-dimensional space (K;

integer of 2 or more) and a second group of n second points x_i (i;

integer between 1 and n) in the same space as the K-dimensional space, said system comprising;

a neural network having a total of n² neurons each provided for each one of point pair combinations between said first group of points and said second group of points, said neurons connected to each other in a manner that each neuron inputs data associated with the output values of the other neurons;

means for determining that, when an output of each of said neurons has a value of substantially "1", the point pair combination associated with the neuron is matched, whereas, when the output of the neuron has a value of substantially "0", the point pair combination associated with the neuron is not matched; and

adjusting means for operating the neural network to provide a minimum overall energy of said neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation.

13. A point pattern matching method as set forth in claim 12, wherein said neurons form a Hopfield-type neural network.

14. A point pattern matching method for deciding pair combinations between a first group of n points X_j (n:

integer of 2 or more) (j;

integer between 1 and n) in a two-dimensional space and a second group of n second points x_i (i;

integer between 1 and n) in the same space as the two-dimensional space, the method comprising the steps of;

providing a single neuron to each one of point pair combinations between said first group of points and said second group of points for a total of n² neurons;

determining that, when an output of each of said neurons has a value of substantially "1", the point pair combination associated with the neuron is matched and, when the output of the neuron has a value of substantially "0", the point pair combination associated with the neuron is not matched; and

connecting said neurons in a Hopfield-type neural network in a manner that each neuron inputs data associated with the output values of the other neurons to provide a minimum of overall energy of the neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points all in 1;

1 relation.

15. A point pattern matching method as set forth in claim 14, wherein said second energy is a cost energy which is defined as said first group of points subjected to a linear transformation with respect to said second group of points, and, when coordinates of the first group of points X_j and coordinates of the second group of points x_i are expressed respectively as (X_j1, X_j2, X_j3, . . . , X_jk) and (x_i1, x_i2, x_i3, . . . , x_ik), said second energy E₂ is given as, ##EQU28## where V is an output of a neuron, where n'"'"' is an integer, where q of x_iq represents a coordinate axis component of a point x_i before being subjected to an affine transformation, such that x_iq represents a q-th coordinate axis component of an i-th point and where a_pq represents an affine transformation coefficient corresponding to x_iq, and affine transformation coefficients a₁₁, a₁₂, a₁₃, . . . , a_kk and c₁, c₂, c₃, . . . , c_k satisfy the following K equations (p:

integer between 1 and K), ##STR7##

16. An object recognizing method for recognizing a site of an object in an image picture through picture processing, the method comprising the steps of:

extracting a first group of characteristic points x_i (i;

integer between 1 and n) from said object in said picture;

storing in memory means a second group of characteristic points X_j (j;

integer between 1 and n) of a model corresponding to the object and attribute data for said second group of characteristic points;

providing a neural network having a plurality of neurons each provided for each one of point pair combinations between the first group of characteristic points and the second group of characteristic points and the neurons connected to each other in a manner that each neuron inputs data associated with the output values of the other neurons;

operating the neural network to provide a minimum overall energy of said neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points al in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation;

reading out an output value of each neuron and determining that, when the output value of the neuron is substantially "1", the point pair combination associated with the neuron is matched, and

reading out from said memory means one of said attribute data of the second group of characteristic points corresponding to said point pair combination determined to be matched in said determining step.

17. A point pattern matching method as set forth in claim 16, wherein said neural network comprises a Hopfield-type neural network.

18. A point pattern matching method as set forth in claim 17, wherein said second group of characteristic points correspond to a group of n points (n:

integer of 2 or more) in a K-dimensional space (K;

integer of 2 or more) and said first group of characteristic points correspond to a group of n points in the same space as the K-dimensional space, and wherein, when coordinates of the second group of points X_j and coordinates of the first group of points x_i are expressed respectively as (X_j1, X_j2, X_j3, . . . , X_jk) and (x_i1, x_i2, x_i3, . . . , x_ik), said second energy E₂ is given as, ##EQU29## where V is an output of a neuron, where n'"'"' is an integer, where q of x_iq represents a coordinate axis component of a point x_i before being subjected to an affine transformation, such that x_iq represents a q-th coordinate axis component of an i-th point and where a_pq represents an affine transformation coefficient corresponding to x_iq, and affine transformation coefficients a₁₁, a₁₂, a₁₃, . . . , a_kk and c₁, c₂, c₃, . . . , c_k satisfy the following K equations (p;

integer between 1 and K), ##STR8##

19. An object recognizing system for recognizing a site of an object in an image picture through picture processing, said system comprising:

first means for extracting a first group of characteristic points x_i (i;

integer between 1 and n) from said object in said picture;

second means for storing a second group of characteristic points X_j (j;

integer between 1 and n) of a model corresponding to the object and attribute data for said second group of characteristic points;

a neural network having a plurality of neurons connected to each other in a manner that each neuron inputs data associated with the output values of the other neurons, the plurality of neurons each provided for each one of point pair combinations between the first group of characteristic points and the second group of characteristic points;

operating means for operating the neural network to provide a minimum overall energy of said neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation;

third means for reading out an output value of each neuron and determining that, when the output value of the neuron is substantially "1", the point pair combination associated with the neuron is matched; and

fourth means for reading out from said second means one of said attribute data of the second group of characteristic points corresponding to said point pair combination determined as matched by said third means.

20. A point pattern matching method for deciding pair combinations between a first group of feature points in a two-dimensional space and a second group of feature points in the same two-dimensional space, the method comprising the steps of:

providing a single neuron to each one of point pair combinations between said first group of feature points and said second group of feature points for a total of n² neurons (where n is an integer of 2 or more);

connecting said neurons to each other in a neural network in a manner that each neuron inputs data associated with the output values of the other neurons;

operating the neural network based on neurodynamics utilizing energy functions to provide a minimum overall energy of the neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation; and

,

determining that when the minimum overall energy of the neurons is achieved, optimal matching between the first group of feature points and the second group of feature points is achieved.

21. A point pattern matching method for deciding pair combinations between a first group of feature points in a two-dimensional space and a second group of feature points in the same space as the two-dimensional space, the method comprising the steps of:

providing a single neuron to each one of point pair combinations between said first group of points and said second group of points to make a total of n² neurons (where n is an integer of 2 or more);

connecting said neurons to each other in a neural network in a manner that each neuron inputs data associated with the output values of the other neurons;

operating the neural network based on weighting coefficients defined by coordinate values of the feature points to provide a minimum overall energy of the neurons, said overall energy being a linear coupling between a first energy defined as having its minimum value when said first group of points are matched with said second group of points all in 1;

1 relation and a second energy defined as providing a minimum of a matching error in a least squares sense when the first group of points are matched with the second group of points in a 1;

1 relation; and

determining that when the minimum overall energy of the neurons is achieved, optimal matching between the first group of feature points and the second group of feature points is achieved.