This program allows you to upload and crop your images horizontally using seam carving, a technique for reducing image sizes while keeping the most information
possible in the image.
Seam carving allows you to take an image such as
And by cutting 300 pixels (about a half of the image), get the following result
Where the main information of the image has stayed, and areas where there is little information has been cut dynamically.
Note: Currently this project has not been optimized for speed, and so this process is currently on the order of a few minutes for seam carving a high percentage of some large images, however if more time gets allocated to this project in future this will be quickened substantially ideally.
Seam carving uses three main steps in processing the image to dynamically cut a "seam", a line of connecting pixels from the top of the image to the bottom, from the image.
Firstly, we run a simple edge detection algorithm across the image. The information that seam carving attempts to preserve is based on the strong edges in the image, so backgroup material is often cut in way of keeping foreground objects present. We do this by convolving the image using the sobel operator.
Second we take the edge detected image and compute what we call an energy image using dynamic programming techniques. To identify a path of least edges from the top to the bottom, we dynamically fill in a new table bottom-up with path-summed edge values. Starting at the bottom row, each value (0-255 as image is black and white, and then normalized to 0-1) is filled into the table, Then for each next row, row[i] = edge(row[i]) + max((row-1)[i-1], (row-1)[i], (row-1)[i+1]), i.e, the current edge value at the image plus the largest current path below it. This dynamically gives a table of an image as show above, where dark spots are low "energy", or low edge value paths, and very white are high edge value paths.
Finally, once we have an energy table calculated, we simply follow the minimum values of the image downward. We start by finding the minimum value on the top row, which will correspond to the lowest energy total path. This gets added to our seam. Then, seam[i] = min(rowOF(seam[i-1])[i-1], rowOF(seam[i])[i-1], rowOF(seam[i-1])[i+1]). We simply follow the minimum path down from the starting pixel of the seam. This results in a seam as shown above. Then we recreate the original image, ignoring these pixels, and a seam has been removed from the image.
To cut a large amount of this image, we just repeat this process, identifying and cutting new seams.