디지털 위상 기하학(digital topology)

<디지털위상기하학(digital topology)>
- 영상에 구멍(hole) 등 특정 물체의 수 또는 존재 여부에 관심을 가지는 경우,
  한 영상의 이들 기본적 성절의 조사를 '디지털위상기하학' 또는 '영상위상기하학(image topology)라고 한다

>>nt=~im2bw(n,0.5); //black과 white를 서로 뒤집는다
>>n2=imopen(nt,strel('disk',5));
*strel('disk',5) //structural element(matlab 함수)







<이웃화소(Neighbors)와 인접화소(Adjacency)>
- 화소 P가 4개의 이웃이 있는 경우 : 4-인접
- 화소 P가 8개의 이웃이 있는 경우 : 8-인접






<경로(path)와 성분(components)>
-오브젝트 사이의 연결
- ex)
  - Distance=6(4연결)
  - Distatnce=4(8연결)






<성분의 라벨링> - object 갯수를 count, default=8연결
- 목적(foreground)화소 : object가 있는 경우
- 배경(background)화소 : object가 없는 경우

- 알고리즘(-4성분 마스크) -
  1. p의 상태를 확인. 만일 p가 배경화소이면 다음 스캔의 위치로 이동. 목적화소이면 u와 l을 확인. 만일 그들(u와 l)이 모두 배경화소들이면 p에 새로운 라벨을 부여
  - u와 l중의 하나가 목적화소이면 p에 라벨을 부여
  - u와 l이 모두 목적화소이고, 같은 라벨을 가지면 그들 라벨 중의 하나를 p에 부여하고 그들 2개의 라벨이 서로 등가로 만들어라(u와 l이 p에서 동일한 4-연결이 되기 때문)
  2. 스캔의 마지막에서, 모든 목적화소들은 라벨링이 되었지만, 몇 개의 라벨이 등가일 수도 있다. 그 라벨들을 등가분류로 분류하고 각 분류에 다른 라벨을 부여한다
  3. 각 목적화소에 있는 라벨을 이전 단계에서 등가분류로 부여된 라벨을 치환하면서 영상을 통해 2번째로 처리
>>bwlabel(i,4) //4연결 : 대각 성분을 건너지 못한다

- 알고리즘(-8성분 마스크)
  1. 만일 p가 배경화소이면 다음 스캔 위치로 이동하라. 만일 p가 목적화소이면 d,u,e 및 l을 확인해라. 만일 그들이 모두 배경화소들이면 p에 새로운 라벨을 부여하라. 
     만일 하나의 화소라도 목적화소가 있으면 p에 그 라벨을 부여하라. 
     만일 2개 이상의 목적화소가 있으면 그둘 중 어느 하나를 부여하고 그들의 모든 화소들을 등가로 처리한다
  2. 단계 2와 3은 동일
  - 이 알고리즘은 'bwlabel' 함수로 구현된다
>>bwlabel(i,8) //8연결 : 대각 성분을 건널 수 있다

- ex) 박테리아만 볼 수 있는 이진 영상을 얻기 위해 문턱치 처리(b<100)을 해야 하고, 그 후에 그 결과에 bwlabel을 적용한다
  여기서 만들어진 가장 큰 라벨을 간단히 아래와 같이 구하여 물체들의 수를 구할 수 있다
>>b=imread('bacteria.tif');
>>bt=b<100;
>>bl=bwlabel(bt);
>>max(bl(:))

>>21





<Look-Up 테이블>
- 대응하면 이웃들로부터 출력을 표현하는 각 요소는 길이가 512인 벡터이다
  반복적인 작업을 줄여서 계산속도를 줄이기위해 사용한다
  이웃 화소들과 출력 화소들 사이에 1대 1대응이 되도록 모든 이웃 화소들을 정렬하는 일종의 속임수이다
  이것은 이웃 화소의 각 화소에 아래와 같이 가중치를 준다
  즉, 테이블을 만들어서 '패턴매치'를 한다

  -  패턴(2의 제곱승) - 
  1  8     64
  2  16   128
  4  32   256
- 규칙에 따라 look-up 테이블을 정의하는 'makelut'함수를 이용
-> makelut(function, n, P1, P2, ... ) 
  - function : 어떤 기능을 가지는 look-up table을 만들 것인가
  - n : Mask Size , P1, P2, ...는 그 함수를 적용하게 될 선택적인 파라메터
     - 4연결 함수, 엣지가 얇게 나온다
      >>f=inline('x(5)&~(x(2)*x(4)*x(6)*x(8))');
  - 즉, 4연결을 고려할 때 x(5)가 1일 때 (목적화소) x(2), x(4), x(6), x(8) 중 하나라도 0이면 x(5)는 경계가 되고 1을 return 한다
    Pattern의 수 2^4=16개의 pattern을 갖는다

      - 이 함수에 대하여 x(5)는 3X3 매트릭스 x의 중심화소이고, x(2), x(4), x(6), x(8)은 중심에 4-인접 화소들이 되도록 하는 단일 값의 매트릭스 인덱싱 구조
      >>f8=inline('x(5)&~(x(1)*x(2)*x(2)*x(3)*x(4)*x(6)*x(7)*x(8)*x(9))'); //8연결 함수, 엣지가 두껍게 나온다
      >>lut=makelut(f8,3);
      >>cw=applylut(c,lut);
      >>imshow(cw) 
  - 즉, 8연결을 고려할 때, x(5)가 1일 때 (목적화소) x(1), x(2), x(3), x(4), x(6), x(7), x(8), x(9) 중 하나라도 0이 되면 x(5)는 경계가 되고 1을 return 한다
    Pattern의 수 2^8=256개의 pattern을 갖는다






<거리(distance)>
- 거리함수 d(x,y)는 다음을 만족하는 경우에 metric(미터법)이라고 한다
   1. d(x,y)=d(x,y) (symmetry)
  2. d(x,y)>=0 and d(x,y)=0 if and only if x=y (positivity)
  3. d(x,y) + d(x,y) <= d(x,z) (the triangle inequaility) 
  metric 표준거리는 x=(x1,x2)와 y=(y1,y2)인 경우 Euclidian distance로 나타내고
  아래와 같이 표현한다
  d(x,y)=root(x1-y1)^2+(x2-y2)^2 //x와 y사이의 직선거리
  1,2는 미터법에 의해 쉽게 만족됨을 알 수 있고, 이것은 항상 (positive)이며, x1=y1과 x2=y2일 때만, 즉 x=y일 때 0이다





<거리 변환>
- 영상 내 object가 있고 그 영역을 R이라고 할 때 R 외부의 한 점 (x,y)로부터 영역 R내부의 모든 점까지의 거리를 모두 구하고 이 중 가장 작은 것을 거리고 정한다면 R이 클 때 많은 계산이 필요하다
단계 1. 영상에서 R로부터 각 화소 (x,y)까지의 거리를 나타내는 라벨 d(x,y)을 붙어라
     R에서 각 화소가 0인 라벨을 붙여서 시작하고, R에 존재하지 않으면 '무한'을 붙여라

단계 2. 이 영상을 통해 1화소씩 이동한다. 각 화소 (x,y)에 대하여 아래와 같이 무한대+1=무한대를 이용하여 해당하는 라벨로 치환한다
  min{d(x,y),d(x+1,y)+1, d(x-1,y)+1, d(x,y-1)+1, d(x,y+1)+1}

단계 3. 모든 화소들이 무한대가 아닌 값으로 변환될 때 까지 단계 2를 반복

- Matlab에서의 구현
  1. 마스크의 사이즈를 이용하여 적당히 0으로 영상을 채운다
  2. 각 0을 무한대로 바꾸고, 각 1을 0으로 바꾼다
  3. 순방향 및 역방향마크스를 만든다
  4. 순방향 pass를 실핸한다. 각 라벨을 그 이웃들의 최소값과 순방향마스크를 더한 값으로 치환한다
  5. 역방향 pass를 실행한다. 각 라벨을 그 이웃들의 최소값과 역방향마스크를 더한 값으로 치환한다