2853: Spot The Difference: Auto-Correlation Edition

|< < Prev Comic #2853 (2017-03-11) Next > >|

Spot The Difference: Auto-Correlation Edition

Made by: Alien@System

Explanation

This comic is unexplained. If you can edit this page to provide an explanation, please do!

The author writes:

Here we see the results of two different full Garfield strips when auto-correlated. One of them is the infamous 2013 birthday strip, which is pretty close to copy and paste in all three panels. The other is from the 1989 Halloween special and doesn't even have a ledge in common between the three panels. Guess which auto-correlation corresponds to which.

To those among you who have been wondering about the efficiency of the cross-correlation algorithm described in my previous entry: after all, multiplying the pixels of one image (N) with the corresponding of the other and doing that for every possible shift (also N), we get a runtime of O(N²), which isn't good. Okay, it's still polynomial, but for large pictures, it's obviously unfeasible, as N itself usually grows quadratically, too.

Fortunately, maths has a solution for us: Fourier transformations, which we should know from SRoMG #43. It turns out that, due to some freaky maths reasons, a convolution in real space is a multiplication in Fourier space. A convolution is an operation very similar to the cross-correlation, in fact it can be described as "cross-correlation, except you turn one of the pictures on its head beforehand". Even if it might seem counter-intuitive, convolutions are actually more common in mathematics than cross-correlations, but important to us now is: Fourier transformations can be done pretty quickly with the right algorithm, in O(N log(N)) time. So we just need to Fourier transform both images, multiply them, then transform them back (the "turn picture on head" difference between convolution and cross-correlation turns into a sign difference in Fourier space, so we don't need additional time for that, either). All in all, O(N log (N)), an improvement over the "stupid" algorithm. It's also how I calculated all these pictures, and it didn't take more than one minute for each on my home computer.

Original strips: 1989-10-24, 2013-06-19.

Transcript

{An image in two halves. The top half is mostly black, with a white central spot and some clearly-defined whitish lines running horizontally and vertically. The bottom half has those same whitish lines but is overall much whiter, with three irregularly shaped grey patches roughly where the panels of a Garfield strip would fall.}

Trivia

This strip's author's notes were hit with mojibake errors in a later site recoding effort; the original author's notes unaffected by mojibake are currently lost to the public due to this.