finding the best match for an image inside a shape

[klepthys]

I'm trying to work around a quite complex problem using imagemagick.

I have sets of images that can have any shape on black background. https://dl.dropboxusercontent.com/u/282 ... -00001.png

My goal is to find how to best resize those images to be enclosed in simple shapes.

Furthermore, I need the operation to be consistent over every image in the set : The same transform must be applied to every image in the same set (ie. a smaller image should appear smaller after transform).

Here is a working example for a triangle :
https://dl.dropboxusercontent.com/u/282 ... iangle.png


convert -resize 100% triangle.png -|composite -compose Dst_in -gravity South - "input.png" - | compare -metric AE -fuzz 15% - "input.png" /dev/null'

By varying the resize parameter, i'm able to determine the best size. Then I take the max found size over the full set and apply this following command :


convert -resize ${resize_value}% 'triangle.png -|composite -compose Atop -gravity South input.png - - |convert png:- \
-trim +repage -background black \
+' -gravity South'
+' -extent ${output_width}x${output_height}


This script does work, but it's quite long to compute.

However, my main problem isn't time : it's other shapes where it's not working. For example this one : https://dl.dropboxusercontent.com/u/282 ... iamond.png

The reason is obvious : I don't dynamically position my mask.

I can't find a way to make it work. One solution would be to try "every" position to check best match and iterate over this but process time would be enormous.

[snibgo]

Correct me if I am wrong: you have some shapes, all on black backgrounds. You want to know the maximum resize factor such that all the shapes, when resized with that same factor, fit in some other shape. The transformation is resize ONLY, and does not include rotation or translation. Is that correct?

If so, then I would start by making a super-shape, that is the union of all the shapes to be tested. Find the resize for this, and that is your answer.

This is a 1-D search, and binary chop would be useful.

[klepthys]

Your idea of a supershape is indeed a good one. I was in fact only checking for greater scale for each images, which I think should take (approx. ) the same time on best case (like, first image is the largest), but your method should be much faster with slow varying shapes.

This is a 1-D search, and binary chop would be useful.

I don't understand. What is binary chop?

[snibgo]

See http://en.wikipedia.org/wiki/Binary_search_algorithm