# optimization in image processing

I want to solve the following problem. I know it is an optimization problem, but since I don't know anything about optimization, I would appreciate if you would give me some guidance regarding where to look in order to find the answer (what kind of optimization, what kind of techniques can solve this problem etc.)

Let digital image $I$ with distribution (histogram) $h(x)$ for $x\in[0,B]$ and $x, B, h(x) \in \mathbb N$.

Let mapping function $g(A,x)=int\left[\frac{Ax}{B+A-x}\right]$ with $A \in \mathbb R^{+}$ and $g\to[0,B]$, which is applied to all the pixels of image $I$, thus, getting the transformed image $II=g(A,I)$

Let $H(A,x)$ be the histogram of image $II$

$$H(A,x)=\sum^{B}_{k=0} \left[\delta\left(g(A,k)-x\right)h(k)\right]$$

This new histogram is solely depended on the initial image $I$ and in the value $A$. The question is which value of $A$ can maximize/minimize a specific metric over the histogram $H$ of the transformed image $II$, without trying all the possible values of $A$. The metric could be histogram flatness

$$\operatorname{flatness}(A)=\frac{\sum^{B}_{i=0}\left[\frac{S}{B}-H(A,i)\right]^2}{S^2}$$

where $S=\sum^{B}_{k=0}h(k)$ (the total number of pixels in the image).

Thank you in advance for your guidance....

-
In the definition of $g(A,x)$, is $int$ supposed to be a rounding function? (Also: I edited the formatting of your math. It's preferable to always keep variable names inside the dollar signs, so they are rendered consistently in italics and stand out of the normal text.) – Rahul Feb 15 '13 at 2:12
@5pm: I don't know if putting a bounty on a question whose asker hasn't responded to questions asked in the comments is the best policy. But you've tempted me to go ahead and post an (incomplete) answer anyway. – Rahul Feb 18 '13 at 6:55
@ℝⁿ. The OP was last seen Feb 13 at 7:02, which was before you commented. Since the question got no response in the five days before that, chances are that the OP is not checking it daily. // I'm sure that int is a rounding function, but I also agree that optimization for $A$ should probably disregard rounding in favor of continuity. – user53153 Feb 18 '13 at 20:32

## 2 Answers

The situation becomes much easier to analyze if we approximate the histograms by continuous distributions. That is, $h$ is a function $[0,B]\to\mathbb R$ such that the number of pixels in the image $I$ with intensities between $a$ and $b$ is $\int_a^b h(x)\,\mathbb dx$, and similarly for $H$. Then if $y=g_A(x)$, we can write $H(y)\,\mathrm dy=h(x)\,\mathrm dx$. You want to minimize \begin{align} \operatorname{flatness}(A)&=\int_0^B\big(S/B-H(y)\big)^2\,\mathrm dy\\ &=(S/B)^2\int_0^B\mathrm dy-2(S/B)\int_0^BH(y)\,\mathrm dy+\int_0^BH(y)^2\,\mathrm dy\\ &=\text{const.}+\int_0^BH(y)^2\,\mathrm dy, \end{align} so you really just want to minimize $\int_0^BH(y)^2\,\mathrm dy$. But we have \begin{align} \int_0^BH(y)^2\,\mathrm dy&=\int_0^BH(y)h(x)\,\mathrm dx=\int_0^B\frac1{\mathrm dy/\mathrm dx}h(x)^2\,\mathrm dx\\ &=\int_0^B\frac1{g_A'(x)}h(x)^2\,\mathrm dx=\int_0^B\frac{(A+B-x)^2}{A(A+B)}h(x)^2\,\mathrm dx. \end{align} So the intuition is simply that you want $g_A(x)$ to increase rapidly wherever $h(x)$ is large. A formal solution would require differentiating the last integral with respect to $A$ and setting the result to zero. Good luck...

-
I deeply apologize for not responding earlier to this. Thank you very much for your answer. Approximating the histogram with a continuous function indeed gave me better insights on how to approach this problem! Thank you once more! – user53785 Mar 4 '15 at 2:17

I am not quite clear what's your question is, especially for the int function (I treated as a rounding function).

From you penalty function, I guess it is related to the histogram equalization topic, which mapping an arbitrary pixel intensity distribution to a uniform one. Because your flatness function attains its minimum 0, only when $H(A,i)= S/B$ for all $i$s. Check wiki or matlab help for details about histogram equalization.

A common way to find the optimized mapping is to take the derivative, but in your case the rounding function is discontinuous and thus not differentiable. Actually, I cannot see why you cannot accept a searching-based solution, unless you want to give a very nice closed-form of this problem in a paper.

-
I also apologize for not getting back to this earlier. Thank you very much for your answer! int is the integer function, so rounding is also correct. Initially I thought I could find a closed form solution, but since this seems not feasible, I will consider also other approaches. – user53785 Mar 4 '15 at 2:20