A Comparison of Parallel Algorithms for Calculating the Anti-Aliased Euclidean Distance Transform

This thesis presents a comparison of three different parallel algorithms, adapted to calculate the anti-aliased euclidean distance transform. They were originally designed to calculate the binary euclidean distance transform. The three algorithms are; SKW, Jump Flooding Algorithm (JFA), and Parallel Banding Algorithm (PBA). The results presented here show that the two simpler algorithms, SKW and JFA, can easily be adapted to calculate the anti-aliased transform rather than the binary transform. These two algorithms show good performance in regards to accuracy and precision. The more complex algorithm, PBA, is not as easily adapted. The design of this algorithm is based on some assumptions about the binary transform, which do not hold true in the case of the anti-aliased transform. Because of this the algorithm does not produce a transform with the same level of accuracy as the other algorithms produce