This paper presents algorithms for implementing an important image processing operation, the Hough transform, on a mesh connected computer (MCC). The MCC consists of an $N \times N$ array of processors, each of which holds a single pixel of the image. The MCC operates in a Single Instruction Stream, Multiple Data Stream (SIMD) mode, which is in agreement with the hardware constraints found in existing meshes. Five algorithms for computing the Hough transform are presented. These algorithms use a number of different techniques, and they have varying time complexities and architectural requirements. The most notable algorithm presented computes any P angles of the Hough transform in $O(N + P)$ time and uses only a constant amount of memory per processor. Because the Hough transform is a particular case of the discrete Radon transform, all of the algorithms will be presented for computing the Radon transform of gray-level images.

Two parallel algorithms are presented for the problem of labeling the connected components of a binary image. The machine model is an SIMD two-dimensional mesh-connected computer consisting of an N*N array of processing elements, each containing a single pixel of an N*N image. Both new algorithms use a local shrinking operation defined by S. Levialdi (1972) and have time complexities of O(N log N) bit operations, making them the fastest local algorithms for the problem. Compared to other approaches with similar or better asymptotic time complexities, this local approach greatly simplifies the algorithms and reduces the constants of proportionality by nearly two orders of magnitude, making them the first practical algorithms for the problem. The two algorithms differ in the amount of memory required per processing element; the first uses O(N) bits, while the second uses a novel compression scheme to reduce the requirement to O(log N) bits.>

An important midlevel task for computer vision is addressed. The problem consists of labeling connected components in N/sup 1/2/*N/sup 2/2/ binary images. This task can be solved with parallel computers by using a simple and novel algorithm. The parallel computing model used is a synchronous fine-grained shared-memory model where only one processor can read from or write to the same memory location at a given time. This model is known as the exclusive-read exclusive-write parallel RAM (EREW PRAM). Using this model, the algorithm presented has O(log N) complexity. The algorithm can run on parallel machines other than the EREW PRAM. In particular, it offers an optimal image component labeling algorithm for mesh-connected computers.>