A parallel algorithm for 3D reconstruction of angiographic images

Accurate diagnosis and therapeutic evaluation of coronary dysfunction is po ssible by tri-dimensional (3D) visualization of Coronary arteries. Reconstr uction based on bi-dimensional (2D) images can be presented as a discrete o ptimization problem. A blind search cannot be applied, instead a Branch-and -Bound algorithm is used to explore the state space and give an intermediat e result. The heuristic information used is based on 2D and 3D a priori kno wledge. A sequential algorithm using suitable filters leads to implementations wher e the execution time is measured in days. In order to minimize the executio n time we propose to apply parallel computing techniques. The critical issue in parallel search algorithms is the distribution of the search space among the processors. We propose a technique to compute the t otal amount of work units among the processors. The technique is based on t he enlargement of segments (unitary threads) representing pieces of arterie s. We achieve a good load balancing and the speedup obtained is nearly opti mum. (C)2000 Published by Elsevier Science B.V. All rights reserved.