How GIMP Fuzzy Selection Calculates Pixel Similarity
This article explains how the GNU Image Manipulation Program (GIMP) evaluates pixel similarity using Euclidean distance metrics during the operation of the Fuzzy Select (Magic Wand) tool. It covers the initial sampling of the seed pixel, the mathematical formula applied across color channels, how the user-defined threshold serves as a boundary condition, and how the algorithm traverses neighboring pixels to build a contiguous selection mask.
The Seed Pixel and Reference Point
When you click an image using GIMP's Fuzzy Select tool, the clicked pixel acts as the "seed" pixel. The tool reads the color channel values of this seed—typically Red, Green, Blue, and optionally Alpha (\(R_0, G_0, B_0, A_0\)) in standard RGB space. These values establish the reference coordinates in a multi-dimensional color space against which all candidate neighboring pixels are evaluated.
The Euclidean Color Distance Formula
To determine whether an adjacent pixel is visually "close" enough to the seed pixel to be selected, GIMP treats color values as coordinates in a spatial coordinate system. In a standard 8-bit RGB color model, each channel ranges from 0 to 255, placing colors inside a three-dimensional cube.
The straight-line difference between the candidate pixel \((R_1, G_1, B_1)\) and the reference pixel \((R_0, G_0, B_0)\) is calculated using the standard Euclidean distance metric:
\[d = \sqrt{(R_1 - R_0)^2 + (G_1 - G_0)^2 + (B_1 - B_0)^2}\]
If transparency is involved and the selection criteria account for alpha, the formula extends into a 4-dimensional Euclidean metric:
\[d = \sqrt{(R_1 - R_0)^2 + (G_1 - G_0)^2 + (B_1 - B_0)^2 + (A_1 - A_0)^2}\]
In modern versions of GIMP powered by GEGL (Generic Graphical Library), pixel data is often handled in high-precision floating-point formats (from 0.0 to 1.0) and can be evaluated in linear or perceptual color spaces, but the fundamental geometric formula remains the same.
The Threshold Evaluation
The calculated Euclidean distance \(d\) represents the total color divergence. GIMP compares this value directly against the Threshold parameter specified in the tool options.
- Within Threshold (\(d \le \text{Threshold}\)): The candidate pixel is deemed similar enough and is added to the selection mask.
- Exceeds Threshold (\(d > \text{Threshold}\)): The candidate pixel is rejected, forming a boundary that halts expansion in that direction.
Because calculating a square root for millions of pixel comparisons is computationally expensive, the algorithm typically compares the squared Euclidean distance (\(d^2\)) against the squared threshold (\(\text{Threshold}^2\)) to optimize performance:
\[(R_1 - R_0)^2 + (G_1 - G_0)^2 + (B_1 - B_0)^2 \le \text{Threshold}^2\]
Contiguous Traversal (Flood Fill)
Fuzzy selection relies on a flood-fill algorithm (such as breadth-first search or scanline fill) to traverse the canvas. The Euclidean metric is not computed globally across the entire image at once; instead, the algorithm starts at the seed pixel and checks adjacent pixels (usually 4-connected neighbors: north, south, east, and west).
If an adjacent pixel satisfies the threshold condition, it is added to the selection queue, and its own neighbors are subsequently tested against the original seed pixel values. The expansion continues outward until it hits pixels where the Euclidean distance exceeds the threshold or reaches the canvas boundaries.
Channel Selection Modes
While Euclidean distance in composite RGB/RGBA is the default behavior, GIMP allows users to base similarity on specific criteria under the "Select by" options, such as:
- Individual Channels (Red, Green, Blue, Alpha): The calculation reduces to a one-dimensional scalar absolute difference: \(|C_1 - C_0|\).
- HSV/LCH Components (Hue, Saturation, Lightness, Value): The distance is calculated along alternate axes, where angular differences (such as Hue on a 0–360° circle) use modular distance formulas rather than standard Cartesian metrics.