Sneller naar een virtuele wereld

Menthy
Denayer

Modelleren en 3D-scanning leiden beide tot het maken van een virtuele wereld. 3D-scanning leidt echter tot een veel sneller resultaat.

Om het beste algoritme te selecteren, moeten we de algoritmes eerst met elkaar vergelijken. Zo bestaan er veel algoritmes die helpen om een virtuele wereld sneller op te bouwen. Virtuele werelden zijn onmisbaar. Denk maar aan zelfrijdende auto’s, die niet mogen botsen, of medisch personeel dat wordt opgeleid zonder in levende proefpersonen te moeten snijden.

 

Virtuele ogen

Wanneer je met de auto rijdt, gebruik je je ogen om in te schatten wanneer je moet remmen, om zo een aanrijding te vermijden. De ogen van een zelfrijdende wagen zijn sensors of 3D-camera’s. Deze 3D-camera’s geven ons een idee over de afstand van elk object tot de camera. Dat is niet het geval wanneer je met je smartphone een foto neemt van je huisdier. Die foto bestaat uit pixels, kleine vierkantjes met een welbepaalde kleur. Een afbeelding is echter een 2D, vlakke voorstelling van de werkelijkheid. De informatie over de diepte, of hoe ver elk object staat van de camera, wordt niet bewaard. Het resultaat van een 3D-camera is een puntenwolk, waarbij ieder punt nu een kleur heeft en diepte.

Puntenwolk in de vorm van een vliegtuig.

Een puntenwolk bestaande uit een collectie van punten die de driedimensionale wereld – hier een vliegtuig – voorstellen.

 

Het registratieprobleem

Beeld je nu in dat we twee puntenwolken hebben, bijvoorbeeld twee kubussen. Beide stellen hetzelfde object voor, maar staan op een andere plaats in de ruimte. Als we nu beide wolken willen samenbrengen, waardoor ze overlappen, lijkt dat een simpele taak. Voor een computer is deze alignatie echter niet zo voor de hand liggend. Dit probleem, namelijk ervoor zorgen dat de twee puntenwolken overlappen, heet ook wel het registratieprobleem en is zeer populair binnen de computerwetenschappen.

Twee puntenwolken in de vorm van kubussen worden gealigneerd.

De twee kubussen (blauw, rood) worden gealigneerd door een algoritme. De positie van de ene kubus ten opzichte van de andere wordt zo gevonden.

 

Een zee van algoritmes

Er bestaan talloze methodes om het registratieprobleem op te lossen, met variërende resultaten. Het ligt dan voor de hand om het “beste” algoritme te selecteren. “Beste” is echter geen duidelijke maatstaf. Daarom vergelijken we in dit onderzoek enkele van deze verschillende methodes met elkaar. Sommige methodes zijn bijvoorbeeld zeer snel en leiden tot een oplossing in minder dan een seconde. Andere doen er wat langer over, maar resulteren in een veel nauwkeuriger resultaat.

Om de algoritmes te vergelijken voeren we de alignatie uit voor enkele eenvoudige, symmetrische vormen. De twee puntwolken maken we uit een driedimensionaal model van het voorwerp (dit is de template) en een scan gemaakt met een 3D-camera. Het experiment wordt meerdere keren herhaald, waarbij bijvoorbeeld het aantal punten wordt veranderd. Ieder individueel resultaat toetsen we op verschillende vlakken, zoals hoe goed de puntenwolken overlappen, de benodigde rekentijd enzovoort.

Twee puntenwolken worden gemaakt. Eén uit een 3D-model, één met een 3D-camera. De puntenwolken worden gealigneerd met een algoritme.

Het driedimensionaal model (blauw, ook wel “template” genoemd) wordt gealigneerd met de driedimensionale scan (rood).

Uit onze vergelijking blijkt dat sommige algoritmes zeer nauwkeurig zijn, maar ook wat trager. Dat maakt hen niet ideaal voor toepassingen waarbij de registratie vaak opnieuw moet worden opgelost, bijvoorbeeld als de objecten bewegen. Andere methodes zijn gemaakt om zeer snel te zijn en worden daardoor minder nauwkeurig. In die gevallen gebruiken we een extra algoritme om de resultaten verder te verfijnen.

De resultaten vatten we ook samen in een zogenaamde flowchart. Dit is een schema met verschillende ja-nee vragen. Door de vragen één voor één te beantwoorden, kan een andere onderzoeker (of geïnteresseerde lezer) de “beste” methode selecteren voor de eigen toepassing, als een soort “eerste hulp bij algoritme keuzestress”.

 

Een virtuele wereld scheppen

We kunnen de oplossing van het registratieprobleem ook gebruiken om complete virtuele werelden te bouwen. De echte wereld tot een driedimensionale, virtuele kopie omtoveren is immers een intensief karwei. Klassiek gebeurt dit door object per object een driedimensionaal model te bouwen. Beeld je bijvoorbeeld een stoel in onder een tafel. Dan moet je voor zowel de stoel als de tafel een 3D-model opbouwen tot in de kleinste details.  Een 3D-camera laat toe om dat proces te versnellen. Je loopt simpelweg rond de tafel en de stoel, scant de omgeving met de camera en je verkrijgt onmiddellijk een complete, driedimensionale puntenwolk.

Is daarmee het probleem opgelost? Niet helemaal. De punten in de puntenwolk vormen samen een kopie van de omgeving, maar hoe weet je bij welk object een punt hoort? Bijvoorbeeld, punt A is een onderdeel van het object “stoel” en punt B van het object “tafel”. Er bestaan verschillende algoritmes die de punten kunnen groeperen, onder meer You Only Look Once (YOLO). Met behulp van dit algoritme kunnen de punten worden onderverdeeld in de verschillende objecten of voorwerpen.

Een puntenwolk wordt onderverdeeld in een stoel en tafel.

De puntenwolk bestaat uit duizenden punten, die aangeduid moeten worden. Bijvoorbeeld, de roze punten maken deel uit van het object stoel en de gele van het object tafel.

Er blijft echter nog één probleem over: hoe kunnen we nu van deze objecten de positie in de ruimte bepalen? Een robot bijvoorbeeld, moet weten waar een voorwerp staat om het te kunnen grijpen. De oplossing hiervoor is het registratieprobleem. Als we weten waar twee puntenwolken zich ten opzichte van elkaar bevinden, kunnen we ook hun positie achterhalen. Hiermee weet onze slimme, zelfrijdende wagen niet alleen exact waar de voorliggende auto zich bevindt, maar kan hij ook een volledige virtuele kopie maken van de omgeving waarin hij rijdt. 

 

De virtuele toekomst

Interactieve virtuele werelden bestaan ondertussen al in verschillende vormen en formaten. Denk hierbij maar aan VR spelletjes, waar je plots stapt op een smal plankje, dat zich hoog in de lucht bevindt, of de namen van sterrenbeelden die voor je ogen verschijnen wanneer je naar de sterren staart. De mogelijkheden zijn dan ook eindeloos en de enige limiet is je eigen verbeelding, op het maken van die virtuele wereld na. Het is net hierin dat dit onderzoek ons verder helpt. Door onderzoekers naar de beste methodes te leiden, kunnen nieuwe ideeën sneller ontstaan. Die beste methode selecteer je dan op basis van een vergelijking, zoals de onze. Met precieze 3D-camera's en een nauwkeurig en snel registratieproces, komen we sneller tot een virtuele wereld.

Bibliografie

[1]         S. Alizadehsalehi, ‘BIM/Digital Twin-Based Construction Progress Monitoring through Reality Capture to Extended Reality (DRX)’, p. 212.

[2]         Y. Aoki, H. Goforth, R. A. Srivatsan, en S. Lucey, ‘PointNetLK: Robust & Efficient Point Cloud Registration Using PointNet’, in 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Long Beach, CA, USA: IEEE, jun. 2019, pp. 7156-7165. doi: 10.1109/CVPR.2019.00733.

[3]         S. Bangay, J. Gain, G. Watkins, en K. Watkins, ‘Building the second generation of parallel/distributed virtual reality systems’, Parallel Comput., vol. 23, nr. 7, pp. 991-1000, jul. 1997, doi: 10.1016/S0167-8191(97)00040-9.

[4]         M. Berger e.a., ‘A Survey of Surface Reconstruction from Point Clouds’, Comput. Graph. Forum, vol. 36, nr. 1, pp. 301-329, jan. 2017, doi: 10.1111/cgf.12802.

[5]         B. Bhattacharya en E. H. Winer, ‘Augmented reality via expert demonstration authoring (AREDA)’, Comput. Ind., vol. 105, pp. 61-79, feb. 2019, doi: 10.1016/j.compind.2018.04.021.

[6]         E. Brachmann, ‘6D Object Pose Estimation using 3D Object Coordinates [Data]’. heiDATA, 2020. doi: 10.11588/DATA/V4MUMX.

[7]         C. Choy, W. Dong, en V. Koltun, ‘Deep Global Registration’, in 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Seattle, WA, USA: IEEE, jun. 2020, pp. 2511-2520. doi: 10.1109/CVPR42600.2020.00259.

[8]         M. Ciocarlie, K. Hsiao, E. G. Jones, S. Chitta, R. B. Rusu, en I. A. Şucan, ‘Towards Reliable Grasping and Manipulation in Household Environments’, in Experimental Robotics, vol. 79, O. Khatib, V. Kumar, en G. Sukhatme, Red., in Springer Tracts in Advanced Robotics, vol. 79. , Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 241-252. doi: 10.1007/978-3-642-28572-1_17.

[9]         K. Collins, A. J. Palmer, en K. Rathmill, ‘The Development of a European Benchmark for the Comparison of Assembly Robot Programming Systems’, in Robot Technology and Applications, K. Rathmill, P. MacConaill, P. O’Leary, en J. Browne, Red., Berlin, Heidelberg: Springer, 1985, pp. 187-199. doi: 10.1007/978-3-662-02440-9_18.

[10]       ‘Compare Intel RealSense Depth Cameras (Tech specs and Review)’, Intel® RealSenseTM Depth and Tracking Cameras. Geraadpleegd: 19 februari 2023. [Online]. Beschikbaar op: https://www.intelrealsense.com/compare-depth-cameras/

[11]       ‘Computer Science’. Geraadpleegd: 27 oktober 2022. [Online]. Beschikbaar op: https://www.ru.ac.za/computerscience/

[12]       S. Doolani e.a., ‘A Review of Extended Reality (XR) Technologies for Manufacturing Training’, Technologies, vol. 8, nr. 4, p. 77, dec. 2020, doi: 10.3390/technologies8040077.

[13]       M. A. Fischler en R. C. Bolles, ‘Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Carthography.pdf’, Communications of the ACM, p. 15, jun. 1981.

[14]       E. Frécon en M. Stenius, ‘DIVE: a scaleable network architecture for distributed virtual environments’, Distrib. Syst. Eng., vol. 5, nr. 3, pp. 91-100, sep. 1998, doi: 10.1088/0967-1846/5/3/002.

[15]       ‘Global registration — Open3D 0.15.1 documentation’. Geraadpleegd: 27 oktober 2022. [Online]. Beschikbaar op: http://www.open3d.org/docs/release/tutorial/pipelines/global_registrati…

[16]       ‘Google Colab’. Geraadpleegd: 28 februari 2023. [Online]. Beschikbaar op: https://research.google.com/colaboratory/faq.html

[17]       ‘Iterative closest point’, Wikipedia. 26 juni 2022. Geraadpleegd: 5 september 2022. [Online]. Beschikbaar op: https://en.wikipedia.org/w/index.php?title=Iterative_closest_point&oldi…

[18]       ‘librealsense/wrappers/opencv/kinfu at master · IntelRealSense/librealsense’, GitHub. Geraadpleegd: 29 april 2023. [Online]. Beschikbaar op: https://github.com/IntelRealSense/librealsense

[19]       X. Gu, X. Wang, en Y. Guo, ‘A Review of Research on Point Cloud Registration Methods’, Mater. Sci. Eng., p. 10, 2019.

[20]       X.-F. Han, J. S. Jin, M.-J. Wang, W. Jiang, L. Gao, en L. Xiao, ‘A review of algorithms for filtering the 3D point cloud’, Signal Process. Image Commun., vol. 57, pp. 103-112, sep. 2017, doi: 10.1016/j.image.2017.05.009.

[21]       K. He, J. Sun, en X. Tang, ‘Guided Image Filtering’, IEEE Trans. Pattern Anal. Mach. Intell., vol. 35, nr. 6, pp. 1397-1409, jun. 2013, doi: 10.1109/TPAMI.2012.213.

[22]       Z. Hendricks, G. Marsden, en E. Blake, ‘A Meta-Authoring Tool for Specifying Interactions in Virtual Reality Environments’, p. 10.

[23]       B. Jerbić, F. Šuligoj, M. Švaco, en B. Šekoranja, ‘Robot Assisted 3D Point Cloud Object Registration’, Procedia Eng., vol. 100, pp. 847-852, 2015, doi: 10.1016/j.proeng.2015.01.440.

[24]       J. Kim, M. Kim, Y.-G. Shin, en M. Chung, ‘Accurate depth image generation via overfit training of point cloud registration using local frame sets’, Comput. Vis. Image Underst., vol. 226, p. 103588, jan. 2023, doi: 10.1016/j.cviu.2022.103588.

[25]       M. Laielli, J. Smith, G. Biamby, T. Darrell, en B. Hartmann, ‘LabelAR: A Spatial Guidance Interface for Fast Computer Vision Image Collection’, in Proceedings of the 32nd Annual ACM Symposium on User Interface Software and Technology, New Orleans LA USA: ACM, okt. 2019, pp. 987-998. doi: 10.1145/3332165.3347927.

[26]       D. Lee, O. C. Hamsici, S. Feng, P. Sharma, en T. Gernoth, ‘DeepPRO: Deep Partial Point Cloud Registration of Objects’, in 2021 IEEE/CVF International Conference on Computer Vision (ICCV), Montreal, QC, Canada: IEEE, okt. 2021, pp. 5663-5672. doi: 10.1109/ICCV48922.2021.00563.

[27]       Y. Lee, B. Yoo, en S.-H. Lee, ‘Sharing Ambient Objects Using Real-time Point Cloud Streaming in Web-based XR Remote Collaboration’, in The 26th International Conference on 3D Web Technology, Pisa Italy: ACM, nov. 2021, pp. 1-9. doi: 10.1145/3485444.3487642.

[28]       L. Li, R. Wang, en X. Zhang, ‘A Tutorial Review on Point Cloud Registrations: Principle, Classification, Comparison, and Technology Challenges’, Math. Probl. Eng., vol. 2021, pp. 1-32, jul. 2021, doi: 10.1155/2021/9953910.

[29]       S. Liu, D. Gao, P. Wang, X. Guo, J. Xu, en D.-X. Liu, ‘A Depth-Based Weighted Point Cloud Registration for Indoor Scene’, Sensors, vol. 18, nr. 11, p. 3608, okt. 2018, doi: 10.3390/s18113608.

[30]       B. Mahmood en S. Han, ‘3D Registration of Indoor Point Clouds for Augmented Reality’, p. 8.

[31]       R. A. Newcombe e.a., ‘KinectFusion: Real-Time Dense Surface Mapping and Tracking’.

[32]       S. Nilsson en B. Johansson, ‘Acceptance of augmented reality instructions in a real work setting’, in CHI ’08 Extended Abstracts on Human Factors in Computing Systems, Florence Italy: ACM, apr. 2008, pp. 2025-2032. doi: 10.1145/1358628.1358633.

[33]       A. Prouzeau, Y. Wang, B. Ens, W. Willett, en T. Dwyer, ‘Corsican Twin: Authoring In Situ Augmented Reality Visualisations in Virtual Reality’, p. 9, 2020.

[34]       #0K Srinivasan Ramachandran, ‘NOTE’: 10 februari 2023. Geraadpleegd: 17 februari 2023. [Online]. Beschikbaar op: https://github.com/aalavandhaann/go-icp_cython

[35]       J. Redmon, S. Divvala, R. Girshick, en A. Farhadi, ‘You Only Look Once: Unified, Real-Time Object Detection’. arXiv, 9 mei 2016. Geraadpleegd: 4 november 2022. [Online]. Beschikbaar op: http://arxiv.org/abs/1506.02640

[36]       R. B. Rusu, N. Blodow, en M. Beetz, ‘Fast Point Feature Histograms (FPFH) for 3D registration’, in 2009 IEEE International Conference on Robotics and Automation, Kobe: IEEE, mei 2009, pp. 3212-3217. doi: 10.1109/ROBOT.2009.5152473.

[37]       V. Sarode e.a., ‘PCRNet: Point Cloud Registration Network using PointNet Encoding’. arXiv, 3 november 2019. Geraadpleegd: 23 september 2022. [Online]. Beschikbaar op: http://arxiv.org/abs/1908.07906

[38]       A. Segal, D. Hähnel, en S. Thrun, ‘Generalized-ICP’, gepresenteerd bij Proc. of Robotics: Science and Systems, jun. 2009. doi: 10.15607/RSS.2009.V.021.

[39]       Sungjoon Choi, Q.-Y. Zhou, en V. Koltun, ‘Robust reconstruction of indoor scenes’, in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA: IEEE, jun. 2015, pp. 5556-5565. doi: 10.1109/CVPR.2015.7299195.

[40]       V. Tadic, A. Odry, I. Kecskes, E. Burkus, Z. Kiraly, en P. Odry, ‘Application of Intel RealSense Cameras for Depth Image Generation in Robotics’, vol. 18, 2019.

[41]       L. P. Tchapmi, V. Kosaraju, H. Rezatofighi, I. Reid, en S. Savarese, ‘TopNet: Structural Point Cloud Decoder’, in 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), jun. 2019, pp. 383-392. doi: 10.1109/CVPR.2019.00047.

[42]       T. Teo, ‘VIDEO-BASED POINT CLOUD GENERATION USING MULTIPLE ACTION CAMERAS’, Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci., vol. XL-4/W5, pp. 55-60, mei 2015, doi: 10.5194/isprsarchives-XL-4-W5-55-2015.

[43]       D. Tramberend e.a., ‘Avocado: A Distributed Virtual Environment Framework’, mei 2003.

[44]       R. Volk, J. Stengel, en F. Schultmann, ‘Building Information Modeling (BIM) for existing buildings — Literature review and future needs’, Autom. Constr., vol. 38, pp. 109-127, mrt. 2014, doi: 10.1016/j.autcon.2013.10.023.

[45]       Q. Wang, Y. Tan, en Z. Mei, ‘Computational Methods of Acquisition and Processing of 3D Point Cloud Data for Construction Applications’, Arch. Comput. Methods Eng., vol. 27, nr. 2, pp. 479-499, apr. 2020, doi: 10.1007/s11831-019-09320-4.

[46]       T. Wang e.a., ‘CAPturAR: An Augmented Reality Tool for Authoring Human-Involved Context-Aware Applications’, in Proceedings of the 33rd Annual ACM Symposium on User Interface Software and Technology, Virtual Event USA: ACM, okt. 2020, pp. 328-341. doi: 10.1145/3379337.3415815.

[47]       Y. Wang en J. M. Solomon, ‘Deep Closest Point: Learning Representations for Point Cloud Registration’. arXiv, 8 mei 2019. Geraadpleegd: 8 september 2022. [Online]. Beschikbaar op: http://arxiv.org/abs/1905.03304

[48]       Y. Wang en J. M. Solomon, ‘PRNet: Self-Supervised Learning for Partial-to-Partial Registration’. arXiv, 29 oktober 2019. Geraadpleegd: 8 september 2022. [Online]. Beschikbaar op: http://arxiv.org/abs/1910.12240

[49]       W. Wong, ‘What is Gumbel-Softmax?’, Medium. Geraadpleegd: 23 september 2022. [Online]. Beschikbaar op: https://towardsdatascience.com/what-is-gumbel-softmax-7f6d9cdcb90e

[50]       M. Wozniewski en P. Warne, ‘Towards in situ authoring of augmented reality content’, p. 4, 2011.

[51]       XuyangBai, ‘awesome-point-cloud-registration’. 21 oktober 2022. Geraadpleegd: 23 oktober 2022. [Online]. Beschikbaar op: https://github.com/XuyangBai/awesome-point-cloud-registration

[52]       J. Yang, H. Li, D. Campbell, en Y. Jia, ‘Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration’, IEEE Trans. Pattern Anal. Mach. Intell., vol. 38, nr. 11, pp. 2241-2254, nov. 2016, doi: 10.1109/TPAMI.2015.2513405.

[53]       Z. J. Yew en G. H. Lee, ‘RPM-Net: Robust Point Matching using Learned Features’. 30 maart 2020. doi: 10.1109/CVPR42600.2020.01184.

[54]       W. Yuan, B. Eckart, K. Kim, V. Jampani, D. Fox, en J. Kautz, ‘DeepGMR: Learning Latent Gaussian Mixture Models for Registration’. arXiv, 20 augustus 2020. Geraadpleegd: 8 september 2022. [Online]. Beschikbaar op: http://arxiv.org/abs/2008.09088

[55]       Z. Zhang, Y. Dai, en J. Sun, ‘Deep learning based point cloud registration: an overview’, Virtual Real. Intell. Hardw., vol. 2, nr. 3, pp. 222-246, jun. 2020, doi: 10.1016/j.vrih.2020.05.002.

[56]       J. Zhao, ‘Point Cloud Denoise’. 17 maart 2023. Geraadpleegd: 30 april 2023. [Online]. Beschikbaar op: https://github.com/aipiano/guided-filter-point-cloud-denoise

[57]       Zhirong Wu e.a., ‘3D ShapeNets: A deep representation for volumetric shapes’, in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA: IEEE, jun. 2015, pp. 1912-1920. doi: 10.1109/CVPR.2015.7298801.

[58]       Q.-Y. Zhou, J. Park, en V. Koltun, ‘Fast Global Registration’, in Computer Vision – ECCV 2016, vol. 9906, B. Leibe, J. Matas, N. Sebe, en M. Welling, Red., in Lecture Notes in Computer Science, vol. 9906. , Cham: Springer International Publishing, 2016, pp. 766-782. doi: 10.1007/978-3-319-46475-6_47.

[59]       Q.-Y. Zhou, J. Park, en V. Koltun, ‘Open3D: A Modern Library for 3D Data Processing’, p. 6.

[60]       Y. Zhou en O. Tuzel, ‘VoxelNet: End-to-End Learning for Point Cloud Based 3D Object Detection’, in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, USA: IEEE, jun. 2018, pp. 4490-4499. doi: 10.1109/CVPR.2018.00472.

[61]       L. Zhu, C. Lin, D. Liu, X. Li, en F. Gómez-Fernández, ‘Deep Models with Fusion Strategies for MVP Point Cloud Registration’. arXiv, 18 oktober 2021. Geraadpleegd: 4 november 2022. [Online]. Beschikbaar op: http://arxiv.org/abs/2110.09129

[62]       L. Zhu e.a., ‘Point Cloud Registration using Representative Overlapping Points’. arXiv, 6 juli 2021. Geraadpleegd: 10 oktober 2022. [Online]. Beschikbaar op: http://arxiv.org/abs/2107.02583

[63]       vinit sarode, ‘Learning3D: A Modern Library for Deep Learning on 3D Point Clouds Data’, Medium. Geraadpleegd: 4 november 2022. [Online]. Beschikbaar op: https://medium.com/@vinitsarode5/learning3d-a-modern-library-for-deep-l…;

Download scriptie (20.06 MB)
Universiteit of Hogeschool
Vrije Universiteit Brussel
Thesis jaar
2023
Promotor(en)
Ir. Joris De Winter, Prof. Dr. Ir. Bram Vanderborght, Prof. Dr. Ir. Tom Verstraten
Thema('s)