# Local Histogram Processing clarification

In Gonzales' book Digital Image Processing in the section Local Histogram Processing, he writes, for a 2D image:

At each location, the histogram of the points in the neighborhood is computed and either a histogram equalization or histogram specification function is computed and either a histogram equalization or histogram specification transformation function is obtained. This function is then used to map the intensity of the pixel centered in the neighborhood. The center of the neighborhood region is then moved to an adjacent pixel location and the procedure is repeated.

He then writes:

Because only one row or column of the neighborhood changes during a pixel-to-pixel translation of the neighborhood, updating the histogram obtained in the previous location with the new data introduced at each motion step is possible. This approach has the obvious advantages over repeatedly computing the histogram of all pixels in the neighborhood each time the region is moved over one pixel location.

This last statement I am not clear about. Given a neighborhood, say a 3 by 3 patch centered at a pixel location $$(x,y)$$, if we shift the neighborhood over by one pixel to the right say, so it is now centered at $$(x+1,y)$$, in this case the letmost 3 by 1 column from the previous neighbourhood will not be in the new patch, and a new 3 by 1 column on the right of the previous patch will be present in the new patch.

What does the author mean when he says that this approach has the obvious advantages over repeatedly computing the histogram of all pixels in the neighborhood region each time the region is moved one pixel location?

• Populating a histogram for a 3x3 area means 3x3 =9 operations (reading data and incrementing the corresponding bins). If you slide that histogram by one element, e.g. to the right, you can get by with doing 3 new insertions, and 3 subtractions corresponding to the column that just went outside the window for a total of 6 operations. 6/9 means a 33% reduction in complexity. That is how I interpret the text. – Knut Inge May 7 at 5:31

If the histogram component for the k$$^{th}$$ intensity level is $$p_{k}=n_k/n$$ where n is the total number of pixels in the neighborhood and $$n_k$$ is the number of pixels with intensity k.
For new window, $$p'_{k} = (n_k+n_{r_k}-n_{l_k})/n$$ where $$n_{r_k}$$ is number of occurrence of the $$k^{th}$$ intensity level pixels in the added right column and $$n_{l_k}$$ is number of occurrence of the $$k^{th}$$ intensity level pixels in the deleted left column.
$$p'_{k} = n_k/n+(n_{r_k}-n_{l_k})/n$$ $$p'_{k} = p_k+(n_{r_k}-n_{l_k})/n$$