Let $f$ denote the measurement contribution function for paths of length $k\in\mathbb N$, i.e. $$f(x)=g(x_0\leftrightarrow x_1)W_{\text e}(x_1\to x_0)t_k(x_0,\ldots,x_k)L_{\text e}(x_k\to x_{k-1}),$$ where $$t_k(x)=\prod_{i=2}^kg(x_{i-1}\leftrightarrow x_i)f_{\text s}(x_i\to x_{i-1}\to x_{i-2}),$$ and $h_j$ denote the image reconstruction filter of the $j$th pixel so that the measurement $I_j$ of the $j$th pixel color is given by $$I_j=\int h_jf\:{\rm d}\mu.$$

What can we assume know about $h_j$ in general? One thing is that it will only depend on first two vertices of a path.

There are two properties which I really would like to being able to assume: (a) $c:=\sup_j\left\|h_j\right\|<\infty$ (b) $\int|g_j|^2\:{\rm d}\mu\le\alpha\int|f_0|^2\:{\rm d}\mu$ for some $\alpha\ge0$, where $g_j:=1_{\{\:h_j\:>\:0\:\}}\left(h_jf-\frac1{\mu\left(\left\{h_j>0\right\}\right)}I_j\right)$ and $f_0:=1_{\{\:f\:\ne\:0\:\}}\left(f-\frac1{\mu\left(\left\{f\ne0\right\}\right)}\int f\:{\rm d}\mu\right)$.

However, I know almost nothing about the mathematical properties of $h_j$ and so it's hard for me to verify if these properties hold. I guess that generally $h_j\ge0$, but I'm even unsure about that. Maybe even $h_j\in[0,1]$? It would be great if someone could answer if (a) and/or (b) hold or link me to a reference.

  • $\begingroup$ Technically you can pick it to be whatever you like. In practice it is a low-pass filter and the first requirement is obviously desirable. You cannot guarantee the second one for arbitrary $f$ and $h$. How did you come up with (b)? $\endgroup$ – lightxbulb Feb 20 at 5:21
  • $\begingroup$ (b) is closely related to the asymptotic variance of estimates of $I_j$. I've missed a constant on the right-hand side. Does it change your comment? $\endgroup$ – 0xbadf00d Feb 20 at 5:34
  • $\begingroup$ With the $\alpha$ it's trivial if you can guarantee that $\exists \alpha, \forall x, \, |h_j(x)f(x) - I_j|^2 \leq \alpha |f(x) - \int f|^2$. Note that this may prove problematic only at points where the right hand-side is zero. So I guess you need some extra assumptions on $h$. $\endgroup$ – lightxbulb Feb 20 at 5:48
  • $\begingroup$ @lightxbulb Yes, that' clear. But, again, I'm lacking information on $h$. Can we say more if we assume that $h$ is a "Box filter"? $\endgroup$ – 0xbadf00d Feb 20 at 5:57
  • 1
    $\begingroup$ If you can rewrite the reconstruction as convolution with a low pass filter, I believe you can use Young's theorem to get a bound. Sketch: $\|e * h\|^2_2 \leq \|e\|^2_2\|h\|^2_1$, if the 1-norm of $h$ is less or equal to 1 (should probably hold for your low pass filter), then you can bound the lhs by the 2-norm of $e$. $\endgroup$ – lightxbulb Feb 20 at 6:05

I am replying to the last edit of the question.

You can show that $\|h_j * f \|^2_2 \leq \|h_j\|^2_1\|f\|^2_2$ from Young's theorem. Provided that $\|h_j\|_1 \leq 1$ you have: $\|h_j * f \|^2_2 \leq \|f\|^2_2$. Additionally for $g_j$ I believe you want to clamp the indicator function to $\{h_j > 0 \wedge f > 0\}$. Then $\int_{\{h_j>0 \wedge f>0\}} a\leq \int_{\{f>0\}}a$ (since the integrands are always non-negative: $a\geq 0$). This basically proves that the inequality holds for the left terms of the quadratic expansions, the middle terms are both negative, so those may be ignored. The only thing left to prove is: $(\frac{1}{\mu(\{h_j>0 \wedge f>0\})}\int h_jf)^2 \leq (\frac{1}{\mu(\{f>0\})}\int f)^2$, which is the case if $h_j \leq 1$ everywhere. Basically, as long as your filter $h_j$ preserves the minimum and maximum of the image, you're good (this is not an unreasonable requirement for a filter, note however, that there are filers that do not preserve min-max).

Edit: My bad, the middle terms may not be ignored (at least the one on the right of the inequality). Which means you are left to prove that:

$$\frac{(\int h_jf)^2}{\mu(\{h_j>0 \wedge f>0\})} \geq \frac{(\int f)^2}{\mu(\{f>0\})}$$, which will be a problem.

I guess one has to use tighter bounds to relate the mixed term with the squared terms.

Edit 2:

Let's consider the expression as a whole then:

$$\int \left(h_jf - \frac{\int h_jf}{\mu(\{h_j > 0 \wedge f > 0\})} \right)^2 \leq \alpha \int \left(f - \frac{\int f}{\mu(\{f > 0\})} \right)^2$$ $$ 0 \leq \alpha\int (f)^2 - \int (h_jf)^2 +\alpha\frac{(\int f)^2}{\mu^2(\{f > 0\})} - \frac{(\int h_jf)^2}{\mu^2(\{h_j > 0 \wedge f > 0\})} + \frac{2(\int h_jf)^2}{\mu(\{h_j > 0 \wedge f > 0\})} - \alpha\frac{2(\int f)^2}{\mu(\{f > 0\})}$$ $$ 0 \leq \alpha\left(\int (f)^2 - \frac{(1-2\mu(\{f > 0\}))(\int f)^2}{\mu^2(\{f > 0\})}\right) - \left( \int (h_jf)^2 - \frac{(1-2\mu(\{h_j > 0 \wedge f > 0\}))(\int h_jf)^2}{\mu^2(\{h_j > 0 \wedge f > 0\})}\right) $$

$$0 \leq \left(\int(\sqrt{\alpha}f)^2-\int (h_jf)^2\right) - \left(\frac{\alpha(1-2\mu(\{f > 0\}))(\int f)^2}{\mu^2(\{f > 0\})} - \frac{(1-2\mu(\{h_j > 0 \wedge f > 0\}))(\int h_jf)^2}{\mu^2(\{h_j > 0 \wedge f > 0\})}\right) $$

$$0 \leq \left(\int(\sqrt{\alpha}f)^2-\int (h_jf)^2\right) - \left(a \left(\int \sqrt{\alpha}f\right)^2 - b\left(\int h_jf\right)^2\right)$$

Note also that $\left(\int u\right)^2 \leq \int u^2$. Then with an appropriate $\alpha$ and $h_j$ bounded it should hold. You may want to study the $a,b$ tems also.

| improve this answer | |
  • $\begingroup$ Thank you for your answer. It would be enough for me to show (b) for the box filter with radius 1/2. $\endgroup$ – 0xbadf00d Mar 2 at 12:30
  • $\begingroup$ Regarding your "whole term equation": Note that it simplifies to $$\mu|h_jf|^2-\frac{|\mu(h_jf)|^2}{\mu(B_j)}\le\alpha\left[\mu|f|^2-\frac{|\mu f|^2}{\mu(B)}\right],$$ where $B:=\{f\ne0\}$, $B_j:=B\cap\{h_j>0\}$ and $\mu g:=\int g\:{\rm d}\mu$. And it might be useful to note that, if each $h_j$ is a box filter and hence takes only the values $0$ or $1$, we've got $|h_j|^2=h_j$. $\endgroup$ – 0xbadf00d Mar 2 at 12:47
  • $\begingroup$ And let me note that the aspect of (b) I'm looking for is that we can bound the left-hand side in terms of the variance of $f$. So, the factor $\frac1{\mu(B)}$ before the integral in the definition of $f_0$ is not important for me. $\endgroup$ – 0xbadf00d Mar 2 at 12:57
  • $\begingroup$ If you set $a=b=1$, then $h_j \leq \sqrt{\alpha}$ is your requirement. But I believe you allow for $\alpha$ to be any, thus you just require for $h_j$ to never go to infinity (which holds for filters). Since it's also an integral, I would say that it's even ok for it to explode on sets of measure zero. $\endgroup$ – lightxbulb Mar 2 at 13:00
  • $\begingroup$ How do I need to read your equation lines? Are they meant to be equivalent to each other or are they meant to be implications (eq. 1 implies eq.2 and so on)? I begin to struggle what you did from (and including) the third equation on. Do you agree that your first equation is equivalent to the one in my second comment? $\endgroup$ – 0xbadf00d Mar 2 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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