Seam Carving
Read the full writeup.
Seam carving isn’t a particularly complicated concept. Basically, we’re removing unimportant “seams” of our images in order to adjust the size while also preserving the good stuff. We define the importance of each pixel as the pixel’s gradient magnitude.
To determine the optimal vertical seam to remove, we follow the dynamic programming approach of computing the cumulative minimum “energy” (i.e. importance) of each pixel, and then backtracking from the least important entry in the bottommost row. Since the removal of one seam equates to the removal of one pixel from the total width, we repeat this process – identification and removal – until our image has the desired dimensions. Note that to reduce the height with only vertical seam removal, we can transpose the image, run the program as normal, and then transpose it back.
