A CONTINUOUS RANDOM WALK MODEL WITH EXPLICIT COHERENCE REGULARIZATION FOR IMAGE SEGMENTATION

Abstract

Random walk is a popular and efficient algorithm for image segmentation, especially for extracting regions of interest (ROI). One difficulty with the random walk algorithm is the requirement for solving a huge sparse linear system when applied to large images. Another limitation is its sensitivity to seeds distribution, i.e. the segmentation result depends on the number of seeds as well as their placement, which puts a burden on users. In this paper, we first propose a continuous random walk model with explicit coherence regularization (CRWCR) for the extracted ROI, which helps to reduce the seeds sensitivity, so as to reduce the user interactions. Then, a very efficient algorithm to solve the CRWCR model will be developed, which helps to remove the difficulty of solving huge linear systems. Our algorithm consists of two stages: initialization by performing one dimensional random walk sweeping based on user-provided seeds, followed by the alternating direction scheme, i.e. Peaceman-Rachford scheme for further correction. The first stage aims to provide a good initial guess for the ROI, and it is very fast since we just solve a limited number of one dimensional random walk problems. Then this initial guess is evolved to the ideal solution by applying the second stage, which should be also very efficient since it fits well for GPU computing and 10 iterations are usually sufficient for convergence. Numerical experiments are provided to validate the proposed model as well as the efficiency of the two-stage algorithm.

Existing System

Preconditioned conjugate gradient (PCG), incomplete Cholesky Factorization (ICF)

Proposed System

A continuous model is formulated for the random walk algorithm, which approximates well the discrete energy defined for the RW model when working on images. This continuous formulation leads to a fast solver for RW based segmentation problems. A constraint term that explicitly measures the intensity coherence of the extracted ROI is introduced and integrated into the continuous RW model, which helps to reduce seeds sensitivity, so as user interactions. An efficient algorithm to solve the continuous model is proposed, which aims to remove the difficulty with solving huge linear systems when applying random walk based algorithms.

Architecture

BLOCK DIAGRAM