Edge-Respecting Brushes

Related comments:


Summary:
In this paper, Dan R. Olsen Jr. and Mitchell K. Harris of Brigham Young University's Computer Science Department discuss various methods of making brushes for image-editing programs like Photoshop "smarter" by utilizing least-cost algorithms and edge-respecting implementations.  

The authors discuss five prior techniques that framed their research -- flood fill (fills all adjacent pixels the same color until a clearly-defined edge is reached), boundary specification (the "lasso" tool), tri-maps (user-specified map of foreground, background, and unused pixels), bilateral grids (color difference-aware), and quick select (inferred selection from a brush stroke).  The edge-respecting brush they developed takes elements of these techniques and refines them by applying cost and alpha computation algorithms like the one below:

A user study was conducted with 9 subjects who were asked to manipulate 6 images each.  The edge-respecting brush was found to produce edge-agreement accuracy 99% of the time -- 3% higher on average than the traditional lasso and snap tools.

Discussion:

I wish Photoshop already had something like this.  Lasso selection is a painful process that requires Keebler-elf precision and saintly patience to yield accurate results, and most snap tools don't perform well enough for my needs.  Being able to paint along an edge without fear of messing up a critical part of the image would make creating layers much easier, and generally speed up the image editing process.  

EDIT:  I found out a few days ago that Photoshop CS5 is actually implementing something like this with their "content-aware fill" tool.  Awesome!