title: Algorithm Efficiency Pattern Matching, Checking for image inside image
body: <p>This is a more descriptive version of my <a href="https://stackoverflow.com/questions/24050383/algorithm-complexity-and-efficiency-exponential-operation-java?noredirect=1#comment37158877_24050383">previous question</a>. The problem I am trying to solve relates to block-matching or image-within-image recognition.</p>
  
  <p>I see an image, extract the [x,y] of every black pixel and create a set for that image, such as </p>
  
  <pre><code>{[8,0], [9,0], [11,0]} 
  </code></pre>
  
  <p>The set is then augmented so that the first pixel in the set is at [0,0], but the relationship of the pixels is preserved. For example, I see {[8,0], [9,0]} and change the set to {[0,0], [1,0]}. The point of the extraction is that now if I see {[4,0], [5,0]}, I can recognize that basic relationship as two vertically adjacent pixels, my {[0,0], [1,0]}, since it is the same image but only in a different location. </p>
  
  <p>I have a list of these pixel sets, called "seen images". Each 'seen image' has a unique identifier, that allows it to be used as a nested component of other sets. For example:</p>
  
  <pre><code>{[0,0], [1,0]} has the identifier 'Z' 
  </code></pre>
  
  <p>So if I see:</p>
  
  <pre><code>{[0,0], [1, 0], [5,6]}
  </code></pre>
  
  <p>I can identify and store it as:</p>
  
  <pre><code>{[z], [5, 6]}
  </code></pre>
  
  <p>The problem with this is that I have to generate every combination of [x,y]'s within the pixel set to check for a pattern match, and to build the best representation. Using the previous example, I have to check:</p>
  
  <pre><code>{[0,0], [1,0]}, 
  {[0,0], [5,6]}, 
  {[1,0], [5,6]} which is {[0,0], [4,5]} 
  {[0,0], [1,0], [5,6]}
  </code></pre>
  
  <p>And then if a match occurs, that subset gets replaced with it's ID, merged with the remainder of the original set, and the new combination needs to be checked if it is a 'seen image':</p>
  
  <pre><code>{[z],[5, 6]}
  </code></pre>
  
  <p>The point of all that is to match as many of the [x,y]'s possible, using the fewest pre-existing pieces as components, to represent a newly seen image concisely. The greedy solution to get the component that matches the largest subset is not the right one. Complexity arises in generating all of the combinations that I need to check, and then the combinations that spawn from finding a match, meaning that if some match and swap produces {[z], [1,0], [2,0]}, then I need to check (and if matched, repeat the process):</p>
  
  <pre><code>{[z], [1,0]}
  {[z], [2,0]}
  {[1,0], [2,0]} which is {[0,0], [1,0]}
  {[z], [1,0], [2,0]}
  </code></pre>
  
  <p>Currently I generate the pixel combinations this way (here I use numbers to represent pixels 1 == [x,y]) Ex. (1, 2, 3, 4): Make 3 lists:</p>
  
  <pre><code>1.)   2.)   3.)
  12    23    34
  13    24
  14    
  </code></pre>
  
  <p>Then for each number, for each list starting at that number index + 1, concatenate the number and each item and store on the appropriate list, ex. (1+23) = 123, (1+24) = 124  </p>
  
  <pre><code>1.)   2.)   3.)
  12    23    34
  13    24
  14  
  ----  ----  ----
  123   234
  124   
  134
  </code></pre>
  
  <p>So those are all the combinations I need to check if they are in my 'seen images'. This is a bad way to do this whole process. I have considered different variations / optimizations, including once the second half of a list has been generated (below the ----), check every item on the list for matches, and then destroy the list to save space, and then continue generating combinations. Another option would be to generate a single combination, and then check it for a match, and somehow index the combinations so you know which one to generate next. </p>
  
  <p>Does anyone recognize this process in general? Can you help me optimize what I am doing for a set of ~million items. I also have not yet come up with a non-recursive or efficient way to handle that each match generates additional combinations to check. </p>