Hi
I've never had that exact problem, but I've done some obscure image processing with PHP before. First, you cannot do much with gdlib. PHP is not good for pixel wise processing, so we need tools. Try this:
http://www.imagemagick.org/script/index.php
My advice is first to try to solve the problem on the command line. If it scales badly executing commands in the script, there is a PHP module. On my system it's called "php4-imagick".
Warning:
ImageMagick is progressing fast. So it tends to being incompatible with old versions. They forked into "GraphicsMagick" for that reason.