A relaxed and efficient approach to interactive segmentation of multiple objects using graph cut

Abstract

Image segmentation can be defined by the process of identify and isolate relevant objects in an image. This process can be interactive or automatic and consists on determinate the approximate location of the object of interest (recognition) and delineate precisely which pixels belong to this object (delineation). Delineation techniques by graph cut represents the state of art of interactive segmentation. In this case, the recognition can be easily solved by internal and external markers selected by the user. However, most of the techniques are constrained to binary segmentation (foreground and background) and the graph cut optimization usually produces borders that are not smooth, below the user expectation. The goal of this project is to investigate and propose a solution that relaxes the restriction of the graph cut optimality in order to obtain smoother borders and closer to the user expectation. In this sense, the proposed method must be proved to be more accurate. Depending on the energy functional parameter of the cut to be minimized, the most suitable delineation implementation can be the obtained by the Image Foresting Transform (IFT) or by the maximum flow algorithm. The second algorithm usually generate smoother borders; however, it is less efficient and restricted to binary segmentation. The IFT algorithm can be executed in linear time to the number of pixels in the image and independently to the number of objects. It is possible to obtain smoother borders with the relaxed IFT algorithm; however, this algorithm do not guarantee connectivity between the IFT roots (markers) and the pixels labeled by them. This dissertation contemplates a solution to this problem, which becomes critical when adopting the differential IFT algorithm to correct segmentation errors in sub linear time (interactive). The results will be evaluated with natural and medical images. To avoid problems with multiple users, the validation will be based on robots that simulates experienced and inexperienced users. (AU)