Motivation
An image edge is not an object boundary supplied directly by a camera. The camera records intensities; an algorithm estimates where those intensities change rapidly. A boundary can be hidden by weak contrast, while a shadow or texture can create a strong intensity change with no change of object. The first mathematical task is therefore more limited: compute and organize local evidence of change under a specified image model.
Differentiation amplifies rapid variation, including noise. Smoothing reduces some noise but can spread a transition over several pixels. A useful detector must acknowledge both effects rather than treating a large gradient as a perfect boundary label. Later steps also introduce nonlocal decisions: a weak candidate may survive because a path connects it to strong evidence elsewhere.
This unit develops those ideas with explicit discrete formulas. We derive a normalized Sobel filter, prove its response on affine intensity fields and its variance under independent noise, then prove a finite graph algorithm for threshold connectivity. It is not a complete computer-vision course or a guarantee of semantic object recognition.
Definitions
Definition 8.1.1
(Pixel coordinates and boundary rules)
Write image intensity as on integer pixel coordinates, with the first coordinate taken as horizontal. Interior formulas below assume all referenced pixels exist. On an actual finite array, padding, reflection, cropping or periodic extension must be specified separately; changing the boundary rule changes the computed image near its border.
Definition 8.1.2
(Convolution and correlation)
A finite-support convolution kernel acts by . Some software instead calls the unflipped sum with a convolution. That is correlation under this convention. For symmetric smoothing kernels the distinction disappears; for antisymmetric derivative kernels it can reverse the sign.
Definition 8.1.3
(Normalized Sobel response and gradient magnitude)
Define a horizontal centered difference and vertical binomial smoothing by
The normalized horizontal Sobel response is ; define by exchanging coordinates. Shift-invariant finite filters commute on the infinite grid, and at interior pixels of a finite image, because their finite sums can be reordered. A padding or cropping rule can break commutation near the boundary. Expanding gives
The normalization makes an affine ramp of slope one have response one. An implementation using the integer kernel without division by eight computes a scaled response and needs correspondingly scaled thresholds. Gradient magnitude is . For nonzero gradient, the vector gives a normal to a local level curve; a tangent is perpendicular to it. Orientation is undefined when both responses vanish.
These formulas measure change per pixel. If physical spacings are , use to measure change per physical length. Indeed the physical ramp produces raw responses . Unequal pixel spacings can therefore alter the physical gradient direction as well as its magnitude. Dividing both coordinates by one arbitrary common scale does not correct an anisotropic grid.
Definition 8.1.4
(Independent-noise model)
For noise analysis, let observed , with deterministic clean image and zero-mean independent pixel noises of common finite variance . This is a model, not a universal property of camera noise. Spatial correlation, unequal variances and signal-dependent noise require altered calculations.
Definition 8.1.5
(Hysteresis thresholds)
For threshold connectivity, take a finite pixel-neighbor graph, such as four- or eight-neighbor adjacency, and a fixed nonnegative candidate score . Choose . Weak candidates satisfy , and strong seeds satisfy . Hysteresis retains exactly those vertices of connected to some vertex of by a path entirely inside . The graph, score, inequalities and tie conventions are part of the definition.
Theorem/Proposition
Theorem 8.1.6
(Affine exactness and independent-noise variance)
At every interior pixel, normalized Sobel applied to gives and . Under the stated independent-noise model, each response is unbiased for the clean filter response and has variance . By comparison, the unsmoothed centered difference has variance . These are variance statements for signed responses, not unbiasedness of their nonlinear magnitude.
Proposition 8.1.7
(Hysteresis is seeded graph reachability)
Initialize a queue and retained set with every strong seed. Repeatedly remove a retained vertex and insert every previously unretained weak neighbor. On a finite graph this procedure terminates and returns exactly the weak vertices connected to a strong seed. It is independent of queue visitation order, though changing the neighborhood graph can change its answer.
Proof sketch or proof idea
Proof
(Exactness by symmetry, variance by coefficient squares)
For an affine image, the symmetric vertical average preserves its value: the vertical offsets have weighted average zero and the weights sum to one. The centered horizontal difference then gives exactly. Exchanging coordinates gives . Constants vanish because derivative weights sum to zero; this is also a direct check on the kernel's sign and normalization.
For any finite linear filter with coefficients , zero mean gives expected noise response zero. Expanding the squared sum, independence and centering remove cross terms, leaving . The horizontal Sobel coefficients are the products of difference weights with smoothing weights . Their squared sum is . Without smoothing the squared sum is . This proves the variance comparison without assuming Gaussian noise.
Proof X-ray
A stochastic improvement need not improve every perturbation
The variance reduction uses independent centered random noise to cancel cross terms in expectation. For an arbitrary deterministic perturbation bounded by at every pixel, both these normalized filters only give the bound . Thus smaller random variance does not prove a smaller worst-case response to every possible disturbance. The type of error model determines what “less sensitive” means.
Proof
(Reachability by induction on path length)
For hysteresis soundness, each inserted seed has a length-zero seed path. Whenever a weak neighbor is inserted, append its edge to the already existing path. Thus every retained pixel has a weak path to a seed. Conversely, induct on path length from a seed: the first vertex is initially inserted. The loop runs until the queue is empty, so every inserted predecessor is eventually processed and inserts the next vertex. All weak paths are therefore reached. Marking at insertion prevents duplicate processing; finite vertices and edges imply termination in time with adjacency lists. Traversal order cannot change a reachability set.
Concept lensStructural
Hysteresis as components of the weak subgraph
The result has a useful component interpretation: retain an entire connected component of the weak subgraph if and only if it contains a strong seed. This makes the global effect of thresholds clear. Lowering can create a bridge and admit a whole weak component. Raising can remove the last seed and discard a component even when all its individual weak scores stay unchanged.
Worked examples
Worked example 8.1.8
(A ramp checks scale and geometric meaning)
For , normalized Sobel gives and magnitude at every interior pixel. Measured in the stated coordinate frame, the normal direction has angle , approximately minus degrees; a level-curve tangent is perpendicular. Negating contrast reverses the signed gradient but leaves magnitude unchanged. A nonzero response over an entire ramp is not a thin edge map: another selection policy is still needed.
Worked example 8.1.9
(Smoothing spreads a step before differentiation)
In one dimension let for and for . Centered difference is at and zero elsewhere. First smooth in the same coordinate with weights . The smoothed values near the jump are at minus one and at zero. Differentiating afterwards gives at indices minus two through one. The total response remains one, but the peak decreases and the response spreads. This is same-direction presmoothing, distinct from the perpendicular smoothing in the Sobel definition.
Worked example 8.1.10
(Weak islands and seeded components)
On a seven-pixel chain with scores , choose . Weak candidates are indices and strong seeds are . Reachability retains and discards the weak island 4. A one-pass rule that keeps only weak pixels directly adjacent to a seed would incorrectly discard index 2. Repeated propagation is needed to realize the component definition.
For a numerical noise comparison, gives centered-difference variance 2 and normalized Sobel variance . The variance ratio is , while the standard-deviation ratio is . Reporting the variance ratio as the standard-deviation ratio exaggerates the reduction. The clean-image response is still the filtered gradient estimate, not an exact derivative for every non-affine image.
Common mistakes
Counterexample mode
A local score change can remove distant weak pixels
On a chain with scores , let . All pixels survive through the seed at the first position. Reducing only the middle score to 2 breaks the weak path; the last score remains 3 but is now discarded. Hysteresis is a connectivity decision, not an independent classification of each pixel. This nonlocal dependence is intended, yet it can also connect noise through an accidental bridge.
Common mistake
(Expecting one-pixel edges from a thresholded gradient)
Nonmaximum suppression usually compares gradient magnitude with nearby values along its estimated normal direction, using a specified interpolation rule. It can thin a ridge, but equal-value plateaux require a stated tie policy. A magnitude profile across an edge has two equal maxima: a rule that keeps ties yields a two-pixel edge, and a rule that demands a strict maximum deletes the edge. A gradient direction identifies a normal, while an edge-following tangent is perpendicular; confusing them suppresses or tracks along the wrong direction.
Common mistake
(Reading border outputs as edges)
Boundary handling changes the output near the border. On a constant image with zero padding, a pixel in the first column (and an interior row) gets although the image has no edge. A periodic extension joins opposite borders, which is appropriate for a periodic model but not automatically for a photograph. The interior exactness theorem cannot certify those border outputs.
Common mistake
(Treating a centered signed noise response as zero magnitude)
A signed response equal to or with probability each has mean , yet its magnitude is with certainty. Taking a norm is nonlinear and nonnegative, so in a constant clean region the measured magnitude can be positive on average even though each signed response is centered.
Threshold selection, contrast normalization and task evaluation therefore need additional decisions. Detecting intensity changes is a useful feature-extraction step, while identifying objects or physical causes of those changes requires further modeling.
Summary
Normalized Sobel is a specific linear combination of differencing and smoothing with checkable units. Its affine response and independent-noise variance follow directly from coefficient moments. Smoothing changes localization as well as noise, and hysteresis turns local candidates into seeded connected components. Keep signed response, magnitude, thinning, connectivity and semantic interpretation as separate mathematical tasks.
Exercises
Quick check
(Find both Sobel responses and magnitude for . What changes if an unnormalized integer Sobel kernel is used?)
Solution · Answer
The signed responses are minus three and four, with magnitude five. The integer kernels without division by eight multiply both responses and magnitude by eight, giving minus twenty-four, thirty-two and forty. Direction is unchanged by this common positive scaling, but thresholds must be scaled to preserve selections.
Quick check
(Average two independent centered-difference estimates, each with variance . Find the variance of the average. Explain why sharing pixels can invalidate this calculation.)
Solution · Answer
Independence gives variance . In general an additional covariance term appears: the average variance is . Shared noisy pixels can make that covariance nonzero, so averaging two overlapping stencils is not automatically equivalent to averaging independent observations.
Exercise 8.1.11
(On a chain with scores and thresholds , find the hysteresis output. Recompute for with unchanged and explain the removed vertices.)
Core
Solution(3)
- 1
Find the weak components at L = 2
Key step
Weak candidates have score at least : indices . Strong seeds have score at least : indices and . The weak components are and , and each contains a seed, so all five vertices are retained.
- 2
Weak candidates now have score at least : indices . Indices and , with score , are no longer weak. The components are and , both containing a seed, so the retained vertices are .
- 3
Explain the removal
Vertices and are removed because the candidate set changed, not because their scores or the strong seeds changed.
Exercise 8.1.12
(For a fixed score field and fixed graph, prove that increasing either threshold, while retaining , cannot add retained vertices. Does switching from four-neighbor to eight-neighbor adjacency have the same monotonic direction?)
Core
Solution(3)
- 1
Raising L shrinks the weak set
Key step
If , every vertex with also has , so the weak set can only shrink.
Because: The weak set is .
- 2
Raising H shrinks the seed set
Likewise, if , every vertex with also has , so the seed set can only shrink.
- 3
Compare retained sets
A vertex retained under the larger thresholds has a path inside the smaller weak set to a seed of the smaller seed set. That same path and seed are available under the original thresholds, so the vertex was already retained: increasing thresholds cannot add vertices. Eight-neighbor adjacency instead adds edges to the four-neighbor graph, so every four-neighbor weak path remains a path. It can add retained vertices and cannot remove them when scores and thresholds are fixed, which is the opposite direction. This follows from path inclusion, not from a claim that either neighborhood is always more accurate.