위상학적 골격

Topological skeleton
토폴로지를 보존하는 씬닝 알고리즘을 사용하여 계산된 형태와 그 골격.

형상 분석에서, 어떤 형태의 골격(또는 위상학적 골격)은 그 경계와 동일한 그 형태의 얇은 버전이다.골격은 보통 연결성, 위상, 길이, 방향, 폭과 같은 형상의 기하학적, 위상학적 특성을 강조한다.형상 경계까지의 점의 거리와 함께, 골격은 형상을 표현하는 역할도 할 수 있다(형상을 재구성하는 데 필요한 모든 정보를 포함한다).

해골은 기술 문헌에서 몇 가지 다른 수학적 정의를 가지고 있으며, 해골의 연산 알고리즘도 다양하다.직선 골격, 형태학적 골격 등 다양한 변형 골격도 찾아볼 수 있다.

기술 문헌에서 스켈레톤과 내축의 개념은 일부 저자에 의해 상호 교환적으로 사용되고 있는 반면,[1][2][3][4][5] 일부 다른 저자들은[6][7][8] 이 개념들을 연관성이 있는 것으로 간주하지만 동일하지는 않다.마찬가지로 골격화와 얇아지는 개념도 일부에서는 동일하다고 간주하고,[2] 다른 일부에서는 동일하다고 보지 않는다.[6]

해골은 광학 문자 인식, 지문 인식, 육안 검사 또는 압축 등의 목적으로 컴퓨터 비전, 이미지 분석, 패턴 인식, 디지털 이미지 처리 등에 널리 사용된다.생명과학에서 뼈대는 다양한 생물학적 척도로 단백질 접힘과[9] 식물 형태학을 특징짓는 광범위한 용도를 발견했다.[10]

수학적 정의

해골은 기술 문헌에서 몇 가지 다른 수학적 정의를 가지고 있다. 해골의 대부분은 연속적인 공간에서 유사한 결과를 가져오지만, 보통 이산적인 공간에서는 다른 결과를 낳는다.

화재 전파 모델의 지점 확인

주요기사 : 잔디불변형

메사추세츠주 베드포드에 있는 한스컴 공군기지에 있는 공군 캠브리지 연구소의 해리 블럼은[11] 그의 세미나의 논문에서 필드가 주어진 형상의 형태를 갖는 잔디밭에서 화재 전파의 직관적인 모델을 사용하여 형상의 골격을 계산하기 위한 내적 축을 정의했다.만약 풀밭의 경계에 있는 모든 지점에 동시에 불을 지른다면, 해골은 두 개 이상의 파도와 만나는 지점, 즉 해골의 집합이다.이러한 직관적인 설명은 많은 더 정확한 정의의 출발점이다.

최대 Disk(또는 볼)의 중심

디스크(또는 공) B는 다음과 같은 경우에 세트 A에서 최대치라고 한다.

  • 및
  • 다른 디스크 D에 B가 포함되어 있으면

A 형상의 골격을 정의하는 한 가지 방법은 A에 있는 모든 최대 디스크의 중심 집합이다.[12]

양탄젠트 원의 중심

A 형상의 골격은 두 개 이상의 위치에서 A의 경계와 접촉하는 디스크의 중심 집합으로도 정의할 수 있다.[13]이 정의는 스켈레톤 점이 형상 경계로부터 등거리이며 블럼의 내축 변환과 수학적으로 동등하다는 것을 보장한다.

거리 함수의 능선

해골의 많은 정의는 거리 함수의 개념을 사용하는데, 이것은 A형 내부의 각 점 x에 대해 A의 경계에서 가장 가까운 점까지의 거리를 되돌리는 함수다.거리 함수를 사용하는 것은 그것의 계산이 비교적 빠르기 때문에 매우 매력적이다.

거리 함수를 이용한 골격의 정의 중 하나는 거리 함수의 능선으로서이다.[6]문헌에는 골격이 거리 변환에서 "로컬하게 최대"인 점들로 구성된다는 잘못된 설명이 공통적으로 있다.거리 변환과 그 결과의 골격을 대충 비교해도 알 수 있듯이, 이것은 단순히 그렇지 않다.능선은 높이가 다를 수 있으므로 능선의 지점은 능선의 바로 이웃 지점보다 낮을 수 있다.따라서 능선에 속하더라도 국부적 최대치가 아니다.그러나 그것은 지상의 거리보다 수직으로 덜 떨어져 있다.그렇지 않으면 경사면의 일부가 될 것이다.

기타 정의

  • 거리 함수에 업스트림 세그먼트가 없는 점.점 x의 업스트림은 최대 구배 경로를 따르는 x에서 시작하는 세그먼트다.
  • 거리 함수의 기울기가 1(또는 동등하게 정의되지 않음)과 다른 점
  • 토폴로지를 보존하고 테두리에 동일한 가능한 최소 선 집합

스켈레톤화 알고리즘

연속적인 세트뿐만 아니라 디지털 이미지의 도형에 대한 해골을 계산하는 알고리즘은 매우 다양하다.

  • 형태론적 연산자 사용(형태론적 골격[13] 참조)
  • 형태론적 연산자를 형상 기반 가지치기[14] 방식으로 보완
  • 경계 단면으로부터의 거리의 교차점 사용
  • 곡선 진화 사용
  • 레벨 세트[8] 사용
  • 거리 함수의[6] 능선점 찾기
  • 토폴로지를 변경하지 않고 수렴할[18] 때까지 모양을 "감기"

스켈레톤화 알고리즘은 때때로 출력 스켈레톤에 원하지 않는 분기를 만들 수 있다.가지치기 알고리즘은 종종 이러한 가지를 제거하는데 사용된다.

참고 항목

메모들

  1. ^ Jain, Kasturi & Schunck(1995), 섹션 2.5.10, 페이지 55.
  2. ^ a b 곤잘레스 & 우즈(2001), 섹션 11.1.5, 페이지 650
  3. ^ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
  4. ^ 더거티(1992년).
  5. ^ 오그니에비치(1995)
  6. ^ a b c d A. K. 자인(1989), 9.9, 페이지 382.
  7. ^ 세라(1982년).
  8. ^ a b 세션(1999), 제17.5.2절, 페이지 234.
  9. ^ 아베싱헤 외(2008)
  10. ^ 벅치(2014년)
  11. ^ 해리 블럼 (1967년)
  12. ^ A. K. 자인(1989), 9.9, 페이지 387.
  13. ^ a b 곤잘레스 & 우즈(2001), 섹션 9.5.7, 페이지 543.
  14. ^ 아베싱헤 외 (2008).
  15. ^ R. 킴멜, D. 셰이크, N. Kiryati, A. M. Bruckstein.https://www.cs.technion.ac.il/~ron/paper/skeletonization_CVIU_1995.pdf Comp.시각 및 이미지 이해, 62(3):382-391, 1995.
  16. ^ 탄넨바움(1996)
  17. ^ 바이, 룽인&웬유(2007년).
  18. ^ A. K. 자인(1989), 9.9, 페이지 389.

참조

  • Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), "Segmentation-free skeletonization of grayscale volumes for shape understanding", IEEE Int. Conf. Shape Modeling and Applications (SMI 2008) (PDF), pp. 63–71, doi:10.1109/SMI.2008.4547951, ISBN 978-1-4244-2260-9, S2CID 15148296.
  • Abeysinghe, Sasakthi; Ju, Tao; Baker, Matthew; Chiu, Wah (2008), "Shape modeling and matching in identifying 3D protein structures" (PDF), Computer-Aided Design, Elsevier, 40 (6): 708–720, doi:10.1016/j.cad.2008.01.013
  • Bai, Xiang; Longin, Latecki; Wenyu, Liu (2007), "Skeleton pruning by contour partitioning with discrete curve evolution" (PDF), IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (3): 449–462, doi:10.1109/TPAMI.2007.59, PMID 17224615, S2CID 14965041.
  • Blum, Harry (1967), "A Transformation for Extracting New Descriptors of Shape", in Wathen-Dunn, W. (ed.), Models for the Perception of Speech and Visual Form (PDF), Cambridge, Massachusetts: MIT Press, pp. 362–380.
  • Bucksch, Alexander (2014), "A practical introduction to skeletons for the plant sciences", Applications in Plant Sciences, 2 (8): 1400005, doi:10.3732/apps.1400005, PMC 4141713, PMID 25202647.
  • Cychosz, Joseph (1994), Graphics gems IV, San Diego, CA, USA: Academic Press Professional, Inc., pp. 465–473, ISBN 0-12-336155-9.
  • Dougherty, Edward R. (1992), An Introduction to Morphological Image Processing, ISBN 0-8194-0845-X.
  • Gonzales, Rafael C.; Woods, Richard E. (2001), Digital Image Processing, ISBN 0-201-18075-8.
  • Jain, Anil K. (1989), Fundamentals of Digital Image Processing, Bibcode:1989fdip.book.....J, ISBN 0-13-336165-9.
  • Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Machine Vision, ISBN 0-07-032018-7.
  • Ogniewicz, R. L. (1995), "Automatic Medial Axis Pruning Based on Characteristics of the Skeleton-Space", in Dori, D.; Bruckstein, A. (eds.), Shape, Structure and Pattern Recognition, ISBN 981-02-2239-4.
  • Petrou, Maria; García Sevilla, Pedro (2006), Image Processing Dealing with Texture, ISBN 978-0-470-02628-1.
  • Serra, Jean (1982), Image Analysis and Mathematical Morphology, ISBN 0-12-637240-3.
  • Sethian, J. A. (1999), Level Set Methods and Fast Marching Methods, ISBN 0-521-64557-3.
  • Tannenbaum, Allen (1996), "Three snippets of curve evolution theory in computer vision", Mathematical and Computer Modelling, 24 (5): 103–118, doi:10.1016/0895-7177(96)00117-3.

오픈 소스 소프트웨어

외부 링크