Negative sum values in Summed Area Table (Integral Images)

Question

I'm trying to implement the integral images concept in my project (based on this explanation https://computersciencesource.wordpress.com/2010/09/03/computer-vision-the-integral-image/), but I'm having some problems.

I have square (N * N) matrices with double values of which I calculate the corresponding SAT Table. On the next step, I want to know the sum of the values in square blocks (L * L) starting at the R index on the main diagonal. I don't know if I can explain it well enough for you to understand, but I hope my code can talk to you, better than I do ;)

public class Testing {

    public Testing() {
        double[][] values = {
                            {0.00,0.00,0.00,0.00,0.00,0.00,3.95,4.35,1.92,12.07,14.16,134.88},
                            {0.00,0.00,0.00,0.00,0.00,0.00,0.00,4.74,1.13,12.23,5.70,89.01},
                            {0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,2.10,13.72,1.49,71.94},
                            {0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.58,7.79,55.21},
                            {0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.79,33.01},
                            {0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,3.92},
                            {5.39,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,22.09},
                            {9.34,0.39,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,37.28},
                            {5.79,4.35,3.23,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,47.29},
                            {5.67,3.82,0.97,6.30,0.00,0.00,0.00,0.00,0.00,0.00,0.00,47.29},
                            {24.11,6.31,6.45,13.88,0.00,0.00,0.00,0.00,0.00,0.00,0.00,47.29},
                            {46.09,69.39,55.13,46.03,41.76,7.00,31.91,43.70,58.39,98.75,132.71,0.00}
                            };

        double[][] sat = calculateSAT(values);
        int size = sat.length;

        for (int r = 0; r < size; r++) {
            System.out.println("R: " + r);
            for (int l = 2; l <= size - r; l++) {
                int blockSize = l - 1;
                double s_A, s_B, s_C, s_D = sat[r + blockSize][r + blockSize];

                if (r == 0) {
                    s_A = 0;
                    s_B = 0;
                    s_C = 0;
                }
                else {
                    s_A = sat[r - 1][r - 1];
                    s_B = sat[r + blockSize][r - 1];
                    s_C = sat[r - 1][r + blockSize];
                }

                System.out.println("L: " + l);
                System.out.println("Sum: " + (s_A + s_D - s_B - s_C));
            }
            System.out.println("-------------");
        }
    }

    public double[][] calculateSAT(double[][] matrix) {
        int size = matrix.length;
        double[][] sat = new double[size][size];

        for (int x = 0; x < size; x++) {
            for (int y = 0; y < size; y++) {
                double ixy = matrix[x][y], sat_left = 0.0, sat_top = 0.0, sat_lefttop = 0.0;
                if (x == 0) {
                    sat_left = 0;
                    sat_lefttop = 0;
                }
                else {
                    sat_left = sat[x-1][y];
                }
                if (y == 0) {
                    sat_top = 0;
                    sat_lefttop = 0;
                }
                else {
                    sat_top = sat[x][y-1];
                }
                if (x != 0 && y != 0) {
                    sat_lefttop = sat[x-1][y-1];
                }

                sat[x][y] = ixy + sat_left + sat_top - sat_lefttop;
            }
        }
        printSAT(sat);
        return sat;
    }

    public void printSAT(double[][] sat) {
        for (int x = 0; x < sat.length; x++) {
            for (int y = 0; y < sat.length; y++) {
                System.out.print(sat[x][y] + "\t");
            }
            System.out.println();
        }
        System.out.println("-------------");
    }

    public static void main(String[] args) {
        new Testing();
        System.out.println("All done! :D");
    }
}

And the output is this:

0.0 0.0 0.0 0.0 0.0 0.0 3.95    8.3 10.22   22.29   36.45   171.32999999999998  
0.0 0.0 0.0 0.0 0.0 0.0 3.95    13.040000000000003  16.090000000000003  40.39   60.25000000000001   284.14  
0.0 0.0 0.0 0.0 0.0 0.0 3.95    13.040000000000003  18.190000000000005  56.21000000000001   77.56000000000002   373.39  
0.0 0.0 0.0 0.0 0.0 0.0 3.95    13.040000000000003  18.190000000000005  63.79000000000001   92.93000000000004   443.96999999999997  
0.0 0.0 0.0 0.0 0.0 0.0 3.95    13.040000000000003  18.190000000000005  63.79000000000001   100.72000000000003  484.77  
0.0 0.0 0.0 0.0 0.0 0.0 3.95    13.040000000000003  18.190000000000005  63.79000000000001   100.72000000000003  488.69000000000005  
5.39    5.39    5.39    5.39    5.39    5.39    9.34    18.430000000000003  23.580000000000002  69.18   106.11000000000001  516.1700000000001   
14.73   15.119999999999997  15.119999999999997  15.119999999999997  15.119999999999997  15.119999999999997  19.069999999999997  28.16   33.31   78.91000000000001   115.84000000000003  563.1800000000001   
20.52   25.259999999999994  28.489999999999995  28.489999999999995  28.489999999999995  28.489999999999995  32.43999999999999   41.53   46.68000000000001   92.28000000000002   129.21000000000004  623.84  
26.189999999999998  34.75   38.95   45.25   45.25   45.25   49.2    58.29000000000001   63.440000000000026  109.04000000000002  145.97000000000003  687.89  
50.3    65.17   75.82000000000001   96.00000000000001   96.0    96.0    99.94999999999999   109.04  114.19  159.79  196.71999999999997  785.9299999999998   
96.39   180.64999999999998  246.43  312.64000000000004  354.40000000000003  361.40000000000003  397.26  450.05  513.59  657.94  827.58  1416.7899999999997  
-------------
R: 0
L: 2
Sum: 0.0
L: 3
Sum: 0.0
L: 4
Sum: 0.0
L: 5
Sum: 0.0
L: 6
Sum: 0.0
L: 7
Sum: 9.34
L: 8
Sum: 28.16
L: 9
Sum: 46.68000000000001
L: 10
Sum: 109.04000000000002
L: 11
Sum: 196.71999999999997
L: 12
Sum: 1416.7899999999997
-------------
R: 1
L: 2
Sum: 0.0
L: 3
Sum: 0.0
L: 4
Sum: 0.0
L: 5
Sum: 0.0
L: 6
Sum: 0.0
L: 7
Sum: 5.129999999999999
L: 8
Sum: 15.940000000000007
L: 9
Sum: 60.560000000000024
L: 10
Sum: 109.96999999999996
L: 11
Sum: 1149.0699999999997
-------------
R: 2
L: 2
Sum: 0.0
L: 3
Sum: 0.0
L: 4
Sum: 0.0
L: 5
Sum: 0.0
L: 6
Sum: 0.0
L: 7
Sum: 5.330000000000009
L: 8
Sum: 33.90000000000002
L: 9
Sum: 71.29999999999995
L: 10
Sum: 951.9999999999999
-------------
R: 3
L: 2
Sum: 0.0
L: 3
Sum: 0.0
L: 4
Sum: 0.0
L: 5
Sum: 0.0
L: 6
Sum: 7.105427357601002E-15
L: 7
Sum: 13.88000000000001
L: 8
Sum: 43.33999999999995
L: 9
Sum: 796.9699999999997
-------------
R: 4
L: 2
Sum: 0.0
L: 3
Sum: 0.0
L: 4
Sum: 0.0
L: 5
Sum: 7.105427357601002E-15
L: 6
Sum: 7.105427357601002E-15
L: 7
Sum: 7.789999999999921
L: 8
Sum: 660.1799999999996
-------------
R: 5
L: 2
Sum: 0.0
L: 3
Sum: 0.0
L: 4
Sum: 7.105427357601002E-15
L: 5
Sum: 7.105427357601002E-15
L: 6
Sum: -5.6843418860808015E-14
L: 7
Sum: 577.6199999999997
-------------
R: 6
L: 2
Sum: 0.0
L: 3
Sum: 7.105427357601002E-15
L: 4
Sum: 7.105427357601002E-15
L: 5
Sum: -5.6843418860808015E-14
L: 6
Sum: 566.6999999999996
-------------
R: 7
L: 2
Sum: 1.7763568394002505E-14
L: 3
Sum: 1.4210854715202004E-14
L: 4
Sum: -2.8421709430404007E-14
L: 5
Sum: 512.6999999999996
-------------
R: 8
L: 2
Sum: -1.4210854715202004E-14
L: 3
Sum: -7.105427357601002E-14
L: 4
Sum: 431.7199999999998
-------------
R: 9
L: 2
Sum: -5.6843418860808015E-14
L: 3
Sum: 326.03999999999974
-------------
R: 10
L: 2
Sum: 179.99999999999966
-------------
R: 11
-------------
All done! :D

The issue I'm having with this code is that some of those sums are negative. Is that possible? If I understood SAT tables correctly, that shouldn't be possible.

As those values are really small, is this an issue of double precision?

Thank you so much for your help :)

PS: I'm sorry my english isn't any better than this.

Jared · Accepted Answer · 2015-01-21T17:31:17.663

1

Yes, the negative values are due to precision issues. If a number is small enough, treat it as zero.

edited Jan 21 '15 at 17:31

answered Jan 21 '15 at 17:22

Jared

46
2

So, is it safe to assume that the sum of the values in those intervals are zero? – jmvieira Jan 21 '15 at 17:28
Yes, that is a safe assumption. – Jared Jan 21 '15 at 17:31
Ok, thank you so much! Just another question, is there a safe threshold in which a double number is considered zero? Or is that a decision that the programmer makes? – jmvieira Jan 21 '15 at 17:51
1

Here's a related question: http://stackoverflow.com/questions/3728246/what-should-be-the-epsilon-value-when-performing-double-value-equal-comparison – Jared Jan 21 '15 at 17:55

Negative sum values in Summed Area Table (Integral Images)

1 Answers1