Przegląd najpopularniejszych koncepcji szkieletyzacji obrazów 3D

• Autorzy: Janaszewski M. , Babout L.

Warianty tytułu

EN

Review of popular skeleton conception of 3D images

• Języki publikacji: PL

Abstrakty

PL

Szkieletyzacja obrazów to technika upraszczająca wizualną reprezentację obiektu do zbioru połączonych, cienkich (grubości jednego piksela) łuków i odcinków. W przypadku obrazów 3D na szkielet mogą składać się dodatkowo powierzchnie. Na przestrzeni kilkudziesięciu lat badań nad metodami szkieletyzacji wypracowano wiele rozwiązań, które można zaliczyć do trzech podstawowych kategorii: algorytmy pocieniania, algorytmy oparte o diagram Voronoi oraz koncepcje budowane na bazie transformacji odległości. Wielość rozwiązań spowodowana jest tym, że do dnia dzisiejszego nie zbudowano jeszcze algorytmu szkieletyzacji, który byłby uniwersalny, zwracający zadowalające wyniki dla wszystkich typów obrazów. Stworzone dotychczas rozwiązania posiadają istotne wady, co ogranicza ich zastosowanie do pewnych typów obrazów. Niniejszy artykuł charakteryzuje przedstawicieli trzech wspomnianych wyżej klas algorytmów szkieletyzacji obrazów 3D. Ponadto autorzy zamieścili dyskusję wad i zalet proponowanych rozwiązań.

EN

The skeleton of images is the technique simplifying visual representation of object to collection joined, thin (thickness of one pixel) arcs and segments. In case of 3D images, the skeleton can contains surfaces too. Over some dozen years of the skeleton methods investigations, many solutions were worked out. It was possible to accept them to three basic categories: thinings algorithms, algorithms leaning on Voronoi diagram, as well as conceptions built on base of distance transformation.

Słowa kluczowe

PL

szkieletyzacja obrazów; 3D; algorytmy pocieniania; transformacja odległości; algorytmy oparte o diagram Voronoi

• Wydawca: Wyższa Szkoła Informatyki i Umiejętności
• Czasopismo: Zeszyty Naukowe Wyższej Szkoły Informatyki
• Rocznik: 2007
• Tom: Vol. 6, Nr 1
• Strony: 59--72
• Opis fizyczny: Bibliogr. 34 poz., rys.

Twórcy

autor

Janaszewski M.

autor

Babout L.

• Katedra Informatyki Stosowanej, Politechnika Łódzka

Bibliografia

• [1] Attali D., Montanvert A.: Semicontinous skeletons of 2D and 3D shapes, presented at 2nd International Workshop on Visual Form, Singapore, 1994.
• [2] Bai X., Latecki L., Liu J.: Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 29, pp. 449--462, 2007.
• [3] Berg M., Kreveld M., Overmars M., Schwarzkopf O.: Geometria obliczeniowa, algorytmy i zastosowania: WNT, 2007.
• [4] Bertrand G., Aktouf Z.: A three-dimensional thinning algorithm using subfields, Proceedings of the SPIE The International Society for Optical Engineering, vol. 2356, pp. 113-24, 1995.
• [5] Bitter I., Kaufman A. E., Sato M.: Penalized-distance volumetric skeleton algorithm, IEEE Transactions on Visualization and Computer Graphics, vol. 7, pp. 195-206.
• [6] Blum H.: Transformation for Extracting New Descriptions of Shape, in Models for the Perception of Speech and Visual Form, 1967, pp. 362--380.
• [7] Cornea N., Silver D., Min P.: Curve-skeleton applications, http://www.caip.rutgers.edu/~cornea/CurveSkelApp/, 2007.
• [8] Couprie M., Zrour R.: Discrete bisector function and Euclidean skeleton.
• [9] Di Ruberto C.: Recognition of shapes by attributed skeletal graphs, Pattern Recognition, vol. 37, pp. 21-23, 2004.
• [10] Etzion M., Rappoport A.: Computing Voronoi skeletons of a 3-D polyhedron by space subdivision, Computational Geometry, vol. 21, pp. 87-120, 2002.
• [11] Ferley E., Cani M.-P., Attali D.: Skeletal Reconstruction of Branching Shapes, Computer Graphics Forum, vol. 16, pp. 283-293, 1997.
• [12] Gagvani N., Silver D.: Parameter-controlled volume thinning, Graphical Models and Image Processing, vol. 61, pp. 149-64.
• [13] Kong T. Y.:A digital fundamental group, Computer Graphics, vol. 13, pp. 159-166, 1989.
• [14] Ma C. M.: A 3D fully parallel thinning algorithm for generating medial faces, Pattern Recognition Letters, vol. 16, pp. 83–87, 1995.
• [15] Ma C. M., Sonka M.: A fully parallel 3D thinning algorithm and its applications, Computer Vision and Image Understanding, vol. 64, pp. 420–433, 1996.
• [16] Malandain G., Fernandez Vidal S.: Euclidean skeletons, Image and Vision Computing, vol. 16, pp. 317-27.
• [17] Naf M., Szekely G., Kikinis R., Shenton M. E., Kubler O.: 3D Voronoi skeletons and veir usage for the characterization and recognition of 3D organ shape, Computer Vision and Image Understanding, vol. 66, pp. 147-161, 1997.
• [18] Palagyi K., Kuba A.: A parallel 3D 12-subiteration thinning algorithm, Graphical Models and Image Processing, vol. 61, pp. 199-221, 1999.
• [19] Palagyi K., Sorantin E., Balogh E., Kubal A., Halmai C., Erdohelyi B., Hausegger K.: A sequential 3D thinning algorithm and its medical applications, presented at Information-Processing-in-Medical-Imaging.-17th-International-Conference, 2001.
• [20] Pervouchine V.,. Leedham G, Melikhov K.: Handwritten character skeletonisation for forensic document analysis, in Proceedings of the 2005 ACM symposium on Applied computing. Santa Fe, New Mexico: ACM Press, 2005, pp. 754-758.
• [21] Pizer S. M., Gerig G., Joshi S., Aylward S. R.: Multiscale medial shape-based analysis of image objects, Proceedings of the IEEE, vol. 91, pp. 1670-9.
• [22] Preparata F. P., Shamos M. I.: Computational Geometry. New York: Springer-Verlag, 1985.
• [23] Pudney C.: Distance-based skeletonization of 3D images.
• [24] Saha P. K., Chaudhuri B. B., Majumder D. D.: A new shape preserving parallel thinning algorithm for 3D digital images, Pattern Recognition, vol. 30, pp. 1935-55, 1997.
• [25] Schirmacher H., Zockler M., Stalling D., Hege H. C.: Boundary surface shrinking-a continuous approach to 3D center line extraction.
• [26] Shamir A., Shaham A.: Skeleton based solid representation with topology preservation, Graphical Models, vol. 68, pp. 307-21.
• [27] Sorantin E., Halmai C., Erdôhelyi B., Palágyi K., Nyúl L. G., Ollé L. K., Geiger B., Lindbichler F., et al.: Spiral-CT-based assessment of tracheal stenoses using 3-D-skeletonization, IEEE Transactions on Medical Imaging, vol. 21, pp. 263-273, 2002.
• [28] Svensson S., Nystrom I., Sanniti di Baja G.: Curve skeletonization of surface-like objects in 3D images guided by voxel classification, Pattern Recognition Letters, vol. 23, pp. 1419-26, 2002.
• [29] Torsello A., Hancock E. R.: A Skeletal Measure of 2D Shape Similarity, Computer Vision and Image Understanding, vol. 95, pp. 1 - 29, 2004.
• [30] Tran S., Shih L.: Efficient 3D binary image skeletonization, presented at Computational Systems Bioinformatics Conference Workshops, 2005.
• [31] Wade L., Parent R. E.: Automated generation of control skeletons for use in animation, Visual Computer, vol. 18, pp. 97-110.
• [32] Wang T., Basu A.: A note on a fully parallel 3D thinning algorithm and its applications, Pattern Recognition Letters, vol. 28, pp. 501--506, 2007.
• [33] Whichello A. P., Hong Y.: Reconstruction of character skeletons using Gabor filter features, Electronics Letters, vol. 31, pp. 1911-1912, 1995.
• [34] Zhou Y., Toga A. W.: Efficient skeletonization of volumetric objects, IEEE Transactions on visualization graphics, vol. 5, pp. 196-209, 1999.