ABSTRACT

Image segmentation is an indispensable processing tool due to its wide applications in science, medicine, and the arts. The most successful segmentation algorithms map pixels onto a graph, define an energy function on this graph, and cast segmentation as a minimization of this discrete space using graph theory to compute minimum cuts, minimum paths, minimum spanning trees, or random walks on the graph. While segmentations can be calculated automatically, semi-automatic interactive approaches based on user input are often preferred because segmentations can be ill-defined, ambiguous, and/or subjective for many applications. Furthermore, while efficient for small images, graph-based algorithms scale poorly for large imagery, and in recent years consumer and scientific imagery has exploded in size. This work will lay the foundation for novel algorithms for robust interactive segmentation of large imagery that provide actionable real-time feedback independent of the image size, fluid interactions that scale with the segmented object, interactivity without the need for a significant high-performance backend, and the ability to run on modest hardware like mobile devices. The techniques developed in this research will not only provide fundamental contributions within computer science, but will enable significant advancements in applications across the sciences, in medicine and the arts. More immediately, the project will support a graduate student who is a member of an underrepresented minority, and will provide the groundwork for a high-impact dissertation.

The work will focus on scalable algorithms for minimum cut and minimum path segmentations. First, the research will target robust, hierarchical segmentation through the use of improved image filtering and the computation of multiple narrow bands. This will improve on the state-of-the-art which currently either produces poor segmentations due to falling into local minima during the optimization, needs a significant high-performance backend, or relies on heavy heuristically-driven preprocessing. Second, the work will design a novel query-driven, view-dependent segmentation that is produced as a user explores the large image and manipulates the segmentation without the need of the full resolution solution. This enables the deferment of the expensive full optimization until after the interaction is completed. User effort for interactions will be independent of the scale of the segmented object. Assuring that the local, view-dependent solution is a valid representation of the full optimization without knowing the solution a priori will constitute a significant advancement to the state-of-the-art in image segmentation.

Please report errors in award information by writing to: awardsearch@nsf.gov.