PHP GD Anti-aliasing

gd_aa_test
 

I've been having a little "fun" lately writing some graphing/visualization code (mostly in SVG+JavaScript... more on that another day). I was thinking it would be cool to render some SVG paths using GD. I did this with a map of the country before, and it worked reasonably well. However, the glaring problem was a lack of anti-aliasing in the GD drawing output. There's some support through imageantialias(), but it is severely limited in practice. I want to send PNGs with alpha channels to the browser.

I scoured the web looking for ideas, and mostly found a lot of people worrying about very specific algorithms for arcs/ellipses and lines. Granted, these methods are probably memory- and speed-efficient. But, they don't solve the general problem. What if I have a rendering library that could generate all kinds of unknown geometry? What if the complexity of the geometry approaches a point where optimizing individual elements uses more resources than just filtering the entire image? It's not uncommon for a lot of vector geometry to be hidden behind other elements such that they require very little or no anti-aliasing to improve the image.

So, I decided to try a proof-of-concept myself. The idea is used in a lot of signal theory and 3D rendering techniques: oversampling. If you render more information than is needed, then allow a generic interpolation algorithm to reduce the amount of information available, you automatically get anti-aliased information in the output. When dealing with images, it works well to generate four times the number of pixels than is needed in the output. This is the lower bound of the Nyquist sampling theorem since we're dealing with information on two coordinate axes (2 x pixels + 2 x axes). The pixel interpolation algorithm used by GD's imagecopyresampled() appears to be happy with this amount of oversampling, and retains all the information in the oversampled image.

The image shown is my test output. I wanted to see how it worked with geometry that needs a lot of anti-aliasing to "smooth out," and a few elements that don't really benefit from a lot of anti-aliasing. This example actually renders 16 source pixels for every output pixel. So far, I'm pretty satisfied with the results.

The main issue with this technique is dialing in the "weight" of any stand-alone lines (edges without fills). When the oversampled image is scaled down, the lines will be reduced in thickness. To preserve the thickness, and ensure a good portion of completely solid pixels, I added a weighting factor that is multiplied with the oversampling coefficient. This gives the impression of "lighter" or "heavier" sub-pixel interpolation for stand-alone lines.

The numbers displayed on the image are the memory usage values at various points in the process. The middle number is the important one since that's how much memory is used while working with the oversampled image. It's obvious that on a crowded server that's starved for memory, the 16:1 oversampling would be pushing things. But, I hope whomever has the wherewithal to implement such a beast isn't generating every output image on the fly, and either rendering the images before they are served, or implementing some intermediate form of caching. Even then, if you stepped back to something more modest like an 8:1 oversampling, you'd be in pretty good shape for live rendering on a server with spare memory.

Download the test script.

<?php
/*****************************************************************************
    PHP/GD Antialiasing, Proof of Concept
    Zac Hester - 2011-06-28

    Just a small bit of code to see if it can be done, and what kind of
    memory overhead is needed to pull off an arbitrary, geometry-agnostic
    antialiasing that works with transparent images.
*****************************************************************************/

//Pretty-printing for memory sizes
function get_size($nbytes) {
    $i = 0; $units = array('B', 'kB', 'MB', 'GB', 'TB');
    while($nbytes >= 1024) { $nbytes /= 1024; ++$i; }
    return sprintf('%01.2f %s', $nbytes, $units[$i]);
}

//A few configurable (within limits) values
$tw = isset($_GET['w']) && ($_GET['w'] <= 640) ? intval($_GET['w'])   : 320;
$th = isset($_GET['h']) && ($_GET['h'] <= 640) ? intval($_GET['h'])   : 240;
$aa = isset($_GET['a']) && ($_GET['a'] <= 4)   ? intval($_GET['a'])   : 4;
$wf = isset($_GET['f']) && ($_GET['f'] <= 4 )  ? floatval($_GET['f']) : 0.75;

//The AA source is an over-sampled image
$aw = $tw * $aa;
$ah = $th * $aa;

$usage = array(memory_get_usage());

//Create the over-sampled image, and the final image
$im0 = imagecreatetruecolor($aw, $ah);
$im1 = imagecreatetruecolor($tw, $th);

//Configure both images to use alpha channels
imagealphablending($im0, false);
imagesavealpha($im0, true);
imagealphablending($im1, false);
imagesavealpha($im1, true);

//Set up colors and transparency
$color0 = imagecolorallocate($im0, 0, 0, 255);
$color1 = imagecolorallocate($im1, 0, 0, 255);
$trans0 = imagecolorallocatealpha($im0, 255, 255, 255, 127);
$trans1 = imagecolorallocatealpha($im1, 255, 255, 255, 127);

//Override the default backgrounds in both images
imagefilledrectangle($im0, 0, 0, $aw, $ah, $trans0);
imagefilledrectangle($im1, 0, 0, $tw, $th, $trans1);

//AA graphics
//Note: the weighting factor can be used to provide "heavier" and "lighter"
//  subpixel interpolation in the final image.
imagesetthickness($im0, ($aa*$wf));
//Note: imagearc() interprets a 360deg arc as an ellipse, and imageellipse()
//  has problems with imagesetthickness().
imagearc($im0, ($aw/4), ($ah/2), ($aw/3), ($aw/3), 0, 359.9, $color0);
imageline($im0, ($aw/8), ($ah/8), ($aw*3/8), ($ah*7/8), $color0);
imageline($im0, ($aw/8), ($ah*7/8), ($aw*3/8), ($ah/8), $color0);
imageline($im0, ($aw/8), ($ah/2), ($aw*3/8), ($ah/2), $color0);
imageline($im0, ($aw/4), ($ah/8), ($aw/4), ($ah*7/8), $color0);

//Downsize and interpolate to provide AA
imagecopyresampled($im1, $im0, 0, 0, 0, 0, $tw, $th, $aw, $ah);

$usage[] = memory_get_usage();

imagedestroy($im0);

//Non-AA graphics (for comparison)
imagearc($im1, ($tw*3/4), ($th/2), ($tw/3), ($tw/3), 0, 359.9, $color1);
imageline($im1, ($tw*5/8), ($th/8), ($tw*7/8), ($th*7/8), $color1);
imageline($im1, ($tw*5/8), ($th*7/8), ($tw*7/8), ($th/8), $color1);
imageline($im1, ($tw*5/8), ($th/2), ($tw*7/8), ($th/2), $color1);
imageline($im1, ($tw*3/4), ($th/8), ($tw*3/4), ($th*7/8), $color1);

$usage[] = memory_get_usage();

//Print memory usage information on the image
$str = implode(', ', array_map('get_size', $usage));
$fx = ($tw/2) - ((imagefontwidth(3) * strlen($str)) / 2);
imagestring($im1, 3, $fx, ($th-20), $str, $color1);

//Output the image
header('Content-Type: image/png');
imagepng($im1);
imagedestroy($im1);

?>