제 6 장 영상 분할
[email protected]
Prof. Doo-Hyun Choi
Introductory Image Processing
Contents
영상 분할
문턱 값에 의한 영상 분할
p-타일법
모드법
반복적 문턱 값 선택법
최적 이진화 기법
에지(edge) 기반 영상 분할
고립점 검출
직선 검출
에지 검출
미분 연산자
라플라시안(Laplacian)
영역 기반 영상 분할
화소 집성에 의한 영역 성장법
단일 연결에 의한 영역 성장법 (Single-linkage region growing)
중심 연결에 의한 영역 성장법 (Centroid-linkage region growing)
분리 및 병합법
분수령 알고리즘(Watershed algorithm)을 이용한 분할
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (3/26)
영상 분할
영상 분할
영상을 구성하고 있는 내부의 객체들을 구분하여 나누는 것
분할된 영역들은 화소의 밝기(brightness), 질감(texture), 색상(color) 등의 동질성 (homogeneity)을 가져야 한다.
주어진 영상 R을 N개의 영역으로 분할 했을 때 다음을 만족하여야 한다.
영상 분할 방법
문턱 값(thresholding value)에 의한 영상 분할
에지(edge) 기반 영상 분할
영역(region) 기반 영상 분할
y homogeneit
and ty connectivi
: ) 3
,
) 2
) 1
1
n j i N n
n
R
j i R
R
R R
≠
=
=
=
φ
문턱 값에 의한 영상 분할
영상의 히스토그램 분포에서 문턱 값을 결정하고, 이를 이용하여 영상을 분할하는 방법
히스토그램에 따른 문턱 값 선택
실제 문턱 값을 정하기는 쉽지 않다. (명확하지 않은 히스토그램의 골과 마루, 잡음 등)
문턱 값을 자동으로 결정하는 방법
p-타일(tile) 법
모드(mode) 법
반복적 문턱 값 선택법 (iterative threshold selection method)
최적 이진화 기법 (optimal thresholding)
Multi-modal 히스토그램 Bi-modal 히스토그램
명암도
화소수
T 명암도
화소수
T1 T2
문턱 값에 의한 영상 분할
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (5/26)
p-타일법
영상의 히스토그램으로부터 상위 p%가 되는 명암도를 문턱 값으로 결정하는 방법
전체 영상에서 객체의 비율을 미리 알 수 없음.
일반적으로 사전에 p 값을 알 수 없으므로 제한된 응용에 사용됨.
p-타일법
명암도
화소수
T P%
모드법
단순한 영상에 사용함.
모드 값에 의한 문턱 값 결정 알고리즘
1. 히스토그램H에서 일정 거리 이상을 가지는 2개의 국부 최대 점(local maxima) i 와 j 를 찾 는다.
2. i 와 j 사이의 히스토그램 최소 점 k 를 찾는다.
3. 아래에 정의된 Peakness(P)를 계산한다.
4. 단계 1에서 3까지를 전 명암도에 걸쳐 반복적으로 적용하여 최대P를 갖는 k를 문턱 값으로 한다.
( )
) (
) ( ), ( min
k H
j H i P= H
모드법
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (7/26)
반복적 문턱 값 선택법
모드 값에 의한 문턱 값 결정 알고리즘
1. 초기 문턱 값T를 선택한다. (일반적으로 영상의 평균으로 설정한다.) 2. 선택된 문턱 값을 이용해서 영상을 R1, R2로 분할한다.
3. R1, R2의 평균μ1, μ2를 구한다.
4. μ1, μ2의 변화가 정해진 기준 이하가 될 때까지 단계2로 간다.
반복적 문턱 값 선택법을 이용한 영상 분할의 예 2
2
1 μ
μ +
= T
반복적 문턱 값 선택법
Lena 영상 5회 반복 분할 영상 Girl 영상
(T=117) 5회 반복 분할 영상
(T=84)
최적 이진화 기법 (1/2)
가정: 영상의 히스토그램은 두 개의 마루와 하나의 골을 갖고 각각 Gaussian 분포를 따른다.
혼합 확률밀도함수 p(z): p(z) = P1p1(z) + P2p2(z)
여기서, P1, P2: Gaussian 분포의 가중치, P1과P2의 합은 1.
p1(z), p2(z): Gaussian 확률밀도함수
여기서, μ1, μ2 각 그룹의 평균, σ1, σ2 각 그룹의 평균
객체영역(1영역)이 배경영역(2영역)으로 분류되어지는 확률:
배경영역이 객체영역으로 분류되어지는 확률:
전체 에러 확률: e(T) = P1e1(T) + P2e2(T)
최적 이진화 기법 (1/2)
( ) ( )
22 2 2
1 1
2 2 2 2
1 2 1
2 1
1 ( ) ( ) 2 2
)
( σ
μ σ
μ
πσ πσ
− −
− −
+
= +
=
z z
P e P e
z p P z p P z p
−∞= T p z dz T
e1( ) 2( )
∞= Tp z dz T
e2( ) 1( )
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (9/26)
최적 이진화 기법 (2/2)
에러 확률을 최소화 하는 T를 찾기 위해 Liebnitz의 Rule을 적용한다. 즉, e(T)를 T에 대해 미분하여 0으로 두면, P1p1(T) = P2p2(T) AT2 + BT + C = 0
여기서,
두 그룹의 표준편차가 σ = σ1 = σ2 인 경우,
두 그룹의 가중치가 P1 = P2 인 경우, 문턱 값 T는 두 그룹의 평균값들의 평균이 됨.
최적 이진화 기법 (2/2)
( )
+
−
=
−
=
−
=
2 1
1 2 2
2 2 2 1 2 2 2 1 2 1 2 2
1 2 2
2 2 1
2 2
1 , 2 , 2 ln P C P
B
A
σ σ μ σ μ σ μ σ μ σ σ σ σ σ
1 2 2 1 2 2
1 ln
2 P
T P
μ μ μ σ μ
+ +
= +
2
2
1
μ
μ
+= T
에지(edge) 기반 영상 분할
에지
밝기의 변화가 큰 부분, 객체의 윤곽선
에지 연산자: 에지를 검출하는 연산자
에지 기반 영상 분할
검출된 에지를 사용하여 연결성과 동질성을 만족하는 영역들을 분할하는 방법
과정
1. 에지 검출 2. 세선화 3. 영역 분할
고립점 검출
마스크 연산: 만약 결과의 절대치 > Threshold, 중심화소는 고립점
-1 -1 -1
-1 8 -1
-1 -1 -1
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (11/26)
직선 검출
네 방향 직선 검출을 위한 마스크
각 방향 응답 값이 문턱 값보다 크면 해당 방향의 직선 위 화소로 판단함.
-1 -1 2
-1 2 -1
2 -1 -1
2 -1 -1
-1 2 -1
-1 -1 2
-1 -1 -1
2 2 2
-1 -1 -1
-1 2 -1
-1 2 -1
-1 2 -1
수평방향 수직방향 +45O −45O
에지 검출
에지
밝기 값의 변화가 급격한 부분
미분 연산을 이용하여 검출될 수 있다
에지에 대한 미분 연산자의 특성
영상의 에지에서 1차 미분 값의 절대치는 최대
영상의 에지에서 2차 미분 값은 0
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (13/26)
미분 연산자 (1/2)
미분 연산자
영상 f(x,y)
3 x 3 크기의 화소들
중심화소인 z5의 기울기 근사화
2
2
:
, )
, ( :
x y
y
x f G G
y fx f G
y G x
f ∇ = +
∂
∂∂
∂
=
=
∇ 기울기의크기
기울기 혹은
미분
z1 z2 z3
z4 z5 z6
z7 z8 z9
( ) ( )
8 6 9 5
6 5 8 5
6 2 2 5
8 5
z z z z f
z z z z f
z z z
z f
− +
−
≈
∇
− +
−
≈
∇
− +
−
≈
∇
미분 연산자 (2/2)
미분 연산을 위한 여러 마스크
미분 연산자를 이용한 에지 검출의 예
-1 -1 -1
0 0 0
1 1 1
Prewitt 연산자
1 0
0 -1
0 1
-1 0
Roberts 연산자
-1 0 1
-1 0 1
-1 0 1
-1 -2 -1
0 0 0
1 2 1
Sobel 연산자
-1 0 1
-2 0 2
-1 0 1
Prewitt 연산자
Roberts 연산자 Sobel 연산자
원 영상 (Lena)
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (15/26)
라플라시안(Laplacian) (1/3)
라플라시안(Laplacian)
가장 많이 쓰이는 Laplacian 근사화
에지는 2차 미분이 0이 되는 점들의 집합. 마스크를 래스트(Raster) 스캔하면서 응답 값의 부호가 바뀌는 점을 찾으면 된다.
0 -1 0
-1 4 -1
0 -1 0
2 2 2 2 ( , ) 2
y f x
y f x
f ∂
+∂
∂
= ∂
∇
(
2 4 6 8)
2f(x,y)=4z5− z +z +z +z
∇
z1 z2 z3
z4 z5 z6
z7 z8 z9
라플라시안(Laplacian) (2/3)
LOG (Laplacian Of Gaussian)
잡음에 대한 영향을 줄이기 위해 라플라시안을 2차원 Gaussian 필터링
LOG 연산에 의해 에지 검출
Laplacian은 잡음에 민감함.
LOG 연산 후, 영 교차점이면서 국부 분산 값이 일정 값 이상인 경우만 에지로 판단한다.
{ }
{ }
22 2
4 2 2 2 2 2
2 2
y) 2 g(x,
where ) , ( ) , ( )
, (
n Convolutio
Laplacian
Gaussian
. 2
response
impulse Gaussian
: ) , ( where ) , ( ) , ( )
, (
Laplacian
Gaussian
. 1
σ
σσ
e x y yy x x f y x g y
x h
y x g y
x f y x g y
x h
− +
−
= +
∇
∗
∇
=
∗
∇
=
방법 하는 영상과
원 후에 적용한 을
에
방법 적용하는 을
평활화하여 필터로
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (17/26)
라플라시안(Laplacian) (3/3)
LOG (Laplacian Of Gaussian) 필터의 예
11 x 11 크기, σ = 1.4
LOG 연산을 이용한 에지 영상
국부 분산을 이용하여 잘못된 윤곽선 제거
영역 기반 영상 분할
영역 기반 영상 분할
영역 성장법 (region growing)
Seed에서 시작하여 영역을 확장시켜 가는 방법
하나의 화소나 작은 영역들이 유사한 특징을 지닌 주위의 영역들을 흡수하여 영역을 확대해 나가는 방법
종류
화소 집성에 의한 영역 성장법
단일 연결에 의한 영역 성장법 (Single-linkage region growing)
중심 연결에 의한 영역 성장법 (Centroid-linkage region growing)
영역 분리법 (split)
전체 영상을 균일한 영역으로 세분화시켜 가는 방법
분리 및 병합법 (split and merge)
두 가지 방법을 통합
분수령 알고리즘(Watershed algorithm)을 이용한 분할
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (19/26)
화소 집성에 의한 영역 성장법
화소 집성에 의한 영역 성장법 (Region growing by pixel aggregation)
화소 단위로 영역을 성장시키는 방법
균질성(homogeneity)이 존재해야 영역 성장이 가능함
균질성의 판단은 영상 분할의 목적에 따라 다름.
일반적으로 명암도 혹은 색상의 차이를 이용한다.
화소 집성에 의한 영역 성장법의 예
단점: Seed에 따라 결과가 달라지고, 균질성의 판단 기준 설정이 어렵다.
0 1 5 7 8
0 2 1 7 6
1 1 3 6 7
2 1 0 8 7
1 1 7 5 8
0 1 5 7 8
0 2 1 7 6
1 1 3 6 7
2 1 0 8 7
1 1 7 5 8
0 1 5 7 8
0 2 1 7 6
1 1 3 6 7
2 1 0 8 7
1 1 7 5 8
원 영상 Seed를 1,7로 설정
명암도 차이의 문턱 값을 3으로 했을 경우
명암도 차이의 문턱 값을 8으로 했을 경우
단일 연결에 의한 영역 성장법
단일 연결에 의한 영역 성장법(Single-linkage region growing)
영상의 각 화소를 그래프의 노드로 취급하고 4방향 이웃 화소 사이에 균질성이 존재 할 때 그 화소 사이를 호(arc)로 연결시켜 영상을 분할하는 방법
단점: 영상 내부에서 명암도가 서서히 연속적으로 한 방향으로 변할 경우, 낮은 명암 도와 높은 명암도의 화소들 사이의 균질성이 낮아도 동일 영역으로 분할될 수 있다.
원 영상 분할된 영상
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (21/26)
중심 연결에 의한 영역 성장법
중심 연결에 의한 영역 성장법(Centroid-linkage region growing)
임의의 화소와 이웃하는 영역의 평균과의 균질성을 이용해서 영상을 분할하는 방법
알고리즘
1. 전체 영상에 대해 래스트 스캔을 시작한다.
2. X0화소와 인접한 4개의 이웃 화소들X1~ X4이 속한 영역의 특성(밝기 값 등)을 비교하여 균질성을 조사한다.
3. 균질성이 존재하는 가장 유사한 영역에 X0를 병합한다. 만약 균질성이 있는 이웃 화소가 없 다면X0를 새로운 영역으로 할당한다.
4. 스캔이 끝날 때까지 단계 2로 돌아가서 반복한다.
예: 척추 자기 공명(MRI, Magnetic Resonance Imaging) 영상
X4 X3 X2
X1 X0
원 영상 분할된 영상
분리 및 병합법 (1/2)
전체 영상을 하나의 영역으로 두고 4분할을 이용해서 영상을 분리한다. 인접 분할 영 역의 균질성이 있으면 다시 병합해 주는 과정으로 전체 영상을 분할하는 방법
균질성: 화소의 밝기, 색상, 질감 등의 영상 특징들의 유사성
알고리즘
1. 전체 영상을 하나의 분할된 영역 R로 하여 시작한다.
2. 현재까지 분할된 영역들의 균질성을 조사하여 균질성이 존재하지 않는 영역들을 각각 같은 크기의 네 영역으로 분할한다.
3. 현재까지 분할된 영역들에 대해서 인접한 영역들 간에 균질성이 존재하면 이들 영역들을 병 합한다.
4. 더 이상의 분할 또는 병합되지 않을 때까지 단계 2로 돌아가서 반복한다.
분리 및 병합의 예1
4 분할 비 균질 영역을 다시 4 분할
균질 영역은 병합 비 균질 영역은 분리
최종 분할 결과
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (23/26)
분리 및 병합법 (2/2)
분리 및 병합의 예2
원 영상 분할된 영상
분수령 알고리즘을 이용한 분할 (1/2)
지형학에서 주로 연구, 영상의 밝기를 고도(altitude)로 생각하여 영상처리에 응용됨
담수지역을 구분하는 분수령을 찾아서 영역 분할에 이용함.
분수령을 계산하는 다양한 방법이 연구되었으나, immersion simulation이 가장 효과 적인 기법으로, 계층적 queue로 구현됨.
Immersion simulation을 이용한 영역 분할 과정 1. 낮은 고도에서부터 담수지역에 물을 채워 나간다.
2. 서로 다른 지역에 물이 채워지다가 만나게 되면 만나는 경계에 가상의 댐을 쌓는데, 이 댐이 분수령이 된다.
3. 이 과정이 모두 끝나면 물의 위치는 절대 최고치의 높이에 이른다. 전체 영역은 분수령에 의 해서 담수지역으로 분할된다.
Immersion simulation은 이중 순서의 특성을 지닌다. 계층적 queue로 구현
낮은 고도가 먼저 물이 찬다.
같은 고도에서는 물이 넘치는 쪽에 가까운 위치가 먼 위치보다 먼저 찬다.
계층적 queue: 우선권(priority)이 다른 queue들의 집합
우선권이 높은 queue에 있는 원소 먼저 처리
같은 queue내에서는 FIFO (first-in-first-out)
Introductory image Processing Lecture Note 06
IISL, School of EECS, KNU (25/26)
분수령 알고리즘을 이용한 분할 (2/2)
계층적 queue를 이용한 Watershed 알고리즘의 구현
Queue의 초기화
우선권은 신호 값의 역수
최 상위 우선권은 전체 최소 값의 화소 위치
범람(flooding)
Queue에서 화소를 꺼내서 담수 지역에 속하지 않 는다면 이웃 담수지역 중 밝기 값이 가까운 지역으 로 할당
이 화소에 인접해 있는 화소 중 담수지역으로 할당 되지 않는 화소는 queue에 입력 (Queue의 화소들 은 담수 지역을 접하고 있는 화소들임)
모든 화소들이 담수 지역으로 할당될 때까지 범람 과정 반복
Practice
문턱 값에 의한 영상 분할
반복적 문턱 값 선택법을 구현하시오. (강의노트 p. 7 참조)
에지 기반 영상 분할
미분 연산자를 이용해서 에지를 검출하시오. (강의노트 p. 14 참조)
LOG와 국부 분산을 이용하여 에지를 구하시오. (강의노트 p. 17 참조)
영역 기반 영상 분할(Optional)
중심 연결에 의한 영역 성장법을 구현하시오. (강의노트 p. 21 참조)
분리 및 병합법으로 영역을 분할하시오. (강의노트 p. 23 참조)