Imgdiff: Faster than the fastest pixel-by-pixel image difference tool

I too was surprised that OP's imgdiff is "3X faster than the fastest in the world pixel-by-pixel image difference tool". I would have expected imagemagick etc to be faster.

Here's some Python code (using OpenCV & numpy) that is roughly equivalent to OP's imgdiff. It is single-threaded but it'll be vectorised and it's 3x faster on my 5-year-old 2-core laptop (even counting the Python overhead):

  import sys, cv2, numpy
  
  f1 = cv2.imread(sys.argv[1])
  f1 = cv2.cvtColor(f1, cv2.COLOR_BGR2GRAY)
  f2 = cv2.imread(sys.argv[2])
  f2 = cv2.cvtColor(f2, cv2.COLOR_BGR2GRAY)
  threshold = 0.1
  
  absdiff = cv2.absdiff(f1, f2)
  _, thresholded = cv2.threshold(
      absdiff, int(threshold * 255),
      255, cv2.THRESH_BINARY)
  
  cv2.imwrite("output.png", thresholded)
  print("Different pixels: %s" % numpy.count_nonzero(thresholded))

Benchmark:

  $ /usr/bin/time python test.py water-4k.png water-4k-2.png
  Different pixels: 89153
  1.39user 0.34system 0:01.33elapsed 129%CPU

  $ /usr/bin/time ./imgdiff water-4k.png water-4k-2.png output.png
  Failure! Images are different.
  Different pixels: 89142
  Command exited with non-zero status 1
  8.85user 0.10system 0:04.02elapsed 222%CPU

(Edit: The Python code is a simplified version extracted from https://github.com/stb-tester/stb-tester -- we use it for regression testing of GUI screenshots.)

Congratulations on writing a tool that has 3 times the performance of the most commonly used competitor. The fact that you exploited simply straightforward technique in terms using Go's multithreading is a plus in my book, no magic just simple engineering. Also, thanks for sharing it :)

For the curious, if you want to avoid numpy's memory overhead[1] here's how you'd do it in C with no dependencies: https://github.com/stb-tester/stb-tester/blob/v32/_stbt/sqdi...

This C code isn't doing exactly the same thing; here it's calculating a global similarity measure by calculating sum-of-squared-differences and comparing the end sum against the specified threshold, instead of comparing each pixel-wise diff against the threshold.

It is straightforward C code but it's vectorised by the compiler: https://godbolt.org/z/-3uO1z

Excluding the overhead of reading & decoding the PNGs, it takes 80ms for the same 8400x4725 images as my parent comment.

Benchmark:

  $ git clone git@github.com:stb-tester/stb-tester.git
  $ cd stb-tester
  $ make
  $ ipython
  >>> import _stbt.sqdiff, cv2, timeit
  >>> f1 = cv2.imread("water-4k.png")
  >>> f2 = cv2.imread("water-4k-2.png")
  >>> timeit.timeit(lambda: _stbt.sqdiff._sqdiff_c(f1, f2), number=1)
  0.081

[1] The Python code in my parent comment will allocate memory (the size of the entire image) for each intermediate calculation like the colourspace conversion, the absolute differences, etc.

This can be done much faster. The problem is memory/disk bound.

Decoding the PNGs should be most of the work if written properly.

Edit: Yes, this is more reasonable: https://news.ycombinator.com/item?id=25405595

I believe many (most?) opencv & numpy operations release the GIL.

Good point about OpenCV's in-place operations. Sometimes it's tricky/impossible to do that in numpy if you need to implement something that OpenCV doesn't provide. For example the C code that I linked in my previous comment, we wrote as an optimization of OpenCV's `matchTemplate` when the inputs meet a specific condition (that both input images are the same size). In C we do the multiplications as we iterate over the images and we maintain a rolling sum in a single variable. In numpy you can't really do this, you have to multiply the whole array and then sum the result.

For 720p images our C implementation[1] was 100x faster than our numpy implementation[2], and 10x faster than numba[3].

[1]: https://github.com/stb-tester/stb-tester/blob/v32/_stbt/sqdi...

[2]: https://github.com/stb-tester/stb-tester/pull/566/files#diff...

[3]: https://github.com/stb-tester/stb-tester/pull/566/files#diff...