Geometry & Recognition

(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 에서 옮긴 자료.

* 구현: https://kipl.tistory.com/66

https://kipl.tistory.com/299