FREAK Orientation computation is unnecessarily imprecise

[pieter3d]

https://github.com/Itseez/opencv_contrib/blob/master/modules/xfeatures2d/src/freak.cpp#L536

In freak.cpp, line 536, a division by 2048 is performed. Since all values are integer, a round towards negative infinity is implied. Round correction should be performed, or better yet add 1024 and shift down by 11.

[pieter3d]

Actually looking at it more, the division can simply be removed. The common factor is canceled out in the atan2 operation anyway. All the division accomplishes now is extra CPU load, and loss of precision.

[pieter3d]

The computation of delta is also missing a round correct in the event that srcMatType is not an integer type.

[pieter3d]

Anyone care to comment? It seems to me a lot of precision is thrown away, introducing unnecessary noise.

[bmagyar]

I see your point. Maybe you could provide a single main.CPP with an example that spits out some relevant indication numbers.

[pieter3d]

Alright, here is a small program that shows what kinds of errors you can get with the division. You can see in the printouts that the errors are particularly large when the sample point values are close to each other.

The constants in the code below are directly from the computed arrays in freak.cpp

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define PI 3.14159265358979323846

const int orientation_pairs[45][2] = {
  { 0 , 3  }, { 1 , 4  }, { 2 , 5  }, { 0 , 2  }, { 1 , 3  }, { 2 , 4  }, { 3 , 5  }, { 4 , 0  }, { 5 , 1  },
  { 6 , 9  }, { 7 , 10 }, { 8 , 11 }, { 6 , 8  }, { 7 , 9  }, { 8 , 10 }, { 9 , 11 }, { 10, 6  }, { 11, 7  },
  { 12, 15 }, { 13, 16 }, { 14, 17 }, { 12, 14 }, { 13, 15 }, { 14, 16 }, { 15, 17 }, { 16, 12 }, { 17, 13 },
  { 18, 21 }, { 19, 22 }, { 20, 23 }, { 18, 20 }, { 19, 21 }, { 20, 22 }, { 21, 23 }, { 22, 18 }, { 23, 19 },
  { 24, 27 }, { 25, 28 }, { 26, 29 },
  { 30, 33 }, { 31, 34 }, { 32, 35 },
  { 36, 39 }, { 37, 40 }, { 38, 41 },
};

const int orientation_weights[][2] = {
  { -767, 1330 }, 
  {  768, 1330 }, 
  { 1536, 0    }, 
  { -997, 576  }, 
  {    0, 1152 }, 
  {  998, 576  }, 
  { -383, 665  }, 
  {  384, 665  }, 
  {  768, 0    }, 
  {  296, -511 }, 
  { -295, -511 }, 
  { -590, 0    }, 
  { -295, 512  }, 
  {  296, 512  }, 
  {  591, 0    }, 
  { -442, 256  }, 
  {    0, 512  }, 
  {  443, 256  }, 
  {    0, -408 }, 
  { -353, -204 }, 
  { -353, 205  }, 
  {    0, 409  }, 
  {  354, 205  }, 
  {  354, -204 }, 
  { -176, 307  }, 
  {  177, 307  }, 
  {  354, 0    }, 
  {  148, -255 }, 
  { -147, -255 }, 
  { -295, 0    }, 
  { -147, 256  }, 
  {  148, 256  }, 
  {  296, 0    }, 
  { -221, 128  }, 
  {    0, 256  }, 
  {  222, 128  }, 
  {    0, -221 }, 
  { -191, -110 }, 
  { -191, 111  }, 
  {    0, 222  }, 
  {  192, 111  }, 
  {  192, -110 }, 
  {  -95, 166  }, 
  {   96, 166  }, 
  {  192, 0    } };

int main(void) {

  int points[43];


  // Various spreads of point values, analyze a few types of point distributions
  for(int s = 5; s < 200; ++s) {
    // Generate values that fluctuate around grey 128, with swing s
    int min_val = 128 - s/2;
    const int num_runs = 10000;
    double angle_error = 0;
    double angle_error_abs = 0;
    for(int n = 0; n < num_runs; ++n) {

      // Generate random set of points
      for(int i = 0; i < 43; ++i) {
        points[i] = (rand() % s) + min_val;
      }

      // Find orientation as in freak.cpp
      int dx = 0;
      int dy = 0;
      for(int i = 0; i < 45; ++i) {
        int delta = points[orientation_pairs[i][0]] - points[orientation_pairs[i][1]];
        dx += delta*orientation_weights[i][0] / 2048;
        dy += delta*orientation_weights[i][1] / 2048;
      }
      double freak_angle = atan2(dy,dx) * 180 / PI;

      // Find the angle again, but skip the divide
      dx = 0;
      dy = 0;
      for(int i = 0; i < 45; ++i) {
        int delta = points[orientation_pairs[i][0]] - points[orientation_pairs[i][1]];
        dx += delta*orientation_weights[i][0];
        dy += delta*orientation_weights[i][1];
      }
      double accurate_angle = atan2(dy,dx) * 180 / PI;

      angle_error += freak_angle - accurate_angle;
      angle_error_abs += fabs(freak_angle - accurate_angle);
    }
    angle_error /= num_runs;
    angle_error_abs /= num_runs;

    printf("With point swing value %d, average error is %.3f, average error magnitude is %.3f\n", s, angle_error, angle_error_abs);
  }

  return 0;
}

Output of this program:

With point swing value 5, average error is 11.783, average error magnitude is 58.466
With point swing value 6, average error is 10.198, average error magnitude is 54.088
With point swing value 7, average error is 8.659, average error magnitude is 49.261
With point swing value 8, average error is 7.485, average error magnitude is 45.214
With point swing value 9, average error is 5.347, average error magnitude is 43.540
With point swing value 10, average error is 5.719, average error magnitude is 40.370
With point swing value 11, average error is 7.022, average error magnitude is 38.092
With point swing value 12, average error is 3.531, average error magnitude is 35.557
With point swing value 13, average error is 5.086, average error magnitude is 34.616
With point swing value 14, average error is 4.621, average error magnitude is 31.094
With point swing value 15, average error is 3.281, average error magnitude is 30.144
With point swing value 16, average error is 4.180, average error magnitude is 27.582
With point swing value 17, average error is 2.849, average error magnitude is 27.245
With point swing value 18, average error is 3.338, average error magnitude is 24.729
With point swing value 19, average error is 2.301, average error magnitude is 24.419
With point swing value 20, average error is 3.767, average error magnitude is 23.923
With point swing value 21, average error is 3.261, average error magnitude is 22.930
With point swing value 22, average error is 2.859, average error magnitude is 23.153
With point swing value 23, average error is 1.834, average error magnitude is 20.642
With point swing value 24, average error is 2.352, average error magnitude is 19.117
With point swing value 25, average error is 3.393, average error magnitude is 20.227
With point swing value 26, average error is 2.542, average error magnitude is 18.733
With point swing value 27, average error is 2.373, average error magnitude is 17.374
With point swing value 28, average error is 1.738, average error magnitude is 17.819
With point swing value 29, average error is 2.362, average error magnitude is 16.946
With point swing value 30, average error is 2.366, average error magnitude is 17.459
With point swing value 31, average error is 1.965, average error magnitude is 15.048
With point swing value 32, average error is 0.906, average error magnitude is 15.282
With point swing value 33, average error is 1.172, average error magnitude is 15.455
With point swing value 34, average error is 1.660, average error magnitude is 15.084
With point swing value 35, average error is 2.530, average error magnitude is 15.007
With point swing value 36, average error is 1.875, average error magnitude is 13.387
With point swing value 37, average error is 2.371, average error magnitude is 13.749
With point swing value 38, average error is 1.483, average error magnitude is 13.337
With point swing value 39, average error is 1.896, average error magnitude is 13.246
With point swing value 40, average error is 2.117, average error magnitude is 13.778
With point swing value 41, average error is 1.403, average error magnitude is 12.430
With point swing value 42, average error is 2.813, average error magnitude is 12.095
With point swing value 43, average error is 1.144, average error magnitude is 11.953
With point swing value 44, average error is 1.601, average error magnitude is 11.636
With point swing value 45, average error is 1.372, average error magnitude is 12.437
With point swing value 46, average error is 0.768, average error magnitude is 10.607
With point swing value 47, average error is 1.295, average error magnitude is 11.526
With point swing value 48, average error is 0.627, average error magnitude is 10.195
With point swing value 49, average error is 1.133, average error magnitude is 10.237
With point swing value 50, average error is 1.209, average error magnitude is 10.233
With point swing value 51, average error is 0.729, average error magnitude is 9.123
With point swing value 52, average error is 0.651, average error magnitude is 9.418
With point swing value 53, average error is 1.598, average error magnitude is 10.213
With point swing value 54, average error is 1.225, average error magnitude is 10.256
With point swing value 55, average error is 0.259, average error magnitude is 9.643
With point swing value 56, average error is 1.367, average error magnitude is 9.693
With point swing value 57, average error is 1.158, average error magnitude is 9.055
With point swing value 58, average error is 0.920, average error magnitude is 9.429
With point swing value 59, average error is 1.341, average error magnitude is 9.054
With point swing value 60, average error is 0.680, average error magnitude is 8.299
With point swing value 61, average error is 0.888, average error magnitude is 8.210
With point swing value 62, average error is 0.694, average error magnitude is 8.418
With point swing value 63, average error is 1.180, average error magnitude is 8.768
With point swing value 64, average error is 1.487, average error magnitude is 8.698
With point swing value 65, average error is 1.153, average error magnitude is 7.443
With point swing value 66, average error is 1.204, average error magnitude is 8.333
With point swing value 67, average error is 1.403, average error magnitude is 7.952
With point swing value 68, average error is 0.826, average error magnitude is 7.544
With point swing value 69, average error is 0.840, average error magnitude is 8.102
With point swing value 70, average error is 1.252, average error magnitude is 7.253
With point swing value 71, average error is 1.225, average error magnitude is 7.582
With point swing value 72, average error is 0.758, average error magnitude is 7.515
With point swing value 73, average error is 0.921, average error magnitude is 7.625
With point swing value 74, average error is 0.985, average error magnitude is 6.921
With point swing value 75, average error is 0.345, average error magnitude is 6.876
With point swing value 76, average error is 0.507, average error magnitude is 7.187
With point swing value 77, average error is 0.292, average error magnitude is 6.188
With point swing value 78, average error is 0.063, average error magnitude is 6.898
With point swing value 79, average error is 0.882, average error magnitude is 6.373
With point swing value 80, average error is 1.037, average error magnitude is 6.582
With point swing value 81, average error is 0.335, average error magnitude is 6.188
With point swing value 82, average error is 0.578, average error magnitude is 7.045
With point swing value 83, average error is 0.265, average error magnitude is 6.279
With point swing value 84, average error is 0.718, average error magnitude is 6.329
With point swing value 85, average error is 0.587, average error magnitude is 6.515
With point swing value 86, average error is 0.646, average error magnitude is 5.665
With point swing value 87, average error is 0.642, average error magnitude is 5.891
With point swing value 88, average error is 0.725, average error magnitude is 5.751
With point swing value 89, average error is 0.670, average error magnitude is 5.591
With point swing value 90, average error is 0.725, average error magnitude is 5.486
With point swing value 91, average error is 0.456, average error magnitude is 5.783
With point swing value 92, average error is 0.647, average error magnitude is 5.792
With point swing value 93, average error is 0.322, average error magnitude is 5.557
With point swing value 94, average error is 0.597, average error magnitude is 5.632
With point swing value 95, average error is 1.365, average error magnitude is 5.641
With point swing value 96, average error is 1.100, average error magnitude is 5.303
With point swing value 97, average error is 0.581, average error magnitude is 5.154
With point swing value 98, average error is 1.232, average error magnitude is 5.221
With point swing value 99, average error is -0.078, average error magnitude is 5.051
With point swing value 100, average error is 0.624, average error magnitude is 5.220
With point swing value 101, average error is 0.485, average error magnitude is 4.859
With point swing value 102, average error is 1.570, average error magnitude is 5.548
With point swing value 103, average error is 0.479, average error magnitude is 5.040
With point swing value 104, average error is 0.166, average error magnitude is 4.813
With point swing value 105, average error is 0.645, average error magnitude is 4.566
With point swing value 106, average error is 1.425, average error magnitude is 5.505
With point swing value 107, average error is 0.592, average error magnitude is 5.101
With point swing value 108, average error is 0.446, average error magnitude is 4.711
With point swing value 109, average error is 0.586, average error magnitude is 4.496
With point swing value 110, average error is 0.619, average error magnitude is 4.641
With point swing value 111, average error is 0.136, average error magnitude is 4.704
With point swing value 112, average error is 0.630, average error magnitude is 4.689
With point swing value 113, average error is 0.716, average error magnitude is 5.268
With point swing value 114, average error is 1.036, average error magnitude is 4.417
With point swing value 115, average error is 0.016, average error magnitude is 4.393
With point swing value 116, average error is 0.890, average error magnitude is 4.784
With point swing value 117, average error is 0.550, average error magnitude is 4.584
With point swing value 118, average error is 0.783, average error magnitude is 4.473
With point swing value 119, average error is 0.769, average error magnitude is 4.629
With point swing value 120, average error is 0.136, average error magnitude is 4.095
With point swing value 121, average error is 0.383, average error magnitude is 4.355
With point swing value 122, average error is 0.017, average error magnitude is 3.929
With point swing value 123, average error is 0.235, average error magnitude is 4.292
With point swing value 124, average error is 0.241, average error magnitude is 4.389
With point swing value 125, average error is 0.011, average error magnitude is 3.920
With point swing value 126, average error is 0.790, average error magnitude is 4.508
With point swing value 127, average error is 0.600, average error magnitude is 4.080
With point swing value 128, average error is 0.770, average error magnitude is 4.333
With point swing value 129, average error is 0.452, average error magnitude is 4.223
With point swing value 130, average error is 0.387, average error magnitude is 3.999
With point swing value 131, average error is 0.894, average error magnitude is 4.260
With point swing value 132, average error is 0.425, average error magnitude is 4.282
With point swing value 133, average error is -0.290, average error magnitude is 4.472
With point swing value 134, average error is -0.301, average error magnitude is 3.924
With point swing value 135, average error is 0.878, average error magnitude is 4.363
With point swing value 136, average error is -0.088, average error magnitude is 3.650
With point swing value 137, average error is 0.171, average error magnitude is 3.471
With point swing value 138, average error is 0.021, average error magnitude is 3.703
With point swing value 139, average error is 0.729, average error magnitude is 3.843
With point swing value 140, average error is 0.495, average error magnitude is 3.645
With point swing value 141, average error is 0.337, average error magnitude is 3.504
With point swing value 142, average error is 0.504, average error magnitude is 4.065
With point swing value 143, average error is 0.126, average error magnitude is 3.537
With point swing value 144, average error is 0.491, average error magnitude is 3.393
With point swing value 145, average error is 0.350, average error magnitude is 3.630
With point swing value 146, average error is 0.352, average error magnitude is 3.661
With point swing value 147, average error is 0.257, average error magnitude is 3.547
With point swing value 148, average error is 0.081, average error magnitude is 3.363
With point swing value 149, average error is 0.025, average error magnitude is 3.197
With point swing value 150, average error is 0.119, average error magnitude is 3.572
With point swing value 151, average error is 0.479, average error magnitude is 3.214
With point swing value 152, average error is -0.117, average error magnitude is 3.413
With point swing value 153, average error is 0.001, average error magnitude is 3.387
With point swing value 154, average error is 0.201, average error magnitude is 3.414
With point swing value 155, average error is 0.288, average error magnitude is 3.155
With point swing value 156, average error is 0.050, average error magnitude is 3.891
With point swing value 157, average error is 0.270, average error magnitude is 3.382
With point swing value 158, average error is 0.196, average error magnitude is 3.830
With point swing value 159, average error is 0.404, average error magnitude is 3.578
With point swing value 160, average error is 0.229, average error magnitude is 3.359
With point swing value 161, average error is 0.422, average error magnitude is 3.691
With point swing value 162, average error is 0.440, average error magnitude is 3.558
With point swing value 163, average error is 0.169, average error magnitude is 3.563
With point swing value 164, average error is 0.416, average error magnitude is 3.566
With point swing value 165, average error is -0.212, average error magnitude is 3.485
With point swing value 166, average error is 0.163, average error magnitude is 3.153
With point swing value 167, average error is -0.025, average error magnitude is 3.076
With point swing value 168, average error is 0.429, average error magnitude is 3.158
With point swing value 169, average error is 0.468, average error magnitude is 3.207
With point swing value 170, average error is 0.334, average error magnitude is 2.757
With point swing value 171, average error is 0.002, average error magnitude is 2.976
With point swing value 172, average error is 0.321, average error magnitude is 3.297
With point swing value 173, average error is 0.318, average error magnitude is 3.104
With point swing value 174, average error is 0.291, average error magnitude is 2.951
With point swing value 175, average error is 0.201, average error magnitude is 2.980
With point swing value 176, average error is -0.007, average error magnitude is 3.113
With point swing value 177, average error is -0.005, average error magnitude is 2.540
With point swing value 178, average error is 0.080, average error magnitude is 2.783
With point swing value 179, average error is -0.086, average error magnitude is 3.092
With point swing value 180, average error is 0.347, average error magnitude is 2.619
With point swing value 181, average error is 0.521, average error magnitude is 2.921
With point swing value 182, average error is 0.430, average error magnitude is 3.128
With point swing value 183, average error is 0.368, average error magnitude is 2.509
With point swing value 184, average error is 0.437, average error magnitude is 2.855
With point swing value 185, average error is 0.230, average error magnitude is 2.890
With point swing value 186, average error is 0.614, average error magnitude is 2.574
With point swing value 187, average error is 0.475, average error magnitude is 3.190
With point swing value 188, average error is 0.395, average error magnitude is 2.598
With point swing value 189, average error is -0.146, average error magnitude is 2.530
With point swing value 190, average error is 0.378, average error magnitude is 2.808
With point swing value 191, average error is 0.428, average error magnitude is 3.086
With point swing value 192, average error is 0.394, average error magnitude is 2.857
With point swing value 193, average error is 0.084, average error magnitude is 2.761
With point swing value 194, average error is 0.654, average error magnitude is 2.756
With point swing value 195, average error is 0.427, average error magnitude is 2.463
With point swing value 196, average error is 0.089, average error magnitude is 2.735
With point swing value 197, average error is 0.127, average error magnitude is 3.098
With point swing value 198, average error is 0.291, average error magnitude is 3.043
With point swing value 199, average error is 0.213, average error magnitude is 2.448

[pieter3d]

So no desire to address this?

[cbalint13]

@pieter3d ,

• Very interesting observation. I try verify it but my conclusion would be:

Just a minute:
a. https://github.com/Itseez/opencv_contrib/blob/master/modules/xfeatures2d/src/freak.cpp#L290
b. https://github.com/Itseez/opencv_contrib/blob/master/modules/xfeatures2d/src/freak.cpp#L536

Looking at {a}, then {b} div with 2048 makes much more sense to me:
at L279 there is a round-up with 0.5f also computation of delta is done by integers (as i can see)

• However i will try your idea on real scenario to see the impact.

[pieter3d]

Well, that 0.5 won't do anything interesting with the *4096. If the /2048 is left in, there should at least still be a round correction, so that there isn't a bias towards 0.

My point remains though that the division is pointless since they get cancelled out in the atan2. At the very least, it is wasted CPU.

[pieter3d]

Any plan to fix this?