Deux approches courantes pour l'adaptation plane sont RANSAC et Hough. En voici une comparaison des performances:
https://www.researchgate.net/publication/259519997_Continuous_plane_detection_in_point-cloud_data_based_on_3D_Hough_Transform
Comme beaucoup de problèmes en géométrie algorithmique et de traitement d'image, plutôt que de considérer ce qui est « le plus rapide » considèrent ce qui est optimal pour votre application en termes de performance, l'effort de développement, et Coût. La recherche de l'algorithme le plus rapide possible pourrait vous mener vers un coût et une complexité effrayants, alors que vous pourriez mettre en place une chaîne de traitement des données d'algorithmes relativement plus simples et suffisamment rapides pour offrir une expérience agréable et agréable à l'utilisateur. En bref, je recommande de commencer avec un ajustement de plan Hough. Les algorithmes de transformée de Hough sont relativement faciles à écrire (une fois que vous maîtrisez les bases), et les paramètres de modification sont intuitifs.
https://en.wikipedia.org/wiki/Hough_transform
L'une des raisons d'écrire votre propre algorithme est que vous serez en mesure de mieux comprendre les changements qui doivent être apportés une fois (pas si) vous découvrez les données de nuages de points est plus bruyant et moins bien comporté que l'on voudrait.
Atteindre une bonne vitesse va compter sur un certain nombre de facteurs, y compris ceux-ci:
- nuage point de pré-traitement. Recherchez des moyens de décomposer le nuage de points en morceaux pouvant être traités plus rapidement.
- Paramétrage. Une fois les données prétraitées, vous pouvez définir des limites de recherche plus étroites pour votre algorithme d'ajustement de plan. Par exemple, n'essayez que des ajustements d'avion à quelques degrés de la verticale. Vous devrez également choisir des paramètres pour trouver un équilibre entre la vitesse et la qualité de l'ajustement.
- Qualité des données 3D. C'est un grand sujet en soi, et le plus tôt vous pouvez regarder de plus près les problèmes dans les données le mieux.
- Que signifie "en temps réel". Même pour les applications graphiques 3D qui impliquent une interaction de l'utilisateur, il peut être moins important de réaliser un temps réel basé strictement sur les spécifications (mises à jour à N images/seconde) que de présenter une interface simple et fluide.
- Multithreading et parallélisme.
- Affichage 3D. Un autre grand sujet.
Pré-traitement. Vous n'avez pas besoin d'ajuster des plans de taille arbitraire à des nuages de points arbitraires: à la place, vous devez adapter les murs et peut-être les planchers et les plafonds. Pour les algorithmes de Hough, cela signifie que vous pouvez limiter la plage sur laquelle les paramètres sont testés, et donc accélérer le traitement. Plutôt que d'essayer de trouver tous les ajustements plans pour le nuage de points complet original, trouvez des moyens de décomposer le nuage de points en groupes de sous-nuages auxquels les tests d'ajustement de plan peuvent être exécutés plus efficacement.PCL peut calculer les normales de surface pour vous. Si vous pouvez identifier des amas de normales de surface orientées à peu près dans la même direction, et ensuite essayer des ajustements plans pour des grappes individuelles, vous devriez être capable d'accélérer considérablement les choses. De plus, pour votre premier passage, vous aurez probablement besoin de sous-échantillonner vos données et d'essayer de faire relativement moins de points. Ceci est analogue à la création d'une "pyramide d'images" pour le traitement 2D.
Les Octrees sont des moyens simples et agréables de diviser l'espace pour les requêtes, les tests de collision, etc. Un octree divise un espace en huit nœuds ou "octants". Cela peut être imaginé comme couper un cube en huit cubes plus petits. Chaque octant est ensuite divisé en huit octants, et ainsi de suite. Si un octant (un nœud) ne contient pas de points, vous n'avez pas besoin de le diviser davantage.
https://en.wikipedia.org/wiki/Octree
Paramétrisation. Les descriptions ci-dessus doivent indiquer clairement que si vous pouvez pré-traiter les données en simplifiant et/ou en décomposant le nuage de points bruts d'origine, vous pourrez tester des recherches beaucoup plus précises qui s'exécuteront plus rapidement.
D'ailleurs, vous n'avez probablement pas besoin d'une grande précision dans les ajustements en plan. Vous pouvez générer des ajustements raisonnablement bons, puis ajuster ces ajustements pour générer des plafonds, des murs et des planchers à angle droit les uns par rapport aux autres.
Qualité des données 3D. Le Kinect v2 est un appareil à temps de vol présentant des problèmes inhérents de précision de mesure. Par exemple, si vous prenez une seule image d'un mur plat et que vous vérifiez ensuite les valeurs de profondeur, vous remarquerez une certaine gêne non planaire dans les coins de l'image. Si vous regardez la plage (ou l'écart-type) des valeurs de profondeur à chaque pixel (x, y) sur plusieurs images, vous remarquerez également des différences de bruit entre les pixels centraux et les pixels de bord.
Une fois que vous avez effectué un ajustement plan, générez une mesure de la qualité d'ajustement. Cela nécessite de remonter les données pour calculer les distances point à plan des points utilisés pour le calcul. (Pour l'accélérer, n'utilisez que tous les points N ou échantillonnez au hasard les points.) Lorsque vous modifiez les paramètres, vous verrez les effets en termes de vitesse et de qualité d'ajustement.
Temps réel vs. Lissé de façon perceptible. Si vous avez seulement besoin de l'utilisateur pour déplacer les meubles en temps réel, il est préférable de passer plus de temps à générer les ajustements initiaux.
multithreading/Parallélisme Pour gérer l'entrée de données, montage plan et l'interface utilisateur vous presque certain devez penser sérieusement à multithreading. Pour tester les algorithmes, vous travaillez sur le thread d'interface utilisateur juste pour commencer, mais c'est limitant.
Une application comme celle-ci demande CUDA ou OpenCL. Pour l'affichage 3D, vous utiliserez la carte graphique de toute façon. Bien que vous n'ayez pas besoin de sauter tout de suite dans la programmation GPU, il est utile de garder à l'esprit comment les algorithmes pourraient être parallélisés.
Affichage 3D. Aviez-vous prévu d'utiliser Direct3D ou OpenGL pour l'affichage et l'interaction 3D? La mise en œuvre d'un logiciel permettant à l'utilisateur «d'ajouter en temps réel des modèles 3D de différents types de meubles» suggère que vous devrez compter sur la carte graphique.
Si vous pouvez afficher le nuage de points dans une vue 3D, vous n'avez peut-être même pas besoin d'ajustement d'avion. Vous pouvez même vous en sortir avec la détection de collision: si le modèle 3D d'une chaise rencontre un groupe de points (par exemple un mur), vous pouvez simplement détecter cette collision plutôt que d'essayer d'ajuster des plans pour définir des limites. Les octants et d'autres techniques de division de l'espace aideront à accélérer les tests de collision.
La société Matterport (http://matterport.com/) a développé quelque chose qui ressemble beaucoup à ce que vous décrivez. Si rien d'autre vous pouvez essayer leur logiciel et envisager ce qui pourrait être amélioré/adapté à vos besoins.
Cela m'a définitivement donné beaucoup à réfléchir et à essayer d'optimiser tout. Jusqu'à présent, j'ai essayé beaucoup de méthodes intégrées pour détecter des avions dans la pièce comme ransac, prosac, lmeds, ... Je suis maintenant à la recherche d'un didacticiel de transformation descendant, vu que je suis assez nouveau pour travailler avec des modèles 3D, mais tout ce que je trouve est des explications pour le traitement d'image 2D. Savez-vous où je pourrais trouver des informations pour les images 3D? Aussi merci de prendre le temps pour toutes les informations jusqu'à présent, je n'aurais même pas considéré hough et le pré-traitement sans tout cela :) – Kiiiieeeeuuuw
Le temps de traitement et la mémoire requise pour Hough échelles avec le nombre de variables nécessaires pour décrire une forme géométrique.Pour un avion, vous avez besoin de quatre variables, et une simple technique de force brute nécessiterait beaucoup de temps et de mémoire, bien que vous puissiez limiter la plage de recherche pour votre application (par exemple, les avions proches de la verticale ou de l'horizontale). En outre, une technique d'accélération de l'examen des ajustements localisés est d'abord décrite dans https://en.wikipedia.org/wiki/Hough_transform#3-D_Kernel-based_Hough_transform_for_plane_detection_.283DKHT.29. – Rethunk