PatchMatch Stereo - Stereo Matching with Slanted Support Windows

 

내 맘대로 Introduction

 

엄청 오래 된 2011년 논문이다. 그 당시 딥러닝 없이 이미지 disparity 찾는 기술 중 가장 유명한 것이 patch match였고 이를 stereo에 확장한 논문이다. 이제는 더 이상 활용할 수 없을 정도로 오래 된 논문이기는 하지만 몇몇 MVS 논문들에서 여전히 기본으로 깔고 가는 논문이기도 해서 간단히 정리해두고 한다. 

 

patchmatch의 핵심 아이디어는 픽셀마다 패치를 할당하고 이미지 A, B 패치 간의 매칭을 무작위로 수행한 뒤, 우연히 잘 된 매칭이 있다면 이를 propagation해서 주변을 점진적으로 매칭해나가는 방식이다. 

 

patchmatch stereo는 patchmatch의 컨셉을 가져와 픽셀마다 3d plane(정확히는 dispairty plane)을 할당하고 left, right 이미지 간 매칭을 무작위로 수행하고, 우연히 매칭이 잘된 픽셀이 있다면 그 주변부로 propagation하면서 disparity를 점점 채워나가는 방식이다. 이미지 패치가 3d disparity plane으로 바뀐 점, 그리고 무작위로 매칭 수행하는 것이 rectifed line search로 조금 좁혀진 점이 특징이다. 

 

성능은 더 이상 중요하지 않은 논문이므로 아이디어만 짚고 넘어가고자 한다.

 

메모하며 읽기

픽셀마다 할당하는 plane은 독특하게 3d plane이 아니고 disparity space에서 정의된 plane이다. real scale 3d plane으로 할 경우, 범위가 너무 넓기 때문에 disparity space에서 정의하여 자유도를 낮췄다.  disparity는 사실 3d plane의 normal을 알고 있으면 환산할 수 있는 값이기 때문에 물리적으로는 의미가 같다.  normal과 비슷한 개념인 disparity gradient로 표현되는 수식(1)이 disparity plane이다. ---- pixel p, 해당 plane fp을 모두 할당하고 나면 이제 cost를 정의해야 한다. 어떻게 pixel, plane끼리 비교할 지 기준을 만들어야 plane을 업데이트할 수 있으니 말이다.  수식(3)이 해당 코스트인데, p가 주어졌을 때 p 주변 window 범위를 잡고 fp를 이용해 right 이미지로 warping한다. 그리고는 수식(5)와 같이 color, color gradient가 같은지 확인하는 것이다.  plane이 정확하다면 left-to-right warping이 정확히 될 것이고 color difference가 작아야 한다.  이 때 w(p,q)는 color 같은 window pixel을 강조하는 역할을 한다.

무작위 매칭을 시작해야 하는데 초기화도 무작위다. pixel마다 주어진 plane을 초기화 해야하는데 dispairty gradient 값 상에서 초기화 하면 너무 변화하가 크기 때문에 normal을 아무거나 만들고 이를 disparity plane으로 바꾸는 식으로 초기화했다.  그리곤 무작위로 초기화된 disparity값을 시작으로 탐색을 시작하는 방식이다.  어쩌다 cost가 작게 나오는 값이 있으면 그 pixel을 기준으로 propagation 한다.

propagation은 3가지 축이 있다. 1) sptial propagation : 같은 이미지 내 같은 이미지 내에서 인접한 애들은 비슷한 disparity plane을 가질 것이란 가정 하에, 주변 pixel의 plane으로 계산했을 때 cost가 더 작으면 대체한다.  2) view propagation : 다른 이미지 간 현 pixel의 correspondence를 현 plane으로 계산한 뒤, warped pixel의 plane으로 계산한 cost가 더 작으면 대체한다. 3) tempoarl propagation : (있다면) 다른 시간 간 비디오일 경우, 현 pixel의 plane과 다음 시점의 같은 pixel plane을 비교한다. 마지막으로 plane refinement는 1) 2) 3)을 마친 후 채워진 값에 일종의 pertubation을 주는 것이다. 찾아진 값에 특정 범위 안의 noise를 일부러 더해서 cost 계산하는 것을 반복하다가 cost가 더 작은 경우가 발견되면 업데이트한다.

후처리 단계는 cross-check다. left, right 이미지의 모든 픽셀에 모두 plane을 할당한 이유가 이 cross check 때문인데 correspondence 간의 disparity 차이가 1이상일 경우 버린다.  그리고 주변에 disparity 1 이하로 잘 찾아진 valid correspondence의 값으로 재계산해서 다시 채우는 식이다. (이 때 left plane, right plane 2개를 갖고 계산할 수 있으므로 값이 2개가 나오는데 더 작은 값을 썼다. 이유는 invalid는 보통 먼 거리 배경에서 나오므로 작은 disparity이 맞을 확률이 높다는 전제) 마지막으로 값을 다시 채운 이후 weighted media filter를 적용하는데 weighted filter는 수식(4)와 같다.

약간 post processing 한 번 더 하는 느낌인데, 현재 disparity 값 -0.5~+0.5 에서 cost를 만들어 volume 하고 이를 최소화하도록 solver에 넣어 한 번 더 풀어주는 것이다. 이부분은 그냥 점프하는게 좋을 듯. 아이디어만 이해하면 충분.