Superpixel Lattices
[cite]10.1109/CVPR.2008.4587471[/cite]
1. Introduction
컴퓨터 비전의 한 목표로 주어진 이미지의 의미, 상황을 알아내고자 하는 이미지 파싱(Image parsing)이 있다. 이것은 단순히 색이나 인텐서티값을 보는 것만으로는 쉽지 않은 문제인 것이, 파란색이라고 해도 하늘의 그것인지 바다인지, 아니면 파란색 자동차의 부분인지 알 길이 전혀 없는 것이다. 위치상 위에 있다면 아마도 하늘일 가능성이 많겠지만 말이다.
이러한 문제를 다루는 방법으로 Markov Random Field (MRF)나 Conditional Random Field (CRF) 모델에다 컨텍스트 정보를 넣어 사용되곤 하는데, 이것들이 여전히 빠른 방법은 아니라는 것이다. 특히 이미지의 한 픽셀을 한 노드로 처리하는 방식이 덕택에 이미지 크기에 따라 계산량이 결정되는데, 하나의 오브젝트임에도 불구하고 비슷한 색의 픽셀들을 모두 처리해야하기 때문에 이것 또한 중복으로 계산하는 셈이 된다. 멀티 스케일을 이용한 방법으로 이를 해결하려는 시도도 있지만, 여기서 알아볼 방법은 Ren and Malik에 의해 시도된 Superpixel을 도입을 통한 해결이다.
그전까지 제안되었던 Superpixel 방법은 본래 이미지가 갖던 격자형 Grid 형식을 유지하지 못하는 단점이 있었다. 따라서 이미지에서 적용되던 여러 알고리즘을 Superpixel 이후에는 적용하기 어려워져 계산량을 줄이고자 했던 방법이 막상 알고리즘을 적용하기 어려워지는 문제점들을 안고 있었다.
이 논문에서 이를 해결하고자 Grid 형식을 유지하면서도 비슷한 특징들을 가지는 Superpixel들을 생성하여 기존 알고리즘들의 처리 속도를 높이고자 한다.
2. A Greedy Regular Lattice
일단 알고리즘의 입력은 정규화된 boundary map으로 한다. 야간 생소할 수도 있지만, 이것의 가장 단순한 예는 에지맵이라고 할 수 있으며 좀 더 복잡한 정보를 사용하고 싶다면 natural, 혹은 occlusion boundary들의 확률 값들을 사용해도 좋다. 대신 결과물들을 그 값이 가장 큰 녀석(boundary)을 1로, 아닌 부분을 0으로 하여 정규화를 해놓고 이를 boundary cost map이라고 부르자. 이제 이 map에서 cost가 가장 낮은 경로들을 따라 이미지를 자르기 시작할 것이다.
방법은 아주 간단하다. 종이를 반으로 반으로 접듯, 가로로 한번 세로로 한번 나누고, 나눠진 4조각을 또 4개로 나눈다. 이를 원하는 만큼 반복하면 된다.
이미지를 둘로 나누는 방법은 s-t cut을 이용하거나 dynamic programming을 이용하도록 하자. 기존의 두 알고리즘에서 크게 변화된 것이 없으므로 자세한 방법은 논문을 참고하도록 하자.
단, 나누는 과정에서 한가지 제한이 들어가는데, 자르게 되는 극단적으로 치우쳐서 예를들면 대각선으로 잘라버리는 것을 방지하기 위해서, 논문에서 Strip이라 불리는 넘지 못하는 테두리를 정의하여 그 이상 넘어가지 않도록 한다. 이는 한쪽으로 치우치는 것 뿐만 아니라, 이전에 잘랐던 라인과 아주 가까이 겹쳐지는 것도 방지하는 효과가 있다.
2.1. Parameters of Greedy Lattice
이 알고리즘에서 쓰이는 세 가지 파라미터가 있다.
첫번째로, 최종적으로 만들어질 Superpixel 이미지의 해상도. 두번째는 이미지를 자를 때 사용되는 Strip의 크기. 마지막으로 이미지를 자르는 경로의 tortuosity이다.
7. Discussion and Conclusions
가로 세로로 번갈아 가며 자르기 때문에 당연히 결과물은 Grid의 모양새를 가지게 된다. Grid의 성질을 토대로 기존 이미지에서 사용되던 알고리즘을 적용하는데 문제가 없게 된다. 한가지 장점으로 내세우는 것은, 계속적으로 나누는 방법의 특성상 현재 Superpixel 해상도에서 나누기 몇 단계 전의 결과물을 사용하면 멀티스케일의 효과를 얻을 수 있다고 한다.
실제 구현을 해보면 Grid를 유지하기 위해 격자형으로 자른 것이 오히려 단점으로 작용하는 것을 볼 수가 있다.