Histogramming is a useful image processing primitive. One application is histogram normalization (or equalization), a technique that flattens the histogram and, thus, improves the contrast of an image by ``spreading out'' colors which might be too clumped together for human visual distinction.
Let k be the number of grey levels in the 
input image
X, and without loss of generality, k is assumed to be a power of
two. Note that this implies that for 
, the value of
is an integer 
. Our histogramming algorithm is
quite simple. The first step consists of creating an array
on every processor i, such that each processor
tallies the number of grey levels in its own 
subimage into its array 
. The purpose of the
next step is to rearrange the data so that the tallies of each grey
level reside on the same processor. If k<p we use a truncated
transpose to put each row into a processor, 
, 
. If 
we transpose 
rows of the local
histograms into each processor, such that each processor, 
, has
all the intermediate sums needed to compute 
through 
. The
routing step is followed by local computations of the histogram which
can be done in O
operations. Next, one processor, 
,
prefetches the results by doing a circular data movement, as described
in Section 2, and outputs the k-bar histogram of
the image.
The communication complexity can be estimated as follows. Two main
communication steps are used in our algorithm. The first is a matrix
transpose of the 
histogram array and takes 
. The second communication
collects the histogram bars on a single processor and takes 
. Thus, the
histogramming algorithm has the following complexities:
