Seam Carving - acnelson12/CS-335-Algorithms GitHub Wiki

The biggest problem I have found is that transparency is handled very poorly (and by “very poorly”, I mean not at all, and bad things happen because of it). I am not sure of how to go about the resolution of this issue. It seems that one would have to create maps of both the color gradient and the alpha gradient. While this in itself is relatively simple, I don’t really know where to go from here.

I have run the program on some line-drawing SVGs that I converted to PNGs. When the program is run on such pictures, a bias towards seam removal from particular sides becomes very apparent. The only way I can see to resolve this is to randomize seam selections when ties are encountered, but this could cause a drop in performance as well as (and most importantly) potentially leading to different results on different runs when given the same input.

Initially, I was rather dissatisfied with the runtime of my program. The problem with the runtime is mostly with the horizontal seam removal. Although transposing the array does make the code simpler, it creates a substantial bottleneck. To this problem, I tried to apply the little I know about computer architecture. This is my understanding: The simplest matrix transposition algorithm involves many non-contiguous memory accesses. This will lead to many processor cache-misses during execution, slowing down the program and using more memory bandwidth. In my research, this led me into the concept of cache-oblivious algorithms. I found that divide-and-conquer algorithms naturally take advantage of the processor caching system, so I tried to write an algorithm that used this tactic in a method called transposeR (R for Recursive). I tested the runtimes of the iterative solution vs. the recursive solution on a 5184×3456 image and found that the recursive solution consistently ran about 100 seconds slower. Any number of things could be to blame for this, from less-than-ideal circumstances with the way the image is stored, to ignorance and error on my part, to the dynamic nature of Java interfering with optimization attempts that would be simpler in a language like C/C++. The first break-through in speed was made when I directly used BufferedImage’s getRGB method. To gain more access to this method, I moved the shrinkImage method to the UWECImage class as well as the transpose methods. Largely through this, but also through other tweaks, I was pretty much able to cut the runtime in half. I decided to push the limits as far as I could with the methods fastVSShrink and fastHSShrink which are mainly designed to take advantage of the fact that not all values in the energy and path-weight maps need to be recalculated.

Also, in the context of matrix operations, the transpose is not a rotation but a reflection across the diagonal. I’m not sure if this is what was meant in the specs.