Source-linked AI summary
Neural Disjunctive Normal Forms for Learning Exact Rank Filters
Diego Marcondes, Wonder A. L. Alves, Ronaldo F. Hashimoto
TL;DR
Sparse derivatives can hinder learning structuring elements for rank filters. The paper combines threshold decomposition with a neural DNF representation to derive a smooth surrogate for the backward pass while keeping the forward operator exact. From generic random initialisation, it reports gains over exact-subgradient training in every setting and over smooth morphological networks in all denoising settings.
Problem
At pixels where an order statistic has a unique winner, the derivative is nonzero only at that structuring-element position, potentially hindering optimisation and making training sensitive to initialisation.
Source: §1 · p. 1Method
Results
From generic random initialisation, the method improves on exact-subgradient training in every setting and on smooth morphological networks in all denoising settings.
Source: §1 · pp. 2–3Takeaways & Limitations
For fixed ranks, the procedure applies to any rank filter and extends to compositions, infima and suprema while retaining exact forward evaluation.
Source: §1 · p. 2, §6 · p. 11The architecture fixes the rank beforehand; learning the rank is left for future research.
Source: §6 · p. 11
Abstract
from arXiv · showhide
Gradient-based learning of morphological operators is hindered by locally sparse derivatives with respect to the structuring elements. We develop a method for learning rank filters that retains exact operator evaluation while distributing the derivatives across the window. Using threshold decomposition, we construct a neural disjunctive normal form representation and establish a sufficient condition for exactness with integer-valued images and structuring elements. We then derive a smooth surrogate from the unique root of a smooth threshold equation. Implicit differentiation gives closed-form derivatives with normalised local weights, whose distribution is controlled by a smoothing parameter. These derivatives are used in a straight-through procedure: the forward pass evaluates the exact rank filter, while the backward pass uses the surrogate. For fixed ranks, the procedure learns real-valued structuring elements of any rank filter, including the median, and extends to compositions, infima, and suprema of rank filters. Experiments on image denoising using MNIST and Fashion-MNIST and retinal vessel segmentation show that, starting from a generic random initialisation, the proposed approach consistently improves performance over training with exact subgradients in every setting. In image denoising, our best network also outperforms smooth morphological networks in all settings. On vessel segmentation, the learned erosions recover structuring elements that fit the vessels, as theoretically expected, whereas most of those trained with exact subgradients remain close to their initialisation.
1 Introduction
Rank-filter learning preserves exact operator evaluation, but exact subgradients are locally sparse and can make optimisation sensitive to initialisation. The paper derives a smooth surrogate for the backward pass and reports improved training from generic random initialisation.
1 Introduction
- At positions where an order statistic has a unique winner, only that structuring-element position receives a nonzero derivative, which can hinder optimisation and increase sensitivity to initialisation.Smooth layers instead approximate the operators, while earlier exact-forward approaches used heuristic gradient redistribution.Source: §1 · pp. 1–2
- Threshold decomposition and a neural DNF representation yield a smooth rank-filter representation that is exact on the integer grid when the smoothing parameter is large enough.Implicit differentiation gives normalised local weights as the surrogate derivative, rather than the heuristic smoothed impulses used in earlier work.Source: §1 · p. 2
- For fixed ranks, a straight-through procedure learns real-valued structuring elements using the exact filter in the forward pass and the surrogate in the backward pass.It applies to any rank, including the median, and extends to compositions, infima and suprema of rank filters.Source: §1 · p. 2
- From generic random initialisation, the method improves on exact-subgradient training in every setting and on smooth morphological networks in all denoising settings.The retinal-vessel erosions also recover structuring elements of different sizes and orientations that fit the vessels, unlike most exact-subgradient-trained erosions, which remain near their initialisation.Source: §1 · pp. 2–3
2 Theoretical background
The background sets up rank filters on greyscale images and introduces a Boolean representation that supports exact order-statistic computation. Threshold decomposition expresses a rank filter through Boolean order statistics, which a neural DNF layer can represent exactly.
2 Theoretical background
- Greyscale images are functions whose values give pixel intensities, and each image restriction to a translated window can be reindexed on the window itself.The background also equips window-valued images with pointwise order and defines the sign convention used in the Boolean construction.Source: §2 · p. 3
2.1 Rank filters and threshold decomposition
- A rank filter applies the q-th order statistic to image values adjusted by a structuring element; threshold decomposition expresses its output through Boolean order statistics.The q-th rank includes erosion and dilation as endpoint cases and the usual median for the middle rank with zero structuring element.Source: §2.1 · pp. 3–4
2.2 Semi-symbolic neural layers
- The neural DNF layer can represent any order statistic of Boolean inputs exactly when its weights and δ are chosen appropriately.The layer includes maximum, minimum and median as particular choices of δ.Source: §2.2 · p. 4, Figure 2 · p. 5
3 A smooth surrogate for rank filters
Threshold decomposition and a neural disjunctive normal form yield a smooth surrogate for rank filters that is exact on the integer grid above a sufficient smoothing threshold. A unique root of a smooth threshold equation supplies derivatives that distribute updates across the window, and the representation extends to compositions, infima, and suprema.
3 A smooth surrogate for rank filters
- For integer-valued structuring elements, the DNF representation exactly matches every rank filter when α > ln(2|W| − 1).The representation applies to every rank q.Source: §3 · p. 5
- The surrogate uses the unique root of a smooth threshold equation, with the rank-filter output obtained by truncating that root to a greyscale level.The root is the threshold where S_α(t, a, f_W) + β(δ) equals zero.Source: §3 · pp. 5–6
- Implicit differentiation gives negative structuring-element derivatives whose magnitudes sum to one, with α redistributing probability across the window toward the selected order-statistic position.As α grows, the mass concentrates on the unique position attaining the q-th order statistic.Source: §3 · p. 6
- Sequential layers represent compositions of rank filters, while adapted layers compute their infimum or supremum and provide derivatives with respect to each structuring element.The infimum construction requires α > ln(2n − 1).Source: §3 · p. 6
4 Training exact rank filters with smoothed gradients
Training uses an exact rank filter in the forward pass and its smooth surrogate in the backward pass. The smoothing parameter controls how broadly gradients are distributed, and the approach extends to compositions, infima, and suprema.
4 Training exact rank filters with smoothed gradients
- The straight-through procedure evaluates the exact rank filter in the forward pass and uses the smooth root surrogate for backward gradients.The rank and δ satisfy relation (5).Source: §4 · p. 6, §4.1 · p. 7
4.1 Straight-through and derivatives
- Input gradients propagate through compositions, and the same training approach extends to compositions, infima, and suprema with approximate backward subgradients.The forward pass remains exact for these combined operators.Source: §4.1 · p. 7
- Lower α spreads the negative structuring-element derivatives across the window and encourages updates to the whole element without changing the exact evaluated operator.The negative derivatives form a probability vector whose spread decreases as α increases.Source: §4.1 · p. 7
- The root is computed independently at each pixel using Newton’s method, with four steps for rank filters and eight for the supremum.The root calculations are parallelisable on a GPU.Source: §4.1 · p. 7
5 Experiments
The experiments compare exact rank-filter training with surrogate backward gradients against exact subgradients and smooth morphological networks. The proposed method improves denoising results and all five vessel-segmentation metrics, while retaining exact operator evaluation.
5 Experiments
- The experiments test image denoising on MNIST and Fashion-MNIST and retinal-vessel segmentation on CHASE_DB1, using random initialisations.For vessel segmentation, the network is a supremum of 256 erosions trained against the exact-subgradient baseline.Source: §5 · pp. 7–8, §5.2 · p. 9
- Across denoising and vessel segmentation, the method improves on exact-subgradient training while keeping the evaluated operators exact.Denoising gains reach 2.0 dB; on vessel segmentation, all five metrics improve.Source: §5.1 · p. 9, Table 1 · p. 9, §5.2 · p. 10
5.1 Experiment 1: image denoising
- Up to 2.0 dB higher mean test PSNR (ASF on MNIST at 5% noise) is reported against exact-subgradient training.The best proposed networks also outperform smooth HSMorph networks in all ten denoising settings.Source: §5.1 · p. 9, Table 1 · p. 9
5.2 Experiment 2: retinal vessels
- On CHASE_DB1, the method improves all five test metrics over exact-subgradient training, while exact-subgradient training improves little over the top-hat input.The method's active erosions are varied line segments; exact-subgradient training leaves 75% of structuring-element entries never updated, versus fewer than 0.1% with the proposed method.Source: §5.2 · p. 10, Table 2 · p. 10
6 Final remarks
The method trains exact rank filters with a straight-through estimator and extends to compositions, infima, and suprema. Its scope leaves rank learning and non-increasing operators for future work.
6 Final remarks
- The framework extends exact, interpretable training to compositions, infima, and suprema of rank filters, including grey-level images.The paper contrasts this scope with smooth layers that generally approximate only erosions and dilations.Source: §6 · p. 11
- The method's supported scope uses fixed ranks; learning the rank so architecture need not be fixed is left for future research.Source: §6 · p. 11
- The authors identify extending the framework to non-increasing operators through a Banon-Barrera decomposition as future work.Source: §6 · p. 11
7 Proofs
The proofs establish exactness for a Boolean order statistic, extend the smooth threshold construction to integer-valued inputs, and derive the surrogate derivative by implicit differentiation.
7 Proofs
- The Boolean threshold construction makes the represented function equal the q-th order statistic by choosing a bias that separates its two possible outputs.Source: §7 · p. 11
- For integer-valued inputs and structuring elements, a sufficiently large smoothing parameter preserves the sign of the threshold equation and yields exact evaluation.Source: §7 · p. 11
- The surrogate derivative follows by implicit differentiation of the smooth threshold equation's root with respect to each structuring-element entry.Source: §7 · p. 11