2. 디지털 영상 기초(3)

2.5 화소 간 몇 가지 기본적 관계

2.5.1 화소 이웃

좌표 (x,y)에서 화소 p는 네 개의 수평, 수직 이웃을 가진다.

$(x+1, y),(x-1,y),(x,y+1),(x,y-1)$

이 화소 집합이 p의 4-neighbors이며 $N_4(p)$로 표기된다. p의 대각 이웃 좌표는 다음과 같고 $N_D(p)$로 표기된다.

$(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)$

이 점들은 4-neighbors와 함께 8-neighbors로 사용된다.

2.5.2 인접성, 연결성, 영역, 경계

• 인접성
  • 밝기 값들의 집합 V, 이진 영상에서 값 1을 갖는 화소들의 인접성을 말하고자 한다면, $V=\{1\}$이다. 0~255인 화소들의 인접성에서 집합 V는 256개 값들의 어떤 부분 집합이 될 수 있다.
    • 4-adjacent : V로부터의 값을 갖는 두 화소 p와 q는 만일 q가 집합 $N_4(p)$에 있으면 4-adjacent
    • 8-adjacent : V로부터의 값을 갖는 두 화소 p와 q는 만일 q가 집합 $N_8(p)$에 있으면 8-adjacent
    • m-adjacent : V로부터의 값을 갖는 두 화소 p와 q는 다음과 같을 때 m-adjacent이다.
      • q가 $N_4(p)$에 있거나,
      • q가 $N_D(p)$에 있고 집합 $N_4(p)\cap N_4(q)$가 V로부터의 값을 갖는 화소를 갖지 않을 때.

  m-인접성은 8-인접성의 모호성을 해결하기 위해 등장함.

  예를 들어 V={1}에 대해 왼쪽 그림과 같이 화소를 배치했을 때 8-adjacent를 고려하면 가운데 그림과 같이 연결이 생긴다. 다중연결(모호성)을 해소하기 위해 m-adjacent를 적용하여 오른쪽 그림처럼 모호성을 제거할 수 있다.

  

  좌표 (x,y)인 화소 p로부터 (s,t)인 화소 q까지의 경로는 좌표들이 $(x_0,y_0),(x_1,y_1),...,(x_n,y_n)$인 서로 다른 화소들의 시퀀스이다.

  여기서 $(x_0,y_0) = (x,y)$이고 $(x_n,y_n)=(s,t)$이며 $1\le i\le n$에 대해 화소 $(x_i,y_i)$와 $(x_{i-1},y_{i-1})$은 인접한다. 이 경우 n이 경로의 길이다.

  만약 $(x_0,y_0)=(x_n,y_n)$인 경우, 경로는 닫힌 경로이다.

• 연결성
  • 영상의 화소들의 어떤 부분집합을 S라고 할 때, 두 화소 p와 q는 S의 화소로만 구성된 둘 사이의 경로가 존재하면 연결되어 있다고 말한다.
  • S의 어떤 화소 p에 대해, S 안에서 p에 연결되어 있는 화소들의 집합을 S의 연결 성분이라고 한다. 만약 집합 S가 하나의 연결 성분만 갖는다면 연결 집합이라고 한다.

    

• 영역
  • R을 영상의 화소들의 부분집합이라고 하자. 만약 R이 연결 집합이라면 R을 그 영상의 영역(Region)이라고 한다. 두 영역 $R_i, R_j$은 이 둘의 합집합이 연결집합을 형성하면 인접한다고 한다. 인접하지 않은 영역은 분리되어 있다고 한다. 영역에 대해 말할 때는 4,8-adjacent을 고려한다.
  • 어떤 영상이 K개의 분리 영역 $R_k=1,2,3,...,k$를 포함하며 영상의 경계에 닿지 않는다고 가정하면, 모든 K개의 영역의 합집합을 $R_u$, 여집합을 $(R_u)^c$로 표기할 수 있다. 이 때, $R_u$의 모든 점을 foreground(전경), $(R_u)^c$을 background(배경)이라고 한다.

• 경계
  • 경계(border)는 $(R_u)^c$에 있는 점들에 인접한 점들의 집합니다. 경계는 적어도 하나의 background 이웃을 갖는 화소들의 집합이다. 경계는 8-adjacent를 사용해 정의된다.

    

  • 위에서 이야기한 경계는 영역의 내부 경계(inner border)로 불린다. 배경과 대응하는 경계인 외부 경계(outer border)와 구분하기 위해서이다. 경계 추적 알고리즘은 일반적으로 닫힌 경로를 형성하도록 외부 경계를 추적하도록 짜여진다.
  • 다음 그림에서의 영역은 확실히 내부경계로 볼 수 있으나 닫힌 경로를 형성하지 않는다. 경계는 지역적(local)으로 보는게 아니라 전역적(global)으로 구분하기 위한 것으로 외부 경계를 추적한다.

    

border를 edge와 혼동할 수 있다. 이 두 개념 사이에 중요한 차이가 있다. 유한한 region에서 border는 닫힌 경로를 형성하고 global한 개념이다. edge는 미리 설정된 threshold를 넘는 미분 값을 갖는 화소들로 형성된다. 따라서 edge는 local한 개념이다.

이 장에서는 edge를 밝기의 불연속으로 생각하고 border를 닫힌 경로로 생각하는 것이 편하다.

2.5.3 거리 척도

각 좌표가 $(x,y), (s,t), (v,w)$인 화소 $p,q,z$에 대해 다음에 따라 D는 거리 함수 또는 메트릭이다.

$(a)\quad D(p,q)\geq0\quad \text{(D(p,q)=0 \quad iff\quad p=q}),\\(b)\quad D(p,q)=D(q,p),\\(c)\quad D(p,z)\leq D(p,q)+D(q,z)$

1. p와 q 사이의 Euclid Distance

   $D_e(p,q)=[(x-s)^2+(y-t)^2]^{\frac{1}{2}}$

2. p와 q 사이의 city-block distance(Manhattan dist, L1 dist)

   거리가 1인 화소들은 (x,y)의 4-neighbors이다.

   $D_4(p,q)=|x-s|+|y-t|$

3. p와 q 사이의 d8 distance(chessboard distance)

   거리가 1인 화소들은 (x,y)의 8-neighbors이다.

   $D_8(p,q)=\max{(|x-s|,|y-t|)}$

Uploaded by Notion2Tistory v1.0.0