{ "cells": [ { "cell_type": "markdown", "id": "61d224be", "metadata": {}, "source": [ "# Lesson 13: Second Derivatives and the Laplacian\n", "\n", "Lesson 12 found edges as *peaks* in the first derivative (gradient magnitude). This lesson uses the **second** derivative instead, where edges show up as **zero crossings** — the basis of the classic Marr-Hildreth edge detector. We then reuse the same blur-and-difference idea to build a **Laplacian pyramid**, which fixes the information-loss problem from Lesson 11's Gaussian pyramid." ] }, { "cell_type": "code", "execution_count": null, "id": "bdf9a010", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import cv2\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "id": "425965cb", "metadata": {}, "source": [ "## Why zero crossings? A 1D intuition\n", "\n", "Consider a single step edge along one row. The first derivative is a spike at the edge; the second derivative swings from positive to negative (or vice versa) and crosses exactly zero right at the edge location." ] }, { "cell_type": "code", "execution_count": null, "id": "46fe6a1c", "metadata": {}, "outputs": [], "source": [ "x = np.linspace(0, 10, 400)\n", "step = 1 / (1 + np.exp(-6 * (x - 5))) # a smoothed step, to keep derivatives well-defined\n", "first_deriv = np.gradient(step, x)\n", "second_deriv = np.gradient(first_deriv, x)\n", "\n", "fig, axes = plt.subplots(3, 1, figsize=(6, 6), sharex=True)\n", "for ax, y, title in zip(axes, [step, first_deriv, second_deriv],\n", " ['Intensity (step edge)', 'First derivative (peak at edge)', 'Second derivative (zero crossing at edge)']):\n", " ax.plot(x, y)\n", " ax.axvline(5, color='gray', linestyle='--', linewidth=1)\n", " ax.set_title(title, fontsize=10)\n", "if True:\n", " axes[2].axhline(0, color='red', linewidth=0.8)\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "30f25db3", "metadata": {}, "source": [ "## The Laplacian: a 2D second derivative\n", "\n", "The Laplacian sums the unmixed second partial derivatives of a 2D image:\n", "\n", "$$\\nabla^2 I = \\frac{\\partial^2 I}{\\partial x^2} + \\frac{\\partial^2 I}{\\partial y^2}$$\n", "\n", "Unlike the gradient, it's a single scalar at each pixel (no direction) — it just measures how much a pixel differs from the average of its neighbors. Two common discrete kernels:\n", "\n", "$$K_4 = \\begin{bmatrix}0&1&0\\\\1&-4&1\\\\0&1&0\\end{bmatrix} \\qquad K_8 = \\begin{bmatrix}1&1&1\\\\1&-8&1\\\\1&1&1\\end{bmatrix}$$\n", "\n", "$K_4$ uses only the 4-connected neighbors; $K_8$ also includes the diagonals for a stronger, more isotropic response." ] }, { "cell_type": "code", "execution_count": null, "id": "47469667", "metadata": {}, "outputs": [], "source": [ "img = np.zeros((150, 150), dtype=np.float64)\n", "cv2.rectangle(img, (30, 30), (100, 100), 200, -1)\n", "cv2.circle(img, (110, 110), 25, 120, -1)\n", "\n", "k4 = np.array([[0, 1, 0], [1, -4, 1], [0, 1, 0]], dtype=np.float64)\n", "lap = cv2.filter2D(img, cv2.CV_64F, k4)\n", "\n", "print('matches cv2.Laplacian?', np.allclose(lap, cv2.Laplacian(img, cv2.CV_64F, ksize=1)))\n", "\n", "fig, axes = plt.subplots(1, 2, figsize=(7, 3.5))\n", "axes[0].imshow(img, cmap='gray')\n", "axes[0].set_title('Original')\n", "axes[1].imshow(lap, cmap='coolwarm', vmin=-200, vmax=200)\n", "axes[1].set_title('Laplacian response\\n(red=positive, blue=negative)')\n", "for ax in axes:\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "3e5fdd61", "metadata": {}, "source": [ "Every edge produces a positive lobe on one side and a negative lobe on the other — the edge itself sits at the zero crossing between them." ] }, { "cell_type": "markdown", "id": "3eb00db7", "metadata": {}, "source": [ "## The Marr-Hildreth detector: Laplacian of Gaussian (LoG)\n", "\n", "The Laplacian, like any derivative, amplifies high-frequency noise — and a *second* derivative amplifies it even more than a first derivative does. Marr and Hildreth's fix (1980): **smooth first**, then take the Laplacian. Since convolution is associative, this is equivalent to convolving directly with a single combined kernel, the **Laplacian of Gaussian (LoG)**:\n", "\n", "$$\\text{LoG}_\\sigma(I) = \\nabla^2(G_\\sigma * I) = (\\nabla^2 G_\\sigma) * I$$\n", "\n", "Edges are then found as **zero crossings** of the LoG response, rather than by thresholding its magnitude directly." ] }, { "cell_type": "code", "execution_count": null, "id": "118bccd2", "metadata": {}, "outputs": [], "source": [ "rng = np.random.default_rng(1)\n", "disk = np.zeros((150, 150), dtype=np.float64)\n", "cv2.circle(disk, (75, 75), 50, 255, -1)\n", "noisy_disk = np.clip(disk + rng.normal(0, 10, disk.shape), 0, 255)\n", "\n", "sigma = 2.0\n", "log_response = cv2.Laplacian(cv2.GaussianBlur(noisy_disk, (0, 0), sigmaX=sigma), cv2.CV_64F, ksize=3)\n", "\n", "\n", "def zero_crossings(response, threshold=4.0):\n", " \"\"\"Mark a pixel as an edge if it's adjacent to a sign change of at least `threshold` magnitude.\"\"\"\n", " edges = np.zeros_like(response, dtype=np.uint8)\n", " shifts = [(0, 1), (1, 0), (1, 1), (1, -1)]\n", " for dy, dx in shifts:\n", " shifted = np.roll(np.roll(response, dy, axis=0), dx, axis=1)\n", " sign_change = (response * shifted < 0) & (np.abs(response - shifted) > threshold)\n", " edges |= sign_change.astype(np.uint8)\n", " return edges * 255\n", "\n", "log_edges = zero_crossings(log_response)\n", "\n", "fig, axes = plt.subplots(1, 3, figsize=(10, 3.5))\n", "for ax, im, title in zip(axes, [noisy_disk, log_response, log_edges],\n", " ['Noisy input', 'LoG response', 'Zero crossings\\n(Marr-Hildreth edges)']):\n", " ax.imshow(im, cmap='gray' if title != 'LoG response' else 'coolwarm')\n", " ax.set_title(title, fontsize=9)\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "8b0d8d43", "metadata": {}, "source": [ "### The cheaper approximation: Difference of Gaussians (DoG)\n", "\n", "Computing a true LoG kernel is more expensive than blurring. A widely used shortcut: the *difference* of two Gaussian blurs at slightly different scales approximates a scaled LoG:\n", "\n", "$$\\text{DoG} = G_{\\sigma} - G_{k\\sigma} \\;\\approx\\; -(k-1)\\sigma^2 \\cdot \\text{LoG}_\\sigma$$\n", "\n", "This is the same building block later reused by SIFT for keypoint detection at multiple scales." ] }, { "cell_type": "code", "execution_count": null, "id": "3fac7420", "metadata": {}, "outputs": [], "source": [ "k = 1.6\n", "g_sigma = cv2.GaussianBlur(noisy_disk, (0, 0), sigmaX=sigma)\n", "g_ksigma = cv2.GaussianBlur(noisy_disk, (0, 0), sigmaX=sigma * k)\n", "dog = (g_ksigma - g_sigma) / ((k - 1) * sigma**2)\n", "\n", "correlation = np.corrcoef(log_response.ravel(), dog.ravel())[0, 1]\n", "print(f'correlation between LoG and scaled DoG: {correlation:.3f}')\n", "\n", "fig, axes = plt.subplots(1, 2, figsize=(7, 3.5))\n", "axes[0].imshow(log_response, cmap='coolwarm', vmin=-30, vmax=30)\n", "axes[0].set_title('LoG')\n", "axes[1].imshow(dog, cmap='coolwarm', vmin=-30, vmax=30)\n", "axes[1].set_title('DoG (scaled)')\n", "for ax in axes:\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "ffad9753", "metadata": {}, "source": [ "The two are highly correlated but not identical — DoG is an approximation, not an exact substitute, but a much cheaper one (two blurs and a subtraction vs. an explicit second-derivative kernel)." ] }, { "cell_type": "markdown", "id": "2f72c1bc", "metadata": {}, "source": [ "## Laplacian pyramids: recovering what Gaussian pyramids throw away\n", "\n", "Lesson 11 showed that a Gaussian pyramid loses information: blurring and downsampling repeatedly, then trying to upsample back, doesn't reconstruct the original. A **Laplacian pyramid** fixes this by storing, at each level, exactly the detail that would otherwise be lost — the *difference* between a Gaussian level and the coarser level upsampled back to match it. That difference is a discrete approximation of the Laplacian, which is why it shares the name." ] }, { "cell_type": "code", "execution_count": null, "id": "a2368682", "metadata": {}, "outputs": [], "source": [ "def gaussian_pyramid(image, num_levels):\n", " pyramid = [image]\n", " current = image\n", " for _ in range(num_levels - 1):\n", " current = cv2.pyrDown(current)\n", " pyramid.append(current)\n", " return pyramid\n", "\n", "\n", "def laplacian_pyramid(gauss_pyramid):\n", " lap_pyramid = []\n", " for i in range(len(gauss_pyramid) - 1):\n", " size = (gauss_pyramid[i].shape[1], gauss_pyramid[i].shape[0])\n", " upsampled = cv2.pyrUp(gauss_pyramid[i + 1], dstsize=size)\n", " detail = gauss_pyramid[i].astype(np.int16) - upsampled.astype(np.int16)\n", " lap_pyramid.append(detail)\n", " lap_pyramid.append(gauss_pyramid[-1].astype(np.int16)) # the smallest level: no finer detail to subtract\n", " return lap_pyramid\n", "\n", "\n", "def reconstruct_from_laplacian(lap_pyramid):\n", " current = lap_pyramid[-1]\n", " for i in range(len(lap_pyramid) - 2, -1, -1):\n", " size = (lap_pyramid[i].shape[1], lap_pyramid[i].shape[0])\n", " upsampled = cv2.pyrUp(current, dstsize=size)\n", " current = upsampled + lap_pyramid[i]\n", " return np.clip(current, 0, 255).astype(np.uint8)\n", "\n", "\n", "photo = np.zeros((256, 256, 3), dtype=np.uint8)\n", "photo[:] = (40, 40, 40)\n", "cv2.circle(photo, (128, 128), 90, (255, 120, 30), -1)\n", "cv2.rectangle(photo, (30, 30), (110, 110), (30, 200, 255), -1)\n", "\n", "g_pyr = gaussian_pyramid(photo, num_levels=5)\n", "l_pyr = laplacian_pyramid(g_pyr)\n", "\n", "fig, axes = plt.subplots(1, len(l_pyr), figsize=(13, 3))\n", "for ax, level in zip(axes, l_pyr):\n", " display = np.clip(level.astype(np.int32) + 128, 0, 255).astype(np.uint8) # shift for visibility\n", " ax.imshow(display)\n", " ax.set_title(f'{level.shape[1]}x{level.shape[0]}', fontsize=9)\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "12c2355f", "metadata": {}, "source": [ "Each level (shown shifted by +128 gray levels so negative values are visible) is mostly flat gray except right at edges — exactly where detail is lost by blurring and downsampling. The final, smallest level stores actual image content rather than a difference, since there's nothing coarser left to compare it to." ] }, { "cell_type": "markdown", "id": "6a760213", "metadata": {}, "source": [ "### Exact reconstruction\n", "\n", "Because each level stores exactly what its Gaussian-pyramid counterpart discarded, summing back up the pyramid reconstructs the original image exactly (up to integer rounding)." ] }, { "cell_type": "code", "execution_count": null, "id": "9d23ed1c", "metadata": {}, "outputs": [], "source": [ "reconstructed = reconstruct_from_laplacian(l_pyr)\n", "diff = np.abs(reconstructed.astype(int) - photo.astype(int))\n", "\n", "print(f'max reconstruction error = {diff.max()} gray levels')\n", "print(f'mean reconstruction error = {diff.mean():.4f} gray levels')\n", "\n", "fig, axes = plt.subplots(1, 2, figsize=(6, 3.5))\n", "axes[0].imshow(photo)\n", "axes[0].set_title('Original')\n", "axes[1].imshow(reconstructed)\n", "axes[1].set_title('Reconstructed from Laplacian pyramid')\n", "for ax in axes:\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "be2bc728", "metadata": {}, "source": [ "Compare this to Lesson 11's `pyrDown` + `pyrUp` result, which had a visibly nonzero reconstruction error: the Laplacian pyramid stores just enough extra information at each level to make the process perfectly reversible, at the cost of needing to keep all the levels around (not just the smallest one)." ] }, { "cell_type": "markdown", "id": "c6e101e8", "metadata": {}, "source": [ "### Exercise\n", "\n", "1. Try `threshold=1.0` and `threshold=15.0` in `zero_crossings`. How does the number of detected edge pixels change, and why does a *higher* threshold on a *second*-derivative sign-change criterion behave differently than a magnitude threshold on a first derivative?\n", "2. Increase the noise level in `noisy_disk` and see how large `sigma` needs to be before the zero-crossing edge map stops being dominated by spurious noise loops.\n", "3. Laplacian pyramids are the classic tool behind seamless image blending (e.g. blending two photos along a mask, level by level). Sketch out — in words or code — how you'd blend two Laplacian pyramids (e.g. average them with a spatially-varying weight per level) before reconstructing, and why blending in this representation avoids sharp seams that blending the original images directly would produce." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }