Search for special image difference metric

Question

For regression tests of our note typesetting program, LilyPond, we currently use ImageGraphick's compare program with the MAE metric (mean absolute error, average channel error distance). A typical call to get metric values is

compare -verbose \
        -metric psnr \
        -depth 8 \
        -dissimilarity-threshold 1 \
         regtest-old.png regtest-new.png regtest-diff.png

This works fine for almost all regression test comparisons. However, it doesn't give good results for some cases that must be flagged as problematic, namely the appearance or disappearance of objects.

Consider the following two images, which are identical except a vertical shift by one pixel.

The MAE reported by a call as described above is 5422.7.

On the other hand, the following two images are substantially different (at least from the viewpoint of LilyPond) – they are identical except a small object, which is missing in the second image.

Here, the MAE is much smaller, namely 14.8507.

Due to rendering at a rather low resolution (to speed up the regression tests) we use a threshold to reject 'unimportant' differences. Alas, the case with the missing object is below our threshold.

My question: Is there a better metric available that returns smaller values for image shifts and the like but larger values for missing or added objects? All other metrics offered by the compare program seem to be unsuitable.

Answer 1

I’ve invented (or perhaps reinvented; I’m not particularly familiar with the field) an image comparison algorithm which is intended to solve almost this exact problem: sharp-edged shapes whose boundaries may be rendered slightly differently, but which should not have missing or mis-colored elements.

• First, pick a color comparison function that returns a distance value, which I'll call $c$ — the precise choice is only important insofar as you care about accurate color rendering, which I suspect is not much in your case.

• Define the “half-diff” function $h(a, b, x, y)$, where $a$ and $b$ are images and $x$ and $y$ are positions in them, as

  $$ h(a, b, x, y) = \min_{Δx \in \{-1, 0, 1\} \\ Δy \in \{-1, 0, 1\}} c(a[x, y], b[x + Δx, y + Δy]) $$

  That is, $h$ compares a pixel in $a$ to a 3×3 (±1) neighborhood of pixels of $b$, and accepts the least difference found. This is how the algorithm accounts for spatial shifts; the rationale for ±1 pixel is that rounding errors that produce 1-pixel shifts are extremely common. (A generalization of this algorithm would be to replace the neighborhood with an arbitrary kernel.)

• Finally, define the complete difference function $d$ as

  $$ d(a, b, x, y) = \max(h(a, b, x, y), h(b, a, x, y)) $$

  This combination of the two half-diffs ensures that no elements may be omitted or added to the image; every color in one image must be represented in the other (within the distance determined by the neighborhood).

Now, it is a largely separate matter how you wish to summarize these $d$ pixel differences over the whole image. I build a histogram, and then set acceptance criteria like “there may be N pixels with up to D color-difference”. For simple cases, you may need no threshold at all — the neighborhood can account for all differences that are simply 1-pixel shifts in the position/shape of edges.

A deficiency in this algorithm is that it does not account for the variations in the details of antialiased edges. I believe this can be fixed by, instead of finding the distance to each color in the neighborhood, finding the distance to the convex hull of the colors in the neighborhood — that is, if the neighborhood contains both black and white, then all grays are permitted. However, this might be too lenient, and will certainly require much more computation; I have not yet prototyped it, and am handling the situation so far by setting lenient thresholds and testing only non-antialiased rendering whenever feasible.

---

This algorithm is implemented in my Rust library rendiff (GitHub, crates.io). The repository includes a command-line tool that could be used as the starting point for integrating the implementation into a non-Rust project, but it's likely that you’d prefer to reimplement the algorithm.