Computing Rand error efficiently

Question

I'm trying to compare two image segmentations to one another. In order to do so, I transform each image into a vector of unsigned short values, and calculate the rand error, according to the following formula:

where:

Here is my code (the rand error calculation part):

cv::Mat im1,im2;

//code for acquiring data for im1, im2
//code for copying im1(:)->v1, im2(:)->v2


int N = v1.size();
double a = 0;
double b = 0;
for (int i = 0; i <N; i++)
{
    for (int j = 0; j < i; j++)
    {
        unsigned short l1 = v1[i];
        unsigned short l2 = v1[j];
        unsigned short gt1 = v2[i];
        unsigned short gt2 = v2[j];
        if (l1 == l2 && gt1 == gt2)
        {
            a++;
        }
        else if (l1 != l2 && gt1 != gt2)
        {
            b++;
        }

    }
}

double NPairs = (double)(N*N)/2;
double res = (a + b) / NPairs;

My problem is that length of each vector is 307,200. Therefore the total number of iterations is 47,185,920,000.

It makes the running time of the entire process is very slow (a few minutes to compute). Do you have any idea how can I improve it?

Thanks!

Answer 1

Let's assume that we have P distinct labels in the first image and Q distinct labels in the second image. The key observation for efficient computation of Rand error, also called Rand index, is that the number of distinct labels is usually much smaller than the number of pixels (i.e. P, Q << n).

Step 1

First, pre-compute the following auxiliary data:

• the vector s₁, with size P, such that s₁[p] is the number of pixel positions i with v₁[i] = p.

• the vector s₂, with size Q, such that s₂[q] is the number of pixel positions i with v₂[i] = q.

• the matrix M, with size P x Q, such that M[p][q] is the number of pixel positions i with v₁[i] = p and v₂[i] = q.

The vectors s₁, s₂ and the matrix M can be computed by passing once through the input images, i.e. in O(n).

Step 2

Once s₁, s₂ and M are available, a and b can be computed efficiently:

This holds because each pair of pixels (i, j) that we are interested in has the property that both its pixels have the same label in image 1, i.e. v₁[i] = v₁[j] = p; and the same label in image 2, i.e. v₂[i] = v₂[ j ] = q. Since v₁[i] = p and v₂[i] = q, the pixel i will contribute to the bin M[p][q], and the same does the pixel j. Therefore, for each combination of labels p and q we need to consider the number of pairs of pixels that fall into the M[p][q] bin, and then to sum them up for all possible labels p and q.

Similarly, for b we have:

Here, we are counting how many pairs are formed with one of the pixels falling into the bin M[p][q]. Such a pixel can form a good pair with each pixel that is falling into a bin M[p'][q'], with the condition that p != p' and q != q'. Summing over all such M[p'][q'] is equivalent to subtracting from the sum over the entire matrix M (this sum is n) the sum on row p (i.e. s₁[p]) and the sum on the column q (i.e. s₂[q]). However, after subtracting the row and column sums, we have subtracted M[p][q] twice, and this is why it is added at the end of the expression above. Finally, this is divided by 2 because each pair was counted twice (once for each of its two constituent pixels as being part of a bin M[p][q] in the argument above).

---

The Rand error (Rand index) can now be computed as:

The overall complexity of this method is O(n) + O(PQ), with the first term usually being the dominant one.