Two linear time Union-Find strategies for image processing
Two linear time Union-Find strategies for image processing
复制标题
DOI：
10.1016/0304-3975(94)00262-2
复制
发表时间：
1996-02-05
影响因子：
1.1
通讯作者：
Gustedt, J
中科院分区：
文献类型：
--
作者：
Fiorio, C;Gustedt, J
我们考虑将Union-Find作为一种合适的数据结构来获得两种用于图像分割的线性时间算法。线性是通过限制执行Union的顺序来获得的。对于一种算法，通过平摊查找操作来证明复杂度界。对于另一种方法，我们使用周期性更新来保持union - find树的相关部分保持恒定高度。这两种算法都是一般化的，并导致了新的Union-Find线性策略，这些策略既没有被Gabow和Tarjan（1984）的算法所涵盖，也没有被Dillencourt等人（1992）的算法所涵盖。
We consider Union-Find as an appropriate data structure to obtain two linear time algorithms for the segmentation of images. The linearity is obtained by restricting the order in which Union's are performed. For one algorithm the complexity bound is proven by amortizing the Find operations. For the other we use periodic updates to keep the relevant part of our Union-Find-tree of constant height. Both algorithms are generalized and lead to new linear strategies for Union-Find that are neither covered by the algorithm of Gabow and Tarjan (1984) nor by the one of Dillencourt et al. (1992).