Introductory Image Processing

(1)

제 7 장 이진 영상 처리

[email protected]

Prof. Doo-Hyun Choi

Introductory Image Processing

이진 영상 처리

 이진 영상

 영상 이진화: 명암도 영상에서 이진 영상을 얻는 과정

 보통 배경 영역(0)과 객체 영역(1 혹은 255)으로 구성

 문턱 값 설정에 필요한 정보

 객체의 밝기 특성

 영상에서 객체가 차지하는 비율

 객체 개수

 Etc.

 예: 히스토그램을 이용한 영상 분할 혹은 영상 이진화 )

ing value (threshold

: where

) , ( , 0

) , ( , ) 1

, (

값 T 문턱

T n m f

T n m n f

m

f   

<

= ≥

객체의 표현

 면적(area)

 이진 영상에서 객체에 해당하는 화소들의 갯수

 위치(position), 무게중심(Center of mass)

 객체의 위치는 면적의 중심으로 한다. (잡음에 강인함.)

.

(area),

: where

) ,

1

(

0 1

0

가정 갖는다고 크기를

의 객체는

면적 M N

A

n m f A

^M

m N

n

×

=  

⁻

=

−

=

) , (

, ) ,

(

¹

0 1 0 1

0 1

0

A n m nf A y

n m mf x

M m

N c n

M m

N

c

=  

n

=  

⁻

=

−

=

−

=

−

=

(3)

연결 성분

 연결 성분(connected components)

 영상에서 같은 값을 갖고 연결되어 있는 화소들의 집합  객체

 연결 성분 레이블링(connected component labeling)

 같은 연결 성분에 속하는 화소들에 같은 레이블을 할당하는 것

 방법

 재귀적 알고리즘

 순차적 알고리즘

재귀적 알고리즘

 영상 전체를 동시에 메모리에 저장하고, 전체 영상을 동시에 처리하는 방법

 단점: 큰 메모리 용량과 많은 연산량이 필요함.

 알고리즘

1. 영상을 스캔하여 레이블링이 되어 있지 않는 1을 갖는 화소를 찾아 새로운 레이블l을 부여한 다.

2. 레이블 l을 가진 화소를 기준으로 그 이웃 화소가 레이블을 가지고 있지 않다면, 재귀적(반복 적)으로 레이블l을 주변의 이웃 화소에 부여한다.

3. 레이블이 할당되지 않은 화소가 존재하면 단계 1로 간다.

(4)

순차적 알고리즘 (1/2)

 2단계 과정으로 레이블링을 하는 방법

 첫 번째 과정: 레이블링을 하면서 연결된 성분의 동치 테이블을 만든다.

 두 번째 과정: 동치 테이블을 이용하여 각각의 객체에 고유한 레이블을 부여한다.

 순차적 알고리즘의 비교영역

 4-이웃의 경우: 위쪽 U와 왼쪽 L 만 비교하여 연결성 판단

 8-이웃의 경우: 위쪽 세 화소 및 왼쪽 한 화소를 비교하여 연결성 판단.

 알고리즘

1. 레이블 값을 초기화하고, 영상을 왼쪽에서 오른쪽 방향으로, 위에서 아래 방향으로 탐색한다.

2. 현재 화소 C가 1이면

 U와 L중 어느 한쪽만 레이블을 갖는 경우, 현재 화소에 그 레이블을 부여한다.

 U와 L이 같은 레이블을 갖는 경우, 현재 화소에 그 레이블을 부여한다.

 U와 L이 서로 다른 레이블을 갖는 경우, 현재 화소에 U의 레이블을 부여하고 동치 테 이블에U와 L의 레이블이 같음을 나타낸다.

 U와 L이 레이블을 가지지 않는 경우, 현재 화소에 새로운 레이블을 부여한다.

3. 레이블이 할당되지 않은 화소가 있다면 단계 2로 간다.

4. 동치 테이블을 이용하여 동치 레이블들 중 가장 낮은 레이블로 대치한다.

 동치 테이블: 같은 레이블을 가져야 하는 레이블들을 등록하는 테이블

U

L C

순차적 알고리즘 (2/2)

 순차적 알고리즘의 결과

(5)

세선화 (1/3)

 세선화(thinning)

 선 또는 영역의 연결성은 변화시키지 않고 선분을 한 화소 굵기로 표현하는 것

 세선화 알고리즘은 다음의 세가지 조건을 만족하여야 한다.

1. 선분의 끝점은 제거되지 않아야 한다.

2. 선분은 연결되어야 한다.

3. 선분은 한 화소 굵기로 표현되어야 한다.

 Zhang-Suen 알고리즘

 가정: 객체 영역의 화소들은 1을 가지고, 배경 영역의 화소들은 0을 가진다.

 다음의 2개의 단계들을 객체 영역의 모든 외곽선 화소들에 적용한다.

 외곽선 화소: 이웃 화소들 중 적어도 한 개의 화소가 0의 값을 가지는 화소 단계 1: (a) 2 ≤ N(z₅) ≤ 6, (b) S(z₅) = 1, (c) z₂z₆z₈= 0, (d) z₄z₆z₈ = 0.

단계 1의 모든 조건을 만족하면 1인z₅를 0으로 한다.

단계 2: (a) 2 ≤ N(z₅) ≤ 6, (b) S(z₅) = 1, (c) z₂z₄z₆= 0, (d) z₂z₄z₈= 0.

단계 2의 모든 조건을 만족하면 1인z₅를 0으로 한다.

여기서,N(z₅): z₅의 이웃 중에 0이 아닌 값을 가진 화소의 개수

S(z₅): z₁,z₂,z₃,z₆,z₉,z₈,z₇,z₄,z₁의 순서에서 0에서 1로 천이된 회수

z₁ z₂ z₃ z₄ z₅ z₆ z₇ z₈ z₉

세선화 (2/3)

 Zhang-Suen 알고리즘의 단계 별 조건 분석

 단계 1:

(a) 2 ≤ N(z₅) ≤ 6

 N(z₅) = 1인 경우, z₅가 끝점이므로 1인z₅를 0으로 하면 안 됨.

 N(z₅) = 7인 경우, 1인z₅를 0으로 하면 객체 영역이 침식됨.

(b) S(z₅) = 1

 두께가 1인 선분 위의 화소의 경우, 1인z₅를 0으로 하면 선분의 연결성이 깨어짐.

(c) z₂z₆z₈= 0, (d) z₄z₆z₈ = 0.

 z₆= 0 또는z₈= 0 또는 (z₂= 0 & z₄= 0)일 때, 즉, z₅는 선분의 동쪽, 남쪽, 북서쪽 모서리

 단계 2:

(a) 2 ≤ N(z₅) ≤ 6 (b) S(z₅) = 1

(c) z₂z₄z₆= 0, (d) z₂z₄z₈ = 0.

 z₂= 0 또는z₄= 0 또는 (z₆= 0 & z₈= 0)일 때, 즉, z₅는 선분의 북쪽, 서쪽, 동남쪽 모서리 z₁ z₂ z₃

z₄ z₅ z₆ z₇ z₈ z₉

(6)

세선화 (3/3)

 Zhang-Suen 알고리즘의 세선화 예

원 영상 레이블링 된 영상

이진 형태학 연산 (1/4)

 이진 형태학 연산(binary morphology operation)

 형태학적 기법

 영상 내의 객체 구조를 명확히 함

 예: 객체 내의 홀 채우기, 배경 잡음 제거, 객체의 경계나 골격 추출

 이진 형태학 연산

 형태소(structuring element)를 이진 영상의 일부와 비교하여 결과(0 또는 1)를 할당하는 연산

 형태소

 이진 영상으로 표현 가능한 임의의 크기와 구조를 가진 어떤 모양

 원점: 형태소 내의 어떤 화소, 형태소의 중심점, 보통 중심 화소를 원점으로 잡는다.

 여러 가지 모양의 형태소와 원점(진한 화소)

(7)

이진 형태학 연산 (2/4)

 기본 연산

 네 가지 기본 연산

 팽창(dilation)

 형태소 S에 의한 이진 영상 B의 팽창연산 B ⊕ S: 형태소의 각 화소에 대응하는 영상 화 소 중에 하나라도 1이면 형태소 원점에 대응되는 영상의 화소는 1이 됨.

 팽창연산 후의 영역은 확장된다.

 침식(erosion)

 형태소 S에 의한 이진 영상 B의 침식연산 B Θ S: 형태소의 각 화소에 대응하는 영상 화 소 중에 하나라도 0이면 형태소 원점에 대응되는 영상의 화소는 0이 됨.

 팽창연산 후의 영역은 축소된다. 특히 형태소보다 작은 영역은 제거된다.

 채움(closing)

 팽창연산 후 침식연산

 B • S = (B ⊕ S) Θ S

 팽창연산(형태소보다 작은 홀을 채우는 등 영역 확장)  침식연산(영역 침식)

 제거(opening)

 침식연산 후 팽창연산

 B ο S = (B Θ S) ⊕ S

 침식연산(형태소보다 작은 영역을 제거하여 영역 축소)  팽창연산(영역 확장)

이진 형태학 연산 (3/4)

 형태학적 연산의 예1

이진 영상 B

팽창연산 B ⊕ S 침식연산 B Θ S

(8)

이진 형태학 연산 (4/4)

 형태학적 연산의 예2

이진 영상 B

형태소 S

팽창연산 B ⊕ S 침식연산 B Θ S

제거연산 B ο S = (B Θ S) ⊕ S 채움연산 B • S = (B ⊕ S) Θ S

이진 형태학 연산의 응용 (1/3)

 객체의 경계 추출 (1/2)

 이진 영상(B)과 형태소(S)의 침식연산(Θ) 후, 이진 영상과 XOR 연산  경계( β ⁽ ^B))

 β ⁽ B) = (B Θ S) XOR B

 경계 추출 과정

원 영상 B 침식연산 B Θ S 경계 β ^(B)

(9)

이진 형태학 연산의 응용 (2/3)

 객체의 경계 추출 (2/2)

 형태학적 연산을 이용한 경계 추출의 예

원 영상 B 경계 β ^(B)

이진 형태학 연산의 응용 (3/3)

 영상 골격화

 영상 골격화의 예

시작 형태소

수축 팽창

XOR

수축 팽창

XOR

수축 팽창

OR

(10)

Introductory Image Processing

제 7 장 이진 영상 처리

[email protected]

Prof. Doo-Hyun Choi

Introductory Image Processing

Contents

 이진 영상 처리

 객체의 표현

 연결 성분(connected components)

 세선화(thinning)

 이진 형태학 연산(binary morphology operation)

이진 영상 처리

 이진 영상

 영상 이진화: 명암도 영상에서 이진 영상을 얻는 과정

 보통 배경 영역(0)과 객체 영역(1 혹은 255)으로 구성

 문턱 값 설정에 필요한 정보

 예: 히스토그램을 이용한 영상 분할 혹은 영상 이진화 )

ing value (threshold

: where

) , ( , 0

) , ( , ) 1

, (

값 T 문턱

T n m f

T n m n f

m

f   

<

= ≥

객체의 표현

 면적(area)

 이진 영상에서 객체에 해당하는 화소들의 갯수

 위치(position), 무게중심(Center of mass)

 객체의 위치는 면적의 중심으로 한다. (잡음에 강인함.)

.

(area),

: where

) ,

(

가정 갖는다고 크기를

의 객체는

면적 M N

A

n m f A

×

=  

) , (

, ) ,

(

A n m nf A y

n m mf x

=  

=  

연결 성분

 연결 성분(connected components)

 영상에서 같은 값을 갖고 연결되어 있는 화소들의 집합  객체

 연결 성분 레이블링(connected component labeling)

 같은 연결 성분에 속하는 화소들에 같은 레이블을 할당하는 것

 방법

재귀적 알고리즘

 영상 전체를 동시에 메모리에 저장하고, 전체 영상을 동시에 처리하는 방법

 단점: 큰 메모리 용량과 많은 연산량이 필요함.

 알고리즘

순차적 알고리즘 (1/2)

 2단계 과정으로 레이블링을 하는 방법

 순차적 알고리즘의 비교영역

 알고리즘

 동치 테이블: 같은 레이블을 가져야 하는 레이블들을 등록하는 테이블

순차적 알고리즘 (2/2)

 순차적 알고리즘의 결과

세선화 (1/3)

 세선화(thinning)

 선 또는 영역의 연결성은 변화시키지 않고 선분을 한 화소 굵기로 표현하는 것

 세선화 알고리즘은 다음의 세가지 조건을 만족하여야 한다.

 Zhang-Suen 알고리즘

세선화 (2/3)

 Zhang-Suen 알고리즘의 단계 별 조건 분석

세선화 (3/3)

 Zhang-Suen 알고리즘의 세선화 예

원 영상 레이블링 된 영상

 이진 영상(B)과 형태소(S)의 침식연산(Θ) 후, 이진 영상과 XOR 연산  경계( β ⁽ ^B))

 β ⁽ B) = (B Θ S) XOR B

원 영상 B 침식연산 B Θ S 경계 β ^(B)

원 영상 B 경계 β ^(B)