title: Algorithm to cut down number of comparisons to calculate chi-squared distance between histograms?
body: <p>I'm working on a side project that will accept a source image and then produce a photo mosaic using a set of thumbnailed images it has available. I have an implementation that works OK (see below) but I'm running up against "big O" issues trying to increase the number of available images for replacement.</p>
  
  <p>The process I'm currently using is the following:</p>
  
  <ul>
  <li>I pre-calculated 4 bucket RGB color histograms for all the available replacement images</li>
  <li>Scale up the source image to 1000x1000</li>
  <li>Create 20x20 "tiles" from the scaled source image and create 4 bucket RGB histograms for each tile</li>
  <li>For each tile, calculate the Chi-squared distance for each of the available replacement images</li>
  <li>For each tile, select the replacement image with the smallest Chi-squared distance</li>
  </ul>
  
  <p>So concretely, the problem I'm running into as the number of available replacement images increases the number of comparisons grows exponentially. I'm currently testing with 25,000 available replacement images and it takes nearly 10 minutes to generate the final image across 4 cores on my laptop.</p>
  
  <p>My question is, is there an approach I can use to avoid having the number of distance calculations grow exponentially?</p>
  
  <p>One idea I had was calculating the distances between each of the goal "tiles", separating them into some N groups, finding an average histogram within the group and then finding the closest K available images to the average histogram. From there, I'd go back and calculate the closest matches for the tiles within each group but from a smaller source of the K closest images.</p>
  
  <p><a href="https://i.stack.imgur.com/EnDeW.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/EnDeW.png" alt="Example mosaic"></a></p>