[cosmie]

I remember reading up on that a while back, but never actually did anything with it. Care to benchmark a normal resize to the content aware scaling? It'd be interesting to see the performance hit you'd take to dynamically resize a large number of images.

On a side note, GraphicsMagick, a fork of ImageMagick and used by Flickr and Etsy, is a bit quicker.

[gibbonweb]

WUT!!! This would be absolutely awesome for generating mid-size square thumbnails of arbitrary images... I AM SO GOING TO USE THIS. Thanks for the info!

[Kyek]

Stuff like this kills me. I want to use it SO BAD, but I have no reason to. So I start reeling for projects I could do that would use it, then I realize *I have no time for these goddamned projects*.

Daniel15 is ruining my life D:

[arronhunt]

Kyek, on 16 November 2011 - 11:14 AM, said:

Stuff like this kills me. I want to use it SO BAD, but I have no reason to. So I start reeling for projects I could do that would use it, then I realize *I have no time for these goddamned projects*.

Story of my life.

This is pretty cool though, someone should code up or link to a live example.

[Koen]

Found some amazing videos on the subject (yes, the first 2 hits on youtube, but they're great!)

[soulcyon]

D: just ingenius... how do they make these algorithms?

[gibbonweb]

soulcyon, on 16 November 2011 - 02:06 PM, said:

D: just ingenius... how do they make these algorithms?

normally you do this by writing an "energy function" for the image and writing an algorithm which looks for a "way through the image with the lowest energy waste possible".
The "energy function" is typically a function of the image which is high in areas of high contrast changes (norm of the gradient, image laplacian) and low in "blurry" areas (where the gradient is near zero).
The algorithm will then traverse the image, let's say vertically along the center of the image. It counts how much energy is "spent" by summing up all values of the energy function over the pixels it is traversing. then, it loops over neighboring paths to see if there is a "better", i.e. "less energy consuming" way of traversing the image. By repeating this often enough, you'll end up with a path which is crossing the image in mostly "blurry" areas. Assuming you did this vertically, you can delete all of the concerned pixels and you'll end up with an image which is one pixel less wide. Then you repeat until you have reached the desired size.
This answers the performance question from above: This method is MUCH less performant than a simple cropping/rescaling. Obviously.

[soulcyon]

Instead of traversing via rows or columns, would it be more accurate to traverse over perimeter? Or traverse over a certain path that expands/contracts to the boundaries of the image? Wouldn't doing only vertical/horizontal traversal affect a certain affinity of pixels because of the direction you traversed? I would assume that doing a "dynamic" traversal will result in a more fluid movement - something like a outline or perimeter.

[gibbonweb]

PS: This is described here with a few nice images: http://www.cs.cmu.ed...j2/www/wwedler/

Quote

Assigning energy to each pixel

Each pixel has energy based on the sum of the x and y derivatives at that point. The derivatives are computed by taking the finite divided difference between the pixel and its neighbors. The energies from each color channel are computed and then summed for the overall energy of the pixel.

This is the easiest way to write an energy function, however:

Quote

Finding an appropriate energy function can drastically affect the results. One problem with this energy function is that it does not take into account vertical lines in the image. A minimum path may not cross through a vertical line directly, but if part of the path is on one side of a line and part of the path is on the other, then the end result may be a skew in the vertical line.

soulcyon, on 16 November 2011 - 02:35 PM, said:

Instead of traversing via rows or columns, would it be more accurate to traverse over perimeter? Or traverse over a certain path that expands/contracts to the boundaries of the image? I would assume doing a row-only or column-only will be choppy or incorrect in images without vertical/horizontal alignment.

yep, see my link for this, they talk about that problem also. the trick is to write an "intelligent" energy function which will try to avoid "important" features of the image at all cost. It IS complicated and still an active field of research

[Kyek]

Edit: Oh shit, everyone replied while I was typing D: Type slower D:

soulcyon, on 16 November 2011 - 02:06 PM, said:

D: just ingenius... how do they make these algorithms?

I haven't gone through the whitepaper of how the algorithm works, but I'm going to guess the meat of it is nothing more than a simple recursive function. I'll use a maze as my example:



How would you write a program to solve that? Here's how I'd do it: This maze is on a grid, like someone took graph paper and just blacked out some of the lines for walls. If you step into the left entrance, for example, your legal moves would be UP and RIGHT. If you stepped right, your legal moves would be LEFT and RIGHT. Only, in this case, we're going to eliminate "LEFT" as a legal move since we just came from there.

Make sense? Using that thinking, this maze can be solved by one function:

const UP = 0;
const RIGHT = 1;
const DOWN = 2;
const LEFT = 3;

// Maze is an object that knows what the legal moves are
// for every position, and where the exit is.
// It also tracks where we're "standing" and where we've
// been.
function solveMaze($maze) {
    if ($maze->solved())
        return $maze->getPath();
    for ($i = 0; $i < 4; $i++) {
        if (!$maze->directionBlocked($i) && !$maze->beenThereBefore($i)) {
            $success = solveMaze($maze->stepTo($i));
            if ($success)
                return $success;
        }
    }
    return false;
}

That's it. Not including the explanatory constants and comments, that's all of about 10 lines. Basically what's going on is, that function has no effing idea how to solve a maze. All it knows how to do is check to see if this space is the exit. If not, it will attempt moving to an empty space that 1) is not blocked, and 2) it's never been in before, and then it calls itself to start the whole damn process over again. So in all of 10 lines of code, we're attempting every path from a given start point to a given end point, and only returning the one that actually works.

Now let's think of how we might use the same concept to find a seam in this image. We're only concerned with one type of path: any path that starts along one edge of the picture, ends along the opposite edge of the picture, and doesn't intersect any areas of high "energy".

So step one is going to have nothing to do with what we just did. Step one is going to be running a filter similar to "Find Edges" in photoshop. If you were writing it yourself, you'd probably look at each pixel (or a small box of pixels) and determine if the pixels/units surrounding it are within a similar color range, or if they're drastically different. If they're drastically different, chances are that you're on the edge of a new element in the photograph, and you mark that section as being high "energy". And you'd probably put a value with that. If you're going from stark white to stark black, that's be a really really really high energy. If you're going from a dark green to a dark blue, that'd be a lower energy. If you're going from one color to the exact same color, that's no energy. You run over every pixel or group of pixels in the photo, and construct a "grid". If every pixel were a space on a piece of graph paper, each line would have your "energy" level on it, defining how big the difference is between those blocks.

...so... piece of graph paper ... an object that describes which lines can and can't be crossed ... is this sounding familiar to you? ;-)

We can use that exact friggin same algorithm to find a "seam", with just a few really really basic tweaks. Obviously, if we're drawing a seam from left to right, you wouldn't want the algorithm to be able to move right, then up, then left-- so you'd just need to bar it from moving toward the edge you started on. From there, you just need to try going in your remaining three directions. Your first version might always choose to move along the path of least resistance -- cross the "line" with the least amount of energy on it. Your second version might try going in all of the directions, even if one path makes you cross more energy than another, because the path as a whole might result in less energy. Your third version might be a combination of the two, defining a range of energy levels that are OK to cross, but not attempting to cross any really significant energy lines. The point is, no matter how you roll it, the function should add up each amount of "energy" it crossed and return the lowest energy path it could find.

Since our function requires that we give it a starting point, we'd just try it with all the pixels (or every few pixels) across one edge of the image. Take the path that had the least amount of energy, and bam. You, sir, just found a seam of pixels that you can safely delete from this image.

Run that algorithm repeatedly until the image is resized to where you want it. Done. You could write an acceptable version of sucker in a couple days, after some research on the best way to manipulate image data.

This would be very very slow, of course -- no doubt these guys found a way to optimize it way more than what I'm suggesting. But I'd bet a lot of money that it's the same basic logic.

[Daniel15]

Quote

Found some amazing videos on the subject

The first video is by the guy that wrote the paper on this algorithm. His algorithm is the one used in liblqr (the library used by GIMP and ImageMagick) and in Photoshop. He must be quite famous now

Quote

On a side note, GraphicsMagick, a fork of ImageMagick and used by Flickr and Etsy, is a bit quicker.

Interesting, I wonder if PHP supports it. I couldn't find a working PHP ImageMagick DLL for Windows so I switched to my Ubuntu machine and just did an "apt-get install php5-imagick"

Quote

Care to benchmark a normal resize to the content aware scaling?

Great idea, will try to do when I have some more free time. It'll be interesting to benchmark this against the high quality (but slow-ish) resize interpolators like Lanczos. Liquid resizing would have to do a LOT more work, so I can imagine it'd be slower. But I wonder if the work could be done in multiple threads in the C/C++ code. Then it might not be very slow at all.

Quote

This would be very very slow, of course -- no doubt these guys found a way to optimize it way more than what I'm suggesting.

Take a look at the paper, it describes the algorithm: http://www.faculty.i...imret/imret.pdf (PDF, 19 MB)

[cosmie]

gibbonweb, on 16 November 2011 - 02:24 PM, said:

This answers the performance question from above: This method is MUCH less performant than a simple cropping/rescaling. Obviously.

Cropping is not rescaling. And there are several different algorithms that are used for rescaling an image. Obviously content-aware scaling is going to be more performance intensive than dumb scaling, I mentioned benchmarking to see how significant the difference was, not to see if there was one.

Daniel15, on 16 November 2011 - 05:00 PM, said:

Interesting, I wonder if PHP supports it. I couldn't find a working PHP ImageMagick DLL for Windows so I switched to my Ubuntu machine and just did an "apt-get install php5-imagick"

It does.
And it's just as easy to install

[Daniel15]

Quote

It does.
And it's just as easy to install

Looks like it's in beta though, so not sure if I'd want to run it on a live server. That, and I can't find the documentation.

[tao]

Very cool, great find. I remember reading about this technique back when Photoshop was adding it. I agree with your consensus though, might not suggest using it in production just yet, but definitely worth looking into and will be great once its stable.