0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Knut Inge
    Commented May 7, 2020 at 5:31

1 Answer 1

Reset to default
1
$\begingroup$

If you move the 3x3 window to the right by 1 pixel, a new column gets introduced to the right of the previous window and the leftmost column gets deleted.

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$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.