Image inpainting(3)

A. A. Efros and W. T. Freeman, “Image quilting for texture synthesis
and transfer” 논문을 리뷰 해보는 시간을 갖겠습니다.

Abstract

이미지들의 작은 패치들을 이용해 한땀한땀 바느질 하듯이 새로운 이미지를 synthesis 하는 방법 - Image quilting 을 제시하고 있습니다.

1. Wide range Image를 synthesis 할 수 있다.
2. synthesis 뿐만 아니라 texture transfer 에도 확장시킬 수 있다.

위와 같은 특징들을 말하고 있으며, 3D Information 같은 다른 정보 없이 이미지 자체적으로 수행될 수 있다고 말하고 있습니다.

Introduction

Texture synthesis 에서는 주로 실제 세계에서 small patch들을 떼 와서 그걸 바탕으로 synthesize 하는 것이 대부분이고, scratch 부터 recreate 하는 경우는 거의 없다고 합니다.

간략하게 synthesis 과정을 설명하자면 texture sample을 통해서 무한한 양의 image를 생성하는 것인데, 이때 image가 실제와 완전히 같지는 않더라도 인간이 보았을 때 texture sample과 same texture로 인지될 수 있는 정도의 image 입니다.

이런 synthesis 과정은 texture transfer에도 유용하게 사용될 수 있습니다.

본 논문에서는 synthesis를 위한 매우 간단한 알고리즘과 texture transfer에서는 이 알고리즘이 어떻게 쓰이는지에 대해 제안을 합니다.

Quilting

Algorithm

synthesis 과정에 관한 설명입니다.

$B_i$ : 정사각형 block(User specified size)
$S_B$ : input texture image를 구성하고 있는 block들의 집합

우선 synthesis 할 이미지를 block 단위로 raster scan을 수행합니다.

그 후 각 location마다 overlap constraints를 만족하는 block set을 구하고, 그 block set에서 무작위로 block 하나를 추출합니다.

추출된 block과 원래 있던 block에 대해 겹친 부분(overlap region)에 대해 Dynamic programming을 이용해 최소의 cost를 구하고, 최소의 cost 일 때 어떻게 겹쳐졌는지(어떤 boundary 기준으로 겹쳐졌는지)를 구합니다.

Minimum Error Boundary Cut

Dynamic programming 에 이용되는 수식은 다음과 같습니다.

$B_1, B_2$ : 겹쳐져 있는 두 blocks
$B^o_1, B^o_2$ : 각 block에 대해 겹쳐져 있는 부분
$e$ = $(B^o_1 - B^o_2)^2$ : error
$E_i,_j$ = $e_i,_j$ + $min$$($$E_i$$_-$$_1$$_,$$_j$$_-$$_1$ , $E_i$$_-$$_1$$_,$$_j$ , $E_i$$_-$$_1$$_,$$_j$$_+$$_1$)

다음과 같은 수식을 이용해 최소의 cost(error)를 찾고 그때의 boundary를 찾는 알고리즘 입니다.

이 논문에서 overlap constraints는 최적의 matching block (즉 겹쳤을 때 error 값이 가장 작은 block) 과 0.1배 이상 차이가 나지 않을 경우 block set에 넣을 수 있음으로 설정했습니다.

(a) : random하게 block들을 배치한 경우
(b) : overlap constraints 만 반영해 배치한 경우
(c) : Dynammic programming을 이용해 최적의 boundary를 찾아 반영한 경우

입니다.

사진만 봐도 (c)가 가장 자연스러움을 알 수 있습니다.

Synthesis Results

사진은 실제 synthesis 결과 입니다.

Texture structure가 잘 보이는 sample 에서도 잘 동작할 뿐만 아니라, stochastic texture에서도 잘 작동함을 확인할 수 있었습니다.

또한 MATLAB code를 이용해 구현했는데, algorithm 수행시간도 input과 output size와 block size에 따라 15초에서 몇 분정도 걸리는 매우 짧은 수행시간을 확인할 수 있었습니다.

Texture Transfer

Image quilting algorithm이 local image information을 기반으로 output을 낸다는 점에서 transfer에서도 잘 적용할 것이라 생각했습니다.

Correspondence map $C$와 원래 synthesis algorithm을 둘 다 만족시킬 수 있는 image patch를 이용하는 것으로 algorithm을 증강시켰습니다.

Correspondence map은 source image와 target image의 Image intensity, orientation angle과 같은 quantity를 포함하고 있는 spatial map을 의미합니다.

사진은 texture transfer의 한 예시 입니다.

여기서 correspondence map은 Image intensity가 사용되었습니다.

즉, input에서 남자의 얼굴 중 밝은 image patch와 쌀의 밝은 image patch에 있어서 low correspondence error을 갖게 되는 것 입니다.

Texture transfer는 두 가지 부분이 지켜져야 하는데
1. Output은 Source image(위의 예시에서는 쌀)의 synthesis 중 한 예시
2. correspondence map이 잘 반영 될 것
입니다.

Algorithm 수정의 경우 우선 사용하던 Error term을 수정했습니다.

$\alpha$ times 동안에는 원래 사용하던 error인 overlap matching error을 더해주고
(1-$\alpha$) times 동안에는 correspondence map과의 squared error를 더해줍니다.

즉 $\alpha$가 correspondence map과 texture synthesis 사이의 tradeoff 관계를 결정하는 것 입니다.

이런 추가적인 constraints가 생김으로써 synthesis 결과가 만족스럽지 못한 경우가 생기는데, 이럴 경우에는 block size를 달리 해주면서 몇 번의 반복을 합니다.

Conclusion

Texture syntheis의 한 방법으로 Image quilting을 제시했습니다.

상당히 간단한 방법임에도 불구하고 A. A. Efros and T. K. Leung, "Texture Synthesis by Non-parametric Sampling" 이 방법보다 좋은 결과를 냈습니다.

또한 Texture transfer로도 적용될 수 있음을 보여줬습니다.