完全欧几里德距离变换的最优算法

摘要

欧几里德距离变换(EDT)对由黑白象素构成的二值图象中所有象素找出其到最近黑色象素的距离,应用于图象分析、计算机视觉.在本文之前,该问题的最好复杂度为O(n2logn).本文提出了一个复杂度为O(n2)的算法,使复杂度达到了最优.该算法可以并行化,在有r个处理单元的EREW PRAM计算模型上,若rlogr≤22/6n,则时间复杂度为O(n/r),否则为O(nlogr).