Method for detecting and estimating the spatial position of objects from a two-dimensional image

• US 5,533,177 A
• Filed: 04/22/1993
• Issued: 07/02/1996
• Est. Priority Date: 10/24/1990
• Status: Expired due to Fees

• Current Assignee: Kraft Foods Incorporated (Mondelez International, Inc.)
• Original Assignee: Siemens AG
• Inventors: Maggioni, Chistoph, Wirtz, Brigitte
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US08/039,352
• Time in Patent Office: 1,167 Days
• Field of Search: 395/118, 395/119, 395/120, 395/124, 395/125, 395/127
• US Class Current: 345/419
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06T 2207/20084 Artificial neural networks [ANN]
• CPC Class Codes: G06T 7/50 Depth or shape recovery
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

Use is made of an adaptive vector quantization in order to detect three-dimensional objects and to estimate their position parameters in space from two-dimensional coordinates of feature points which have been obtained by digital image preprocessing methods from a two-dimensional image of the three-dimensional object. For this purpose, a special learning method and a special method for object detection and for position estimation are specified. The method can be applied in wide fields of video-based production automation.

Claims

1. A method for estimating position parameters of an object in space from a two-dimensional image using a Kohonen network having neurons, comprising the steps of:

a) prescribing indexable weighting vectors m(i)=(m(i,1), . . . , m(i,M)) of a dimension M and positional parameters x(i)=(x(i,1), . . . , x(i,N)) of a dimension N, allocated to the weighting factors, by whole numbers i that unambiguously identify each neuron i of the Kohonen network;

b) forming a pattern vector v=(v(1), . . . , v(k), . . . , v(M)) from two-dimensional coordinates p(k), g(k) of feature points in the image, whereby v(k) describes a respective feature point in the image in a respective form v(k)=(p(k),q(k));

c) applying the pattern vector v=(v(1), . . . v(k), . . . , v(M)) to each neuron i of the Kohonen network;

d) calculating a respective output value a(i)=a(v,m(i)) for the applied pattern vector v=(v(1), . . . , v(k), . . . , v(M)) in each neuron i of the Kohonen network; and

e) deriving sought positional parameters from respective positional parameters x(i)=(x(i,

     1), . . . , x(i,N)) allocated to a neuron i having an optimum output value a(v,m(i)).

2. The method according to claim 1 for object detection in conjunction with simultaneous estimation of position parameters of an object in space from a two-dimensional image using a Kohonen network having neurons, wherein the method further comprises using, in addition to the positional parameters, object identities for recognition of objects in the step of adapting.

3. The method as claimed in claim 1, wherein the output values a(i) are calculated using the relationship ##EQU17## from the pattern vector v and the weighting vectors m(i), and wherein minimum output values are optimal.

4. The method as claimed in claim 1, wherein the output values a(i) are calculated using the relationship ##EQU18## from the pattern vector v and the weighting factors m(i), weights g(v, k) being a measure of reliability of values of the components v(k) of the pattern vector v, and minimum output values being optimal.

5. The method as claimed in claim 1, wherein the output values a(i) are calculated using the relationship ##EQU19## from the pattern vector v and the weighting factors m(i), and wherein maximum output values are optimal.

6. The method as claimed in claim 1, wherein said position parameters include rotational angles referenced to three axes of a spatial coordinate system.

20. The method according to claim 5, wherein object identities for recognition of objects are additionally taken into consideration in the adaptation.

7. A method for estimating position parameters of an object in space from a two-dimensional image using a Kohonen network having neurons, comprising the steps of:

a) prescribing indexable weighting vectors m(i)=(m(i,1), . . . , m(i,M)) of a dimension M and positional parameters x(i)=(x(i,1), . . . , x(i,N)) of a dimension N, allocated to the weighting factors, by whole numbers i that unambiguously identify each neuron i of the Kohonen network;

b) forming a pattern vector v=(v(1), . . . , v(k), . . . , v(M)) from two-dimensional coordinates p(k), g(k) of feature points in the image, whereby v(k) describes a respective feature point in the image in a respective form v(k)=(p(k),q(k));

c) applying the pattern vector v=(v(1), . . . v(k), . . . , v(M)) to each neuron i of the Kohonen network;

d) calculating a respective output value a(i)=a(v,m(i)) for the applied pattern vector v=(v(1), . . . , v(k), . . . , v(M)) in each neuron i of the Kohonen network;

e) deriving sought positional parameters from respective positional parameters x(i)=(x(i,1), . . . , x(i,N)) allocated to a neuron i having an optimum output value a(v,m(i));

f) calculating an optimum of a function

space="preserve" listing-type="equation">A(u,b)=a(v,b·

m(w)+(1-b)·

m(u))

of a real variable b with 0≦

b≦

1 for all grid points u in a predetermined environment U of a grid point w that is determined by the neuron i having the optimum output value a(v,m(i));

g) identifying a grid point, opt, for which A(opt,b(opt)) is optimum among all A(u,b(u)) for all grid points u of the environment in the grid point w, whereby b(u) identifies the position of the optimum of A(u,b) as a function of b in an interval 0≦

b≦

1; and

h) deriving the sought positional parameters x(i) from the relationship

space="preserve" listing-type="equation">x(i)=b(opt)·

x(w)+(1-b(opt))·

x(opt)

as a convex linear combination from positional parameters of two grid points.

8. The method as claimed in claim 7, wherein the output values a(i) are calculated using the relationship ##EQU20## from the pattern vector v and the weighting vectors m(i), and wherein minimum output values are optimal.

9. The method as claimed in claim 7, wherein the output values a(i) are calculated using the relationship ##EQU21## from the pattern vector v and the weighting factors m(i), weights g(v, k) being a measure of reliability of values of the components v(k) of the pattern vector v, and minimum output values being optimal.

10. The method as claimed in claim 7, wherein the output values a(i) are calculated using the relationship ##EQU22## from the pattern vector v and the weighting factors m(i), and wherein maximum output values are optimal.

11. The method as claimed in claim 7, wherein said position parameters include rotational angles referenced to three axes of a spatial coordinate system.

12. The method as claimed in claim 7, wherein the method further comprises using, in addition to the positional parameters, object identities for recognition of objects in the step of adapting.

13. A method for estimating position parameters of an object in space from a two-dimensional image using a Kohonen network having neurons, comprising the steps of:

a) prescribing indexable weighting vectors m(i)=(m(i,1), . . . , m(i,M)) of a dimension M and positional parameters x(i)=(x(i,1), . . . , x(i,N)) of a dimension N, allocated to the weighting factors, by whole numbers i that unambiguously identify each neuron i of the Kohonen network;

b) forming a pattern vector v=(v(1), . . . , v(k), . . . , v(M)) from two-dimensional coordinates p(k), g(k) of feature points in the image, whereby v(k) describes a respective feature point in the image in a respective form v(k)=(p(k),q(k));

c) applying the pattern vector v=(v(1), . . . , v(k), . . . , v(M)) to each neuron i of the Kohonen network;

d) calculating a respective output value a(i)=a(v,m(i)) for the applied pattern vector v=(v(1), . . . , v(k), . . . . , v(M)) in each neuron i of the Kohonen network;

e) deriving sought positional parameters from respective positional parameters x(i)=(x(i,

     1), . . . , x(i,N)) allocated to a neuron i having an optimum output value a(v,m(i));

f) calculating an optimum of a function ##EQU23## of a real variable b in an interval 0≦

b≦

1 for all grid points u in a predetermined environment U of a grid point w that is determined by the neuron i having the optimum output value a(v,m(i)); and

g) deriving the sought positional parameters x(i) from the relationship ##EQU24## as a convex linear combination of positional parameters x(w) and x(u).

14. The method as claimed in claim 13, wherein the output values a(i) are calculated using the relationship ##EQU25## from the pattern vector v and the weighting vectors m(i), and wherein minimum output values are optimal.

15. The method as claimed in claim 13, wherein the output values a(i) are calculated using the relationship ##EQU26## from the pattern vector v and the weighting factors m(i), weights g(v, k) being a measure of reliability of values of the components v(k) of the pattern vector v, and minimum output values being optimal.

16. The method as claimed in claim 13, wherein the output values a(i) are calculated using the relationship ##EQU27## from the pattern vector v and the weighting factors m(i), and wherein maximum output values are optimal.

17. The method as claimed in claim 13, wherein said position parameters include rotational angles referenced to three axes of a spatial coordinate system.

18. The method as claimed in claim 13, wherein the method further comprises using, in addition to the positional parameters, object identities for recognition of objects in the step of adapting.

19. A method for adapting weighting vectors for estimating positional parameters of an object in space from a two-dimensional image using a Kohonen network having neurons, the neurons i forming a grid, comprising the steps of:

a) prescribing indexable weighting vectors m(i)=(m(i,1), . . . , m(i,M)) of a dimension M and positional parameters x(i)=(x(i,1), . . . , x(i,N)) of a dimension N, allocated to the weighting factors, by whole numbers i that unambiguously identify each neuron i of the Kohonen network;

b) for every time t of the adaptation,

b1) prescribing a learning rate L(t) that monotonously decreases with time;

b2) prescribing a degree of coupling factor h(i,j,t) that allocates a degree of coupling that decreases monotonously with spacing of points of the grid and monotonously with time to two respective points (i(1,i(2),i(3), (j(1),j(2),j(3)) on the grid that is formed by the neurons i of the Kohonen network;

b3) prescribing a training pattern vector v(t)=(v(1,t), . . . , v(M, t)) of dimension M that is formed of two-dimensional coordinates of feature points in the image and positional parameters XT(t)=(XT(1,t), . . . , XT(N,t)) associated with said training pattern vector;

b4) calculating momentary output values a(i,t)=a(v(t), m(i,t)) at time t for each neuron i from the prescribed training pattern vector v(t) and from momentary weighting vectors m(i,t) at time t;

b5) calculating a neuron i with optimum output value a(v,m(i)), said neuron i having an associated grid point w;

b6) adapting weighting vectors m(i,t) of every neuron i using the relationships

space="preserve" listing-type="equation">m(i,t+1)=m(i,t)+L(t)·

h(i,w,t)·

(v(t)-m(i,t))

space="preserve" listing-type="equation">x(i,t+1)=x(i,t)+L(t)·

h(i,w,t)·

(XT(t)-x(i,t)).

21. The method as claimed in claim 19, wherein the method further comprises using a learning rate L(t) of a form ##EQU28## with prescribed initial and final learning rates L(start) and L(end) respectively, up to a final instant t(end) of the adaptation.

22. The method according to claim 19, wherein the method further comprises using a coupling strength function h(i, j, t) of a form ##EQU29## and with prescribed initial and final ranges s(start) and s(end), respectively, up to a final instant t(end) of the adaptation.

23. The method as claimed in claim 19, wherein the pattern vectors v=(v(1), . . . , v(M)) in the form of v(k)=(p(k), q(k)) are formed from two-dimensional coordinates p(k), q(k) of feature points k=1, . . . , M in the image.

24. The method as claimed in claim 19, wherein the output values a(i) are calculated using the relationship ##EQU30## from the pattern vector v and the weighting vectors m(i), and wherein minimum output values are optimal.

25. The method as claimed in claim 19, wherein the output values a(i) are calculated using the relationship ##EQU31## from the pattern vector v and the weighting factors m(i), weights g(v, k) being a measure of reliability of values of the components v(k) of the pattern vector v, and minimum output values being optimal.

26. The method as claimed in claim 19, wherein the output values a(i) are calculated using the relationship ##EQU32## from the pattern vector v and the weighting factors m(i), and wherein maximum output values are optimal.

27. The method as claimed in claim 19, wherein said position parameters include rotational angles referenced to three axes of a spatial coordinate system.