[ACM SIGGRAPH '2004] Feature Matching and Deformation for Texture Synthesis Qing Wu Yizhou Yu University of Illinois at Urbana-Champaign Abstract 패치기반의텍스쳐합성(synthesis) 에서중요한문제는인접한패치의 경계면에서찢어진모양이나타난다는것. 이러한이유는, 패치합병을위한최적화설계가부정확한유사측정으 로인해이웃검색이샘플텍스쳐에서만족스러운후보를찾지못할때 실패하기때문. 이논문에서, 우리는곡선의특징과변형에대해서모두고려함. 우리는구조상의유사도측정에의해서특징을맞추고정렬을수행하는 새로운알고리즘을개발함. 우리의기술은 feature map 을샘플텍스쳐에서추출하며, 새로운 feature map 과텍스쳐맵을생성함. Feature map에의해서좌우되는텍스쳐합성은 feature의불연속성과 관련된현상을상당히줄일수있으며만족할만한결과를냄. 1. Introduction 텍스쳐합성은컴퓨터그래픽스분야에서중요한연구주제로인식되어옴. 이웃에기반한합성(synthesis) 방법 -1-
[Efros and Leung 1999; Wei and Levoy 2000; Ashikhmin 2001; Liang et al. 2001; Hertzmann et al. 2001; Efros and Freeman 2001; Zhang et al. 2003; Kwatra et al. 2003] 패치에기반한방법 [Liang et al. 2001; Efros and Freeman 2001; Kwatra et al. 2003] 그러나두개의인접한패치의경계면에서깨진모양이나타나는것은여전히심각한문제이며, [Efros and Freeman 2001; Kwatra et al. 2003] 에서그러한현상을완화하는시도를함. 이러한이웃에기반한알고리즘은두단계가있음. ii) 샘플텍스쳐에서이웃과가장비슷한배경을검색함. ii) 합성된출력텍스쳐를이용하여패치나픽셀을합침. [Efros and Freeman 2001] 의동적프로그래밍과 [Kwatra et al. 2003] 의그래프컷 은패치를합성하는단계를최적화하는데사용됨. 이러한알고리즘의문제점은두번째단계를위한최적화방법이, 첫번째단계가부 정확한유사방법때문에충분한이웃들을찾을수없을때부드러운변화를찾는데 실패한다는것. 우리는현저한특징과변형을이용하여텍스쳐합성을제안함. 우리는지각유사성을측정할때모든픽셀이똑같이중요하지는않다는것을주목함. 훌륭한지각측정방법은인간의시각시스템이텍스쳐에서에지(edge) 와 corner, 그리 고다른높은수준의모양에민감하다는사실을설명해야함. 우리는이러한높은수준의특징을구조상의정보라칭함. 구조상의유사점은이웃을찾는동안중요한요소임. 여태까지, 색의 summed squared differences (SSD) 는텍스쳐패치사이에유사점을 측정하는데가장일반적으로사용됨. 이는구조상의정보를획득하는데썩좋지는않음. 구조상의정보를위한바람직한측정기준은대응되는특징사이에서최소한의누적된 거리를추정하는것. 이에반해서, 작은양의변형은시각적불연속성보다눈에띄지않음. 텍스쳐합성에서이웃검색은컴퓨터비전에서 [Zitova and Flusser 2003] 의이미지 registration 과매우흡사함. -2-
변하지않는 template 매칭은이러한 registration 방법에서가장간단함. [Zitova and Flusser 2003] 에서, 물체특징과모양은다른이미지에서다른수준의 왜곡을가지기때문에변형가능한 template 와융통성있는매칭은일반적이지않음. 변형은이웃한정규패턴을이용하여텍스처의부분집합에대해서도고려됨. [Liu and Lin 2003] 일반적인텍스쳐합성에대해서변형가능한모델을갖는것은매우바람직함. 두텍스쳐이웃들사이에시각적으로다른점은색차이와모양변형에대해서반영해 야한다는것. 이미지registration 기술의큰부분, 특히흥미있고관련있는것은두개의이미지로 부터그사이의거리의평균을최소화시켜서특징을맞추는것으로소개된 [Barrow et al. 1977; Borgefors 1988] 임. 위의방법에영감을받아, 우리는특징정렬을하는동안특징매칭과패치변형사이 에구조적유사성을고려하는새로운특징합성알고리즘을개발함. 우리는 feature 와색을동시에고려하는텍스쳐합성방법을개발함. 이방법에서,feature 들은지표로써사용되며텍스쳐합성을향상시킴. 2. Curvilinear Feature Matching and Synthesis 에지나리지(ridge) 와같은곡선으로만들어진얇은 feature는텍스쳐의총체적인구조 -3-
상의배치를제공함. 텍스쳐의곡선의 feature 집합은원본텍스쳐의 feature map으로불리는바이너리이 미지로표현될수있음. 이장에서, 우리는존재하는것으로부터새로운 feature map 을합성하는, 간단하지만 효율적인알고리즘을소개함. 보편성의상실없이, 우리는이알고리즘을패치기반의합성환경에서제안함. 곡선의 feature detection은 2.3 장에서설명될것임. 입력의예와합성된feature map은그림1 에나와있음. 2.1 Curvilinear Feature Matching 우리는feature 매칭을할때두개의항위치와기울기방향의차이을고려함 ( ) feature를매칭하는도중위치의작은차이가그사이의작은틈을나타내기때 문에위치는중요함. 일관된기울기방향은바람직한기하학적연결성과 feature를매칭하는도중시 각적부드러움을보장해주는데중요함. 출력된 feature map 에서새로운패치를삽입하는것을고려함. 이패치는이미합성된부분에서 L 모양의 context region 을가짐. ( 그림 2(a)) Context region에서픽셀위치의집합은 로표현됨. 우리는가장좋은매치를찾을때, 입력된 feature map에서context region을모든가 능한위치로간단히변형함. Context region은입력feature map 에서겹치는부분을가짐. 이영역은context region의변환벡터 에의해명기됨. -4-
이렇게겹쳐진부분에서 feature의집합은 으로표현됨. 앞서말한 feature의두집합사이의매칭 cost는일반적으로첫번째집합에서 와두번째집합에서모든 feature 사이의가장짧은거리를요함. 두번째집합에서가장짧은거리를달성하게하는 feature는 에대응되는 feature 로정의될수있음. 우리는이러한대응을표현하기위해 non-parametric 매핑 를사용함. 우리의 feature 매칭 cost는실질적으로 Euclidean 거리이외에도기울기벡터의차이 를고려하기때문에, 를직접계산하는데 시간이걸림. 값비싼계산을피하기위해, 우리는기울기방향의 quantization을통해 의값을 추정함. 바람직한방향에대해서좀더빠르게 feature를찾기위해불연속의 quantization 레 벨들은 " 물통(buket)" 의역할을함. 거리변형은 feature에대해서같은 quantization 레벨로수행될수있음. 이러한거리변형은바람직한방향에대해서가까운 feature를정하는것을일정시간 에가능하게함. 에서기울기의방향은 4개의간격으로일정하게 quantize 됨. ( 그림 2(b)) 각각의간격은두개의서로다른방향을포함함. 어떠한구간의기울기가속하는것에의존하여우리는 feature 픽셀을 4그룹의하나 로분류함. 두인접한그룹은인접한방향의구간을가지는것처럼우리는그룹을분류함. 과 은인접한것으로고려됨. 비슷하게, 에대해서방향에기반한분류는 로나타냄. 으로분류된 feature 을고려함. 기울기일관성을유지하기위해,, 후보로고려됨. 또는 의 feature들만 는이러한세그룹중에서가장가까운feature 를가짐. 를위한 이러한가장가까운feature들은 에서각각,, 로나타남. -5-
우리의feature 픽셀쌍사이의새로운거리계산법은다음과같이정의됨. (1) : 에서의기울기 : 에서의기울기 : 기울기상수의계수 우리의근사해 은 를만 족함. 그림 3 은기울기계수의필요성을설명함. Feature 매칭을위해, 우리는좀더좋은튜닝이가능하더라도단순히 로설정 함. Feature 정렬을쉽게하기위해, 1:1 매핑을하는것이바람직함. 그러므로우리는 위에서 매핑의대응관계(bijectivity) 를측정하기위해 다른 를정의함. 은 에서같은 feature 로매핑되는다른 feature 의개수를표현함. Feature의두집합사이의매칭 cost는 와 의대응관계에의한변형의양에 독립적으로정의됨. 매칭 cost 는다음과같이계산됨. -6-
(2) : 두항사이에상대적인중요성을조정하는데쓰이는양수의가중치값 모든실험에서, 우리는거리가픽셀사이에서계산될경우 으로사용함. 위의매칭 cost를최소화시키는 translation 벡터 는입력feature map에서최적의 매칭패치를나타냄. 마지막으로, 우리는 context region으로부터관계없는대응 feature를없애는것에의 해 1:1 매핑을수행함. 우리는입력 feature map에대해네그룹에서 feature를위한각각의 transform을이 용하여 4종류의 distance transform 을미리계산함. 이러한 distance transform은 level set 방법[Sethian 1999] 을사용하면효과적으로 계산할수있음. Distance map의모든픽셀에서우리는가장가까운 feature 픽셀을가리키는 pointer 를저장함. 한편, 입력 feature map에서모든 feature 픽셀은현재의 context region에서대응되 는 feature 의개수를나타내는카운터를가지고있음. 이러한자료구조에대해서, 위에서언급한겹쳐진지역의쌍사이에매칭 cost를계 산하는것은보통이미지에서드문드문퍼져있는 시간복잡도를가짐. feature 픽셀의숫자에대하여선형 2.2 Feature Alignment Using Deformation Feature 매칭 cost 가앞장에서정의되었다고하더라도, 입력텍스쳐가비주기적이고 context region의정확한복사본을포함하고있지않을때 feature의잘못된정렬은남 아있음. 출력 feature map 으로최적의매칭패치를합치는것은 [Efros and Freeman 2001; Kwatra et al. 2003] 의기술로는제거되지않는불연속을만들어냄. -7-
임의의단계로써, 우리는이미지에서작은양의변형을도입함으로써 feature가잘못 정렬된것을깔끔하게제거함. 이는부드러운 warping 함수를사용한알맞은패치변형에의해서쉽게달성됨. 우리는먼저 context region과최적의알맞은패치사이에서성긴 feature를얻기위해 새로운 feature 매핑 를계산함. 이러한매핑은일반적으로 feature 매칭을하는동안얻어진매핑 와는다름. 현재의 context에서매핑 는 (2) 만큼의동일한매칭 cost 를사용하지만, 기울기를 강조하기위해 (1) 에서 를 10 으로설정하여계산됨. Warping 함수는최적의알맞은패치를각 feature 가 context region에서이에대 응되는 feature 로이동하는동안부드럽게변형시켜야함. 최적의알맞은패치는 4 개의경계가있다는것을명심해야함. 변형의누적을방지하기위해, 우리는오른쪽과아래의경계면의픽셀이 warping 하는 동안고정되어있어야한다는것이필요함. 이러한고정된픽셀들은역시나 warping 함수는무난해야한다는제한으로고려됨. Warping 함수를얻는것은흩뿌려진데이터 interpolation 과동일함. 우리는일반적인두가지 interpolation 기술을적용함. Thin-plate splines(tps) [Meinguet 1979; Turk and O'Brien 1999] Spepard's method [Hoschek and Lasser 1993] Thin-plate spline은 warp 제한을만족시키는모든 interpolant중에서가장작은 bending 에너지를가짐. 하지만, thin-plate spline은때때로나쁜조건을가지는 linear system을푸는것 이필요함. 그래서성긴 feature 대응이주어지고, 우리는먼저 thin-plate spline interpolation 을적용함. 만약, 결과 warping 함수가 warp 제약을만족하지못할경우우리는 Shepard's method 로변경함. -8-
2.3 Feature Detection 이논문에서, 우리는에지나리지같은 feature 를쉽게찾는것을고려함. 에지를찾기위해, 우리는먼저에지를날카롭게하는 bilateral 필터링을적용함. [Tomasi and Manduchi 1998] [ 원본이미지] [1 회수행] [5 회수행] [ Bilateral Filtering] [ 원본이미지] [Radius 1.6 Pixel] [Radius 3.2 Pixel] [ Laplacian Filtering ] Bilateral 필터에서, 근사함수 의계수는언제나 2.0으로맞추었으며유사함수 의계수는 256 greyscale 레벨중에서 10 으로맞춤. 우리는모든픽셀에서에지반응(response) 을얻기위해, 간단한 gradient estimator로 두이미지축을따라서미분을사용함. 이는두단계로분류됨. 첫번째단계로, 전체적인높은 threshold는보통작은조각으로깨지는강한에 지를찾는데사용됨. 두번째단계에서, 공간적으로변화하는낮은 threshold는각각의강한에지의이 -9-
웃에서약한에지를찾는데사용됨. Canny detector[canny 1986] 에서낮은 threshold 와는다르게, 그것은첫번째단계 에서찾아진픽셀의에지반응에지역적으로의존함. 실험을통해, 우리는고정된비율 를찾음. 반응하는강한에지주위의이웃을위한낮은 threshold는 로정함. 두번째단계는깨진강한에지를효과적으로연결할수있음. 리지를찾기위해, 우리는 bilateral 필터링다음에 Laplacian 필터를적용함. 모든픽셀에서필터반응이있더라도, 에지를위한동일한두단계의분류가리지에도 적용됨. 이논문에서보여주는결과를위해, 는항상0.3 으로정해짐. 전체적인높은 threshold 는먼저, 전체이미지에서가장높은필터반응의고정된백 분위수를이용하여자동으로추정됨. 이는결과를향상시키기위해사용자에의해서로조정될수있음. 찾아진에지나리지는다양한픽셀너비를가지기때문에, 우리는수정된 feature의 연결성을보장해주는동안약한필터반응으로부터픽셀들을제거해주는 고리즘을적용함. 결과feature 는언제나하나의픽셀너비를가짐. thinning 알 Thinning 알고리즘에대한상세한논의는 [Pavlidis 1982] 에서발견할수있음. 찾아진각각의 feature 픽셀에서, 우리는그색과부드러운기울기를그의성분으로 저장함. 3. Feature-Guided Texture Synthesis 우리의 feature map 합성은기존의패치기반의텍스쳐합성알고리즘 [Liang et al. 2001; Efros and Freeman 2001; Kwatra et al. 2003] 과서로보완적임. 텍스쳐합성에서 feature map 을통합시키기위해, 우리는주어진입력텍스쳐와그 feature map으로부터새로운텍스쳐와그 feature를동시에만드는 hybrid 방법을고 안함. 새로운패치를삽입하기위해우리는항상 feature 매칭과 color 매칭을동시에고려 함. -10-
우리는 feature 를위해 (2) 에서의매칭 cost와색을위한 SSD 를적용함. 매칭 cost 의합은이러한두개사이의가중평균임. 샘플텍스쳐로부터매칭패치가골라지면,2.2 장에의해서변형됨. 각각의출력텍스쳐에서알맞은패치를합치기전에, 우리는패치경계면에서변화를 향상시키기위해 graph cuts [Kwatra et al. 2003] 을적용함. 그림 1은 feature map 으로부터의합성예제를보여줌. 그림 1 의두번째줄에서보여주는것과같이, 확률적인 feature map은남부럽지않 은합성결과를만들어낼수있음. 우리의방법과다른 3개의알고리즘의비교는그림 4 에있음. 이는우리의방법이텍스쳐에서각각의물체의모양과마찬가지로그것들을합치지않 고구조적인 feature 의연속성을유지하는데매우좋다는것을나타냄. 그림5에서주어진좀더많은합성예제에서출력텍스쳐의해상도는256x256 임. 텍스쳐합성을위한실행시간은 Pentium 4 2.0Ghz 에서, 128x128과 256x256의해 상도를각각가지는샘플과출력텍스쳐에대해서 2 분보다적게걸림. 패치크기는 32x32에서 64x64 사이에서골라지며, feature와 SSD color 매칭 cost 사 이의상대적인가중치는항상 0.5 로맞춤. 약간의샘플텍스쳐( 그림 1 에서마루와꽃, 그림 5 에서잎과물) 를위해, 그것의회전 되거나반사된버전들역시다양한텍스쳐변화를제공하기위해우리프로그램의입 력으로표현됨. 4. Discussion 이논문에서, 우리는새로운 feature에기반한 local curvilinear feature 매칭과텍스쳐 warping 의사용을통해기존의텍스쳐합성기술을확장하는합성방법을소개함. 이러한 feature 가존재하지않을때, 우리의기술은색에기반한방법으로돌아감. 수동적인조정이필요했던 texton mask extraction [Zhang et al. 2003] 과는다르게, 그방법은우리의 feature map 을자동으로얻는데쉬움. 샘플텍스쳐의 feature map은역시우리의 user interaction 에의해향상될수있음. 가장중요한새로운 feature map은 curvilinear feature를위해사용자가설계한새로 운매칭표준을이용하여합성됨. 이러한표준은좀더좋은결과를얻기위한텍스쳐합성의지표가됨. -11-
-12- Byungseok Roh