Skip to content

Paper 40: Graph-Based Image Segmentation with Shape Priors and Band Constraints

Abstract

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.

My Review

Summary

The paper introduces a concept called Band Constraint and it shows how it can be applied as a shape prior in binary image segmentation. Relationships with similar constraints are described and some theoretical results are presented. In particular, Proposition 2 and Theorem 1 forms the theorical basis of Algorithm 1. Algorithm 1 finds an optimal segmentation among the hard-constraint imposed by a star-convex shape template. Finally, few examples of segmentation of leaf objects are shown.

Relevance to DGMM

The paper introduces a constraint to be used in the context of binary segmentation via optimization of paths in a weighted digraph. Therefore, it fits the topic Image Segmentation and Discrete Shape Analysis.

General comments

  • It would help to illustrate the segmentation of the leafs if figures illustrating the results with different values of \Delta could be shown. Even better would be to make the code publicly accessible or at least to make it public a collection of segmentation results returned by the algorithm.
  • In the conclusion section is described how you handle the translation and rotation of the shape template. But it seems to me that the proper scale parameters of the Gielis function (A,B) must be discovered somehow. So I am assuming that you expect that proper scaling parameters are given by the user?
  • It seems to me that the upper-bound of Proposition 1 could be tighter.

Given the assumptions:

(A1) Let t in O (A2) C(t) < C(s) + \Delta for all t in O and s in N/O s.t ||s-t|| <= R+r (A3) r = max ||s-t|| (A4) Let u in bd(O) s.t ||t-u|| <= R

There exists a s in N/O s.t. (u,s) in A(u). Therefore, by applying (A3) on the pair (t,s) and (A4) on the pair (t,u) we obtain

||s-u|| <= ||s-t|| + ||t-u|| <= r+R

Thus, the pair (u,s) also respects condition (A2), because u in bd(O) implies that u in O.

We also have that

C(t) - C(u) <= |C(t)-C(s)| + |C(s)-C(u)|

Applying (A2) for the pairs (t,s) and (u,s) we obtain

Ct() - C(u) <= \Delta + \Delta

Notes

  • What is Oriented Image Foresting Transform?
  • Boundary Band Constraint
  • Local Boundary Constraint
  • I didn't read proposition 2 carefully