2D and 3D Optimal Parallel Image Warping

Spatial image warping is useful for image processing and graphics. In this paper, we present concurrent-read-exclusive-write (CREW) and exclusive-read-exclusive-write (EREW) parallel-random-access-machine (PRAM) algorithms that achieve O(1) asymptotic run time. The significant result is the creative processor assignment that results in an EREW PRAM algorithm. The forward algorithm calculates any nonscaling affine transform including arbitrary skewings, translations, and rotations. The EREW algorithm is the most efficient in practice, and the MasPar MP-1 with 16K processors rotates a 4-million-element image in under a second and a 2-million-element volume in one-half of a second. This high performance allows interactive viewing of volumes from arbitrary viewpoints and illustrates linear speedup. This practical efficiency is analyzed and illustrated by using a bridging model of computation. We develop the mixed cost communication machine (MCCM) to quantify the communication costs and correlate these costs to the MasPar MP-1. The forward algorithm has provable N = 1 congestion on the MCCM, while the backward algorithm has congestion N > 1 which varies with the transform. There are also important quality advantages using our direct warping techniques; empirical measurements are given to provide comparisons to multipass warps.