These are boom days for online photo-editing sites. Most people have Internet connections that let them upload pictures relatively quickly, and Flash, the programming language on which many of the editing applications run, has advanced to the point that developers can use it to implement tricks previously found only in the pricey photo-editing software Photoshop.
Now, a site called Rsizr (pronounced “resizer”) has added a feature that isn’t even in the newest version of Photoshop: the ability to shrink or enlarge pictures–horizontally and vertically–with relatively little distortion. For instance, Rsizr can compress a photo of students in a classroom without sacrificing resolution by removing the pixels between desks. Likewise, Rsizr can expand the picture to fill, say, an entire computer screen by adding extra pixels in certain places.
The algorithm that Rsizr is based on was originally developed by Shai Avidan, senior research scientist at Adobe Systems, and Ariel Shamir, a visiting researcher at Mitsubishi Electric Research Laboratories, in Cambridge, MA. In August, Avidan and Shamir published their photo-editing trick, known as seam carving, at the annual SIGGRAPH conference in San Diego. In addition, the researchers posted a video on YouTube describing the technique. Will Tsui, the founder and only employee of Rsizr, saw the video, read the paper, and recognized that Avidan and Shamir’s algorithm could easily be modified to work in Flash. Independently, Tsui developed a Flash-based seam-carving program, added a few extra features, and designed an interface so that users could upload pictures and edit them in a Web browser. Rsizr was launched at the end of September. Other online photo-editing sites, such as Arbor Labs’ FotoFlexer, have adopted the algorithm too. It can also be added to Photoshop as a plug-in.
Adobe’s Avidan says that seam carving is fairly straightforward. If, for instance, a person wanted to compress a picture lengthwise by a single pixel, the software would scan the image to find the best pixels to remove. This is usually a zigzagging, vertical seam that is surrounded by pixels on the left and right that have a similar color. The pixel-wide seam is removed and the image is compressed without distorting the objects in the image. What makes the duo’s algorithm impressive is that it can find and remove these pixels quickly, so a person can expand and compress a picture quickly. The process works well for photos with backgrounds such as sky or grass, in which there can be little variation in color and pattern, Avidan explains, although it works poorly for people’s faces and more varied landscapes.
This video illustrates the process of removing a person from a picture using Rsizr. First the user selects the parts of the image that are important and shouldn’t be adjusted, and colors those items green. Then the user colors the items to be removed from the picture red. The software automatically removes the items to be deleted and reorganizes the photo according to the user’s demands.
Credit: Technology Review
By publishing the paper and making the approach available to anyone, Avidan inadvertently spurred the proliferation of sites that are making use of seam carving. He’s pleased to see the technique being used in a variety of ways by the open-source community and Web developers. But Avidan isn’t really surprised that some websites have made use of the technology. “It’s not a big effort to implement it,” he says.
Fredo Durand, a professor of computer science at MIT, notes, “Perhaps the best thing about this technique is its simplicity. It is a very short algorithm, and it works very well. This is why people like Rsizr and others have been able to implement it so quickly.”
While the seam-carving algorithm wasn’t difficult to translate into Flash, Tsui says that it took a few iterations to optimize his version of the technology so that it would work quickly on the Web. He also modified it so that a user could expand or contract in both the horizontal and vertical directions at once. “The novel thing about Rsizr,” he says, “is that it works in both directions simultaneously.” Getting this to happen was a challenge, he says, because removing a seam from the vertical direction can affect a horizontal seam later. Tsui’s software works by making educated guesses about the entire area around a pixel, estimating which pixels can be removed in both directions with the least amount of distortion to the picture.
Tsui says that he has received positive feedback from users about his product since its launch. He’s now working with an image-hosting company called Image Shack to implement his approach to seam carving.
Avidan says that seam carving can be used for more than just still images. While he won’t comment on his current work at Adobe, he says, “The next step will be applying [seam carving] to video.” The benefit here is that any video could fit on any screen, no matter the size. Additionally, it could make low-definition video look better when viewed on a high-definition display by dynamically adding pixels.