I'm on a very simplified pattern recognition quest!

First I thought i would post here, I'm not realy expecting any perfect answers, but I'm looking to see if someone else is interested in the same problem, has solutions, has links to information about solutions etc.

Basic problem, find the sub-image-map in the image-map. The largest scaled version of the sub-image-map should be the final answer.

Image-Map
0000000000000000000000
0000000001111100000000
0000000001111100000000
0000000001111100000000
0000000001111100000000
0000011111111111110000
0000011111111111110000
0000011111111111110000
0000011111111111110000
0000000001111100000000
0000000001111100000000
0000000001111100000000
0000000001111100000000
0000000000000000000000

[download]
Sub-Image-Map
010
111
010

[download]

A couple ideas I've considered and will try to implement include, breaking the image-map down further into 2x2 blocks, 3x3, 4x4, etc and compare each of those grids to the sub-image-map. This definitly counts as a brute force, and would require tons of passes to get any results. So then my second idea is to start with the sub-image-map, and slowly increase its size (scanning over the image-map each time) until i get a match. This has the same problems as the first idea except that you don't loose any detail in the original so matches that wouldn't fall neatly into 4x4 blocks (or 2x2,3x3,etc) could still be matched. Both of these seem brutish and I'm sure others out there have some ideas how to match them in a better fashion.

So how did I get to this quest? I want to catalog my existing collection of pictures. Yes I know its hard, maybe even impossible to do well. My goal is to learn and maybe explore some non-traditional methods ;) So my first idea is to let the user highlight "significant" portions of an image and tag them with a name. For instance I might outline my face and tag it "eric". Then I want it to store that tag and scan all other images for that sub-image (for lack of a better term.) Now of course a straight compare wont work well because of variations in the photo's size, color and background. So the first step would be to normalize the photo's down to contain less information. A couple ideas for that include histograms, density maps, edge detection etc. Once I have normalized the images on file, and the sub-image, then its STILL a matter of searching for the sub-image-map in the whole list of image maps. Which brings us to my post ;) Given the following image-map and sub-image-map can anyone devise an algorithm that isn't brute force? The examples here are obviously very simple and no where near realistic, however you have to start somewhere, and the bottum easiest case is the way to start.


___________
Eric Hodges

In reply to Pattern Recognition Quest by eric256

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.