Smart Image Resizing Using Seam Carving
Seam carving is a fascinating technique to scale up/down an image (or a video frame).
Caution: It is slow. I will optimize it to work in real-time when I get time to work on it again. [dead!] http://seam.ashishchaudhary.in:8080/
The code is available at: tocttou/smartresizing
The algorithm implementation is available directly at: SeamCarver.kt
- Max image size: 1MB
- Max image resolution: 600x600
- Max dimension change at a time: -+30%
The code is written to be thread safe and can run multiple workers in parallel using rabbitmq. However, I can only afford to allot this service a single core CPU with 512MB RAM, with a single worker running. So if it feels stuck on the loading screen, please be patient and allow it a minute to process. Cancelling and trying out another image does not cancel the previous task, and the new task will get queued.
Results are fascinating (mostly).
Reduction and Expansion
energyfor each pixel in the image based on the local color gradient (rms value of error in color between the adjacent pixels) - values can be cached but it becomes too memory intensive.
- Add two virtual pixels, one at the top and one at the bottom of the image.
- Construct an edge-weighted-digraph with the top virtual pixel as the source and the bottom virtual pixel as the sink. Each pixel points to the pixel directly below it and the two pixels adjacent to that pixel. The top virtual pixel points to all the pixels in the top row, and all the pixels in the bottom row point to the bottom virtual pixel.
- We need to find the seam (path) with the low total energy, since that would be the seam that could be removed without affecting the image much. Starting from the top and coming to the bottom, we can see that the digraph is already topologically sorted and is guaranteed to be acyclic. This means that we can simply relax the edges as we come downwards using dynamic programming. Keep track of the edge in the lowest energy path connecting each pixel.
- Trace back the edge with the lowest energy from the bottom virtual pixel up to the top virtual pixel to obtain the seam.
- Once the seam is obtained, remove it from the image.
- Repeat this process
dimension - desiredDimensiontimes.
- Take a temporary copy of the original image and perform reduction on it
dimension -desiredDimensiontimes. Keep a track of all the consecutive seams thus obtained.
- Since the reduction of these seams was supposed to cause the least change in the appearance of the image, addition of a seam nearby in the original image will have the same effect.
- For each such obtained seam, add a seam adjacent to the location of that seam in the original picture. The color of an added pixel in that seam is calculated by averaging the colors of the adjacent pixels.
The code is written in Kotlin and is self-explanatory. It has the following components:
- A webserver with websockets to propagate results using Ktor.
- A task dispatcher.
- A message broker (rabbitmq).
- A forward queue for tasks, a backwards queue for results.
- A task runner (consumer).
Task runner is independent of all other parts, can be launched separately, and can have multiple instances running at once. Message broker passes the tasks to these instances in round-robin fashion.
A caching layer returns the pre-computed results if available.
Big improvments can be made by pre-computing the edge-weighted-digraph and just mutating the seams adjacent to the lowest energy seams as required. I will work on this whenever I get time. Caching the energy values helps a bit too, but not much.