15-463 Fall 2007
Seam-carving for Multiscale Image Rendering in Hypertext Documents
Although interactive examples of seam-carving have been demonstrated, it has primarily been viewed as a static procedure; the goal has been to produce resized images rather than to produce an image in a form that allows for dynamic resizing.
Avidan and Shamir make mention of such a technique and describe the data structure that would be necessary for its implementation, but they only mention one application (images in web pages) and neglect to consider how this might be accomplished. I have implemented such a technique to allow for the presence of images which are resizable through seam-carving in web pages.
My solution consists of three parts:
- Precompute the data structure needed for fast seam-carving and insertion. This is done automatically when images are uploaded to the server. This data structure consists of a matrix of indices where each value corresponds to a pixel in the image. These values specify the order in which pixels are removed as we shrink the image. Please see section 6 of Avidan and Shamir for more details.
- A client-side script determines the dimensions required for the image to fit in the web page and requests such an image from a server-side program.
- The server-side program uses the precomputed data structure to produce an image of the desired size. This image is cached to reduce the time required to process future requests, and its URL is returned to the client-side script which displays it in the document.
Unfortunately, my implementation requires some special server setup, so I am not able to provide a demonstration here. A full demonstration of the technique including image uploading and complete image-resizing demos is available here, however. Please be gentle with my server, as it is small and puny. Also note that, as of 12/17/2007, the client-side script only works in Firefox. I will be working to make it more portable as I have the time.
Overall, the results were very good. My solution is able to resize and display multiple images concurrently. The performance of the system is somewhat underwhelming, taking 2 or 3 seconds to resize and display an image, but my seam-carving implementation is not particularly efficient so I suspect that this can be greatly improved. Also remember that it is to be expected that this system have the same deficiencies as regular seam-carving. Some images work better than others, and even for those that work well there is a limit as to how small the images can be shrunk before being distorted.