optimization in image processing

Question

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

Answer 1

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.

Answer 2

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