Wednesday 6 November 2013

Summed Area Tables (Integral Images), Explanation and Implementation in C++

In 1984, Crow proposed an image representation where each pixel value is replaced by the sum of all the pixels that belong to the rectangle defined by the lower left corner of the image and the pixel of our interest [1].
Even though more storage space may be required to save the image, the sum of every rectangle in the image can be calculated in constant time once the table is constructed. The summed area table can be constructed in linear time O(n), where n is the number of pixels in the image, since one iteration through the entire image is enough to replace the pixel values inside the area table.

Figure 1. This figure depicts the parameters of the following equation [2].

 
So, let’s assume the we have the above image and we would like to find the sum of the blue area defined by the pixels (x,y) and (x+lenX, y+lenY) included. Then the sum is given by: 
sum =  T(x+lenX, y+lenY) - T(x+lenX, y-1) - T(x-1,y+lenY) +  T(x-1, y-1)
      
Figure 2. Once the Integral Image is constructed, the sum of any rectangular area is calculated in constant time [2].


Where T(x,y) is the value in the table with coordinates (x,y).

Code Available here:
https://www.dropbox.com/s/83oynkf11rrjd21/SumTables.zip

The images are taken from the following article, which explains how Sum Area Tables, in other words Integral Images, are used in 3D (named Integral Volumes) to optimise reconstruction of polygon representations from voxelised data[2]: https://www.mdpi.com/2072-4292/13/4/559



Work Cited

[1] Crow, F.C. (1984, July). Summed-Area Tables for Texture Mapping. ACM, Computer Graphics, Volume 18, Number 3

[2] Miltiadou M, Campbell NDF, Cosker D, Grant MG. A Comparative Study about Data Structures Used for Efficient Management of Voxelised Full-Waveform Airborne LiDAR Data during 3D Polygonal Model Creation. Remote Sensing. 2021; 13(4):559. https://doi.org/10.3390/rs13040559

Friday 18 October 2013

std::unordered_map example

Unordered map is a structure that allows you to save data in an easy to access format.

For example, let assume that we would like to create a telephone catalogue. If we use an std::vector then looping though all the contact to find a number is time expensive. Instead we can use an std::unordered_map and have a much quicker search of data.

So this is an example code using the unordered_map:

#include 
#include 


int main(void)
{
   // initialise the map which takes as input a string and an integer
   std::unordered_map < std::string,unsigned int > mymap;

   // create and insert a new contact
   std::pair < std::string, unsigned int > pair("Maria",300);
   mymap.insert(pair);

   // search for a contract
   std::string input = "Maria";

   std::unordered_map < std::string,unsigned int > ::const_iterator got = mymap.find(input);
   if(got == mymap.end())
   {
       std::cout << "Contact does not exist\n";
   }
   else
   {
       std::cout << got -> first << "'s number is " << got->second <<"\n";
   }

  return 0;
}


So if you run the above example, this is what you get:

Maria's number is 300


Please note that unsigned int is not a prober type to save telephone numbers, because telephone numbers if are treated as numbers then you can easily end up with an overflow.
In this example I just wanted to show that unordered map allows you to save two different types of variables. A better approach will have been to have two string instead of string and an unsigned int.

Wednesday 9 October 2013

Merge Sort without Recursion.

MathJax TeX Test Page
Well, I needed a sorting algorithm in C++, so I decided to write my own. Merge sort is quick, O(nlogn), and stable. Recursion is also slow so I decided to write it without recursion:


  // array to be sorted
  int array[] = {12,4,10,2,3,2,8,7,-1,-4,14,8,9,2,11};
  unsigned int len = 15;
  // allocate memory for temporarly saved values
  std::vector tempValues;
  tempValues.resize(len);
  // start sorting 2 elements each time, then merge them with the two next to them etc
  for(int step=2; step/2 < len; step*=2)
  {
     for(unsigned int i=0; i < len; i+=step)
     {
        int endOfT2 = i+step;
        if(i+ step/2 >= len)
        {
           continue;
        }
        else if (i+step >= len)
        {
           endOfT2 = len;
        }
        // both sets have step/2 items.
        // t1 points to the first set of values
        int t1 = i;
        // t2 points to the second set of values
        int t2 = i+step/2;
        // here we save all the values that have been overridden from the first set
        unsigned int tempIndex=0;
        while(t1 < i+step/2 && t2 < endOfT2)
        {
           if(array[t1]>array[t2])
           {
              tempValues[tempIndex]=array[t1];
              t1++;
           }
           else
           {
              tempValues[tempIndex]=array[t2];
              t2++;
           }
           tempIndex++;
        }
        while(t1 < i+step/2)
        {
           tempValues[tempIndex]=array[t1];
           t1++;
           tempIndex++;
        }
        // write values back to the array
        for(unsigned int t=0; t < tempIndex; ++t)
        {
            array[i+t]=tempValues[t];
        }
     }
  }

  // print the sorted array
  for(unsigned int i=0; i < len; ++i)
  {
      std::cout << " " << array[i];
  }
  std::cout << "\n";

Thursday 26 September 2013

Reading Binary Files into Structures - C++

Hello,

this tutorial aims to give an overview on how to read binary files into structures in C++. These are the methods used for reading the LAS files in DASOS [1], an open source softwaring for managing full-waveform LiDAR data. I found reading binary files pretty interesting and challenging at the same time, so I decided to write a short tutorial about it.

If you want to read a binary file, you should first know how the bytes are structured inside the file. For example the first 10bytes may represents a word, the next 4 bytes may be a float number, the next 6 bytes may be 3 short int numbers, etc. For that reason you should also know how many bytes each type is. If not then, you can use the sizeof(<type>) command and find out. 

Let's assume that we have a file with a word, a float number and 3 short ints as the above example, then a struct with these information should be defined.

typedef struct myStructure
{
   char word[10];           // 10 bytes                    
   float number;            //  4 bytes
   short int A;             //  2 bytes
   short int B;             //  2 bytes
   short int C;             //  2 bytes
}myStructure;

The above should be 20 bytes, but that is not guarantee. While I was writing my code I came across a case where my struct should have been 235 bytes, but sizeof(myStructure) returned 243. This occured because of the way C++ allocates memory for structures. In order to avoid it, you have to use #pragma and specify how your data should be packed. If not then your binary data will not match with the structure since you will try to match 235 bytes into a structure which is 243 and the results will be wrong. 

#pragma pack(push)
#pragma pack(1)
typedef struct myStructure
{
   char word[10];           // 10 bytes                    
   float number;            //  4 bytes
   short int A;             //  2 bytes
   short int B;             //  2 bytes
   short int C;             //  2 bytes
}myStructure;
#pragma pack(pop)

Once the structure is defined the next step is to open the file as follow:
file.open(filename.c_str(),std::ios::binary);
if(!file.is_open())
{
   std::cerr << "File noT found \n"
   exit(EXIT_FAILURE);
}

Then define a variable of type myStructure and read the data into the structure:

myStructure data;
file.read((char *) &data,sizeof(data));

and you are done! The data is now into the structure.

There were occasions where I couldn't read the data straight into the structure, because I didn't know the length of a few variable from the beginning. This problem was solved by first reading all the data into an array of char (each char is a byte) and then use memcpy to copy the data into structures or arrays.

 char allData [sizeOfAllData];
// read all the data from the binary file
file.read((char *) allData,sizeOfAllData);
// in this example we want to read ints
int partOfData = new (std::nothrow) int[numOfInts];
// testing if memory has been allocated for that data
if(partOfData==0) // memory  couldn't not been allocated
{
   std::cout << "Allocation of memory failed\n"
   exit(EXIT_FAILURE);
}
memcpy((void *)partOfData,(void *)allData,numOfInts*sizeof(int));

By the end once we get the information we need, we should close the file:

   file.close();

Please note that most of the code is written by heart, so there may be a few spelling mistakes.

I hope you find this tutorial useful. If you have any comments, corrections or questions please don't hesitate to contact me. =)


More information about the software here:
Miltiadou, M., Grant, M. G., Campbell, N. D., Warren, M., Clewley, D., & Hadjimitsis, D. G. (2019, June). Open source software DASOS: Efficient accumulation, analysis, and visualisation of full-waveform lidar. In Seventh International Conference on Remote Sensing and Geoinformation of the Environment (RSCy2019) (Vol. 11174, p. 111741M). International Society for Optics and Photonics.