A look into seam carving
Good day readers,
I’ve been thinking about algorithms recently due to some reading from “The Pattern on the Stone.” It’s interesting how algorithms make logical ways of doing a task. It’s really cool how it can be applied to theoretically any programming language. It’s not operating specific, not programming language specific, not hardware specific. It’s how it’s done on a more basic logical level. Even technically algorithms can be done manually without a computer (albeit most would be a little slow, tedious, and boring). The book describes what an algorithm is this way. “an algorithm is a fail-safe procedure, guaranteed to achieve a specific goal.” (2) I have been doing a bit of research on various algorithms in studying for this post and happened upon this algorithm. It’s called seam carving. Before delving into what it does, I’ll present the problem first. imagine you have an image that will be displayed on many different screens with many different resolutions and aspect ratios: on a webpage per say. It needs to be dynamically resized. We need an algorithm for that. There is something about algorithms though, like my book says “Usually, many algorithms can compute the same result… different algorithms require different amounts of time to complete a given task. Certain algorithms might offer other kinds of advantages.” (2) We’ll take a look at those advantages with an example of a panorama I took at a family vacation. With this resizing thing, how should you go about resizing? If you resize the image keeping aspect ratio, you could end up with something like this.
 |
| Panorama screenshot on my phone |
If you resize it not preserving the aspect ratio, you could end up with something like this.
 |
| Aspect ratio not held well |
The first one is just too small, the second one puts everything out of proportion.
But here is the image I did some seam carving on. (notice the forest is denser)
But here is the image I did some seam carving on. (notice the forest is denser)
 |
| Seam carving is awesome |
With this algorithm I marked my family to be preserved. And for being a panoramic image, it did a pretty good job of keeping things not as squished as the first example of normal resizing.
Wikipedia has a good summery of what it is. “Seam carving (or liquid rescaling) is an algorithm for content-aware image resizing, developed by Shai Avidan, of Mitsubishi Electric Research Laboratories (MERL), and Ariel Shamir, of the Interdisciplinary Center and MERL. It functions by establishing a number of seams (paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs.” (3)
This is really cool! It allows an image to be distributed across a network without any worry about it being out of proportion or too small on one device.
But how does this work? What makes it tick?
From there, a line produced going from one side of the image (whether that’s top, bottom, right or left) and going to the opposite side. It follows the path of least resistance or the least energy used)
 |
| Seam lines - Wikipedia - (3) |
It does this going row by row, or column by column following one of 3 pixels below or to the side. This line is then removed from the image, and this process is repeated until the desired size is achieved.  |
| Seam lines cut - Wikipedia - (3) |
algorithm working. Makes it easier to understand.
Bibliography
1. Hillis, W. Daniel. The Pattern on the Stone: The Simple Ideas That Make Computers Work. New York: Basic, 1998. Print. Pg. 78, 79
2. Avidan, Shai, and Ariel Shamir. "Seam Carving for Content-Aware Image Resizing." Ariel Shamir. N.p., n.d. Web. 17 Sept. 2016. <http://www.faculty.idc.ac.il/ARIK/site/seam-carve.asp>..
3. "Seam Carving." Wikipedia. Wikimedia Foundation, n.d. Web. 17 Sept. 2016. <https://en.wikipedia.org/wiki/Seam_carving>.
Comments
Post a Comment