Документ взят из кэша поисковой машины. Адрес оригинального документа : http://graphics.cs.msu.ru/sites/default/files/download/gc2009_PointCloudSegmentation.pdf Дата изменения: Tue Oct 13 15:48:58 2009 Дата индексирования: Sun Apr 10 02:22:11 2016 Кодировка:

A. B. Velizhev, R.V. Shapovalov, D.Potapov, L.Tretiak, A. Konushin Department of Computational Mathematics and Cybernetics Moscow State University, Moscow, Russia avelizhev@graphics.cs.msu.ru, shapovalov@graphics.cs.msu.ru, potapov@graphics.cs.msu.ru, tretiak@graphics.cs.msu.ru, ktosh@graphics.cs.msu.ru
R- (R-Tree) [4] . . 2 . Seg-Tree . 4 , Seg-Tree. .


, , . , , kd- - . , , . , . , Seg-Tree, . . : , , , , .

2.
, .

2.1
- kd- [5]. k- [7]. 2006 [2], . , (, ). , , , . R-, [4]. . R- . , . , R- , . , R- , . , ( ). ,

1.
. , . . . - , . , Seg-Tree, , [6]. . Seg-Tree , .


, [3] . - , cR-. , . ( . 3).

3. SEG-TREE
R- [4] , . (R- CAD-), . R- : · ; · ; · . .

2.2
. . [1]. . . , [6] . , . . , , . , (, ). - . , , . kd- - (Wang et al., 2004, Bucksch et al., 2006). (Biosca et al., 2008) -. , . , . -, . -, , . . , , , . -, . , .

3.1
. , . , minDist (. 1) , , , . , , . , . , . . , , , . , , . . , . , , . . , . Dist / minDist. Dist , . . . . ,


minDist == 0 ( ). , minDist. pruneDist ­ . , , minDist , pruneDist.

4.
[6] Seg-Tree.. . , [6] , Seg-Tree. . 3.

1: Dist, MinDist MaxDist. 4 .

2: Seg-Tree. , , , , , . . , k , . , , , . , - , . , , (. 3c).. .

3.2
, . [3] -. , - ( ) , .

3.3
, , . , ( L1) - R.

5.
the [6]. SegTree . , , . , , . (. 4.).

3.4 Seg-Tree
, R, Seg-Tree. , 3.1, minDist Dist. - . 1 64 4 16 . . 2 Seg-Tree.


, , .

7.
[1] Biosca, J., Lerma, J., 2008. Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods. ISPRS Journal of Photogrammetry and Remote Sensing, Volume 63(1), Pages 84-98 [2] Boubekeur, T., Heidrich, W., Granier, X., Schlick, C., 2006. Volume-Surface Trees. Computer Graphics Forum (Proceedings of EUROGRAPHICS 2006), 25(3), pp. 399-406 [3] Brakatsoulas S., Pfoser D., Theodoridis Y., 2002. Revisiting R-tree construction principles. Proceedings of the 6th East European Conference on Advances in Databases and Information Systems, pp. 149-162. [4] Guttman A., 1984. R-trees: a dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pp. 47-57. [5] Jackins, C., Tanimoto S., 1983. Quad-trees, oct-trees, and ktrees. A generalized approach to recursive decomposition of Euclidean space, IEEE Transactions, Pattern Analysis and Machine Intelligence, vol. PAMI-5, pp. 533-539 [6] Rabbani T., van den Heuvel, F., Vosselmann, G., 2006, Segmentation of point clouds using smoothness constraint. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 36(5), pp. 248-253 [7] Sankaranarayanan, J., Samet, H., Varshney, A., 2007. A fast all nearest neighbor algorithm for applications involving large point-clouds. Computers and Graphics, 31(2), pp. 157-174

6.
, . , , , . Seg-Tree . : · ; · ; · , .

8.
», 182. 3: Seg-Tree. a) Seg-Tree, b) c) . «

Robust LIDAR data segmentation using compact point clusters Abstract
Segmentation algorithms, which work with individual points, are sensitive to measurement noise and are computational-intensive. In recent years several segmentation algorithms based on hierarchical structure, like octree or kd-tree, were proposed. However, such plane-based partitioning procedures cannot produce correct results for various complex scenes with holes and occlusions. Continuous surfaces are often split and neighbor points are inserted into different tree nodes that degrade the segmentation result. In this paper we introduce a new hierarchical tree, named Seg-Tree, and show its effectiveness by applying to the popular segmentation algorithm region grow. Our version of this algorithm is robust to the noise and produce stable segmentation with lesser dependency of angular threshold. SegTree is created using special over-segmentation procedure that produces compact leaves both for smooth and heavily noisy point sample surfaces. The over-segmentation procedure is performed using R-Tree construction with k-means clustering technique.

4: : . a), b) ­ Seg-tree, 5° 10° . c), d), - . , [6], , . , Seg-Tree . , .