Abstract

We describe a new method to register surface data measured by optical three-dimensional (3-D) sensors from various views of an object. With our method, complete 3-D models of objects can be generated without user interaction. Circumferential acquisition of 3-D objects is done by taking several views from different directions. To generate a complete 3-D-model, the views must be aligned with each other. This process is called registration and is commonly done interactively by searching for so-called corresponding points in the different views and by use of these points to calculate the appropriate rotation and translation. Our approach is based on automatically finding points that are eye catching or salient compared with other surface points. We derive a quantitative measure of point salience and a feature definition for free-form surfaces by introducing a concept to measure pragmatic information. Experiments confirm that our salient points can be robustly located on general free-form surfaces, even if there are no corners or edges. Furthermore, the neighborhoods of the salient points are highly distinguishable from each other. This results in a large reduction of the complexity of the subsequent geometric matching. The computing time is only a few seconds. We present results from various fields of application.

© 2006 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. G. Guidi, J.-A. Beraldin, and C. Atzeni, "High-accuracy 3D modeling of cultural heritage: the digitizing of Donatello's Maddalena," IEEE Trans. Image Process. 13, 370-380 (2004).
    [CrossRef] [PubMed]
  2. C. Brenner, J. Böhm, and J. Gühring, "Experimental measurement system for industrial inspection of 3D parts," in Machine Vision Systems for Inspection and Metrology VII, B. G. Batchelor, J. W. Miller, S. S. Solomon, eds., Proc. SPIE 3521, 237-247 (1998).
    [CrossRef]
  3. M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.
  4. V. Blanz and T. Vetter, "Face recognition based on fitting a 3D morphable model," IEEE Trans. Pattern Anal. Mach. Intell. 25, 1063-1074 (2003).
    [CrossRef]
  5. T. Kanade, P. Rander, and P. J. Narayanan, "Virtualized reality: constructing virtual worlds from real scenes," IEEE Multimedia 4, 34-47 (1997).
    [CrossRef]
  6. I. Söderkvist, "Introductory overview of surface reconstruction methods," Research Report 10 (Department of Mathematics, Lulea University, S-97187 Lulea, Sweden, 1999), www.sm.luth.se/∼inge/publications/surfrec.ps.
  7. S. Karbacher, N. Schön, H. Schönfeld, and G. Häusler, "Digitizing 3D objects for reverse engineering and virtual reality," in Principles of 3D Image Analysis and Synthesis, B.Girod, G.Greiner, and H.Niemann, eds. (Kluwer Academic, 2000), Chap. 8.1, pp. 336-347.
  8. S. Karbacher, X. Laboureux, N. Schön, and G. Häusler, "Processing range data for reverse engineering and virtual reality," in Proceedings of Third International Conference on 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 2001), pp. 314-321.
    [CrossRef]
  9. M. Gruber and G. Häusler, "Simple, robust and accurate phase-measuring triangulation," Optik 89, 118-122 (1992).
  10. K. Veit and G. Häusler, "Metrical calibration of a phase measuring triangulation sensor," in Vision, Modeling, and Visualization 2000, B.Girod, G.Greiner, H.Niemann, and H.-P.Seidel, eds. (IEEE Signal Processing Society, 2000), pp. 33-38.
  11. C. Wagner and G. Häusler, "Information theoretical optimization for optical range sensors," Appl. Opt. 42, 5418-5426 (2003).
    [CrossRef] [PubMed]
  12. P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
    [CrossRef] [PubMed]
  13. S. Karbacher and G. Häusler, "New approach for the modeling and smoothing of scattered 3D data," in Three Dimensional Image Capture and Applications, R. N. Ellson and J. H. Nurre, eds., Proc. SPIE 3313, 168-177 (1998).
    [CrossRef]
  14. N. Schön, P. Gall, and G. Häusler, "Three dimensional acquisition of colored objects," in Workshop Color Image Processing (German Society of Color Science and Application, 2002), pp. 63-70.
  15. P. J. Besl and H. D. McKay, "A method for registration of 3-D shapes," IEEE Trans. Pattern Anal. Mach. Intell. 14, 239-256 (1992).
    [CrossRef]
  16. N. Diehl and H. Burkhardt, "Motion estimation in image sequences," in International Workshop on High Precision Navigation, K. Linkwitz and U. Hangleiter, eds. (Springer, 1989).
    [CrossRef]
  17. X. Laboureux and G. Häusler, "Localization and registration of three-dimensional objects in space--where are the limits?" Appl. Opt. 40, 5206-5216 (2001).
    [CrossRef]
  18. D. Gernert, "Pragmatic information as a unifying concept," in Information. New Questions to a Multidisciplinary Concept, K.Kornwachs and K.Jacoby, eds. (Akademie-Verlag, 1996), pp. 147-162.
  19. C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 379-423, 623-656 (1948).
  20. J. B. A. Maintz and M. A. Viergever, "A survey of medical image registration," Med. Image Anal. 2, 1-36 (1998).
    [CrossRef]
  21. S. Winkelbach, M. Rilk, C. Schönfelder, and F. M. Wahl, "Fast random sample matching of 3d fragments," in Pattern Recognition (DAGM Symposium), C.E.Rasmussen, H.H.Bülthoff, B.Schölkopf, and M.A.Giese, eds., Vol. 3175 of Lecture Notes in Computer Sciences, (Springer, 2004), pp. 129-136.
    [CrossRef]
  22. R. Capurro and B. Hjørland, "The concept of information," Annu. Rev. Inf. Sci. Technol. 37, 343-411 (2003), http://www.capurro.de/infoconcept.html.
    [CrossRef]
  23. S. Siggelkow and H. Burkhardt, "Invariant feature histograms for texture classification," in Joint Conference on Information Sciences (JCIS), Vol. 4, pp. 230-233 (Research Triangle Park, North Carolina, 1998).
  24. A. E. Johnson and M. Hebert, "Surface registration by matching oriented points," in International Conference on Recent Advances in 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 1997), pp. 121-128.
  25. R. J. Campbell and P. J. Flynn, "A survey of free-form object representation and recognition techniques," Comput. Vision Image Understand. 81, 166-210 (2001).
    [CrossRef]
  26. L. G. Shapiro and R. M. Haralick, "Relational matching," Appl. Opt. 26, 1845-1851 (1987).
    [CrossRef] [PubMed]
  27. G. R. Putland, "Modeling of horns and enclosures for loudspeakers," Ph.D. dissertation (Department of Electrical and Computer Engineering, University of Queensland, 1995), http://www.users.bigpond.com/putland/phd/thes.ps.gz.
  28. C. F. v. Weizsäcker, Aufbau der Physik (Hanser, München, 1985), p. 171.
  29. S. Siggelkow and H. Burkhardt, "Image retrieval based on local invariant features," in IASTED International Conference on Signal and Image Processing (International Association of Science and Technology for Development, 1998), pp. 369-373.
  30. T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, 1991), p. 18.
    [CrossRef]
  31. V. Gaede and O. Günther, "Multidimensional access methods," ACM (Assoc. Comput. Mach.) Comput. Surveys 30, 170-231 (1998).
  32. B. K. P. Horn, "Closed-form solution of absolute orientation using unit quaternions," J. Opt. Soc. Am. A 4, 629-642 (1987).
    [CrossRef]
  33. N. Schön and G. Häusler, "Automatic coarse registration of 3D Surfaces," in Vision, Modeling, and Visualization 2005, G.Greiner, J.Hornegger, H.Niemann, and M.Stamminger, eds. (Akademische Verlagsgesellschaft, 2005), pp. 479-486.
  34. N. Schön, B. M., T. Maier, E. Nkenke, F. W. Neukam, and G. Häusler, "Information-soptimierte Merkmale zur Grobregistrierung von Freiform-Flächen," in Bildverarbeitung für die Medizin 2004, T. Tolxdorff, J. Braun, H. Handels, A. Horsch, and H.-P. Meinzer, eds., Informatik Aktuell (Springer, 2004).
    [CrossRef]
  35. T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.
  36. 3D-Shape GmbH, Henkestrasse 91, D-91052 Erlangen, Germany; http://www.3d-shape.com.
  37. "Sonderforschungsbereich 603, Modellbasierte Analyse und Visualisierung komplexer Szenen und Sensordaten," http://sfb-603.uni-erlangen.de.

2004

G. Guidi, J.-A. Beraldin, and C. Atzeni, "High-accuracy 3D modeling of cultural heritage: the digitizing of Donatello's Maddalena," IEEE Trans. Image Process. 13, 370-380 (2004).
[CrossRef] [PubMed]

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

2003

V. Blanz and T. Vetter, "Face recognition based on fitting a 3D morphable model," IEEE Trans. Pattern Anal. Mach. Intell. 25, 1063-1074 (2003).
[CrossRef]

R. Capurro and B. Hjørland, "The concept of information," Annu. Rev. Inf. Sci. Technol. 37, 343-411 (2003), http://www.capurro.de/infoconcept.html.
[CrossRef]

C. Wagner and G. Häusler, "Information theoretical optimization for optical range sensors," Appl. Opt. 42, 5418-5426 (2003).
[CrossRef] [PubMed]

2001

X. Laboureux and G. Häusler, "Localization and registration of three-dimensional objects in space--where are the limits?" Appl. Opt. 40, 5206-5216 (2001).
[CrossRef]

R. J. Campbell and P. J. Flynn, "A survey of free-form object representation and recognition techniques," Comput. Vision Image Understand. 81, 166-210 (2001).
[CrossRef]

1998

V. Gaede and O. Günther, "Multidimensional access methods," ACM (Assoc. Comput. Mach.) Comput. Surveys 30, 170-231 (1998).

J. B. A. Maintz and M. A. Viergever, "A survey of medical image registration," Med. Image Anal. 2, 1-36 (1998).
[CrossRef]

C. Brenner, J. Böhm, and J. Gühring, "Experimental measurement system for industrial inspection of 3D parts," in Machine Vision Systems for Inspection and Metrology VII, B. G. Batchelor, J. W. Miller, S. S. Solomon, eds., Proc. SPIE 3521, 237-247 (1998).
[CrossRef]

S. Karbacher and G. Häusler, "New approach for the modeling and smoothing of scattered 3D data," in Three Dimensional Image Capture and Applications, R. N. Ellson and J. H. Nurre, eds., Proc. SPIE 3313, 168-177 (1998).
[CrossRef]

1997

T. Kanade, P. Rander, and P. J. Narayanan, "Virtualized reality: constructing virtual worlds from real scenes," IEEE Multimedia 4, 34-47 (1997).
[CrossRef]

1992

M. Gruber and G. Häusler, "Simple, robust and accurate phase-measuring triangulation," Optik 89, 118-122 (1992).

P. J. Besl and H. D. McKay, "A method for registration of 3-D shapes," IEEE Trans. Pattern Anal. Mach. Intell. 14, 239-256 (1992).
[CrossRef]

1987

1948

C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 379-423, 623-656 (1948).

Atzeni, C.

G. Guidi, J.-A. Beraldin, and C. Atzeni, "High-accuracy 3D modeling of cultural heritage: the digitizing of Donatello's Maddalena," IEEE Trans. Image Process. 13, 370-380 (2004).
[CrossRef] [PubMed]

Bauer, M.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Benz, M.

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

Beraldin, J.-A.

G. Guidi, J.-A. Beraldin, and C. Atzeni, "High-accuracy 3D modeling of cultural heritage: the digitizing of Donatello's Maddalena," IEEE Trans. Image Process. 13, 370-380 (2004).
[CrossRef] [PubMed]

Besl, P. J.

P. J. Besl and H. D. McKay, "A method for registration of 3-D shapes," IEEE Trans. Pattern Anal. Mach. Intell. 14, 239-256 (1992).
[CrossRef]

Blanz, V.

V. Blanz and T. Vetter, "Face recognition based on fitting a 3D morphable model," IEEE Trans. Pattern Anal. Mach. Intell. 25, 1063-1074 (2003).
[CrossRef]

Böhm, J.

C. Brenner, J. Böhm, and J. Gühring, "Experimental measurement system for industrial inspection of 3D parts," in Machine Vision Systems for Inspection and Metrology VII, B. G. Batchelor, J. W. Miller, S. S. Solomon, eds., Proc. SPIE 3521, 237-247 (1998).
[CrossRef]

Brenner, C.

C. Brenner, J. Böhm, and J. Gühring, "Experimental measurement system for industrial inspection of 3D parts," in Machine Vision Systems for Inspection and Metrology VII, B. G. Batchelor, J. W. Miller, S. S. Solomon, eds., Proc. SPIE 3521, 237-247 (1998).
[CrossRef]

Burkhardt, H.

S. Siggelkow and H. Burkhardt, "Invariant feature histograms for texture classification," in Joint Conference on Information Sciences (JCIS), Vol. 4, pp. 230-233 (Research Triangle Park, North Carolina, 1998).

N. Diehl and H. Burkhardt, "Motion estimation in image sequences," in International Workshop on High Precision Navigation, K. Linkwitz and U. Hangleiter, eds. (Springer, 1989).
[CrossRef]

S. Siggelkow and H. Burkhardt, "Image retrieval based on local invariant features," in IASTED International Conference on Signal and Image Processing (International Association of Science and Technology for Development, 1998), pp. 369-373.

Campbell, R. J.

R. J. Campbell and P. J. Flynn, "A survey of free-form object representation and recognition techniques," Comput. Vision Image Understand. 81, 166-210 (2001).
[CrossRef]

Capurro, R.

R. Capurro and B. Hjørland, "The concept of information," Annu. Rev. Inf. Sci. Technol. 37, 343-411 (2003), http://www.capurro.de/infoconcept.html.
[CrossRef]

Cover, T. M.

T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, 1991), p. 18.
[CrossRef]

Diehl, N.

N. Diehl and H. Burkhardt, "Motion estimation in image sequences," in International Workshop on High Precision Navigation, K. Linkwitz and U. Hangleiter, eds. (Springer, 1989).
[CrossRef]

Fahlbusch, R.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Flynn, P. J.

R. J. Campbell and P. J. Flynn, "A survey of free-form object representation and recognition techniques," Comput. Vision Image Understand. 81, 166-210 (2001).
[CrossRef]

Gaede, V.

V. Gaede and O. Günther, "Multidimensional access methods," ACM (Assoc. Comput. Mach.) Comput. Surveys 30, 170-231 (1998).

Gall, P.

N. Schön, P. Gall, and G. Häusler, "Three dimensional acquisition of colored objects," in Workshop Color Image Processing (German Society of Color Science and Application, 2002), pp. 63-70.

Ganslandt, O.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Gernert, D.

D. Gernert, "Pragmatic information as a unifying concept," in Information. New Questions to a Multidisciplinary Concept, K.Kornwachs and K.Jacoby, eds. (Akademie-Verlag, 1996), pp. 147-162.

Greiner, G.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Gruber, M.

M. Gruber and G. Häusler, "Simple, robust and accurate phase-measuring triangulation," Optik 89, 118-122 (1992).

Gühring, J.

C. Brenner, J. Böhm, and J. Gühring, "Experimental measurement system for industrial inspection of 3D parts," in Machine Vision Systems for Inspection and Metrology VII, B. G. Batchelor, J. W. Miller, S. S. Solomon, eds., Proc. SPIE 3521, 237-247 (1998).
[CrossRef]

Guidi, G.

G. Guidi, J.-A. Beraldin, and C. Atzeni, "High-accuracy 3D modeling of cultural heritage: the digitizing of Donatello's Maddalena," IEEE Trans. Image Process. 13, 370-380 (2004).
[CrossRef] [PubMed]

Günther, O.

V. Gaede and O. Günther, "Multidimensional access methods," ACM (Assoc. Comput. Mach.) Comput. Surveys 30, 170-231 (1998).

Haralick, R. M.

Hastreiter, P.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Häusler, G.

C. Wagner and G. Häusler, "Information theoretical optimization for optical range sensors," Appl. Opt. 42, 5418-5426 (2003).
[CrossRef] [PubMed]

X. Laboureux and G. Häusler, "Localization and registration of three-dimensional objects in space--where are the limits?" Appl. Opt. 40, 5206-5216 (2001).
[CrossRef]

S. Karbacher and G. Häusler, "New approach for the modeling and smoothing of scattered 3D data," in Three Dimensional Image Capture and Applications, R. N. Ellson and J. H. Nurre, eds., Proc. SPIE 3313, 168-177 (1998).
[CrossRef]

M. Gruber and G. Häusler, "Simple, robust and accurate phase-measuring triangulation," Optik 89, 118-122 (1992).

S. Karbacher, N. Schön, H. Schönfeld, and G. Häusler, "Digitizing 3D objects for reverse engineering and virtual reality," in Principles of 3D Image Analysis and Synthesis, B.Girod, G.Greiner, and H.Niemann, eds. (Kluwer Academic, 2000), Chap. 8.1, pp. 336-347.

N. Schön, P. Gall, and G. Häusler, "Three dimensional acquisition of colored objects," in Workshop Color Image Processing (German Society of Color Science and Application, 2002), pp. 63-70.

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

K. Veit and G. Häusler, "Metrical calibration of a phase measuring triangulation sensor," in Vision, Modeling, and Visualization 2000, B.Girod, G.Greiner, H.Niemann, and H.-P.Seidel, eds. (IEEE Signal Processing Society, 2000), pp. 33-38.

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

N. Schön and G. Häusler, "Automatic coarse registration of 3D Surfaces," in Vision, Modeling, and Visualization 2005, G.Greiner, J.Hornegger, H.Niemann, and M.Stamminger, eds. (Akademische Verlagsgesellschaft, 2005), pp. 479-486.

S. Karbacher, X. Laboureux, N. Schön, and G. Häusler, "Processing range data for reverse engineering and virtual reality," in Proceedings of Third International Conference on 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 2001), pp. 314-321.
[CrossRef]

N. Schön, B. M., T. Maier, E. Nkenke, F. W. Neukam, and G. Häusler, "Information-soptimierte Merkmale zur Grobregistrierung von Freiform-Flächen," in Bildverarbeitung für die Medizin 2004, T. Tolxdorff, J. Braun, H. Handels, A. Horsch, and H.-P. Meinzer, eds., Informatik Aktuell (Springer, 2004).
[CrossRef]

Hebert, M.

A. E. Johnson and M. Hebert, "Surface registration by matching oriented points," in International Conference on Recent Advances in 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 1997), pp. 121-128.

Hjørland, B.

R. Capurro and B. Hjørland, "The concept of information," Annu. Rev. Inf. Sci. Technol. 37, 343-411 (2003), http://www.capurro.de/infoconcept.html.
[CrossRef]

Horn, B. K. P.

Johnson, A. E.

A. E. Johnson and M. Hebert, "Surface registration by matching oriented points," in International Conference on Recent Advances in 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 1997), pp. 121-128.

Kanade, T.

T. Kanade, P. Rander, and P. J. Narayanan, "Virtualized reality: constructing virtual worlds from real scenes," IEEE Multimedia 4, 34-47 (1997).
[CrossRef]

Karbacher, S.

S. Karbacher and G. Häusler, "New approach for the modeling and smoothing of scattered 3D data," in Three Dimensional Image Capture and Applications, R. N. Ellson and J. H. Nurre, eds., Proc. SPIE 3313, 168-177 (1998).
[CrossRef]

S. Karbacher, N. Schön, H. Schönfeld, and G. Häusler, "Digitizing 3D objects for reverse engineering and virtual reality," in Principles of 3D Image Analysis and Synthesis, B.Girod, G.Greiner, and H.Niemann, eds. (Kluwer Academic, 2000), Chap. 8.1, pp. 336-347.

S. Karbacher, X. Laboureux, N. Schön, and G. Häusler, "Processing range data for reverse engineering and virtual reality," in Proceedings of Third International Conference on 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 2001), pp. 314-321.
[CrossRef]

Laboureux, X.

X. Laboureux and G. Häusler, "Localization and registration of three-dimensional objects in space--where are the limits?" Appl. Opt. 40, 5206-5216 (2001).
[CrossRef]

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

S. Karbacher, X. Laboureux, N. Schön, and G. Häusler, "Processing range data for reverse engineering and virtual reality," in Proceedings of Third International Conference on 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 2001), pp. 314-321.
[CrossRef]

Maier, B. M.

N. Schön, B. M., T. Maier, E. Nkenke, F. W. Neukam, and G. Häusler, "Information-soptimierte Merkmale zur Grobregistrierung von Freiform-Flächen," in Bildverarbeitung für die Medizin 2004, T. Tolxdorff, J. Braun, H. Handels, A. Horsch, and H.-P. Meinzer, eds., Informatik Aktuell (Springer, 2004).
[CrossRef]

Maier, T.

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

Maintz, J. B. A.

J. B. A. Maintz and M. A. Viergever, "A survey of medical image registration," Med. Image Anal. 2, 1-36 (1998).
[CrossRef]

McKay, H. D.

P. J. Besl and H. D. McKay, "A method for registration of 3-D shapes," IEEE Trans. Pattern Anal. Mach. Intell. 14, 239-256 (1992).
[CrossRef]

Narayanan, P. J.

T. Kanade, P. Rander, and P. J. Narayanan, "Virtualized reality: constructing virtual worlds from real scenes," IEEE Multimedia 4, 34-47 (1997).
[CrossRef]

Neukam, F.

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

Neukam, F. W.

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

N. Schön, B. M., T. Maier, E. Nkenke, F. W. Neukam, and G. Häusler, "Information-soptimierte Merkmale zur Grobregistrierung von Freiform-Flächen," in Bildverarbeitung für die Medizin 2004, T. Tolxdorff, J. Braun, H. Handels, A. Horsch, and H.-P. Meinzer, eds., Informatik Aktuell (Springer, 2004).
[CrossRef]

Nimsky, C.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Nkenke, E.

N. Schön, B. M., T. Maier, E. Nkenke, F. W. Neukam, and G. Häusler, "Information-soptimierte Merkmale zur Grobregistrierung von Freiform-Flächen," in Bildverarbeitung für die Medizin 2004, T. Tolxdorff, J. Braun, H. Handels, A. Horsch, and H.-P. Meinzer, eds., Informatik Aktuell (Springer, 2004).
[CrossRef]

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

Putland, G. R.

G. R. Putland, "Modeling of horns and enclosures for loudspeakers," Ph.D. dissertation (Department of Electrical and Computer Engineering, University of Queensland, 1995), http://www.users.bigpond.com/putland/phd/thes.ps.gz.

Rander, P.

T. Kanade, P. Rander, and P. J. Narayanan, "Virtualized reality: constructing virtual worlds from real scenes," IEEE Multimedia 4, 34-47 (1997).
[CrossRef]

Rezk-Salama, C.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Rilk, M.

S. Winkelbach, M. Rilk, C. Schönfelder, and F. M. Wahl, "Fast random sample matching of 3d fragments," in Pattern Recognition (DAGM Symposium), C.E.Rasmussen, H.H.Bülthoff, B.Schölkopf, and M.A.Giese, eds., Vol. 3175 of Lecture Notes in Computer Sciences, (Springer, 2004), pp. 129-136.
[CrossRef]

Schön, N.

N. Schön, B. M., T. Maier, E. Nkenke, F. W. Neukam, and G. Häusler, "Information-soptimierte Merkmale zur Grobregistrierung von Freiform-Flächen," in Bildverarbeitung für die Medizin 2004, T. Tolxdorff, J. Braun, H. Handels, A. Horsch, and H.-P. Meinzer, eds., Informatik Aktuell (Springer, 2004).
[CrossRef]

N. Schön and G. Häusler, "Automatic coarse registration of 3D Surfaces," in Vision, Modeling, and Visualization 2005, G.Greiner, J.Hornegger, H.Niemann, and M.Stamminger, eds. (Akademische Verlagsgesellschaft, 2005), pp. 479-486.

S. Karbacher, X. Laboureux, N. Schön, and G. Häusler, "Processing range data for reverse engineering and virtual reality," in Proceedings of Third International Conference on 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 2001), pp. 314-321.
[CrossRef]

S. Karbacher, N. Schön, H. Schönfeld, and G. Häusler, "Digitizing 3D objects for reverse engineering and virtual reality," in Principles of 3D Image Analysis and Synthesis, B.Girod, G.Greiner, and H.Niemann, eds. (Kluwer Academic, 2000), Chap. 8.1, pp. 336-347.

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

N. Schön, P. Gall, and G. Häusler, "Three dimensional acquisition of colored objects," in Workshop Color Image Processing (German Society of Color Science and Application, 2002), pp. 63-70.

Schönfeld, H.

S. Karbacher, N. Schön, H. Schönfeld, and G. Häusler, "Digitizing 3D objects for reverse engineering and virtual reality," in Principles of 3D Image Analysis and Synthesis, B.Girod, G.Greiner, and H.Niemann, eds. (Kluwer Academic, 2000), Chap. 8.1, pp. 336-347.

Schönfelder, C.

S. Winkelbach, M. Rilk, C. Schönfelder, and F. M. Wahl, "Fast random sample matching of 3d fragments," in Pattern Recognition (DAGM Symposium), C.E.Rasmussen, H.H.Bülthoff, B.Schölkopf, and M.A.Giese, eds., Vol. 3175 of Lecture Notes in Computer Sciences, (Springer, 2004), pp. 129-136.
[CrossRef]

Seeger, S.

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

Shannon, C. E.

C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 379-423, 623-656 (1948).

Shapiro, L. G.

Siggelkow, S.

S. Siggelkow and H. Burkhardt, "Image retrieval based on local invariant features," in IASTED International Conference on Signal and Image Processing (International Association of Science and Technology for Development, 1998), pp. 369-373.

S. Siggelkow and H. Burkhardt, "Invariant feature histograms for texture classification," in Joint Conference on Information Sciences (JCIS), Vol. 4, pp. 230-233 (Research Triangle Park, North Carolina, 1998).

Söderkvist, I.

I. Söderkvist, "Introductory overview of surface reconstruction methods," Research Report 10 (Department of Mathematics, Lulea University, S-97187 Lulea, Sweden, 1999), www.sm.luth.se/∼inge/publications/surfrec.ps.

Soza, G.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

Thomas, J. A.

T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, 1991), p. 18.
[CrossRef]

Veit, K.

K. Veit and G. Häusler, "Metrical calibration of a phase measuring triangulation sensor," in Vision, Modeling, and Visualization 2000, B.Girod, G.Greiner, H.Niemann, and H.-P.Seidel, eds. (IEEE Signal Processing Society, 2000), pp. 33-38.

Vetter, T.

V. Blanz and T. Vetter, "Face recognition based on fitting a 3D morphable model," IEEE Trans. Pattern Anal. Mach. Intell. 25, 1063-1074 (2003).
[CrossRef]

Viergever, M. A.

J. B. A. Maintz and M. A. Viergever, "A survey of medical image registration," Med. Image Anal. 2, 1-36 (1998).
[CrossRef]

Vogt, F.

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

Wagner, C.

Wahl, F. M.

S. Winkelbach, M. Rilk, C. Schönfelder, and F. M. Wahl, "Fast random sample matching of 3d fragments," in Pattern Recognition (DAGM Symposium), C.E.Rasmussen, H.H.Bülthoff, B.Schölkopf, and M.A.Giese, eds., Vol. 3175 of Lecture Notes in Computer Sciences, (Springer, 2004), pp. 129-136.
[CrossRef]

Weizsäcker, C. F. v.

C. F. v. Weizsäcker, Aufbau der Physik (Hanser, München, 1985), p. 171.

Winkelbach, S.

S. Winkelbach, M. Rilk, C. Schönfelder, and F. M. Wahl, "Fast random sample matching of 3d fragments," in Pattern Recognition (DAGM Symposium), C.E.Rasmussen, H.H.Bülthoff, B.Schölkopf, and M.A.Giese, eds., Vol. 3175 of Lecture Notes in Computer Sciences, (Springer, 2004), pp. 129-136.
[CrossRef]

ACM

V. Gaede and O. Günther, "Multidimensional access methods," ACM (Assoc. Comput. Mach.) Comput. Surveys 30, 170-231 (1998).

Annu. Rev. Inf. Sci. Technol.

R. Capurro and B. Hjørland, "The concept of information," Annu. Rev. Inf. Sci. Technol. 37, 343-411 (2003), http://www.capurro.de/infoconcept.html.
[CrossRef]

Appl. Opt.

Bell Syst. Tech. J.

C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 379-423, 623-656 (1948).

Comput. Vision Image Understand.

R. J. Campbell and P. J. Flynn, "A survey of free-form object representation and recognition techniques," Comput. Vision Image Understand. 81, 166-210 (2001).
[CrossRef]

IEEE Multimedia

T. Kanade, P. Rander, and P. J. Narayanan, "Virtualized reality: constructing virtual worlds from real scenes," IEEE Multimedia 4, 34-47 (1997).
[CrossRef]

IEEE Trans. Image Process.

G. Guidi, J.-A. Beraldin, and C. Atzeni, "High-accuracy 3D modeling of cultural heritage: the digitizing of Donatello's Maddalena," IEEE Trans. Image Process. 13, 370-380 (2004).
[CrossRef] [PubMed]

IEEE Trans. Pattern Anal. Mach. Intell.

V. Blanz and T. Vetter, "Face recognition based on fitting a 3D morphable model," IEEE Trans. Pattern Anal. Mach. Intell. 25, 1063-1074 (2003).
[CrossRef]

P. J. Besl and H. D. McKay, "A method for registration of 3-D shapes," IEEE Trans. Pattern Anal. Mach. Intell. 14, 239-256 (1992).
[CrossRef]

J. Opt. Soc. Am. A

Med. Image Anal.

P. Hastreiter, C. Rezk-Salama, G. Soza, M. Bauer, G. Greiner, R. Fahlbusch, O. Ganslandt, and C. Nimsky, "Strategies for brain shift evaluation," Med. Image Anal. 8, 447-464 (2004).
[CrossRef] [PubMed]

J. B. A. Maintz and M. A. Viergever, "A survey of medical image registration," Med. Image Anal. 2, 1-36 (1998).
[CrossRef]

Optik

M. Gruber and G. Häusler, "Simple, robust and accurate phase-measuring triangulation," Optik 89, 118-122 (1992).

Proc. SPIE

C. Brenner, J. Böhm, and J. Gühring, "Experimental measurement system for industrial inspection of 3D parts," in Machine Vision Systems for Inspection and Metrology VII, B. G. Batchelor, J. W. Miller, S. S. Solomon, eds., Proc. SPIE 3521, 237-247 (1998).
[CrossRef]

S. Karbacher and G. Häusler, "New approach for the modeling and smoothing of scattered 3D data," in Three Dimensional Image Capture and Applications, R. N. Ellson and J. H. Nurre, eds., Proc. SPIE 3313, 168-177 (1998).
[CrossRef]

Other

N. Schön, P. Gall, and G. Häusler, "Three dimensional acquisition of colored objects," in Workshop Color Image Processing (German Society of Color Science and Application, 2002), pp. 63-70.

S. Winkelbach, M. Rilk, C. Schönfelder, and F. M. Wahl, "Fast random sample matching of 3d fragments," in Pattern Recognition (DAGM Symposium), C.E.Rasmussen, H.H.Bülthoff, B.Schölkopf, and M.A.Giese, eds., Vol. 3175 of Lecture Notes in Computer Sciences, (Springer, 2004), pp. 129-136.
[CrossRef]

S. Siggelkow and H. Burkhardt, "Invariant feature histograms for texture classification," in Joint Conference on Information Sciences (JCIS), Vol. 4, pp. 230-233 (Research Triangle Park, North Carolina, 1998).

A. E. Johnson and M. Hebert, "Surface registration by matching oriented points," in International Conference on Recent Advances in 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 1997), pp. 121-128.

M. Benz, X. Laboureux, T. Maier, E. Nkenke, S. Seeger, F. Neukam, and G. Häusler, "The symmetry of faces," in Proceedings of Vision, Modeling, and Visualization, G.Girod, H.Niemann, T.Ertl, B.Girod, and H.-P.Seidel, eds. (Akademische Verlagsgesellschaft, 2002), pp. 43-50.

K. Veit and G. Häusler, "Metrical calibration of a phase measuring triangulation sensor," in Vision, Modeling, and Visualization 2000, B.Girod, G.Greiner, H.Niemann, and H.-P.Seidel, eds. (IEEE Signal Processing Society, 2000), pp. 33-38.

D. Gernert, "Pragmatic information as a unifying concept," in Information. New Questions to a Multidisciplinary Concept, K.Kornwachs and K.Jacoby, eds. (Akademie-Verlag, 1996), pp. 147-162.

I. Söderkvist, "Introductory overview of surface reconstruction methods," Research Report 10 (Department of Mathematics, Lulea University, S-97187 Lulea, Sweden, 1999), www.sm.luth.se/∼inge/publications/surfrec.ps.

S. Karbacher, N. Schön, H. Schönfeld, and G. Häusler, "Digitizing 3D objects for reverse engineering and virtual reality," in Principles of 3D Image Analysis and Synthesis, B.Girod, G.Greiner, and H.Niemann, eds. (Kluwer Academic, 2000), Chap. 8.1, pp. 336-347.

S. Karbacher, X. Laboureux, N. Schön, and G. Häusler, "Processing range data for reverse engineering and virtual reality," in Proceedings of Third International Conference on 3-D Digital Imaging and Modeling (Institute of Electrical and Electronics Engineers, 2001), pp. 314-321.
[CrossRef]

N. Diehl and H. Burkhardt, "Motion estimation in image sequences," in International Workshop on High Precision Navigation, K. Linkwitz and U. Hangleiter, eds. (Springer, 1989).
[CrossRef]

G. R. Putland, "Modeling of horns and enclosures for loudspeakers," Ph.D. dissertation (Department of Electrical and Computer Engineering, University of Queensland, 1995), http://www.users.bigpond.com/putland/phd/thes.ps.gz.

C. F. v. Weizsäcker, Aufbau der Physik (Hanser, München, 1985), p. 171.

S. Siggelkow and H. Burkhardt, "Image retrieval based on local invariant features," in IASTED International Conference on Signal and Image Processing (International Association of Science and Technology for Development, 1998), pp. 369-373.

T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, 1991), p. 18.
[CrossRef]

N. Schön and G. Häusler, "Automatic coarse registration of 3D Surfaces," in Vision, Modeling, and Visualization 2005, G.Greiner, J.Hornegger, H.Niemann, and M.Stamminger, eds. (Akademische Verlagsgesellschaft, 2005), pp. 479-486.

N. Schön, B. M., T. Maier, E. Nkenke, F. W. Neukam, and G. Häusler, "Information-soptimierte Merkmale zur Grobregistrierung von Freiform-Flächen," in Bildverarbeitung für die Medizin 2004, T. Tolxdorff, J. Braun, H. Handels, A. Horsch, and H.-P. Meinzer, eds., Informatik Aktuell (Springer, 2004).
[CrossRef]

T. Maier, M. Benz, N. Schön, E. Nkenke, F. W. Neukam, F. Vogt, and G. Häusler, "Automatic coarse registration of 3D surface data in oral and maxillofacial surgery," in Perspective in Image-Guided Surgery, T.M.Buzug and T.C.Lueth, eds. (RheinAhrCampus Remagen, 2004), pp. 51-58.

3D-Shape GmbH, Henkestrasse 91, D-91052 Erlangen, Germany; http://www.3d-shape.com.

"Sonderforschungsbereich 603, Modellbasierte Analyse und Visualisierung komplexer Szenen und Sensordaten," http://sfb-603.uni-erlangen.de.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (13)

Fig. 1
Fig. 1

(Color online) Two surface views with salient points for the human visual system (marked by an x). Three corresponding point pairs (circles) are assigned.

Fig. 2
Fig. 2

Three surfaces on which points are not localized. The local frames ( e x , e y , e z ) can be moved along two independent directions (dotted curves) without changing the surface description with reference to the frame.

Fig. 3
Fig. 3

Local coordinate system ( e x , e y , e z ) on a surface point x with normal n. The neighborhood of x, bounded by the intersecting line between the surface and the bounding cylinder, is adumbrated. Each point x k in the neighborhood has local cylindrical coordinates of r k , φ k , h k .

Fig. 4
Fig. 4

Rendered range image of a face; see the Fig. 5 caption for a detailed explanation.

Fig. 5
Fig. 5

Salience image of the 3-D view shown in Fig. 4. The salience values are displayed as intensity values. The size of the neighborhoods of two exemplary surface points is marked by circles. For point 1, for example, no salience value is computed. In neighborhood 1 in Fig. 4, points are missing on the right because of shadowing during the measurement. This effect explains why there is much less surface area covered by the salience image than by the range image. The nose, e.g., drops out almost completely. At point 2 there is a local maximum of the salience because the surface in its neighborhood is highly structured.

Fig. 6
Fig. 6

Rendering of the complete surface model of a horse sculpture by Franz Marc. Photo courtesy of the Staatliche Galerie Moritzburg Museum, Halle (Saale), Germany.

Fig. 7
Fig. 7

Salience images of two different range images from regions of the object in Fig. 6 that are only slightly structured. The salience maxima are marked by black squares; some of the corresponding points by circles and numbers.

Fig. 8
Fig. 8

Normalized frequencies p [ ξ ^ ( i ) ] of discretized normalized distances ξ ^ ( i ) of closest salient points in the overlapping regions of two data sets. The discretization intervals are Δξ̂ = 0.5. The histogram is normalized to i = 1 p [ ξ ^ ( i ) ] Δ ξ ^ = 1 . By far the most frequent distances are those that are smaller than the mean sampling distance, i.e., ξ ^ < 1 .

Fig. 9
Fig. 9

Normalized frequencies p D of discrete feature distances D ( i ) with i p D [ D ( i ) ] Δ D = 1 computed for pairs of corresponding and randomly selected points.

Fig. 10
Fig. 10

Feature recognition rate versus maximum allowed feature distance for four objects.

Fig. 11
Fig. 11

Top: salience images of preoperatively (left) and intraoperatively (right) acquired face data. The salient points are indicated by black squares; the corresponding points are emphasized by circles. Bottom: 3-D renderings of preoperative (left), intraoperative (middle), and registered (right) range images displayed in different shades of gray.

Fig. 12
Fig. 12

Salience images and 3-D renderings of two views of a tooth; see the Fig. 11 caption for details.

Fig. 13
Fig. 13

Top and middle: salience images of two different views of a sword with the salient points indicated by black squares. The corresponding points are emphasized by white circles. Bottom: registered data sets displayed in different shades of gray.

Tables (1)

Tables Icon

Table 1 Properties, Parameters, Processing Times, and Registration Accuracy of Four Objects a

Equations (163)

Equations on this page are rendered with MathJax. Learn more.

e x
e y
e z
e z
x
n
x
{ x 1 , x 2 ,   , x N }
H ( X ) = i = 1 N p ( x i ) log 2 [ p ( x i ) ]
p ( x i )
x i
X X
H ( X )
H ( X )
X X
x k
x k = ( r k , φ k , h k )
r k
h k
φ k
r k
h k
r k r max .
r max
x k
x k
κ k
r k = { x k x 2 [ n ( x k x ) ] 2 } 1 / 2 ,
h k = n ( x k x )
κ k = 2 h k r k 2 + h k 2 .
p ( κ )
κ [ κ max , κ max ]
Δ κ ^
N ^ κ = 2 κ max / Δ κ ^ + 1
κ ^ ( i ) , i = 1 ,   , N ^ κ
p κ ( κ ^ )
H spherical ( κ ^ ) = i = 1 N ^ p [ κ ^ ( i ) ] log 2 { p [ κ ^ ( i ) ] } .
κ k
H spherical ( κ ^ ) = 0
( κ = 0 )
N salient
N sal = 100
H spherical
s x
s x l
N adj
x l
d s
s x s x l > d s = 1.05 , l { 1 , , N adj } ,
s x
5 %
s x l
d s
r max
Δ κ ^
κ max
Δ x csp
Δ x
p ( ξ ^ )
ξ ^
ξ = Δ x csp Δ x ¯ .
p u ^ , v ^
x k
r k
κ k
r k
κ k
u k = r k 2 ,
v k = κ k .
u ^
N ^ u
Δ u ^
u ^ ( i )
i = 1 ,  
N ^ u
v ^
N ^ v
Δ v ^
v ^ ( j )
j = 1 ,   , N v
u [ 0 , r max 2 [
[ u ^ ( i ) , u ^ ( i + 1 ) [
v [ κ max , κ max [
v ( j ) = κ ( j )
N ^ v = N ^ κ
x k
x k
p u ^ , v ^ ( 1 ) ( u ^ ,   v ^ )
p u ^ , v ^ ( 2 ) ( u ^ ,   v ^ )
D [ p u ^ , v ^ ( 1 ) ,   p u ^ , v ^ ( 2 ) ]
χ 2
D [ p u ^ , v ^ ( 1 ) , p u ^ , v ^ ( 2 ) ] = i = 1 N ^ u j = 1 N ^ v { p u ^ , v ^ ( 2 ) [ u ^ ( i ) , v ^ ( j ) ] p u ^ , v ^ ( 1 ) [ u ^ ( i ) , v ^ ( j ) ] } 2 .
N sal
N sim
N P = N sal N sim
D max
D max
D D max
Δ x max
Δ x max : = Δ x ¯
N C S
N C ¯ S
N C ¯ S ¯
N C S ¯
p true
p C S
p C ¯ S ¯
p succ = p C S p C ¯ S ¯ ,
p C S
p C ¯ S ¯
N C
N C ¯
p succ = N C S N C N C ¯ S ¯ N C ¯ ,
p succ
P = ( r max , Δ κ ^ , κ max , D max )
P opt
p succ
P opt = arg max P p succ ( P ) .
p succ
D max
D max
D max
D max
N P
[ x A ( 1 ) , x B ( 1 ) ]
x A ( 1 )
A
x B ( 1 )
[ x A ( 1 ) , x B ( 1 ) ]
[ x A ( 2 ) , x B ( 2 ) ]
d A = x A ( 1 ) x A ( 2 )
A
d B = x B ( 1 ) x B ( 2 )
| d A d B | Δ x ¯
Δ x ¯
[ x A ( 2 ) , x B ( 2 ) ]
N P
( x A , x B )
N P
D ( x A , x B )
s x ( x A )
O [ ( N P ) 2 ] = O [ ( N sal N sim ) 2 ]
N sal
N sim
N sal = 100
N sim = 5
2.4   GHz
O [ ( N P ) 2 ]
Δ x ¯
( N ^ u × N ^ v )
( Δ x ¯ c p )
( Δ x ¯ c p )
( e x , e y , e z )
( e x , e y , e z )
x k
r k , φ k , h k
p [ ξ ^ ( i ) ]
ξ ^ ( i )
i = 1 p [ ξ ^ ( i ) ] Δ ξ ^ = 1
ξ ^ < 1
p D
D ( i )
i p D [ D ( i ) ] Δ D = 1

Metrics