<p>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.</p>
<ul>
<li><p>First, pick a color comparison function that returns a distance value, which I'll call <span class="math-container">$c$</span> — the precise choice is only important insofar as you care about accurate color rendering, which I suspect is not much in your case.</p>
</li>
<li><p>Define the “half-diff” function <span class="math-container">$h(a, b, x, y)$</span>, where <span class="math-container">$a$</span> and <span class="math-container">$b$</span> are images and <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are positions in them, as</p>
<p><span class="math-container">$$
  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])
  $$</span></p>
<p>That is, <span class="math-container">$h$</span> compares a pixel in <span class="math-container">$a$</span> to a 3×3 (±1) neighborhood of pixels of <span class="math-container">$b$</span>, and accepts the <em>least</em> 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 <a href="https://en.wikipedia.org/wiki/Kernel_(image_processing)" rel="nofollow noreferrer">kernel</a>.)</p>
</li>
<li><p>Finally, define the complete difference function <span class="math-container">$d$</span> as</p>
<p><span class="math-container">$$ d(a, b, x, y) = \max(h(a, b, x, y), h(b, a, x, y)) $$</span></p>
<p>This combination of the two half-diffs ensures that no elements may be omitted <em>or</em> added to the image; every color in one image must be represented in the other (within the distance determined by the neighborhood).</p>
</li>
</ul>
<p>Now, it is a largely separate matter how you wish to summarize these <span class="math-container">$d$</span> 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.</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Convex_hull" rel="nofollow noreferrer">convex hull</a> 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.</p>
<hr />
<p>This algorithm is implemented in my Rust library <code>rendiff</code> (<a href="https://github.com/kpreid/rendiff" rel="nofollow noreferrer">GitHub</a>, <a href="https://crates.io/crates/rendiff" rel="nofollow noreferrer">crates.io</a>). 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.</p>

CC BY-SA 4.0
2024-07-30T04:05:46.077Z
Thanks a lot!  It will take some time for our developers to test your suggestions, though – I'm just the messenger :-)
lemzwerg
CC BY-SA 4.0
2024-07-28T16:01:42.403Z
2024-07-28T16:01:42.403Z
Kevin Reid
<p>For regression tests of our note typesetting program, <a href="https://lilypond.org" rel="nofollow noreferrer">LilyPond</a>, we currently use ImageGraphick's <code>compare</code> program with the MAE metric (mean absolute error, average channel error distance).  A typical call to get metric values is</p>
<pre class="lang-sh prettyprint-override"><code>compare -verbose \
        -metric psnr \
        -depth 8 \
        -dissimilarity-threshold 1 \
         regtest-old.png regtest-new.png regtest-diff.png
</code></pre>
<p>This works fine for almost all regression test comparisons.  However, it doesn't give good results for some cases that <em>must</em> be flagged as problematic, namely the appearance or disappearance of objects.</p>
<p>Consider the following two images, which are identical except a vertical shift by one pixel.</p>
<p><a href="https://i.sstatic.net/AwWkCa8J.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/AwWkCa8J.png" alt="image-x" /></a>
<a href="https://i.sstatic.net/WiEZjpSw.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WiEZjpSw.png" alt="image-y" /></a></p>
<p>The MAE reported by a call as described above is 5422.7.</p>
<p>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.</p>
<p><a href="https://i.sstatic.net/1adRZ63L.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1adRZ63L.png" alt="image-a" /></a>
<a href="https://i.sstatic.net/lG66QrI9.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lG66QrI9.png" alt="image-b" /></a></p>
<p>Here, the MAE is <em>much</em> smaller, namely 14.8507.</p>
<p>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.</p>
<p>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 <code>compare</code> program seem to be unsuitable.</p>

CC BY-SA 4.0
2024-09-25T13:08:52.510Z
Yes, I would use the **equality** metric.  If the pixel values are identical to the baseline then the test passes.  If any pixel is off, even by one bit, then the test SHOULD FAIL (because something has changed) and the test should then either be be re-baselined or a bug should be logged.  Let go of your notion that "close is good enough".  If you have randomness for dithering or something that you're trying to accommodate - seed your random number generator for your unit test.  Your renderer should produce repeatable results in your unit tests.
Wyck
CC BY-SA 4.0
2024-09-25T17:28:44.400Z
It's not that easy, unfortunately.  Vertical shifts by a fraction of a pixel occur regularly and are in almost all cases completely irrelevant.  We really want to discard such differences and classify them as unimportant (i.e., below a given threshold).
lemzwerg
CC BY-SA 4.0
2024-09-28T17:18:10.320Z
_Vertical shifts by a fraction of a pixel occur regularly_  Sounds like you've found your first important bug.
Wyck
CC BY-SA 4.0
2024-09-28T22:30:54.777Z
I probably was unclear: Such shifts are *expected* but unimportant, there is no bug.  LilyPond has a working comparison system for its regression test suite that helps us find rendering problems quite reliably, and which was fine-tuned and improved over the course of more than 20 years.  What we want to do is to *further* improve it to catch a very specific problem as described above.  An equality metric definitely doesn't fit the bill for this task.
lemzwerg
CC BY-SA 4.0
2024-09-29T04:51:49.943Z
I hear you, but I'll try to be clear again as well.  You could further improve this 20-year-old test suite by eliminating any non-deterministic behaviour so that you can use equality comparisons against baseline output.  Why do you expect non-deterministic output from your typesetter?  Why would you have a test that gives you a shifted result one time and an unshifted (or differently shifted) result some other time such that you have to accommodate both results as passes?  It feels like you're missing the point of what a regression test is supposed to do.
Wyck
CC BY-SA 4.0
2024-09-29T13:49:10.447Z
There is a misunderstanding again: I have nowhere mentioned that we get non-deterministic behaviour!  This is *your* interpretation, and you are wrong.  The vertical shifts are *fully expected* due to changes of, say, different metrics of a glyph, a changed regression test, or due to different typesetting because a commit modifies the layout of some music.

I really, really want an algorithm as described above, I don't need a lecture on regression tests.
lemzwerg
CC BY-SA 4.0
2024-09-29T16:40:31.403Z
I apologize for any misunderstanding on my part regarding non-deterministic behaviour.     It sounds like you're focused on finding an algorithm that handles expected vertical shifts and do not want comments about how you're using it in the context of regression testing.  I'm sorry.
Wyck
CC BY-SA 4.0
2024-09-29T20:14:57.017Z
Thanks.  The thing is that we currently have almost 2500 test files, and sometimes even small changes in the code can cause many tiny (expected) differences, which sometimes create so much noise that real bugs (for example, disappearing notes) are lost.
lemzwerg
<algorithm><image-processing><image-comparison>
Search for special image difference metric
lemzwerg
# Search for special image difference metric

(Asked by: username_0 on 2024-07-27)

For regression tests of our note typesetting program, [LilyPond](https://lilypond.org), 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

```sh
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.

[![image-x](https://i.sstatic.net/AwWkCa8J.png)](https://i.sstatic.net/AwWkCa8J.png)
[![image-y](https://i.sstatic.net/WiEZjpSw.png)](https://i.sstatic.net/WiEZjpSw.png)

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.

[![image-a](https://i.sstatic.net/1adRZ63L.png)](https://i.sstatic.net/1adRZ63L.png)
[![image-b](https://i.sstatic.net/lG66QrI9.png)](https://i.sstatic.net/lG66QrI9.png)

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.

**Tags:** algorithm, image-processing, image-comparison

> **Comments:**
> **username_1**: Yes, I would use the **equality** metric.  If the pixel values are identical to the baseline then the test passes.  If any pixel is off, even by one bit, then the test SHOULD FAIL (because something has changed) and the test should then either be be re-baselined or a bug should be logged.  Let go of your notion that "close is good enough".  If you have randomness for dithering or something that you're trying to accommodate - seed your random number generator for your unit test.  Your renderer should produce repeatable results in your unit tests.  
> **username_0**: It's not that easy, unfortunately.  Vertical shifts by a fraction of a pixel occur regularly and are in almost all cases completely irrelevant.  We really want to discard such differences and classify them as unimportant (i.e., below a given threshold).  
> **username_1**: _Vertical shifts by a fraction of a pixel occur regularly_  Sounds like you've found your first important bug.  
> **username_0**: I probably was unclear: Such shifts are *expected* but unimportant, there is no bug.  LilyPond has a working comparison system for its regression test suite that helps us find rendering problems quite reliably, and which was fine-tuned and improved over the course of more than 20 years.  What we want to do is to *further* improve it to catch a very specific problem as described above.  An equality metric definitely doesn't fit the bill for this task.  
> **username_1**: I hear you, but I'll try to be clear again as well.  You could further improve this 20-year-old test suite by eliminating any non-deterministic behaviour so that you can use equality comparisons against baseline output.  Why do you expect non-deterministic output from your typesetter?  Why would you have a test that gives you a shifted result one time and an unshifted (or differently shifted) result some other time such that you have to accommodate both results as passes?  It feels like you're missing the point of what a regression test is supposed to do.  
> **username_0**: There is a misunderstanding again: I have nowhere mentioned that we get non-deterministic behaviour!  This is *your* interpretation, and you are wrong.  The vertical shifts are *fully expected* due to changes of, say, different metrics of a glyph, a changed regression test, or due to different typesetting because a commit modifies the layout of some music.  I really, really want an algorithm as described above, I don't need a lecture on regression tests.  
> **username_1**: I apologize for any misunderstanding on my part regarding non-deterministic behaviour.     It sounds like you're focused on finding an algorithm that handles expected vertical shifts and do not want comments about how you're using it in the context of regression testing.  I'm sorry.  
> **username_0**: Thanks.  The thing is that we currently have almost 2500 test files, and sometimes even small changes in the code can cause many tiny (expected) differences, which sometimes create so much noise that real bugs (for example, disappearing notes) are lost.  

---

## 1 answers

### Answer by username_2 on 2024-07-28. Score: 0

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](https://en.wikipedia.org/wiki/Kernel_(image_processing)).)
* 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](https://en.wikipedia.org/wiki/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](https://github.com/kpreid/rendiff), [crates.io](https://crates.io/crates/rendiff)). 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.

> **Comments:**
> **username_0**: Thanks a lot!  It will take some time for our developers to test your suggestions, though – I'm just the messenger :-)  

---

