Calculate the gradient for an histogram in c++

Question

I calculated the histogram(a simple 1d array) for an 3D grayscale Image. Now I would like to calculate the gradient for the this histogram at each point. So this would actually mean I have to calculate the gradient for a 1D function at certain points. However I do not have a function. So how can I calculate it with concrete x and y values?

For the sake of simplicity could you probably explain this to me on an example histogram - for example with the following values (x is the intensity, and y the frequency of this intensity):

x1 = 1; y1 = 3

x2 = 2; y2 = 6

x3 = 3; y3 = 8

x4 = 4; y4 = 5

x5 = 5; y5 = 9

x6 = 6; y6 = 12

x7 = 7; y7 = 5

x8 = 8; y8 = 3

x9 = 9; y9 = 5

x10 = 10; y10 = 2

I know that this is also a math problem, but since I need to solve it in c++ I though you could help me here.

Thank you for your advice Marc

Answer 1

Hi

1. Take some squared paper and draw on it your histogram. Draw also vertical and horizontal axes through the 0,0 point of your histogram.

2. Take a straight edge and, at each point you are interested in, rotate the straight edge until it accords with your idea of what the gradient at that point is. It is most important that you do this, your definition of gradient is the one you want.

3. Once the straight edge is at the angle you desire draw a line at that angle.

4. Drop perpendiculars from any 2 points on the line you just drew. It will be easier to take the following step if the horizontal distance between the 2 points you choose is about 25% or more of the width of your histogram. From the same 2 points draw horizontal lines to intersect the vertical axis of your histogram.

5. Your lines now define an x-distance and a y-distance, ie the length of the horizontal/ vertical (respectively) axes marked out by their intersections with the perpendiculars/horizontal lines. The gradient you want is the y-distance divided by the x-distance.

Now, to translate this into code is very straightforward, apart from step 2. You have to define what the criteria are for determining what the gradient at any point on the histogram is. Simple choices include:

a) at each point, set down your straight edge to pass through the point and the next one to its right;

b) at each point, set down your straight edge to pass through the point and the next one to its left;

c) at each point, set down your straight edge to pass through the point to the left and the point to the right.

You may want to investigate more complex choices such as fitting a curve (such as a quadratic or higher-order polynomial) through a number of points on your histogram and using the derivative of that to represent the gradient.

Until you understand the question on paper avoid coding in C++ or anything else. Once you do understand it, coding should be trivial.

Regards

Mark

Answer 2

I think you can calculate your gradient using the same approach used in image border detection (which is a gradient calculus). If your histogram is in a vector you can calculate an approximation of the gradient as*:

for each point in the histogram compute 
     gradient[x] = (hist[x+1] - hist[x])

This is a very simple way to do it, but I'm not sure if is the most accurate.

• approximation because you are working with discrete data instead of continuous

Edited:

Other operators will may emphasize small differences (small gradients will became more emphasized). Roberts algorithm derives from the derivative calculus:

lim delta -> 0 = f(x + delta) - f(x) / delta

delta tends infinitely to 0 (in order to avoid 0 division) but is never zero. As in computer's memory this is impossible, the smallest we can get of delta is 1 (because 1 is the smallest distance from to points in an image (or histogram)).

Substituting

lim delta -> 0 to lim delta -> 1

we get

f(x + 1) - f(x) / 1 = f(x + 1) - f(x) => vet[x+1] - vet[x]

Answer 3

Two generally approaches here:

1. a discrete approximation to the derivative
2. take the real derivative of a fitted function

In the first case try:

g = (y_(i+1) - y_(i-1))/2*dx

at all the points except the ends, or one of

g_left-end  = (y_(i+1) - y_i)/dx
g_right-end = (y_i - y_(i-1))/dx

where dx is the spacing between x points. (Unlike the equally correct definition Andres suggested, this one is symmetric. Whether it matters or not depends on you use case.)

In the second case, fit a spline to your data[*], and ask the spline library the derivative at the point you want.

[*] Use a library! Do not implement this yourself unless this is a learning project. I'd use ROOT because I already have it on my machine, but it is a pretty heavy package just to get a spline...

---

Finally, if you data is noisy, you ma want to smooth it before doing slope detection. That was you avoid chasing the noise, and only look at large scale slopes.