Project topics and materials
Get Complete Project Material File(s) Now! »
Lack of common parallelization strategy for topological operators
In 1996, Bertrand [20] introduced connectivity numbers for grayscale image. These numbers describe locally (in a neighborhood of 3*3) the topology of a point. According to this description any point can be characterized following its topological characteristics. He also introduced some elementary operations able to modify gray level of a point without modifying image topology. These elementary operations of point characterization present the fundamental link of large class of topological operators including, mainly, skeletonization and crest restoring algorithms [8]. This class can also be extended, under condition, to homotopic kernel and leveling kernel transformation [21], topological 2D and 3D object smoothing algorithm [22] and topological watershed algorithm [23]. All mentioned algorithms get also many algorithmic structure similarities. In fact associated characterizations procedures evolve until stability with induce common recursively between different algorithms. Also the grey level of any point can be lowered or enhanced more than once. Finally, all the mentioned algorithms get a pixel’s array as input and output data structure. Expect in special cases where graphs are used. It is important to mention that, to date, this class has not been efficiently parallelized like other classes as connected filter of morphological operator which recently has been parallelized in Wilkinson’s work [24]. Parallelization strategy proposed by Sienstra [25] for local operators and point to point operators can also be cited as example. For global operators, an adapted parallelization strategy is given in Meijster work [9]. Hence the need of a common parallelization strategy for topological operators that offers adapted algorithm structure design space. Chosen algorithm structure patterns to be used in the design must be suitable for SMP machines.
Fundamental basis for parallelization
Before defining parallelization’s stages of any sequential problem, it is essential to link the spectacular evolution of parallel architectures and the parallel processing. In reality, if the parallelization strategies are so valuable, it is thanks to substantial improvements in multiprocessing systems and the rise of multi-core processors. In terms of feasibility, it will be easier to design architecture with a single fast processor (clock speed over 3 GHz) than one with many slow processors (clock speed around 1.5 GHz) with the same throughput. But during last years the clock speed of processors in multi-core architectures has increased ,see (tab. 1), by almost two and associated cache size has increased tenfold with the addition of a third cache level L3 which ensures optimal L2 access speed while increasing the total cache. These twin barriers have flipped the equation, making multiprocessing very practical and advised even for small applications.
Watershed transformations
The watershed concept began with Maxwell [55] who introduces the theory behind representing physical characteristics of a land by means of lines drawn on a map. He highlights relationships between the numbers of hills, dales and passes which can co-exist on a surface. Subsequently, through the work of Beucher and al. [56], watershed transform was introduced to image segmentation and nowadays it represents one of the basic foundations of image processing [57]. In this framework, the most simplified description of the watershed approach is to consider a grayscale image as a topographic surface: the gray level of a pixel becomes the elevation of a point, the basins and valleys correspond to dark areas, whereas the mountains and crest lines correspond to the light areas. If topographic relief is flooded by water, watersheds will be the divide lines of the attraction’s domains of rain falling over the region [58] or sources of water springing from reliefs’ peaks. Another synopsis has shown consistency is that topographic surface is immersed in a lake with holes pierced in local minima. Catchment basins will fill up with water starting at these local minima, and, at points where water coming from differentbasins would meet, dams are built. As a result, the topographic surface is partitioned into different basins separated by dams, called watershed lines. Figure 8 gives a very symbolic description of the mentioned approach. In fact, it shows trends watershed transform use for image processing.
Table of contents :
ABSTRACT
RÉSUMÉ
ACKNOWLEDGEMENTS / REMERCIEMENTS
PUBLICATIONS
CONTENTS
LIST OF FIGURES
LIST OF TABLES
LIST OF DEFINITIONS
LIST OF ALGORITHMS
INTRODUCTION
1.1 Context and motivations
1.2 Contributions
1.3 Report organization
PARALLELIZATION STRATEGY
2.1 Lack of common parallelization strategy for topological operators
2.2 Fundamental basis for parallelization
2.3 Classification of SD&M strategy
2.4 SD&M strategy conception
2.4.1 The splitting phase
2.4.2 Distribution phase
2.4.3 The Merging phase
2.5 Conclusion
TOPOLOGICAL WATERSHED
3.1 Watershed transformations
3.1.1 Watershed based on flooding
3.1.2 Watershed based on path-cost minimization
3.1.3 Topological watershed
3.1.4 Watershed transform based on local condition
3.1.5 Watershed transform based on minimum spanning forest
3.2 Classification of watershed algorithms
3.3 Construction of parallel topological watershed
3.3.1 Basic notions and definitions
3.3.2 Parallel stream computing
3.4 Performance testing
3.5 Conclusion
TOPOLOGICAL THINNING
4.1 Classification of thinning algorithms
4.2 Parallel lambda-skeleton algorithms
4.2.1 Theorical background
4.2.2 Illustration of original algorithm
4.2.3 Parallel thinning algorithm
4.2.4 Experimental analysis
4.3 Conclusion
TOPOLOGICAL SMOOTHING
5.1 Theoretical background
5.2 Parallel smoothing filter
5.2.1 Study on Euclidean distance algorithms
5.2.2 Parallelization of Meijster algorithm
5.2.3 Thinning and thickening computation
5.3 Global analysis
5.3.1 Execution time
5.3.2 Cache memory evaluation
5.4 Conclusion
CONCLUSION
6.1 Contributions
6.2 Perspectives
BIBLIOGRAPHY
