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).
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.
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.
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).
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.
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:
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.
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):
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.
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].
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.
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.
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".
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.
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"
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.
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
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 :)
65 comments
[ 3.1 ms ] story [ 13.7 ms ] threadThere'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.
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.
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.
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?
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).
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.
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.
https://imagemagick.org/script/compare.php
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
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)
What makes this fast?
https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdif...
I am really used to just being able to do go build from the root directory of the repository.
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.
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):
Benchmark: (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.)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:
[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.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).
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...
> 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.
(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.
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.
Edit on the above: it should say "fixed set of bytes" not "fixed set of pixels"
https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdif...
https://github.com/n7olkachev/imgdiff/blob/master/pkg/yiq/de...
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.
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