Design and Implementation of Morphological and Order Statistic Filters

Chair: Jisang Yoo, Kwangwoon University, Korea

Home


A Fast Algorithm for Computing Morphological Image Processing Primitives

Authors:

D.M.P. Hagyard, University of East Anglia (U.K.)
M. Razaz, University of East Anglia (U.K.)
P. Atkin, Synoptics Imaging Systems Ltd (U.K.)

Volume 1, Page (NA), Paper number 221

Abstract:

Morphological image processing is performed by successive application of Minkowski or Flit or Miss primitive operations. A 2D structuring element is used to specify the directions in which the primitives operate. The success or failure of this type of image processing, for many real world imaging applications, is critically dependent on the efficiency with which these primitives are computed. If the direct definition of the primitives is used for their implementation, a brute force algorithm, then the time taken to complete the operation of a primitive is proportional to the number of pixels in the structuring element. This paper presents a new fast morphological transform (FMT) algorithm for computing binary morphological primitives The computation time of the FMT is shown to be independent of the size of the structuring element used. The algorithm is compared against four other algorithms that we have implemented, namely, the brute force method and three fast frequency-domain convolution based algorithms for calculating morphological primitives. Many different comparative tests were performed, here we present some typical experimental results. In practically all the experiments, the FMT algorithm proved to be the fastest.

ns970221.pdf (Scanned)

ns970221.pdf (From Postscript)

TOP



Implementation of Parallel Adaptive Stack Filter Using PVM

Authors:

Youngrock Yoon, Yonsei University (Korea)
Hyeran Byun, Yonsei University (Korea)
Yillbyung Lee, Yonsei University (Korea)
Jisang Yoo, Hallym University (Korea)

Volume 1, Page (NA), Paper number 222

Abstract:

Stack filter showed good performance for signal restoration and noise reduction especially for impulsive noises, but required too much resource. Parallel adaptive stack filtering algorithm was developed to overcome this problem and implemented on parallel architecture. We implemented this algorithm using new heterogeneous parallel computing environment known as parallel virtual machine (PVM), using a well-known master-slave scheme. Load balancing, which is another important factor of heterogeneous computing, was used to balancing workloads of each host which is used as a separated parallel processor. It showed a better performance than previous implementation, when it was applied to a big image with large window size using reasonable number of hosts as the parallel processor.

ns970222.pdf (Scanned)

ns970222.pdf (From Postscript)

TOP



A Histogram Method for Fast Greyscale Morphology Operations

Authors:

D.M.P. Hagyard, University of East Anglia (U.K.)
M. Razaz, University of East Anglia (U.K.)
P. Atkin, Synoptics Imaging Systems Ltd (U.K.)

Volume 1, Page (NA), Paper number 223

Abstract:

A novel histogram method is presented for fast computation of greyscale morphology operations. This method is compared against the list method, a brute force approach. The histogram method is shown to be considerably faster than the brute force method, and that its computation time is independent of the size of the structuring element. For comparison purposes we have also implemented an alternative fast algorithm based on the van Herk approach for performing maximum and minimum filters on a 1D array of data. The histogram and van Herk methods are compared and contrasted. Both methods are fast but the histogram method is more flexible in dealing with different types of structuring element shapes.

ns970223.pdf (Scanned)

ns970223.pdf (From Postscript)

TOP



Structuring Element Decomposition by Tree Searching

Authors:

M. Razaz, University of East Anglia (U.K.)
D.M.P. Hagyard, University of East Anglia (U.K.)

Volume 1, Page (NA), Paper number 224

Abstract:

Morphological image processing is a technique that is becoming increasingly important for a wide range of image processing tasks. The two primitive operations, dilation and erosion, expand or contract objects of an image in a manner described by the structuring element, commonly a binary image. The shape of the structuring element allows fine control over the shapes processed by the operation. The time taken for morphological operations to complete is proportional to the number of pixels in the structuring element. By breaking the structuring element down into pieces that are applied sequentially to an image the computation time for the morphological operations can be reduced. Ibis paper examines our implementation of the Zhuang and Haralick tree search decomposition algorithm and presents results of timing experiments that show the time taken for decomposition rises exponentially with the number of pixels in the structuring element.

ns970224.pdf (Scanned)

ns970224.pdf (From Postscript)

TOP



Synthesis of A Parallel, Optimal Stack Filter Training Algorithm

Authors:

Kelvin L. Fong, Purdue University (U.S.A.)
George B. Adams III, Purdue University (U.S.A.)
Edward J. Coyle, Purdue University (U.S.A.)
Jisang Yoo, Hallym University (Korea)

Volume 1, Page (NA), Paper number 225

Abstract:

An adaptive algorithm for generating optimal stack filters is presented. The algorithm is iterative and highly parallel. The algorithm is summarized, its time complexities axe analyzed, and implementation details, such as data distribution and communication patterns, are described including performance results from an implementation on a 16K processor MasPar MP-1 SIMD computer.

ns970225.pdf (Scanned)

ns970225.pdf (From Postscript)

TOP



Decomposition of Structuring Elements for Optimal Implementation of Morphological Operations

Authors:

Hochong Park, Samsung Electronics Co. (Korea)
Roland T. Chin, Hong Kong University of Science and Technology (Hong Kong)

Volume 1, Page (NA), Paper number 226

Abstract:

The computational cost of morphological operations can be reduced by proper decomposition of structuring elements into smaller elements. In this paper, optimal decomposition of a set of commonly-used structuring elements is derived for two hardware architectures 2D mesh array processors and 3 x 3 pipeline machines, based on the decomposition algorithms reported in [11 and [21. The resulting set of optimal decomposition provides a useful reference guide to the design and optimal implementation of morphological image filters.

ns970226.pdf (Scanned)

ns970226.pdf (From Postscript)

TOP