Shortest Path Based Interactive Image Segmentation
We developed a method for user assisted segmentation of objects of interest, which combines point-based soft constraint on object boundary and stroke-based regional constraint. The user points act as attraction points and are treated as soft constraints, rather than hard constraints that the segmented boundary has to pass through the user specified control points. User can also use strokes to specify region of interest. The probabilities of region of interest for each pixel are then calculated and their discontinuity is used to indicate object boundary. This combined approach is formulated as an energy minimization problem on a multilayered graph, which is solved using a shortest path search algorithm. The proposed approach allows efficient and effective interactive segmentation, which can be used in open or closed curves to segment a variety of images in different ways.
Our method involves the user selecting a series of user control points on the image. These represent the start and the end point for the segmentation, and the user selected points act as the attraction points in the shortest path search which results in the segmentation. These user selected points act in a fashion similar to an elastic band, pulling the segmentation towards them. An energy functional is then formulated based on the combination of the attraction force that is computed using distance transform and the discontinuity in foreground probability. By assuming the user points are in a sequential order, we construct a multilayer graph with each layer encapsulating a single individual user point. The segmentation problem is then transformed into searching the shortest path in this layered graph.
Segmentation process
 |
| (Left) initial image, (Middle) super-pixel segmentation, and (Right) binary representation of graph nodes. |
Layered Graph Construction
 |  |
| (a) | (b) |
(a) Multilayer graph construction (the n+1 layers corresponds to the number of user points), and (b) the final segmentation result.
Example results - wide lives and natural scenes
 |
| (From left to right) Original image, graph cut, seeded star graph cut, grabcut, and the proposed method, where red curve shows the segmentation results, blue, green, and yellow curves represent the background strokes, foreground strokes, and star point and the initial window of the grabcut, respectively. |
Example results - complex scenes
 |
| (From left to right) Original image, graph cut, seeded star graph cut, grabcut, and the proposed method, where red curve shows the segmentation results, blue, green, and yellow curves represent the background strokes, foreground strokes, and star point and the initial window of the grabcut, respectively. |
Publications
- J.-L. Jones, X. Xie, and E. Essa, Image Segmentation using Combined User Interactions, In Proceedings of the Computational Visual Media Conference, September 2013.
- J.-L. Jones, E. Essa, X. Xie and J. Cotton, Interactive segmentation of lumen border in OCT, In Proceedings of International Conference on Computational and Mathematical Biomedical Engineering, December 2013.