Source-linked AI summary
Maximin affinity learning of image segmentation
Srinivas C. Turaga, Kevin L. Briggman, Moritz Helmstaedter, Winfried Denk, H. Sebastian Seung
TL;DR
Affinity-edge error is only indirectly related to the quality of a partitioned segmentation. MALIS trains maximin affinities using a Rand-index objective and connected-components partitioning, and its classifier dramatically outperforms standard affinity learning on ROC and precision-recall curves.
Problem
Method
MALIS trains a nearest-neighbor affinity classifier against Rand-index segmentation error after thresholding and connected-components partitioning, emphasizing maximin edges.
Source: §1 · pp. 1–2Results
Over 95% Rand index for both algorithms on many-segment images, while ROC and precision-recall curves show the maximin affinity classifier dramatically outperforming the standard affinity classifier.
Source: §7.3 · p. 7Takeaways & Limitations
Thresholded affinity classification followed by connected components can be extremely competitive when trained with a segmentation-based cost, and the trained algorithm is fast.
Source: §7.3 · p. 7, §8 · p. 7Maximin computation requires the whole-image affinity graph on each iteration, making learning slower than standard local affinity learning.
Source: §6 · p. 6
Abstract
from arXiv · showhide
Images can be segmented by first using a classifier to predict an affinity graph that reflects the degree to which image pixels must be grouped together and then partitioning the graph to yield a segmentation. Machine learning has been applied to the affinity classifier to produce affinity graphs that are good in the sense of minimizing edge misclassification rates. However, this error measure is only indirectly related to the quality of segmentations produced by ultimately partitioning the affinity graph. We present the first machine learning algorithm for training a classifier to produce affinity graphs that are good in the sense of producing segmentations that directly minimize the Rand index, a well known segmentation performance measure. The Rand index measures segmentation performance by quantifying the classification of the connectivity of image pixel pairs after segmentation. By using the simple graph partitioning algorithm of finding the connected components of the thresholded affinity graph, we are able to train an affinity classifier to directly minimize the Rand index of segmentations resulting from the graph partitioning. Our learning algorithm corresponds to the learning of maximin affinities between image pixel pairs, which are predictive of the pixel-pair connectivity.
1 Introduction
The section frames segmentation learning as optimizing segmentation quality rather than affinity-edge accuracy alone. It introduces MALIS, which predicts nearest-neighbor affinities, partitions the thresholded graph by connected components, and trains against the Rand index.
1 Introduction
- The method predicts nearest-neighbor affinity weights, thresholds the graph, finds connected components, and adjusts classifier parameters by gradient learning against the Rand index.The thresholding is softened during learning.Source: §1 · p. 1
- MALIS focuses learning on maximin edges because misclassifying them can cause genuine segmentation errors by splitting or merging segments.The method is named for maximin affinity learning of image segmentation.Source: §1 · p. 2
- MALIS is presented as the first supervised method to optimize a genuine segmentation-performance measure, unlike prior edge-error training or normalized-cut approaches that do not optimize such a measure.Bach and Jordan minimize only an upper bound to a renormalized Rand index; both approaches require approximations for tractable learning.Source: §1 · p. 2
- The classifier can resemble a boundary detector, but its parameters are trained for Rand-index segmentation performance rather than boundary-detection performance.A nearest-neighbor affinity graph is essentially a boundary map up to sign inversion.Source: §1 · p. 2
- Markov or conditional random-field labeling is closer to multiclass pixel classification; cited parsing models were simplistic or piecemeal and were not trained to minimize Rand index [12, 22].Source: §1 · p. 2
2 Partitioning a thresholded affinity graph by connected components
The section describes segmentation as thresholding a nearest-neighbor affinity graph and taking its connected components. This simple partitioner supports direct supervised optimization, while the discussion notes trade-offs and assumptions behind the design.
2 Partitioning a thresholded affinity graph by connected components
- The classifier assigns affinities to edges between nearest-neighbor image pixels using an image patch surrounding each edge; higher affinity means the pixels tend to belong to the same segment.Graph nodes are image pixels.Source: §2 · pp. 2–3
- Removing edges below threshold θ and taking the remaining graph's connected components produces the image segments.Source: §2 · p. 3
- A single affinity-edge error can dramatically change the segmentation by splitting or merging segments, motivating learning against segmentation performance rather than affinity prediction.Source: §2 · p. 3
- Connected components is simple, but that simplicity permits a direct supervised method for optimizing a true measure of segmentation performance.The section contrasts this with learning based on more sophisticated partitioners.Source: §2 · p. 3
- The authors favor putting sophistication in a sufficiently powerful trainable classifier rather than a hand-designed partitioner, while noting that sophisticated partitioners rely on prior assumptions that may be incorrect.They hope the classifier can learn useful partitioning strategies from training data.Source: §2 · p. 3
3 The Rand index quantifies segmentation performance
The section defines segmentation quality through pixel-pair connectivity disagreements between a test segmentation and ground truth. It explains why the Rand index penalizes split and merger errors according to the affected pairs.
3 The Rand index quantifies segmentation performance
- In this paper, 1 − RI is called the Rand index and measures the fraction of pixel pairs on which the segmentations disagree, although RI strictly measures agreement.Source: §3 · p. 3
- The Rand index is used as the learning objective by comparing the algorithm's segmentation with ground truth, penalizing affinity errors that produce split or merger errors.A wrongly classified edge can merge segments and misassign many pixel pairs, whereas affinity misclassifications need not always harm the segmentation.Source: §3 · p. 3
- The Rand index compares pixel-pair connectivity in the two segmentations; disagreements occur when pairs that should be connected are separated or pairs that should be separate are connected.The connectivity matrices are symmetric and block-diagonal, with each diagonal block representing connected pairs within a segment.Source: §3 · p. 3, Figure 2 · p. 4
4 Connectivity and maximin affinity
In a thresholded affinity graph, two pixels are connected exactly when their maximin affinity exceeds the threshold. This gives a way to infer pixel-pair connectivity from the graph’s affinities.
4 Connectivity and maximin affinity
- A pixel pair’s maximin affinity is the greatest, over paths joining the pair, of each path’s weakest edge affinity.It is also the affinity of the maximin edge, or the minimum affinity along the maximin path.Source: §4 · p. 4
- A pixel pair is connected in the thresholded affinity graph if and only if its maximin affinity exceeds the threshold.The connectivity indicator is expressed by thresholding maximin affinity with the Heaviside step function.Source: §4 · p. 4
- A maximum spanning tree supports maximin-path computation in O(|E| · α(|V|)); all-pairs values take O(|V|^2), while test-time connected components take O(|E|).Maximin affinities are needed for training, but not for test-time segmentation.Source: §4 · pp. 4–5
5 Optimizing the Rand index by learning maximin affinities
The learning objective uses maximin affinities to relate classifier outputs to pixel-pair connectivity, then relaxes the discontinuous objective for gradient learning. Unlike standard affinity learning, MALIS sums over all pixel pairs and weights edges by the number of pairs they cause to be misclassified.
5 Optimizing the Rand index by learning maximin affinities
- The objective replaces the discontinuous function of maximin affinities with a relaxed loss, for which square or hinge loss can be used.The affinities and maximin affinities are functions of image I and classifier parameters W.Source: §5 · p. 5
- When the loss and affinity are smooth, continuity and differentiability of the max and min operations make the cost gradient well-defined for gradient descent.The max and min operations are differentiable but not continuously differentiable.Source: §5 · p. 5
- MALIS sums over all pixel pairs, unlike standard affinity learning’s sum over nearest-neighbor pairs, so an edge can be weighted by the number of pairs it misclassifies.A single edge may be the maximin edge for multiple pixel pairs.Source: §5 · p. 5
6 Online stochastic gradient descent
Online stochastic learning updates parameters after each pixel pair, training the maximin edge on a path between the sampled pixels. It trains global connectivity decisions but requires whole-image affinity computation, making it slower than standard local affinity learning.
6 Online stochastic gradient descent
- Online stochastic gradient learning updates parameters after each pixel pair and may be more efficient than batch learning.Batch computation requires finding maximin edges for all pixel pairs.Source: §6 · pp. 5–6
- Standard learning samples a nearest-neighbor pair and trains its edge, whereas MALIS samples an arbitrary-separation pair and trains the minimum-affinity edge on its maximin path.Both methods select a random pixel pair from a random image at each iteration.Source: §6 · p. 6
- MALIS trains long-distance connectivity decisions, but each update requires the affinity graph for the whole image, making it slower than standard local learning.The computational cost is the price of optimizing a true segmentation error.Source: §6 · p. 6
7 Application to electron microscopic images of neurons
On rabbit-retina electron-microscopy volumes, MALIS trained affinity classifiers for segmentation and dramatically outperformed standard affinity learning on pixel-pair connectivity measures. The application used convolutional networks and a proxy training set that limited the maximum separation of training pairs.
7.1 Electron microscopic images of neural tissue
- The experiments used two hand-segmented 100^3-voxel rabbit-retina image volumes for training and testing, collected with serial block-face scanning electron microscopy.The study frames this data as a high-resolution neural-tissue segmentation task relevant to reconstructing neural wiring diagrams.Source: §7.1 · p. 6
7.2 Training convolutional networks for affinity classification
- The authors trained identical four-layer convolutional networks with standard affinity learning or MALIS; the method can also use any classifier smooth in its parameters.Training used overlapping 21 × 21 × 21 sub-images to reduce graph size, limiting training-pair separation to less than about 20 pixels; standard-cost pretraining accelerated MALIS training.Source: §7.2 · pp. 6–7
7.3 Maximin learning leads to dramatic improvement in segmentation performance
- MALIS dramatically outperformed the standard affinity classifier on ROC and precision-recall evaluations, although Rand index exceeded 95% for both methods.The evaluation plotted Rand index across threshold values; the figure also reports near-perfect connectivity-classification performance and measures segmentation error by splits and mergers.Source: §7.3 · p. 7, Figure 3 · p. 7
- The results suggest that properly trained affinities can make thresholding followed by connected components highly competitive despite the method’s simplicity.The standard and maximin segmentations differed in objects merged by the standard result and objects missing from the ground-truth segmentation.Source: §7.3 · p. 7
8 Discussion
The discussion presents thresholding and connected components as a simple, fast way to partition learned affinity graphs. It relates maximin affinity learning to hierarchical clustering and graph-based segmentation methods.
8 Discussion
- The maximin segmentation correctly separates some objects merged in the standard segmentation and segments some objects absent from the ground truth.Figure 4 shows a 2D cross-section through a 3D test-image segmentation; black pixels mark fully disconnected boundary regions.Source: Figure 4 · p. 8
- Connected-components partitioning runs in time linear in the number of graph edges and requires no prior knowledge of segment counts or sizes at test time.These properties contrast with other graph-partitioning algorithms [7, 20].Source: §8 · p. 8
- Maximin affinities connect to single-linkage clustering, minimum spanning trees, and ultrametric distances, and learning them can improve related segmentation algorithms.The discussion notes that the Ultrametric Contour Map produces hierarchical segmentations nearly identical to those obtained by varying the partitioning threshold.Source: §8 · p. 8