10-04-2017, 08:40 PM
[attachment=4401]
ABSTRACT
MORPHOLOGICAL operators like dilation and erosion With structuring elements (S.E.) are the most fundamental Operators in mathematical morphology and have become Common tools for both image filtering and analysis , of binary And grayscale images, especially since the development of Efficient algorithms . Usually, these efficient algorithms Can only be used for binary images , 9, , , or They are limited to shapes that can (efficiently) be decomposed Into a series of linear S.E.s 8, , . Efficient implementations For specialized hardware have also been studied extensively, Such as the decomposition of arbitrary shapes into Blocks 0. A recent overview of efficient algorithms for morphological operators with linear S.E. and -D S.E. decompositions Can be found in . All methods based on decomposition Of -D S.E.s into linear S.E.s share the same limitation: many Shapes either cannot be decomposed efficiently or they cannot Be decomposed at all. In the binary case, efficient algorithms For some -D shapes like circles do exist, but these cannot efficiently Be extended to the grayscale case, for which polygonal Approximations , 6 of circles usually are used instead. For Larger circles these approximations tend be either too coarse or Manuscript received January 6, 00; revised October , 00. The associate Editor coordinating the review of this manuscript and approving it for publication Was Prof. Philippe Salem bier. The authors are with the Institute of Mathematics and Computing Science, University of Groningen, 900 AV, Groningen, the Netherlands. Digital Object Identifier 0.09/TIP.00.98 Too computationally intensive, since the number or linear S.E.s Required is proportional to the diameter of the circle. Algorithms that efficiently perform morphological operators With arbitrary S.E.s not only are important for those cases where The S.E. cannot be decomposed, but also wherever a generic algorithm Is desired such as in image processing libraries, which Often have a number of specialized routines for specific cases, And a direct implementation for arbitrary S.E. Furthermore, for Many applications the benefits of using the fastest specialized Algorithm available instead of using one slightly less efficient Generic algorithm does not outweigh the costs involved in Adapting the methods used. S.E. shape decompositions require Some design and programming efforts that can be avoided if A generic algorithm is used. Our algorithm is efficient for any S.E. and only significantly outperformed when large linear S.E.s or compositions of linear S.E.s are used with a dedicated Algorithm such as proposed by Gil and Kimmel . Commercial and open source image processing software for Performing morphological operations was found to be either Quite slow, being based on a processor optimized version of the direct algorithm (like openCV or Mat lab) or fast but limited to rectangular S.E.s (like Adobe Photoshop CS). Olena , which uses the algorithm by Van Droogenbroeck and Talbot , is one of the fewexceptions that is faster and can handle arbitrary S.E.s. Van Droogenbroeck and Talbot proposed an efficient algorithm for computing morphological operations with arbitrary -D shapes using a histogram, which makes the computing time of their algorithm dependent on the number of gray levels used. Their idea is to compute for one pixel of the image the complete histogram based on the intensities of the pixels around corresponding to elements of the S.E. The value of after erosion is the minimum intensity in the histogram which has a value 0. For all succeeding pixels of the image (by moving around the S.E. over the image), the histogram is efficiently updated and the position of its minimum intensity changes only if i) a new minimum value is shifted into the histogram, which can be kept track when the histogram is updated, or ii) when the current minimum is shifted out of the histogram, in which case the algorithm searches for the first following (brighter) intensity which is now represented in the histogram. The C source code of the following algorithms are available on request: i) our proposed ( Urbach-Wilkinson or UW) algorithm, ii) Van Droogenbroeck and Talbot (DT) for arbitrary -D S.E.s, and ii) Gil and Kimmel (GK) for linear S.E.s. In a preliminary version 8, we presented a new method for performing morphological operators with any -D flat structuring element that always outperforms existing