Directed Acyclic Subgraphs Model for Fast Labeling of Markov Random Fields

Abstract

Discrete labeling is a technique to obtain information by assigning discrete values to each pixel in an image. By defining a meaning of discrete values, it can be applied to various computer vision and image processing fields. The basic graphical model to solve the discrete labeling problem is the Markov random fields (MRF) model, which is a graphical model to represent images easily and efficiently. The MRF model exploits the fact that labels of neighboring pixels are similar to each other. Previous MRF-based algorithms use iterative schemes which achieve high accuracy, but take too long to converge on the optimal solution.

In this dissertation, I propose a new graphical model to overcome the demerit of the MRF model.

I propose a directed acyclic graphical model that which is a very efficient structure for solving MRF labeling problems. Using four directed acyclic subgraphs (DAS), MRF labeling results can be estimated quickly with just four scans in an image. Compared to previous message-passing methods on undirected cyclic graphs, message receiving on the DAS graphical model can gather more pixel information in the same amount of time. Because the proposed algorithm can share information from all parts of an image with four scans, it achieves similar or higher accuracy compared to iterative algorithms despite short runtime. I show the wide usefulness of the proposed algorithm by applying it to several computer vision and image processing problems.

Also, I analyze how the DAS algorithm delivers messages more efficiently than previous message-passing algorithm in three aspects (graphical model, inference, and algorithm process). I address the merits of the DAS graphical model by comparing it with the undirected cyclic MRF graphical model. Based on each graphical model, I show differences between message receiving of the DAS model and message passing of the MRF model. The four scans of the DAS model are compared to the iterative algorithm of the MRF model. By comparing results from the DAS algorithm and iterative algorithms, I show that four scans is sufficient to gather information from all parts of an image.

Lastly, I propose an uncertainty measure to evaluate the uncertainty of each pixel of an image using proposed DAS algorithm. Algorithms that use subgraph structure can exploit subgraph consistency, which evaluates the uncertainty of each pixel by comparing the estimated label results of each subgraph. Because the DAS algorithm uses four subgraphs, it can measure the uncertainty of each pixel by comparing subgraph results after four scans without any learning scheme. To use the proposed uncertainty measure effectively, I also propose a new MRF model that includes an uncertainty term. By applying the proposed MRF model and uncertainty measure to several computer vision algorithms, I show that proposed algorithm achieves fast and accurate MRF labeling results.

영상 라벨링은 영상의 각 픽셀에 이산 값을 라벨링하여 영상에서 의미 있는 정보나 값을 얻어내는 기술을 말한다. 영상에 어떤 의미로 이산 값을 정하느냐에 따라 여러 가지 알고리즘에 적용할 수 있기 때문에 다양한 컴퓨터 비전 및 영상처리 문제를 푸는데 많이 사용된다. 영상 라벨링을 하기 위해서 기본적으로 사용되는 그래프 모델이 마르코브 랜덤 필드(Markov Random Fields; MRF) 모델이다. MRF 모델은 인접한 영상 픽셀간의 라벨 값이 유사하다는 사전 정보를 바탕으로 영상 라벨링을 할 수 있도록 하는데, 기존의 MRF 모델을 사용하는 알고리즘들은 반복 계산 방법을 통하여 정확한 라벨링을 목표로 하고 있다. 반복 계산 방법을 통하여 MRF 라벨링을 하게 되면 정확한 라벨링이 가능하지만 계산 복잡도가 높아지는 단점이 있다.

본 논문에서는 이러한 MRF 모델의 단점을 개선하기 위하여 새로운 그래프 모델을 제안한다. 기존의 비방향성 순환형 그래프 모델인 MRF 모델과는 다르게 방향성 비순환형 그래프 모델을 제안하여 더 효율적으로 MRF 라벨링 문제를 풀 수 있는 방법을 제안한다. 4개의 방향성 비순환형 서브그래프(Directed Acyclic Subgraphs; DAS)를 이용하여 반복 계산방법이 아닌 4번의 스캐닝을 통하여 빠르게 MRF 라벨링을 할 수 있다. 기존의 비방향성 순환형 MRF 모델에서의 메세지 전달 방식과는 다르게 본 논문에서 제안하는 그래프 모델에서의 메세지 전달 방식은 동 시간 내에 더 많은 픽셀 정보를 이용할 수 있게 만들어 준다. 이런 메세지 전달 방식을 바탕으로 4번의 스캐닝으로도 모든 픽셀의 정보를 공유할 수 있는 고효율 알고리즘을 구성할 수 있다. 4번의 스캐닝으로도 모든 픽셀 정보를 공유하기 때문에 동작 시간이 짧음에도 불구하고 기존의 알고리즘과 유사하거나 보다 높은 정확도를 보여준다. 다양한 컴퓨터 비전 및 영상처리 문제에 적용함으로써 제안하는 알고리즘이 여러 가지 분야에 적용될 수 있다는 것을 보여준다.

또한 기존의 메세지 전달 알고리즘과의 연관성을 통하여 DAS 알고리즘이 기존의 메세지 전달 알고리즘보다 어떻게 효과적으로 메세지를 전달하는지 3가지 측면(그래프 모델, 메세지 전달 방법, 알고리즘)으로 비교, 분석한다. 비방향성 순환형 MRF 그래프 모델과 방향성 비순환형 DAS 그래프 모델의 비교를 통하여 DAS 그래프 모델이 가지는 장점에 대해서 서술한다. 각 그래프 모델을 바탕으로 MRF 모델의 메세지 전달 방법과 DAS 모델의 메세지 전달 방법이 어떻게 다른지 비교한다. 각 그래프 모델의 메세지 전달 방법을 바탕으로 MRF 모델의 반복계산 방법과 DAS 모델의 4 스캐닝 방법의 차이점을 서술한다. 이를 바탕으로 반복 알고리즘의 라벨링 결과와 DAS 알고리즘의 라벨링 결과를 비교하여, 4번의 스캐닝만으로도 반복 알고리즘의 효과를 얻어낼 수 있다는 것을 보여준다.

마지막으로, 제안한 DAS 알고리즘을 이용하여 MRF 라벨링 결과의 불확실성 정도를 계산하는 측정도구로써의 방법을 제안한다. 서브그래프를 사용하는 알고리즘은 서브그래프간 결과를 비교하여 해당 픽셀의 불확실성을 측정하는 서브그래프 일치 방법을 사용할 수 있다. 4개의 서브그래프를 사용하는 DAS 알고리즘은 4번의 스캐닝 이후 각 서브그래프 결과를 비교함으로써 비학습적 방법으로 빠르게 각 픽셀의 불확실성을 측정할 수 있다. 제안하는 불확실성 측정값을 이용하여 더 정확한 라벨을 추정 할 수 있는 새로운 MRF 모델을 제안하여 반복 알고리즘보다 비교적 단시간에 정확한 라벨링이 가능하도록 하였다. 제안한 MRF 모델과 불확실성 측정값을 여러 가지 컴퓨터 비전 응용 알고리즘에 적용하여 빠르지만 정확한 MRF 라벨링 결과를 구할 수 있다는 것을 보여준다.