以Flooding 方法改善Graph-Cut 演算法之影像切割效率研究

Flooding-Based Approach for Image Segmentation to Improve the Performance of Graph-Cut

洪若倫(Jo-Lun Hung)

指導教授 ： 虞台文

大同大學/電機資訊學院/資訊工程學系所/碩士(2011年)

摘要

隨著電腦運算能力不斷躍升，影像切割也成為近年來熱門的研究項目。其中以
Graph-Cut 為主影像切割演算法更是不斷被人拿來討論研究。Graph-Cut 演算法係以
max-flow/min-cut 原理作為影像切割手段。要言之，使用Graph-Cut 演算法進行影像
切割時，使用者先自由選取一部分前景和背景作為種子，藉以建構一網路流量圖模
型的權重，利用進而max-flow/min-cut 原理將整張影像前景和背景切割出來。傳統
的Graph-Cut 演算法係以像素（pixels）作為流量圖之節點（vertices）。當原始影像
尺寸過大時，傳統方法將造成整體運算時間過於冗長。本論文使用Flooding Fill 演
算法對整張影像進行注水，以結合鄰近顏色相近的像素成一個節點，再對此節點較
少之流量圖進行Graph-Cut，以大幅降低運算時間並兼顧正確結果。此外，在前景
與背景交界處，我們將利用已知的前景和背景顏色，推估出適當 值，以便所切割
出的前景能和新背景自然融合，達成理想的影像合成（image composition）效果。

關鍵字

Graph-Cut ； max-flow/min-cut

並列摘要

Following the rapid growth of computing speed of computers, image segmentation
technique attracts many researches. Graph-Cut algorithm is the most popular method adopted by researchers. It uses the max-flow/min-cut principle as the theoretical base for image segmentation. Roughly speaking, using Graph-Cut algorithm to segment an image, users firstly choose some representative portions of the image as the foreground and background
seeds to build a netflow graph so as to model the kinship between pixels. Accordingly, the max-flow/min-cut principle is applied to segment the image foreground and background appropriately. The traditional Graph-Cut algorithm uses pixels to form the main vertices of the netflow graph. If the image size is too big, it requires tremendous amount of computation
time. To accelerate the segmentation process, Flooding-Fill algorithm is applied to aggregating neighboring prixels of similar colors to mean-color nodes so as to reduce the size of netflow graph. This will save significant amount of computation time and not deteriorate the segmentation quality provided that a suitable interactive mechanism is involved. Besides, to achieve natural combination for image composition, we also estimate
the values for pixels located at the boundaries between foreground and background based on the definite foreground and background pixels.

並列關鍵字

Graph-Cut ； max-flow/min-cut

參考文獻

[1] Y. Boykov and G. Funka-Lea, “Graph Cuts and Efficient N-D Image Segmentation,”

[Online]. Available: http://dx.doi.org/10.1007/s11263-006-7934-5

Aug. 2004. [Online]. Available: http://dx.doi.org/10.1145/1015706.1015720

Available: http://dx.doi.org/10.1145/1186562.1015719

algorithms for energy minimization in vision,” Pattern Analysis and Machine