The Scholars' Avenue

“Okay, well, Charles, you are a mathematician, you’re always looking for the elegant solution. Human behavior is rarely, if ever, elegant. The universe is full of these odd bumps and twists. You know, perhaps you need to make your equation less elegant, more complicated; less precise, more descriptive. It’s not going to be as pretty, but it might work a little bit better.” – Larry Fleinhardt, in “Numb3rs”

What is pattern? To the businessman, a plot of the SENSEX is a pattern in the forthcoming share prices. To a mathematician, the same plot is a part of a polynomial curve.

To an artist, the plot is the representation of lightning or plain strokes on white. Consider a case, when you are given an image and told to point out the portions you find important. It is obvious that different people will consider different parts of the image to be important. On an average though, most persons in the survey will have at least one portion in common.

Input Image

Say for example, the image contains Bill Gates in it; to most people who know Bill Gates, that portion of the image is important. In other words, these persons will consider the image to have lost a defining characteristic if Bill Gates is say, distorted in or completely deleted from the image. To identify these common portions of importance in an image is an intriguing field of research known as Pattern Recognition in Image Processing .

Unfortunately, common processes like image resizing (making an image smaller or larger) and image compression (example, changing an image from .bmp to .jpg format to save on space), are bound to distort poor Bill Gates.

Resizing by scaling

If you change the image size of 300*500 to 300*300 using scaling in Windows Paint Brush, Bill Gates will look a lot thinner. A couple of scientists in Israel (Avidan and Shamir) recently invented an algorithm which can miraculously protect these important portions of the image while reducing or increasing its size. They named this algorithm Seam Carving.

Seam Carving for Content Aware Image Resizing

Avidan and Shamir came up with this brilliant idea that using an energy function one can more or less identify the important portions of the image. An image is represented as an array of pixels each of which has a position on the image and an intensity value between 0 and 255 for the 3 basic colours; red, blue and green (RGB). Simple observation says that more the difference in these intensity values for abut pixels, more likely is an observer to notice that portion of the image. In other words, you recognize sudden changes in color more than smooth changes in color. This can be represented as a simple difference of the intensity values (known as the energy function of the image).

Resizing by seam carving

When an image is subject to seam carving, a least energy path from top to bottom is removed, instead of just cutting a column. This will ensure that the least noticeable connected path is removed, and not the least energy column. When you remove this connected path, the important objects (assuming that energy is best metric to define pattern) are retained in the image.

Relevant Research in IIT Kharagpur

A team of five 4^th year undergraduate E&ECE students, with guidance from Dr. Sudhirkumar Barai (Associate Professor in Civil Engineering) have extended this idea of seam carving to a more general case. They assumed that energy is not the only metric to define the content and pattern in the image. Using tools that they learnt in the course by Dr. Barai (Soft computing Tools in Engineering), the team developed a fuzzy logic and neural network based image processor that could vaguely detect human beings in an image. Fuzzy logic and neural networks are learning algorithms that try to imitate the human brain and perception.

Resizing by seam carving after softcomputing based pattern recognition

Since pattern is very subjective and differs from person to person, emulating the same to detect important portions in an image using these tools, will give a better idea as to which areas in the image need more care during the resizing process.

The fuzzy logic tool tries to break up an image into rough portions known as segments (say, an image with a tree, grass and sky will have 3 segments). The neural network is then tuned to detect human features such as skin color in the image. When these two images (the outputs of the segmented image and the output of the neural network) are overlapped, the merged image gives a vague idea about where human beings may be present in the image. The results of this new method also show that like humans other important objects can also be similarly detected. The next step is to take the energy function, originally derived for seam carving, and add some extra energy to the portions of the image identified to have higher content by the soft computing methods, i.e., add some extra weights to human beings detected in the image. This will ensure that these portions are skipped when the least energy path is calculated and removed. The results were automatically improved over seam carving and normal methods like scaling. In the example shown, the energy image of an input with a man shows very little content on the man. Resizing methods such as scaling and seam carving therefore only distort his portion of the image, as shown. When the energy of the man is increased using the soft computing tools, he is protected from distortions during the resizing process. The result after image resizing by 50 seams shows little distortion.

Application and Future Prospects

The above method was published in a paper at the proceedings of the 2008 IEEE Conference on Softcomputing in Industrial Applications. There exist many applications. Remote areas requiring quick image processing of photos with humans (criminal, medical etc.), may require to transfer original images over low bandwidth connections. Such image resizing methods will help in retaining pattern while simultaneously enabling size reduction.

The method may also be extended to videos, by considering planes in a space-time coordinate system as described Avidan and Shamir in a recent paper. Details on the original papers can be found in Youtube:

Original Seam carving Paper: http://in.youtube.com/watch?v=6NcIJXTlugc

Seam carving for Videos: http://in.youtube.com/watch?v=AJtE8afwJEg&feature=related

More information and full paper on the method by IIT Kharagpur students:

http://sushilsubramanian.googlepages.com/publications.html

Team Members:

Sushil Subramanian (sushilsub@gmail.com)

Kundan Kumar (kundanjaiswal2002@gmail.com)

Bibhu Prasad Mishra (bibhumi1@gmail.com)

Animesh Banerjee (animesh121@gmail.com)

Debdutta Bhattacharya (debduttaiit@gmail.com)

For more information, download our Oct 22, 2008 issue.