Interactive Image Segmentation: Algorithms And The System

Image segmentation is one of the most fundamental and important problems in computer vision. Due to the huge gap between computer and human in abilities to understand image contents, recently, user-assisted interactive image segmentation has been extensively studied and widely applied in various fields related to digital image processing. The purpose of interactive image segmentation research is to quickly and accurately extract the foreground object with high-level semantics, through convenient and intuitive human computer interactions. However, with the rapid development of digital technologies, the resolution of images generated by digital imaging devices has increased significantly. Although current state-of-the-art interactive image segmenta-tion systems, which are based on global optimization algorithms, can provide the user with friendly interaction interface, they gradually lose the ability of instantly producing precise feedback for the user. Therefore, the focus of this thesis is to study how to enable the user to obtain instant and accurate segmentation results on high-resolution images through efficient and straightforward interactions. On the one hand, we start from the users'most natural way of interaction and design efficient segmentation al-gorithms to match it; on the other hand, we design parallel optimization algorithms to exploit the power of modern multi-core processors and further improve system response time. The contents and innovations of this thesis is summarized as the following:1. Through careful studies of how users interact in the image segmentation task, we propose a progressive segmentation algorithm, which matches the users'way of interaction and effectively avoids redundant computations; meanwhile, it simpli-fies the optimization problem through local color modeling and accelerates the optimization process. The progressive segmentation algorithm can be seamlessly combined with multi-scale banded graph-cut optimizations to reduce the compu-tational complexities in the banded optimizations. We also propose an adaptive band upsampling scheme, which utilizes the image priors across multiple scales, to further reduce the number of pixels participating in the banded optimizations.2. To accelerate the graph-cut optimization process on multi-core platforms, we propose two parallel maximum flow algorithms based on graph partitioning. By partitioning the graph into several disjoint subgraphs in a dynamic or static man- ner, the parallelization effectively avoids the overhead induced by heavy syn-chronization among threads, so that the multi-core processor can spawn multiple threads to carry out the maximum flow computations within each subgraph in-dependently. Besides interactive image segmentation, these two algorithms can also be widely applied in various computer vision and graphics problems such as stereo vision,3D surface fitting and so on.3. We design a new interactive image segmentation system (Paint Selection), it not only incorporates the above proposed progressive segmentation algorithm, adap-tive band upsampling scheme, multi-core graph-cut optimization, but also con-tains three new interface elements, which are tool interchangeability (allowing users to select any tool in any order to finish the segmentation task), scribble competition (intelligently handling conflicting input from the user) and dynamic local window (improving segmentation accuracy with respect to users'zoom in ratio). Compared with existing interfaces, Paint Selection is more user-friendly and efficient.4. We design a new user interface for image matting (Paint Matting), enabling the user to conveniently and quickly make the transition from binary segmentation to detailed image editing (cut-and-paste, color adjustments, etc.). Paint Matting improves the response speed by a local updating scheme and avoid the UI block-ing by utilizing multi-threading techniques, and thus boosts the user-friendliness and usability of the interface.