Random walk is a popular and efficient algorithm for image segmentation, especially for extracting regions of interest (ROIs). 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 also be 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.