Home > V.3.1: Learning, Recognition, and Human Computer Interaction > Sketch-based object selection

 

Selecting Visual Objects with Freehand Sketches

Kar-Han Tan
Department of Computer Science
Narendra Ahuja
Department of Electrical and Computer Engineering

Beckman Institute for Advanced Science and Technology
University of Illinois at Urbana-Champaign


Introduction
Applications
Algorithm
Results
References
Contact Info

 

Introduction

Selectionin digital image editing is the task of extracting an object embedded in an image, a task performed frequently in many digital content creation applications. A classic example of selection is in broadcast television news where blue screen matting is used to place a newscasterís image in front of background graphics. Artists creating magazine covers routinely extract people or products from photographs to remove unwanted background and compose the new images such that magazine titles appear to be occluded by the object naturally. Currently a number of commercial tools are available that aid in the process, but they either have severe limitations in their capabilities, or require very careful user guidance and control. In this project, we attempt to making selection easier and usable in a wider range of applications. We present the design of a tool for selecting objects using simple, rough freehand sketches similar to those used in normal interhuman communication.

Figure 1. Example of object selection. (a) Original image, with a sketch drawn over image. (b) Selection computed is composited against a black background. (Original image by Gerald and Buff Corsi, California Academy of Science)

 

Applications
A sketching interface is an appropriate choice for image editing because the pen and pencil are ubiquitous tools for creating graphics, and sketch-based interaction would be very natural for use in handheld personal digital assistants and the emerging class of ìtabletî computers. A typical example of the kind of sketch allowed by the selection tool we will describe is shown in figure 1(a). With the sketch shown, our selection tool was able to extract the head of the crane, as shown in figure 1(b). Despite the fairly convoluted profile of the craneís head, which consists of both sharp boundaries along the beak and complicated boundaries around the craneís crown, our selection tool needed only the simple sketch shown, which is natural and can be drawn quickly, without much skill and dexterity. We believe that this tool will enable sophisticated and high-fidelity graphical selection and manipulation operations in situations where the user may not have much time, such as during a live sports broadcast, or may not have much dextrous control, such as on a mobile handheld device, or may want to avoid the monotony and tedium of selection, without compromising the quality of the selection. 

 

Algorithm

Step 1: Draw Sketch

User draws sketch over the image. Users can make three types of sketch strokes:
  • Points
  • Lines
  • Regions (closed loops)

Step 2: Image Segmentation

Compute a global segmentation of the image. We can use any existing segmentation method. The segment map illustrated is computed by recursive binary-split vector quantization in the (x,y,rgb) space.

Step 3: Sketch Processing

Use sketch to select a number of segments from the image that form the foreground object.

Step 4: Simplicial Decomposition

We want to decompose the image into small triangles so they can be processed individually. We can use: 
  • Delaunay Triangulation of the segment centroids, [1] or
  • Use the segmentation to compute a triangulation [2].

Step 5: Object Extraction

Each triangle is processed separately as follows:
  • Find a linear approximation to the local object boundary.
  • Re-segment the image within the boundary using the same segmentation algorithm as in step 2.
  • Classify the new segments into foreground/background using the linear boundary.
  • Pick a window of pixels around each of the new segment centroids and use them as samples of foreground/background colors
  • Estimate alpha channel

Step 6: Complete Selection

Composite the result from each triangle back into a complete selection.

Figure 2: Steps in selection algorithm.

 

Results


 

Sketch

Resulting Selection
Figure 3: Results computed with the Delaunay Triangulation decomposition method.


References

1. Kar-Han Tan and Narendra Ahuja. Selecting Objects with Freehand Sketches. In Proceedings IEEE International Conference on Computer Vision. 2001. 
Download Paper: [PS 19.8MB][PDF 12.9MB][ Small PDF 1.3MB]

2. Kar-Han Tan and Narendra Ahuja. A Representation for Image Structure and its Application in Object Selection with Freehand Sketches. In Proceedings IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2001. 
Download Paper: [PS 13.2MB][PDF 4.3MB][Small PDF 1.3MB]

 

Contact Information

Kar-Han Tan

e-mail: tankh at vision.ai.uiuc.edu
Phone: 

217-244-4392 (lab)
217-333-1869 (office)
Address: 
Beckman Institute
405 N Mathews Ave
Urbana IL 61801

 

Acknowledgements

We would like to thank Mark Ruzon and Carlo Tomasi for making available the source code for alpha estimation. The support of the Office of Naval Research under grant  N00014-96-1-0502, and the Beckman Institute Graduate Fellowship is gratefully acknowledged.

| Home | Projects | People | Publications | Links |