After my post about the various content-aware image resizing projects I couldn't resist to take a closer look at Joa Ebert's ImageResizing class and take him on his word "If you can improve something do not be shy and post it". I just love code optimizing and saw several points to attack.

First I replaced the loop that moved the pixels via getPixel()/setPixel() by a displacementMap filter. The additional benefit of this is that I can use the same displacement map on the grayscale map which is used for the energy calculation so it just needs to get calculated once. It is even possible to apply it to the energy map, too but that map should only be used for a few carves and then get recalculated. Otherwise artifacts will show up quickly.

Another part I changed is the energy function itself. I'm not sure if that improves the speed, but I think it improves the seam selection quality. Instead of a convolution filter I blur the image first and then draw() it onto itself offset by a few pixels with difference mode. The idea behind this is that this will keep strong edges but does not emphasize noise and small patterns as much.

Here is the optimized ImageResizing AS source. And here's a demo of the optimized version:

Click on it to reset it and press any key (whilst it has the focus) to switch between horizontal and vertical shrinking.

For comparison check out the original version here.

The longest time is spend in the search for the seam with the lowest energy. So that's where the most optimization can be done. And indeed there were several easy victims to be found:

This is the original part of the inner loop where a seam gets built - it works by looking at the current pixel, checking its three neighbors to the right and then walking to the one of the three with the lowest energy. For this demonstration I have condensed the code a bit and removed the checks for vertical swipes:


for ( var p: int = 1; p < end; p++ )
{
point = point.next = new SeamPoint;
energy = energyMap.getPixel( o, p - 1 ) & 0xff;

e0 = energyMap.getPixel( o - 1, p ) & 0xff;
e1 = energyMap.getPixel( o , p ) & 0xff;
e2 = energyMap.getPixel( o + 1, p ) & 0xff;

d0 = Math.abs( energy - e0 );
d1 = Math.abs( energy - e1 );
d2 = Math.abs( energy - e2 );

min = Math.min( d0, d1, d2 );

if ( min == d0 ) o--;
else if ( min == d2 ) o++;

if ( o < 0 ) o = 0;
if ( o == endO ) o = endO - 1;

point.x = o;
point.y = p;

differenceTotal += min;
}

_energy = ( differenceTotal / end ) / 255;


The first thing that falls into my eye is that it is not necessary to read the "energy " pixel each time anew. We have that information already because it one of the three neighbors. So let's move that outside the loop - voilá - one getPixel less.


energy = energyMap.getPixel( o, 0 ) & 0xff;

for ( var p: int = 1; p < end; p++ )
{
point = point.next = new SeamPoint;

e0 = energyMap.getPixel( o - 1, p ) & 0xff;
e1 = energyMap.getPixel( o , p ) & 0xff;
e2 = energyMap.getPixel( o + 1, p ) & 0xff;

d0 = Math.abs( energy - e0 );
d1 = Math.abs( energy - e1 );
d2 = Math.abs( energy - e2 );

min = Math.min( d0, d1, d2 );

if ( min == d0 ) {
o--;
energy = e0;
} else if ( min == d2 ) {
o++;
energy = e2;
} else {
energy = e1
}

if ( o < 0 ) o = 0;
if ( o == endO ) o = endO - 1;

point.x = o;
point.y = p;

differenceTotal += min;
}

_energy = ( differenceTotal / end ) / 255;


The next thing is those Math.abs(). Whenever I see a Math.XY I look for ways to replace them with something faster. Ideally with bit arithmetics. And indeed there is a nice alternative possible here. All the pixels we read will be in the range of 0-255 aka one byte. And what we are calculating is the absolute difference between two bytes. This is a case for the XOR operator ^.

This:


d0 = Math.abs( energy - e0 );
d1 = Math.abs( energy - e1 );
d2 = Math.abs( energy - e2 );


becomes this:


d0 = energy ^ e0;
d1 = energy ^ e1;
d2 = energy ^ e2;


But there is another Math in here - Math.min( d0, d1, d2 ). Well of course this looks very nice and clean, but by making it a bit less nice and clean we can speed it up considerably:


energy = energyMap.getPixel( o, 0 ) & 0xff;

for ( var p: int = 1; p < end; p++ )
{
point = point.next = new SeamPoint;

e0 = energyMap.getPixel( o - 1, p ) & 0xff;
e1 = energyMap.getPixel( o , p ) & 0xff;
e2 = energyMap.getPixel( o + 1, p ) & 0xff;

d0 = energy ^ e0;
d1 = energy ^ e1;
d2 = energy ^ e2;

if ( d0 < d1 )
{
if ( d0 < d2 )
{
o--;
energy = e0;
if ( o < 0 ) o = 0;
min = d0;
} else {
o++;
energy = e2;
if ( o > endO ) o = endO ;
min = d2;
}
} else {
if ( d1 <= d2 )
{
energy = e1;
min = d1;
} else {
o++;
energy = e2;
if ( o > endO ) o = endO;
min = d2;
}
}

point.x = o;
point.y = p;

differenceTotal += min;
}

_energy = ( differenceTotal / end ) / 255;


There are some minor cleanups. For example by not creating a grayscale energy map but rather just storing the energy in the blue channel I can get rid of the &ff after the getPixels(). For the energy calculation it is also not necessary to normalize it - so the division at the end can go. One issue I had was with the border pixels - in the original implementation those non-existing pixels were simply read - Flash will return 0 in that case. I think that's not ideal so I made those pixels very expensive instead by adding 0x100 to them:


e0 = o > 0 ? energyMap.getPixel( o - 1, p ) : 0x100 | energy;
e1 = energyMap.getPixel( o, p );
e2 = o < endO ? energyMap.getPixel( o + 1, p ) : 0x100 | energy;


One very important optimization though is simply not not calculate values that are not needed. In our case we don't need to keep following a seam if it is more energy expensive than the best previously found. So by letting the seam finder routine know what is the best level yet it can stop searching once it is worse than that.


_energy += min;
if (_energy> bestEnergy)
{
_energy = Number.MAX_VALUE;
return;
}


So putting it all together it looks like this:


_energy = 0;
energy = energyMap.getPixel( o, 0 ) & 0xff;

for ( var p: int = 1; p < end; p++ )
{
e0 = o > 0 ? energyMap.getPixel( o - 1, p ) : 0x100 | energy;
e1 = energyMap.getPixel( o, p );
e2 = o < endO ? energyMap.getPixel( o + 1, p ) : 0x100 | energy;

d0 = energy ^ e0;
d1 = energy ^ e1;
d2 = energy ^ e2;

if ( d0 < d1 )
{
if ( d0 < d2 )
{
o--;
energy = e0;
if ( o < 0 ) o = 0;
min = d0;
} else {
o++;
energy = e2;
if ( o > endO ) o = endO ;
min = d2;
}
} else {
if ( d1 <= d2 )
{
energy = e1;
min = d1;
} else {
o++;
energy = e2;
if ( o > endO ) o = endO;
min = d2;
}
}

point.x = o;
point.y = p;

_energy += min;
if (_energy> bestEnergy)
{
_energy = Number.MAX_VALUE;
return;
}
}


I have still some ideas for possible improvements and I'm closely working together with Joa on this. The next step is to grow images. And of course in the end the whole thing has to be packaged and documented properly so it can be used conveniently.