7 ms·
Imgdiff: Faster than the fastest pixel-by-pixel image difference tool
- ajfjrbfbf 6y agoWhy 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.
- detaro 6y agoDoes using the GPU pay off for one-off diffing? It's "obvious" that it makes sense for Gimp, but does it for this?
- ben-schaaf 6y agoCompared 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.
- formerly_proven 6y agoThe 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).
- eps 6y agoCompressed, but not as a single continuous block. The bottleneck will probably be in doing things serially, both with decompression and the disk IO.
- viraptor 6y agoEven before you get into GPU, it looks like you could do the normalisation here https://github.com/n7olkachev/imgdiff/blob/master/pkg/yiq/delta.go#L13 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.
- kaetemi 6y agoConsidering 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.
- amelius 6y agoI 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?
- kaetemi 6y agoYou'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.
- Kuinox 6y agoGPU can now directly read the file on the SSD.
- plasticchris 6y agoCitation needed? I know things have been announced but what's available now?
- harias 6y agoGPUDirect has been available for quite sometime now: https://developer.nvidia.com/gpudirect https://developer.nvidia.com/gpudirect
- dheera 6y agoI'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
- jihchi 6y agoWere you comparing two identical image? Could you try two different image?
- noahtallen 6y agoTo 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.
- acdha 6y agoYou 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.
- donatj 6y agoI'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?
- kripke 6y agoI 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).
- oefrha 6y agohttps://github.com/n7olkachev/imgdiff/blob/9b2a87e1b729c70b5d702cb9309a46b58ebd0190/pkg/imgdiff/imgdiff.go#L37-L38 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.
- esimov 6y agoI 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.
- watermelon59 6y agoYears 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.
- d76d6776yudsy 6y agomind blown
- nine_k 6y agoDid you know that ImageMagick includes an image diffing tool? https://imagemagick.org/script/compare.php https://imagemagick.org/script/compare.php
- canada_dry 6y ago...plus ImageMagick has a myriad of options.
- deleted 6y ago[deleted]
- systemvoltage 6y agoWhat are some of the common applications for diffing an image?
- fouronnes3 6y agoRegression testing image processing algorithms.
- vkou 6y agoDiff testing UIs.
- kaetemi 6y agoAutomated testing of a rendering engine.
- acdha 6y agoI’ve used them for regression testing web apps: https://github.com/python-needle/needle 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 https://github.com/hectorgon/perceptual-diff
- umaar 6y agoVisual 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-auditing/3-visual-testing/single-element https://github.com/umaar/learn-browser-testing/tree/master/3... (just as learning material)
- m463 6y agojudging the effectiveness of an exercise or supplement program by comparing before and after images of a participant.
- BuzzwordBingo 6y agoLooks like a for loop iterating over each pixel one row at a time. What makes this fast?
- srgpqt 6y agoDunning-Kruger syndrome, probably.
- viraptor 6y agoIt's fastest because others are slower. It doesn't necessarily mean it's fast :)
- time0ut 6y agoIt does at least parallelize the work across available cores.
- arendtio 6y agoThis is the line that makes the difference: https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdiff/imgdiff.go#L37 https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdif...
- franciscop 6y agoWhen 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.
- tobyhinloopen 6y agoThere are so many tools on github lacking screenshots or examples. It’s like they don’t want to sell their free content!
- woko 6y agoI 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-is-next.html#iii-20-min-create-good-readme https://ternaus.blog/tutorial/2020/08/28/Trained-model-what-...
- johnisgood 6y agoYou 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.
- chmod775 6y agoCompared 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.
- hinkley 6y agoWhen 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.
- drothlis 6y agoI 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 https://github.com/stb-tester/stb-tester -- we use it for regression testing of GUI screenshots.)
- drothlis 6y agoFor 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/sqdiff.c 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 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.
- graderjs 6y agoI 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/84620bd87abb32b2f2c3dc0b79a0be5212fa14ee/zombie-lord/screenShots.js#L9 https://github.com/c9fe/ViewFinder/blob/84620bd87abb32b2f2c3... And a demo of the project is: https://demo.browsergap.dosyago.com 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.
- filleokus 6y agoDid you try using any exotic wide instructions, like AVX or something?
- graderjs 6y agoNo 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"
- bloaf 6y agoThis feels like an application where an APL one-liner would just be the fastest thing that there is.
- alpb 6y agoWorth noting it's ~100-lines of Go code that's quite readable: https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdiff/imgdiff.go https://github.com/n7olkachev/imgdiff/blob/master/pkg/imgdif... https://github.com/n7olkachev/imgdiff/blob/master/pkg/yiq/delta.go https://github.com/n7olkachev/imgdiff/blob/master/pkg/yiq/de...
- ganstyles 6y agoThis 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?
- alpb 6y agoLikely 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.
- smcleod 6y agoA 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 https://github.com/sammcj/urldiff Not exactly something I'm proud of, but the pixel loop solution did make me laugh at the time.
- rohan404 6y agoFor 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 https://github.com/rohanpatel2602/ruby-dhash
- nairoz 6y agoWould it be possible to compare image files before decompression ? For JPEG, directly compare the DCT coefficients
- dingdingdang 6y agoCongratulations 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 :)
- petters 6y agoThis 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 https://news.ycombinator.com/item?id=25405595
- kimown 6y agogm compare -metric mse ./a.jpeg ./b.jpeg -file ./difference.png