Internship in algorithm development (C++)

Internship in algorithm development (C++)

Internship in algorithm development (C++)

For MSc students

Context

LiDAR (Light Detection and Ranging) technology is currently revolutionizing data acquisition in the natural sciences. In the forestry and ecology sectors, airborne laser scanning (ALS), using an aircraft-mounted sensor is an increasingly common remote sensing application for characterizing the topography of large areas of the Earth’s surface using a cloud of georeferenced points.

Manipulating ALS data requires processes point clouds with computing algorithms. In the fields of forestry and ecology, bespoke scripts are typically developed outside dedicated software by different research teams to meet specific data processing such as tree segmentation, tree species recognition, ground segmentation or to explore and develop new tools and methodologies to evaluate quantities of interest such as the biomass of the forests. These scripts are often written within programming environments such as the R language, which is extensively used in forestry and ecology research.

However, until recently there were no purpose-built packages in R to manipulate ALS data in a convenient and efficient way. In this context we developed an open-source R framework called lidR to perform such tasks.

Projects

We would like to hire an IT intern for four to six months to help us developing this R package by implementing new algorithms in C++ within R. The scientific literature decribes many algorithms to achieve various tasks as accurately as possible, including individual tree segmentation, ground segmentation or species recognition from the point clouds. These algorithms are usually presented as text-only in scientific papers with no implementation, no shared source code or not even a pseudo-code to help users to implement their own version of the algorithms.

The plan is to implement several algorithms from a list we set-up from our litterature review. We don’t have specific requierements. The student will be free to chose the algorithms he or she feels confortable with, or more technically interesting. A short (non-exhaustive) list is provided here as a general indication of the expectations:

     Li et al. (2012) is an algorithm for tree segmentation from a point cloud. We already implemented this algorithm, but believe it could be made a lot faster

     Axelsson (1999) is an algorithm for ground segmentation. There are several closed-source implementations. We would like to make an open-source one.

     Hamraz, Contreras, and Zhang (2016) is an algorithm for tree segmentation from a point cloud. We would like to implement it.

     Yao, Krzystek, and Heurich (2012) is an algorithm for tree segmentation from a point cloud. We would like to implement it.

     Anahita Khosravipour et al. (2014) is an algorithm to build a canopy height model. We already implemented it and so far it should be the only open-source implementation. We believe it can be optimized to be made faster and to use less memory.

     A Khosravipour, Skidmore, and Isenburg (2016) is an algorithm to build a canopy height model. There is one closed-source implementation. We would like to make an open-source one.

Considering the huge amount of points sampled with lidar
data, the student will have to focus about memory usage and computation speed.
The intern will have to manipulate efficient lookup structures such as
QuadTrees, OctTree, common algorithms such as Delaunay triangulation,
parallelized processes to improve computation, and will have to carefully
choose the most appropriate structure from the C++ standard library.

The intern will also use code profiling tools to identify
performance problems. In addition, the intern will have to deal with some
technical contraints due to the R language itself, which can sometimes make the
tasks tricky.

Skill requierements

Requiered skills

     C++ standard library knowledge is absolutely required, as well as the common features of a low-level language such as pointers, reference, dynamic memory allocation an so on.

     The intern must be conformatble with git, GNU/Linux, a terminal, a makefile, a bash script and other common developper tools.

Non requiered skills

Although the work will take place inside the R language, no knowlege is required of this language. A day of training will be dedicated to the R language and another day will be dedicated to in-depth knowledge of the internal behavior of R in terms of memory. We will also see how to mix C++ within R and how to make code profiling. We strongly believe that a student with C++ skills should be able to learn these points within a couple of days.

Can be an advantage

These skills are not required but can be useful and valuable:

     Being confortable with LATEX to write documents.

     Already have some knowlege of the R language.

     Skills in OpenGL would be appreciated (we have other work for you!)

     Skills in drawing with Inskape to illustrate algorithms

Location and scholarship

The internship will last between 4 and 6 months. The date and the duration is flexible but we would like to start in the early spring of 2018, if possible. The intership will take place in Québec City, Quebec, Canada at Laval University (we speak French). The intern will receive a 1200 CAD scholarship per month, which should be enough to travel to and live in Quebec City for the training period.

How to apply

Send an email to Jean-Romain Roussel (jean-romain.roussel.1 [at] ulaval [dot] ca). The core of your email should contain a motivation letter and a CV in attachment in an open format (write in French if it is your mother tongue). Please do not send any boring or ugly-looking CVs. Be quirky, this job is fun!

References

Axelsson, Peter. 1999. “Processing of laser scanner data—algorithms and applications.” ISPRS Journal of Photogrammetry and Remote Sensing 54: 138–47. doi:10.1016/S0924-2716(99)00008-8.

Hamraz, Hamid, Marco A. Contreras, and Jun Zhang. 2016. “A
robust approach for tree segmentation in deciduous forests using
small-footprint airborne LiDAR data.” International
Journal of Applied Earth Observation and Geoinformation
52. Elsevier B.V.:
532–41. doi:10.1016/j.jag.2016.07.006.

Khosravipour, A, A K Skidmore, and M Isenburg. 2016.
“Generating spike-free Digital Surface Models using raw LiDAR point clouds: a
new approach for forestry applications.” International
Journal of Applied Earth Observation and Geoinformation
52: 104–14.

Khosravipour, Anahita, Andrew K. Skidmore, Martin Isenburg,
Tiejun Wang, and Yousif A. Hussin. 2014.

“Generating Pit-free Canopy Height Models from Airborne
Lidar.” Photogrammetric Engineering &
Remote Sensing
80 (9): 863–72. doi:10.14358/PERS.80.9.863.

Li, Wenkai, Qinghua Guo, Marek K Jakubowski, and Maggi Kelly.
2012. “Photogrammetric Engineering & Remote Sensing.” Photogrammetric Engineering & Remote Sensing 78 (1): 75–84. doi:10.14358/PERS.78.1.75.

Yao, W., P. Krzystek, and M. Heurich. 2012. “Identifying
Standing Dead Trees in Forest Areas Based on

3D Single Tree Detection from Full Waveform LIDAR Data.” ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences I-7 (September): 359–64. doi:10.5194/isprsannals-I-7-359-2012.

This topic was automatically closed 365 days after the last reply. New replies are no longer allowed.