Fast approximate Random Walker segmentation using eigenvector precomputation

Interactive segmentation is often performed on images that have been stored on disk (e.g., a medical image server) for some time prior to user interaction. We propose to use this time to perform an offline precomputation of the segmentation prior to user interaction that significantly decreases the amount of user time necessary to produce a segmentation. Knowing how to effectively precompute the segmentation prior to user interaction is difficult, since a user may choose to guide the segmentation algorithm to segment any object (or multiple objects) in the image. Consequently, precomputation performed prior to user interaction must be performed without any knowledge of the user interaction. Specifically, we show that one may precompute several eigenvectors of the weighted Laplacian matrix of a graph and use this information to produce a linear-time approximation of the Random Walker segmentation algorithm, even without knowing where the foreground/background seeds will be placed. Finally, we also show that this procedure may be interpreted as a seeded (interactive) Normalized Cuts algorithm.