The Förstner operator
detect_foerstner is the interest operator of Förstner and Gülch (Förstner and Gülch, 1987): it finds windows of a grey image whose gradients locate a point well, and estimates in each a junction point and a circular point by least squares, keeping the one a significance test prefers. It follows the MATLAB reference implementation ip_fop.m (Luxen, 2005) step by step, including the two extensions it takes from Köthe (Köthe, 2003): the image is processed at doubled resolution, and the :koethe window criterion ranks windows by the smaller eigenvalue of the structure tensor.
using VisualGeometryToolkitFeatures, VisualGeometryToolkitCore
points = detect_foerstner(img) # Float32, default_device()
corners = filter(d -> d.label === :corner, points)
Ellipse(first(corners).value; sigma = 1) # the 1σ error ellipse (ip_errell.m)What it returns
One row per window, a StructArray of Detection(Uncertain(PointFrame(x), Σ), (; label, window, F, covariance_status)). The frame is VisualGeometryToolkitCore's PointFrame, a position without a scale: neither point model estimates a size.
label | the row's point and covariance |
|---|---|
:corner | the junction point (the reference's corner) |
:circular | the reference's circular point (dot_point): the centre of a rotationally symmetric pattern, a dot or a ring. Förstner & Gülch's term; it carries no size estimate and is not a scale-space blob |
:unknown | the window centre and a NaN covariance: the significance test labelled neither (the reference's noclass, which has no estimate) |
window is the window centre (the reference's win), F the statistic Ω_corner / Ω_circular the label was decided on, and covariance_status which covariance Σ is (below).
The covariance
With the image noise known, detect_foerstner(img; noise = σn) (iid pixel noise, in grey levels of an 8-bit image) returns the noise PROPAGATED through the detector, Σ = σn² J Jᵀ, marked covariance_status = :propagated. The window estimate is x̂ = N⁻¹ b with N = Σₚ v vᵀ, b = Σₚ v vᵀ p over the window's pixels, v = R∇g (R the identity for a corner, the 90° rotation for a circular point). A perturbation of the gradient moves it, by the implicit-function theorem, by
\[\delta\hat x = N^{-1} \sum_p A(p)\, \delta\nabla g(p), \qquad A(p)\, w = (v^\top e)\, R w + v\, e^\top R w, \quad e = p - \hat x,\]
the window centre (a discrete choice) fixed. The gradient is linear in the input — the doubling, then the derivative taps along one axis and the across taps along the other — so every input pixel q gives one column J[:, q], built from the adjoint of the detector's own stages, exact up to the image borders (the doubling's clamp, the correlations' zero padding). One kernel evaluates Σ_q σn² J[:, q] J[:, q]ᵀ per window, at its own gradient and estimate, on the CPU or a GPU.
On a RAW's green cells, detect_foerstner(L::LinearRaw; sensor_model) takes the frame's SensorModel (VisualGeometryToolkitCore's sensor_model, the one L was linearised with). Under a Poisson–Gaussian noise (a gain) L carries each value's variance, and each pixel's own variance weighs its column, Σ = J diag(var) Jᵀ, marked :propagated_measured, :propagated_estimated or :propagated_specified by the gain's source. Read noise alone, a relative noise or none is not fed: the covariance stays the a-posteriori one.
Without a noise (noise = nothing, the default) the covariance is the reference's a-posteriori Ω/redundancy · N⁻¹, marked :a_posteriori. It is not calibrated: Ω holds the model misfit (a blurred apex, a dot's flank), which does not scale with the noise, and the pixels' residuals are correlated by the derivative and doubling kernels; Monte Carlo NEES runs from 0.01 to 25 with the scene and scales. The propagated covariance gives NEES₂ ≈ 2 and the χ²₂ 95 % coverage about each dot's noise-free estimate (the test suite checks both at σᵢ = 1.41 and 3). Neither covers the operator's own bias (pixel locking, up to ≈ 0.04 px on small dots), which is a property of the estimator, not of the noise.
Coordinates
Positions are COLMAP pixel centres of the input image, (x, y) = (column, row), the top-left pixel's centre at (0.5, 0.5), as every detector of the package returns them. MATLAB indexes the pixel (r, c) at its centre, so a position (r, c) of the reference is (c − ½, r − ½) here.
The operator works on the doubled image. The package's one 2× upsampling (the ASIFT seed's, VLFeat's grid) makes the doubled pixel (r′, c′) (1-based) the bilinear sample at input position (r′/2, c′/2), 1-based, so a doubled-grid position is at COLMAP ((c′ − 1)/2, (r′ − 1)/2) in the input, and a covariance shrinks by 4. The conversion is made once, at the output.
Devices and precision
The image-wide steps — the doubling, the gradient and its integration, the window measures, the regional maxima and the non-maximum suppression, and the two least-squares estimates per window — are KernelAbstractions kernels, the same code on KA.CPU() and on a GPU (device = CUDABackend()). The squared gradient stays on the device and the kept window centres are compacted there, so only the centres and the windows' estimates reach the host, where the F-test and the result are assembled. T sets the precision: Float32 by default, Float64 as the reference. On the reference's example image Quadrate.tif (500 × 500, 100 windows) a CUDA device and the CPU give the same labels and positions within 3.1 × 10⁻⁵ px in Float32 and 3.2 × 10⁻¹⁴ px in Float64; the test suite checks it whenever a CUDA device is present.
Accuracy
On area-sampled synthetic dots (radius 2.5 px, sub-pixel centres spread over the whole frame up to 8 px from every border) every circular point comes back within 0.0054 px of the truth. A junction is less exact: at an X-junction the window measure is flat around the vertex, so the window can land a few doubled pixels off it, and the point estimate in an off-centre window is biased by up to ≈ 0.1 px (within its reported covariance); this is the operator's, not a difference from the reference.
On Quadrate.tif with the defaults, both window criteria find 100 windows, all labelled :corner; with the reference example's parameters (noise_sigma = 1, integration = :gaussian, derivative_sigma = 0.7, integration_sigma = 2) also 100 corners, median position standard deviation 0.057 px.
Windows chosen by scale: SFOP and seeded windows
The image-wide search uses one integration scale for every window. For circular points (dots) detect_sfop selects one per point instead: SFOP (Förstner et al., 2009) at α = 90°, the precision of a circular point's estimate maximised over position and scale on the image's Gaussian scale space (gaussian_scale_space, ASIFT's own pyramid; level_sigma gives a level's blur in input pixels), with the gradient this operator uses (gaussian_gradient). Its rows, Detection(Disc(x, σ), (; precision)), seed detect_foerstner(img, seeds), which runs the window estimation (steps 4–6 of the docstring) in each seed's window, the box of integration_sigma = σ, and skips the image-wide search:
seeds = detect_sfop(img; noise_sigma = 2) # discs: the selected σ per dot
points = detect_foerstner(img, seeds; noise = 2) # one row per seed whose window lies inside the imageThe rows are those of detect_foerstner(img); at the windows detect_foerstner(img) chose, the seeded form returns its rows bit for bit (a test item). The seeded form takes only the window estimation's keywords (device, noise, derivative, derivative_sigma, significance_level, f_tests) and polarity (below); the image-wide search's are refused by name. On a RAW's green cells both take the LinearRaw: detect_sfop(L) and detect_foerstner(Float64, L, seeds; sensor_model), positions on the cell grid and the covariance under the frame's sensor model.
On a RAW mosaic: the green photosites at the raw resolution
On a RawMosaic both take the mosaic and its frame's sensor model, and work on the green photosites without the cells' 2×2 decimation (whose square lattice aliases the green quincunx's diagonal detail: small dots missed):
seeds = detect_sfop(m; sensor_model, device) # raw COLMAP pixels, σ in raw pixels
points = detect_foerstner(m, seeds; sensor_model, device) # positions and covariances in raw pixelsThe image is the bilinear green on the raw grid, the normalized convolution of the usable green photosites with the cross kernel: a green photosite its own value, a red or blue one the mean of its usable green 4-neighbours. A saturated photosite is CENSORED: a normal sample, its value clipped at the white level (1) and its variance the noise law's there, flagged (saturated). A defect of the sensor model is MISSING: it drops out, and a pixel with no usable green under its cross (a defective green) is the mean of the usable greens of its 3×3 neighbourhood (its four diagonal greens). Only a pixel with no usable green in the 3×3 (a defect cluster) has no value, and every window reading it fails. SFOP runs on it as on any image, its first octave upsampled 2×, input_blur the image's stated blur 1/√3 raw pixels (the photosite's box, variance 1/12, and the interpolation's, ¼ on average). The seeded Förstner estimates on the raw-grid image, its own doubling as for any image, and propagates the noise from the photosites through the bilinear weights, Σ = Σ_k σ_k² J_k J_kᵀ; its F-test's degrees of freedom are those of that noise (white over the green photosites, interpolated: about 15 % below white input pixels'). On synthetic dots on a Bayer mosaic the covariance is calibrated (NEES ≈ 2, 95 % coverage) and the spread is about two thirds of the green cells'. The greens G1 and G2 are taken to respond alike: the sensor model carries no per-channel response, so a G1/G2 mismatch stays in the image as a checkerboard of its amplitude (a known limit).
A set of photographs: the F-test's table
The F-test's critical values depend on the configuration only (the gradient taps, the window half-width ρ, the noise structure, significance_level), never on the image, but each call computes them on the host, one ρ at a time; under the photosite noise of a mosaic that is eight lattice phases and centre parities per ρ, and on the GPU it was most of a seeded call's time. A FoerstnerTests table holds them: make one per detect configuration and give it to each call as f_tests. Each entry is keyed by everything it depends on, so one table can serve calls of different settings, and the rows are bit-identical to the calls without it (a test item, CPU and GPU):
f_tests = FoerstnerTests() # one per configuration, held by the caller
for m in mosaics
seeds = detect_sfop(m; sensor_model, device)
points = detect_foerstner(m, seeds; sensor_model, device, f_tests)
endPolarity
The structure tensor Σ∇g∇gᵀ does not see the sign of a blob: SFOP finds a dark spot as readily as a bright dot. detect_sfop(img; polarity = :light) keeps the light blobs, :dark the dark ones (ASIFT's vocabulary and sign, is_dark). The sign is the scale-normalised Laplacian of Gaussian σ²∇²(G_σ ⋆ I) at each candidate's selected σ, positive at a dark blob, and it is tested one-sided at significance_level under the λ₂ test's noise. A candidate whose sign the noise could have given (a window on flat background between dots) is kept for neither polarity: a missed blob, never one of the wrong sign. SFOP applies the gate before its NMS, so a blob of the other sign never suppresses a kept one. The seeded detect_foerstner(img, seeds; polarity) gates its seeds by the same test; it needs the pixel noise (noise, or a gain-carrying sensor_model on a LinearRaw) and is refused without it. :none, the default, applies no gate.
On 295 photographs of the five FX3 chrome sets (RAW green cells), detect_sfop(L; polarity = :light) followed by the seeded detect_foerstner loses no significantly light :circular row of Features 0.9.5: each row it drops is significantly dark or of a sign the noise could have given, and every pair of rows within 1 px (one blob seen from two seeds) is kept (an opt-in real-data test item holds this on a sample of those photographs).
Duplicates are not removed here: one blob seen from two seeds (SFOP finds a sharp dot at two scales more than a half-octave band apart, and the NMS keeps both) gives two rows, and the consumer resolves them by its own geometry (an assignment to the target's points, say).
A measured limitation, accepted (owner, 2026-11-14). At a dot radius of about 1.8 px the window SFOP selects is 0.0008 px RMS worse than the best fixed window (0.0092 vs 0.0084 px, synthetic discs, σᵢ 1.41); at the other radii from 0.9 to 5 px the two agree within the Monte Carlo error. Three window rules were tested and failed (the smallest a-posteriori variance, a window proportional to the radius, Gaussian weighting), and Farid–Simoncelli derivatives had no effect: the limit is the window estimator's pixel locking, so the selected window is kept. The test suite holds the pipeline on a grid of dots of radius 2.2 px: every error below 0.05 px, and the RMS within 5 % of the image-wide search's at integration_sigma = 4.
Differences from ip_fop.m
The implementation follows the reference line for line except in four places, each recorded here with its evidence.
1. Undoing the doubling: fixed
The reference doubles the image with imresize(g, 2, 'bilinear') (line 172) and maps positions back with transf_H, transf_v (lines 340–350, applied at 436, 446 and 457): x = (1 − n)/(1 − 2n)·x′ + (1 − 2)n/(1 − 2n) per axis, n the image size. That map is the inverse of an align-corners grid, on which the doubled pixels 1 and 2n sit on the input pixels 1 and n. imresize's grid is not that: its doubled pixel j samples the input at j/2 + 1/4 (1-based), so the exact inverse is x = x′/2 + 1/4, and the reference's points are off by ((n + 1)/2 − x)/(2n − 1): zero at the image centre, up to 0.25 px toward the centre at the borders.
What this rests on, since MATLAB cannot be run here: MATLAB's imresize documentation states that antialiasing applies only when shrinking, so a 2× bilinear enlargement is plain bilinear interpolation; and imresize.m maps output to input coordinates by u = x/scale + 0.5·(1 − 1/scale), i.e. u = x/2 + 1/4 for scale = 2, with the out-of-range neighbour of the first sample taken from the edge pixel (index mirroring, which at this offset replicates the border). The tests emulate that grid to measure the reference's map.
Measured on 30–42 area-sampled dots spread over the frame (sub-pixel centres, up to 8 px from every border), sampled on imresize's grid:
| back-map | largest error |
|---|---|
the reference's transf_H, transf_v | 0.236 px (borders; ≈ 0 at the centre), matching the predicted ((n + 1)/2 − x)/(2n − 1) to 0.002 px at every dot |
imresize's exact inverse | 0.0054 px |
the package's upsampling grid, its exact inverse (what detect_foerstner does) | 0.0054 px |
The package's grid (input j/2) is a quarter input pixel from imresize's (input j/2 + 1/4); the doubled samples differ accordingly, and the measured effect on the positions is nil at this precision (0.0054 px either way).
2. The circular point's residual sum: kept as the reference has it
Line 423 computes the circular point's weighted residual sum as Σ γ_cc·Δr_dot² − 2γ_rc·Δr_corner·Δc_corner + γ_rr·Δc_corner²: two of its three terms use the junction model's residuals. Förstner and Gülch's circular model has, for each pixel i, the residual ∇gᵢ⊥ᵀ(x̂ − xᵢ) (the distance of the point from the line through the pixel along its gradient, weighted by the gradient), so its residual sum is Σ (xᵢ − x̂)ᵀ Γᵢ⊥ (xᵢ − x̂) with all three terms from the circular estimate. That sum enters the covariance Ω/redundancy · N⁻¹ (line 449) and the test statistic (line 427).
A Monte Carlo test of the reported covariance does not support the derived form. On noisy synthetic dots (radius 2.5 px, random sub-pixel centres, 400 trials each; NEES eᵀΣ⁻¹e, nominal mean 2):
| noise (of the [0, 1] range) | mean NEES | 95 % coverage | 99.9 % coverage | |
|---|---|---|---|---|
| 0.01 | line 423 (kept) | 3.0 | 0.85 | 0.965 |
| 0.01 | derived residual sum | 13.7 | 0.375 | 0.65 |
| 0.03 | line 423 (kept) | 8.7 | 0.578 | 0.805 |
| 0.03 | derived residual sum | 20.4 | 0.315 | 0.52 |
Neither form is calibrated for circular points (both under-cover: the variance factor treats the gradients of a window as independent, which the smoothing makes them not), and the reference's form is the closer one. The labels were the same under both in all 1 600 trials (dots and X-junctions at both noise levels), the junction covariance does not involve it (NEES 0.91 and 1.72, 95 % coverage 0.998 and 0.96), and the reference's sum was never ≤ 0. So line 423 is kept as written; a test item reruns a 100-trial version of the comparison.
3. Defaults: the code's
The reference's header documents SIGMA_N = 2.5 grey values and SIGMA_DIFF = 0.7 px (lines 37 and 50); its code runs with 2.0 and 1.0 (lines 521 and 524). The defaults here are the code's — what ip_fop.m actually ran. This is a conflict in the reference's documentation, not a correction.
4. The F-test's degrees of freedom: corrected
The reference labels a window by F = Ω_corner / Ω_circular against F(redundancy, redundancy), redundancy = (2ρ + 1)² − 2 the window's doubled pixels less two (line 429), as if each pixel's residual were independent. They are not: the doubling and the derivative and across taps correlate the doubled samples. Under white input noise each residual sum is a quadratic form of the input pixels, Ω = Iᵀ Q I, so E[Ω] = σₙ² tr Q, Var Ω = 2σₙ⁴ tr Q², and its effective degrees of freedom (Satterthwaite) are ν = (tr Q)²/tr Q². The gradient's components are separable (the rows' and the columns' one-axis operators), so ν costs O(ρ²) per window half-width; the sums are taken about the window centre, neglecting the estimate's two parameters (about 2 of ν), which keeps the test conservative. The test now uses F(ν_corner, ν_circular) at the same significance_level.
| ρ (doubled px) | integration σ (input px) | redundancy | ν_corner | ν_circular | F(ν, ν) at 0.999 |
|---|---|---|---|---|---|
| 6 | 1.3 | 167 | 11.9 | 12.5 | 6.76 |
| 10 | 2.4 | 439 | 25.6 | 24.8 | 3.65 |
| 15 | 4.0 | 959 | 47.9 | 46.1 | 2.54 |
| 22 | 6.0 | 2023 | 89.8 | 87.1 | 1.95 |
(derivative_sigma 1, Gaussian derivative.) On white noise, seeded windows at σ = 6: the mean of Ω_circular is σₙ² tr Q to 1 %, its measured ν 77 ± 5 (the circular sum is line 423's, see 2) and Ω_corner's 89 ± 5. At the pixel count 20 % of the noise windows were labelled circular and 25 % corner at 0.999; with ν none (the two sums are positively correlated, so the ratio varies less than F(ν, ν), and the test is conservative). On the chrome photographs the windows between dots, on line artefacts and on letter strokes (F ≈ 1–3) were labelled circular at the pixel count; with ν they are unknown. The a-posteriori covariance keeps the reference's Ω/redundancy · N⁻¹.
At ρ = 6 (the first row; also the image-wide search's default window, integration_sigma 1.41 at derivative_sigma 1) a corner at 0.999 needs F < 0.143: a sharp, noise-free checkerboard X-junction (F ≈ 0.16) is unknown there, a corner at 0.99 (F < 0.241). An unknown row keeps its window centre and a NaN covariance.
Also as the reference
noise_sigma is in grey levels of an 8-bit image, as the reference's for a uint8 image: the operator reads the image in [0, 1] and uses noise_sigma / 255. The reference stretches a floating-point image to its own range; this does not. With a Gaussian integration the estimation window still weighs its pixels equally, which the reference's header flags as an inconsistency.
The full docstring: detect_foerstner.