Recognition algorithms for the connection machine

This paper describes an object recognition algorithm both on a sequential machine and on a single instruction multiple data (SIMD) parallel processor such as the MIT connection machine. The problem, in the way it is presently formulated on a sequential machine, is essentially a propagation of constraints through a tree of possibilities in an attempt to prune the tree to a small number of leaves. The tree can become excessively large, however, and so implementations on massively parallel machines are sought in order to speed up the problem. Two fast parallel algorithms are described here, a static algorithm and a dynamic algorithm. The static algorithm reformulates the problem by assigning every leaf in the completely expanded unpruned tree to a separate processor in the connection machine. Then pruning is done in nearly constant time by broadcasting constraints to the entire SIMD array. This parallel version is shown to run three to four orders of magnitude faster than the sequential version. For large recognition problems which would exceed the capacity of the machine, a dynamic algorithm is described which performs a series of loading and pruning steps, dynamically allocating and deallocating processors through the use of the connection machine's global router communications mechanism. Ce rapport decrit un algorithme pour la reconnaissance ? objets qui s'adapte a la fois a un ordinateur sequentiel ou la connection machine du MIT, un multiprocesseur parallele du type SIMD. Sur un ordinateurconventionel, ľ algorithme propage des contraintes a travers un arbre de solutions probables de facon aeliminer le plus de branches que possible. Puisque ľ arbre a tendance a devenir enorme, nous avons considere le transfert de ľ algorithme sur un systeme a multiprocesseurs. Deux algorithmes paralleles sont proposes, un sous forme statique, ľ autre dynamique. Ľ algorithme statique assigne un processeur de la connection machine a chacune des options generees dans ľ arbre. Ľ analyze se fait done en un temps quasi constant en transmettant a chacun des processeurs les contraintes necessaires pour trouver la solution. Ceci accelere ľ algorithme par troi.s ou quatre ordres de grandeur par rapport a la version sequentielle. Pour des problemes plus.complexes qui excederaient la capacitye du multiprocesseur, une autre solution assigne de facon dynamique les differents processeurs lors du traitement en utilisant le systeme ? intercommunication global de la connection machine. Mots cles: traitement parallele, reconnaissance ? objets, connection machine, ordinateur adressable parcontenu, recherche dans des structures a base ? arbres. Summary A well-established algorithm for object recognition on a sequential machine was explained and fast connection machine algorithms were devised. First, a static parallel algorithm was discussed, in which the entire tree of possible interpretations is loaded into the connection machine before run time. The search is then done in one step and therefore in constant time. For problems that are too large to fit in the array, a dynamic algorithm was devised. In this algorithm, the connection machine is loaded with as many levels of the tree as can fit. Then a pruning is done in parallel as in the static algorithm. However, processors that survive the initial pruning step and still represent consistent pairings must find unused processors which can be assigned to the new branches of the tree. This is similar to the way the sequential algorithm first described prunes the search space. Processors that are pruned are deallocated and reused on the next iteration. The router mechanism of the connection machine which is not used in the static algorithm is necessary here to support dynamically allocating and deallocating processors.