Liquid Resize & Seam Carving

[anthony]

It has been suggested that IM should provide an operator to allow you to do Liquid Resize, also known as Seam Carving...

How hard would it be to add liquid resizing/seam carving to IM? It would be a very cool addition to the library, though I understand that protection/deletion would have to be done with masks.

You should have a look at this. It is very interesting. It is resizing by simple pixel removal but in a very special and interesting way, so as to try an preserve image content defined either by 'energy' functions, or adjusted by secondary masks (user or program generated)

YouTube Video Demo: http://www.youtube.com/watch?v=c-SSu3tJ3ns
PDF document: http://www.faculty.idc.ac.il/arik/imret.pdf
Wikipedia (source links): http://en.wikipedia.org/wiki/Seam_carving

The problem is not so much adding this to IM. IM would be very capable of doing this type of thing. It is getting programmers with some time to implement it.

Also as it is just direct pixel removal a lot of other aspects of resizing (filtering) is not needed, I am sure that some local filtering could also improve overall results for a higher quality IM output. An optional second image can be used to add positive / negative weights, perhaps with a user generated energy function, or face reconition masking.

I added it to the TO-DO list. I have about 2 months of work (Wizards toolkit, textual data mining, started writing a book) before I have more than a few minutes of free time.

In fact some of the sub-functions would be useful things in and of themselves.

• the Autocrop method, that is mentioned at the start of the PDF paper. That is find the crop position of a specific size basied on maximizing the energy function.
• The generation of some of the various energy functions mentioned. (preservation masks)
• The generation of a the list of seams to be removed in sequence from the preservation mask (generated from combining a user selection with the energy function) as a gray-scale image that can be thresholded, based on the number of seams to be removed.
• A routine to delete a boolean mask of pixels (the thresholded seams list image) by shifting rows left or columns up. Assuming a equal number of pixels is removed from every row/column to preserve the rectangular image outline.

These sub-functions are in and of themselves useful not just for seam carving or liquid resizing, but as general processes in there own right.

One use that was not shown was the use of seam carving to generate 'fold lines' in an image animation. The YouTube Video uses something like that at the begining and end of the video when resizing the title image. It can also be used for the removal of interline space within a text file.

Also something that has not been mentioned was how the algorithm should remove seams that all have about the same minimal energy! Or methods that try to separate the seams so you don't end up remove a stack of seams that are all next to each other. This is something I noticed happening in some of the incremental demonstrations.

On thing I would like to try is to use the seam removal (pixel removal mask) to create a distortion map, rather than just direct pixel removal. That of course means access to the intermediate image processing stages. Of source the resulting image should be better as it will be properly smoothed from seam artifacts, but it will not be much good for object removal, not unless you did that in two stages.

[DeadlyDad]

A Google search reveals more than 38,000 pages talking about it, including a GIMP plugin!

One thing that occurred to me is that, to get a more natural flow when removing pixels, perhaps they should be 'leeched' into surrounding pixels before removing them. Setting an averaging radius & profile (i.e. linear/sine/log/etc.) would be handy, too. Another option would be to average the (X) pixels on either side of the seam.

[DeadlyDad]

-----8<-----
Also something that has not been mentioned was how the algorithm should remove seams that all have about the same minimal energy! Or methods that try to separate the seams so you don't end up remove a stack of seams that are all next to each other. This is something I noticed happening in some of the incremental demonstrations.
-----8<-----

Hmmmmm..... How about 'minimum pixel separation' & 'minimum energy difference' parameters, to space the seams out. (At least until none are left that aren't below the minimum, which is then decremented by one, and the whole process continues.) You would take the energy of the current seam, find the next seam according to the MED value, then, using the MPS value, travel down the two seams, checking for sufficient separation. As soon as you get two pixels that are too close, abandon that seam and pick the next one. For example, if it the MED was set to '3', and the seams had energies of 1..9, the (untested for MPS) order would be 1,4,7,2,5,8,3,6,9. As (I imagine) the adjacent seams that would be the least 'interesting' would have energies that would be relatively similar, this 'seek the lowest energy that isn't too close to the last energy or seam' method wouldn't effect the more 'interesting' parts of the image until not long before they would with MED & MPS values of '0'. (i.e. the current method)

[anthony]

This was one reason I would like to get the seam removal mask to generate a distortion map (LUT) so that pixels aren't actually removed just compressed A large group of pixels would just cause that area to compress more. The amount of compression spread would be just a blur of the distortion map. But I would need access to the seam removal mask to do this.

[DeadlyDad]

This was one reason I would like to get the seam removal mask to generate a distortion map (LUT) so that pixels aren't actually removed just compressed A large group of pixels would just cause that area to compress more. The amount of compression spread would be just a blur of the distortion map. But I would need access to the seam removal mask to do this.

I think that I'm getting where you are going with this; basically, the more 'interesting' a pixel is, the more it is shifted left/up, and the more weight it has when it is averaged with the current value of the pixel it is being moved to. For example a pixel with a weight of 'FF' would simply replace any pixel that it ended up 'on top of' (i.e. protected), while one with a weight of '00' wouldn't be moved at all (i.e. deleted). Is that a fairly accurate assessment?

[anthony]

Not quite.

What I'd like to do is use the seams mask to determine the areas where you want the image to be compressed the most to resize it. That is something between normal scaling to resize, and seam carving to resize, producing a distorted image so that the uninteresting areas get compressed more (not actually removed) than the areas of interest.

Basically a variation of seam carving that should produce a smoother and better looking result than just direct removal of pixels.

Something like this in IM Examples...

Though only using compression when shrinking and expandsion when enlarging to resize the original image. The above image uses both, to demonstrate a displacement mapping technique, not to resize the image.

I invisiage using the seam carving mask to generate a smoothed Distortion map to resize the original image. This would become even better when Distortion Maps are properly incorperated into IM to make use of the new underlying Resampling methods, that is now available.

Of course this is a side issue or variation to the normal Liquide Resize technique.

[DeadlyDad]

Okay. I think that I have a clearer understanding of what you are getting at. The problem comes in because you are using Absolute Distortion LUT Maps generated by a single, simple function, when this situation calls for Relative Distortion LUT Maps generated on-the-fly. We don't know precisely where a particular pixel is going to end up while seaming, but we can know how far left/right/up/down to move it and how much the size has to change at each step, so each pixel needs to have two signed integers (X & Y) for position, and two signed integers (X & Y) for size attached to it. Every time a seam is chosen for removal, the offset of every pixel to the right/down is decreased, and the size of the pixels in the seam is set to zero. Every time a seam is chosen for expansion, the offset of every pixel to the right/down is increased, and the size of every pixel in the seam is increased in the appropriate direction, . (Note: This is completely separate from deciding the seam paths. This is strictly to create a distortion map. Protection & deletion issues won't change the distortion map, as the path-finding algorithm will automatically deal with them. All pixels within a protected area will never have their offsets changed except as a bulk 'move everything left/right/up/down', so they will stay in the same position relative to each other. All pixels within a deletion area will have pixels to the right/down moved into their location (and the size increased to fill in the empty spot if the size of the picture isn't being reduced) over and over again until they are all gone.) Once the relative size & position distortion maps are complete, they can be converted in to absolute ones, then be applied like any others.

Does that make sense?

[anthony]

Okay. I think that I have a clearer understanding of what you are getting at. The problem comes in because you are using Absolute Distortion LUT Maps generated by a single, simple function, when this situation calls for Relative Distortion LUT Maps generated on-the-fly.

Sure relative distortion LUT's are useful as they can extend beyond the bounds of the original image, as as such can handle edge effects via the -virtual-pixel setting. And while Absolute Distortion maps are currently only available via a slow DIY (-fx) methods (see Absolute Distortion LUTs) but even that will become available.

We don't know precisely where a particular pixel is going to end up while seaming

Actually we do. That is what the Seam Mask provides. Picture this....

Take a gradient image which is the null absolute distortion map. Use the seam mask from the original image to remove the seams from the gradient image. Now the gradient image has the appropriate bits missing and represents the final size. If you apply this absolute distortion LUT to the original image you will get the normal seam carved image (if the quality is good enough for the image size, eg a Q16 or HDRI, floating point internal representation version of IM).

Now if you take that LUT and smooth it with a small blur you will get a warping form of seam carved image with the image being variably scaled to compress/expand unimportant parts and preserving the important content. Remember blurring a gradient should (with the correct handling for edge effects) leave a gradient unchanged, so the parts without any seam removals will be left unchanged.

When the smoothed seam carved gradient is used to distort the original image the result should be a LOT smoother and cleaner than direct seam carving, especially if a scaling resampling method is used (when distortion LUTs become built in) rather that the current unscale interpolated pixel lookup. But it will NOT just remove unwanted parts, only compress them.

Seam mask expandsion to warping, is simular, you just use the seams to expand the gradient image, before again smoothing it.

This however only works for absolute distortion LUT maps. You can not do this in relative LUTs, as you are resizing images. But that does not mean they can not be convert to a relative LUT. I worked out that conversion as a DIY operation in IM examples. See this