// probabilistic (of course)
srecord noeq ImageSimilarityAtScale(
  IIntegralImage img1,
  IIntegralImage img2,
  int featureSize // smallest block size looked at (in pixels)
  ) extends Probabilistic {
  
  int channels;
  LookAtClip root;
  
  record LookAtClip(LookAtClip parent, Rect r) implements Runnable {
    L<LookAtClip> children;
    
    // diffs are in range [0;255*channels*pixelsCovered]
    double initialDiff, diffsFromChildren, areaCoveredByChildren;
    double latestDiff;
    
    double calculateLatestDiff() {
      ret latestDiff = initialDiff-diffsFromChildren*areaCoveredByChildren;
    }
    
    run {
      // make initial guess
      
      double sum = 0;
      for channel to channels:
        sum += sqr(
          img1.rectSum(r, channel)-img2.rectSum(r, channel));
      initialDiff = sqrt(sum);
      updateMeAndParent();
      
      if (r.w > r.h) {
        if (r.w > featureSize)
          splitHorizontally();
      } else {
        if (r.h > featureSize)
          splitVertically();
      }
    }
    
    void splitHorizontally {
      split(asList(splitRectInHorizontalHalves(r)));
    }
    
    void splitVertically {
      split(asList(splitRectInVerticalHalves(r)));
    }
    
    void split(L<Rect> parts) {
      double p = 0.99; // TODO: do something smarter (recurse earlier in "interesting" areas)
      children = map(parts, r -> new LookAtClip(r));
      scheduleAll(p, children);
    }
    
    void updateMeAndParent() {
      calculateLatestDiff();
      if (parent != null) {
        parent.diffsFromChildren += latestDiff;
        parent.areaCoveredByChildren += area(r);
        parent.updateMeAndParent();
      }
    }
  }
  
  run {
    assertEqualsVerbose("Sizes of compared images have to be equal", img1.getSize(), img2.getSize());
    assertEqualsVerbose("Channel counts of compared images have to be equal", channels = img1.nChannels(), img2.nChannels());
    
    schedule(1.0, root = new LookAtClip(imageRect(img1)));
  }
}