Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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