1. A region segmentation apparatus that divides an image into an object region and a region other than the object region, the apparatus comprising: a candidate region setting unit that sets a candidate region for the object region in the image; and a region segmentation unit that sets a cost for each of an S link, a T link and an N link in a graph including a point S corresponding the object region, a point T corresponding to the region other than the object region, a point corresponding to each of pixels in the image, the S link connecting a point corresponding to each of the pixels and the point S to each other, the T link connecting a point corresponding to each of the pixels and the point T to each other, and the N link connecting two points corresponding to each pair of adjacent pixels to each other, and performs a graph cut that minimizes the sum of costs set for links to be cut, and judges whether a point corresponding to one of the pixels connected to the point S by a link is present in the graph after performance of graph cut, and if no point is present, performs the graph cut at each stage while costs set for all the S links connecting points corresponding to pixels in the candidate region set by the candidate region setting unit and the point S to each other are increased stepwise in an increment of less than or equal to a predetermined threshold until a point corresponding to one of the pixels connected to the point S by a link appears, and determines whether each of the pixels in the image belongs to the object region or the region other than the object region based on a result of a graph cut performed last.