Fast component labelling and convex hull computation on reconfigurable meshes

摘要

Traditionally, buses have been used exclusively to support fast communication and data transfer needs within a parallel machine. We demonstrate novel uses for buses in a multiprocessor reconfigurable architecture. Specifically, we show that buses can be successfully used both as topological descriptors and as powerful computational devices. This new paradigm affords us fast algorithms to solve a number of fundamental image processing and computer vision tasks, including connected component labelling and computing the convex hull of every object in a given image. On a binary image of size √n × √n stored one pixel per processor, both our component labelling and convex hull algorithms run in O(log n) time and O(itlog su2 n)it time, respectively. In fact, our convex hull algorithm applies to ordered points in the plane as well: with an ordered set S of n such points stored one per processor in a reconfigurable mesh of size √ × √n, our algorithm computes the convex hull of S in O(log2 n).