Graph-Based Image Segmentation with Shape Priors and Band Constraints

In this work, we describe an efficient algorithm, with proof of correctness, for finding an optimal binary segmentation of an image such that the indicated object satisfies a novel high-level prior, called the Band constraint (B), which is the extension of a recent shape prior, called Local Band constraint (LB), to its limiting case with radius tending to infinity. Unlike the LB constraint, the new algorithm can be applied directly to the original image graph saving memory. In our theoretical investigations, we discuss the theoretical relationship of the new B constraint with the Boundary Band (BB) constraint, formerly known as Geodesic Band constraint. Finally, we experimentally conduct a template rotation invariance study of the B constraint within the Oriented Image Foresting Transform framework in region adjacency graphs, when applied to natural images with templates by Gielis geometric equation.