Extracting and identifying images from a larger image

[balsaboom]

Hi Everyone,
I'm trying to develop a web application that will do the following:
The user will upload an image to the site, and the site will transfer the image to my server. Then, on the server side, I want to process the image.
The image consists of several small boxes arranged in a grid on a background. The boxes can have 5 possible borders, so I'm planning on using the presence of this border as a way to determine the location of one of the smaller images I want to process.

Code: Select all

______________________________
|                             |
|     []  []   []     []      |
|     []  []   []     []      |
|     []  []   []     []      |
|     []  []   []     []      |
|     []  []   []     []      |
|     []  []   []     []      |
|_____________________________|

This is a crude sketch of the scenario, the image that will be supplied is the large rectangle. The smaller rectangles (the []s) are the features that I want to extract from the image. Luckily, as a previously mentioned, the smaller rectangles are guaranteed to have 1 of 5 borders. However, the size of the smaller rectangles may vary (by just a bit, the aspect ratio will still be the same). After extracting the smaller rectangles, I want to compare each of the smaller rectangles to a database of images that I have. The images should be an exact match (except for maybe small variations in aspect ratio). I then want to print the name of all of the smaller rectangles in the image given.

As a real life example, lets say each of the [] would contain the face of a US president. Each of the photos would be in a database that I could access. I would want to identify the presidents in the photo.

[fmw42]

Are all the small images, the same size and are they arranged in uniform or well know positions? It may be hard to extract them otherwise, even with known borders. You would need to match an image of each border to your image and somehow ignore what is inside the borders. I am not sure IM has the feature yet. It can located a small image inside a larger one. So you may be better looking for a match to against the database.

Nevertheless, if you can extract the individual images by some means, then IM has a compare function to match two same sized images. The compare function can also be used to match a small image to find where it resides in a larger image.

See
http://www.imagemagick.org/script/compare.php
http://www.imagemagick.org/Usage/compare/
http://www.imagemagick.org/Usage/compare/#statistics

and an old example of mine at
viewtopic.php?f=1&t=14613&p=51076&hilit ... ric#p51076

note that current versions of IM now require the addition of -subimage-search for the latter type search of a small image inside a larger on.

I also have a script that will locate multiple matches from the second output image from the subimage search. It is a bash unix shell script. See the script, maxima, at the link below.

A real example image of your larger image would likely help us understand the problem better. You can post it to some free image hosting service such as dropbox and put a link to it here.

[balsaboom]

Are all the small images, the same size and are they arranged in uniform or well know positions? It may be hard to extract them otherwise, even with known borders. You would need to match an image of each border to your image and somehow ignore what is inside the borders. I am not sure IM has the feature yet. It can located a small image inside a larger one. So you may be better looking for a match to against the database.

Nevertheless, if you can extract the individual images by some means, then IM has a compare function to match two same sized images. The compare function can also be used to match a small image to find where it resides in a larger image.

I don't need to ignore the borders, as my database includes the borders in the image. Each specific image is guaranteed to only have 1 type of border around it, but there are 5 different borders possible.

A real example image of your larger image would likely help us understand the problem better. You can post it to some free image hosting service such as dropbox and put a link to it here.

http://i.imgur.com/b8rv8yo.png?9817
This is an example of the image that will be supplied; I'm creating a web application for identifying a user's monsters in their box for a popular mobile game. There around almost 1000 monsters, so the method of taking an image from the database, then then match subimage to see whether it is in the photo is pretty inefficient in my opinion; it'd be far quicker to extract these boxes, then compare these individual boxes to the database. Another problem is the text at the bottom of each image, which depicts a monster 'level'. Could imagemagick extract the image, then compare it to the database and select a best fit?

[fmw42]

If all the small images are in well know places and sizes, then IM -crop can extract them one by one. Or you can crop out the region of the icons and probably use -crop to get them all in one command via tile cropping and then trim the black outside. See

http://www.imagemagick.org/Usage/crop/#crop
http://www.imagemagick.org/Usage/crop/#crop_tile

Once you have the individual images, you can loop over them to compare them to images you retrieve from your database. However, compare is not fast with large images.

You may be better storing some kind of image hash or metric with your images. Then compare the hashes to get a list of images to then compare with IM.

see
http://www.imagemagick.org/Usage/compare/#metrics
http://www.imagemagick.org/Usage/compare/#type_general

[snibgo]

To expand slightly on fmw's replies:

Cropping out each image, then comparing each one to the 1000 database entries, will be far quicker than searching for each database entry in the whole image.

When comparing each crop to the database entries, you will probably find that you can resize the crop and the database entries to 50% and get a reliable match. This will speed it up by a factor of four. If you are very lucky you will find that resizing down to a single pixel gives a reliable match, and this will be very fast. It should never return a wrong match but might return a number of possible matches. If so, you then search this subset of the database.

If the database is constant then a text hash might be fastest. This could be, for example, the values of the pixels after a resize to 3x3. So you have a hash table of 1000 lines. Pass the crop through the same hash algorithm (eg resize to 3x3) and search the hash table for a match.

[fmw42]

More details about the single pixel (average color) and 3x3 pixels concepts have been discussed by Anthony at http://www.imagemagick.org/Usage/compare/#metrics

I think the main idea here (from both snibgo and me) is to find some quick method to try first to select images for further examination by the slower compare method. Thus one has a two stage approach.

[balsaboom]

If all the small images are in well know places and sizes, then IM -crop can extract them one by one. Or you can crop out the region of the icons and probably use -crop to get them all in one command via tile cropping and then trim the black outside. See

http://www.imagemagick.org/Usage/crop/#crop
http://www.imagemagick.org/Usage/crop/#crop_tile

I'm still unsure that I completely understand this part. Problem is, the locations of the boxes can shift slightly (due to cross platform iOS and Android resolution differences), so I'd probably opt with your 2nd idea. I'm still wondering what you mean by "trim the black outside", however. Could you perhaps rephrase it?

Thanks for all your help!

[fmw42]

I simply mean that if you crop equal sizes by tile cropping in the area of the icons, you will have a border around each crop that is your background. I though it was black, but it actually has a pattern. That makes the trim to "shave" it down to remove the background harder. You might be better off if you can change the background around the icons to pure black or some pure color.

[balsaboom]

I simply mean that if you crop equal sizes by tile cropping in the area of the icons, you will have a border around each crop that is your background. I though it was black, but it actually has a pattern. That makes the trim to "shave" it down to remove the background harder. You might be better off if you can change the background around the icons to pure black or some pure color.

If i were to change the icons, wouldn't that first require identification of the locations of the icons? (thus negating the need for it) Or is there another way that doesn't involve knowing the location?
Is it possible that I could just have the user select which device they use at the start of the process, and create several templates, one for each device OS (as each device OS has a different amount of boxes / row, etc).

[fmw42]

I am not sure I understand your question. I was saying that the background might be better if it was pure black. I am not saying to change the icons.

If you have different patterns of icons, then you would need to use tile cropping differently for each depending upon the number and size of the icons. Otherwise, you would need to know the locations and size of each icon, so you can crop it without the need for the trim.

[fmw42]

Here is an example of tile cropping of your image.

First I crop out the region with the icons.




Then I run this command (IM 6.8.8.1 Q16 Mac OSX)

Code: Select all

convert test.png -crop 133x139 +repage test%d.png

It produces a sequence of 30 images (some needed to be discarded as they were simply borders), which for display purposes I have combined the first 20 into an animation.




If the background were solid black, then I could add -trim to the crop command and it should then remove the excess background, leaving only the icon.

[balsaboom]

I am not sure I understand your question. I was saying that the background might be better if it was pure black. I am not saying to change the icons.

To change the background to black, wouldn't I have to know the location of the icons (in order to not color them black). If i knew where they were, couldn't i just use -crop? Or is there another way I can use.

If you have different patterns of icons, then you would need to use tile cropping differently for each depending upon the number and size of the icons. Otherwise, you would need to know the locations and size of each icon, so you can crop it without the need for the trim.

They aren't different patterns persay, but the number of icons per picture can change (because different mobile devices have different screen resolutions). so it might be 5 rows x 5 cols or 6 rows x 5 cols. I was proposing that maybe it would work if I could take all the different ratios that they are in, sort them by device, and manually compile "templates" for each device/resolution that would know exactly where the icons are, and I could have the user specify which resolution/device they took the screenshot from.

First I crop out the region with the icons.

Which command did you use to crop out the region?

If the background were solid black, then I could add -trim to the crop command and it should then remove the excess background, leaving only the icon.

Is there anyway to make the background solid black, or would it need to be solid black originally in the input image? If you have the images as shown in the animation, isn't it possible to just compare those to the database and get a "best fit" approximation for the matching image?

[fmw42]

You would have to make the template you use black in that area. There is no really good way to alter it if you already have the background. But going forward, you could change your template.

I cropped it manually in this case, but once you have different templates you can figure out how to crop each one and use that in a script in IM.

If the icon size and spacing does not change, then the tile crop command would be the same for all templates. Otherwise, you need to adjust the command for the tile/icon size and spacing. But again you could have a script for each template.

[fmw42]

If the icons are same sized and equally spaced, you can write a script to loop over and to crop out each one without the background. It would just need a start position and X,Y increment as well as the icon size. The script would be different for each template/arrangement.

[balsaboom]

Alright, I think I have a pretty good idea of what I'm going to do. I'm going to allow the user to upload the file via html5/ javascript, which will then use ajax to send the image to a server. While uploading, they will also specify what device type they use, which will inturn determine which template of image processing i would use. I dont think there's anyway to remove the background as of this moment, so I'll just leave it be. As a result, I'm going to have to use fuzzy matching or something of the sort to determine a best guess for what image it is, does imagemagick have tools for doing this / does the rest of it sound correct?