Image segmentation through the scale-space random walker

This thesis proposes an extension to the Random Walks assisted segmentation algorithm that allows it to operate on a scale-space. Scale-space is a multi-resolution signal analysis method that retains all of the structures in an image through progressive blurring with a Gaussian kernel. The input of the algorithm is setup so that Random Walks will operate on the scale-space, rather than the image itself. The result is that the finer scales retain the detail in the image and the coarser scales filter out the noise. This augmented algorithm is referred to as "Scale-Space Random Walks" (SSRW) and it is shown in both artifical and natural images to be superior to Random Walks when an image has been corrupted by noise. It is also shown that SSRW can impove the segmentation when texture, such as the artifical edges created by JPEG compression, has made the segmentation boundary less accurate. This thesis also presents a practical application of the SSRW in an assisted rotoscoping tool. The tool is implemented as a plugin for a popular commerical compositing application that leverages the power of a Graphics Processing Unit (GPU) to improve the algorithm's performance so that it is near-realtime. Issues such as memory handling, user input and performing vector-matrix algebra are addressed.