Mathematical morphology is a family of shape operations on images. Dilation grows shapes, erosion shrinks them, and chains such as opening (erode, then dilate) remove specks or fill holes. Each operation is defined by a small binary stencil called a structuring element. When these operators are learned with gradient descent, a lopsided failure appears. Dilation is learned easily. Erosion, its exact mathematical mirror, is learned up to 100 times more slowly. Continuous architecture search drops erosion altogether. We propose a different way to find these stencils. For a single layer, finding the stencil that reproduces given input and output masks is not a gradient problem at all. It is a small hitting-set problem: choose a set of stencil cells that intersects every one of a list of given sets. A MaxSAT solver, which finds the Boolean assignment satisfying the most weighted logical constraints, solves this exactly in milliseconds. The hard part of learning a chain of operators is that the intermediate images are unknown.
Our plan splits the work between two tools. A differentiable morphological network proposes the unknown intermediate images. A per-layer exact solver returns the best binary stencil for each layer given those images. It also returns a "core": a minimal set of pixels whose constraints cannot all be satisfied together. The cores are sent back to the network as localized corrections. The output is a pipeline of truly binary stencils that comes with a per-layer optimality certificate, and an exact global certificate whenever training error reaches zero. This replaces BiMoNN's post-hoc rounding step. The test case is erosion-heavy chains, which current gradient methods learn worst.
Core Claim
In BiMoNN (Binary Morphological Neural Network), each binary morphology neuron (called a BiSE) passes a convolution through a smooth threshold. Dilation becomes a "hit" test $I*S\ge 1$ and erosion a "fit" test $I*S\ge|S|$, with a tanh replacing the step. Binary stencils are recovered afterward with a heuristic "Linear Check." That paper reports perfect recovery of single disks and crosses, Dice 0.93–0.96 on opening and closing chains on its synthetic Diskorect benchmark, and erosion learning "up to 100x slower on MNIST."
Our claim is that most of this gap comes from asking gradient descent to solve a combinatorial subproblem it is badly suited for. Fix one layer's input mask $X$ and target mask $Y$, and let the stencil be a subset $S$ of a window $W$. Exact erosion consistency then reads
$$Y(x)=1 \Rightarrow S\subseteq P_x,\qquad Y(x)=0 \Rightarrow S\cap N_x\neq\emptyset,$$
where $P_x=\{w\in W: X(x+w)=1\}$ and $N_x=W\setminus P_x$. Each pixel is therefore a clause over at most $|W|$ Boolean variables: 49 variables for a 7×7 window, regardless of image size. Making each pixel a soft clause turns noisy targets into a weighted MaxSAT instance. Dilation has the mirrored form.
The one-layer problem is therefore tiny and exactly solvable. In a chain, the only thing left that needs learning is the intermediate masks, and that is where a differentiable model earns its place. Because the solver treats erosion and dilation with the same encoding, the hybrid should remove the erosion penalty. Removing that penalty is the measurable prediction.
Relation to Prior Work
Three morphology papers motivate the gap. BiMoNN supplies the network, the benchmarks, and the erosion slowdown. Learning Deep Morphological Networks with NAS (Hu et al.) relaxes operator placement into a continuous space. Its search runs "approximately six days per task" and discards erosion because min-pooling suppresses gradients. This is independent evidence that continuous search avoids the operator we target. Counter-harmonic-mean smoothing (Angulo et al.; A Learning Framework for Morphological Operators Using Counter-Harmonic Mean) gives a second continuous relaxation, which interpolates between max and min. We use it as a baseline, not a mechanism.
InSeIn (Optimizing against Infeasible Inclusions from Data for Semantic Segmentation through Morphology) is the closest point where morphology meets logical constraints. It uses a fixed, parameter-free area opening as a soft loss and learns no stencils. We do the opposite: we learn stencils, and we enforce consistency exactly rather than as a penalty.
From hybrid optimization we borrow three techniques. From ruler (A Scalable Two Stage Approach to Computing Optimal Decision Sets) we take the idea of splitting a monolithic logic problem into small exact pieces. That split took it from 351 to 802 provably optimal datasets. From core-guided hitting-set MaxSAT (PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving) we take the per-layer solver. From automatic logic-based Benders decomposition (Automatic Logic-Based Benders Decomposition with MiniZinc) we take the habit of turning a subproblem's failure into a minimal explanation, a minimal unsatisfiable core, that is fed back to the coordinating problem.
DiffILO (Differentiable Integer Linear Programming) supplies the "neural proposal, exact repair" pattern: its standalone relaxation was feasible on only 50.8% of Set Covering instances and needed Gurobi to finish. DiffILO handles only linear constraints $Ax\le b$, however. Here the exact solver sits inside training rather than after it, and the constraints are morphological.
Research Program
The system alternates two phases.
In the network phase, a BiMoNN chain of $L$ layers trains on input–target pairs as usual. Its sigmoid-scale intermediate activations $\tilde Z_1,\dots,\tilde Z_{L-1}$ are rounded to masks $Z_l$ every $K$ steps.
In the solver phase, each layer $l$ receives the pair $(Z_{l-1}, Z_l)$, with $Z_0$ the input and $Z_L$ the target. For that pair it solves the MaxSAT instance above, with one soft clause per pixel and a free choice of erosion or dilation. The solver returns three things: the optimal stencil $S_l$, its exact error count, and the unsatisfiable cores. A core is a minimal set of pixels at layer $l$ whose constraints conflict, which means some pixel of $Z_{l-1}$ in their neighborhoods must change.
Two feedback channels return to the network.
The first is projection. Each layer's continuous weights are reset to the exact BiSE encoding of $S_l$, a warm restart in the DiffILO spirit. The BiSE encoding is exact by BiMoNN's construction.
The second is core feedback. The binary chain is run forward with the projected stencils, which yields $\hat Z_{l-1}$, layer $l-1$'s actual output. Each core is then turned into an extra loss on layer $l-1$'s output. For every pixel $p$ in a core's neighborhood, a cross-entropy term pushes $\tilde Z_{l-1}(p)$ toward the flipped value $1-\hat Z_{l-1}(p)$. Pixel $p$ is weighted by how many cores it touches, normalized to sum to one per core. This is the Benders-style "explain the failure, then fix the cause" step, applied to a neural proposer.
Training ends with the projected binary chain, which carries two certificates. Each layer's stencil is provably optimal for its realized intermediate masks. If total training error is zero, the whole pipeline is exactly consistent.
We will be honest about the limit. This is not a global optimality proof for nonzero error. For small windows we will compute the global optimum with a monolithic encoding, so the gap can be measured directly.
The analysis then asks three questions. Does the erosion/dilation time ratio collapse toward one? Does core feedback matter beyond projection? How does the advantage scale with chain depth, image size, and label noise?
Baselines
The naive reference point is BiMoNN trained exactly as published, then binarized with its Linear Check. This is also the strongest existing method on these benchmarks. It reports DICE error 0.000 on single disk and cross operations and Dice between 0.93 and 0.96 on Diskorect opening and closing (Binary Morphological Neural Network). For MNIST erosion it reports only a relative slowdown of up to 100x, not an absolute time. We rerun it on the same generated data, with the same initialization budget and the same wall-clock limit, tuning its learning rate and tanh scale with the same number of trials we give our method.
Beating it means two things. On erosion-containing chains, our method must reach a higher binarized Dice than BiMoNN's 0.93–0.96 on Diskorect. On MNIST it must shrink the erosion-to-dilation time ratio by at least an order of magnitude. Both comparisons count wall-clock time including solver calls.
A second continuous baseline is the counter-harmonic-mean relaxation, binarized by thresholding. This shows whether a different smoothing alone fixes the gap.
The key ablations isolate each piece of the hybrid. Projection-only drops the core feedback. Post-hoc-only trains BiMoNN to convergence and then applies a single exact projection. That isolates whether the solver must be in the loop, or whether the result is just a better replacement for the Linear Check. Finally, a random-proposal variant replaces the network's intermediate masks with masks obtained by applying a random stencil from the same window to the previous layer. It tests whether the network's proposals carry real information.
Why not just…?
Why not just learn erosion as a dilation of the complemented image? Erosion by $S$ equals the complement of dilating the complement by the reflected stencil. A BiSE could therefore be reparameterized so that every erosion is trained as a dilation sandwiched between two cheap, differentiable complements. If the asymmetry is purely a matter of how the operator is written down, this fixes it at no cost. That makes it a real threat. We will include this "dual-parameterized BiMoNN" as a first-class baseline. If it matches our method on both single-layer and chain erosion, then the solver's contribution reduces to binarization certificates, and we will say so. We expect it to help single layers but not chains. Our reason is the NAS paper's account that min-type operators suppress gradients through the non-selected inputs (Hu et al.). On that account, flipping polarity alone should not restore the missing gradient in a deep chain. The chain-depth experiment settles this.
Why not just encode the whole chain monolithically in MaxSAT? Make the intermediate pixels Boolean variables too, and one solver call returns the global optimum with a proof. For small images and few training pairs this will work, and we use it as ground truth. Our expected weakness is size. The encoding needs auxiliary variables roughly proportional to $L\cdot H\cdot W_{img}\cdot|W|$ per training image, where $H\times W_{img}$ is the image size. For 50×50 MNIST, a 7×7 window, and four layers, that is about half a million per image, multiplied by the number of training pairs. The same size wall is what pushed ruler to a decomposed design (A Scalable Two Stage Approach to Computing Optimal Decision Sets). No reported result was found on Lacuna for monolithic SAT learning of morphological chains. We will therefore measure exactly where the monolithic encoding stops finishing within the time limit.
Why not just run local search over binary stencils? Simulated annealing over the $2^{|W|}$ stencils per layer needs no gradients or solvers. However, it also inherits the problem of latent intermediate masks: scoring a stencil change at layer 1 requires re-running all later layers, so each move costs a full chain evaluation. We include it under equal wall-clock as a baseline. If it matches us, the claim that the network's proposals matter fails.
Proposed Experiments
All experiments use BiMoNN's benchmarks: Diskorect and binarized and inverted MNIST at 50×50 (Binary Morphological Neural Network). Targets are generated by known stencil chains of depth one to six, with windows from 3×3 to 9×9 and erosion fractions from zero to one. Bernoulli label noise is added at several rates.
The metrics are:
- binarized Dice on held-out images;
- exact-recovery rate of the ground-truth stencils, up to equivalent operators;
- wall-clock time to reach a Dice threshold;
- the ratio of that time for erosion versus dilation targets;
- the fraction of runs ending with a zero-error certificate;
- on small instances, the gap to the monolithic global optimum.
The decisive check is an erosion-sweep curve. Time-to-target and final Dice are plotted against the fraction of erosions in the chain, for every method. Our hypothesis predicts a flat curve for the hybrid. Continuous baselines should show a rising curve, consistent with BiMoNN's reported 100x MNIST gap.
Three outcomes would falsify the proposal:
- dual-parameterized BiMoNN produces an equally flat curve on deep chains;
- post-hoc projection matches in-loop training, which would mean the solver only needs to run once;
- the monolithic MaxSAT encoding remains within the time limit at MNIST scale for six-layer chains.
The secondary check is the core ablation. Core feedback should reduce the number of solver rounds needed to reach zero error on depth four and above, compared with projection only. The size of this reduction is the evidence that Benders-style explanations, and not just exact rounding, are what transfer from hybrid optimization to morphology.
References
- Binary Morphological Neural Network
- Learning Deep Morphological Networks with Neural Architecture Search
- A Learning Framework for Morphological Operators Using Counter-Harmonic Mean
- Optimizing against Infeasible Inclusions from Data for Semantic Segmentation through Morphology
- A Scalable Two Stage Approach to Computing Optimal Decision Sets
- PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving
- Automatic Logic-Based Benders Decomposition with MiniZinc
- Differentiable Integer Linear Programming