Fast algorithm and its systolic realisation for distance transformation

Distance transformation has been widely applied to image matching and analysis. The hardware implementation of distance transformation is necessary because real-time (video rate) processing is required for most applications. The paper proposes a four-pass algorithm for distance transformation. Its computation complexity is the same as a two-pass raster scan algorithm but the data dependencies are simpler and therefore more suitable for designing hardware architectures. Systolic arrays are very amenable to VLSI implementation. They are especially suited to a special class of computation-bound algorithms with regular, localised data flow. In the paper the authors design a systolic array for the proposed four-pass algorithm and use the multilevel pipelining technique to improve the performance. Its speed is 2.4 times, and the cost is 2/3 times, that of a systolic array designed using the two-pass raster scan algorithm