Method for recognizing objects in digitized images

• US 7,113,641 B1
• Filed: 08/13/1999
• Issued: 09/26/2006
• Est. Priority Date: 08/14/1998
• Status: Expired due to Term

• Current Assignee: Christian Eckes, Chrstoph Von Der Malsburg, Efthimia Kefalea, Jochen Triesch, Michael Rinne, Pötzsch, Michael, Vorbrüggen, Jan C.
• Original Assignee: Christian Eckes, Chrstoph Von Der Malsburg, Efthimia Kefalea, Jochen Triesch, Michael Rinne, Pötzsch, Michael, Vorbrüggen, Jan C.
• Inventors: Rinne, Michael, Vorbrüggen, Jan C., Pötzsch, Michael, Von Der Malsburg, Chrstoph, Eckes, Christian, Kefalea, Efthimia, Triesch, Jochen
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/762,806
• Time in Patent Office: 2,601 Days
• Field of Search: 345/419, 345/440, 345/473, 345/619, 345/646, 348/77, 348/169, 382/103, 382/115, 382/118, 382/154, 382/180, 382/190, 382/209, 382/217, 382/218, 382/260, 382/278, 382/279, 382/285
• US Class Current: 382/218
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 40/172 Classification, e.g. identification
• CPC Class Codes: G06V 40/28 Recognition of hand or arm movements, e.g. recognition of deaf sign language static hand signs G06V40/113

Abstract

A method for automatically recognizing one or more structures in digitized image date includes determining sub-jets of the image graph at the nodes defined by its structure. The sub-jets correspond to at least part of the determined sub-jets of the specific reference graph. The projection of the net-like structure of the specific reference varies until a graph comparison function, which compares the jets of the image graph with the corresponding jets of the specific graph, becomes optimal. The structure is associated with a reference image corresponding to the reference graph for which the graph comparison function is optimal, with respect to the optimal image graph determined for the reference graph.

Claims

1. A method for automatically recognizing one or more structures in digitized image data, comprising the following steps:

providing at least one reference graph comprising digitized reference image data of corresponding reference images, the reference graph or each reference graph comprising;

a net-like structure, the respective net-like structure being defined in that specific reference image data have assigned thereto nodes which are interconnected by links in a predetermined manner, and

jets, each node having a jet assigned thereto and each jet comprising at least one sub-jet which is determined by convolutions of at least one class of filter functions with different magnitudes and/or orientations with the reference image data of the corresponding reference image at the specific node, or by convolutions of at least one class of filter functions with different magnitudes and/or orientations with colour-segmented reference image data of the corresponding reference image at the specific node, or by colour information on the reference image data at said specific node, or by texture descriptions of the corresponding reference image at the specific node, said texture descriptions being gained by statistical methods, or by motion vectors at the specific node, said motion vectors being extracted from successive reference images,

determining an optimum image graph from the digitized image data for each reference graph, said optimum image graph representing for a specific reference graph the optimum adaptation to said reference graph and being determined by;

projecting the net-like structure of said specific reference graph into the image data whereby the structure of the image graph is defined, and

determining sub-jets of the image graph at the nodes defined by its structure, said sub-jets corresponding to at least part of the determined sub-jets of the specific reference graph, and

the projection of the net-like structure of said specific reference graph being varied until a graph comparison function which compares the jets of the image graph with the corresponding jets of said specific reference graph becomes optimal,

associating the structure or each structure with the reference image corresponding to the reference graph for which the graph comparison function is optimal with respect to the optimal image graph determined for said reference graph.

2. The method according to claim 1, wherein in addition

a plurality of reference graphs is provided, and

the reference graphs, which have net-like structures that are topologically identical, are combined to form a reference bunch graph, said reference bunch graph comprising:

a net-like structure defined by nodes which correspond to the nodes of the reference graphs and by links which are determined by averaging the corresponding links of the reference graphs, and

bunch jets, each of said bunch jets being composed of the sub-jets corresponding to the sub-jets at the respective nodes of the reference graphs combined in the reference bunch graph; and

an optimum image graph is determined for the or for each reference bunch graph, said optimum image graph representing for a specific reference bunch graph the optimum adaptation to said reference bunch graph and being determined by;

projecting the net-like structure of said specific reference bunch graph into the image data whereby the structure of the image graph is defined, and

determining sub-jets corresponding to at least part of the sub-jets which have been used for determining the sub-jets of the reference graphs underlying the specific reference bunch graph, and

the projection of the net-like structure of said specific reference bunch graph being varied until a graph comparison function which compares the jets of the image graph with the corresponding bunch jets of said specific reference bunch graph becomes optimal,

each sub-jet of the image graph being compared with the sub-jets in the corresponding bunch jet of said specific reference bunch graph;

and wherein finally

each structure is associated with the reference image corresponding to the reference graph or to the reference graph from the reference bunch graph or graphs for which the graph comparison function is optimal with respect to the optimal image graph determined for said reference graph.

3. The method according to claim 2, wherein only part of the reference graphs provided are combined so as to form one or a plurality of reference bunch graphs.

4. The method according to claim 2, wherein all the reference graphs provided are combined so as to form one or a plurality of reference bunch graphs.

5. The method according to one of the preceding claims, wherein the structure of the node-associated jets, which is determined by the sub-jets, depends on the respective node.

6. The method according to one of the claims 1 to 4, wherein the structure of the node-associated jets, which is determined by the sub-jets, is identical for all nodes.

7. The method according to one of the preceding claims, wherein a graph comparison function is used, which comprises a jet comparison function that takes into account the similarity of the jets corresponding to one another.

8. The method according to claim 7, wherein the graph comparison function additionally comprises a comparison function for the net-like structure, which takes into account the metric similarity of the image graph and the corresponding reference graph or the corresponding reference bunch graph.

9. The method according to claim 8, wherein the graph comparison function is defined as a weighted sum of the jet comparison function and of the comparison function for the net-like structure.

10. The method according to one of the claims 7 to 9, wherein the jet comparison function is defined as a function of single jet comparison functions of jets corresponding to one another.

11. The method according to claim 10, wherein the jet comparison function is defined as a weighted sum of the single jet comparison functions and/or as a weighted product of the single jet comparison functions.

12. The method according to claim 10 or 11, wherein sub-jets of the corresponding jets are taken into account for determining a single jet comparison, and wherein a single jet comparison function is defined as a function of sub-jet comparison functions.

13. The method according to claim 12, wherein the single jet comparison functions are defined as weighted sum of the sub-jet comparison functions and/or as a weighted product of the sub-jet comparison functions and/or as extremum of the sub-jet comparison functions.

14. The method according to one of the claims 7 to 13, wherein different node-dependent jet comparison functions and/or single jet comparison functions and/or sub-jet comparison functions are used.

15. The method according to one of the claims 7 to 9 in combination with claim 2, wherein the bunch jets of the reference bunch graph B^M are divided into sub-bunch jets b_k^M, and the jet comparison function between the sub-bunch jets b_k^M of the reference bunch graph and the corresponding sub-jets j_j′

of the image graph G′

for n nodes for m recursions is calculated according to the following formulae;

$S_{\mathrm{Jet}}<br><br>\left(B^M,G^{\mathrm{\prime <br><br>}}\right)=\underset{n}{\sum <br><br>}<br><br>{\mathrm{\omega <br><br>}}_n<br><br>S_n<br><br>\left(B_n^M,J_n^{\mathrm{\prime <br><br>}}\right),\mathrm{or}$$S_{\mathrm{Jet}}<br><br>\left(B^M,G^{\mathrm{\prime <br><br>}}\right)=\underset{n}{\prod <br><br>}<br><br>{\left(S_n<br><br>\left(B_n^M,J_n^{\mathrm{\prime <br><br>}}\right)\right)}^{{\mathrm{\omega <br><br>}}_n},$

wherein

ω

_n is a weighting factor for the n-th node n, and the comparison function S_n(B_n^M,J_n′

) for the n-th node of the reference bunch graph with the n-th node of the image graph is given by;

$S<br><br>\left(B^M,J^{\mathrm{\prime <br><br>}}\right)=\mathrm{\Omega <br><br>}<br><br>\left(\left\{S_{\mathrm{kl}}<br><br>\left(b_k^M,j_l^{\mathrm{\prime <br><br>}}\right)\right\}\right)=\text{;<br><br>}<br><br>\mathrm{\Omega <br><br>}<br><br>\left(M\right),\mathrm{with}$${\mathrm{\Omega <br><br>}}^{\left(0\right)}<br><br>\left(M\right)=\underset{i}{\sum <br><br>}<br><br>{\mathrm{\omega <br><br>}}_i<br><br>{{\mathrm{\Omega <br><br>}}_i}^{\left(1\right)}<br><br>\left(M_i^{\left(1\right)}\right),\mathrm{or}$${\mathrm{\Omega <br><br>}}^{\left(0\right)}<br><br>\left(M\right)=\underset{i}{\prod <br><br>}<br><br>{\left({\mathrm{\Omega <br><br>}}_i^{\left(1\right)}<br><br>\left(M_i^{\left(1\right)}\right)\right)}^{{\mathrm{\omega <br><br>}}_i},\mathrm{or}$${\mathrm{\Omega <br><br>}}^{\left(0\right)}<br><br>\left(M\right)=\underset{i}{\max }<br><br>\left\{{\mathrm{\omega <br><br>}}_i<br><br>{\mathrm{\Omega <br><br>}}_i^{\left(1\right)}<br><br>\left(M_i^{\left(1\right)}\right)\right\},\mathrm{or}$${\mathrm{\Omega <br><br>}}^{\left(0\right)}<br><br>\left(M\right)=\underset{i}{\min }<br><br>\left\{{\mathrm{\omega <br><br>}}_i<br><br>{\mathrm{\Omega <br><br>}}_i^{\left(1\right)}<br><br>\left(M_i^{\left(1\right)}\right)\right\},\mathrm{wherein}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i}{\bigcup <br><br>}<br><br>M_i^{\left(1\right)}=M$$\mathrm{\dots <br><br>}$${\mathrm{\Omega <br><br>}}_i^{\left(m-1\right)}<br><br>\left(M_i^{\left(m-1\right)}\right)=\underset{j}{\sum <br><br>}<br><br>{\mathrm{\omega <br><br>}}_j<br><br>{\mathrm{\Omega <br><br>}}_j^{\left(m\right)}<br><br>\left(M_j^{\left(m\right)}\right),\mathrm{or}<br><br>\text{\hspace{1em}<br><br>}$${\mathrm{\Omega <br><br>}}_i^{\left(m-1\right)}<br><br>\left(M_i^{\left(1\right)}\right)=\underset{j}{\prod <br><br>}<br><br>{\left({\mathrm{\Omega <br><br>}}_j^{\left(m\right)}<br><br>\left(M_j^{\left(m\right)}\right)\right)}^{{\mathrm{\omega <br><br>}}_j},\mathrm{or}$${\mathrm{\Omega <br><br>}}_i^{\left(m-1\right)}<br><br>\left(M_i^{\left(m-1\right)}\right)=\underset{j}{\max }<br><br>\left\{{\mathrm{\omega <br><br>}}_j^{\left(m\right)}<br><br>\left(M_j^{\left(m\right)}\right)\right\},\mathrm{or}$${\mathrm{\Omega <br><br>}}_i^{\left(m-1\right)}<br><br>\left(M_i^{\left(m-1\right)}\right)=\underset{j}{\min }<br><br>\left\{{\mathrm{\omega <br><br>}}_j<br><br>{\mathrm{\Omega <br><br>}}_j^{\left(m\right)}<br><br>\left(M_j^{\left(m\right)}\right)\right\},\mathrm{wherein}<br><br>\text{<br><br>}<br><br>\underset{j}{\bigcup <br><br>}<br><br>M_j^{\left(m\right)}=M_i^{\left(m-1\right)}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{with}$$S<br><br>\left(b^M,j^{\mathrm{\prime <br><br>}}\right)=\underset{n}{\sum <br><br>}<br><br>{\mathrm{\omega <br><br>}}_n<br><br>S_n<br><br>\left(j_n^M,j^{\mathrm{\prime <br><br>}}\right),\mathrm{or}$$S<br><br>\left(b^M,j^{\mathrm{\prime <br><br>}}\right)=\underset{n}{\prod <br><br>}<br><br>{\left(S_n<br><br>\left(j_n^M,j^{\mathrm{\prime <br><br>}}\right)\right)}^{{\mathrm{\omega <br><br>}}_n},\mathrm{or}$$S<br><br>\left(b^M,j^{\mathrm{\prime <br><br>}}\right)=\underset{n}{\max }<br><br>\left\{{\mathrm{\omega <br><br>}}_n<br><br>S_n<br><br>\left(j_n^M,j^{\mathrm{\prime <br><br>}}\right)\right\},\mathrm{or}$$S<br><br>\left(b^M,j^{\mathrm{\prime <br><br>}}\right)=\underset{n}{\min }<br><br>\left\{{\mathrm{\omega <br><br>}}_n<br><br>S_n<br><br>\left(j_n^M,j^{\mathrm{\prime <br><br>}}\right)\right\}.$

16. The method according to claim 15, wherein the sub-bunch jets of the reference bunch graph or graphs comprise only features which have been determined by convolutions of at least one class of filter functions with different magnitudes and/or orientations with the reference image data of the corresponding reference image at the specific node, or by convolutions of at least one class of filter functions with different magnitudes and/or orientations with colour-segmented reference image data of the corresponding reference image at said specific node, or by colour information on the reference image data at said specific node, or by texture descriptions of the corresponding reference image at said specific node, said texture descriptions being gained with statistical methods, or by motion vectors at said specific node, said motion vectors being extracted from successive reference images.

17. The method according to claim 15, wherein the sub-bunch jets of the reference bunch graph or graphs comprise only features which result from a reference graph.

18. The method according to one of the preceding claims, wherein, after the recognition of each structure, a step for determining the significance of the recognition is provided.

19. The method according to claim 18, wherein an estimator is used for determining the significance, said estimator taking into account the optimum graph comparison function as well as the non-optimum graph comparison function.

20. The method according to claim 19, wherein the distance of the values of the non-optimum graph comparison functions from the value of the optimum graph comparison function is used as an estimator.

21. The method according to one of the preceding claims, wherein, in addition, each structure is associated with the reference images corresponding to the reference graphs and/or the reference graphs from the reference bunch graphs for which the values of the graph comparison functions lie within a predetermined range.

22. The method according to one of the preceding claims, wherein the colour information comprises hue values and/or colour saturation values and/or intensity values determined from the reference image data and the image data, respectively.

23. The method according to one of the claims 1 to 22, wherein the step of providing the reference graphs and the reference bunch graphs, respectively, comprises fetching the reference graphs and the reference bunch graphs from a central and/or decentralized data base.

24. The method according to one of the preceding claims, wherein a regular grid is used as a net-like structure of the reference graph, the nodes and links of said regular grid defining rectangular meshes.

25. The method according to one of the claims 1 to 23, wherein an irregular grid is used as a net-like structure of the reference graph, the nodes and links of said irregular grid being adapted to the structure to be recognized.

26. The method according to claim 25, wherein the nodes are associated with characteristic points, so-called landmarks, of the structure to be recognized.

27. The method according to one of the preceding claims, wherein Gabor filter functions and/or Mallat filter functions are used as class of filter functions for convolution with the reference image data and image data, respectively.

28. The method according to one of the preceding claims, wherein Gabor filter functions and/or Mallat filter functions are used as class of filter functions for convolution with the colour-segmented reference image data and image data, respectively.

29. The method according to one of the preceding claims, wherein the projection of the net-like structure of the specific reference graph and/or the specific reference bunch graph comprises centering the reference graph and/or the specific reference bunch graph in the image.

30. The method according to claim 29, wherein the projection of the net-like structure of the specific reference graph and/or of the specific reference bunch graph comprises a displacement and/or rotation of the centered reference graph and of the centered reference bunch graph, respectively.

31. The method according to claim 29 or 30, wherein the projection of the net-like structure of the specific reference graph and/or of the specific reference bunch graph comprises scaling the centered reference graph and the centered reference bunch graph, respectively.

32. The method according to claim 31 in combination with claim 30, wherein the displacement and the scaling and the rotation of the centered reference graph and of the centered reference bunch graph, respectively, are carried out simultaneously.

33. The method according to one of the claim 30, wherein the displacement and/or the scaling and/or the rotation are determined on the basis of a comparison between the image graph and the corresponding reference graph and/or the corresponding reference bunch graph.

34. The method according to one of the claims 29 to 32, wherein the projection of the net-like structure comprises local distortions of the centered reference graph.

35. The method according to claim 34, wherein a local distortion is caused by locally displacing a respective node of the centered reference graph.