As it turns out, my C++ functions suck. Really bad. Since my python functions turned out to be alright, I started developing their vigra counterparts. After a long night I finally got the python interface to the UnionFind data structure somewhat right, and I turned to the implementation of the mergeLabels function.

This function should simply inspect two adjacent chunks, find labeled regions that cross the boundary and merge the corresponding labels in the global UnionFind structure. A fairly simple task, as you can see from my python implementation:

1
2
3
4
5
6
7
8
9
10
11
def mergeLabels(hyperplane_a, hyperplane_b,
                label_hyperplane_a, label_hyperplane_b,
                mapping_a, mapping_b, GUF):
 
    # the indices where objects are adjacent
    idx = hyperplane_a == hyperplane_b
 
    # merge each pair of labels
    for label_a, label_b in zip(label_hyperplane_a[idx],
                                label_hyperplane_b[idx]):
        GUF.makeUnion(mapping_a[label_a], mapping_b[label_b])

But converting this into a vigra function turned out to be not that trivial. Consider this naive port (skip to line 24 if you are not familiar with vigra) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template <int N, class PixelType, class LabelType>
void mergeLabels(MultiArrayView<N, PixelType> const & left,
                 MultiArrayView<N, PixelType> const & right,
                 MultiArrayView<N, LabelType> const & leftLabels,
                 MultiArrayView<N, LabelType> const & rightLabels,
                 MultiArrayView<1, LabelType> const & leftMap,
                 MultiArrayView<1, LabelType> const & rightMap,
                 detail::UnionFindArray<LabelType> & unionFind
                 ) {
    vigra_precondition(left.shape() == right.shape(), "Shape mismatch");
    vigra_precondition(leftLabels.shape() == rightLabels.shape(), "Shape mismatch");
    vigra_precondition(leftLabels.shape() == left.shape(), "Shape mismatch");
 
    const MultiArrayIndex LEFT_PIXEL = 1;
    const MultiArrayIndex RIGHT_PIXEL = 2;
    const MultiArrayIndex LEFT_LABEL = 3;
    const MultiArrayIndex RIGHT_LABEL = 4;    
 
    typedef typename CoupledIteratorType<N, PixelType, PixelType, LabelType, LabelType>::type Iterator;
 
    Iterator start = createCoupledIterator(left, right, leftLabels, rightLabels);
    Iterator end = start.getEndIterator();
 
    for (Iterator it = start; it < end; it++) 
    {
        if (it.get<LEFT_PIXEL>() == it.get<RIGHT_PIXEL>()) 
        {
            unionFind.makeUnion(leftMap[it.get<LEFT_LABEL>()],
                                rightMap[it.get<RIGHT_LABEL>()]);
        }
    }
}

This does actually do what we want, and we are using a C-loop over the blocks so we should be fine performance-wise, shouldn’t we? Guess again. A little benchmark showed these results:

pyMergeLabels() for shape (10, 100, 100):
    0.014s
cMergeLabels() for shape (10, 100, 100):
    0.293s

This is just sad. Numpy is actually about 20 times faster than my C++ function, even with a favourable axis order. I guess I’m gonna stick to my python function until I figure out why my array traversal is so slow.