Counting local n-ary patterns

Despite the fact that image descriptors based on the statistical distribution of local patterns are very common tools, most of their mathematical underpinnings have been largely overlooked. Among them, the rigorous determination of the number of possible patterns that can arise from a given neighbourhood and kernel function – particularly when invariance under group actions (e.g. rotations and/or reflections) is taken into account – has received little or no attention in the literature. In this note we address the problem of counting local patterns in a rigorous way. We provide exact formulas for the number of the possible directional, rotation- and reflection-invariant patterns generated by neighbours of n points over alphabets of k symbols. Variations on this scheme such as rank and uniform patterns are considered, and direct applications to a number of common descriptors (e.g. Local Binary Patterns, Texture Spectrum and Full Ranking) are also presented.