Incorporating Topological Constraints within Interactive Segmentation and Contour Completion via Discrete Calculus

Jia Xu       Maxwell D. Collins       Vikas Singh

University of Wisconsin-Madison

196062_orig.jpg 196062_contour_seed_Jia.jpg 196062_result_euler_only_boundary
41006_orig.jpg 41006_contour_seed_Jia.jpg 41006_result_euler_only_boundary


We study the problem of interactive segmentation and contour completion for multiple objects. The form of constraints our model incorporates are those coming from user scribbles (interior or exterior constraints) as well as information regarding the topology of the 2-D space after partitioning (number of closed contours desired). We discuss how concepts from discrete calculus and a simple identity using the Euler characteristic of a planar graph can be utilized to derive a practical algorithm for this problem. We also present specialized branch and bound methods for the case of single contour completion under such constraints. On an extensive dataset of ~1000 images, our experiments suggest that a small amount of side knowledge can give strong improvements over fully unsupervised contour completion methods. We show that by interpreting user indications topologically, user effort is substantially reduced.


  • Jia Xu, Maxwell D. Collins, Vikas Singh. Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), June 2013. PDF, Extended Version, Poster, Bibtex.

  • Dataset

    Our seeds database for Weizmann Horse Database (WHD), Weizmann Segmentation Database (WSD), and Berkeley Segmentation Data Set (BSDS500) can be download here.

    Source code

    Our source code can be downloaded here (31MB), README.txt.
    Click to see how EulerSeg works in practice.


    This work is funded via grants NIH R01 AG040396 and NSF RI 1116584. Partial support was provided by UW-ICTR and Wisconsin ADRC. Collins was supported by a CIBM fellowship (NLM 5T15LM007359).