Convex Shape Representation with Binary Labels for Image Segmentation: Models and Fast Algorithms

Shousheng Luo, Xue‐Cheng Tai, Yang Wang

Abstract

We present a novel and effective binary representation for convex shapes. We show the equivalence between the shape convexity and some properties of the associated indicator function. The proposed method has two advantages. Firstly, the representation is based on a simple inequality constraint on the binary function rather than the definition of convex shapes, which allows us to obtain efficient algorithms for various applications with convexity prior. Secondly, this method is independent of the dimension of the concerned shape. In order to show the effectiveness of the proposed representation approach, we incorporate it with a probability based model for object segmentation with convexity prior. Efficient algorithms are given to solve the proposed models using Lagrange multiplier methods and linear approximations. Various experiments are given to show the superiority of the proposed methods.

Introduction

Image segmentation—the process of partitioning an image into meaningful regions—is notoriously difficult when images are noisy, poorly lit, or contain occlusions. To address these challenges, researchers often employ "shape priors," which are mathematical assumptions about the target object's geometry. Convexity is a particularly powerful prior because many real-world objects, such as fruit, biological cells, or organs, are roughly convex.

However, enforcing convexity in computer vision models is computationally expensive. Existing approaches generally fall into two categories: level-set methods, which use curvature constraints but struggle to scale to 3D, and binary representations, which often rely on checking every possible line segment between points—a combinatorial challenge that leads to high computational costs. This paper proposes a representation that is both mathematically simple and computationally efficient.

Proposed Method

The core innovation of this work is a boundary-based characterization of convexity. The authors prove that a shape $D$ is convex if and only if, for any ball $B$ centered on its boundary, the volume of the ball outside the shape is at least half the total volume of the ball.

Illustration of the convexity property: Circle B on a convex boundary segment has at least half its area outside the shape, whereas Circle A on a concave segment does not.

This geometric observation is translated into a binary indicator function $u$ (where $u=0$ inside the object and $u=1$ outside). The convexity constraint is then expressed as a simple convolution inequality: $$u(b * u) \geq 0.5u$$ where $b$ is a radial function, such as a uniform disc.

To perform segmentation, this constraint is incorporated into a Potts model, which balances three components:

  1. Region Force: Alignment of pixel colors with foreground/background probability models (fitted using Mixed Gaussian Distributions).
  2. Boundary Regularization: Ensuring smooth object edges.
  3. Convexity Constraint: Enforcing the new binary rule.

The resulting model is solved using a Lagrange multiplier method combined with an alternating direction method. To maintain high performance, the authors linearize the quadratic constraints and utilize Fast Fourier Transforms (FFT) for efficient convolution handling.

Experimental Evaluation

The method was evaluated on a diverse range of images, including natural images (apples, oranges, tomatoes), medical/scientific images (microscopic cells, CT/MRI scans), and benchmark data from the University of Western Ontario.

Key Insights

  • Local to Global Enforcement: Convexity, typically a global property, is enforced through local checks (convolutions with small balls) along the boundary.
  • Dimension Independence: The logic relies on the volume of a $d$-dimensional ball, making the mathematics identical for 2D photographs and 3D medical volumes.
  • Label Efficiency: Unlike previous state-of-the-art methods requiring dense user "scribbles," this model produces clean convex shapes even with sparse user input.
  • Numerical Stability: A "narrow band" technique updates the binary function only near the estimated boundary, significantly speeding up convergence.

Results

The proposed method demonstrates higher accuracy compared to previous standards (e.g., Gorelick et al., 2017), capturing sharp corners and fine details more effectively where other methods might "smear" boundaries. In experiments with limited labels, the method successfully segmented objects like tomatoes or mushrooms where competing methods failed or produced fragmented results. Furthermore, by reducing the convexity check to convolutions, the algorithm remains computationally efficient and suitable for real-time applications.

Conclusion and Future Work

While effective, the method requires careful selection of the radial function radius ($r$). If $r$ is too large, boundaries may appear aliased; if too small, the algorithm might permit non-convex boundaries with low absolute curvature. Future research will focus on extending this framework to segment multiple overlapping convex objects and conducting full-scale experiments on 3D medical image data.

Summary updated

Abstract

We present a novel and effective binary representation for convex shapes. We show the equivalence between the shape convexity and some properties of the associated indicator function. The proposed method has two advantages. Firstly, the representation is based on a simple inequality constraint on the binary function rather than the definition of convex shapes, which allows us to obtain efficient algorithms for various applications with convexity prior. Secondly, this method is independent of the dimension of the concerned shape. In order to show the effectiveness of the proposed representation approach, we incorporate it with a probability based model for object segmentation with convexity prior. Efficient algorithms are given to solve the proposed models using Lagrange multiplier methods and linear approximations. Various experiments are given to show the superiority of the proposed methods.
BibTeX
@misc{luo2020convex,
  author = {Shousheng Luo and Xue‐Cheng Tai and Yang Wang},
  title = {{Convex Shape Representation with Binary Labels for Image Segmentation: Models and Fast Algorithms}},
  year = {2020},
  eprint = {2002.09600},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.09600},
}
Figure