Lineal Feature Extraction by Parallel Stick Growing

Third International Workshop on Parallel Algorithms for Irregularly Structured Problems (IRREGULAR '96) |

Published by Springer Verlag | Organized by European Association for Theoretical Computer Science and the International Federation of Information Processing (IFIP)

Editor(s): Afonso Ferreira, Jose Rolim, Yousef Saad, Tao Yang

Finding lineal features in an image is an important step in many object recognition and scene analysis procedures. Previous feature extraction algorithms exhibit poor parallel performance because features often extend across large areas of the data set. This paper describes a parallel method for extracting lineal features based on an earlier sequential algorithm, stick growing. The new method produces results qualitatively similar to the sequential method. Experimental results show a significant parallel processing speed-up attributable to three key features of the method: a large numbers of lock preemptible search jobs, a random priority assignment to source search regions, and an aggressive deadlock detection and resolution algorithm. This paper also describes a portable generalized thread model. The model supports a light-weight job abstraction that greatly simplifies parallel vision programming.