LooseCut: Interactive Image Segmentation with Loosely Bounded Boxes

abstract

이미지에 있는 관심있는 object를 interactive하게 segment하는 기본적으로 사용되는 방법은 객체를 포함하는 상자를 만들고 binary labeling을 지정하는 것입니다. 하지만 이러한 interactive하게 이미지 segment하는 기존 알고리즘은 객체에 밀착해서 객체를 포함하는 상자를 만드는 방법을 선호합니다. 이러한 방법은 객체를 포함하는 상자를 만드는것에 대해서 부담을 주고, 다른 object detecting 알고리즘으로 검출한 boundery box를 사용하는 것에 대해서 제한사항을 주게됩니다. 본 논문에서는 boundery box가 느슨하게 잡히더라도 object segment를 잘할 수 있는 새로운 LooseCut 알고리즘을 제안합니다. 우리는 느슨한 박스를 사용함에도 불구하고 잘 segmentation을 하게만들기 위해서 유사한 모양의 화소와 배경을 더 잘 구분하기 위해 추가 에너지 term을 포함하는 추가적인 에너지 조건을 포함한 Markov Random Fields(MRF)를 제안합니다. 이 MRF모델은 반복된 max-flow알고리즘에 의해서 최적화됩니다. 우리는 3가지의 공개된 데이터 셋에서 label box상자 크기를 증가시킬 때, 다른 알고리즘들과 LooseCut 알고리즘을 비교해서 평가합니다.

1. Introduction

이미지에서 관심있는 Object를 사람과의 상호작용을 통해서 편리하고 정확하게 segment하는것은 image/video 편집 및 detection/tracking에서 핵 심적인 역활을 합니다. 넓게 사용되는 상호방법에는 해당 객체를 포함하는boundery box로 주석을 달아주는 것입니다. 한편으로는 이러한 bounding box의 입력은 object의 공간정보를 제공해줍니다. 다른 한편으로는 이 bounding box를 통해서 전경과 배경에 대해서 모델에 초기화 정보를 줄 수 있으며, 이를 통해 전경과 배경을 세밀하게 구분할 수 있습니다.  하지만 Object의 경계와 Object 픽셀 표현의 복잡함으로 인해서 존재하는 수많은 알고리즘들은 bounding box를 object와 굉장히 밀착해서 치는 것을 요구합니다. 예를들면 Fig1에서 볼 수 있듯이 GrabCut알고리즘은 bounding box를 object에게 밀착해서 치지 않으면 segment 작업이 실패하게 됩니다. 이렇게 Object에 bounding box를 밀착해서 치는 방법은 사용자들에게 많은 부담을 줄 뿐만 아니라 다른 Object Detecting 알고리즘을 통해서 나온 Bounding Box를 사용하는데도 제약을 줍니다. 따라서 이러한 타이트한 Bounding box는 메리트가 없습니다.

현재 존재하는 알고리즘들은 bounding box를 느슨하게 치게될 경우에 대부분 Segmentation이 실패하게되는데, 이런 실패의 주 이유는 이러한 경우에서의 전경에 대한 추정모델이 부정확하기 때문입니다. 존재하는 많은 알고리즘들은 반복적인 절차를 통해서 segmentation을 가다듬게됩니다. 만약 bounding box가 느슨하게 쳐지게 되면, 초기에 추정된 전경에 대한 모델이 부정확하고 Global Minima에 도달하기 전에 Local Minima에 수렴하게되는 경향이 있습니다. 우리는 기존의 GrabCut을 토대로 새로운 LooseCut 알고리즘을 개발했습니다. LooseCut알고리즘은 느슨한 Bounding box에도 더 나은 전경분리 성능을 보여줍니다. 특별하게도 LooseCut은 느슨한 Bounding Box에도 강건한 Segmentation 성능을 갖기 위해서 두가지 전략을 제안합니다. 첫째 우리는 인접하지 않은 유사 픽셀에 대해서 일관된 라벨 표시를 장려하기 위해서 GrabCut의 energy function에 라벨 일관성 term을 추가하는 것을 제안합니다. 두번째로 우리는 전경 모델과 배경 모델간의 차이를 명시적으로 강조하기 위해서 반복적인 절차에서 전역적인 유사성을 강조하도록 강제하는 것을 제안합니다. 추가적인 에너지항과 제약 조건을 고려해서 우리는 image segmentation을 위한 반복적인 max-flow 알고리즘을 개발했습니다. 실험에서는 우리는 느슨한 bounding box를 사용해서 다른 현존하는 알고리즘과 LooseCut알고리즘을 비교 평가했습니다.

2. 제안된 접근법

2-1. GrabCut

GrabCut은 MRF 모델을 사용하여 각각의 픽셀에 이진 labeling을 수행합니다.   을 각 픽셀 의 이진 label이라고 합시다. 는 전경이고 은 배경입니다. 는 전경의 Gaussian Mixture Model(GMM)  과 배경의 Gaussian Mixture Model(GMM) 을 포함한 GrabCut의 표현 모델입니다. GrabCut은 다음의 수식을 최소화하는 최적값을 찾게됩니다.

는 픽셀의 neighboring system입니다. 예를들어 4 또는 8의 인접에 대한 연결을 의미합니다. 단항식  는 표현 모델  에 기반한 레이블링된 전경과 배경 pixel 에 대한 비용을 의미합니다. 다항식 는 서로 다른 label을 가진 이웃 픽셀 간의 불연속성에 대해서 패널티를 줌으로써 label을 부드럽게 만들어주는 것을 가능하게합니다. Max-Flow 알고리즘은 일반적으로 MRF를 최적화하는데 쓰이는 최적화알고리즘입니다. GrabCut은 입력 bounding box를 가지고 다음의 수행을 통해서 이진 이미지 segmentation을 달성합니다. (step 1). 초기 표현 모델  를 각각의 bounding box의 내부와 외부 pixel을 이용하여 초기 추정합니다. (step 2) 현재 표현모델 를 기반으로 각 픽셀의 전경 및 배경의 likelihood를 양자화하고, 이것을 단항식 D를 정의하는데 사용합니다. 식 1을 최소화하는 최적의 labeling을 구합니다. (step 3) 얻은 labeling 를 기반으로 모델 를 업데이트하고 다시 (step2)로 돌아갑니다. 해당 step을 수렴할 때까지 반복합니다.

2-2. MRF Model for LooseCut

GrabCut에서 사용된 MRF 모델을 따르면 제안된 LooseCut은 다음과 같은 MRF 에너지 함수를 취할 수 있습니다.

는 식1에서 주어진 GrabCut의 에너지 함수입니다. 그리고 는 label 일관성을 장려하기 위한 에너지 항입니다. 여기서 조건을 따릅니다. 우리는 를 더 잘 추정하고 전경과 배경을 잘 구별하기 위해 전역 유사성 제약 조건을 적용해서 식2를 최소화합니다. 다음 섹션에서 레이블 일관성 term인 와 전역 유사성 제약 조건에 대해서 더 자세히 설명할 것입니다.

2-3. Label Consistency Term 

인접하거나 인접하지 않은 유사 표현 pixel의 label 일관성을 장려하기 위해서 특징 및 공간 일관성을 유지하는 슈퍼픽셀 알고리즘을 사용하여 모든 이미지 픽셀을 클러스터링합니다. K-means 스타일 절차에 따르는 이 클러스터링 알고리즘은 이미지를 작은 픽셀 세트로 분할하고, 각 결과 클러스터는 하나 이상의 슈퍼 픽셀로 구성됩니다. 

는 클러스터 를 의미합니다. 그리고 픽셀은 속해서 같은 label을 할당받게됩니다. 슈퍼픽셀 알고리즘을 달성시키기 위해서 우리는 0과 1 값을 갖는 클러스터 label를 설정하며, 레이블 일관성 에너지 항을 다음과 같이 정의합니다.

는 True 혹은 False 인자에 대해서 1또는 0을 취하는 표시함수입니다. 제안된 알고리즘에서 우리는 pixel label과 cluster label을 MRF optimization을 통해서 동시에 해결할 수 있습니다.

2-4. Global Similarity Constraint

이번 섹션에서 우리는 제안된 global similarity constraint에 대해서 정의합니다.  는  를 의미하는 Gaussian Components  를 갖습니다.  는 를 의미하는 Gaussian Components 를 갖습니다. 전경 GMM 의 각 Gaussian component 에 대해 먼저 에서 가장 가까운 Gaussian component를 다음과 같이 찾습니다.

이를 통해 Gaussian component 와 전체 배경 GMM 사이의 유사성을 정의 할 수  있습니다.

이는 배경 GMM에서 와 가장 가까운 가우스 성분 간의 평균 차이의 역수입니다. 그런 다음에 Global Similarity function  을 정의합니다.

GMM 거리에 대한 비슷한 정의는 이전 연구에서 발견 할 수 있습니다. 다음 절에서 논의 될 MRF Optimization에서 를 추정하는 단계에서 Global Similarity 가 임계값보다 작도록 적용할 것입니다.

2.5 Optimization

이번 섹션에서는 식2에 정의된 Global Similarity constraint가 적용된 에너지 함수를 최적화하는 최적의 binary label을 찾는 알고리즘을 제안합니다. 특히 각 반복에서 우리는 label X를 고정시키고 에 Global Similarity Constrain를 적용하여 를 최적화합니다. 그 후에 를 고정하고 최적의 를 를 최솨화하는 방법으로 찾습니다. 이러한 두가지의 최적화 단계는 수렴 또는 사전 설정된 최대 반복 횟수에 도달할 때까지 번갈아서 반복됩니다. 초기화는 반복작업에서 binary labeling X를 정의하기 위해서 입력 bounding box를 사용합니다. (inside box = label 1, outside box = label 0). 이에 따라 우리는 이 두가지 최적화 단계에 대해서 자세히 설명합니다.

2.5.1 Fixing  and Optimizing Over 

고정된 binary labeling X를 사용하면 우리는 를 표준 EM기반 클러스터링 알고리즘을 사용해서 추정할 수 있습니다.  label을 1로 갖는 모든 픽셀은 전경 GMM 를 계산하기 위해 사용되며, label을 0으로 갖는 모든 픽셀은 배경 GMM 를 계산하는데 사용됩니다. 우리는 의도적으로  

이 되도록 와를 선택합니다. 왜냐면 일부 배경 구성 요소는 느슨하게 설정된 bounding box에 의해 정의된 초기 X는 전경이 혼합되어있기 때문입니다. 얻은 와 에 대해서 Global Similarity constraint가 만족되는지 검사합니다. 즉, 인지 검사합니다. 이 제약 조건이 충족되면 결과 를 취해 다음 최적화 단계로 진행합니다. 이 제약 조건을 만족하지 못하면 다음 알고리즘을 사용하여 를 더 세분화합니다.

1. 식 5에 따른 각 Gaussian Component , 사이의 유사성을 계산합니다. 그리고 와 가장 유사한 의 K개의 Gaussian Components를 식별합니다.

2. 이러한 K 성분들 중, 성분이 를 만족하지 않으면 해당 성분을에서 삭제합니다.

3. 모든 삭제가 끝나면 나머지 Gaussian 구성 요소를 사용하여 업데이트 된 를 생성합니다.

이 알고리즘은 업데이트 된 및 가 Global Similarity constraint 조건을 충족시키는지 확인합니다.

2.5.2 Fixing  and Optimizing over 

우리는 에너지 함수 를 최소화하는 최적의 를 찾기 위해서 보조 노드가 있는 방향이 없는 그래프를 만듭니다. 각 픽셀 클러스터 를 표현하기 위해서 보조 노드 를 구성합니다. 엣지는 보조 노드 와 의 픽셀을 나타내는 노드를 식5. 에서 사용되는 에지 가중치  와 연결하도록 구성됩니다. 이러한 그래프의 예시가 Fig4. 에 있습니다. 여기서 핑크노드 ,는 동일한 클러스터에서 보조 노드 에 의해서 표현되는 3개의 픽셀을 나타냅니다. 파란색의 모든 노드는 다른 클러스터를 나타냅니다. 고정된 로 이 그래프에서 max-flow 알고리즘을 사용하여를 최소화하는 최적의를 찾습니다.

Fig 4. 와 같이 구성된 그래프는 OneCut에서 생성된 그래프와 유사합니다. 그러나 제안된 알고리즘과 OneCut 사이에는 두 가지 주요한 차이점이 있습니다. 

1. OneCut에서는 먼저 입력 이미지에 대해 색 히스토그램이 구성되고 각 히스토그램 빈에 대해 하나의 보조 노드가 구성됩니다. 그런 다음 모든 픽셀이 이러한 저장소로 양자화되고 각 저장소의 픽셀이 해당 보조 노드에 연결됩니다. 본 논문에서는 슈퍼 픽셀 기반 클러스터를 사용하여 보조 노드를 정의합니다.

2. OneCut의 단항 에너지 항은 제안 된 방법의 단항 에너지 항과 다르며 결과적으로 OneCut과는 다른 소스 및 싱크 노드를 포함하는 에지 가중치를 정의합니다. OneCut은 ballooning 기법을 따릅니다. S는 bounding box 내부의 모든 피겟ㄹ과 경계 사이의 가장자리에 대해 1로 설정되고, 그렇지 않으면 0으로 설정됩니다. 마찬가지로, 가중치는 T와 테두리 상자의 모든 픽셀 사이의 가장자리에 대해 0으로 설정되고, 그렇지 않으면 무한대로 설정됩니다. 제안된 알고리즘에서 S또는 T로부터 입사하는 에지의 가중치는 모델 에 기반한 식1. 의 단항 항을 반영합니다.

두가지 차이점을 고려하여 oneCut은 전경과 배경간의 L1 거리 기반 히스토그램 겹침을 최소화하려고합니다. 이는 제안된 알고리즘의 목표와 다릅니다. 이 그래프 구조를 사용하여 동일한 클러스터에서 픽셀의 레이블 일관성을 향상시키는 방법을 찾습니다. 우리는 후자의 실험에서 OneCut과 비교할 것입니다. 전체 LooseCut 알고리즘은 알고리즘1에 요약되어있습니다.