Many computer vision problems such as object segmentation or reconstruction can be formulated in terms of labeling a set of pixels or voxels. In certain scenarios, we may know the number of pixels or voxels which can be assigned to a particular label. For instance, in the reconstruction problem, we may know size of the object to be reconstructed. Such label count constraints are extremely powerful and have recently been shown to result in good solutions for many vision problems.
Traditional energy minimization algorithms used in vision cannot handle label count constraints. This paper proposes a novel algorithm for minimizing energy functions under constraints on the number of variables which can be assigned to a particular label. Our algorithm is deterministic in nature and outputs $\epsilon$-approximate solutions for all possible counts of labels. We also develop a variant of the above algorithm which is much faster, produces solutions under almost all label count constraints, and can be applied to all submodular quadratic pseudoboolean functions. We evaluate the algorithm on the two-label (foreground/background) image segmentation problem and compare its performance with the state-of-the-art parametric maximum flow and max-sum diffusion based algorithms. Experimental results show that our method is practical and is able to generate impressive segmentation results in reasonable time.
Object segmentation이나 object reconstruction과 같은 많은 컴퓨터 비전 문제들이 각각의 픽셀에 라벨을 부여하는 것으로 표현될 수 있다. 이와 관련해서 특정 라벨을 갖는 픽셀의 개수를 고정하는 것이 의미있을 수 있다. 예를 들어, reconstruction 문제에서 복원될 물체의 크기에 대한 정보를 어느 정도 알고 있을 때, 이러한 제약을 줌으로써 원하는 결과를 얻는데 도움이 될 수 있다. 또는 복원될 물체의 원하는 규모를 지정하는 것으로 생각할 수도 있다. 이러한 label count 제약은 최근으로 오면서 많은 컴퓨터 비전 문제들에서 좋은 결과를 보여주고 있다.
컴퓨터 비전에서 사용되는 기존의 에너지 최소화 알고리즘들은 label count 제약을 다루지 못하고 있다. 이 논문에서는 각각의 라벨에 대해, 그 라벨을 갖는 변수의 수가 정해진 제약에서 에너지를 최소화 하는 알고리즘을 제안한다. 제안하는 알고리즘은 deterministic이며, 모든 가능한 label count 제약에 대해 $\epsilon$-근사 해를 계산한다. 또한 위의 알고리즘의 변형이며, 훨씬 더 빠른, 그리고 에너지 함수가 submodular pseudoboolean 일때 적용가능한, 거의 대부분의 label count 제약에 대해 해를 계산하는 알고리즘도 제시한다. 우리는 두개의 label을 이용한 (전경/배경) image segmentation problem에 대해 두가지 알고리즘의 성능을 평가하고, 기존의 알고리즘인 parametric maxflow와 max-sum diffusion과도 성능을 비교한다. 이러한 실험을 통해 우리는 제안된 알고리즘이 실제 문제에서 잘 동작하며, 적당한 시간내에 좋은 결과를 낸다는 것을 확인할 수 있다.
