시계열 매칭 기술을 활용한 윤곽선 이미지 매칭 연구

(1)

시계열 매칭 기술을 활용한 윤곽선 이미지 매칭 연구

2017. 3. 21 김범수

고려대학교

데이터 인텔리전스 연구실

1

(2)

• 이미지 매칭

• 모양(shape) 매칭

• 시계열 매칭

• 윤곽선의 시계열 데이터 변환

• 윤곽선 이미지 매칭

• Challenging Problems

• 스케일링-불변 윤곽선 이미지 매칭

• 노이즈 제거 윤곽선 이미지 매칭

• 부분 노이즈 제거 윤곽선 이미지 매칭

• 결론

Korea University 2

(3)

이미지 매칭

• CBIR (content-based image retrieval)

– 색상, 질감, 모양 등 이미지 특성을 기반으로 유사한 이미지를 찾는 작업

Korea University 3

(4)

모양 (shape) 매칭(1/2)

• 이미지의 모양 특성을 기반으로 유사 이미지를 찾는 작업

• 모양 특성들 (shape features)

– Chain code [FS78], shape context [BMP02], CCD [ZL04] 등

Korea University 4

(5)

모양 (shape) 매칭(2/2)

• 기존의 모양 매칭(검색) 연구

– 매칭의 걸리는 시간 보다 매칭의 정확성에 초점

• 대용량 데이터베이스 대상의 상호 작용(interactive)이 가능한 대화형 매칭 시스템을 위해 빠른 매칭이 필요함

시계열 매칭 기술을 활용한 윤곽선 이미지 매칭 제안

(이미지 도메인에서 시계열 도메인으로 문제를 전환하여 해결 시도)

Korea University 5

(6)

시계열 매칭 (1/2)

• 시계열 데이터 (time-series data)

– 각 시간별로 측정한 실수 값의 시퀀스

– ex) 주식 데이터, 날씨 데이터, 환율 데이터 등

• 시계열 매칭

– 질의 시계열과 데이터 시계열간의 비교를 통해 유사한 데이터 시퀀스를 찾는 작업

Korea University 6

질의 시계열 데이터 시계열

시계열 데이터베이스

유사하다(similar) 질의 시계열

유사한 시계열

• 두 시계열간 거리가 허용치 ε 이하이면 유사(similar)하다고 정의

유클리디안 거리 유사 모델 사용

(7)

시계열 매칭 (2/2)

• 시계열 매칭의 특징

– 인덱스를 사용하여 대용량 데이터베이스 대상의 빠른 매칭이 가능함 – 다양한 유사 거리 계산이 가능함

• Ex) 유클리디안, DTW(dynamic time warping), LCSS(longest common subsequence)

– 수행 성능을 향상시킬 수 있는 다양한 기법들의 적용이 쉬움

• Ex) 유사 거리의 하한(lower bound) 기법, 차원 축소 기법

Korea University 7

(8)

윤곽선의 시계열 데이터 변환

• CCD (centroid contour distance)

– 중심점에서 n개의 일정한 각도로 나누어 중심점과 윤곽선과의 거리를 계산

– 윤곽선  n 차원의 시계열 데이터로 변환  시계열 매칭 사용 가능

Korea University 8

Boundary extraction

Transformation by CCD



Distance

Angle( ) Image domain Time-series domain

(9)

윤곽선 이미지 매칭

• 윤곽선 이미지를 시계열로 변환하여 이미지의 유사성 정의

• 윤곽선 이미지 매칭

Korea University 9

A B D(X,Y) ≤ε

윤곽선 시계열X 윤곽선 시계열 Y A 는 B 와 유사하다

이미지 이미지

데이터 시계열

유사하다

질의 시계열

유사한 이미지들

데이터베이스이미지

(10)

Challenging Problems

• 윤곽선 이미지 매칭에서

– 스케일링-불변 문제

– 노이즈 문제

– 회전-불변 문제

Korea University 10

?

생략

(11)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (1/18)

• 연구 동기

– 스케일이 왜곡된 이미지라 하더라도 매칭에서 제대로 찾을 수 있어야 함

Korea University 11

S1

S2

S3

( 2 1)

D S ,S

원본 이미지가 변환된 시계열의 거리 비교

(

2 3

)

D S ,S Similar?

I1

I2

I3

0 20 40

0 45 90 135 180 225 270 315

0 20 40

0 45 90 135 180 225 270 315

0 20 40

0 45 90 135 180 225 270 315

찌그러진 이미지

원본 이미지

원본이 다른 이미지

(12)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (2/18)

• 기존 이미지 도메인의 스케일링-불변 연구와의 차이점

– 이미지 x, y축에 다양한 스케일링 팩터 값을 허용함

• 기존 스케일링-불변 연구  이미지 x, y축에 동일한 스케일링 팩터 값만 허용함

– 대용량 이미지 데이터베이스 사용 가능

• 스케일링-불변 윤곽선 이미지 매칭

– 이미지를 가로 혹은 세로로 적당히 스케일링하여 유사한 이미지들을 찾는 작업

Korea University 12

질의 이미지

이미지DB

유사 이미지들 스케일된 이미지

α

β Similar?

(13)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (3/18)

• 스케일링-불변 윤곽선 이미지 매칭이 어려운 이유

– “적당히”라는 스케일링 정도, 즉 스케일링 팩터를 결정하기 어려움

– 이미지를 좌우로 혹은 상하로 어느 정도 스케일링해야 데이터 이미지와 의 거리가 가장 작아지는지를 쉽게 결정할 수 없음

– 이미지 도메인에서 스케일링 변환 시 많은 계산이 필요하며, 스케일링 팩 터가 동적으로 변화하기 때문에 실질적으로 사용하기 어려움

Korea University 13

원본 윤곽선 이미지

스케일링 시계열 변환

스케일된 이미지

스케일된 시계열

(a) 원본 이미지

si 1

si+ 1

si− θi

(x yi, i) (=sicos , sinθisi θi) 스케일링 (α,β)

(b) 스케일된 이미지

s′i 1

si′+ 1

si′− i′ θ

( )² ( )²

cos1

i i i

i

s x y

x s

−

′= ′ + ′

 ′ θ =′   ′

(x yi′ ′ = α β, i) ( x yi, i)

zi 1

zi+ 1

zi− θi

(1, ,..., , , ,...,2 1 2 )

() is an interpolation function.

i n n

z f s s s f

′ ′ ′ ′ ′ ′

= θ θ θ

(c) 보간에 의해 스케일된 시계열 보간

(14)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (4/18)

• 스케일링 거리 정의

가로축 스케일링 팩터 α와 세로축 스케일링 팩터 β에 의한스케일링 거리 SD(Q,S,α,β)는 다음 거리 식으로 정의

여기서, Z는 질의 시계열 Q가 (α,β)에 의해 스케일된 시퀀스

Korea University 14

데이터 이미지(원본)

데이터 시퀀스 S

질의 이미지

(원본) 질의 시계열 Q 스케일된 시계열

스케일된 이미지

D(S,Q)=201.8 스케일링 (α = 1.3)

스케일링 (β = 0.8)

스케일된 시계열 스케일된 이미지

SD

(

S

,

Q,

1.3

,

1)=159.8

SD

(

S

,

Q,

1

,

0.8)=245.9

가장 적합한 스케일링

팩터는?

(

, , ,

) (

,

)

SD Q S α β =D Z S

(15)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (5/18)

• 스케일링-불변 거리

– 특정 스케일링 팩터가 주어지지 않음

• 비교 이미지에 따라서 가장 적합한 스케일링 팩터를 선택한 후 스케일링 거리 를 계산

– 특정 스케일링 팩터 대신에, 스케일링 팩터의 구간 사용

– 해당 구간에서의 최소 스케일링 거리를 이미지간의 유사성 척도로 사용

• 정의

– 스케일링 팩터의 가로 및 세로 구간이 각각 과 로 주어졌을 때, 두 이미지(혹은 두 시계열)의 스케일링-불변 거리

는 다음 식으로 구해지는 거리

Korea University 15

[ , ] α α

_s _e

[ , ] β β

_s _e

(

, ,[ , ],[ , ]_s _e _s _e

)

SID Q S α α β β

( , ,[ , ],[ , ] min

_s _e _s _e

) {

⁽

, , , |

⁾ _s _e

,

_s _e

}

SID Q S α α β β = SD Q S α β α ≤ α ≤ α β ≤ β ≤ β

(16)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (6/18)

• 스케일링-불변 거리의 하한과 상한

– 스케일링-불변 거리를 구하는 것은 매우 어려운 문제

• 구간 안의 스케일링 팩터가 무한하기 때문

– 스케일링-불변 거리를 직접 구하는 대신 이 거리의 하한과 상한을 구하고, 이를 윤곽선 이미지 매칭에 활용

Korea University 1616

스케일링-불변 거리의 하한

L U stdiance S

angle

스케일링-불변 거리의 상한

L U stdiance S

angle

( )

( ) ( )

2

2 1

if

, ,[ , ],[ , ] if

0 otherwise

i i i i

n

s e s e i i i i

i

s u s u

LB Q S s l s l

=

 − >

α α β β =  − <



∑

( ) { ( ) (

²

)

²

}

1

, ,[ , ],[ , ]_s _e _s _e ⁿ max _i _i , _i _i

i

UB Q S s u s l

=

α α β β = ∑ − −

L = {l₁, l₂, …, l_n}은 Q가 에 의해 스케일된 시계열, U = {u₁, u₂, …, u_n}은 Q가(α βs, s) 에 의해 스케일된 시계열

(α β_e, _e)

(17)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (7/18)

• 스케일링-불변 유사 이미지

– 스케일링-불변 거리가 허용치 ε 이하인 시계열 S의 윤곽선 이미지

• 스케일링-불변 윤곽선 이미지 매칭

– 윤곽선 이미지 데이터베이스로부터 스케일링-불변 유사 이미지들을 모두 찾는 작업

Korea University 17

(18)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (8/18)

• 스케일링-불변 유사 이미지 판단 기본 알고리즘

– 분할-정복(divide-and-conquer) 전략의 재귀 알고리즘

– 자세한 알고리즘은 생략

Korea University 18

스케일링-불변 거리의 하한

L U stdiance S

angle

스케일링-불변 거리의 상한

L U stdiance S

angle

하한이 허용치를 초과하면 전지

상한이 허용치 이하이면 유사

판별

재귀적 호출

β

α

α_s αe

β_s β_e

(α α ) 2

s+ e

(β β ) 2

s+ e

스케일링 구간 변경

①

② ④

③

(19)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (9/18)

• 기본 알고리즘의 문제점

– 네 구간의 상한 및 하한 값을 고려하지 않음

– 무조건 정해진 순서에 의해서 호출이 일어남, 불필요한 공간을 탐색하는 문제점

• 스케일링-불변 유사 이미지 판단 탐욕적 알고리즘

① 네 구간의 상한과 하한을 각각 구하여,

② 상한이 작아서 유사 이미지로 판정될 가능성이 높거나

③ 하한이 커서 유사하지 않은 이미지로 판정될 가능성이 높은 구간을

④ 먼저 호출

Korea University 19

(20)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (10/18)

• 인덱스를 이용한 성능 향상

– 데이터베이스 내의 모든 시계열을 액세스하므로 많은 디스크 I/O를 유발 – 액세스한 모든 시계열에 대해서 스케일링-불변 유사 여부를 판단해야 하

므로, 많은 CPU 연산 또한 유발

• 스케일링-불변 이미지 매칭의 인덱스 기반 알고리즘

– 고차원 시계열을 그대로 다차원 인덱스 저장할 수 없음

• 시계열 고차원 문제로 성능 저하 발생  차원 축소로 해결

– PAA를 사용하여 변환된 저차원 시계열을 인덱스 저장하여 매칭에 사용

• 착오해답 발생  후처리 과정 진행(고차원 시계열 간의 유사 판별)

Korea University 20

(21)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (11/18)

• 보다 성능 향상을 위해 스케일링-불변 거리에 대한 인덱스 레벨의 하 한을 사용

– PAA 기반의 인덱스 레벨 하한을 계산함

– 유사하지 않은 이미지들을 인덱스 수준에서 신속하게 필터링 가능

Korea University 21

L U stdiancedistance S

dimension

L U S

PAA angle

( )

2 2 1

_ , ,[ , ],[ , ]

if if

0 otherwise

s e s e

i i i i

f

i i i i

i

LB index Q S

s u s u

n s l s l

f

=

α α β β

 − >



=  − <



∑

(22)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (12/18)

• 실험 데이터

– 약 9만 개 이미지 데이터베이스 구축

• 약 1만 개 원본 이미지 사용, 원본에서 여덟 개의 스케일된 이미지 생성

Korea University 22

α = 1.0, β = 0.75 Fix α = 1.0, change β

α = 1.0, β = 1.125

α = 1.0, β = 1.25

α = 0.75, β = 1.25

α = 1.25, β = 0.75

α = 0.75, β = 1.0

α = 1.125, β = 1.0

α = 1.25, β = 1. 0 Change α, fix β = 1.0

Change both α and β Original

image

스케일된 이미지: 원본 이미지에서x,y축의 α,β 팩터 값을 여덟 가지 경우로

변환하여 생성된 이미지

(23)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (13/18)

• 하드웨어 플랫폼

– UltraSPARC IIIi CPU 1.34GHz, 1.0GB RAM, 80GB 하드 디스크를 장착한 SUN Ultra 25

• 소프트웨어 플랫폼

– Solaris 10 운영체제

• 허용치 ε은 스케일링을 하지 않은 상태에서 자기 자신을 포함해서 두 개의 결과가 나오도록 결정

• **R*-트리 사용**

– 페이지 및 인덱스 페이지 크기는 4,096 바이트 – PAA 차원 축소 기법 사용 – 여덟 개의 특성 추출

Korea University 23

(24)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (14/18)

• 꽃잎 모양 이미지의 스케일링-불변 이미지 매칭 결과(허용치 = 45.0)

Korea University 24

[0.95,1.05]

[0.90,1.10]

[0.85,1.15]

[0.80,1.20]

[0.75,1.25]

[1.0,1.0]

Scaling ranges of αand β

Resulting images by the scaling-invariant boundary image matching

(25)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (15/18)

• 물병 모양 이미지의 스케일링-불변 이미지 매칭 결과(허용치 = 41.0)

Korea University 25

[0.95,1.05]

[0.90,1.10]

[0.85,1.15]

[0.80,1.20]

[0.75,1.25]

[1.0,1.0]

Scaling ranges of αand β

Resulting images by the scaling-invariant boundary image matching

윤곽선이 독특하지 않거나,

스케일링 팩터α, β의 범위가 증가함에 따라 스케일링-불변 효과를 가져옴과

동시에 다른 이미지를 유사하다고 판단할 가능성이 높아짐

(26)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (16/18)

• 다양한 다른 종류의 이미지 검색 결과

Korea University 26

Query image Type The number of Images

Scaling ranges of α and β

[1.0,1.0] [0.95,1.05] [0.90,1.10] [0.85,1.15] [0.80,1.20] [0.75,1.25]

Petal Matching images 2 3 4 9 9 9

Similar images 2 3 4 9 9 9

Clobber Matching images 2 3 4 6 8 9

Vase Matching images 2 4 4 6 10 11

Sock Matching images 2 2 3 6 6 9

Leaf Matching images 2 3 3 7 8 9

Duck Matching images 2 3 3 7 9 9

Hat Matching images 2 3 3 7 8 13

Doll Matching images 2 3 3 7 11 26

선형 보간의 오류로 인해 스케일링- 불변 거리가 허용치보다 더 커지기

때문에 아홉 개의 이미지를 모두 찾지 못함

(27)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (17/18)

• 재귀 깊이, 재귀 호출 횟수, 수행 시간의 평균 비교

– 허용치 변화 실험 결과 (스케일링 구간 고정)

– 스케일링 구간 변화 실험 결과 (허용치 고정)

Korea University 27

1.0 1.5 2.0 2.5 3.0

10 20 30 40 50

Recursive depth

Tolerance (ε) Basic Greedy

0.0 2.0 4.0 6.0 8.0

10 20 30 40 50

# of recursive calls

0.0 2.0 4.0 6.0 8.0

10 20 30 40 50

The elapsed time (msec)

(a) The average recursive depth. (b) The average # of recursive calls. (c) The average elapsed time.

1.0 1.5 2.0 2.5 3.0

[0.95,1.05] [0.85,1.15] [0.75,1.25]

Recursive depth

Scaling ranges of α and β Basic Greedy

0.0 2.0 4.0 6.0 8.0

[0.95,1.05] [0.85,1.15] [0.75,1.25]

# of recursive calls

0.0 2.0 4.0 6.0

[0.95,1.05] [0.85,1.15] [0.75,1.25]

기본 알고리즘은 주어진 순서에 의해 호출하기 때문에 하한에 의한 영향을 많이 받아

더 많은 재귀 호출이 발생

스케일링 구간이 증가할수록 검색 공간이 넓어지기 때문에

걸리는 시간 증가

(28)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (18/18)

• 성능 실험 – 인덱스 평가

– 허용치 변화에 대한 비교

• 인덱스 기반 매칭이 순차 매칭에 비해 1.8~8.8배까지 성능을 향상

– 스케일링 구간 변화에 대한 비교

• 인덱스 기반 매칭이 순차 매칭에 비해 3.1~66배까지 성능을 향상

Korea University 28

1.0E+03 1.0E+04 1.0E+05 1.0E+06

10 20 30 40 50

Tolerance (ε)

Sequential matching Index-based matching

1.0E+02 1.0E+03 1.0E+04 1.0E+05

[0.95,1.05] [0.90,1.10] [0.85,1.15] [0.80,1.20] [0.75,1.25]

Scaling ranges of α and β

Sequential matching Index-based matching

(29)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (1/11)

• 연구 동기

– 노이즈 (or 왜곡) 제거 정도에 따라 매칭 결과에 영향을 미침

• 노이즈 제거 파라미터 값에 영향을 많이 받음

• 실시간으로 매칭 결과를 확인하며 노이즈 제거 정도를 조절할 수 있는 윤곽선 이미지 매칭 제안

– 이미지 도메인에서는 전처리 과정(reprocessing)를 통해 일괄적으로 노이 즈 제거함

Korea University 29

(30)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (2/11)

• (k-)이동평균 변환

– 데이터 시퀀스의 연속되는

k개 값의 평균 값을

순차적으로 나열하는 변환

• 이동평균 변환에 의한 이미지 윤곽선의 노이즈 제거 효과

30

(c) 이동평균변환된 시계열들 (k=8).

0 10 20 30 40 50

0 45 90 135 180 225 270 315

0 5 10 15 20 25 30 35 40

0 45 90 135 180 225 270 315

IMG-1 IMG-2

0 5 10 15 20 25 30 35 40

0 45 90 135 180 225 270 315

0 10 20 30 40 50 60

0 45 90 135 180 225 270 315

(b) 윤곽선 이미지에서 변환된 시계열들.

(d) 이동평균변환이 적용 후 윤곽선 이미지들 (k=8).

IMG-1 IMG-2 (a) 노이즈가 있는 원본 이미지들과

그 윤곽선 이미지들.

IMG-1 IMG-2 IMG-1 IMG-2

노이즈의 영향을 감소시킴으로써 시계열 데이터 전체의 경향을 파악하는데 유용함

이동평균 변환을 사용하여 시계열 데이터에서 노이즈를

제거할 시, 원본 이미지 데이터에서도 노이즈가 제거될 것이라는 직관에 기반

(31)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (3/11)

•

k-계수 유사 거리

– 윤곽선 이미지의 유사 거리는 윤곽선 이미지의 노이즈 제거 정도에 따라 달라짐

•

k-계수 윤곽선 이미지 매칭

– 윤곽선 이미지 데이터베이스로부터

k-계수 유사 거리를 만족하는 윤곽선

이미지를 모두 찾는 작업

Korea University 31

A B

D(X

^(k),Y^(k)) ≤ε

윤곽선 시계열X 윤곽선 시계열 Y A 와 B 는k-계수 유사하다

X^(k)

이동평균변환 계수k

Y^(k)

이미지 이미지

이동평균변환

(32)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (4/11)

• 동작 프레임워크

Korea University 32

전처리 과정

윤곽선 이미지를 시계열 데이터로 변환

색인 구성

다계수 이동평균을 사용한 색인을 구축

범위 검색

이동평균 계수

k와

허용치ε으로 검색

(33)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (5/11)

• 다계수 이동평균변환을 사용한 인덱스 구축

– 다차원 인덱스에서 다계수 이동평균 변환[MK07]된 데이터 시퀀스의 집 합을 MBR(minimum boundary rectangle) 로 구성하여 임의의 이동평균 계수에 대한 질의 처리가 가능함

Korea University 33

• • •

Step (2)

Lower-dimensional transformation

•

• • S S a b[ : ]

• • •

Step (3) Multidimensional index

(S( )^[ : ])a b



•

• • S S a b[ : ]

k₁-moving average transform

••

• ^•^•^•

Step (1)

k₂-moving average transform k_m-moving average transform

( )^k1 [ : ] S a b

(^k2)[ : ] S a b

(^k^m)[ : ] S a b

• • •

Step (2)

Lower-dimensional transformation

•

• •

• • •

Step (3) Multidimensional index

(S( )^[ : ])a b



•

• •

(34)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (6/11)

• 이동평균 계수과 매칭 결과와의 관계

Korea University 34

정리: 이동평균 계수 k₁과

k

₂가 주어졌고, k₂ = 2k₁의 관계가 성립한다 하자. 그러면, k₂-계수 이미지 매칭의 결과는 항시

k

₁-계수 이미지 매칭 결과를 포함한다. 즉, k₁-계수 이미지 매칭 결과가

k

₂-계수 이미지 매칭 결과의 부분 집합이다.

k₂(= 2k₁)에 의한 유사 이미지들 k₁에 의한 유사 이미지들

(35)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (7/11)

• 실험 데이터

– 약 9만 개 이미지 데이터베이스 구축

• 약 1만 개 원본 이미지 사용, 원본에서 여덟 개의 노이즈가 적용된 이미지 생성

• 실험 환경

– R*-트리 사용

– DFT 차원 축소 기법 사용 – 여덟 개의 특성 추출

– 허용치는 이동평균변환 없이 자기 자신을 포함해서 두 개의 결과가 나오도록 결정

Korea University 35

블러 효과

(표준편차 값=1.5) 랜덤 노이즈 효과

(노이즈 양=25%) 원본 이미지

랜덤 노이즈 효과 (노이즈 양=50%) 블러 효과

(표준편차 값=3.0)

랜덤 노이즈 효과

(노이즈 양=50%) 랜덤 노이즈 효과

(노이즈 양=25%) 블러 효과

(표준편차 값=3.0) 블러 효과

(표준편차 값=1.5)

(36)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (8/11)

• 항아리 이미지의 매칭 결과

Korea University 36

(37)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (9/11)

• 노이즈가 있는 나뭇잎 매칭 결과

Korea University 37

k 값의 증가가 노이즈 제거 효과를 가져옴과 동시에 다른 이미지를 유사하다고 판단할 가능성도 높임

(38)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (10/11)

• 기존 shape 매칭 방법과 매칭 결과 비교

– 결과는 비슷하나, 수행 성능에서 큰 차이가 남

• Shape context matchin은 하나의 질의 이미지를 처리하는데 4.9분 걸림

• 제안한 방법은 725 마이크로 초 걸림

Korea University 38

(39)

노이즈 제거 윤곽선 이미지 매칭 [KMC+14] (11/11)

• 성능 실험 결과

– 인덱스 기반 매칭이 순차 매칭에 비해 6.7~29.4배까지 성능을 향상

Korea University 39

1 2 4 8 16 32 1 2 4 8 16 32 1 2 4 8 16 32

An index-based method A sequential scan

1 2 4 8 16 32 1 2 4 8 16 32 1 2 4 8 16 32 10E+6

10E+7 10E+8

The elapsed time (µsec)

Moving average order (k) Moving average order (k) Moving average order (k) 10E+5

(a) Selectivity=10E-4 (b) Selectivity=10E-3 (c) Selectivity=10E-2

선택률 = 질의 시계열과 유사한 데이터 이미지 개수 전체 데이터 이미지 개수

(40)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/8)

• 전체 노이즈 제거 문제 [KMC+14]를 확장하여 부분 노이즈 제거 문제 를 연구

• 연구 동기

Korea University 40

부분 노이즈는 매칭 결과를 왜곡시킬 수 있음

(41)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (2/8)

• 부분 노이즈 예제

• 기존 노이즈 제거 연구

– 이미지 전체의 노이즈 제거에 초점

• 노이즈가 이미지 전체가 아닌 일부에만 국한되어 나타날 수 있는데 , 이를 고려한 노이즈 제거 기반의 윤곽선 이미지 매칭이 필요함

Korea University 41

(a) 찢어진 나뭇잎. (b) 빛이 반사된 장미꽃. (c) 북채와 겹쳐있는 북.

윤곽선 이미지에 전체 노이즈 제거를 적용할 경우,

윤곽선이 왜곡될 수 있음

(42)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/8)

• 윤곽선의 부분 노이즈 제거가 어려운 이유

– 질의 윤곽선 이미지에 부분 노이즈가 있는 경우: 사용자가 노이즈를 찾아 원하는 만큼 노이즈를 제거하면 되는 비교적 간단한 문제

– 데이터 윤곽선 이미지에 부분 노이즈가 있는 경우: 모든 데이터 윤곽선 이 미지마다 부분 노이즈를 제거해야 하므로 매우 어려운 문제

Korea University 42

부분 노이즈 제거를 위해 고려해야 될

요소가 많음

(43)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/8)

• 이미지 도메인에서 부분 노이즈 제거된 시계열 구하기

– 부분 노이즈를 찾는데 많은 계산이 필요

– 부분 노이즈의 상태가 모두 다르기 때문에 실질적으로 사용하기 어려움

• 시계열 도메인에서 부분 노이즈 제거된 시계열 구하기

– 다양한 부분 노이즈의 빠른 제거가 가능

–

정확한 부분 노이즈를 찾는데 초점이 있는 것이 아니라 부분 노이즈가 어 디 있든 무관하게 유사 윤곽선 이미지들을 찾는데 초점

Korea University 43

(44)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/8)

• 부분 노이즈 제거 시계열

– 노이즈를 찾았다고 가정

• 부분 노이즈 제거 거리

– 노이즈 제거 길이

l과 이동평균 계수 k가 주어질 때, 부분 노이즈의 모든

위치를 고려한 부분 노이즈 제거 시계열들과의 최소 거리

Korea University 44

l

노이즈 제거 서브시퀀스 k-이동평균 변환 노이즈 제거 길이

부분 노이즈 제거 시계열 X

ik

X

, ik l

X

i

시계열 변환

부분 노이즈 제거된 윤곽선 이미지

모든 위치를 고려하여 가장

작은 거리

Subsequence including partial noise

부분 노이즈가 포함된 이미지 Denoising subsequence

부분 노이즈가 제거된 이미지

이동평균변환 적용

질의 이미지

모든 가능한 부분 노이 즈 위치를 고려함 모든 위치에 부분 노이즈 제거 적용

(45)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/8)

• 부분 노이즈 제거 유사 이미지

– 부분 노이즈 제거 거리가 허용치 ε 이하인 시계열의 윤곽선 이미지

• 부분 노이즈 제거 윤곽선 이미지 매칭

– 이미지 데이터베이스로부터 부분 노이즈 제거 유사 이미지들을 모두 찾 는 작업

• 기본 매칭 알고리즘

– 데이터베이스 내의 모든 시계열을 액세스하므로 디스크 및 CPU 오버헤 드를 심하게 유발시키는 문제 발생

– 부분 노이즈 제거 거리의 계산 복잡도:

• 비교해야 하는 시계열이 많은 경우, 매칭 성능 저하의 주요 원인

Korea University 45

( ^{n l d}

²

)

Θ  ⋅ ⋅ ⋅

(46)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/8)

• 부분 노이즈 제거 거리의 하한

Korea University 46

2

1 2

0

( ) if ;

_ ( , , , ) ( ) if ;

0 otherwise.

i i i i

n

i i i i

i

q u q u

PD LB Q S l k ⁻ q l q l

=

 − >

=  − <



∑

{ } { }

1 1

0 1 1 0 0 1 1 0

where { , , , _n }, _i min ,ⁿ _{i i}^k and { , , , _n }, _i max ,ⁿ _{i i}^k .

i i

L= l l  l − l = =⁻ s s U = u u  u − u = =⁻ s s

(47)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/8)

• 실험 데이터

– 약 십만 개 이미지 데이터베이스 구축

• 약 1만 개 원본 이미지 사용, 원본에서 아홉 개의 부분 노이즈가 적용된 이미지 생성

Korea University 47

(48)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (1/10)

• 나뭇잎 매칭 결과

• 기존 방법과 매칭 결과 비교

Korea University 48

(노이즈 제거 길이 고정, l=108) (노이즈 제거 레벨 고정, d=24)

(49)

부분 노이즈 제거 윤곽선 이미지 매칭 [KML16] (11/11)

• 노이즈 제거 계수 변화에 대한 비교 성능 실험

– 개선된 알고리즘이 기본 알고리즘에 비해 약 11~23배 성능 향상

• 노이즈 제거 길이 변화에 대한 비교 성능 실험

• 유사 이미지 개수 변화에 대한 비교 성능 실험

Korea University 49

1.0E+07 1.0E+08 1.0E+09 1.0E+10

6 12 24 36 48

The elapsed time(μsec)

Denoising order

Naïve-range Naïve-kNN Adv-range Adv-kNN

1.0E+07 1.0E+08 1.0E+09 1.0E+10

36 72 108 144 180

Denoising length Naïve-range Naïve-kNN Adv-range Adv-kNN

1.0E+07 1.0E+08 1.0E+09

1 10 100 1000 10000

similar image(s) Naïve-range Naïve-kNN Adv-range Adv-kNN

(50)

결론

• 시계열 매칭 기술을 활용한 대용량 이미지 데이터베이스 대상의 윤곽 선 이미지 매칭 제안

– 이미지 도메인에서 시계열 도메인으로 문제를 전환하여 해결을 시도하는 새로운 접근법

• 윤곽선 이미지 매칭에서 스케일링-불변 문제 해결

• 윤곽선 이미지 매칭에서 전체 노이즈 & 부분 노이즈 제거 문제 해결

Korea University 50

(51)

참고 문헌

[FS78] H. Freeman and A. Saghri, “Generalized Chain Codes for Planar Curves,” In Proc. of the 4th Int’l Joint Conf.

on Pattern Recognition, Kyoto, Japan, pp. 701-703, Nov. 1978.

[BMP02] S. Belongie, J. Malik, J. Puzicha, “Shape Matching and Object Recognition Using Shape Contexts,” In IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 24, No. 4, pp. 509-522, Apr. 2002.

[ZL04] D. Zhang and G. Lu, “Review of Shape Representation and Description Techniques,” Pattern Recognition, Vol. 37, No. 1, pp. 1-19, Jan. 2004.

[MKK+10] Y.-S. Moon, B.-S. Kim, M. S. Kim, and K.-Y. Whang, “Scaling-Invariant Boundary Image Matching Using Time-Series Matching Techniques,” Data & Knowledge Engineering, Vol. 69, No. 10, pp. 1022-1042, Oct. 2010.

[KMC+14] B.-S. Kim, Y.-S. Moon, M.-J. Choi, and J. Kim, “Interactive Noise-Controlled Boundary Image Matching Using the Time-Series Moving Average Transform," Multimedia Tools and Applications, Vol. 72, No. 3, pp.

2543-2571, Oct. 2014.

[MK07] Y.-S. Moon and J. Kim, “Efficient Moving Average Transform-Based Subsequence Matching Algorithms in Time-Series Databases.,” Information Sciences, Vol. 177, No. 23, pp. 5415-5431, Dec. 2007.

[KML16] B.-S. Kim, Y.-S. Moon, and J.-G. Lee, “Boundary Image Matching Supporting Partial Denoising Using Time-Series Matching Techniques,” Multimedia Tools and Applications, Apr. 2016.(online version)

Korea University 51

(52)

Q & A

Korea University 52

시계열 매칭 기술을 활용한 윤곽선 이미지 매칭 연구

시계열 매칭 기술을 활용한 윤곽선 이미지 매칭 연구

2017. 3. 21 김범수

고려대학교

데이터 인텔리전스 연구실

목차

• 이미지 매칭

• 모양(shape) 매칭

• 시계열 매칭

• 윤곽선의 시계열 데이터 변환

• 윤곽선 이미지 매칭

• Challenging Problems

• 스케일링-불변 윤곽선 이미지 매칭

• 노이즈 제거 윤곽선 이미지 매칭

• 부분 노이즈 제거 윤곽선 이미지 매칭

• 결론

이미지 매칭

• CBIR (content-based image retrieval)

모양 (shape) 매칭(1/2)

• 이미지의 모양 특성을 기반으로 유사 이미지를 찾는 작업

• 모양 특성들 (shape features)

모양 (shape) 매칭(2/2)

• 기존의 모양 매칭(검색) 연구

• 대용량 데이터베이스 대상의 상호 작용(interactive)이 가능한 대화형 매칭 시스템을 위해 빠른 매칭이 필요함

시계열 매칭 기술을 활용한 윤곽선 이미지 매칭 제안

시계열 매칭 (1/2)

• 시계열 데이터 (time-series data)

• 시계열 매칭

시계열 매칭 (2/2)

• 시계열 매칭의 특징

윤곽선의 시계열 데이터 변환

• CCD (centroid contour distance)

윤곽선 이미지 매칭

• 윤곽선 이미지를 시계열로 변환하여 이미지의 유사성 정의

• 윤곽선 이미지 매칭

A B D(X,Y) ≤ε

Challenging Problems

• 윤곽선 이미지 매칭에서

?

?

?

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (1/18)

• 연구 동기

(

)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (2/18)

• 기존 이미지 도메인의 스케일링-불변 연구와의 차이점

• 스케일링-불변 윤곽선 이미지 매칭

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (3/18)

• 스케일링-불변 윤곽선 이미지 매칭이 어려운 이유

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (4/18)

• 스케일링 거리 정의

SD

S

Q,

,

SD

S

Q,

,

(

) (

)

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (5/18)

• 스케일링-불변 거리

• 정의

[ , ] α α

[ , ] β β

(

)

( , ,[ , ],[ , ] min

) {

, , , |

,

}

SID Q S α α β β = SD Q S α β α ≤ α ≤ α β ≤ β ≤ β

스케일링 -불변 윤곽선 이미지 매칭[MKK+10] (6/18)

• 스케일링-불변 거리의 하한과 상한

( )

( ) ( )

• **R*-트리 사용**