# Editing a Picture in Fourier Space The `image-dft` applet on the Fourier Transforms page comes back from the spectrum in four fixed ways. Here you decide which Fourier coefficients to keep. Erase some of them, take the inverse transform, and look at what is left of the picture and at what you took out. ## The idea A picture is an $n \times n$ array $f(m, m')$, with $m$ the row (counted down) and $m'$ the column (counted across). Its two-dimensional discrete Fourier transform is $ F(p, q) = \sum_{m=0}^{n-1}\sum_{m'=0}^{n-1} f(m, m')\,e^{-2\pi i (q m + p m')/n}, $ where $p$ counts cycles per image across and $q$ counts cycles per image down. The inverse transform gives the picture back exactly: $ f(m, m') = \frac{1}{n^2}\sum_{p}\sum_{q} F(p, q)\,e^{2\pi i (q m + p m')/n}. $ Editing in Fourier space means choosing a **mask** $M(p, q)$, a number between 0 and 1 for each coefficient, and coming back with $ g = \text{inverse transform of } M F . $ Setting $M = 0$ at a point zeros that coefficient, and $M = 1$ keeps it. Because the transform is linear, what you took out is the inverse transform of the rest: $ f - g = \text{inverse transform of } (1 - M) F . $ Three facts about $F$ do most of the explaining. - **The centre is the mean.** $F(0, 0) = \sum f(m, m')$, so zeroing it alone subtracts the average brightness from every pixel and changes nothing else. - **A real picture has a mirror-symmetric spectrum.** If $f$ is real then $F(-p, -q) = \overline{F(p, q)}$, with the indices taken mod $n$. A cosine is two complex exponentials, $\cos\theta = \tfrac12(e^{i\theta} + e^{-i\theta})$, so every pattern in the picture shows up twice in the spectrum, once on each side of the centre. If you erase a point and not its mirror image, $g$ comes back complex. - **Energy adds up (Parseval).** $\sum |g|^2 = \frac{1}{n^2}\sum |M F|^2$, so the share of $\sum |F|^2$ you keep is the share of $\sum f^2$ that survives in $g$. ## The applet <div class="applet" data-applet="fourier-edit"></div> The large panel is $\log(1 + |F(p, q)|)$ with $(0, 0)$ in the centre, and red marks where $M = 0$. Hover over it to read $(p, q)$, $|F|$ and $M$ at that point. Paint on it with **erase** to zero coefficients or with **restore** to put them back. The brush radius goes down to a single point. With **mirror each edit through the centre** ticked (the default), every stroke is also made at $(-p, -q)$, and a dashed circle shows where. The **start the mask from** row gives the standard shapes, each with a sharp or a smooth edge: | shape | keeps | |---|---| | low-pass disk | $\rho \le r$, where $\rho = \sqrt{p^2 + q^2}$ | | high-pass | $\rho > r$ | | ring | $r_1 < \rho \le r_2$ | | rectangle | $\lvert p\rvert \le a$ and $\lvert q\rvert \le b$ | | ellipse | $(p/a)^2 + (q/b)^2 \le 1$ | | wedge of directions | frequencies within a half-width of the direction $\theta$, plus $F(0, 0)$ | The smooth low-pass is $M = 2^{-(\rho/r)^2}$, which equals $\tfrac12$ at $\rho = r$. With a smooth edge the rectangle and the ellipse are the same mask, $M = 2^{-(p/a)^2 - (q/b)^2}$. Choosing a shape, or moving its sliders, starts the mask over, and you can paint on top of it afterwards. Below the spectrum, the left panel is $g$. Press and hold it to see the original. The right panel is what was taken out, $f - g$, with mid-grey meaning 0. You can switch the right panel to the original instead. When $g$ goes outside the range 0 to 1, **stretched to fit** rescales the grey levels so you can see all of it. The readout gives the share of coefficients kept and the share of energy kept, once with $F(0, 0)$ and once without (the mean usually holds most of the energy, which hides everything else). It also gives the RMS difference between $g$ and $f$ and says whether $g$ is real. **rectangle** and **ellipse** draw a white shape on black with a width, height and tilt you set (the width and height are in pixels and even, so at tilt 0 a rectangle 120 wide covers exactly 120 columns). **a letter** draws any capital, small letter or digit in bold type, chosen from the dropdown. Your own picture works too. Use **your own picture**, or drop a file on the spectrum. It is cropped to a square, made grey and resampled to $256 \times 256$ in your browser, and nothing is uploaded anywhere. ## Worked examples **Removing stripes.** The default picture is the test card with stripes added, $0.1 + 0.8\,c(m, m') + 0.1\cos\bigl(2\pi(24 m' + 10 m)/256\bigr)$. The stripes are two bright dots at $\pm(24, 10)$, each of size $\tfrac12 \cdot 0.1 \cdot 256^2 = 3276.8$. Hover reads $3291$ there, because the card has a small term of its own at that point. Erase the two dots with the brush at one point: the stripes go, and $g$ is within RMS $0.0006$ of the card without stripes, where the striped picture was $0.0707$ away. The $0.0006$ left over is the card's own term at those two points, removed along with the stripes. A brush of radius 4 zeros 98 coefficients and still leaves only $0.0034$. **Zeroing only the centre.** Set the brush to one point and erase $F(0, 0)$. Then $g = f - \bar f$ to round-off, $4 \times 10^{-15}$. On the 0 to 1 grey scale every pixel darker than the average goes black, and **stretched to fit** shows that nothing else changed. **Sharp and smooth low-pass on the square.** With a sharp disk of radius 16, $g$ runs from $-0.11$ to $1.18$. With a smooth disk of the same radius, $g$ stays between 0 and 1 to within $10^{-8}$. ## Things to try 1. Start from the test card with stripes. Find the two dots that make the stripes and erase them. Why are there two? > [!success]- Answer > The stripes are one cosine, and a cosine is the sum of $e^{i\theta}/2$ and $e^{-i\theta}/2$. The first is the dot at $(24, 10)$ and the second is the dot at $(-24, -10)$. A real picture always has $F(-p, -q) = \overline{F(p, q)}$, so its spectrum is symmetric through the centre and patterns come in pairs. Erasing both dots takes $g$ to within RMS $0.0006$ of the picture without stripes. 2. Move **cycles across** to 24.5 and try again. Erasing the two dots no longer works. Why not? What does the spectrum look like near $(24.5, 10)$? > [!success]- Answer > 24.5 cycles do not fit across the picture, so the stripe pattern jumps where the right edge meets the left edge (the DFT treats the picture as repeating). That jump spreads the stripes along the whole row $q = \pm 10$ as a streak, the same sinc as for the rect pulse. The two points nearest the peak take the RMS error only from $0.0707$ to $0.0545$. Along that row, 97.5% of the stripe energy lies within 8 of the peak, and a disk of radius 8 brings the error to $0.0144$, but it also takes 0.46% of the card's own variation with it. Stripes in a real scan almost never fit the picture exactly, which is why removing them is never perfectly clean. 3. Untick **mirror each edit through the centre** and erase a small patch on one side of the centre only. The readout says $g$ is complex. Why? Look at **Im g**. > [!success]- Answer > The picture $f$ is real only because every coefficient $F(p, q)$ comes with its conjugate at $(-p, -q)$, and the two together add up to a real cosine. Removing one partner leaves a lone complex exponential, so $g$ has an imaginary part. In the test, erasing a patch of 29 coefficients at $(20, 10)$ gave $|\operatorname{Im} g|$ up to $0.017$. **Im g** shows the stripes of that frequency, strongest where the picture had edges running that way. With the mirror on, the same patch zeros 58 coefficients and $g$ is real to $2 \times 10^{-16}$. 4. Choose the **square**, then **low-pass disk** with a sharp edge and radius 16. Look at $g$ near the edges of the square, using **stretched to fit**. Where is the overshoot largest? > [!success]- Answer > $g$ rings on both sides of every edge, going below 0 and above 1. This is the Gibbs effect from the Fourier series page, now in two dimensions. The largest value is $1.179$, which is 18% of the jump, and it sits just inside a **corner**, where two edges meet. Across the middle of an edge the peak is $1.104$. A one-dimensional brick-wall filter at the same cutoff on a single row gives $1.079$, and as the cutoff grows this goes to the familiar 9%. Making the disk bigger does not get rid of the overshoot. At radius 32 the corner peak is still $1.175$, just closer to the edge. > > The **rectangle** with $a = b = 16$ shows why corners are worse. A box keeps $\lvert p\rvert \le a$ and $\lvert q\rvert \le b$, which is a one-dimensional cut along every row followed by one down every column. For the square, which is itself a product of a row profile and a column profile, $g$ is exactly the product of the two one-dimensional results (checked to $7 \times 10^{-15}$). Each one-dimensional result peaks at $1.0787$, so the corner peaks at $1.0787^2 = 1.1637$. 5. Switch the same disk to a **smooth edge**. What happened to the ringing? The readout names a blur. What is it? > [!success]- Answer > The ringing is gone. $g$ stays between 0 and 1 to within $10^{-8}$. The smooth disk $M = 2^{-(\rho/r)^2}$ is a Gaussian, and multiplying the spectrum by a Gaussian is the same as convolving the picture with a Gaussian: a Gaussian blur of > $\sigma = \frac{n\sqrt{\ln 2}}{\sqrt 2\,\pi\,r} \text{ pixels},$ > wrapped around at the edges of the picture. For $r = 20$ that is $\sigma = 2.40$ px, and $g$ agrees with a direct Gaussian convolution to $1.3 \times 10^{-8}$. The sharp edge is what made the ringing. A hard cut in $F$ is a sinc in the picture, and a sinc has negative lobes. This is the same Gaussian blur as on the page *Blurring, Edges, and Nonlinear Diffusion*, where it came from diffusion. 6. Choose the test card and **high-pass** with radius 16. What survives, and why is most of $g$ black on the 0 to 1 scale? > [!success]- Answer > The high-pass removes $F(0, 0)$ along with everything slow, so $g$ has mean 0 and swings either side of it. On the 0 to 1 scale everything below 0 is black. With **stretched to fit**, what is left is the edges and the fine texture: the outlines of the mountains, the sun, the square and the letter, and the black and white blocks. The smooth parts (the sky gradient, the flat colours) are gone. Only 1.3% of $\sum |F|^2$ is kept, and the picture is still recognisable from its edges. 7. The spectrum of the test card has a bright cross along the two axes $p = 0$ and $q = 0$. Predict what erasing both axes, but not the centre, would do to the picture. > [!success]- Answer > The coefficients on the axis $p = 0$ describe how the picture varies **down** the page when every row is averaged across, and those on $q = 0$ describe how it varies across when every column is averaged down. Erasing both axes, while keeping $F(0, 0)$, subtracts from every row its own average and from every column its own average, then adds back twice the overall mean. This was checked to $3 \times 10^{-15}$. On the test card those 510 coefficients hold 44.7% of the energy outside $F(0, 0)$. Most of the cross is the picture's own horizontal and vertical structure: the sky getting lighter down the page, the edges of the red square and of the blocks. Very little of it is the jump at the edges where the picture wraps around, about 0.3% of the energy by the periodic-plus-smooth decomposition (Moisan 2011). The cross is not an artifact to throw away. It is a large part of this picture. 8. Choose **wedge of directions** with $\theta = 90°$ and a half-width of 15°. Which edges in the test card survive? Then turn $\theta$ to 0°. > [!success]- Answer > At $\theta = 90°$ the wedge keeps frequencies pointing up and down the page, which describe variation down the picture. Those come from **horizontal** edges, such as the top and bottom of the red square and of the blocks. Vertical edges, such as the sides of the blocks, mostly disappear, and the sloping sides of the mountains fade. At $\theta = 0°$ the opposite happens. This is the rule from the Fourier Transforms page run backwards: an edge in the picture makes a streak in the spectrum perpendicular to the edge, so keeping only one direction of streak keeps only one direction of edge. 9. Choose the test card and an **ellipse** with half-widths $a = 40$ across and $b = 10$ down, sharp edge. Which edges stay sharp, and which blur? Then switch to a smooth edge and compare it with the smooth **rectangle** with the same $a$ and $b$. > [!success]- Answer > The ellipse keeps frequencies up to 40 cycles across but only up to 10 down, so $g$ keeps fine detail across the picture and loses it down the picture. Vertical edges, such as the sides of the blocks and the stem of the F, stay sharp. Horizontal edges, such as the top and bottom of the red square, blur and ring. It keeps 1249 coefficients, close to the area $\pi a b \approx 1257$, where the rectangle with the same $a$ and $b$ keeps $81 \times 21 = 1701$. With smooth edges the two shapes give the same mask, $2^{-(p/40)^2 - (q/10)^2}$, and the same $g$ to the last digit. That mask is a Gaussian blur of $\sigma = 1.20$ px across and $4.80$ px down. 10. Choose the **ellipse** picture, 120 pixels wide and 60 tall, tilt 0, with the mask on **keep everything**. Hover along the $p$ axis and then along the $q$ axis. How do the two compare? Then tilt the picture. > [!success]- Answer > The spectrum is an ellipse too, but turned the other way: twice as **tall** as it is wide. $|F(1, 0)| = 4264$ and $|F(0, 2)| = 4263$, $|F(2, 0)| = 1376$ and $|F(0, 4)| = 1375$, so going out $p$ across is the same as going out $2p$ down. A long picture direction is a short spectrum direction, the same rule as for the rect pulse, where a wider pulse has a narrower sinc. The continuous transform of a filled ellipse with half-axes $A$ across and $B$ down is $2\pi A B\,J_1(k)/k$ with $k = \sqrt{(A\omega_x)^2 + (B\omega_y)^2}$, whose first dark ring crosses the axes at $p = 2.60$ and $q = 5.20$ for $A = 60$, $B = 30$. The applet's $|F|$ agrees with it to 0.3% of the peak wherever it is above a tenth of the peak. Tilting the picture turns the whole spectrum by the same angle in the same direction. For the **rectangle** 120 by 40 tilted 30°, $|F|$ matches the rotated-bar formula from the Fourier Transforms page turned $+30°$ to 0.1% of the peak, and it misses by 68% if the formula is turned the other way. At tilt 0 the rectangle's transform is exact, $|F(p, q)| = \left|\dfrac{\sin(120\pi p/256)}{\sin(\pi p/256)}\right| \left|\dfrac{\sin(40\pi q/256)}{\sin(\pi q/256)}\right|$, the discrete version of the sinc, with zeros every $256/120 \approx 2.13$ across and $256/40 = 6.4$ down. ## Credits The idea of editing a spectrum by hand and transforming back (a notch filter for stripes, low-pass and high-pass masks) is standard in image processing. The test card is the one from the `image-diffusion` applet. The periodic-plus-smooth decomposition used in answer 7 is from L. Moisan, *Periodic plus smooth image decomposition*, Journal of Mathematical Imaging and Vision 39 (2011).