gd permet aussi de colorier les point un par un, donc même avec une image en dégradé, ca doit être possible. Au pire, même si gd ne permet pas de travailler directement piwxel par pixel, il permet de bosser sur des rectangles donc suffit d'en prendre un de 1 pixel par 1 pixel.
Par contre, je promets rien pour la rapidité.