One of my favorite kinds of assignments in Computer Science classes are the ones that I can show to people because they’re more visually appealing and understandable than just lines of code or a generic print out of a statement. We got an opportunity for this kind of assignment when we analyzed a photo to find “seams.” A seam is a line that, if it were to be removed, would cause the smallest amount of disturbance. For example, in the photo below, the original is on the left. In the photo in the middle, the red lines are the seams of pixels that if removed would cause the photo to stay relatively undisturbed. The photo to the right is what that photo would look like if the seams were removed.
The way we are able to do this is by getting a disruption value for each pixel then moving either to the pixel directly down, down-left, and down-right from the original pixel and adding those disruption values until you reach the bottom of the image. One way to do this is to take each pixel and calculate each seam individually. However, for each pixel, there are three possible directions the seam could go, and each of those three has three other directions it could go, and etc. So imagine the number of seams one would have to calculate and if the photo is anything larger than 5 x 5 pixels. It would take an obscene amount of time to calculate all those seams, store them, and then find the seam with the smallest disruption value. Additionally, for each pixel you can go in three directions down, down-left, and down-right so there will be pixels that will be a part of many different seams. calculating that value more than once is rather impractical. Therefore, for our assignment, we needed to apply our knowledge of algorithms and data structures to find a faster way to do this. We implemented a hashtable which for the sake of simplicity is comparable to an excel sheet with cells. Each “cell” held the value of a pixel. We then examined each pixel or cell and found the cell that was either above, above-left, or above-right with the smallest disturbance value, then added that disturbance to the current cell’s disturbance value. Once we had done that for every “cell” in the table we backtracked to find the seam with the smallest disturbance.
