I know you are trying to do this in Perl, and on your own. However there is a very cheap Windows product that does what you are looking for @ QImage Pro. The site also has some limited technical resources that may be of interest to you and may help complete your task.

For $35.00 USD it was such a bargain I've never used anything else :)

Update: If you get anywhere with your solution I would be most interested in seeing the results. I do a ton of digital photo printing and I would be interested in what you code ends up looking like, as well as the algorithm you end up using. Looks like a cool project :)

"Nothing is sure but death and taxes" I say combine the two and its death to all taxes!