Parallel Optimization of a Pyramidal Computer Vision Algorithm
During my last year of Bachelor's degree, I worked as a research intern for 6 weeks at LIP6 (Paris). I worked with members of the ALSOC team which members are experts in embedded systems and designing efficient applications with good architecture-algorithm adequation.
The purpose of my work was to study parallelism strategies for a pyramidal computer vision algorithm. The algorithm I worked on is inspired from Horn-Schunck algorithm, used by Maxime Millet for detecting meteors from a small satellite in his PHD.
The Pyramidal Computer Vision Algorithm
The computer vision algorithm I studied can be described in the following picture.
The algorithm can be decomposed in 2 phases:
- Down-sampling: Image resolution is decreased by applying filters
- Up-sampling: Image is re-created by using stencils (convolution filters) and upscaling filters
However, measures on the real algorithm showed that the stencil operator is responsible for almost 80% of the whole execution time.
Parallel Execution of the Stencil
In my internship report, I compare several strategies for executing the stencil in parallel. The first one is pretty straight-forward and consists in naive parallelism of the for loops involved in stencil computation. The most interesting one changes the order of the loops in order to improve data locality but at the cost of doing redundant computations referred to as "shadow-zones" shown in below picture.
A detailed explanation of my implementations as well as their evaluation is available in my internship report.
Additionnal resources
If you want to learn more about my work, here are some useful resources:
Special thanks
I want to thank Adrien Cassagne, Alix Munier, Maxime Millet and Lionel Lacassagne for their time and dedication to the follow-up of my internship !