| Image processing and image analysis involve intensive computations. Parallel computing has been perceived as the only economical way to achieve real-time or near real-time task performance. However, programming parallel computers for image processing applications is not an easy job due to the lack of high-level languages for parallel image processing on parallel computers. Image algebra is a unifying mathematical theory for image processing and analysis. It treats images as primary operands and addresses implicitly the parallelism in image processing, providing a highly parallel high-level language for image processing. This dissertation addresses issues of parallel image processing with image algebra on SIMD mesh-connected computers. It explores two aspects of the relationship between image algebra and parallel image processing: how well image algebra serves as a model for parallel image processing algorithms and how well SIMD mesh-connected computers are suited for image algebra implementation.;In the first part of this dissertation, I select a group of image algebra primitives useful for parallel image processing and develop efficient algorithms to implement these primitives on SIMD mesh-connected computers. In the second part, I demonstrate that image algebra can serve as an excellent model for parallel image processing. This is accomplished by using image algebra to describe several new highly parallel algorithms I have developed in order to solve various image processing problems. In particular, I describe a fast algorithm for the Abingdon Cross image processing benchmark and a new algorithm for binary image component shrinking. Additionally, I describe and analyze several local image component labeling algorithms, one of which positively answers an open question whether there exists a local labeling algorithm to label an n x n binary image in O(n) time on an n x n mesh-connected computer with O(log n) bits of local memory on each processing element. I also define a special class of image-template operations that prove useful for computing properties of image components and develop a general algorithm for them. Finally, I provide some suggestions for future research on parallel image processing with image algebra on parallel computers. |
