Showing posts with label seam carving. Show all posts
Showing posts with label seam carving. Show all posts
Between the Canvas and the WebWorker
A few weeks ago, I had written a pure Javascript implementation of the Seam Carving algorithm using Canvas and Web Workers. The advantage of using web workers was to allow the intensive processing of seam carving to run in the background without freezing the UI thread.
There was only one step in this process that still did not fit into the picture - passing the result from the Web Worker to the DOM due to context differences. This was slow as all pixel had to be copied into the CanvasPixelArray of the ImageData. This was a nested loop taking n x m operations.
This post is about the various alternatives I looked at to make this process better, and how the technique used here could feed into a generic canvas+webworker framework for image manipulation.
DataURIs
If I did not want to copy the n x m pixel,I needed a way to send the information from the Web Workers in a way that can be used in the DOM. DataURIs are a good alternative.I looked at a PNG library written in Javascript and it looked promising. Unfortunately, the compression and processing inside the Web Workers was taking longer than pixel copying. Also, it did not work for images wider than 325 pixels.
To avoid the overhead of compression, I tried using a Bitmap library but was having a hard time getting it to work. The dataURI for the uncompressed image that this library generated was invalid. I was losing the alpha transparency parameter anyway.
Forking off for Chrome
If I could not get a image processing library working, I had to find a way to make the pixel copy quicker. I had earlier written that in Firefox and Opera, I could create an object with the height and width as dimensions of the image and assign an array to its data property. I could draw this image using the putImageData and it worked like a charm.Ch
Chrome however, threw an exception because imageData.data was not of type CanvasPixelArray. I caught this exception and resorted to pixel copy in case of Chrome. Interestingly, Chrome traces that part of the code and runs it significantly faster than the other browsers.
Here is the commit with this implementation.
Internet Explorer?
Internet Explorer 9 Beta does not support WebWorkers yet and hence, the demo won't work. I am planning to see if I can move the SeamCarver.js to run on the server using Rhino or Nodejs.
About the Framework
When I started with project, I was also talking to the creator of Caman. It looked like a promising framework for image manipulation using Canvas and Web Workers. Unfortunately, it was plagued by the same issue of pixel copy, and the creator decided to move away from using Web Workers.
The library currently breaks the image into horizontal partitions and processes each strip with a setTimeout.
Apart from still hogging the UI thread (to a lesser extent), this also does not support from image processors like Seam Carving that require processing the whole image.
I hope to convince Caman to move back to its original model, or fork the project back to its original form and use this method of passing information between the canvas and web workers.
Watch this space for more updates.
SeamCarving with Canvas and Web Workers
I had written about Seam Carving in Javascript in my earlier posts. The example that I had till now only demonstrated removing the pre-calculated seams and ran in the browser's foreground thread. This post is about SeamCarving done using Web Workers and Canvas.
A couple of week ago, I stumbled upon CanMan.js on reddit and thought that I could add seam carving as a filter to it. The filters leverage Web workers and it looked like a framework to implement image manipulation filters. Unfortunately, the API signature required for the filters did not allow manipulation based on adjacent pixel in an image. Hence, it was not suitable for Seam Carving.
Having started, I decided to enhance the existing example to use Web Workers. First, I added the missing logic to calculate seams for any image. Since this was an operation what would take a long time, I had to move this processing to web workers. Some interesting observations along the way include
Passing Image Data
The SeamCarver operation takes the image pixels as input and returns image pixels after the desired operation. The canvas' getImageData returns the type ImageData which cannot be passed around in the worker context. Hence I had to deconstruct and reconstruct this every time the processing was complete. This meant that I had to copy all the pixels from an array to the array-like CanvasPixelArray in the ImageData. Interestingly, I could simple reassign the array and Firefox/Opera seems to be fine with it. Chrome however did not accept the simple array assignment, and I had to iterate on the pixels, copying them into the CanvasPixelArray.
Another interesting observation here was that Chrome, with its tight loop tracing performed a lot better than Firefox. I am assuming that Firefox 4 would get the same speed benefits.
Debugging Workers
The hardest part during development was debugging. With so much pixel manipulation, I needed a way to break on statements. Unfortunately, neither Firebug, nor Venkman broke on web worker threads. Chrome developer tools were also not much of a use either. I am hoping that the generic script tools include worker scripts in the script tags.
UI Thread responsiveness
The idea of web workers was to demonstrate UI responsiveness. I thought of using loader gifs, rewriting the DOM with javascript, etc, but finally zeroed in on using a scrolling marquee.
Next Steps
The seams are carved vertically only, so resizing it on the y axis is still not possible.
Some of the things that I am looking at doing in the future include
- Support y-axis resizing
- Port carving to server (using node, etc) and the browser re-sizes the image.
- Try to see if I can use as an example for getting the right API signature in frameworks like CanMan.
Seam Carving as a Service
Hey,
This is in continuation of my posts on Seam Carving. In the previous article, I was talking about making Seam Carving as a web service. I had noted that both HTML Canvas, and Flash were terribly slow while resizing images. The Java implementation of the algorithm seemed fast enough, and given network speeds of today, server based image resizing seems like a practical solution to bring seam carving to the browser. Due to lack of hosting space, I was not really able to host the servlet. However, it would be great if someone could host the Java Servlet that I wrote.
The corresponding client side operations would now become a lot simpler. The HTML Pages that contains images that require to be contextually resized could have a class, say something like <img src="http://www.blogger.com/../img.jpg" class="seam-resize" />. A non-obtrusive JavaScript on the page could have a hook to all the resize events of the image, and replace the source of the image with something that is like
I am still trying to host it by writing a PHP version and hosting it. Will post the link as soon as that is complete.
This is in continuation of my posts on Seam Carving. In the previous article, I was talking about making Seam Carving as a web service. I had noted that both HTML Canvas, and Flash were terribly slow while resizing images. The Java implementation of the algorithm seemed fast enough, and given network speeds of today, server based image resizing seems like a practical solution to bring seam carving to the browser. Due to lack of hosting space, I was not really able to host the servlet. However, it would be great if someone could host the Java Servlet that I wrote.
The corresponding client side operations would now become a lot simpler. The HTML Pages that contains images that require to be contextually resized could have a class, say something like <img src="http://www.blogger.com/../img.jpg" class="seam-resize" />. A non-obtrusive JavaScript on the page could have a hook to all the resize events of the image, and replace the source of the image with something that is like
http://../imageResizeServlet?url=originalUrl.jpg&width=newWidth&height=newHeightThe Servlet internally reads the original image in an InputStream and applies the seam carve function on it. The output of the servlet is the image with the appropriate headers. As an optimization, the JavaScript in the page can stretch the image immediately after the resize, and then redraw the seam carved image as soon as the server returns it. At the server side, instead of reading the original image on every request, it can be cached. The result images with a step of an optimal values can also be cached to enable faster replies by the server.
I am still trying to host it by writing a PHP version and hosting it. Will post the link as soon as that is complete.
Image Resizing - Images from the Server
Hey,
A quick peek at Image Resizing using Flash or HTML canvas shows that it may not yet be feasible to use the technique for actual web sites. Unlike the demo real web sites may not really require changing the picture in real time. The resize could be initiated only when the browser is resized. Hence, I was looking at a more realistic image resizing implementation, having minimal JavaScript code at the client, and not really slowing down the browser by intensive Flash or JavaScript computation.
This approach relies in the image being actually being performed at the server, and the client only fetching the changed image in the background. When the browser is resized, the image is first resized in the native way, and then, the JavaScript code that is triggered, loads the seam-carved image. This approach also had the problem of network latency, and hence I was looking at using YUI Image Loading utility to load the images the background, to reduce the delay between actual resizing and seam based resizing.
A simple central server could host this as a service, reducing the image to the required dimensions. For the demo, due to the unavailability of the server, I precomputed the images for widths 350 to 200, in intervals of 5. The JavaScript in the page first resizes the image to the required width using native image resizing, and then loads the seam resized image. An addition is the use of the YUI image library that tries to pre-load the data for the image in the back ground. It would be great to hear your feedback on the performance for different network latencies.
Please check this link for the demo.
[UPDATE : Having problems with hosting the images. Demo not showing server image. Working to find some other image hosting site]
A quick peek at Image Resizing using Flash or HTML canvas shows that it may not yet be feasible to use the technique for actual web sites. Unlike the demo real web sites may not really require changing the picture in real time. The resize could be initiated only when the browser is resized. Hence, I was looking at a more realistic image resizing implementation, having minimal JavaScript code at the client, and not really slowing down the browser by intensive Flash or JavaScript computation.
This approach relies in the image being actually being performed at the server, and the client only fetching the changed image in the background. When the browser is resized, the image is first resized in the native way, and then, the JavaScript code that is triggered, loads the seam-carved image. This approach also had the problem of network latency, and hence I was looking at using YUI Image Loading utility to load the images the background, to reduce the delay between actual resizing and seam based resizing.
A simple central server could host this as a service, reducing the image to the required dimensions. For the demo, due to the unavailability of the server, I precomputed the images for widths 350 to 200, in intervals of 5. The JavaScript in the page first resizes the image to the required width using native image resizing, and then loads the seam resized image. An addition is the use of the YUI image library that tries to pre-load the data for the image in the back ground. It would be great to hear your feedback on the performance for different network latencies.
Please check this link for the demo.
[UPDATE : Having problems with hosting the images. Demo not showing server image. Working to find some other image hosting site]
Applying Web Based Seam Carving for the "REAL" web page
Hey,
The demonstration video of seam carving indicated that images should be considered at par with text on web pages, and should react to resizing just like text, by automatically adjusting to the available width. With many people implementing seam carving, I picked up a couple of implementations and tried to apply this technique to real web pages. Most of the implementations that I found were executables. There was one good flash implementation that could be used in real web pages.
This article (and this label) suggests some alternatives to make seam carving realistic. I have not had time or server space to implement them all, so I just thought of putting down the steps in text, and a crude demo of what I was able to achieve. As I find more time this week, I would try to refine the demo to something more usable.
Firstly, the <IMG> tag does not allow manipulation of an image at a pixel level. Hence, till the browsers come out with native support for re-targeting, web page will have to squeeze in this functionality using the limited JavaScript support available. That leaves us with two alternatives.
All the <IMG> tags on the page could be simply replaced with a Flash object, or the HTML5 canvas element. These are the two tags that allow manipulation of an image at a pixel level. However, I discovered that the entire process of finding the energy function and subsequently, the seam are very costly processes. I tried to implement a Soble Filter in JavaScript to find the edges, but the browser easily gave up. The flash implementation seemed to work fine. Nevertheless, the operations seem to freeze the browser for some time.
Hence, it may be worthwhile to find the seam at the server, and just pass down the data structure that represents the seam to the client.
Now, all the client has to do is to replace the images that have to be resized with an canvas of equal dimensions, the image drawn on it. When the image is resized, the JavaScript kicks in, removing 'n' seams from the image, where n equals to the difference of the original width and the changed width.
I tried this out for a HTML page, but found that the dynamism that was shown the the video seemed a little tough to achieve. The canvas was very jittery, did not refresh when a new image was drawn, and seemed to hang the browser. Also, the sobel filter that I had used for the energy function was not great with many images.
My demo is currently hosted here, and watch out for updates to the demo.
The demonstration video of seam carving indicated that images should be considered at par with text on web pages, and should react to resizing just like text, by automatically adjusting to the available width. With many people implementing seam carving, I picked up a couple of implementations and tried to apply this technique to real web pages. Most of the implementations that I found were executables. There was one good flash implementation that could be used in real web pages.
This article (and this label) suggests some alternatives to make seam carving realistic. I have not had time or server space to implement them all, so I just thought of putting down the steps in text, and a crude demo of what I was able to achieve. As I find more time this week, I would try to refine the demo to something more usable.
Firstly, the <IMG> tag does not allow manipulation of an image at a pixel level. Hence, till the browsers come out with native support for re-targeting, web page will have to squeeze in this functionality using the limited JavaScript support available. That leaves us with two alternatives.
All the <IMG> tags on the page could be simply replaced with a Flash object, or the HTML5 canvas element. These are the two tags that allow manipulation of an image at a pixel level. However, I discovered that the entire process of finding the energy function and subsequently, the seam are very costly processes. I tried to implement a Soble Filter in JavaScript to find the edges, but the browser easily gave up. The flash implementation seemed to work fine. Nevertheless, the operations seem to freeze the browser for some time.
Hence, it may be worthwhile to find the seam at the server, and just pass down the data structure that represents the seam to the client.
Now, all the client has to do is to replace the images that have to be resized with an canvas of equal dimensions, the image drawn on it. When the image is resized, the JavaScript kicks in, removing 'n' seams from the image, where n equals to the difference of the original width and the changed width.
I tried this out for a HTML page, but found that the dynamism that was shown the the video seemed a little tough to achieve. The canvas was very jittery, did not refresh when a new image was drawn, and seemed to hang the browser. Also, the sobel filter that I had used for the energy function was not great with many images.
My demo is currently hosted here, and watch out for updates to the demo.
Seam Carving for the web
Hey,
Since it appeared on the first page of TechCrunch and Digg, seam carving based image resizing seems to have garnered enough attention to trick any coding enthusiast into coming up with an implementation of the algorithm. A little research, and I found a some source code and interesting examples here, here and here.
I got a little curious and started a little exploration. A couple of hours, and I was finally able to get my own version of the filter to find the energy function of the image. A little more coding, and JavaScript seemed to be stretching to its maximum. By the time the sobel filter was complete, the browser started throwing up the "Script taking too long to execute error".
This is where I had to backtrack a little and get some server side that would compute the seams. The only responsibility that JavaScript now holds is to fetch the seams from the server, given an image, and remove the seams.
Here is the workspace
You could use the build.xml with ant to see this in action.
Some enhancements that remain to be done are
Since it appeared on the first page of TechCrunch and Digg, seam carving based image resizing seems to have garnered enough attention to trick any coding enthusiast into coming up with an implementation of the algorithm. A little research, and I found a some source code and interesting examples here, here and here.
I got a little curious and started a little exploration. A couple of hours, and I was finally able to get my own version of the filter to find the energy function of the image. A little more coding, and JavaScript seemed to be stretching to its maximum. By the time the sobel filter was complete, the browser started throwing up the "Script taking too long to execute error".
This is where I had to backtrack a little and get some server side that would compute the seams. The only responsibility that JavaScript now holds is to fetch the seams from the server, given an image, and remove the seams.
Here is the workspace
You could use the build.xml with ant to see this in action.
Some enhancements that remain to be done are
- convert this to a full fledged demo
- extract this to a independent library, so that this can be used unobtrusively in HTML
- horizontal seam
- image expansion
Making people disappear from Images - Context Aware Image Resizing
Hey,
A couple of days back, I saw an paper on Context Aware Image Resizing by Dr. Ariel Shamir and Dr. Shai Avidan. The concept seemed interesting, and the demonstration video showed some example of how effective context aware image resizing can get. There were people asking for it as a feature in Photoshop.
I was wondering if this could be a useful in HTML pages. Thats how I sat down and started writing quick Javascript to see this magic for images in HTML page. The algorithm over all is simple; the only complexity lies in defining the energy function. This article explains the architecture of the JavaScript code and its functionality of the HTML image resizing code that I am writing. As soon as I give the final touches to the HTML code, I would put it out.
The JavaScript code is non-obtrusive, and requires HTML 5 Canvas element. It does nothing if HTML 5 is not supported. Consider an image is defined using a tag like <image src = "blah" class="autoresize" style = "height : 100; width : 100" >
A wrapper JavaScript class reads the HTML for all the image tags with the specific classname, and initializes them to a ImageResize class. As initialization, the image resize calculates the energy function (that can be customized), then the horizontal and vertical seams using dynamic programming as described in the paper. It then redraws the entire image for that particular dimension. The resize is also captured to enable dynamic image resizing, one of the "wow" factor of the paper.
The script gets a little slow if given a lot of images, and I am looking at way to increase the speed. Watch out for live example that I will post later.
A couple of days back, I saw an paper on Context Aware Image Resizing by Dr. Ariel Shamir and Dr. Shai Avidan. The concept seemed interesting, and the demonstration video showed some example of how effective context aware image resizing can get. There were people asking for it as a feature in Photoshop.
I was wondering if this could be a useful in HTML pages. Thats how I sat down and started writing quick Javascript to see this magic for images in HTML page. The algorithm over all is simple; the only complexity lies in defining the energy function. This article explains the architecture of the JavaScript code and its functionality of the HTML image resizing code that I am writing. As soon as I give the final touches to the HTML code, I would put it out.
The JavaScript code is non-obtrusive, and requires HTML 5 Canvas element. It does nothing if HTML 5 is not supported. Consider an image is defined using a tag like <image src = "blah" class="autoresize" style = "height : 100; width : 100" >
A wrapper JavaScript class reads the HTML for all the image tags with the specific classname, and initializes them to a ImageResize class. As initialization, the image resize calculates the energy function (that can be customized), then the horizontal and vertical seams using dynamic programming as described in the paper. It then redraws the entire image for that particular dimension. The resize is also captured to enable dynamic image resizing, one of the "wow" factor of the paper.
The script gets a little slow if given a lot of images, and I am looking at way to increase the speed. Watch out for live example that I will post later.
Subscribe to:
Comments (Atom)