2
$\begingroup$

I'm a newbie at this forum, so I hope, that this question is not so silly.

Let's have some filter $F$, which is a linear combination, thus $F = \sum_{i=0}^{i=N}\alpha_ib_i$, where $\alpha_i$ are coefficients and $b_i$ are binary box functions. This decomposition is obtained by OOMP, however it is not important.

I've got the following problem: I need to normalize this filter so, that $L^2$ norm is equal to 1. I know, how to normalize $F$ (subtract DC component and compute $\frac{F}{\|F\|}$), however I need to normalize the linear combination with following constraint - recompute just coefficients $\alpha_i$, binary boxes $b_i$ can't be changed.

Thank you for your help.

  • 0
    Do you mean that only $\alpha_i$ can be adjusted? Also, what is OOMP?2011-06-29
  • 0
    Exactly, just $\alpha_i$. OOMP (optimal orthogonal matching pursuit) is a technique, how to select atoms from overcomplete dictionary (in this case, created by binary box functions) that make best approximation of some function. However, it is not important if you get this combination by OOMP, or by some other method. Important is, how to normalize it...2011-06-29

2 Answers 2

0

I tried to google for OOMP and I only got two hits. The first was for this page and the other for a paper on computer vision. I tried to skim that article, but probably I still have serious misunderstandings. Anyway, the problem I have in mind is the following. Using a 1-dimensional space to keep it simple. Assume that the domain is the interval $[0,9]$, and that the OOMP output is $f=1*\chi_{[1,2]}+2*\chi_{[4,8]}$, [Edit] in other words, there are two boxes: the interval $[1,2]$ and the interval $[4,8]$. [/Edit] This has a mean value of 1. I first assumed that removing the DC component amounts to subtracting the constant 1 from this function, but that would give us a function $$f-1=-1*\chi_{[0,1)}-1*\chi_{(2,4)}+1*\chi_{[4,8]}-1*\chi_{(8,9]}$$ and we necessarily create new boxes while doing that, because wherever the value was zero, there is a now a -1.

A way of getting a zero mean function out of this without modifying the set of boxes would be to subtract the mean of the restriction of $f$ to the union of the boxes. Here the union of boxes has measure 5 and the average of $f$ restricted to the union is $9/5$. So, if we do this subtraction business we get $$ f-\frac95\,\chi_{[1,2]\cup[4,8]}=-\frac45\,\chi_{[1,2]}+\frac15\,\chi_{[4,8]}. $$ The reason I think that this latter way of killing the DC-component is bad is that this changes the relative order of the components. The OOMP output marked the box $[1,2]$ as having something above the 'background'. If we subtract a constant only in the union of the boxes, then this box gets a negative sign indicating a level below the background. This is what I meant by saying that the quality of the approximation is now worse: In the computer vision paper the two boxes could in function $f$ mean that those two regions are both noted for being lighter than the surroundings. If the DC-component is removed by subtracting a constant function with support = the union of the boxes, then after this subtraction one of the original lighter regions is now hit with a negative number, and would be interpreted as darker than the surroundings. Ideally we might want the box generation algorithm itself to mark off both darker and lighter regions.

Here's the general formula that I used in the striked example (the latter, `suspicious' version, where no changes to the boxes are done). Let $\chi_{E_i}$ be the characteristic function of box $b_i$. Then the integral of $f$ over the union of the boxes is $\int f=\sum_i \alpha_i m(E_i),$ where $m(E_i)$ is the measure of the box $b_i$. A weighted measure of the union (=overlapping counted many times) is $m=\sum_i m(E_i)$. Then the function $$ \tilde{f}=\sum_i(\alpha_i-\frac{\int f}m)b_i $$ has zero mean. This you can then normalize to have unit $L^2$-norm in the usual way. Note you need to first replace $f$ with $\tilde{f}$ and then normalize. Not the other way around, because the $L^2$-norm goes down, when passing from $f$ to $\tilde{f}$. OTOH scaling the norm scales the mean value, so it won't reproduce a DC-component, if one didn't exist.

If you can spare the cycles, try this, and see if the results are ok. In the image-processing application the DC-component is a general grey level value, and you would have to take that into account outside the boxes also. Your application is hopefully very different.

  • 0
    Yep, as we solved with Steve above, the problem is no with scaling, however with DC subtraction. The question should be modified to the following: $F - mean(F) = \sum\alpha_ib_i - mean(F) = \sum(\alpha_i- ????? )b_i$. The filter looks like modulated Gaussian. I think, that I don't need to subtract anything outside of boxes, since all values outside boxes are $0$ - linear combination of boxes is obtained by OOMP from normalized version $F$ of that filters.Thus, I need just to somehow remove the DC component which is created by a linear combination of boxes(that basically approximate the filter)2011-06-30
  • 0
    Unfortnately, this will be quite tricky, perhaps, some kind of optimization technique may help (I expect, that the minimization of a DC component should be sufficient)?2011-06-30
  • 0
    @morph: Ok, I see that what I was saying was a bit silly. The problem of expressing the characteristic function of the union of boxes as a linear combination of those of the boxes remains. I will think about this a bit, and edit my answer. I have a question: Can the boxes overlap?2011-06-30
  • 0
    thx for interest, btw: answer can't be silly, silly is my questions since it was not accurate enough...2011-06-30
  • 0
    Yes, boxes may overlap since they are chosen from overcomplete dictionary. I do not understand why subtracting of the DC can effect the quality of approximation? Even if so, I suppose that it shouldn't be a serious problem, while the approximation is quite rough (I cannot use many boxes, just few of them because of speed)2011-06-30
  • 0
    well, I`m not sure if I understand you well, what do those indices mean... however, I still think, that it is not important how we get boxes and coefficients, if it is by OOMP, or by some other method. I believe, that there must exists some method how to just tune coefficients to remove the DC2011-06-30
  • 0
    @morph: I re-edited my answer to give the formula used in the example. I'm somewhat suspicious, but my impression is now heavily dependent on skimming that article by Tao, Crabb & Tang. Wonder why I didn't get any other hits, if the technique is widespread?2011-06-30
  • 0
    thank you for comment, I will try to use it2011-06-30
  • 0
    this technique is not so common, however it can help me to find the solution of my problem :) I didn`t see any other paper than those by Tao, Crabb & Tang... moreover it is not important, if it is widespread or not, important is, if it works or not :)2011-06-30
  • 0
    @morph: Agree with this. Good luck. Please give a summary of your findings here, if you can spare the time.2011-06-30
  • 0
    of course, moreover, if it will really help me, I will send you technical report to your email, ok? however it will take a few months...2011-06-30
  • 0
    Could you help me more, pls? Although you reply seemed to me quite clear, I've got some troubles with implementation. What exactly do you mean by "... where $m(E_i)$ is the measure of the box $b_i$..."2011-06-30
  • 0
    @morph: The same that Steve denoted with $|E_i|$. If we are in a 1-dimensional space, then $|[a,b]|$ is the length of the interval. If it is a subset of the plane, then it's the area of the box. In 3D-space it is the volume. If your space is a finite set (=bit combinations, pixels, whatever), then you can use the so called counting measure = the measure is simply the number of pixels in the box. Does any of these fit your needs?2011-06-30
  • 0
    so basically, in the case of binary box filters, $m(E_i)$ is the sum of all 1 of $b_i$ and $m=\sum_i^Nm(E_i)$ is the sum of all 1 of all N binary boxes, right?2011-06-30
  • 0
    $m(E_i)$ measures the size of the box $b_i$. Or the square of the $L^2$-norm of the box $b_i$.2011-07-01
  • 0
    am I right that $\frac{\int F}{m}$ = constant for all $i$? Or am I doing something wrong?2011-07-01
  • 0
    Yes. $\int f$ and $m$ are both constants by design. Do you think something else would work better?2011-07-01
  • 0
    well, it seems, that the DC component is reduced, however the result is different than in the case of removing DC from $F$. I have to try it, if it works or not...2011-07-01
  • 0
    it seems that it works2011-07-02
  • 0
    Glad to hear that! I'm still a bit concerned about the possible distortion of your signals relative to the 'background' level outside the union of the boxes. Another potential problem may be that the intersections of boxes get a double hit with this formula, and that may further distort your signal. Please keep me posted! The system things we're chatting, so you may consider using e-mail:-) If you run into any anomalies while using this formula, then something else will be needed.2011-07-02
0

Supoose that the $\alpha$'s are real. Let $b_i=I_{E_i}$ (characteristic function) be the boxes. Let $|\cdot|$ denote the Lebesgue measure. Suppose $\alpha_1$ can be adjusted. Note that \begin{eqnarray}\|F\|^2&=&\sum_i\sum_j \alpha_i\alpha_j |E_i\cap E_j|\ &=& |E_1|\alpha_1^2+2\alpha_1\sum_{j=1}^N\alpha_j|E_i\cap E_j|+\sum_{i\not=1}\sum_{j\not=1} \alpha_i\alpha_j |E_i\cap E_j|.\end{eqnarray} Then using $t=\alpha_1$, $\|F\|^2$ has the form $f(t)=at^2+bt+c$ with $a>0$. So your problem is solvable if and only if $\min f\le 1$. For example, if $b=0$ (which happens if box $b_1$ is disjoint from the other boxes) and $c>1$, then $\|F\|$ cannot be normalized to $1$ by adjusting $\alpha_1$ alone. So it just depends on the interaction of the terms in your filter. If it can be done, the solution is the zero of a simple quadratic.

  • 0
    Thank you for your reply. Yes, $\alpha$'s are only real numbers. I'm not sure, if I understand you well (I am not a mathematician). Am I right, that your conclude is, that the normalization cannot be done by adjusting $\alpha_1$ alone? However, I didn`t restrict the solution to just a single $\alpha$, I can adjust all $\alpha$'s. Is there any solution then?2011-06-30
  • 0
    It is possible normalize by adjusting one coefficient alone, but not always. It depends on how the boxes and the coefficients interact. If you are allowed to change all the coefficients, then just divide by $\|F\|$. If you have all the parameters available, you can try each one and then two etc.2011-06-30
  • 0
    I can adjust all coefficients... So, should I normalize all $\frac{\alpha_i}{\|F\|}$? I tried, however this really doesn't work... btw: What exactly do you mean by interaction between boxes and coefficients?2011-06-30
  • 0
    Not sure what you mean because $F/\|F\|$ always has norm $1$.2011-06-30
  • 0
    Yes, $\frac{F}{\|F\|}$ has always norm equal to 1, however I need to normalize it by $\alpha$'s (and as I said, $F$ = $\sum_{i=0}^{i=N}\alpha_ib_i$)... I understand, that it sounds strange, however it really doesn't work...2011-06-30
  • 0
    I guess I am not understanding what you are saying: Isn't $$\frac{1}{\|F\|}\sum \alpha_i b_i=\sum \frac{\alpha_i}{\|F\|} b_i$$?2011-06-30
  • 0
    Of course it is... that's why I'm saying, that it's strange, that it doesn't work... perhaps, some troubles with rounding, etc... I have to re-check my code again2011-06-30
  • 0
    You should be OK. It seems that I solved a more difficult problem than you asked but it was interesting and not something I normally would think of doing.2011-06-30
  • 0
    Exactly, you took the harder way :) however, thank you for your help... it seems that there was some matlab stuff again... :/ btw may I have one more question? how should I remove the DC component of $F$ (mean) from $\alpha$'s coefficients? I mean $F - mean(F) = \sum\alpha_ib_i - mean(F) = \sum (\alpha_i - ???)b_i$2011-06-30