Another approach is to create your watermark on a transparent image of the same size (for simplicity) as the original. Ending with 2 images. Then you overlay those images using an appropriate blending mode which GD maybe has it built-in or create your own (warning: this example uses PHP's GD API which I am not sure is the same as that provided for Perl). To experiment with blending modes use gimp or photoshop if you own one and check layer modes

Another way similar to Fletch's is to sample a neighbourhood of original image's pixels around each of the watermark's non-transparent pixels. And pick the watermark pixel color (so no borders) to stand out using the color-wheel, there's a lot of theory about that and some simple equations to get "opposite" colors.

bw, bliako