Applying Parallel Computing To The Hough Transform

Most image processing tasks are very computationally intensive. The amount of data involved and computing power required are very large, which bring great difficulties in real-time applications, while image parallel processing technology is the most efficient technology to improve image processing speed.In the image processing technology, Hough transform is considered as a powerful tool in shape analysis which gives good results even in the presence of noise. But it has two major shortcomings. One is large computing power and long computing time, which can't satisfy some real-time requirements, the other is excessive storage requirement. Therefore, it needs parallel technology. In this paper we give a further consideration about its parallel execution, and the work of the paper is included as following.Many basic concepts in the image parallel processing are from computer parallel processing, so we first look back on the development of parallel computer and its architectures. Otherwise, in the parallel algorithm, we introduce its definition and classification. And on the base of this, the design method of parallel algorithm and its performance evaluation are described.After presenting the definition of the Hough transform, we apply three different architectures and methods to implement parallel execution of the Hough transform.First we implement Hough transform on the mesh-connected computer (MCC). Because of its simplicity and regularity, the 2-dimension MCC is a preferred parallel architecture for solving the computer image processing problem. The conventional Hough transform can only count the number of feature points which are collinear, and can't record the end points of a line segment and its length. Thereby, this paper present an improved Hough transform to overcome these two shortcomings. The algorithm is parallelized and implemented in MCC. What's more, we give a parallel algorithm to identify and eliminate overlapping line segments. These advantages are very useful in the real applications.Although mesh type architecture is very suitable for the image processing, its communication diameter is very large. It tends to be slow when it comes to handling data transfer operations over long distances. So pyramid architectures, consisting of a stack of successively smaller sizedmeshes, have been suggested. Pyramid architectures combine the features of mesh and tree type architectures. This paper presents an etTicient pipelined implementation of the Multiresolution Hough transform (MHT) on a pyramid machine. The MHT uses a set of multiresolution images and accumulator arrays at the different layers of the pyramid, which can be efficiently mapped into the variable sized processor arrays at the different layers of the pyramid. Due to this, the method results in a high utilization of the processors. Besides, the pipelined implementation fashion is suitable for real-time analysis of a continuous sequence of images.Parallel computer architecture consists of two classifications: simple instruction stream-multiple data stream (SIMD) and multiple instruction stream-multiple data stream (MIMD). The above two methods are both based on the SIMD structure. In this paper, we introduce an architecture, referred as Hybrid system, combines both SIMD and MIMD system. Furthermore, we present a new parallel-based Hough transform for implementation on the Hybrid system and give a better result.