Clarifying topic: Design and implementation of an "out of core" watershed algorithm, 2D and 3D

Profile

Specialized in the domain of image processing and mathematical morphology. Good knowledge in Python and/or C/C++.

Context

The project will take place within the division of Materials and Structural Analysis at Thermo Fisher Scientific. Thermo Fisher Scientific is a worldwide company with more than 60000 employees, the company is present in more than 50 countries and generates more than 20 billions of US dollars not only inteded to visualization but also (and mainly) to analysis and quantification for extracting revelant information; these operations are reached by using image processing techniques. However, most of the native algorithms of image processing haven’t been originally designed for large data management. Even if most of the algorithms are compatible with a pep-bloc approach, some of them need a complete algorithmic redesign. It is the case for the watershed algorithm as it is defined by Meyer. Watershed is a key algorithm in image quantification receipies and is identified as a blocking step for processing large volumes datasets.

Objective

The main goal of the internship is to provide to our software and toolkits (Amira, Avizo, OpenInventor) the capability to process watershew-based segmentation workflows on large datasets 2D and 3D, thereby being able to calculate the watershed algorithm on such dataset. A typical use case would be being able to process a dataset having a minimal volume of 32GB by using a computer with 32GB of RAM.

The inherent objectives are about to acquire a deep knowledge and understanding of the state of the art watershed techniques (O1).

As well as being able to propose an alternative algorithm able to process large data (O2) by using an out of core strategy.

Finally, the student will implement a functional prototype in C++ (O3) as a proof of concept by using our software technologies.

Reference papers.

1. Short-term materials:

   1. [A] Van Neerbos, J., Najman, L., & Wilkinson, M. (2011). Towards a parallel topological watershed: first results. Mathematical Morphology and Its Applications to Image and Signal Processing, 248-259. https://hal-upec-\upem.archivesouvertes.fr/hal00622506/file/partpwshedismm2011.pdf

   2. [B] Cousty, J., Bertrand, G., Najman, L., & Couprie, M. (2009). Watershed cuts: Minimum spanning forests and the drop of water principle. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(8), 1362-1374. https://halenpc.archivesouvertes.fr/file/index/docid/622410/filename/flow_watershedPAMI.pdf

      
      

2. Medium-term materials:

   1. [A*] Bertrand, G. (2005). On topological watersheds. Journal of Mathematical Imaging and Vision, 22(2-3), 217-230. https://hal-enpc.archives-ouvertes.fr/file/index/docid/622398/filename/hal.pdf

   2. [B*] Cousty, J., Bertrand, G., Couprie, M., & Najman, L. (2008). Fusion graphs: merging properties and watersheds. Journal of Mathematical Imaging and Vision, 30(1), 87-104. https://perso.esiee.fr/~coustyj/CBCN-fusionJMIV08.pdf

   3. [C*] Cousty, J., Couprie, M., Najman, L., & Bertrand, G. (2008). Weighted fusion graphs: merging properties and watersheds. Discrete Applied Mathematics, 156(15), 3011-3027. https://hal-enpc.archives-ouvertes.fr/file/index/docid/622473/filename/hal.pdf

   4. [D*] Cousty, J., & Najman, L. (2011, July). Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. In International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing (pp. 272-283). Springer, Berlin, Heidelberg. https://hal-upec-upem.archives-ouvertes.fr/hal-00622505/document

   5. [E*] Cousty, J., Najman, L., & Perret, B. (2013, May). Constructive links between some morphological hierarchies on edge-weighted graphs. In International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing (pp. 86-97). Springer, Berlin, Heidelberg. https://hal-upec-upem.archives ouvertes.fr/file/index/docid/806851/filename/ismm2013.pdf

   6. [F*] Najman, L., Cousty, J., & Perret, B. (2013, May). Playing with Kruskal: algorithms for morphological trees in edge-weighted graphs. In International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing (pp. 135-146). Springer, Berlin, Heidelberg. https://hal.archives-ouvertes.fr/file/index/docid/798621/filename/ismm2013-algo.pdf

   7. [G*] Havel, J., Merciol, F., & Lefèvre, S. (2016). Efficient tree construction for multiscale image representation and processing. Journal of Real-Time Image Processing, 1-18. (comme l'article n'est pas disponible en ligne, je te le transmets en pièce jointe).

Laurent Najman, Michel Couprie, Gilles Bertrand. Watersheds, mosaics and the emergence paradigm. Discrete Applied Mathematics, Elsevier, 2005, 147 (2-3), pp.301-324 https://hal-upec-upem.archives-ouvertes.fr/hal-00622113

Laurent Najman, Jean Cousty. A graph-based mathematical morphology reader. Pattern Recognition Letters, Elsevier, 2014, 47, pp.3-17.〈10.1016/j.patrec.2014.05.007.〈hal-00986191〉

Planning for 1st month

If a paper is shorter than 20 pages, read 1 paper per day. If the paper is longer than 20 pages, allocate 2 days per paper.

On the other hand, study more the raw pointers for C++.

Finished the same way as you never ever started!