Quadtree/src/sources/testQuadtrees.cpp

#include "../headers/testQuadtrees.h"

/*
        This file contains quick test and profiling
        code for the different quadtree implementations.
*/

#include <iostream>
using namespace std;

#include "../headers/Order2StatisticalConcept.h"
#include "../headers/NaiveQuadtree.h"
#include "../headers/AreaSumTableQuadtree.h"
#include "../headers/SimpleQuadtree.h"
#include "../headers/AugmentedAreaSumTableQuadtree.h"

#include "../headers/dmath.h"

using namespace za_co_codespot::datastructures;

DECLARE_CLOCK(clock1)

typedef int TestType;

// Test the archetypes
void testQuadtreeArchetypes()
{
        Order2StatisticalArchetype<TestType> ar[32*32];
        Order2StatisticalArchetype<TestType> threshold;

        NaiveQuadtree <Order2StatisticalArchetype<TestType>>(ar, 32, 32, threshold);
}

// Test a few invariances 
// See http://code-spot.co.za/2010/05/12/catching-common-image-processing-programming-errors-with-generic-unit-tests/
// for an explanation
void testReflectionInvariance()
{
        const unsigned int width(64);//this test wont always work if not powers of 2
        const unsigned int height(128);
        const TestType MAX_VAL(255);
        TestType threshold(20);

        TestType * ar1 = new TestType[width*height];
        TestType * ar2 = new TestType[width*height];
        TestType * ar3 = new TestType[width*height];
        TestType * ar4 = new TestType[width*height];

        for (unsigned int x = 0; x < width; x++)
        {
                for(unsigned int y = 0; y < height; y++)
                {
                        TestType val = (TestType)(MAX_VAL * ((TestType) rand()) / RAND_MAX);

                        ar1[y*width + x] = val;
                        ar2[x*height + y] = val;
                        ar3[y*width + (width - x - 1)] = val;
                        ar4[(height - y - 1) * width + x] = val;
                }
        }

        TestType sum1 = 0;
        TestType sum2 = 0;
        TestType sum3 = 0;

        NaiveQuadtree<TestType> quadtree1(ar1, width, height, threshold);
        NaiveQuadtree<TestType> quadtree2(ar2, height, width, threshold);
        NaiveQuadtree<TestType> quadtree3(ar3, width, height, threshold);
        NaiveQuadtree<TestType> quadtree4(ar4, width, height, threshold);


        for (unsigned int x = 0; x < width; x++)
        {
                for(unsigned int y = 0; y < height; y++)
                {
                        sum1 += abs(quadtree1(x, y) - quadtree2(y, x));
                        sum2 += abs(quadtree1(x, y) - quadtree3(width - x - 1, y));

                        if (sum2 > 0)
                        {
                                sum3 = 0;
                        }

                        sum3 += abs(quadtree1(x, y) - quadtree4(x, height - y - 1));
                }
        }

        double error1((double) sum1 / (width * height));
        double error2((double) sum2 / (width * height));
        double error3((double) sum3 / (width * height));

        cout << "Error per pixel: " << error1 << " [XY Reflection]" << endl;
        cout << "Error per pixel: " << error2 << " [X  Reflection]" << endl;
        cout << "Error per pixel: " << error3 << " [Y  Reflection]" << endl;

        cout << endl;
}

// Test whether the implementations give the same results
void testQuadtreeEquivalence()
{
        const unsigned int width(100);
        const unsigned int height(100);
        const TestType MAX_VAL(255);
        TestType threshold(0);

        TestType * ar = new TestType[width*height];

        for (unsigned int i = 0; i < width*height; i++)
        {
                ar[i] = (TestType)(MAX_VAL * ((TestType) rand()) / RAND_MAX);
        }
        
        NaiveQuadtree<TestType> quadtree1(ar, width, height, threshold);
        SimpleQuadtree<TestType> quadtree2(ar, width, height, threshold);       
        AreaSumTableQuadtree<TestType> quadtree3(ar, width, height, threshold);
        AugmentedAreaSumTableQuadtree<TestType> quadtree4(ar, width, height, threshold);

        cout << "Error per pixel: " << error(quadtree1, quadtree1) << " Naive - Naive" << endl; //sanity check for error function! This should be zero.
        cout << "Error per pixel: " << error(quadtree1, quadtree2) << " Naive - Simple" << endl;
        cout << "Error per pixel: " << error(quadtree1, quadtree3) << " Naive - Area Sum Table" << endl;
        cout << "Error per pixel: " << error(quadtree1, quadtree4) << " Naive - Augmented Area Sum Table" << endl;

        cout << endl;
}

//Test the performance of the differenct implementations
//Needs refactoring into functions!
void testQuadtreeSpeed()
{
        const unsigned int step(400);   
        const unsigned int start(32);
        const unsigned int stop((1 << 10) + 1);
        const TestType MAX_VAL((1 << 5) - 1);
        
        TestType threshold(0);

        cout << "Simple" << endl;
        srand(100);

        for (int k = start; k < stop; k*=2)
        {
                const unsigned int width(k);
                const unsigned int height(k);

                TestType * ar = new TestType[width*height];

                for (unsigned int i = 0; i < width*height; i++)
                        ar[i] = (TestType)(MAX_VAL * ((TestType) rand()) / RAND_MAX);
                
                START_CLOCK(clock1, 10)
                SimpleQuadtree<TestType> simpleQuadtree(ar, width, height, threshold);
                STOP_CLOCK(clock1)

                //cout << simpleQuadtree.getNodeCount() << endl;
                
                delete [] ar;
        }

        cout << endl;

        cout << "Naive" << endl;
        srand(100);
        
        for (int k = start; k < stop; k*=2)
        {
                const unsigned int width(k);
                const unsigned int height(k);

                //TestType * ar = new TestType[width*height];
                TestType * ar = new TestType[width*height];

                for (unsigned int i = 0; i < width*height; i++)
                        ar[i] = (TestType)(MAX_VAL * ((TestType) rand()) / RAND_MAX);

                
                START_CLOCK(clock1, 10)
                NaiveQuadtree<TestType> quadtree(ar, width, height, threshold);
                STOP_CLOCK(clock1)

                //cout << quadtree.getNodeCount() << endl;
                delete [] ar;
        }
        
        cout << endl;

        cout << "Area Sum Table" << endl;
        srand(100);
        
        for (int k = start; k < stop; k*=2)
        {
                const unsigned int width(k);
                const unsigned int height(k);

                TestType * ar = new TestType[width*height];

                for (unsigned int i = 0; i < width*height; i++)
                        ar[i] = (TestType)(MAX_VAL * ((TestType) rand()) / RAND_MAX);
                
                START_CLOCK(clock1, 10)
                        AreaSumTableQuadtree<TestType> fastQuadtree(ar, width, height, threshold);
                STOP_CLOCK(clock1)

                //cout << fastQuadtree.getNodeCount() << endl;
                delete [] ar;
        }
        
        cout << endl;

        cout << "Augmented Area Sum Table" << endl;
        srand(100);
        
        
        for (int k = start; k < stop; k*=2)
        {
                const unsigned int width(k);
                const unsigned int height(k);

                TestType * ar = new TestType[width*height];             
                
                for (unsigned int i = 0; i < width*height; i++)
                        ar[i] = (TestType)(MAX_VAL * ((TestType) rand()) / RAND_MAX);
                
                START_CLOCK(clock1, 10)
                        AugmentedAreaSumTableQuadtree<TestType> fastQuadtree2(ar, width, height, threshold);
                STOP_CLOCK(clock1)

                //cout << fastQuadtree.getNodeCount() << endl;
                delete [] ar;
        }
}

void testQuadtrees()
{
        testReflectionInvariance();
        testQuadtreeArchetypes(); 
        testQuadtreeEquivalence();
        testQuadtreeSpeed();    
}