# Blurring, edges, and nonlinear diffusion At the end of [[MATH310F26(Day 23) - Transport moves, diffusion spreads|Day 23]] we noticed that a single white pixel, run through the diffusion equation, turns into a bell curve, so every Gaussian blur is the diffusion equation at work. This page takes that seriously. The brightness $u$ of each pixel is a crowd of walkers. Every tick a walker hops to each of its four neighbours with probability $q$ and stays put with probability $ P_0 = 1 - 4q . $ The edges of the image are walls, so no brightness is lost. In the language of [[The Walk and Its Continuum Limit]] this is the three-move walk in each direction, with $D = 2q$ and $ \frac{\partial u}{\partial t} = \frac{D}{2}\left(\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2}\right) = \frac{D}{2}\,\nabla^2 u . $ Then we change the rule. What if a walker refuses to cross a steep jump in brightness? What if it moves differently in a crowd? Those walkers no longer ignore one another, and the equation stops being linear. <div class="applet" data-applet="blur-edges"></div> ## A blur is diffusion **One white pixel.** Choose **one white pixel** and run it. The row underneath is a bell curve that spreads and flattens. After $t$ steps each direction has variance exactly $Dt = 2qt$, so the picture is a Gaussian blur with $\sigma = \sqrt{2qt}$ pixels. **Against a real Gaussian blur.** With any image, the readout compares the walk with a Gaussian blur done directly, by convolution with a Gaussian of that $\sigma$. The dashed magenta curve in the row plot is that blur. How does the largest difference change as $t$ grows, and why is it largest at the start? **When it stops being a walk.** Push $q$ past $0.25$. Then $P_0 < 0$, which is not a probability, and within a few dozen steps the image erupts into a checkerboard. The condition that keeps this computer scheme stable, $q \le 1/4$, is the condition that the walk makes sense. ## Finding edges An edge is a place where the brightness changes quickly, so the simplest edge detector marks every pixel where $|\nabla u|$ is larger than a threshold. With **compare with the true edges** on, the edge map scores the detector against the edges of the clean image. White pixels were found and are real, orange were found but are not real, and magenta are real edges that were missed. The readout turns that into a score $F$ between $0$ and $1$. **Noise ruins it.** Start the shapes with some noise and look at the edge map at $t = 0$. Every noise speck is a steep jump, so it is found as an edge. **Blur first.** Run the plain blur and watch the orange score $F$ in the last plot. It rises quickly as the noise is averaged away, then falls as the edges themselves are smeared below the threshold. There is a best time to stop, and it comes early. The RMS error against the clean image (teal) has its own best time. Are they the same? **The Laplacian.** Switch the edge map to $\nabla^2 u$. It is positive on the dark side of an edge and negative on the bright side, and it crosses zero right at the edge. The yellow pixels are those zero crossings. This is a classic edge detector (Marr and Hildreth, 1980). Notice that $\nabla^2 u$ is exactly what the diffusion equation uses to update the image, so this edge map is the blur's own rate of change. ## Walkers that avoid steep jumps Choose **avoids steep jumps**. Now a walker crosses between two pixels whose brightness differs by $s$ with probability $q\,g(s)$, where $ g(s) = \frac{1}{1 + (s/K)^2} . $ Small jumps (noise in a flat region) are crossed almost freely, and large jumps (edges) are hardly crossed at all. In the continuum this is the Perona–Malik equation (1990), $ \frac{\partial u}{\partial t} = \nabla \cdot \big(g(|\nabla u|)\,\nabla u\big) . $ The middle plot shows the flux $s\,g(s)$, how much brightness moves across a jump of size $s$. It rises and then turns downhill at $s = K$. In the shaded part, a steeper jump moves less brightness than a gentler one, so steep edges get steeper. That is diffusion running backward, and it is why the edges sharpen instead of smearing. **Compare the two blurs.** Run the shapes with noise under each walker and compare the row plot and the edge map after the same number of steps. Then compare the two curves in the last plot. Which one makes the choice of stopping time less delicate? **The catch.** With no further help, a big enough noise speck is a steep jump too, so the walkers keep it, and sharpen it. Look for specks that survive, and for flat regions that turn into stair steps. The slider **judges the jump on a blur of σ** lets the walker look at a slightly blurred copy of the image when it decides whether to cross. The brightness still moves in the sharp image. Try $\sigma = 1$ and compare the edge score with the plain blur again. (This fix is due to Catté, Lions, Morel and Coll, 1992.) **The hop map.** Switch the edge map to **hop map**. It shows $g$ at each pixel, how freely walkers cross there. The black outlines are the walls the walkers built for themselves. That map is an edge detector in its own right. ## Walkers that notice the crowd Choose **notices the crowd**. Now a walker on a pixel of brightness $u$ hops with probability $q\,h(u)$. Redoing the Day 22 balance with that rule gives $ \frac{\partial u}{\partial t} = \frac{D}{2}\,\nabla^2\big(h(u)\,u\big), $ which spreads like ordinary diffusion with an effective diffusivity proportional to $\dfrac{d}{du}\big(h(u)\,u\big) = h(u) + u\,h'(u)$. That is the curve in the middle plot. **Busier in crowds**, $h = u^m$. Bright regions spread and dark regions barely move, so a bright patch grows with a sharp front instead of a soft Gaussian tail. This is the porous medium equation. **Slower in crowds**, $h = e^{-u/u^*}$. The effective diffusivity is $e^{-u/u^*}(1 - u/u^*)$, which is negative once $u > u^*$. Above that brightness the walkers gather instead of spreading. Run a letter and watch it break up into tight clusters. Why are the clusters the size of single pixels? ## Try it on your own picture The applet below takes any picture you give it. Upload one, or drop it on the left image. It stays in your browser and is never sent anywhere. Everything on this page fits one equation, $ \frac{\partial u}{\partial t} = \nabla\cdot\big(D\,\nabla u\big), $ and the only thing that changes is what the diffusivity $D$ is allowed to depend on. In walker terms, $D$ is how readily a walker hops at that spot. The buttons go up that ladder one step at a time. - **Nothing.** $D$ is the same everywhere, and the picture gets a Gaussian blur. - **The original's edges.** $D$ is computed once from the starting picture, small where it is steep and close to 1 where it is flat, and then held fixed. Walkers are held back at the edges that were there at the start. The equation is still linear. - **The steepness now.** The same rule, recomputed from the picture as it changes. This is Perona–Malik, and the equation is now nonlinear. - **The brightness.** $D$ depends on how bright the picture is where the walker stands, the crowd rules from above. In colour, the steepness counts a change in any of the three colour channels, so a red square on a blue sky is an edge even where the two have the same brightness. The right panel shows $D$ itself, black where walkers are held back. Press and hold the left image to see where it started, and download the result when you like it. <div class="applet" data-applet="image-diffusion"></div> ### What to try **Blur against Perona–Malik.** Add some noise, run the plain blur until the noise is gone, and look at what happened to the outlines. Then go back to the start and do the same with the steepness rule. **Fixed against recomputed.** Compare the original's edges with the steepness now on the same noisy picture. The fixed map was made from the noisy start, so look at the right panel and ask which specks it treats as edges. **What K means.** $K$ is the size of jump the walkers start to refuse. Make it small and watch which parts of your picture freeze. Make it large and watch it turn back into a blur. **The blur inside the rule.** Set the slider for σ to 0 on a noisy picture and run it. Then try 0.5 and 1. What does looking at a slightly blurred copy do to the decision, and what does too much of it cost? **The jump being crossed against the full |∇u|.** Run each on a picture with diagonal or curved edges and compare the outlines up close. **The crowd.** Choose the brightness and slower in crowds. Which parts of your picture break up into dots, and how does that line up with $u^*$?