Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

comparing two images and detecting differences

by moof1138 (Curate)
on Dec 31, 2003 at 01:24 UTC ( #317813=perlquestion: print w/replies, xml ) Need Help??
moof1138 has asked for the wisdom of the Perl Monks concerning the following question:

Greetings kind monks. I collect ancient coins, mostly Greek and Roman. While counterfeits are not common from brick and mortar dealers, unfortunately there are some counterfeits occasionally sold on eBay (mostly cast copies). Fortunately there are many image collections of known forgeries that a collector can use to check up on coins, but they are a pain to work with as there are hundreds of images to scan.

I was thinking about writing a tool in Perl that took a given image, resized it appropriately, and compared it to a set of images and if the images were similar, then present the original image and the counterfeit for human verification. It would be easy to build up a large image library of counterfeits, and many times identical images are used by sellers, so often counterfeits would be an exact match.

When I thought more about the problem I figured I might be in over my head, and I did not see anything on CPAN that did exactly what I was interested in (though perhaps I missed something).

I was thinking I could crop the images to the edges of the coin and resize both, but was not sure if content based cropping was possible. Alignment is not a problem since images are almost always aligned top to bottom. If I could get that far I could use Image Magick, create a negative of one of the images and then composite them, then test the composite image. I am not exactly sure how to test the results off the top of my head, but I think this is something I could sort out. I wanted to know if any monks knew of a CPAN module, a different library that might be useful for this sort of task, or if there is a better approach to take. If anyone has done anything similar and could give me any pointers I would really appreciate it, this particular topic seems to be a real pain to find the right keywords to search for.

There are a lot of folks who are really upset by forgeries and I would really like to make a CGI or a tool available to collectors that they could use to test images. If I made a CGI that did this I could get it hosted for free and I think it would be valuable to a lot of collectors who are currently intimidated by the threat of counterfeits (even though they areally are not that common, even on eBay).

Many thanks for any advice you might have to offer.
  • Comment on comparing two images and detecting differences

Replies are listed 'Best First'.
Re: comparing two images and detecting differences
by tachyon (Chancellor) on Dec 31, 2003 at 01:54 UTC

    Image processing is really a task for C/C++ based tool. There has been a vast ammount of work done on the topic and it gets into tertiary level math. If you wanted to do it in Perl/CGI your quickest path would be to get hold of a C/C++ library and make an XS wrapper for it.

    Here is a useful site with source code. The main library it uses lives here and is available for Win32 or Linux with versions that compile with VCC, BCC, and GCC. You will find a wealth of info on Google searching for strings like 'image compare similarity C++'

    cheers

    tachyon

      Thanks for the link, I think Merlyn's column referred to below should work out as a good place to start, but I will keep that in my back pocket. The server it will wind up running on might be Linux, BSD, or Win2k, depending, and I might need to delegate it to someone else, so I really wanted to avoid C/C++ since I wanted to make sure the code was as portable as possible, and setup was as painless as possible. Again, thanks.
Re: comparing two images and detecting differences
by daddyefsacks (Pilgrim) on Dec 31, 2003 at 05:22 UTC
    merlyn has a column seemingly very similar to what you are looking for. Take a look here if you are interested. Best of luck!
      I did a cursory search of Merlyn's articles, but somehow I missed the perfect one. Many thanks for that link. That looks like an excellent place to start.
      I don't actually think it's very similar. merlyn was trying to find similar images (differing by resolution, format, etc, but otherwise more or less identical) whereas moof1138 is trying to find similar objects - the images he will be comparing will all be lit differently and be photographed against different backgrounds. Removing the backgrounds and adjusting colors based on lighting are both nontrivial tasks. I think the C/C++ based tools mentioned by tachyon in the first post will be your best bet.
      This is definitely a cool problem, here's a possible snag that you may run in to:

      "My selected strategy is to reduce each image to a 4-by-4 grid of RGB values, yielding a 48-number vector of values from 0 to 255."


      Assuming that the counterfeits would at least have similar color schemes to the originals, this has a very good chance of generating a lot of falsely positive matches. You could get around this by increasing the size of the grid (and therefore the length of your vectors), but this is the kind of algorithm in which C/C++ would probably outperform Perl (although you could check out the pdl). Even after making your vectors then you're left with the task of determining a metric for measuring similarity of vectors and deciding how similar two vectors must be in order to assume that they point to the same type of coin.

      Here's what I think that I would do:

      - Play with generating vectors using the method from Merlyn's article until you find an acceptable balance of speed and sensitivity.
      - Use a measure of similarity between vectors (such as Euclidean distance) and compare different images of the same coin.
      - Attempt to determine a reasonable threshold for assuming that they point to a counterfeit copy of the same type of coin.


      Actually, more realistically I'd put this off until after vacation, when I could go back and ask an imaging scientist friend about the problem. :)

      Good luck, and have fun.
Re: comparing two images and detecting differences
by cyocum (Curate) on Dec 31, 2003 at 10:01 UTC

    When I want to deal with Perl and images, the first place I always start is Image Magick. I am not an image expert so doing this type of work while interesting and valuable is out of my league.

Re: comparing two images and detecting differences
by zentara (Archbishop) on Dec 31, 2003 at 16:56 UTC
    My first thought on this, is to try and use the "face-recognition" technology that is being rapidly developed for "homeland security". I would google for that.
      Make sure to also google for "tail-recognition" so you can recognize both sides of the coins ;P
Re: comparing two images and detecting differences
by JoshuaD (Novice) on Jan 01, 2004 at 02:15 UTC
    Like someone said above, image comparision is not an easy subject. You're best bet is to write it in C, and call it from perl. To pre-process the images (before you compare), you should look into color normalization. It's a simple formula actually(the image is a NxM matrix or 2d array).
    foreach pixel { (pixel - min)*255/max }
    If you've got RGB you'll have to do that for each of the color values. After you do that, you'll probobly wanna do edge detection using a laplachian filter. After this it gets really tricky, but learning those two things will get you pointed in the right direction.
      I think comparing edges only may be the key (excellent link, JoshuaD). The edges should capture the features of the coins being compared. Simply comparing images will not work - here's why.
Re: comparing two images and detecting differences
by zentara (Archbishop) on Jan 01, 2004 at 20:29 UTC
    I was going thru the Imager docs today, and came across this:

    I guess the hard part would be aligning the images. But maybe you could do a series of resize and rotations and check for minimum difference?

    From perldoc Imager::Filters

    Image Difference You can create a new image that is the difference between 2 other images. my $diff = $img->difference(other=>$other_img); For each pixel in $img that is different to the pixel in $other_img, the pixel from $other_img is given, otherwise the pixel is transparent black. This can be used for debugging image differences ("Where are t +hey different?"), and for optimizing animated GIFs. Note that $img and $other_img must have the same + number of channels. The width and heigh of $diff will be the minimu +m of each of the width and height of $img and $other_img.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://317813]
Approved by rob_au
Front-paged by grinder
help
Chatterbox?
and the fire pops...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (10)
As of 2017-06-26 18:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    How many monitors do you use while coding?















    Results (585 votes). Check out past polls.