Page MenuHome

Possible bug in libmv in track_region.cc with mask enabled
Confirmed, NormalPublicKNOWN ISSUE

Description

This is a possible bug I found while browsing the source code, so far I don't have a way to reproduce it in Blender.
I was experimenting with libmv in my own project, and I wanted to add a weight to the pixel cost. It turned out that adding a weight (or mask) broke the NCC computation. See this part of the code (track_region.cc):

    if (options_.image1_mask != NULL) {
      x *= mask_value; // XXX assume mask_value is 0.1, now x = x * 0.1
      y *= mask_value;
      num_samples += mask_value; // XXX num_saples += 0.1
    } else {
      num_samples++;
    }
    sX += x; // XXX so this becomes sX += x*0.1, so far so good
    sY += y;
    sXX += x*x; // XXX here sXX += x*0.1*x*0.1, i.e. the weight will be added twice...
    sYY += y*y;
    sXY += x*y;
  }
}
// Normalize.
sX /= num_samples;
sY /= num_samples;
sXX /= num_samples; // XXX so when we normalize here, sXX will be 0.1 times the value it supposed to be.
sYY /= num_samples;
sXY /= num_samples;

Changing the above code to something like:

if (options_.image1_mask != NULL) {
  num_samples += mask_value;
} else {
  num_samples++;
}
sX += x * mask_value;
sY += y * mask_value;
sXX += x*x * mask_value;
sYY += y*y * mask_value;
sXY += x*y * mask_value;

Worked fine in my code.

Note: probably this is not so noticeable in Blender, since most often the mask_value is either 1 (i.e. no bug) or 0 (in which case the value is skipped, again no bug).
This bug should appear only if many of the mask_values are between 0 and 1.

Event Timeline

sXX is supposed to be a sum of squared weighted samples (as in, sum of x * x, where x is actually a weighted sample). So I don't think the issue is there.

One thing which i see from a quick look into the code is that covariance is calculated as it's approximation, presumably, to save time calculating mean value of samples.

What i would try is to use more accurate calculation of covariance [1] and see if that solves your problem.

But i also would like to know how we can see the issue from our side.

[1] https://en.wikipedia.org/wiki/Pearson_correlation_coefficient#Weighted_correlation_coefficient

I'll try to reproduce this in Blender, but it will take some time.
Meanwhile, let's take an example: let's just take two values for x, 8 and 10, and let's ignore Y, so just compute the variance of x

First case: all weights are 1.0:

x = { 8, 10 }
num_samples = 2
sX = (8 + 10) / 2 = 9
sXX = (8^2 + 10^2) / 2 = (64 + 100) / 2 = 82;
var_x = 82 - 81 = 1; // Correct

Now assume all weights are 0.1 (we expect the same result, since all weights are equal):

num_samples = 0.2
sX = (8*0.1 + 10*0.1) / 0.2 = 1.8/0.2 = 9
sXX = (0.8^2 + 1.0*^2) / 0.2 = 1.64 / 0.2 = 8.2
var_x = 8.2 - 81 = -72.8 !!! Very bad, this doesn't supposed to be negative

Now with the new formula, all weights are 0.1:

x = { 8, 10 }
num_samples = 0.2
sX = (0.8 + 1.0) / 0.2 = 9
sXX = (8*8*0.1 + 10*10*0.1) / 0.2 = 16.4 / 0.2 = 82
var_x = 82 - 81 = 1; // Correct

If the weights are different, assume x = { 8, 10 } w = { 1, 4 }

num_samples = 5 // 1 + 4
sX = (8*1 + 10*4) / 5 = 48 / 5 = 9.6
sXX = (8*8*1 + 10*10*4) / 5 = 464 / 5 = 92.8
var_x = 92.8 - 9.6^2 = 92.8 - 92.16 = 0.64 // Probably correct, looks sane at least

I'll try to reproduce this in Blender, but it will take some time.

It doesn't need to be directly reproducable with Blender, is probably not possible with just using interface.

Just knowing what configuration of a mask you're using and such will help creating a regression test and troubleshoot what's going on.

The calculations you've shown clearly shows that math is obviously wrong. But i would like to have a more real life case to see whether fix is indeed working and such.

// Probably correct, looks sane at least

From my understanding result of all weights of 0.1 the covariance of x should be exactly the same as in the case of all weights of 1 (since there is same exact trust to all of the values).

Running through the formulas:

                                   8*0.1 + 10*0.1   0.8 + 1.0
m(x, w) = m([8, 10], [0.1, 0.1]) = -------------- = --------- = 9
                                      0.1 + 0.1       0.2


cov(x, x, w) = cov([8, 10], [8, 10], [0.1, 0.1]) =

    0.1*(8 - 9)^2 + 0.1*(10 - 9)^2    0.1*1 + 0.1*1
  = ------------------------------ =  ------------- = 1
              0.1 + 0.1                     0.2

I think the issue is coming from the fact that an approximation for covariance is used, to make calculation a single-pass.

We can make a few passes in the following way:

  • Pass once, to collect values for x, y, and w, so we don't need to apply warping and sample image multiple pass.
  • Calculate median values (which can be done at the same loop as sampling the images)
  • Calculate proper covariance.
  • See if that behaves correct for your usecase.

Let me know if you need help with implementation or whether you can run such test yourself.

Sergey Sharybin (sergey) lowered the priority of this task from 90 to Normal.Sep 26 2019, 12:23 PM
Jeroen Bakker (jbakker) changed the subtype of this task from "Report" to "Known Issue".Feb 4 2020, 10:46 AM

This seems like an improvement of existing code. Will set it to todo as it hasn't seen activity in the past 3 months