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 excl usive-read-exclusive-write (EREW) parallel-random-access-machine (PRAM ) algorithms that achieve O(1) asymptotic run time. The significant re sult is the creative processor assignment that results in an EREW PRAM algorithm. The forward algorithm calculates any nonscaling affine tra nsform 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 secon d and a 2-million-element volume in one-half of a second. This high pe rformance allows interactive viewing of volumes from arbitrary viewpoi nts and illustrates linear speedup. This practical efficiency is analy zed and illustrated by using a bridging model of computation. We devel op the mixed cost communication machine (MCCM) to quantify the communi cation costs and correlate these costs to the MasPar MP-1. The forward algorithm has provable N = 1 congestion on the MCCM, while the backwa rd algorithm has congestion N > 1 which varies with the transform. The re are also important quality advantages using our direct warping tech niques; empirical measurements are given to provide comparisons to mul tipass warps. (C) 1995 Academic Press, Inc.