Integral Images and Integral Volumes (Tutorial)

Integral Images / Summed Area Tables

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/table can be calculated in constant time once the Integral Table is constructed. The summed area table (Integral Image) 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+Ly, y+Ly) included. Then the sum is given by: 

sum = T(x+Lx, y+Ly) - T(x+Lx, y-1) - T(x-1,y+Ly) + 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 Integral Table (T) with coordinates (x,y).

Example: 

The following Figure shows an example of converting a table into into an Integral Table. 

Figure 3. This figure shows an example of converting a (a) Table  into an (b) Integral Table. The (c) shows the indexes used for guidance in the example later in the text for finding the sum of the shaded area. 

Let's assume we have constructed the Integral Table (T) of Figure 3 and we want to find the sum of the shaded area. Then (x,y)=(1,1), Lx=2 and Ly=1. Therefore S is calculated as follow: 

S = T(x+Lx, y+Ly) - T(x+Lx, y-1) - T(x-1,y+Ly) + T(x-1, y-1)

S = T(1+2,1+1)  – T(1+2,1-1) – T(1-1,1+1) + T(1-1,1-1)

S = T(3,2)– T(3,0)-T(0,2)+ T(0,0)

S = 78 – 10 – 15 + 1 = 54

and its correctness can be checked by summing the values of the shaded area in the non integral table in Figure 1a. As we can see below they are equal as the sum returned by the equation of the Integral table. 

                                                       S = 10 + 11 + 12 + 6 + 7 + 8 = 54               

Integral Volumes

Integral Volumes is the extension of Integral images in 3D. Instead of a 2D image, we have a 3D Volume divided into cubes, named voxels. Each voxel value is replaced by the sum of all the pixels that belong to the cuboid defined by the lower left lower corner of the volume and the voxel of our interest. Then, at constant time we can calculate the sum of any cuboid area at constant O(n) time [2]. 

So let s assume that the value of the voxel (x,y,z). The sum (S) of the cuboid defined by (x,y,z) and 

(x+lx,y+ly,z+lz) is given by:

S=T(x−lx,y+ly,z+lz)−T(x−1,y+ly,z+lz)−T(x+lx,y−1,z+lz)−T(x+lx,y+ly,z−1)+T(x−1,y−1,z+lz)+T(x−1,y+ly,z−1)+T(x+lx,y−1,z−1)−T(x−1,y−1,z−1)$$$$

where T(x,y,z) is the value of the voxel (x,y,z) inside the Integral Volume

           S is the sum of the voxels inside the cuboid

           define the length of the cuboid in the x, y z axes respectively. 

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/htm

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://www.mdpi.com/2072-4292/13/4/559/htm

Learning the basics of Command Prompt

This is a tutorial I found that I included in a lecture I did on the 8th of March, 2017 at the Department of Civil Engineering and Geomatics at Cyprus Unviersity of Technology. The idea was to introduce the students to the basics commands of Command Prompt before explaining to the how to use my open source software DASOS (http://miltomiltiadou.blogspot.com/2015/03/las13vis.html). By quickly reading thought it, I think it worth sharing on my blog. :) 

 

Introduction

This tutorial gives you an overview of the basic line commands that can be executed using the  Microsoft Windows Command Prompt. By following the procedures of this tutorial, you will learn how to:
1. Open Command Prompt on Windows
2. View the contents of a directory
3. Change directory
4. More useful commands
5. Executing multiple commands using .bat files

1.Opening the Command Prompt window

The Command Prompt is the command-line interpreter on Windows machines. For example, it allows you to execute line commands for opening or modifying files. For windows 7 and  lower, the Command Prompt is found by searching ”Command Prompt” on the Star Menu  Search bar (Figure 1a). For windows 10, you will find it by pressing right click on the start  icon (Figure 1b). Inside the black window that appears, we can write and execute commands. Figure 2 shows a Command Prompt window. The last line shows the path of the working  directory, which in this case is C:\Users\Milto. The follow sections give an overview of a few basic commands.

2. Viewing the contents of a directory - <dir>

In order to view the content of the working directory we use the command dir. The name of the command dir is derived from the word ”directory”. Type the following at the command prompt and press ”ENTER” from the keyboard (Please
note this in this tutorial the $: shows the start of a command and it should be ignored.):

$: dir

Once the ”ENTER” is pressed, a list similar to the following appears:

This is the list of all the files and subfiles of the working directory. The <DIR> label indicates that the listed item is a directory itself. If the working directory is not a drive (e.g. C:\), the first two directories ("." and "..") are always listed. The "." directory is the current working directory (C:\Users\Milto) and the ".." is the directory of the folder that contains the working directory (C:\Users). When a directory contains many items, the tag /p is very useful. For example, type the
following command: 

$: dir /p 

This will print a page of the directory list and the next page appears once ”ENTER” is pressed. 

3 Changing directory - <cd>

Moving from one directory to another is essential and the command cd (named after ”change directory”) is responsible for that. From the working directory (C:\Users\Milto), you can move to the subdirectory Documents by typing the following: 

$: cd Documents 

Or you may include the entire path of a directory. For example:  

$: cd C:\Users\Milto\Documents 

By the way, when typing in Command Prompt you may use the tab button to quickly fill the name’s of directories and files. Try typing: 

$: cd C:\Us 

and then press tab. It will automatically be filled to cd C:\Users. If more than one options apply, we can looping through them by pressing the button tab multiple times. Additionally, it is essential to be able to move from a working directory backwards; to the folder containing that working directory. This is done by the following command: 

$: cd .. 

As mentioned before, the directory ".." is the directory of the folder that contains the working directory. Therefore, by using the command cd following with ".." , we can move backwards one folder. Similarly, the following command does nothing because it brings you to the current directory, which is the "." : 

$: cd . 

The final command related to changing directory for this tutorial is the following:

$: cd \ 

Type the above command in Command Prompt. This command brings you to the root directory, which should by C:\. Therefore the Command Prompt should now show: 

C:\> 

Please note that for the final command a baskshlash (\) is used and not a forward slash (/); 

4.Quick Overview of some useful commands

There are numerous commands that can be executed from Command Prompt. Here a number of them are listed. 

To create a folder, use the command md (make directory) as follow. Please replace the <folderName> with the name of the new folder to be created. 

$: md <folderName> 

With the command rd (remove directory), an empty folder can be deleted: 

$: rd <folderName> 

For non-empty folders the tag \s should be added at the end as follow: 

$: rd <folderName> \s 

For renaming a file: 

$: ren <oldName> <newName> 

For deleting a file: 

$: del <filename> 

For copying a file: 

$: copy <file> <destination> 

An example of this command is the following which copies the file.txt from the directory C:Users into the C:\HelloWords: 

$: copy c:\Users\file.txt c:\HelloWorld 

Similarly the structure of the command that moves files is the following: 

$: move <file> <destination> 

The parameter NUL represents emptiness/null. Here, there is a hack for quickly generating an empty text file using the copy command and NUL: 

$: copy NUL emptyFile.txt 

5.Executing multiple commands using batch (.bat) files

A batch file is a script file in Microsoft Windows. It consists of a series of commands, which are stored in a plain text file (most commonly with extension .bat). These commands can be executed by the command-line interpreter (Command Prompt). Figure 3 shows an example of a batch file that uses commands explained in this tutorial. Each line that starts with :: is a comment and it is ignored at execution time. Comments also do not influence the interpretation

of the commands.

As mentioned before, batch files are plain text files and they can therefore been edited using a text editor. A good option for editing batch files is the gedit application, which colours the commands. If gedit is not available, then WordPad will also work fine, but preferably avoid using Notepad because usually it does not identify new lines and there is no indentation. To run a batch script file, just double click on the file and all the commands will be executed. Once the execution is done, the command prompt closes automatically. To avoid that you may include the pause command at the end of the file.

Co-registration of GeoTiff images with Full-waveform LiDAR data

In Remote Sensing, combining multiple sensors could be beneficial due to the increased information that could be used to train a classifier. Here, there is a tutorial with some scripts accosiated to help you co-register LiDAR metrics exported from the open source software DASOS [1] with GeoTIFF sattelitte imagery:

 

Link to script: https://github.com/Art-n-MathS/DASOSmetrics_alignmentWithGeoTIFF 

Link to open source software DASOS: https://github.com/Art-n-MathS/DASOS 

The “FOREST” project, with project protocol number “OPPORTUNITY/0916/MSCA/0005”, is co–financed by the European Regional Development Fund and the Republic of Cyprus through the Cyprus Research & Innovation Foundation.

Work Cited:

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.

DOI: 10.5194/isprsarchives-XL-7-W3-1257-2015

Python script that creates a copy of the same folders structure

Hello, it has been a while since I last posted something. Today, I wrote a very short script but something that could be useful so I thought it worth sharing and keeping into my blog. So have you ever wanted to copy and paste multiple folders without their content! This is what the following python function with automatically do for you:

import os

def creatFolders(i_inDir,i_outDir):
   cdir=os.getcwd()
   os.chdir(i_inDir)
   dirs=[d[0] for d in os.walk(".")]
   os.chdir(cdir+"/"+i_outDir)
   for d in dirs:
      if not os.path.exists(d):
         os.makedirs(d)
   os.chdir(cdir)

The following scripts returns all the files from a direction with a given extension:

import os

def getFiles(i_inDir,i_ext):
    cdir=os.getcwd()
    os.chdir(i_inDir)
    images=[f for f in os.listdir(".")if f.endswith(i_ext)] 
    print (images)
    print ("Images in Dir")
    print (i_inDir)
    os.chdir(cdir)
    return images

This script was developed as part of the "ASTARTE"(EXCELLENCE/0918/0341) project, which is co-financed by the European Regional Development Fund and the Republic of Cyprus through the Research Innovation Foundation. | Powered By Copywriter WordPress Theme.

Installation guide for Anaconda, Python, OpenCV and fmask for interpreting Sentinel Images

Download and Install Anaconda available at: https://www.continuum.io/downloads During installation, make sure you include Python in the path:
- Run Anaconda Prompt as an Administrator to be able to install new libraries and run the following commands:

:$ conda install -c conda-forge gdal

Install Jypiter Notebook:

:$ conda install -c conda-forge jupyterlab

Run JypiterLab:

:$ jupyter-lab

Install opencv:
:$ conda install -c menpo opencv
You may need to run the above command using an Administrator Command Prompt


For reading .nc images of Sentinel 3:
:$ conda install -c conda-forge netcdf4


Install fmask from Administrator Command Prompt as follow:
:$ conda config --add channels conda-forge
:$ conda install -c conda-forge python-fmask

or (to be tested)

:$ conda create -n myenv python-fmask
:$ activate myenv


Other dependencies:
:$ conda install -c anaconda scipy
:$ conda install -c anaconda numpy
:$ conda install -c conda-forge matplotlib
:$ conda install scikit-learn


For Doxygen Documentation please install it from here: http://www.stack.nl/~dimitri/doxygen/download.html


Every time you run your scripts, you need to run Anaconda Prompt as an Administrator and run "activate myenv".


Once you activate myenv, check they version of python that you are using. There is a bug in recent anaconda versions and when myenv is activated, your python is automatically updated to 3.6. You may use the following command to downgrade it:
:$ conda install python=2.7.8
Please note that this may be risky, since other applications may depend on Python 3.6.

Acknowledgement

This is part of the H2020 Research Innovation and Staff Exchange project SEO-DWARF with reg. no MSCA-RISE-691071. Website: seo-dwarf.eu