Collaborators:

Hiroshi Ishikawa (New York University, USA).

Key words:

Region/boundary identification, region/boundary unification, energy minimization, global optimum, minimum ratio weight cycle, active contour, snake, segmentation.

Resume:

We describe a new form of energy functional for the modelling and identification of boundaries and regions in images. The energies are defined on the space of 1-boundaries in the image domain, and have the following properties:

1. The new energies are as general as those used in classical active contours. Thus they can incorporate very general combinations of modelling information both from the boundary (intensity gradients,...) and from the interior of the region (texture, homogeneity,...).
2. Unlike classical active contour energies, which present either trivial global minima or NP-complete optimization problems, the global minima of the new energies can be found in polynomial time. We describe two polynomial-time digraph algorithms for finding these global minima. One of the algorithms is completely general, minimizing the functional for any choice of modelling information. It runs in a few seconds on a 256 x 256 image. The other algorithm applies to a subclass of functionals, but has the advantage of being extremely parallelizable. Neither algorithm requires initialisation.
3. The new form of energy has attractive theoretical properties not possessed by classical energies.

Publications:

• "Globally Optimal Regions and Boundaries as Minimum Ratio Cycles”, Ian H. Jermyn and Hiroshi Ishikawa. IEEE Transactions on Pattern Analysis and Machine Intelligence (Special Section on Graph Algorithms and Computer Vision), Vol. 23, No. 10, pp. 1075–1088, October 2001. (PDF) (Copyright IEEE)
• "Region Extraction from Multiple Images", Hiroshi Ishikawa and Ian H. Jermyn. Proceedings of the 8^th IEEE International Conference on Computer Vision, Vancouver, Canada, 2001. (PDF) (Copyright IEEE)
• "Globally Optimal Regions and Boundaries", Ian H. Jermyn and Hiroshi Ishikawa. Proceedings of the 7^th IEEE International Conference on Computer Vision, Kerkyra, Greece, pp. 904–910, September 1999. (PDF) (Copyright IEEE)