[Solved]: Number of different output labels in Local Binary Pattern

Problem Detail: 

I'm studying about Local Binary Pattern and I'm having trouble understanding the following part about the number of output labels for binary patterns from Computer Vision using Local Binary Patterns, by Pietikäinen et al. (2011):

Another extension to the original operator uses so called uniform patterns [53]. For this, a uniformity measure of a pattern is used: $U$ ("pattern") is the number of bitwise transitions from 0 to 1 or vice versa when the bit pattern is considered circular. A local binary pattern is called uniform if its uniformity measure is at most 2. For example, the patterns 00000000 (0 transitions), 01110000 (2 transitions) and 11001111 (2 transitions) are uniform whereas the patterns 11001001 (4 transitions) and 01010011 (6 transitions) are not. In uniform LBP mapping there is a separate output label for each uniform pattern and all the non-uniform patterns are assigned to a single label. Thus, the number of different output labels for mapping for patterns of $P$ bits is $P(P-1)+3$. For instance, the uniform mapping produces 59 output labels for neighborhoods of 8 sampling points and 243 labels for neighborhoods of 16 sampling points.

I don't understand why the number of different LBP output labels is $P(P-1) + 3$. Could someone explain why?....

Thnx for any help =)

Update: I think I have some idea already :) I included an example from my book:

Asked By : jjepsuomi

Answered By : David Richerby

A pattern with uniformity measure exactly 2 is determined by: the value $b$ of bit 0, the position $i>0$ of the first bit that is different from bit 0 and the position $j$ of the first bit after the $i$th that is different from bit $i$. (We may have $j=0$, for example in the pattern 00001111, which has $b=0$, $i=4$, $j=0$.) How many choices are there for the triple $(b,i,j)$? Clearly, there are two choices for $b$. For $i$ and $j$, there are $\tfrac12(P-1)(P-2)$ choices with $i<j$ and $P-1$ choices where $j=0$. Thus, the total number of choices for $i$ and $j$ is $$ \tfrac12(P-1)(P-2) + P-1 = \tfrac12P(P-1)\,.$$

To that, you need to add three more labels: all zeroes, all ones and the label for all patterns of uniformity measure strictly more than 2.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19844