Fast Procedure to Evaluate Linear Expression AX+BY+C on a Polymorphic-Mesh
Original Publication Date: 1988-Jul-01
Included in the Prior Art Database: 2005-Feb-15
This article describes a procedure which offers a speed improvement of several orders of magnitude over existing methods in evaluating the linear expression AX+BY+C for all possible pairs of (X, Y) in an nxn array. Computing the linear expression AX+BY+C (A, B and C are constant) for an array of (x, y) coordinates where 0&x,y&n-1 is very useful for graphics, image processing and computer vision applications. The linear expression can be computed by a general purpose serial processor in O(nxn) time where the size of the (x, y) array is nxn. This article describes a procedure to compute the linear expression in a bit-serial fashion by an nxn polymorphic-mesh with great speed improvement. The procedure is of complexity O(l + log n) where 1 is the word length of the coefficients A, B and C.