Imgdiff: Faster than the fastest pixel-by-pixel image difference tool | Hacker News Reader

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

github.com

181 pointsdcu62 comments

Compared to the other tool this is just "slow code, but now with threads."

This problem is perfect to exploit capabilities of modern CPUs, and neither of the projects does so. At least this one iterates over the y coordinates in the outer loop.

Nothing about what either tool does is noteworthy.

When one user is waiting for one image, this distinction matters. When multiple users are waiting for an image, or one user waiting for multiple images, the extra complexity is questionable.

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.)

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.

Regarding [1], many OpenCV functions in Python support an optional dst argument, similar to how they do in the C++ API. This makes the memory management situation not completely hopeless.

In my experience, the only drawback of the Python API is the fact that it cannot utilize the multithreading module (probably does not release the GIL for long calls).

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

That's a nice and tidy codebase, real pleasure to read.

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

Any idea how I can determine this? I am prototyping a real time machine vision application targeting 2x720p@240fps and I want to avoid writing any C++ for as long as possible.

I don't know much about Python's C API, but this is the line in the OpenCV Python bindings that drops the GIL: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

(see https://docs.python.org/3/c-api/init.html#releasing-the-gil-... in the Python C API manual).

That's only called from the ERRWRAP2 macro here: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

That macro, in turn, is called from gen_template_func_body in gen2.py: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

And that seems to be a code generator that is generating the bindings for all the OpenCV functions: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

As to testing this, on Linux I'd run `atop` to see if your program is using all available CPUs.

Nice spelunking! If there is hope of avoiding C++ altogether, then I'll try testing it again on something beefier than my laptop. Thanks for taking the time and effort.

When making an image manipulation/creation/diff/etc tool I'd highly recommend showing at least a screenshot or two of the result in the Github itself.

There are so many tools on github lacking screenshots or examples. It’s like they don’t want to sell their free content!

I know you are being ironic, but I wish more people would try to "sell their free content". This blog post would help them do so: https://ternaus.blog/tutorial/2020/08/28/Trained-model-what-...

I'm skeptical about it's high claims. Looking at the code its just using the Go standard library image package, looping over the bounds and calculating delta?

Doesn't seem like there's anything special here? It's roughly what any novice would build if asked to diff two images in Go?

I just skimmed through the code, but as far as I can tell, the main point is that this code is multi-threaded.

Which, sure, gets the job done faster than the single-thread `odiff` on a single image, but is quite irrelevant for a tool marketed for tests/CI where many images are likely to be compared in parallel already (and maybe a single core is even available).

https://github.com/n7olkachev/imgdiff/blob/9b2a87e1b729c70b5...

Yep, uses as many goroutines as the number of CPUs, that's about it. Saying it's 3x faster or whatever in "benchmarks" without even saying what CPU is used in the benchmarks is just sketchy.

I just looked at the source code and I'm very skeptical about what the author claims. The way the code is structured and is written is not very professional. Also I don't see any benchmarks. If you claims something at least give valid sources.

I'm finding "gm compare" to be faster.

    $ time ./imgdiff cypress.png cypress.png         
    Success! Images are equal.
    3.22user 0.10system 0:00.50elapsed 661%CPU 
    (0avgtext+0avgdata 478524maxresident)k
    0inputs+0outputs (0major+48339minor)pagefaults 0swaps
    
    $ time gm compare -highlight-style assign -highlight-color purple -file diff.png cypress.png cypress.png                                             
    1.99user 0.21system 0:02.21elapsed 99%CPU 
    (0avgtext+0avgdata 874948maxresident)k
    0inputs+5240outputs (0major+217173minor)pagefaults 0swaps

    $ time gm compare -metric mse cypress.png cypress.png                                                                                                
    Image Difference (MeanSquaredError):
               Normalized    Absolute
              ============  ==========
         Red: 0.0000000000        0.0
       Green: 0.0000000000        0.0
        Blue: 0.0000000000        0.0
     Opacity: 0.0000000000        0.0
       Total: 0.0000000000        0.0
    0.94user 0.14system 0:00.67elapsed 161%CPU 
    (0avgtext+0avgdata 585832maxresident)k
    0inputs+0outputs (0major+144881minor)pagefaults 0swaps

Were you comparing two identical image? Could you try two different image?

To really see how these algorithms perform, you should compare the worst case for the algorithm. In order to see if a picture is identical, you’d have to loop through every single pixel, which is the worst case. But you can shortcut on the first pixel which is different, which I imagine happens pretty quickly on many generic pictures. So testing performance with two different images is probably not best for comparison.

You can only short-circuit if you’re returning a Boolean. If you need to do what these tools and return some metric for the degree of difference you still have to process both images in entirety.

Years ago I worked with image processing and thought of writing a CLI image diff tool. I then thought meh, anyone can quickly roll their own.

Turns out it seems to be something people care about.

I should just start writing the CLI tools I think of, without dismissing their utility.

Did you know that ImageMagick includes an image diffing tool?

https://imagemagick.org/script/compare.php

...plus ImageMagick has a myriad of options.

Why not use the GPU? This is exactly the kind of tasks GPUs were designed for. Gimp can do this in real time using the difference layer mode.

Does using the GPU pay off for one-off diffing? It's "obvious" that it makes sense for Gimp, but does it for this?

Compared to a threaded CPU implementation, it only pays off if your image is already sitting in VRAM. This kind of operation should be primarily limited by memory bandwidth, so you're just making it take longer by copying the image to VRAM and copying the diff back.

The bottleneck is almost certainly decoding the image (PNGs are zlib compressed, which will be going at something like ~300 MB/s plus the filter stuff PNG does), not comparing raw pixels (which you should be able to do at memory bandwidth, so something in excess of 10 GP/s).

Compressed, but not as a single continuous block. The bottleneck will probably be in doing things serially, both with decompression and the disk IO.

Even before you get into GPU, it looks like you could do the normalisation here https://github.com/n7olkachev/imgdiff/blob/master/pkg/yiq/de... using _mm_mul_ps or _mm256_mul_ps depending on availability instead of standard math. (CPU based vector processing)

There's also bound to be some vector compare trick as well which falls back to pixel-by-pixel only for differences.

I think there are quite a few simple tricks you could apply here to get a bit more performance... Starting with sacrificing some memory and decoding a chunk of image at a time rather than calling .At(x,y) every time. And maybe improving local cache by dividing the image in `cpu` parts rather than having the work interleaved.

Considering the source material is a file, that needs to be loaded up by the CPU first, and the operation itself is dead simple, the real constraint is RAM bandwidth.

I would guess that the time of getting the data out to the GPU and back, is about the same as just calculating the difference on the CPU.

So, the quickest solution is probably to use the CPUs vector operations, and read ahead into the registers so you can exhaust the memory bandwidth fully.

I recently tried this with a 19 megabyte .tiff file in PyTorch. Uploading the tensor took (i think) around 1 or 2 seconds, wall-clock time. So I quickly dismissed the GPU solution to my problem. But I'm still wondering... is this normal?

You've got your GPU program that needs to be compiled to actual GPU code at startup as well. That takes a bit.

The actual file transfer is comparable to the GPU doing a memcpy. (You could also use pinned host memory if the GPU program is just doing a one-off read.)

GPU processing for simple operations really shines if your data is already on the GPU and your code is hot. Otherwise, it's more useful if the process is significantly complex enough to make the overhead of a cold startup insignificant.

GPU can now directly read the file on the SSD.

Citation needed? I know things have been announced but what's available now?

GPUDirect has been available for quite sometime now: https://developer.nvidia.com/gpudirect

Thanks! I forgot storage was supported by that.

Worth noting it's ~100-lines of Go code that's quite readable:

https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdif...

https://github.com/n7olkachev/imgdiff/blob/master/pkg/yiq/de...

This is a go question but I thought go funcs took less than a thread. This assigns one go func per cpu. Can it be faster with more go funcs per cpu?

Likely not. Green threads concept (goroutines) makes a lot of sense if you block on I/O (such as reading DB, making RPCs), you can multiplex a thread. However, in this case, there is not a lot of I/O involved so regular CPU-bound parallel programming practices apply.

This feels like an application where an APL one-liner would just be the fastest thing that there is.

What are some of the common applications for diffing an image?

Regression testing image processing algorithms.

Diff testing UIs.

Automated testing of a rendering engine.

I’ve used them for regression testing web apps:

https://github.com/python-needle/needle

Depending on your needs, detecting duplicates can also be useful – especially if you’re using some kind of CV tool which quickly assesses similarity and you want a second check to confirm that the highly similarity matches aren’t hitting some edge case failure mode.

One challenge is that you sometimes want to allow minor differences - think things like text aliasing or slight differences in the pixel values produced by different compression/color handling/etc. implementations - so there are some neat tools like pdiff which try to emphasize differences which the human visual system is sensitive to:

https://github.com/hectorgon/perceptual-diff

Visual regression testing is a common example, especially with websites.

I've put a few simple examples in Node.js here: https://github.com/umaar/learn-browser-testing/tree/master/3... (just as learning material)

judging the effectiveness of an exercise or supplement program by comparing before and after images of a participant.

A bit meta and very cruddy - a cheap and cheerful ruby tool I whipped up back in 2014 that would render two websites and then diff them.

It was achieved by looping over every RGB pixel from the PNG rendered image of each URL.

https://github.com/sammcj/urldiff

Not exactly something I'm proud of, but the pixel loop solution did make me laugh at the time.

For those interested, I created a gem in Ruby for comparing the similarity of images by computing the dhash of an image and then calculating the Hamming distance between the hashes: https://github.com/rohanpatel2602/ruby-dhash

You should probably provide instructions as to how to build it. The build.sh script does not work for me because cmd/main.go is not in GOROOT. go run main.go and go build inside the cmd/ directory works though.

I am really used to just being able to do go build from the root directory of the repository.

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

Would it be possible to compare image files before decompression ? For JPEG, directly compare the DCT coefficients

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 :)

gm compare -metric mse ./a.jpeg ./b.jpeg -file ./difference.png

I solved this problem for my use case by using an approximate diff.

Basically diffing took too long ( I was diffing to remove duplicate frames from a virtualized browser to browser screencast ), so after trying to various options (hashing, diffs, etc) I just went with a simple check of a basically random but fixed set of pixels, which worked really well. I don't have data on the actual false positives/ negatives but for the thing important in my case, perceptual difference and not sending the same frame twice (to save bandwidth and speed) it worked great, and was "constant time".

The "code" is here: https://github.com/c9fe/ViewFinder/blob/84620bd87abb32b2f2c3...

And a demo of the project is: https://demo.browsergap.dosyago.com (if you check it on Safari mobile you need to plant your clicks about half a finger under where you think they should go, some bug!)

I'd like to know some idea of how this posted fast diff works. I checked around the repo and couldn't figure it out, but it seems to be splitting across multiple cores, but still looping over each pixel (but divided by the number of cores). I thought it might be doing something like checking 64-bit blocks somehow, but seems not.

Did you try using any exotic wide instructions, like AVX or something?

No I didn't and my case didn't need it, but I was thinking maybe that's what this posted fast diff did, but I took a quick look at the go code and couldn't figure out if it did or not.

Edit on the above: it should say "fixed set of bytes" not "fixed set of pixels"

Looks like a for loop iterating over each pixel one row at a time.

What makes this fast?

Dunning-Kruger syndrome, probably.

It's fastest because others are slower. It doesn't necessarily mean it's fast :)

It does at least parallelize the work across available cores.

This is the line that makes the difference:

https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdif...

Reply on news.ycombinator.com