Geometry & Recognition

다각형을 삼각 분할하다 보면 일부 삼각형 중에는 한 변의 길이가 나머지 변의 길이에 비해서 매우 작거나 또는 매우 큰 경우가 많이 나타난다. (이런 경우에 외접원의 반지름이 매우 커진다). 삼각 분할에서 만들어진 삼각형을 이용하여 mesh을 형성할 경우에 분할된 삼각형이 보다 균일한  경우가 더 좋을 것이다.

균일한 삼각 분할을 만들기 위해서 이미 완성된 분할 결과를 가지고 다시 수정 작업을 거쳐야 한다. 삼각 분할 결과로 나타난 각 내부 edge(AC, diagonal)에 대해서 그 edge가 대각선이 되는 사각형(ABCD)을 찾고, 이 사각형이 convex인 경우에 한하여 아래의 과정을 적용한다.

1. 사각형 ABCD를 분할하는 두 개의 삼각형 ABC, ACD의 외접원의 반지름의 최솟값을 찾는다.
   min(radius(ABC), radius(ACD))
2. 사각형 ABCD에서 원래 대각선(AC)과 교차하는 대각선(BD)이 나누는 두 개의 삼각형 BCD, BDA의 외접원의 반지름의 최솟값을 찾는다. 
   min(radius(BCD) and radius(BDA))
3. 원래 대각선(AC)이 나누는 삼각형 외접원의 최소 반지름이 교차 대각선(BD)이 나누는 삼각형의 최소 반지름보다 더 작은 경우 이 대각선을 기존의 edge(AC)와 바꾼다. (바꾼 edge는 더 이상 바꾸지 않는다)
4. 다른 내부 edge에 대해서 동일한 과정을 반복한다.

** 내부 edge의  FLIP;

** 원래의 삼각화(Ear Clipping)

**최적화 후

/**
** http://blog.naver.com/helloktk/80051332733 에서 옮김.
*/

(1) closest pair in the planar point set
     * brute force : O(n^2) --> O(n log n), see also divide and conquer algorithm.
     * ref : http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html 

(2) simplicity of polygon :

Shamos-Hoey Algorithm

(3) voronoi diagram :Fortune algorithm

(4) segment intersection : Bentley-Ottmann Algorithm

      * 파란색 점 : sweep-line과 교차하는 세그먼트들 간의(붉은색으로 표시)의 교차점으로(before sweep-line)로 point 이벤트 큐에 들어간다.
      * 청록색 점 : sweep-line이 지나간 후의 교차점.

sweep-line알고리즘을 구현하는데서 스텝별로 쪼개서 구현하려고 하니 조금 귀찮은 작업들이 많아진다 (DC에 그려지는 것을 자동으로 저장하는 부분을 만들어서 매 스텝마다 캡처하는 작업은 줄였다). 그러나 근본적인 문제는 입력되는 데이터에 degeneracy가 있는 경우다. 이것 때문에 가장 기본적인 세그먼트 intersection 부분부터 다시 살펴보아야 했다.

/**
** http://blog.naver.com/helloktk/80051980882 에서 옮긴 글.
*/

(1) cell image : 원본 영상을 이진화(Otsu-알고리즘)시킨 결과다. 두 군데서 셀이 겹쳤다. 단순히 connected component labeling을 적용해서는 이를 분리할 수 없다.

(2) distance transform : distance 변환 결과에 blurring을 추가한 결과다. distance 변환은 셀 외부는 셀로부터의 거리를, 셀 내부는 배경으로부터의 거리의 음의 값을 취한 후 전체적으로 다시 리스케일한 것이다.  blurring은 watershed 알고리즘이 보다 정확히 동작하는데 필요하다.

(3) watershed segmentation: 분할된 영역의 label이 나온다(경계 label=0). 이 label을 가지고  false coloring을 한 결과다. 이 알고리즘은 논문 "The Watershed Transform: Definitions, Algorithms and Parallelization Strategies", Jos B.T.M. Roerdink and Arnold Meijster의 내용을 구현한 것이다. 8-방향 픽셀 연결성을 이용했다.

(4) final result; watershed 결과를  mask로 이용해서 이미지를 분할한 것이다. 겹친 cell이 분리되었다.

다른 예:

/**
** http://blog.naver.com/helloktk/80051779331 에서 옮긴 자료.
*/