An efficient divide-and-conquer algorithm for morphological filters

Research output: Contribution to journalArticle

Abstract

Morphological filters, evolved from the traditional envelope filter, are function oriented filtration techniques. A recent research on the implementation of morphological filters was based on the theoretical link between morphological operations and the alpha shape. However the Delaunay triangulation on which the alpha shape method depends is costly for large areal data. This paper proposes a divide-and-conquer method as an optimization to the alpha shape method aiming to speed up its performance. The large areal surface is divided into small sub-surfaces so that the alpha shape method is executed on the partitioned surfaces in a fast manner. The contact points are searched on each sub-surface and merged into a super set on which the alpha shape method is applied again to archive the updated result. The recursion process is repeated until the contact points of the whole surface are obtained. The morphological envelope could be computed recursively without the 3D Delaunay triangulation to the whole surface data. Meanwhile this method retains almost all the merits of the alpha shape method. The experiment shows that the result obtained by the divide-and-conquer algorithm is consistent with the one generated by applying the alpha shape method directly. The performance evaluation reveals that the divide-and-conquer algorithm achieved superior performances over the original alpha shape method.

Original languageEnglish
Pages (from-to)142-147
Number of pages6
JournalProcedia CIRP
Volume10
DOIs
Publication statusPublished - 19 Sep 2013
Event12th CIRP Conference on Computer Aided Tolerancing - Huddersfield, United Kingdom
Duration: 18 Apr 201219 Apr 2012
https://www.tib.eu/en/search/id/TIBKAT%3A784140057/12th-CIRP-Conference-on-Computer-Aided-Tolerancing/ (Link to Conference Details )

Fingerprint

Point contacts
Triangulation
Experiments

Cite this

@article{3e80989aa8314e33b6508f0d83da5336,
title = "An efficient divide-and-conquer algorithm for morphological filters",
abstract = "Morphological filters, evolved from the traditional envelope filter, are function oriented filtration techniques. A recent research on the implementation of morphological filters was based on the theoretical link between morphological operations and the alpha shape. However the Delaunay triangulation on which the alpha shape method depends is costly for large areal data. This paper proposes a divide-and-conquer method as an optimization to the alpha shape method aiming to speed up its performance. The large areal surface is divided into small sub-surfaces so that the alpha shape method is executed on the partitioned surfaces in a fast manner. The contact points are searched on each sub-surface and merged into a super set on which the alpha shape method is applied again to archive the updated result. The recursion process is repeated until the contact points of the whole surface are obtained. The morphological envelope could be computed recursively without the 3D Delaunay triangulation to the whole surface data. Meanwhile this method retains almost all the merits of the alpha shape method. The experiment shows that the result obtained by the divide-and-conquer algorithm is consistent with the one generated by applying the alpha shape method directly. The performance evaluation reveals that the divide-and-conquer algorithm achieved superior performances over the original alpha shape method.",
keywords = "Alpha shape, Divide-and-conquer, Morphological filter, Surface texture",
author = "Shan Lou and Xiangqian Jiang and Scott, {Paul J.}",
year = "2013",
month = "9",
day = "19",
doi = "10.1016/j.procir.2013.08.024",
language = "English",
volume = "10",
pages = "142--147",
journal = "Procedia CIRP",
issn = "2212-8271",
publisher = "Elsevier",

}

An efficient divide-and-conquer algorithm for morphological filters. / Lou, Shan; Jiang, Xiangqian; Scott, Paul J.

In: Procedia CIRP, Vol. 10, 19.09.2013, p. 142-147.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An efficient divide-and-conquer algorithm for morphological filters

AU - Lou, Shan

AU - Jiang, Xiangqian

AU - Scott, Paul J.

PY - 2013/9/19

Y1 - 2013/9/19

N2 - Morphological filters, evolved from the traditional envelope filter, are function oriented filtration techniques. A recent research on the implementation of morphological filters was based on the theoretical link between morphological operations and the alpha shape. However the Delaunay triangulation on which the alpha shape method depends is costly for large areal data. This paper proposes a divide-and-conquer method as an optimization to the alpha shape method aiming to speed up its performance. The large areal surface is divided into small sub-surfaces so that the alpha shape method is executed on the partitioned surfaces in a fast manner. The contact points are searched on each sub-surface and merged into a super set on which the alpha shape method is applied again to archive the updated result. The recursion process is repeated until the contact points of the whole surface are obtained. The morphological envelope could be computed recursively without the 3D Delaunay triangulation to the whole surface data. Meanwhile this method retains almost all the merits of the alpha shape method. The experiment shows that the result obtained by the divide-and-conquer algorithm is consistent with the one generated by applying the alpha shape method directly. The performance evaluation reveals that the divide-and-conquer algorithm achieved superior performances over the original alpha shape method.

AB - Morphological filters, evolved from the traditional envelope filter, are function oriented filtration techniques. A recent research on the implementation of morphological filters was based on the theoretical link between morphological operations and the alpha shape. However the Delaunay triangulation on which the alpha shape method depends is costly for large areal data. This paper proposes a divide-and-conquer method as an optimization to the alpha shape method aiming to speed up its performance. The large areal surface is divided into small sub-surfaces so that the alpha shape method is executed on the partitioned surfaces in a fast manner. The contact points are searched on each sub-surface and merged into a super set on which the alpha shape method is applied again to archive the updated result. The recursion process is repeated until the contact points of the whole surface are obtained. The morphological envelope could be computed recursively without the 3D Delaunay triangulation to the whole surface data. Meanwhile this method retains almost all the merits of the alpha shape method. The experiment shows that the result obtained by the divide-and-conquer algorithm is consistent with the one generated by applying the alpha shape method directly. The performance evaluation reveals that the divide-and-conquer algorithm achieved superior performances over the original alpha shape method.

KW - Alpha shape

KW - Divide-and-conquer

KW - Morphological filter

KW - Surface texture

UR - http://www.scopus.com/inward/record.url?scp=84884833030&partnerID=8YFLogxK

U2 - 10.1016/j.procir.2013.08.024

DO - 10.1016/j.procir.2013.08.024

M3 - Article

VL - 10

SP - 142

EP - 147

JO - Procedia CIRP

JF - Procedia CIRP

SN - 2212-8271

ER -