0

I have a set of small sized sprites, usually 25x20 sort of sizes, nothing above 256x256. Some of these sprites are duplicated by them being scaled down slightly, or sometimes a couple of pixels are deleted/added to edges or one colour has changed.

How can I find these duplicates? My application is written in C++ and my images are SDL_Surfaces*'es.

I've attached a couple of example sprite sheets showing the sort of sprites I'm trying to compare and de-dupe.

higher res

lower res and other changes

Here is an image that more clearly shows what I am trying to compare since I think some people got confused and think I want to compare the "whole sprite sheet" when really I just want invidual sprites comparing with each other:

enter image description here

paulm
  • 5,629
  • 7
  • 47
  • 70
  • It seems painful. Theoretically, Template Matching of OpenCV should work. http://docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/template_matching/template_matching.html – lllllllllll Jun 10 '16 at 17:05
  • Huh why the down vote? There is hardly any info online about how to do this – paulm Jun 10 '16 at 17:06
  • A lack of online information does not make your post good or even a good fit for SO. In its current form asking _"I want to do X how to I do it"_ is too broad. – Captain Obvlious Jun 10 '16 at 17:53
  • these are not only scaled they are rotated they are all over the place: you are looking for similarity – gpasch Jun 10 '16 at 17:55
  • Each "island" of pixels is a sprite, they are not rotated – paulm Jun 10 '16 at 18:24
  • gqview/geeqie implements searching for similarities function with relatively simple algorithm. Take a look at comment at the top of https://github.com/BestImageViewer/geeqie/blob/master/src/similar.c – keltar Jun 11 '16 at 08:06
  • Thanks, how does this algorithm work? – paulm Jun 11 '16 at 11:29
  • Btw this question is almost a duplicate: http://stackoverflow.com/questions/2168830/how-can-i-recognize-slightly-modified-images which is also a "I want to do X how to I do it" – paulm Jun 11 '16 at 12:02
  • You only have one _obvious_ object in each image. Means comparing two images is technically comparing two objects. Look up for "Find largest contour in an image" and then think on _how to compare contours_. What is the problem with this approach? – Khalil Khalaf Jun 14 '16 at 12:34
  • What do you mean by "What is the problem with this approach?" I wouldn't know till I try it? :) – paulm Jun 14 '16 at 13:44

1 Answers1

2

Please read my answer on Open CV tic tac toe X / O detection. Also the accepted answer might be helpful too.

My answer for your case: It could be done using the Match Shapes function from OpenCV (Check section 3 in the Documentation)

So for each image, get largest contour (your object) and call that function with ALL the other images. The function returns a value from 0 to 1 for every pair of images that corresponds the similarities between both contours: The smaller the value is the more similar the contours are. You may set a certain threshold to eliminate other images (eliminate all images that are 0.5 similar for example). Trial and Error might be the only way to find the best Threshold. And good luck!

Community
  • 1
  • 1
Khalil Khalaf
  • 9,259
  • 11
  • 62
  • 104