10
$\begingroup$

I was making some gifs of Mobius transformations in Matlab, and some strange patterns began to appear. I'm not sure if a deeper knowledge of the filetype/algorithm is needed to understand this phenomenon, but I thought that there could perhaps be a purely mathematical explanation. The image is obtained by coloring the complex plane like a checkerboard, and then inverting it by taking the reciprocal of the complex conjugate. Here is the math psuedocode for the image with a given zoom $k$:

\begin{align} &\mbox{checkerboard}:\mathbb C \to\{\mbox{black},\mbox{white}\}\\ &\mbox{checkerboard}(z):=\begin{cases} \mbox{black} & \mbox{if }\lfloor\Im(z)\rfloor+\lfloor\Re(z)\rfloor\equiv 0\mod 2\\ \mbox{white} & \mbox{if }\lfloor\Im(z)\rfloor+\lfloor\Re(z)\rfloor\equiv 1\mod 2 \end{cases}\\ &\mbox{image} = \{z\in\mathbb C:|\Re(z)|,|\Im(z)|\leq 1\}\\ &\mbox{color}:\mbox{image}\to\{\mbox{black},\mbox{white}\}\\ &\mbox{color}(z):=\mbox{checkerboard}(k/\overline{z}) \end{align}

And here are the pictures for $k=1$, $k=50$, and $k=200$. The resolution of each picture is $1000\times 1000$. I have no background in signal processing, but I would be eager to learn things!

$k=1$

$k=50$

$k=200$

EDIT:

  • More specifically, why does the Moiré pattern 'sync up' with the resolution of the picture at certain points?
  • Can the Moiré pattern be predicted?
$\endgroup$
  • 2
    $\begingroup$ What you're seeing is aliasing. You're trying to depict an image with higher frequency components than your monitor allows, so you get aliases. en.wikipedia.org/wiki/Moiré_pattern $\endgroup$ – MBaz Mar 15 '17 at 21:32
  • 1
    $\begingroup$ MBaz, I'm looking for a mathematical explanation of why the aliasing pattern looks the way it does! $\endgroup$ – B H Mar 15 '17 at 21:34
  • 1
    $\begingroup$ Yes, the Moiré pattern can be predicted. Are you familiar with the Fourier transform? $\endgroup$ – Marcus Müller Mar 15 '17 at 21:37
  • $\begingroup$ Not enough to use it in this situation! $\endgroup$ – B H Mar 15 '17 at 21:38
  • 1
    $\begingroup$ Have to go to bed now, hope the roughly mathematical explanation below helps you – based on the guess that someone with the cardinality of a countable infinite set might more or less be interested in a rather abstract view than in a functionally-analytical explanation. $\endgroup$ – Marcus Müller Mar 15 '17 at 22:11
13
$\begingroup$

You'll need to understand the sampling theorem. In short, each signal has what we call a spectrum¹, which is the Fourier transform of the signal as it comes in time domain (if it is a time signal), or spatial domain (if it is a picture. Since the Fourier transform is bijective, a signal and its transform are equivalent; in fact, one can often interpret the Fourier Transform as change of basis. We call that "conversion to frequency domain", since the Fourier transform's values for low ordinates describe the things that change slowly in the original (time or spatial) domain signal, whereas high-frequency content is represented by Fourier transform values with high position.

Generally, such spectra can have a certain support; the support is the minimal interval outside of which the spectrum is 0.

If you now use an observing system whose ability to reproduce frequencies is limited to an interval that is smaller than said support (which often is infinite, by the way, and always is infinite for signals that have finite extension in time or space), you can not represent the original signal with that system.

In this case, your picture has a certain resolution – which is, in the end, the fact that you evaluate the value of your function at discrete points in a fixed, non-infinitesimal spacing. The inverse of that spacing is the (spatial) sampling rate.

Thus, your picture cannot represent the original signal – it's simply mathematically impossible that the mapping of underlying function to pixels is truly equivalent to the original function, since we know that in this case, the total range of frequencies representable by your evaluation at discrete points ("sampling") is half the sampling rate, and thus, something must go wrong with the part of your signal's spectrum that is above half the sampling rate.

What happens is, in fact, that the spectrum gets aliases – every spectral component at a frequency $f_o \ge \frac{f_\text{sample}}{2}$ gets "shifted" down by $n\cdot f_\text{sample},\, n\in \mathbb Z$, so that $|f_o-nf_\text{sample}| < \frac{f_\text{sample}}{2}$. In effect, that leads to "structure" where there (feels like) shouldn't be some.

Take the "large" structures from your picture that I've painted green:

Aliasing

It certainly looks like there is low-frequency content here - but in reality, it's just the high-frequecy content at frequencies $>\frac{f_\text{sample}}2$ that got aliased to low frequencies, since it was close to an integer multiple of the sampling rate.

So, yes, you can predict the artifacts that happen to a 2D signal when being sampled by comparing its Fourier transform to the bandwidth offered by the sampling rate.


¹ this might be different from the spectrum as used in linear algebra to describe the Eigen-properties of operators.

$\endgroup$
  • $\begingroup$ Neato!! Thanks so much for this detailed answer. It seems like the behavior of each of the green bits is a little different and I'm guessing it depends on the value of $n$. I've gotta read up on this whole Fourier transform thing!! $\endgroup$ – B H Mar 15 '17 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.