finding images within an image & excluding them from filters

[sas]

Hi,

I have something I'd like to do with ImageMagick, but I'm not sure where to start, or if it's even possible.

Given a source image, for example like this:


... and a "search image", for example like this:


...the ImageMagick script should be able apply some arbitrary filter/effect (like e.g. desaturating) to the source image, but all occurrences of the "search image" within the source image should stay like they were originally:


Given assumptions:

• The source image is fully opaque.
• The "search image" is non-rectangular, and may contain semi-transparency for anti-aliased edges (but other than that, no semi-transparent areas)
• All occurences of the "search image" are fully contained in the source image, and don't overlap

I'd be interested in any pointers on how this might be achievable...
Note that I'd settle for a pragmatic approximation, like e.g. a solution that breaks the anti-aliased edges but otherwise does the job.

[fmw42]

You can use compare to match a small image to where it can be found in a larger image. The output is two images (or two frames) for one name. The second image or frame will be the match score image. In it find the brightest peaks (above some threshold). Once you have those coordinates, you can make a binary mask using your small image as white and insert (composite) it at each location in a same size as the larger image black image. Then create a grayscale version of your large image and use the original and mask to merge the two images so that where the stars exist in the mask you take from the original and elsewhere you take from the grayscale.

An example of compare can be found at the following link. But you now (more recent versions of IM) need to add -subimage-search to make it work. viewtopic.php?f=1&t=14613&p=51076&hilit ... ric#p51076

[anthony]

I see two basic methods, all of which generates a grayscale map of match probabilities

• Sub-image compare (very slow)
• Using Morphology - hit-n-miss, or Correlation
• Fast Fourier Transforms Multiply (actually a convolve, which with a 180 rotation of sub-image generates a correlation)

"Compare" first handles color images, but does not handle transparency (replace with a grey or some other general background color). The other two techniques are really gray scale channel matching, and not true color vector distance matching.

Code: Select all

convert search_image_orig.png -background gray50 -flatten search_image.png
compare -subimage-search -dissimilarity-threshold 100% \
          search_orig.png  search_image.png search_results-%d.png

Inputs...

results:

Two images are generates, a 'best match highlight image' and the 'greyscale match probably map image'
Note the four very bright spots where the 'best matches' were found.

NOTE the probably map image is smaller, as "compare" makes no attempt to find a partial match!


The two morphology methods needs you to convert the sub-image into one or more arrays of floating point values. The script image2kernel can do this.

What is more these can handle shaped images! basically the transparent parts are converted to 'non-values' (NaN or Not a Number, special floating point values) I designed it that way!!!!!

For examples see... Correlation and Shape Searching
http://www.imagemagick.org/Usage/convol ... ate_search
this also goes into enhancing the probability map to locate the 'peaks' better.


FFT is the faster method for larger search images, but involves converting the image into a very different form of data (frequency maps). unfortunately it does not handle shapes, so like sub-image search map the transparency to a general background color.


WARNING: None of the above handles rotations of the search image! For that much more complex methods are needed, or multiple search patterns.

[sas]

Thanks for your help anthony and fmw42.

I've now played around with this a little.
One thing that confuses me is that the -dissimilarity-threshold option of compare doesn't seem to have much of an effect:

Code: Select all

compare -subimage-search -dissimilarity-threshold X% original.png search_image_flat.png result-%d.png

X=0%: , X=100 %:

--------------------------

In either case, the match positions come up like this:

Using a simple threshold:

Code: Select all

convert result-1.png -threshold 99.9% result-1-max.png

Using peak extraction as suggested on the example pages:

Code: Select all

convert result-1.png -bias -100% -convolve '-1,-1,-1,-1,8,-1,-1,-1,-1' -threshold 10% result-1-peaks.png

Does that mean that one should always use a simple threshold when using the "compare -subimage-search" method, and the convolve-peak-extraction is only meant for use in combination with the Morphology/Correlate subimage search methods?

--------------------------

In the next step, what is the best way to construct a binary mask with the shape of the search image at each of the found locations? I know I can write out the "locations" image to "txt:" format, parse the output with grep/sed, and construct new ImageMagick commands from it. But is there some kind of "shortcut" to doing this?

[sas]

Anyways, you're right that this fuzzy "compare -subimage-search" is very slow.

If I were to add the additional assumptions that...

• each occurrence of the search image inside the source image is a pixel-perfect copy of the original search image (except of course for pixels which are transparent or semi-transparent on the original search image)...
• the search image can be uniquely identified by just a small, fully opaque portion of it...

...would that allow for a search method that is both faster, and more accurate?

E.g. consider the following 3x3 px cropped portion of the original search image:

Code: Select all

convert search_image.png -crop 3x3+9+8 +repage search_image_cropped.png

--> (Zoomed for demonstration purposes. Actual image: )

Is there a fast and reliable method for finding the positions within the source image where this 3x3 px block appear?

"compare -subimage-search" doesn't seem to be very helpful now (not to mention that it's still not noticeably faster):

Code: Select all

compare -subimage-search -dissimilarity-threshold 0% original.png search_image_cropped.png result-%d.png
convert result-1.png -threshold 99.9999% result-1-max.png

Lots of false positives here, e.g. this is what it chose as best match: -->

Which method would be better suited in this case?

[fmw42]

In the next step, what is the best way to construct a binary mask with the shape of the search image at each of the found locations? I know I can write out the "locations" image to "txt:" format, parse the output with grep/sed, and construct new ImageMagick commands from it. But is there some kind of "shortcut" to doing this?

Once you have the coordinates, you take your star image and threshold it or some other colorization to make the star white on a black background. Then you composite the star at each coordinate on top of a black image the size of the large image. The match coordinates correspond to the upper left corner of the star image relative to the big image. So those should work directly without any offsets for the center.

see

http://www.imagemagick.org/Usage/layers/#convert
http://www.imagemagick.org/Usage/layers/#flatten


With regard to speed up of the compare search, if you are on Linux/Mac or Windows w/Cygwin, then you can use my norcrosscorr script that does the search in the frequency space i.e. FFT. see the script at my link below and examples at
http://www.fmwconcepts.com/imagemagick/ ... urier.html
in particular
http://www.fmwconcepts.com/imagemagick/ ... mcrosscorr

Note you will need to compile IM in (Q16) HDRI mode to use the script.

[anthony]

NOTE... just a small warning about terms.
the convolve-peaks method is really being used as a correlate-peaks method.
However as the kernel being used is symmetrical, convolve and correlate produce the same result.


Remember colors are not handled well in correlate, or in FFT correlate (same thing, but different method that works better for larger kernel images). Essentially they don't know colors, only arrays of numbers (channel values). This is why it may be better to convert the images to greyscale (intensity channel only) for the correlation process.

Other methods of greyscaling the images may however improve the comparision. For example in stead of intensity,
you may get a better foreground/background differentiation using Hue.

Another greyscale method is to perform an edge detection on the two images. This will highlight the boundaries and shape, which is typically much more important than any smooth gradient or color changes in the image.

For examples of Edge detection methods see
http://www.imagemagick.org/Usage/convolve/#laplacian

The result of the the detection is now greyscaled, and enhanced. In doing this you should use either a 50% bias, or HDRI (which is good for FFT anyway) so as to preserve background/forground aspects of the edge detection.