Parallel asynchronous computations for image analysis
Tóm tắt
Many works have been done for parallelizing low-level image analysis computations. However the task is harder for higher levels, as the data manipulations are complex, and there is a wide range of algorithms to encompass. To allow concurrently speed and programmability, a high-level programming model that can be efficiently implemented on parallel architectures is required. To achieve this goal, we propose the associative nets model, a parallel computing model for image analysis based on simple data-parallelism paradigms, providing special features, such as graph-based data structures to handle irregular data, virtual data-structures to ease hierarchical image descriptions, and specific primitives (dirassoc) to compute on the interpixels relation graph. For implementation purposes, the dirassoc computing primitive performs asynchronous local computations until it reaches stability. Asynchronism has many advantages for hardware (speed, power consumptions, and chip size) as well as in software (less synchronization barriers). However to insure completion of the asynchronous operation, the dirassoc must use a set of specific operators (r-operators) introduced by Ducourthial. In this paper we emphasize on the interest of the r-operators and of the asynchronous computations for image analysis algorithms. We give applications in distance transforms, contour closing, Voronoi segmentation, watershed segmentation, and mathematical morphology. Hence, we show that asynchronous computations are powerful tools for image analysis on interpixel graphs.
Từ khóa
#Concurrent computing #Image analysis #Image segmentation #Parallel programming #Parallel architectures #Parallel processing #Data structures #Stability #Hardware #Energy consumptionTài liệu tham khảo
robin, 1997, É tude d architectures VLSI numé riques parallè les asynchrones pour la mise en æ uvre de nouveaux algorithmes d analyze et rendu d images
10.1145/800123.803971
10.1109/40.526924
paris, 1993, HyperC Language Specification Document
nacken, 1994, Image analysis methods based on hierarchies of graphs and multi-scale mathematical morphology
miller, 1996, Parallel Algorithms for Regular Architectures Meshes and Pyramids
10.1109/ISCAS.1995.519945
potter, 1985, The Massively Parallel Processor, 10.7551/mitpress/4468.001.0001
pighizzini, 1990, About asynchronous cellular automata
perrin, 1996, The Data Parallel Programming Model, 10.1007/3-540-61736-1
10.1142/S0218001492000230
10.1016/S0146-664X(72)80013-3
10.1109/12.589222
10.1109/ICPR.1996.547639
ahuja, 1985, image representation using voronoï tesselation, CVGIP, 29, 286
1993, High Performance Fortran Language Specification Version 1 0
10.1007/978-3-7091-6487-7
10.1145/321941.321956
10.1016/S0167-8191(97)00073-2
kim, 95, mgap applications in computer visio, IEEE CAMP 95 Conf, 67
li, 1991, Reconfigurable Massively Parallel Computers
leighton, 1992, Introduction to Parallel Algorithms and Architectures Arrays Trees Hypercubes
10.1007/978-3-7091-6487-7_12
ducourthial, 1996, Graph Embedding in the Associative Mesh Model
10.1142/S0218001497000494
10.1109/CAMP.2000.875987
ducourthial, 2001, results on multi-threaded parallelizations for image analysis, Special Session on Parallel and Distributed Image and Video Processing (ParIm 01) in Conjunction with the 2001 Int Conf Parallel Computing (ParCo 2001)
dulac, 1996, Contribution au parallé lisme massif en analyze d images une architecture SIMD fondé e sur la reconfigurabilité et l asynchronisme
10.1109/CAMP.1995.521025
fountain, 1987, Processors Arrays Architecture and Applications
gautier, 1995, regular versus irregular problems and algorithms, Proc Irregular 95 vol 980 of Lecture Notes on Computer Science (LNCS), 980, 1, 10.1007/3-540-60321-2_1
guezguez, 1998, parallélization d'une segmentation par ligne de partage des eaux sur la maille associative d'orsay, Congré s de Reconnaissance de Formes et d Intelligence Artificielle 98 RFIA 98
hillis, 1985, The Connection Machine
10.1016/S0734-189X(86)80047-0
blelloch, 1990, Vector Models for Data-Parallel Computing
10.1007/978-1-4615-2413-7
braünl braunl, 1992, transparent massively parallel programming with parallaxi, Int J Mini Microcomput, 14, 82
ducourthial, 1998, new operators for computing with <emph>associative nets</emph>, Proc 5th Int Colloq Structural Information and Communication Complexity (SIROCCO 98), 55
charot, 1994, architectures paralleles specialises pour l'image, Tech Sci Inform, 13, 349
zielonka, 1987, notes on finite asynchronous automata, RAIRO Informatique Thé orique et Applications, 21, 99, 10.1051/ita/1987210200991
ducourthial, 1999, Les ré seaux associatifs un modè le de programmation à parallé lisme de donné es pour algorithmes et donné s irré guliers à primitives de calcul asynchrones
10.1016/0167-8191(89)90079-3
10.1109/34.44407
10.1109/34.87344
10.1006/jpdc.1996.0046
10.1109/83.403422
10.1109/83.334980
1990, C* Programming Guide Version 6 0
stanberry, 1993, dpce status repor, J C Language Transl, 5, 95