# Cluster a signal into areas of equal intensity

Introduction

I have a greyscale photograph that I want to partition into areas of equal intensity. This means, that the integral over each partition should be (roughly) equal. There is no unique solution to this problem, but although I have some ideas on how to implement it, I am looking for any effective solutions for bitmap input.

1D-example

Let f be my signal, and g it's strictly positive, "padded" version:

f[x_] = 0.2 Cos[5 x] + Sin[x];
const = First[Minimize[f[x], {x}]];
g[x_] := 0.1 + f[x] - const;
G[x_] = Integrate[g[s], {s, 0, x}];


My signal is now of total intensity

max = F[4 \[Pi]];


and I can divide my y-axis into equal segments

k = 20;
sols = Table[FindRoot[G[x] - y == 0, {x, y}], {y, Range[0, max, max/(k - 1)]}];


and by intersecting these segments with my integral curve, I can project to the x-axis and get my desired intervals:

Show[
{
Plot[{g[x], G[x]}, {x, 0, 4 \[Pi]}, PlotStyle -> {{Thick, Green}, Red}],
Graphics[Point[{#, G[#]}] & /@ (x /. sols)],
Graphics[Line[{{0, G[#]}, {#, F[#]}, {#, 0}} & /@ (x /. sols)]]
}
]


Which gives me

2D-case

I can imagine that this method generalises to 2D, but it is unclear how to implement it. Also, a big penalty comes from attempts at interpolating the image.

Another idea is to use Sasha's solution for sampling a probability distribution (in my case, the image itself):

RandomVariate from 2-dimensional probability distribution

Thereafter one can generate the Voronoi-diagram for the sample. However, I have been unable to create a feasible solution using this method as well.

It seems to me, that this is a problem better approached by a combination of image processing algorithms. After all, all my input is, is a bitmap. However, after researching this, I could not find a previous description of the problem (or a solution for that matter) in any of the image-processing communities.

Questions

1. Does this problem have an actual name in the community already?

2. Can I find an efficient way of clustering a signal, preferably working on the discrete data, into regions of similar intensity?

3. (Bonus points) Can I generate grids with nice combinatorics? There is a nice Z-combinatorics for the 1D-example of course. Although a Z^2 grid for the 2D-case is too much to ask, perhaps there is a way to get a Quadtree-looking grid?

-
This question seems a better fit for the signal processing site –  belisarius Oct 12 '12 at 12:20
I checked it out, and though I partly agree, I just named this a "signal" in order to open up the question to more than image processing specialists. In addition, I am specifically looking for a Mathematica solution. –  kejace Oct 12 '12 at 12:23
But you need an algorithm first ... I think. Anyway, perhaps someone can come up with something here, mine was only a suggestion –  belisarius Oct 12 '12 at 12:26
–  belisarius Oct 12 '12 at 13:26