FAST HOUGH TRANSFORM ON MULTIPROCESSORS - A BRANCH-AND-BOUND APPROACH

The algorithm of the Fast Hough Transform presents a strong irregulari ty which makes its parallelization difficult, especially; if we introd uce certain improvements into the sequential algorithm, such as the el imination of straight lines, In this work we approach this algorithm a s a branch and bound problem, developing three different parallel algo rithms, The first of these algorithms is based on an initial distribut ion of the problem that guarantees a good balance of computations, The other two algorithms perform a dynamic distribution of the load using different policies, In one of them, the mechanism is distributed and rebalancing is carried out at the demand of the processors left withou t load, In the other, one processor acts as a central processor and de cides when to carry out the rebalance and what the correspondence betw een overloaded and underloaded processors will be. (C) 1997 Academic P ress.