Supervoxels: small pieces to merge
Read these first if they are new to you
- Segmentation: a label for every voxel Intermediate
The idea in one paragraph
Many segmentation programs work in two steps. First they cut the image into many small pieces, called supervoxels, each very likely to lie inside one object. Then they join pieces that seem to belong together. The result is kept as a table that says which object each supervoxel belongs to. Joining two pieces, or undoing a join, changes only that table. The voxels inside each supervoxel never change.
Cutting too finely is safer than cutting too coarsely
A program that makes a segmentation must decide, at every membrane between cells, whether the membrane is real. Some membranes are faint, so it will sometimes be wrong. There are two ways to be wrong.
- It can leave one cell in several pieces. Fixing that means joining pieces: an easy change.
- It can put parts of two cells in one piece. Fixing that means deciding, voxel by voxel, where the cut should go: a hard change.
So the first step cuts generously. It produces a supervoxel: a small group of neighboring voxels that the program is confident lies inside a single object. An image cut this way is over-segmented: it has many more pieces than objects, but almost no piece spans two objects.
A second step joins the pieces into objects
The second step, called agglomeration, joins supervoxels. For each pair of touching supervoxels, the program computes a score from 0 to 1 for how likely they belong to the same object. It joins the pair with the highest score first and continues down the list. It stops when the next score falls below a chosen threshold, here 0.5.
The figure shows two thin, neuron-like objects cut into six supervoxels. They touch at one spot. Before you press anything, predict: how many objects will remain when the program stops?
| Supervoxel | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Object | 1 | 2 | 3 | 4 | 5 | 6 |
Two objects remain: {1, 2, 3} and {4, 5, 6}. The touching spot was a trap. Pieces 2 and 5 touch, but the membrane between them is clear, so their score is low.
You can draw the same process as a graph: each supervoxel is a dot, and each join is a line between two dots. The objects are then the connected pieces of that graph.
A lookup table turns supervoxels into objects
The image of supervoxel numbers is computed once and stored. The joins live in a small separate table that maps each supervoxel to its object. To get the segmentation, replace every supervoxel number by its entry in the table.
- Start with six supervoxels, each its own object: 1→1, 2→2, 3→3, 4→4, 5→5, 6→6.
- Join (1, 2), (2, 3), (4, 5) and (5, 6). The objects are {1, 2, 3} and {4, 5, 6}.
- Name each object after its lowest supervoxel. The table becomes 1→1, 2→1, 3→1, 4→4, 5→4, 6→4.
- Now undo the join (2, 3). Supervoxel 3 becomes an object of its own, so only one entry changes: 3→3.
Undoing the join changed one number in the table and no voxels at all.
In NumPy the table is an array, and indexing with the supervoxel image applies it to every voxel at once.
supervoxels.py
import numpy as np
sv = np.array([ # supervoxel ids in a tiny 2 x 6 slice
[1, 1, 2, 2, 3, 3],
[4, 4, 5, 5, 6, 6],
])
lut = np.array([0, 1, 1, 1, 4, 4, 4]) # lut[s] is the object of supervoxel s
print(lut[sv])
lut[3] = 3 # undo one join: supervoxel 3 becomes its own object
print(lut[sv])
[[1 1 1 1 1 1]
[4 4 4 4 4 4]]
[[1 1 1 1 3 3]
[4 4 4 4 4 4]]Real programs compute each score from the membranes the network predicts along the whole surface two supervoxels share. After each join they recompute the scores between the new, larger object and its neighbors, which is why the order of joins matters. They often join in several rounds at growing scales. Supervoxels are also not always right: now and then one spans two objects, and then someone must edit its voxels. In general computer vision, "supervoxel" can also mean any small region of similar voxels, the 3D form of a 2D superpixel.
Check yourself
-
Why does the first step aim for too many pieces rather than too few?
Answer
Extra pieces are fixed by joining, which changes only the table. A piece that covers two objects must be cut, which means deciding where the boundary runs through its voxels. Joining is much cheaper and easier to undo.
-
Six supervoxels are joined by (1, 4), (4, 6) and (2, 3). Write the table, naming each object after its lowest supervoxel.
Answer
The objects are {1, 4, 6}, {2, 3} and {5}. The table is 1→1, 2→2, 3→2, 4→1, 5→5, 6→1.
-
An object made of 1,000 supervoxels and 50 million voxels is split back into two parts of 400 and 600 supervoxels. What is the smallest number of table entries that must change? How many voxels of the supervoxel image change?
Answer
400 table entries. One part can keep the old object number, so only the other part's supervoxels need a new entry; giving the new number to the smaller part changes 400. No voxels of the supervoxel image change.
Go further
Optional background. This unit covers what you need here.
-
Comparison of segmentation and superpixel algorithms: SLIC scikit-image gallery Tutorial Intermediate
Shows four ways to cut a 2D photo into many small pieces, so you can see over-segmentation on a real image.
Where this shows up
Units that build on this one
- Two kinds of segmentation error Intermediate
- Proofreading a segmentation Intermediate