[Feature Request] add "must-not-link" constraints

[jewettaij]

The ClusterConnected() function (in clustering.hpp) already allows users the ability to merge different clusters, even if they do not appear to be connected. These are called "must-link" constraints. These are very useful when automatic detection fails, and manual user intervention is needed. However, I have not yet added "must-not-link" constraints. This is also very important because it provids a way for users to use more sensitive thresholds (allowing them to see more of the object they want to see) without accidentally merging two different blobs together. To avoid this, the ClusterConnected() function should accept an additional argument containing an array of pairs voxels (triplets of integers) that should not be merged into the same cluster. (Those pairs of voxels can be specified manually by the user.)

Implementation details

This issue was put here to remind me to add this feature later. The rest of its description is a note-to-myself to be read at some future date when I decide to work on this.

Suppose the additional argument added to ClusterConnected() is implemented this way:

 const vector<vector<array<Coordinate, 3> > > *pMustNotLinkConstraints=nullptr

If pMustNotLinkConstraints != nullptr, then convert this into a lookup table. Create a new variable "mustnot_partners" (of type map<array<Coordinate, 3>, array<Coordinate, 3>>) which can be used to quickly lookup whether a voxel belongs to a must-not-link pair, and who it's paired voxel is. Each cluster should maintain a set of "mustnot_voxels" (of type set<array<Coordinate, 3>>). Before a voxel is added to a cluster, see if it belongs to another cluster already. If not, loop through the mustnot_partners of that voxel (if any) and see if they appear in the list of mustnot_voxels for this cluster, and if so, don't include this voxel. If it does belong to another cluster, then loop through all the mustnot_voxels in both that cluster and this cluster (a double-loop) and check whether they appear in the forbidden list of mustnot_partners. If not, merge the clusters (and the mustnot_voxels).

This implementation behaves reasonably regardless of what pairs of voxels are supplied. (I.E., It behaves gracefully even if the user is careless and the two voxels (in a must-not-link pair) clearly belong to the same blob (watershed basin).)

Running time

The running time is proportional to O(n m^2 log(m)), where n is the number of voxels and m is the number of must-not-link constraints. (More precisely, m is maximum number of must-not-link constraints that fall into the same cluster (watershed basin), and n is the number of voxels that fall into any cluster, which for membranes is typically about 1% of the number of voxels in the image. If O(n m^2 log(m)) is too slow, I can implement the mustnot_partners lookup table as a 3D array. But this will waste a lot of memory, and I'm not worried about speed. I don't expect m to be very large. Most of the time, these constraints are not necessary, so m=0. At other times I expect m=1 or m=2.)