SUMMED AREA COMPUTATION USING RIPMAP OF PARTIAL SUMS

摘要

Methods are provided to perform area summation of various subsections of data values in a regular input array of one or several dimensions and varying sizes. The summation is achieved by adding up values from a ripmap of partial sums, where the partial sums are computed from the input array using a binary reduction method. According to such embodiments, the generation of the ripmap of partial sums will employ several binary reduction stages. Within each stage, a reduction operator is used that adds two elements along the respective direction. This is repeated until the output is only one element wide in the respective direction. The addresses of partial sums in the ripmap may subsequently be computed using a binary analysis of the target subsections in order to choose those partial sum values for a desired area that results in the desired area sum using an optimal number of data fetches.

主权项

1. A method for calculating an area sum from an input array, the method comprising:
receiving an input array comprising a plurality of elements; generating a ripmap of partial sums over a plurality of input values of the input array the ripmap being arranged in a plurality of levels; determining a plurality of addresses in the ripmap of partial sums corresponding to an identified target subsection of said input array; fetching a plurality of values corresponding to the plurality of addresses in the ripmap of partial sums; and calculating a total sum corresponding to the target subsection from the subset of partial sums.