In this paper, we address the problem of interactive image segmentation which segments an image based on user-supplied scribbles. For this purpose, we propose a novel framework that provides consistent performance robust to the location of input seeds. Most of the existing methods, especially random walk-based approaches, strongly depend on initial seed positions, which differ from one user to another. To overcome this drawback, the proposed algorithm incorporates the seed expansion step, in which robust seed information is secured and improved. We also address the computation issue using a coarse-to-fine random walk technique. We evaluate our algorithm using challenging datasets, such as Grabcut, PASCAL VOC and Alpha matting datasets. Our algorithm produces a more accurate segmentation results than the existing methods.