A Representation for Image Structure and its Application in Object Selection with Freehand Sketches

Kar-Han Tan and Narendra Ahuja

We present an algorithm for computing a representation of image structure, or image segmentation, and use it for selecting objects in the image with freehand sketches drawn by the user over the image. The sketches are mapped onto image segments whose union forms the intended object. The mapping operation is performed with the aid of a simplicial decomposition of the image segmentation - a triangulation formed with vertices chosen to lie along the medial axes of the segments. Each edge of a triangle lies entirely inside the two segments that contains its vertices. This decomposition captures the adjacency information about the segments as well as the shape of the segment boundaries. Any object boundary is completely contained in a set of triangles. The triangles are also used to formulate the problem of estimating gradual photometric transition across an object boundary, called alpha channel estimation, as a set of local, intratriangle alpha channel estimation problems that can then be solved more accurately, independently, and in parallel. Experimental results are included to show how the algorithm allows selection of image objects with complex boundaries using roughly drawn simple sketches.

Keywords: image segmentation; computer vision; object detection; objects selection; freehand sketches; interactive tool; object boundaries; user input; image computation; two-phase algorithm; coarse global segmentation; finer-grained segmentation; linear approximation; image editing

Full Text: PS 13.2MB PDF 4.3MB Small PDF 1.3MB