Legacy ImageMagick Discussions Archive

As part of a problem I was facing I had a collection of maps (about 30 where were extracted and cleaned up from a game)
For example, ...


These maps overlaped, and I wanted to find how they fitted together.

So I created a rough script
http://www.imagemagick.org/Usage/scripts/overlap.v1

Runing it with the above using produced 4 overlay results (all the same), which is the 'composite layering offset used' for the merge.
map_a3_fellesweden.png -page +-80+-32 map_a4_south_jungle.png -> "merged_001.png"
and results in this image



The script extracts 9 smaller sections (rather blindly) from each map and tries to find those sections in the other map. If the match is good enough, it calculates the offset between the two and layer merges the image to produce a composite.

The script is slow. Does not remember previous matches, and typically finds the same overlapping position multiple times. Also if the 'section' used for a specific search is very plain (that is it has a low energy or entropy) it may fail completely or fail to produce a good match. Also it does not handle multiple images (maps) very well, handle transparency well, or check how well the whole area of image overlap 'fits' together, or determine if it should overlay or underlay images relative to each other.

It is also not designed with 'real life images' or images with perspective distortions in mind, as you get with a panorama composite. but it is a start.

I am putting the script out for anyone else to 'play' with it, and perhaps improve it.

What improvements can you make?

Anthony,

Very interesting. I have not had time to review the script. But could you explain simply how you are able to do a compare on the two images when they overlap only a little? Do you pad out the first image to some large size first and then compare the enlarged first image with the smaller second image? Or are you doing something more clever to avoid the padding?

Fred

I set transparency to mid-grey (hopefully there is very little of that)
I extract a small section of one image, and do a sub-image compare against the second image. If the two find a match that is below a threshold, then merge the match offset with the offset from of the extracted section, and overlay the image (using the next available incrementing numbered filename).

Layers Merge is used so the offsets can be negative, and the resulting image will be large enough to hold both images completely. I don't have to worry about using an offset like +-30 as IM handles that now (thanks for the suggestion Fred)

9 sections (fixed in the script ) from both images against the other.. 18 attempts to find a match.

I am finding that once you get some images merged, then really only the sections from the smaller (next map to merge) should be used to find a matching location.

I wanted to make it merge multiple images into a much larger map, but find I have to check each merger one step at a time.

The sections used for search is extracted blindly. No check is made on if section has transparency, or a lack of 'energy' (like ocean) making it unsuitable as a good search. A couple of maps containing almost total ocean or lots of transparency, required manual placement into the larger composite via gimp

Small sections (5x5 pixels of a high energy areas) could be used to find more possible offsets at a much faster rate, but the list of posible matches would then need to be double checked using a larger area at just that specific location. That I have not done.

Nor is a check made for duplicate matches. The above found 4 matches at exactly the same offset using 2 sections from each image. Thuse produce 4 image that were essentaully exactly the same (2 with one image on top, and 2 with the other image on top.

Basically the script could use a LOT of improvement to both speed it up, prevent duplicate matches, and to discount false positives.

It a is VERY basic start point.

I extract a small section of one image, and do a sub-image compare against the second image. If the two find a match that is below a threshold, then merge the match offset with the offset from of the extracted section, and overlay the image (using the next available incrementing numbered filename).

Got it. Thanks. I was thinking in the wrong direction. Your solution makes sense.

Fred

P.S. I believe in some of the panoramic stitching sofware, they locate a number of high energy (entropy) subsections along the relevant side of the image and match each of them and take some kind of average to get the offsets. Your situations is a harder more 2-dimensional search, since you may not know which edge is needed for the match.

To eliminate patches with low entropy, I find the standard deviation and don't bother trying to find a match if SD < 1000/65535.

snibgo wrote:To eliminate patches with low entropy, I find the standard deviation and don't bother trying to find a match if SD < 1000/65535.

Sounds good I'll tray adding that.

Okay a little more work...

I extracted a 'high entropy' image from one of my maps above...
(channel image edges, masked with transparency and various erodes) -->

This should be a map of all appropriate 'centres', of a 9x9 squares (radius 4 squares), that contain no transparency, and which can be now be extracted as good sub-image searches.

Perhaps you can find a better 'entropy' map?

The problem now is getting a list of centres that are well separated. With preferences to corners and edges.
that is get the top left, bottom right, and so on. preferably without overlapping, though that can be acceptable
toward the end.

That is from the above I need to generate a maximally distributed list of points, starting with the edges.

Note that the image may not be square (due to the transparency which was minimal in this case) so specifically finding the 'corner' is not an appropriate solution.

Here's a standard deviation version of the entropy map, though I don't claim that it is better:
For finding the list of centres, I don't understand the criteria, but here's a possible approach:

First, find the entropy peaks, the lightest parts of the entropy map. This might be from the unthresholded map, or slightly blurred, or thresholded and then blurred. This last method will emphasise the corners.

From this peak map, find the brightest pixel. Then black out all pixels within a certain radius of that pixel, and find the next brightest pixel. Repeat until all pixels are black.

Incidentally, this process of finding the brightest pixel in an image is performed, using ImageMagick, with a sub-image search, and takes a very long time. It's faster to dump the image in text format and scan with a script, or massively faster still to dump the image in .gray format and scan with a compiled program.

Perhaps something could be added to ImageMagick to do this. Perhaps an escape "%[lightest]" that reports the lightest pixel, in the same format as the current txt output format.

Why would finding the highest peak find a corner?

Blurring will find the corners of a white line on black background, because there is a greater density of white at a corner. For example, if we draw the white outline of a square on a black background, and then blur it, the corners are lighter than the edges.

But the middle (beyond the blur radius) will be brighter still. That is why I queried it. It did not make sense to me.

Okay better edge 'entropy' method, whcih produces quite a clean result, was achieved using This can be followed by edge detection code such as or as per "snibgo" I also found it is better applied to all channels at once, but then the color channels gray scaled but using "multiplys of negated images" (IE -compose -screen) using... and then thresholded (10% for standard deviation or segment-median)

More importantally - I now get very clean entropy edge mask, including the 'swampl-jungle' (light green-darkgreen) edges

Here is the whole entropy code, I am now planing to use. very clean, though perhaps a bit specific for this type of image.
->

This still shows points along borders of 'transparent areas' specifically at the top-right, and also points whcih are too close to normal edges (a sub-image centered there will crop off the image). So the next step is remove the points that would be too close to the edge, or contain transparency...
These are the acceptable points, and it is from this I no need to find a well separated distribution of points to use as the center point of a sub-image searches. The next task.

Okay I can now create a incremental list of maximally distribution of points.

From the acceptable points mask, I selected a first point which is simply the closest point to any corner.
For this I set up a distance gradient for each of the corners, mask it, then select the smalled pixel value that
was not zero.

The result in my setup was the lower right corner, but using the above example it is the top-left. Using the X,Y of the point found I set up a 'distribution map'. this is simply an all white image with a single black point at that location. To find the next point to try I take the 'distribution map', run it through the distance function and mask it with the 'acceptable points map'. The pixel with the largest distance was the next point. This new point is added as the second black pixel in the 'distribution map', ready to find the thrid point. After four iterations all four corners were found, which is what I would have expected.

This is what the 'distance gradient' of the 'distribution map' looks like (normalized).


Remember this is then masked with the acceptable points, and the maximum masked distance is used to select the fifth point.

The fifth point was near the center, afetr this edges are selected, and so on... here is the distance map after 6 points have been selected.


And after 10 points have been selected.


Sort of looks like reproducing skin cells
The apparent randomness is due to the 'acceptable points' masking constraint, so the positions that are really most distant may not be selected, only the most distance 'acceptable point' is returned each time.

Note that as more points are found the distance to the next point slowly gets less. In the above (10 point map) the largest distance to found was 33.1 pixels (a 16 bit color value of 3310, in a non-normalized distance gradient)
It actually drops down in stages,

And here is the first 100 maximally distributed acceptable points (largest distance is now only 6.2 pixels)


Note only points which are 'acceptable' according to the mask that was generated from the entropy map will be selected.
I doubt I need to go beyond a list of 100 points in a sub-image serach before finding an appropriate match (probably only the first 10 will be needed).

As a matter of interest Here I let it run for some time (401 points, seperation distance now 2 pixels)




The "overlap" script is currently generating these images as the points are found.

Now I just need to convert these selected points into sub-image crops to search on the second image, and see if we can find a overlap. I would not be suprised if we don't find a good match within 4, (all corners), or 9 (corners, center, edges) points. If not found in 20 points I doubt a acceptable overlap would ever be found for final verification.

Hmm a better entropy program may be to look for the corners of 3 or more 'segments'. Ideas?

Well it works. now that it is selecting 'high entropy' points, it finds the appropriate match (if it exists) nearly 100% of the time.

The crops area (radius around the high entropy selection) is reduced to a radius of 4 pixels (crop areas 9x9)
but I could also use 3 (not a big time decrease). Using a radius 2 or 1 however is finding a percentage of false matches.

All in all automatic selection of small sub-images to find the offset of overlapping images is not working quite well.
The script however is not finalised as I still need to actually merge the overlapping images to generate the resulting image.
It is however a great improvement, with very little time (compared to the sub-image search) in finding better crops for that search.

Any further ideas, are however welcome.

PS: I no longer use -segment as it fails badly on maps of snow areas with ice lakes.

The above realy should be written up in "compares" in IM examples...

The overlap script is now back in working order, and is now using high entropy locations for selecting smaller crops for the sub-image search. It is working very well in that respect.

http://www.imagemagick.org/Usage/scipts/overlap

Of course some type of 'point registration' method of finding overlaps would probably be better and faster but I have no idea where I can find a good (simple) program to do this.


The problem I now face is given what is thought to be a 'good' match. determining if it really is a good match, so it can merge the images, and move on to the next small image to find an overlapping location. At the moment I need to check the results of a number of sub-image searches, and perhaps a flicker-compare, to ensure the merged image is really correct (though it is now very rare for it to make a mistake, even with the much smaller crop images).