Morphological Operations

Let $A$ be a binary image, viewed as a subset of the integer grid $\mathbb{Z}^2$: the set of all foreground (pixel value 1) coordinates. Let $B$, the structuring element, be a small, usually symmetric set of coordinates with a designated origin — commonly a $3\times3$ square, a cross, or a disk. Morphological operations answer geometric questions about how $B$, translated to each position in the image, interacts with $A$.

Erosion of $A$ by $B$, written $A \ominus B$, keeps only those positions $p$ where the translated structuring element $B_p$ (i.e., $B$ shifted so its origin sits at $p$) fits entirely inside $A$:

Erosion shrinks foreground blobs from their boundary inward, by roughly the radius of $B$. Thin protrusions and small isolated specks disappear entirely because no full copy of $B$ fits inside them.

Dilation of $A$ by $B$, written $A \oplus B$, keeps every position $p$ where the translated structuring element $B_p$ overlaps $A$ at all:

Dilation grows foreground blobs outward, filling small holes and bridging small gaps between nearby regions. Erosion and dilation are dual under complementation: eroding a shape is the same as dilating its background and inverting the result. Formally, $(A \ominus B)^c = A^c \oplus \check{B}$, where $\check{B}$ is $B$ reflected through its origin and $A^c$ is the complement of $A$. This duality means you never need two separate implementations — one primitive, correctly generalized, gives you both. From these two primitives, two composite operations are built. Opening, $A \circ B = (A \ominus B) \oplus B$, erodes then dilates: it removes small foreground noise and thin spikes while leaving the main body's size roughly unchanged. Closing, $A \bullet B = (A \oplus B) \ominus B$, dilates then erodes: it fills small holes and bridges small gaps while leaving the outer boundary roughly unchanged. The asymmetry — erode-then-dilate versus dilate-then-erode — is exactly what makes one operation clean noise from outside shapes and the other clean noise from inside shapes.

The practical implementation works on a raster image with a small structuring element, most commonly represented as a binary mask (e.g., a $3\times3$ matrix of 0s and 1s) with a defined origin, typically its center.

Erosion at pixel $p$: examine every offset $(dx, dy)$ where $B$ has a 1. If any corresponding neighbor $A[p + (dx,dy)]$ is 0 (or out of bounds, under the common convention that out-of-bounds counts as background), the output at $p$ is 0. Only if all covered neighbors are foreground does the output stay 1.

Dilation at pixel $p$: examine every offset where $B$ has a 1. If any corresponding neighbor is foreground, the output at $p$ is 1. This is naturally phrased in terms of the reflected structuring element: dilation at $p$ asks whether $A$ has foreground at $p$ minus some offset in $B$, for some offset — equivalently, whether $B$ reflected and centered at $p$ overlaps $A$. ``` function ERODE(A, B, origin):

# A: binary image, H x W

# B: structuring element, list of (dy, dx) offsets relative to origin

# returns: binary image E of same size as A E = zeros(H, W) for y in 0 .. H-1: for x in 0 .. W-1: fits = true for (dy, dx) in B.offsets: ny, nx = y + dy, x + dx if not in_bounds(ny, nx, H, W) or A[ny][nx] == 0: fits = false break E[y][x] = 1 if fits else 0 return E function DILATE(A, B, origin): D = zeros(H, W) Brefl = reflect_through_origin(B) # (dy,dx) -> (-dy,-dx) for y in 0 .. H-1: for x in 0 .. W-1: hit = false for (dy, dx) in Brefl.offsets: ny, nx = y + dy, x + dx if in_bounds(ny, nx, H, W) and A[ny][nx] == 1: hit = true break D[y][x] = 1 if hit else 0 return D function OPEN(A, B): return DILATE(ERODE(A, B), B) function CLOSE(A, B): return ERODE(DILATE(A, B), B) ``` For symmetric structuring elements (a square, a disk, a cross centered on its origin), $B = \check{B}$, so the reflection step is a no-op — this is the common case in practice, and most library implementations assume it by default. A crucial engineering detail is boundary handling. Treating out-of-bounds pixels as background (0) is the standard convention: it makes erosion shrink shapes near the image border (since $B_p$ cannot "fit" if part of it falls outside), and it is the choice consistent with viewing the image as embedded in an infinite background of zeros.

Time complexity. For an image with $n$ pixels and a structuring element with $k$ nonzero offsets, the naive erosion or dilation loop visits every pixel and, for each, scans up to $k$ offsets, giving $O(nk)$ time. For a $3\times3$ element, $k=9$ is a small constant, so this is effectively $O(n)$ — linear in image size, as expected for a local filtering operation. For larger structuring elements — say a disk of radius $r$, with $k = O(r^2)$ — the naive cost becomes $O(n r^2)$, which grows quickly. Two standard optimizations restore near-linear performance:

• Separable structuring elements. A rectangular $k_1 \times k_2$ element decomposes into a 1-D erosion of width $k_1$ along rows followed by a 1-D erosion of width $k_2$ along columns, since a rectangle is the Minkowski sum of two line segments. This reduces cost to $O(n(k_1+k_2))$.
• Van Herk / Gil–Werman algorithm. For a 1-D window of width $k$ (min or max filter, which is exactly what erosion/dilation reduce to along a line), a running min/max can be maintained using two auxiliary arrays (forward and backward running extrema over blocks of size $k$) so that each output element is computed in $O(1)$ amortized time, giving $O(n)$ total time independent of $k$. Applying this row-wise then column-wise handles any rectangular structuring element in $O(n)$ regardless of its size — a genuine algorithmic win, not just a constant-factor speedup.

Opening and closing are each two calls to erosion/dilation, so they inherit the same asymptotic bound: $O(nk)$ naively, or $O(n)$ with the fast algorithms.

Space complexity is $O(n)$: one or two image-sized buffers (input, output, and possibly an intermediate for opening/closing), plus $O(k)$ for the structuring element itself.

Correctness — key algebraic properties, with justification: 1. Duality: $(A \ominus B)^c = A^c \oplus \check B$. Proof sketch: $p \notin A\ominus B$ iff $B_p \not\subseteq A$ iff $B_p$ contains some point in $A^c$ iff $\check B_p$ (as a probe testing overlap) hits $A^c$ — precisely the condition for $p \in A^c \oplus \check B$. This means an erosion implementation immediately gives a correct dilation implementation via complementation, and vice versa; a single verified core routine suffices for both. 2. Monotonicity: if $A \subseteq A'$, then $A \ominus B \subseteq A' \ominus B$ and $A \oplus B \subseteq A' \oplus B$. Proof: directly from the defining quantifiers ("for all" preserves under superset for erosion's containment test; "exists" preserves under superset for dilation's overlap test). This guarantees morphological operations never invert relative shape ordering — useful when reasoning about nested masks (e.g., a mask and its dilated safety margin). 3. Idempotence of opening and closing: $(A \circ B) \circ B = A \circ B$, and similarly for closing. Proof sketch: Opening removes exactly those parts of $A$ where $B$ does not fit; once removed, applying opening again finds nothing further to remove, because every point retained in $A \circ B$ is, by construction, covered by some translate of $B$ fully contained in $A$ (hence fully contained in $A \circ B$ too). This idempotence is the formal reason opening and closing are stable filters: running them twice is provably the same as running them once, so there is no risk of runaway erosion from repeated application — a property naive erosion/dilation alone do not have (repeated erosion keeps shrinking until the image vanishes). 4. Extensivity/anti-extensivity: $A \circ B \subseteq A \subseteq A \bullet B$. Opening only removes points, closing only adds points, relative to the original — so neither operation can "overshoot" into fabricating structure unrelated to $A$'s original footprint at the scale of $B$.

Tradeoffs. Morphology is scale-selective but not scale-adaptive: a single fixed-size structuring element cannot simultaneously remove large noise blobs and preserve fine detail — a limitation addressed by tuning $B$'s size to the noise scale you expect, or by multi-scale/granulometric analysis (a sequence of openings at increasing sizes). It also has no notion of intensity gradients or texture; it treats binary shape purely geometrically, which is a strength (predictability, no training needed) and a weakness (blind to context that a learned model would exploit).

Consider a $7\times 7$ binary image (1 = foreground) representing a thresholded washer with a one-pixel salt-noise speck and a one-pixel pepper-noise hole, using a $3\times3$ square structuring element (all 9 offsets, origin centered): ``` Original A Step 1: Erode (A⊖B) Step 2: Dilate (opened, A∘B) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ``` Reading the trace:

• Row 2 has a pepper hole at column 3 (`0 1 1 0 1 1 0` — a missing pixel inside the disk). During dilation-based closing (shown separately below) this gets filled; during plain opening (shown here) erosion first destroys the whole neighborhood around the thin ring, since no full $3\times3$ window fits inside such a narrow band — this is opening correctly clearing that noisy edge structure.
• Row 6 has a one-pixel spur (`0 0 0 1 0 0 0`) sticking out below the disk — a thin protrusion. After erosion, no $3\times3$ window centered near that spur is entirely foreground (the spur is only 1 pixel wide), so it vanishes and never returns after dilation. Opening has successfully removed the spur while the main disk survives (shrunk then regrown to nearly its original footprint).
• The eroded image is much smaller than the original — this is expected since erosion strips a full "ring" of thickness 1 from the boundary of every shape when using a $3\times3$ structuring element.
• After dilating the eroded result, the disk regrows to approximately its original extent, but the spur and the ring irregularity do not reappear, because dilation only regrows from what erosion left behind, and erosion had already permanently deleted those thin structures.

Now trace closing on the same original image, which fixes the pepper hole instead: ``` Original A Step 1: Dilate (A⊕B) Step 2: Erode (closed, A•B) 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 ``` Here dilation first fills the pepper hole (since the $3\times3$ neighborhood around column 3 of row 2 overlaps plenty of foreground), and grows the whole shape outward by one ring; erosion then shrinks that grown shape back down by one ring, restoring the original boundary — but the hole, once filled by dilation, cannot reappear, because erosion only removes boundary pixels, never re-punches interior holes. The final closed image is a perfectly filled disk with no pepper hole and (in this particular symmetric example) the one-pixel spur is also absorbed into the disk's boundary during dilation and then not fully removed by erosion, illustrating the tradeoff: closing is good at filling gaps/holes but, unlike opening, does not reliably delete small protruding spurs — the two operations solve complementary problems, and pipelines commonly apply opening then closing (or vice versa) to attack both noise types at once.

Document scanning and OCR pipelines apply opening and closing to remove speckle noise from scanned binary text and to reconnect broken character strokes before recognition. Medical imaging pipelines use morphology to clean thresholded segmentations of cell nuclei, blood vessels, or tumor boundaries, removing spurious small regions and filling small gaps in vessel masks before skeletonization. Industrial machine vision — the washer-counting example that opens this article — relies on morphological cleanup after thresholding to get accurate connected-component counts and shape measurements. Video surveillance systems use morphology on foreground masks produced by background subtraction to suppress single-pixel noise from sensor flicker before tracking algorithms consume the mask. Optical Character Recognition engines and barcode/QR readers use morphological gradient and top-hat operations (dilation minus erosion, and related grayscale variants) to normalize uneven illumination before binarization. And, looking forward, the clean binary edge and shape maps morphology produces are exactly the input format expected by geometric detectors such as the Hough Transform for lines and circles, and by Connected Component Labeling for object counting — morphology is the standard bridge between raw thresholded pixels and structured geometric reasoning.

Ask the tutor: How would you design a sequence of openings at increasing structuring-element sizes (a granulometry) to estimate the size distribution of objects in a binary image?