The Laplacian, LoG and Zero-Crossings

The Laplacian marks an edge where a curve changes sign, and blurring the picture first sets how large an edge you care about. Below, the blur grows from 1 to 8 pixels and back, and the white curves are where the result changes sign.

The same second derivative shows up in:

• Sharpening, where subtracting a Laplacian from a photo makes its edges steeper.
• Blur detection: the variance of the Laplacian is a common test for whether a photo is in focus.
• Blob detectors that count cells in a microscope image, which look for the scale at which the Laplacian of Gaussian responds most.
• SIFT, whose difference of Gaussians is a cheap stand-in for the Laplacian of Gaussian (unit 3.3).

The second derivative crosses zero at an edge, so it places the edge without any thinning, at the price of being far more sensitive to noise. The naive Laplacian turns one edge on nine pixels disturbed by 0.03 into four sign changes. Marr and Hildreth build the smoothing into the operator, and on a real photo that takes the noise-made crossings from 2.76× to 1.02×.

Where we are

Lesson 4 of the Edge Detection unit: the alternative at the pipeline’s measuring step. Canny located each edge by thinning the gradient ridge to its peak and linking what survived; that took two extra steps. A zero-crossing gives the position from one division between two samples, with no ridge to thin. Lesson 1 already showed the second derivative crossing zero at an edge; this lesson builds the operator and measures what it costs.

Zero instead of peak

The discrete second derivative of a row is the three-tap kernel $[1, -2, 1]$:

In two dimensions the same idea adds the vertical term, which is the Laplacian: one number per pixel, with no direction attached. That is the trade against lesson 2: the gradient gave a magnitude and an orientation, the Laplacian gives only a sign, and the edge is wherever that sign flips.

Now you try

Set the model to roof and watch the second derivative produce a sign change on each flank while the first derivative crosses zero at the ridge. Then raise the noise with smoothing at zero and read the counter.

And the 2-D operator on a grid, one window at a time:

The smoothing was never optional

Take lesson 1’s noisy row, the one disturbed by no more than 0.03, and apply $[1, -2, 1]$ directly:

The signs run + - + - - - +, which is four sign changes for a row containing one edge. A second derivative doubles the exponent on noise, so a single stray pixel produces a crossing pair on its own.

Smooth first with $[1, 2, 1]/4$ and apply the same kernel:

One sign change, between columns 4 and 5. Three spurious crossings gone for the cost of one three-tap average. Interpolating as before puts it at $4 + 0.0075 / 0.16 = 4.05$, which is 0.05 pixels from where the clean row put it (exactly 4). Noise of this size moves the smoothed crossing by a twentieth of a pixel; what it does to the unsmoothed one is add crossings.

There is an identity hiding here. Smoothing with $[1,2,1]/4$ and then applying $[1,-2,1]$ composes to $[1, 0, -2, 0, 1]/4$, which is exactly the central difference from lesson 1 applied twice. The second-difference table in lesson 1 and the smoothed table above are the same numbers because they are the same operator. Taking a derivative twice by central differences already smooths; the naive $[1,-2,1]$ is the version that does not, which is why it behaves so much worse.

Marr and Hildreth’s move was to make that choice explicit and tunable: convolve with a Gaussian of your chosen $\sigma$, then take the Laplacian [1]. Because both are linear, the pair collapses into one kernel, the Laplacian of Gaussian.

How close is this to OpenCV?

The 2-D Laplacian is four neighbours minus four times the centre, which is one line of NumPy slicing. cv2.Laplacian with ksize=1 uses the same 3x3 kernel. The shape to try it on is a white disc, where the answer is known before running anything: zero inside and outside, positive on the dark side of the rim, negative on the bright side.

The Laplacian in NumPy Reset ▶ Run

import numpy as np
import cv2

img = np.zeros((160, 160), np.float32)
cv2.circle(img, (80, 80), 50, 1, -1)

def laplacian(a):
    # up + down + left + right - 4 x centre
    return (a[:-2, 1:-1] + a[2:, 1:-1]
            + a[1:-1, :-2] + a[1:-1, 2:]
            - 4 * a[1:-1, 1:-1])

lap = laplacian(img)
show((lap + 1) / 2, "grey 0, white +, black -")
print("ours:", lap.shape)

Output

ours: (158, 158)

ref = cv2.Laplacian(img, cv2.CV_32F, ksize=1)
diff = np.abs(lap - ref[1:-1, 1:-1]).max()
print("OpenCV:", ref.shape, " max diff:", diff)

spots = {"centre": (80, 80),
         "rim, bright side": (80, 130),
         "rim, dark side": (80, 131),
         "background": (80, 150)}
for name, (r, c) in spots.items():
    print(f"{name:17} {ref[r, c]:+.0f}")

OpenCV: (160, 160)  max diff: 0.0
centre            +0
rim, bright side  -3
rim, dark side    +1
background        +0

Inside the image the two agree to the last bit. The disc’s rim is where the sign flips: negative on the last bright pixel and +1 on the first dark one, so the zero-crossing sits between columns 130 and 131 and nowhere else. The bright side reads −3 because (80, 130) is the tip of the disc, where three of its four neighbours are dark. On a drawn shape with no noise, that crossing is a closed curve, which is the property the table under “Where this breaks” shows a photograph does not keep.

In the wild

The case against the second derivative is easiest to make on a page of print, where you know roughly what the right answer is: two crossings per stroke, and nothing anywhere else.

Running the Laplacian over a 700 × 700 crop of an 1814 newspaper, and counting how many of its zero-crossings sit where the image is changing:

What it means: unsmoothed, 96.3% of the zero-crossings are not edges. They are the scan’s grain crossing zero, and the Laplacian cannot tell the difference because a sign change carries no notion of size. Smoothing to σ = 4 removes three quarters of them, and the share that are real only climbs from 3.7% to 6.0%. Smoothing suppresses the noise and the text together.

This is the argument for treating the LoG’s σ as a choice of scale more than as a cleanup, and for Canny being built on the first derivative, where a threshold on magnitude can throw away a weak edge that a sign test is blind to.

Where this breaks

Zero-crossings have two properties that no threshold can repair.

Every crossing weighs the same. The sign of $\nabla^2 I$ flips across a faint shadow on the base as it does across a column silhouette. Lesson 2’s magnitude told you how strong an edge was; a crossing tells you only that one is there. Ranking edges, which is what the next lesson depends on, is not available from this operator alone.

Smoothing controls the damage, and it costs structure. Measured on the canonical frame, adding noise of sigma 10 and counting zero-crossing pixels against the clean image:

At sigma 1.0 noise nearly triples the structure. At sigma 3.0 it adds 2%, and the clean image is down to 8,161 crossing pixels from 25,625: about a third of the detail remains. The smoothing that removed the noise removed the other two thirds with it.

The last column is the one that contradicts the usual claim. Zero-crossings of a continuous Laplacian of Gaussian form closed contours, and that survives discretization on synthetic input: a rendered disc gives a closed fraction of 1.000 at every sigma tested. On a photograph it does not. Only 33.4% of the crossing components are closed at sigma 1.0, falling to 15.6% at sigma 3.0, since real contours run off the frame, meet at junctions, and get cut where the response is too flat to count. Closure is a property of the ideal operator, not of the edge map you get.

Exercises

1. Count crossings, and count an exact zero. Write crossings(r), which counts the sign changes in a 1-D response. A zero between a positive and a negative value is one crossing, as the worked example says. On the clean row’s $[1,-2,1]$ response it must return 1, and on the noisy row’s it must return 4.

def crossings(r):
    n = 0
    # count the sign changes in r
    return n

clean = np.array([0.0, 0.0, 0.3, 0.0, -0.3, 0.0, 0.0])
noisy = np.array([0.07, -0.05, 0.33, -0.02,
                  -0.26, -0.07, 0.07])
print(crossings(clean), crossings(noisy))

2. Predict, then run. Smooth the noisy row with $[1,2,1]/4$ first (np.convolve(r, [0.25, 0.5, 0.25], mode="valid")), apply $[1,-2,1]$, and count again. Write down the number before you run it.
3. Check the identity. The section above says that smoothing with $[1,2,1]/4$ and then applying $[1,-2,1]$ is the central difference from lesson 1 applied twice. Compose both pairs of kernels with np.convolve and compare.

Next

So the first derivative gives strength and thickness, and the second gives position and no strength, which is why Canny kept the gradient and added its two steps [2] [3]. Every operator so far returns curves, and a curve cannot say where along it you are. Lesson 5 branches off the gradient step to find points instead.

References

[1] Marr, D., & Hildreth, E. (1980). Theory of edge detection. Proceedings of the Royal Society of London B, 207(1167), 187-217. doi:10.1098/rspb.1980.0020

[2] Canny, J. F. (1986). A Computational Approach to Edge Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6), 679-698. doi:10.1109/TPAMI.1986.4767851

[3] Gonzalez, R. C., & Woods, R. E. (2018). Digital Image Processing (4th ed.), section 10.2 “Point, Line, and Edge Detection”, The Marr-Hildreth Edge Detector, p. 786. Pearson.

[4] Lowe, D. G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 60(2), 91-110. doi:10.1023/B:VISI.0000029664.99615.94