3

I was reading these slides about Bag of Features (BoF). At slide 23 you can read:

each image is represented by a vector, typically 1000-4000 dimension, normalization with L1/L2 norm

What does the bold phrase means?

Community
  • 1
user6321
  • 389
  • 3
  • 12
  • I know what that L2 Eucledian distance is. I don't know what **normalize an histogram with such a norm means** – user6321 Jul 20 '16 at 13:41
  • I just noticed that the title is incompleate, I'm sorry for that – user6321 Jul 20 '16 at 13:41
  • 1
    @Tim and I answered your previous question, and now you are bringing a new question. Really, you shouldn't post updates. Post these as new questions instead. – Firebug Jul 20 '16 at 14:41
  • You're right. If you're still interested to answer, look at [this](http://stats.stackexchange.com/questions/224757/why-should-we-normalized-bag-of-features-histograms) question. – user6321 Jul 20 '16 at 15:08

2 Answers2

3

$L_p$ normalization is actually described in Wikipedia that quotes Dalal and Triggs (2005)

Dalal and Triggs explored four different methods for block normalization. Let $v$ be the non-normalized vector containing all histograms in a given block, $\|v\|_k$ be its $k$-norm for $k={1,2}$ and $e$ be some small constant (the exact value, hopefully, is unimportant). Then the normalization factor can be one of the following:

L2-norm: $f = {v \over \sqrt{\|v\|^2_2+e^2}}$

(...)

L1-norm: $f = {v \over (\|v\|_1+e)}$

L1-sqrt: $f = \sqrt{v \over (\|v\|_1+e)}$

So $L_p$ normalization of histograms in fact relates to using $L_p$ norms to normalize vectors.

By "dimensions" authors mean the "length" of vectors.

Dalal, N., & Triggs, B. (2005). Histograms of oriented gradients for human detection. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) (Vol. 1, pp. 886-893). IEEE.

Community
  • 1
Tim
  • 108,699
  • 20
  • 212
  • 390
  • Thanks for your answer. Ok, should be unimportant, but some suggestion about the value of $e$? – user6321 Jul 20 '16 at 14:35
  • Please, look also at my **UPDATE** – user6321 Jul 20 '16 at 14:39
  • 2
    @user6321 you **changed** your question to different one - please do not to that. You should rather accept one of the answers (it they answer your initial question) and start a **new** question. – Tim Jul 20 '16 at 14:45
  • You're right. If you're still interested to answer, look at [this](http://stats.stackexchange.com/questions/224757/why-should-we-normalized-bag-of-features-histograms) question. – user6321 Jul 20 '16 at 15:08
  • 1
    @user6321 thanks :) This makes this site much better organized and in fact makes you **more** likely to receive answer to the new question because people may be less prone to look at edited question then to check the new question (such new question would be also longer visible on the list of new questions comparing to the edited one). – Tim Jul 20 '16 at 15:10
  • You're welcome :D Should [this](http://stats.stackexchange.com/questions/224764/bag-of-features-why-the-distance-between-two-histograms-of-the-same-image-is-di) question be posted on stackoverflow (since it's about programming)? – user6321 Jul 20 '16 at 16:22
1

Well, if I had to guess what the slide is referring to:

  • $L_{2}$ normalization $$x_i'=\frac{x_i}{\|x\|_2}=\frac{x_i}{\left(\sum_j{x_j^2}\right)^{1/2}}$$

  • $L_{1}$ normalization $$x_i'=\frac{x_i}{\|x\|_1}=\frac{x_i}{\sum_j{|x_j|}}$$

The $L^{p}$ norm is given by $\|x\|_{p}=\sqrt[p]{\sum_i|x_i|^{p}}, p \in \mathbb{R}$ (link).

Firebug
  • 15,262
  • 5
  • 60
  • 127
  • I'm sorry, but I don't understand your annotation. $x_i$ is a the i-th vector? Or is it the i_th dimension of vector x? – user6321 Jul 20 '16 at 13:53
  • Is it a *guess* or an answer? – Tim Jul 20 '16 at 13:55
  • @Tim it's an answer, because that's the definition of the $L^{p}$ norm, but it's a guess because I'm not sure that's what the slide is referring to. – Firebug Jul 20 '16 at 13:57
  • @user6321 $x_i$ is the $i$-th position of the $x$ vector, yes. See the denominator is the norm I refer to. – Firebug Jul 20 '16 at 13:58
  • 1
    An answer. Actually, it is the same as used in loss-regularization techniques for example. Of course, in other fields, other L-norms exists (say, more general definitions), but regarding ML this is the commonly used one. – Mayou36 Jul 20 '16 at 14:01
  • Ok, I hink that there was an error in the answer before the editing :) – user6321 Jul 20 '16 at 14:05
  • @user6321 no, there wasn't, I just clarified the norm in the denominator and notation, no other modifications. – Firebug Jul 20 '16 at 14:10
  • Please, look also at my **UPDATE** – user6321 Jul 20 '16 at 14:39