Publikationsserver der Universitätsbibliothek Marburg

Titel:Rekonstruktion und Verarbeitung von Objekten und Szenen aus Kamerabildern
Autor:Grund, Nico
Weitere Beteiligte: Sommer, Manfred (Prof. Dr.)
Veröffentlicht:2012
URI:https://archiv.ub.uni-marburg.de/diss/z2013/0076
DOI: https://doi.org/10.17192/z2013.0076
URN: urn:nbn:de:hebis:04-z2013-00760
DDC:004 Informatik
Titel (trans.):Reconstruction and processing of objects and scenes from camera images
Publikationsdatum:2013-02-11
Lizenz:https://rightsstatements.org/vocab/InC-NC/1.0/

Dokument

Schlagwörter:
Bildkompression, parallele Simplifizierung, instant level-of-detail, Dreidimensionale geometrische Modellierung, Dreidimensionale Rekonstruktion, 3d-reconstruction, image compression, Generierung von Level-of-Detail, Parallelverarbeitung, parallel progressive mesh editing, GPU-Implementierung, multi-resolution helmholtz stereopsis

Zusammenfassung:
In Computerspielen, Animationsfilmen und anderen interaktiven Rendering-Applikationen werden für gewöhnlich 3D-Modelle verarbeitet. Die Modelle entsprechen dabei meistens einem realen Vorbild, welches mithilfe eines Laserscanners abgetastet wurde. Da moderne Laserscanner teuer und unhandlich sind, werden Alternativen benötigt, mit denen virtuelle Abbilder kostengünstig und effizient erzeugt werden können. Neben den Methoden zur Rekonstruktion dreidimensionaler Objekte sind Verfahren erforderlich, mit deren Hilfe die 3D-Modelle modifiziert werden können. In diesem Kontext spielt die Multiskalen-Modellierung (engl. multi resolution modeling) bei der Durchführung des Editiervorgangs in Echtzeit eine wichtige Rolle, um zum Beispiel komplexe Bewegungsabläufe simulieren zu können. Diese Dissertation beschäftigt sich mit den Möglichkeiten zur Rekonstruktion von Objekten und Szenen aus Kamerabildern und präsentiert neue Techniken, mit denen ein als Polygonnetz vorliegendes 3D-Modell editiert werden kann. Für die 3D-Rekonstruktion werden reziproke Bildpaare verwendet, auf deren Grundlage die Korrespondenzen zwischen den einzelnen Bildpunkten aufgedeckt und eine Tiefenanalyse vollzogen wird. Die daraus resultierenden Tiefenwerte werden in einer Tiefenkarte (engl. depth map) gespeichert, aus denen letztlich ein dreidimensionales Dreiecksnetz generiert werden kann. Während der Umsetzung des Verfahrens wurde großer Wert auf die Parallelisierung der einzelnen Berechnungsschritte gelegt. In Bezug auf die Modellierung von 3D-Modellen wurde zunächst ein hoch-qualitativer, paralleler Simplifizierungsalgorithmus entworfen, der in der Lage ist, in Echtzeit mehrere zu einem 3D-Objekt gehörende Detailstufen zu erzeugen. Auf Basis des Simplifizierungsverfahrens wurde schließlich ein parallel auf der Grafikkarte ausführbares Programm zur Multiskalen-Modellierung realisiert, mit welchem die Möglichkeit geschaffen wurde ein Modell auf verschiedenen Detailstufen zu editieren und die vorgenommenen Modifikationen über die erstellten Detailstufen hinweg in Echtzeit und unter Berücksichtigung der bestehenden Oberflächendetails zu verarbeiten. Die für das Editieren notwendige Datenstruktur wird dabei während der Simplifizierungsphase parallel auf der Grafikkarte innerhalb weniger Sekunden erzeugt.

Bibliographie / References

  1. Wilhelms J., Van Gelder A.: Octrees for faster isosurface generation. ACM Trans. Graph. 11, 3 (July 1992), 201–227.
  2. Derzapf E., Menzel N., Guthe M.: Parallel view-dependent refinement of compact progressive meshes. In Eurographics Symposium on Parallel Graphics and Visualization (2010), pp. 53–62.
  3. Guskov I., Sweldens W., Schröder P.: Multiresolution signal processing for meshes. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques (1999), SIGGRAPH '99, pp. 325–334.
  4. Lindstrom P.: Out-of-core simplification of large polygonal models. In Pro- ceedings of the 27th annual conference on Computer graphics and interactive techniques (2000), SIGGRAPH '00, pp. 259–262.
  5. Guttman A.: R-trees: A dynamic index structure for spatial searching. In International Conference on Management of Data (1984), ACM, pp. 47–57.
  6. Ford L. R., Fulkerson D. R.: Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399–404.
  7. [BKBH09] Bolitho M., Kazhdan M., Burns R., Hoppe H.: Parallel poisson surface reconstruction. In Proceedings of the 5th International Symposium on Advances in Visual Computing: Part I (Berlin, Heidelberg, 2009), ISVC '09, Springer- Verlag, pp. 678–689.
  8. He Z., Hong B.: Dynamically tuned push-relabel algorithm for the maximum flow problem on cpu-gpu-hybrid platforms. In 24th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2010 (2010), IEEE, pp. 1–10.
  9. Stein A. N., Huertas A., Matthies L.: Attenuating stereo pixel-locking via affine window adaptation. In In IEEE International Conference on Robotics and Automation (2006), pp. 914–921.
  10. [GS02] Garland M., Shaffer E.: A multiphase approach to efficient surface simplification. In Proceedings of the conference on Visualization '02 (2002), pp. 117–124.
  11. Schneider J., Westermann R.: Compression domain volume rendering. In Proceedings of the 14th IEEE Visualization 2003 (VIS'03) (Washington, DC, USA, 2003), VIS '03, IEEE Computer Society, pp. 293–300.
  12. Low K.-L., Tan T.-S.: Model simplification using vertex-clustering. In Proceedings of the 1997 symposium on Interactive 3D graphics (1997), pp. 75– ff.
  13. Kim J. C., Lee K. M., Choi B. T., Lee S. U.: A dense stereo matching using two-pass dynamic programming with generalized ground control points. In Proceedings IEEE International Conference on Computer Vision and Pattern Recognition, Vol. II (2005), IEEE Computer Society, pp. 1075–1082.
  14. Luebke D. P.: A developer's survey of polygonal simplification algorithms. IEEE Comp. Graph. Appl. 21 (2001), 24–35.
  15. Anandan P.: A computational framework and an algorithm for the mea- surement of visual motion. International Journal of Computer Vision 2, 3 (January 1989), 283–310–310.
  16. [SCD * 06] Seitz S. M., Curless B., Diebel J., Scharstein D., Szeliski R.: A comparison and evaluation of multi-view stereo reconstruction algorithms, 2006.
  17. Schaefer S., Warren J.: Adaptive vertex clustering using octrees. In SIAM Geometric Design and Computing (2003).
  18. [GT88] Goldberg A. V., Tarjan R. E.: A new approach to the maximum-flow problem. In Journal of the Association for Computing Machinery (ACM) (October 1988), vol. 35, pp. 921–940.
  19. Boykov Y., Kolmogorov V.: An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2001), 359–374.
  20. [OGH * 98] Ohm J.-R., Grüneberg K., Hendriks E., M. E. I., Kalivas D., Karl M., Papadimatos D., Redert A.: A realtime hardware system for ste- reoscopic videoconferencing with viewpoint adaptation. In Signal Processing: Image Communication (1998), pp. 147–171.
  21. Sinop A. K., Grady L.: A seeded image segmentation framework unifying graph cuts and random walker which yields a new algorithm. In Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on (2007), IEEE, pp. 1–8.
  22. Taubin G.: A signal processing approach to fair surface design. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques (1995), SIGGRAPH '95, ACM, pp. 351–358.
  23. Kanade T., Okutomi M.: A stereo matching algorithm with an adaptive window: Theory and experiment. In Proceedings of IEEE Transactions on Pattern Analysis and Machine Intelligence (September 1994), vol. 16, pp. 920– 932.
  24. Scharstein D., Szeliski R.: A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision 47 (2002), 7–42.
  25. Mallat S.: A Wavelet Tour of Signal Processing. Academic Press, 1998.
  26. [MKZB01] Magda S., Kriegman D. J., Zickler T., Belhumeur P. N.: Beyond lambert: Reconstructing surfaces with arbitrary brdfs. In Proceedings of the 8th IEEE International Conference on Computer Vision (June 2001), vol. 2, pp. 391–399.
  27. [ZHK * 03] Zickler T. E., Ho J., Kriegman D. J., Ponce J., Belhumeur P. N.: Bi- nocular helmholtz stereopsis. In Proceedings of IEEE Conference on Computer Vision (October 2003), pp. 1411–1417.
  28. Forsyth D. A., Ponce J.: Computer Vision: A Modern Approach. Pearson Education, 2012.
  29. Azad P., Gockel T., Dillmann R.: Computer Vision: das Praxisbuch. Elektor-Verlag, Aachen, 2011.
  30. [MLM * 07] Matthies, Larry, Maimone, Mark, Johnson, Andrew, Cheng, Yang, Willson, Reg, Villalpando, Carlos, Goldberg, Steve, Huertas, Andres, Stein, Andrew, Angelova, Anelia: Computer vision on mars. International Journal of Computer Vision 75, 1 (October 2007), 67–92.
  31. Vineet V., Narayanan P. J.: Cuda cuts: Fast graph cuts on the gpu. Computer Vision and Pattern Recognition Workshop 0 (2008), 1–8.
  32. Das Originalmodell des Welsh Dragon sowie einige der mithilfe des parallelen Simplifizierungsverfahrens generierten Detailstufen. Insgesamt wurden 10
  33. Derzapf E., Guthe M.: Dependency free parallel progressive meshes. Computer Graphics Forum 31 (December 2012), 2288–2302.
  34. Die gerichtete Graphen-Datenstruktur unkomprimiert (links) und kom- primiert (rechts). Um die verschiedenen, in einem Knoten gespeicherten Koeffizienten differenzieren zu können, wurden diese farblich hervorgehoben.
  35. [LSCO * 04] Lipman Y., Sorkine O., Cohen-Or D., Levin D., Rössl C., Seidel H.-P.: Differential coordinates for interactive mesh editing. In In Proceedings of Shape Modeling International (2004), Society Press, pp. 181–190.
  36. Jähne B.: Digitale Bildverarbeitung. Springer Verlag, 2005.
  37. Pratt W. K.: Digital Image Processing. John Wiley & Sons Inc., 2001.
  38. Wang J., Wong T.-T., Heng P.-A., Leung C.-S.: Discrete wavelet transform on gpu. In Proceedings of ACM Workshop on General Purpose Computing on Graphic Processors (2004), pp. C–41.
  39. Shaffer E., Garland M.: Efficient adaptive simplification of massive meshes. In Proceedings of the conference on Visualization '01 (2001), pp. 127– 134.
  40. Stein F.: Efficient computation of optical flow using the census transform. In Proceedings of the 26th DAGM Symposium (2004), vol. 3175 of Lecture Notes in Computer Science, Springer, pp. 79–86.
  41. Franke U., I. K.: Fast stereo based object detection for stop&go traffic. In Proceedings of the 1996 IEEE, Intelligent Vehicles Symposium (September 1996), pp. 339–344.
  42. Welch W., Witkin A.: Free-form shape design using triangulated surfaces. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques (1994), SIGGRAPH '94, ACM, pp. 247–256.
  43. Marinov M., Botsch M., Kobbelt L.: Gpu-based multiresolution defor- mation using approximate normal field reconstruction. journal of graphics, gpu, and game tools 12, 1 (2007), 27–46.
  44. Dixit N., Keriven R., Paragios N.: Gpu-cuts: Combinatorial optimisation, graphic processing units and adaptive object extraction, 2005.
  45. [BT08] Bhusnurmath A., Taylor C. J.: Graph cuts via l norm minimization. IEEE Trans. Pattern Anal. Mach. Intell. (2008), 1866–1871.
  46. Büsing C.: Graphen-und Netzwerkoptimierung. Spektrum Akademischer Verlag, 2010.
  47. Zickler T. E., Belhumeur P. N., Kriegman D. J.: Helmholtz stereop- sis: Exploiting reciprocity for surface reconstruction. In Proceedings of 7th European Conference on Computer Vision (May 2002), vol. 3, pp. 869–884.
  48. Forsey D. R., Bartels R. H.: Hierarchical b-spline refinement. In Pro- ceedings of the 15th annual conference on Computer graphics and interactive techniques (1988), SIGGRAPH '88, ACM, pp. 205–212.
  49. [VC95] Venkateswar V., Chellappa R.: Hierarchical stereo and motion corre- spondence using feature groupings. Int. J. Comput. Vision 15, 3 (July 1995), 245–269.
  50. Grund N., Menzel N., Guthe M.: High-quality wavelet compressed textures for real-time rendering. In WSCG 2010 Communication Papers Proceedings (2010), pp. 207–212.
  51. [PB99] Petrou M., Bosdogianni P.: Image Processing: The Fundamentals. John Wiley & Sons Inc., 1999.
  52. Grund N., Derzapf E., Guthe M.: Instant level-of-detail. In Vision, Modeling, and Visualization (VMV2011) (2011), pp. 293–299.
  53. Zorin D., Schröder P., Sweldens W.: Interactive multiresolution mesh editing. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (1997), SIGGRAPH '97, pp. 259–268.
  54. Kobbelt L., Campagna S., Vorsatz J., Seidel H.-P.: Interactive multi- resolution modeling on arbitrary meshes. In SIGGRAPH (1998), pp. 105–114.
  55. Taubman D. S., Marcellin M. W.: Jpeg2000: Image compression funda- mentals, standards and practice. In Kluwer International Series in Engineering and Computer Science (2001), Kluwer Academic Publishers.
  56. [SCOL * 04] Sorkine O., Cohen-Or D., Lipman Y., Alexa M., Rössl C., Seidel H.- P.: Laplacian surface editing. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing (2004), SGP '04, pp. 175–184.
  57. Samavati F. F., Bartels R. H.: Local filters of b-spline wavelets. In Proceedings of International Workshop on Biometric Technologies 2004 (2004), pp. 105–110.
  58. Lorensen W. E., Cline H. E.: Marching cubes: A high resolution 3d surface construction algorithm. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1987), SIGGRAPH '87, ACM, pp. 163–169.
  59. Hartley R., Zisserman A.: Multiple View Geometry in Computer Vision. Cambridge University Press, 2003.
  60. Rossignac J., Borel P.: Multi-resolution 3d approximations for rendering complex scenes. In Modeling in Computer Graphics: Methods and Applications (Berlin, June 1993), Falcidieno B., Kunii T., (Eds.), Springer Verlag, pp. 455– 465.
  61. Grund N., Guthe M.: Multi-resolution helmholtz stereopsis. Unpublished.
  62. Kobbelt L., Vorsatz J., Seidel H.-P.: Multiresolution hierarchies on unstructured triangle meshes. Comput. Geom. 14, 1-3 (1999), 5–24.
  63. [Gar99] Garland M.: Multiresolution modeling: Survey & future opportunities. Proceedings of the Eurographics '99 – State of the Art Reports (1999), 111– 131.
  64. [PTVF07] Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P.: Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, 2007.
  65. [SFYC96] Shekhar R., Fayyad E., Yagel R., Cornhill J. F.: Octree-based decimation of marching cubes surfaces. In Proceedings of the 7th conference on Visualization '96 (Los Alamitos, CA, USA, 1996), VIS '96, IEEE Computer Society Press, pp. 335–ff.
  66. Kazhdan M., Bolitho M., Hoppe H.: Poisson surface reconstruction. In SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing (2006), Eurographics Association, pp. 61–70.
  67. Popović J., Hoppe H.: Progressive simplicial complexes. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (1997), SIGGRAPH '97, pp. 217–224.
  68. Shapiro J. M.: Readings in multimedia computing and networking. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001, ch. Embedded Image Coding Using Zerotrees of Wavelet Coefficients, pp. 124–141.
  69. Hirschmüller H., Innocent P. R., Garibaldi J.: Real-time correlation- based stereo vision with reduced border errors. Int. J. Comput. Vision 47 (April 2002), 229–246.
  70. Westermann R., Kobbelt L., Ertl T.: Real-time exploration of regular volume data by adaptive reconstruction of iso-surfaces. The Visual Computer 15 (1999), 100–111.
  71. DeCoro C., Tatarchuk N.: Real-time mesh simplification using the gpu. In Proceedings of the 2007 symposium on Interactive 3D graphics and games (2007), pp. 161–166.
  72. Diverdi S., Candussi N., Höllerer T.: Real-time Rendering with Wavelet- Compressed Multi-Dimensional Datasts on the GPU. Tech. rep., University of California, Santa Barbara, 2005.
  73. Franke U., Joos A.: Real-time stereo vision for urban traffic scene under- standing. In Intelligent Vehicles Symposium, 2000. IV 2000. Proceedings of the IEEE (2000), pp. 273–278.
  74. Kazhdan M.: Reconstruction of solid models from oriented point sets. In Proceedings of the third Eurographics symposium on Geometry processing (2005), SGP '05.
  75. Rekonstruiertes Modell der in der Hängematte liegenden Frau (unten), inklusive der aus der Tiefenanalyse resultierenden Punktwolke (oben). . . 73
  76. [BAC96] Beers A. C., Agrawala M., Chaddha N.: Rendering from compressed textures. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1996), SIGGRAPH '96, ACM, pp. 373–378.
  77. [SHZO07] Sengupta S., Harris M., Zhang Y., Owens J. D.: Scan primitives for gpu computing. In GRAPHICS HARDWARE 2007 (2007), Association for Computing Machinery, pp. 97–106.
  78. Lee S.-B., Oh K.-J., Ho Y.-S.: Segment-based multi-view depth map esti- mation using belief propagation from dense multi-view video. In Proceedings of the 3DTV Conference (May 2008), pp. 193–196.
  79. Garland M., Heckbert P. S.: Simplifying surfaces with color and texture using quadric error metrics. In Proceedings of the conference on Visualization '98 (1998), pp. 263–269.
  80. Garland M., Heckbert P. S.: Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (1997), SIGGRAPH '97, pp. 209–216.
  81. [Bar04] Bartsch H.-J.: Taschenbuch mathematischer Formeln. Fachbuchverlag Leipzig im Carl Hanser Verlag, 2004.
  82. Daubechies I.: Ten Lectures on wavelets. Society for Industrial and Applied Mathematics, 1992.
  83. Fenney S.: Texture compression using low-frequency signal modulation. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware (Aire-la-Ville, Switzerland, Switzerland, 2003), HWWS '03, Eurographics Association, pp. 84–91.
  84. Tanner C. C., Migdal C. J., Jones M. T.: The clipmap: A virtual mipmap. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1998), SIGGRAPH '98, ACM, pp. 151–158.
  85. Garg S.: The image compression benchmark. http://http://www. imagecompression.info/test_images/ (30.10.2012).
  86. Christopoulos C., Skodras A., Ebrahimi T.: The jpeg2000 still image coding system: An overview. In IEEE Transactions on Consumer Electronics (2000), vol. 16, pp. 1103–1127.
  87. [KKDH07] Kazhdan M., Klein A., Dalal K., Hoppe H.: Unconstrained isosurface extraction on arbitrary octrees. In Proceedings of the fifth Eurographics symposium on Geometry processing (Aire-la-Ville, Switzerland, Switzerland, 2007), SGP '07, Eurographics Association, pp. 125–133.
  88. Wöhler C., Krüger L.: A contour-based stereovision algorithm for video surveillance applications. In Proceedings of VCIP'03 (2003), pp. 102–109.
  89. Cooley J., Tukey J.: An algorithm for the machine calculation of complex fourier series. Mathematics of Computation 19, 90 (1965), 297–301.


* Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten