# Novel histograms kernels with structural properties

Jyrko Correa-Morris, Yoanna Martínez-Díaz, Noslen Hernández, Heydi Méndez-Vázquez

► To cite this version:

Jyrko Correa-Morris, Yoanna Martínez-Díaz, Noslen Hernández, Heydi Méndez-Vázquez. Novel histograms kernels with structural properties. Pattern Recognition Letters, 2015, 68, pp.146-152. 10.1016/j.patrec.2015.09.005. hal-04804108

HAL Id: hal-04804108

https://hal.science/hal-04804108v1

Submitted on 26 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Novel Histograms Kernels with Structural Properties

Jyrko Correa-Morrisª, Yoanna Martínez-Díazᵇ, Noslen Hernándezᵇ, Heydi Méndez-Vázquezᵇ

ªMiami Dade College, Miami, USA

ᵇAdvanced Technologies Application Center (CENATAV), Havana, Cuba

## ABSTRACT

This paper introduces a new similarity measure for comparing histograms, named *Weighted Distribution Matching*, which bases the comparison not only in the specific bin values but also in the shape of the histograms. It is proved that the proposed similarity is a conditionally positive definite kernel. The space where histograms lie is studied, and some intuitively desirable structural properties are introduced. The most representative measures of the state of art were compared on the basis of these properties. Experiments conducted on face recognition and image retrieval, validate the proposal.

## 1. Introduction

A histogram is essentially a simple discrete representation of a data distribution that shows how data are piled up, and which of its values occur more frequently than others. That is, a histogram is built by placing the frequency of values in measurements made in a set of samples in a predefined order. Every frequency represented in a histogram is called a bin. In many real applications, the values of measurements range over a large domain (e.g., a continuous domain), and in this case, a quantization is required in order to reduce it to a smaller set of values.

Histograms of visual features, like pixel intensity values, gradient orientations, texture patterns or visual words, have been used in many computer vision tasks (Kim and Billard (2013); Pele and Werman (2010); Tan and Triggs (2007)). Comparing histograms according to their structural resemblance is a common challenge to these applications. Several similarity measures have been proposed in the literature to solve this problem, which can be divided into two classes: *bin-to-bin* and *cross-bin* measures.

Bin-to-bin measures compare only the content of corresponding histogram bins. Since bin values are assumed to be independent of each other, histograms are considered as vectors. The typical measure on this class is the Minkowski distance, induced by the $L_p$ norm in Euclidean spaces, and widely used for the particular cases $p = 1$ and $p = 2$. Also, following a probabilistic approach where histograms are considered empirical estimates of probability density functions (pdfs), measures for comparing pdfs have been adapted for histograms.

This is the case of Bhattacharyya distance (Kailath (1967)), Matusita distance (Matusita (1955)), Kullback-Leibler divergence (Shore and Gray (1982)), and Jeffrey divergence (Puzicha et al. (1997)). Other well known bin-to-bin measures are the $\chi^2$-distance, justified by statistics, and the Histogram Intersection similarity (Swain and Ballard (1991)), which was proved to be a kernel for histograms (Barla et al. (2003)).

One advantage of bin-to-bin measures is its computational simplicity. That is why they are useful to handle large datasets involving a lot of comparisons. However, the main disadvantage of this kind of measures is that they ignore the correlation between neighboring bins. This is a drawback when working with histograms built from the so-called ordinal and modulo measurements, in which there exists an order (and consequently, a relation) between measurement levels (Cha and Srihari (2002)). All bin-to-bin measures have the shuffling invariance property, and this naturally implies the level independency. Besides, in practice, histograms suffer from distortion due to shape deformation, light changes, noise, as well as quantization problems; leading to nonaligned histograms domains. Hence, it is necessary to compare bins at different locations, which can not be done with a bin-to-bin measure. To address these limitations, the cross-bin measures have been proposed.

Cross-bin measures compare both corresponding and noncorresponding bins. The Quadratic-Form distances (Hafner et al. (1995); Pele and Werman (2010)) model the similarity relationships between bins through a similarity matrix. Another form of cross-bin measure is the Earth Mover's Distance (EMD), which calculates the minimal cost that must be paid to transform one histogram into another and models cross-bin re-
lations using *ground distances* (Rubner et al. (2000)). Two special cases of EMD are the Minimum Difference of Pair Assignment distance (Cha and Srihari (2002)), and the Match distance (Shen and Wong (1983)). Other proposals on this class are the Kolmogorov-Smirnov distance (Geman et al. (1990)), the Diffusion distance (Ling and Okada (2006)), the Neighbor-Bank Projection based measures (Kamarainen et al. (2003)), and Peak Matching measure (Strelkov (2008)).

Although cross-bin measures carry out a more reasonable histogram comparison, they present a high computational cost. Several improvements have been proposed to address this problem (Ling and Jacobs (2007); Pele and Werman (2008, 2009); Shirdhonkar and Jacobs (2008)), but they remain more computational demanding than bin-to-bin measures. Various approaches exploiting the advantages of both bin-to-bin and cross-bin measures have emerged; for instance, the Variable Bin Size distance (Ma et al. (2010)) and the Hierarchical Semantic-Based distance (Kurtz et al. (2013)).

This paper introduces a new similarity measure to compare histograms, named *Weighted Distribution Matching*. It inherits the low computational cost of bin-to-bin measures and takes into account the relationship between consecutive bins from the same histogram, being not shuffling invariant. To achieve this, we consider histograms as approximations of empirical distributions and compare them across their *peak distribution*, feature highly related to the histogram shape. We analyze the space to which histograms naturally belong and, define some desired properties that measures for comparing histograms should fulfill. We prove that the proposed measure is a conditionally positive definite kernel (Scholkopf and Smola (2001)), which is appropriated to be used with kernel-based methods.

The rest of the paper is organized as follows. Section 2 states useful definitions and some simple and intuitive structural properties. Section 3 presents the proposed *Weighted Distribution Matching* similarity. Section 4 is devoted to the experimental results. Conclusions and future works are given in Section 5.

## 2. Histogram space and structural properties

Let us begin by noting that a histogram may be characterized by two fundamental aspects: (1) the distribution of peaks, which encodes the information about the shape of the histogram and distinguishes it from a vector; and (2) the specific information at each bin. The following definition formalizes this idea.

**Definition 1.** Let $X$ be an ordered set of $m$ categories. A histogram on $X$ is a pair $h = (b_h, d_h)$ of $m$-tuples such that the $i$th component $b_h(i)$ of $b_h$ stores the number of observations that fall into the $i$th category of $X$, and the $i$th component $d_h(i)$ of $d_h$ is either $+$, $-$, or $0$, depending on whether there is an increase, a decrease or an equality, respectively, when passing from $b_h(i)$ to $b_h(i+1)$. The vector $b_h$ is called the $m$-tuple of bins of $h$, and $d_h$ the peak distribution of $h$. From now on, $H(X)$ denotes the set of all histograms that can be built from $X$.

This definition establishes a histogram as a structured representation and therefore, it is worthy to define when a histogram is considered as a substructure of another one.

**Definition 2.** We say that $h$ is a sub-histogram of $h'$ (in notation $h \le h'$) if and only if (1) for all $1 \le i \le m$, $b_h(i) \le b_{h'}(i)$; and (2) $d_h = d_{h'}$. That is, $h$ is a sub-histogram of $h'$ when they have the same peak distribution, and each bin of $h'$ is greater than the corresponding bin in $h$ (see Fig. 1).

<figure><img src="image_2.png" /><figcaption>Fig. 1: $h_1$ is a sub-histogram of $h'$ while $h_2$ is not</figcaption></figure>

The binary relation $\le$ is reflexive, antisymmetric and transitive. Hence, $(H(X), \le)$ is a partially ordered set. When we endow a set with an order relation, we do nothing but putting a spatial organization or arrangement of its elements. Thereby, an order relation naturally induces a notion of proximity among the elements of a set. So, in the specific context of histogram comparison, considering that $\le$ is based on the structural resemblance between two histograms, it is completely reasonable to expect that a “good” measure for comparing histograms be compatible with this order relation. The properties introduced below are intended to formalize this notion of compatibility. Let $\Gamma$ denote a similarity measure for histograms.

**Collinear Monotonicity (CM):** If $h \le h' \le h''$, then $\Gamma(h, h') \ge \Gamma(h, h'')$. The equality holds if and only if $h' = h''$.

This property asserts that if a histogram $h$ is gradually transformed by increasing the values of its bins without affecting its peak distribution, then the similarity between the initial histogram $h$ and the resulting histogram decreases as the amount of transformation increases. Such a behavior completely matches our visual perception as shown in Fig. 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Three ordered histograms: $h \le h_1 \le h_2$.</figcaption></figure>

**Dual Collinear Monotonicity (DCM):** If $h \le h' \le h''$, then $\Gamma(h'', h') \ge \Gamma(h'', h)$. The equality holds if and only if $h = h'$.

This property is the dual of the previous one. The difference lies in the fact that the comparison is done in the other sense: the values of the bins of the original histogram are decreased.

These properties require that the transformation performed to the original histogram preserve the peak distribution; i.e., the histograms being compared are assumed to have the same peak distribution. Thus, the comparison heavily relies on the specific values of the bins. The next properties are aimed to stand out the role of the peak distribution in the comparison. To facilitate access to them, we shall introduce some terminology.
A function $t: H(X) \to H(X)$ defined by $t(h) = (b_{t(h)}, d_{t(h)})$, where $b_{t(h)}(i) = b_h(i) + n_i$, $n_i \in \mathbb{Z}$, is called histogram transformation. A point here is the preservation of the structure. Given two histogram transformations $t$ and $t'$, we say that $t$ preserves the peak distribution of $h$ more than $t'$ if $d_{t(h)}$ and $d_h$ have more equal components than $d_{t'(h)}$ and $d_h$. That is, $\#\{i : d_{t(h)}(i) = d_h(i)\} \ge \#\{i : d_{t'(h)}(i) = d_h(i)\}$. In particular, $t$ preserves the structure of $h$ if $\#\{i : d_{t(h)}(i) = d_h(i)\} = m$, the number of bins of $h$. (Note that this kind of histogram transformations are the required by the two first properties.)

It is not difficult to see that given two arbitrary histograms $h$ and $h'$, we can always find a third histogram $h \perp h'$ whose resemblance to any of the two original histograms is greater or equal than the existing between them. One can think of $h \perp h'$ as an intermediate histogram placed between $h$ and $h'$. Since the proximity between two histograms depends on both the peak distribution and the values at bins, we construct $h \perp h'$ by ensuring that it has the same peak distribution as $h$ and the minor difference with the corresponding bins of $h'$. (In general, $h \perp h' \neq h' \perp h$.) We build $h \perp h'$ by properly performing transformations in $h'$. That is, $h \perp h' = t(h')$, where $t$ is the histogram transformation that modifies the $i$th bin of $h'$, by adding the quantity $n_i \in \mathbb{Z}$, i.e., $b_{t(h')}(i) = b_{h'}(i) + n_i$, in a way that $\sum_{i=1}^m |n_i|$ is minimized subject to: a) $t(h')$ has the same peak distribution as $h$; and b) for each $1 \le i \le m$, $|b_{h'}(i)+n_i-b_h(i)| \le |b_{h'}(i)-b_h(i)|$.

The minimization of $\sum_{i=1}^m |n_i|$ ensures that we are transforming $h'$ as little as possible to hold conditions a) and b), and thus, $h \perp h'$ retains much of $h'$. In turn, conditions a) and b) guarantee that $h \perp h'$ is also very similar to $h$. We call $h \perp h'$ reflection of $h'$ through $h$. Fig. 3 sheds some light on the matter.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Two histograms $h$ and $h'$ and their reflection $h \perp h'$.</figcaption></figure>

Note that $h$ and $h'$ have different peak distributions and $h \perp h'$ is visually more similar to $h$ than $h'$.

**Reflection Predominance (RP):** For any histograms $h$ and $h'$, $\Gamma(h, h \perp h') \ge \Gamma(h, h')$.

Our last property is even more focused on the role of peak distribution than the previous one.

**Consistency with Peak Distribution (CPD):** Let $h$ be a histogram, and $t$ and $t'$ histogram transformations such that for each $1 \le i \le m$, $|b_h(i) - b_{t(h)}(i)| = |b_h(i) - b_{t'(h)}(i)|$. If $t$ preserves (strictly) more the peak distribution as $h$ than $t'$, then $\Gamma(h, t(h)) > \Gamma(h, t'(h))$.

Let us explain with an example the intuition behind CPD. Suppose we take an arbitrary histogram $h$ (we will show this example with normalized histograms), and for each bin $b_h(i)$, we consider a real number $0 \le n_i \le b_h(i)$ to construct two histogram transformations $t$ and $t'$ that affect the $i$th bin $b_h(i)$ of $h$

by either adding or subtracting $n_i$. For instance, suppose $b_h = (0.15, 0.18, 0.30, 0.22, 0.15)$, $n_1 = 0.10$, $n_2 = 0.04$, $n_3 = 0.15$, $n_4 = 0.03$, and $n_5 = 0.04$; and $t(h) = b_h + (-n_1, -n_2, n_3, n_4, -n_5)$ and $t'(h) = b_h + (n_1, n_2, -n_3, -n_4, n_5)$. Observe that the unique difference between $t$ and $t'$ lies in the signs that appear in front of the $n_i$'s and so, each bin of $h$ differs the same from the corresponding bins in $t(h)$ and $t'(h)$. This way of constructing $t$ and $t'$ ensures that the part of the comparison that depends on bins values is controlled, and suggests that what makes $h$ more similar to either $t(h)$ or $t'(h)$ is the peak distribution.

Fig. 4 shows the histograms given in the example mentioned above. Notice that $t$ preserves more the peak distribution of $h$ than $t'$. This will make $t(h)$ more similar to $h$ than $t'(h)$ (according to CPD), which matches our visual perception.

<figure><img src="image_5.png" /><figcaption>Fig. 4: Histogram transformations, $t(h)$ and $t'(h)$, such that $|b_h(i) - b_{t(h)}(i)| = |b_h(i) - b_{t'(h)}(i)|$.</figcaption></figure>

A toy example (see Table 1) using these histograms shows how measures such as $L_1$, $L_2$, Histogram Intersection $HI$, the Quadratic Form $QF$ and $EMD$, consider $t(h)$ and $t'(h)$ equally similar to $h$. $\chi^2$ and the quadratic-Chi Form $QCN$ fail to match the visual perception and assert that $t'(h)$ is more similar to $h$ than $t(h)$. The Weighted distribution matching (WDM) (to be introduced later) gives a response in correspondence with our intuition.

<table><caption>Table 1: $\Gamma(h, t(h))$ vs. $\Gamma(h, t'(h))$</caption><thead><tr><th>Γ</th><th>Γ(h, t(h))</th><th>Γ(h, t'(h))</th><th>Most similar</th></tr></thead><tbody><tr><td>L<sub>1</sub></td><td>0.36</td><td>0.36</td><td>tie</td></tr><tr><td>L<sub>2</sub></td><td>0.19</td><td>0.19</td><td>tie</td></tr><tr><td>HI</td><td>0.82</td><td>0.82</td><td>tie</td></tr><tr><td>QF</td><td>0.15</td><td>0.15</td><td>tie</td></tr><tr><td>EMD</td><td>0.29</td><td>0.29</td><td>tie</td></tr><tr><td>χ<sup>2</sup></td><td>0.09</td><td>0.08</td><td>t'(h)</td></tr><tr><td>QCN</td><td>0.16</td><td>0.14</td><td>t'(h)</td></tr><tr><td>WDM</td><td>1.49</td><td>-2.51</td><td>t(h)</td></tr></tbody></table>

### 3. Weighted Distribution Matching measures

This section introduces a family of histograms similarities whose members satisfy all the structural properties.

**Definition 3 (Weighted Distribution Matching).** The Weighted Distribution Matching measures for histograms is a function $WDM: H(X) \times H(X) \to \mathbb{R}$ given by:

$$WDM(h, h') = \sum_{i} (\omega_{i}(h, h')\delta_{i}(h, h') - v_{i}(h, h')(1 - \delta_{i}(h, h'))), \quad (1)$$
where for each $1 \le i \le m$, $\delta_i(h, h')$ is equal to 1 if $d_h(i) = d_{h'}(i)$ and equal to 0 otherwise, and $\omega_i$ and $v_i$ are positive and negative weight functions on $H(X)$, respectively.

Roughly speaking, the definition says that WDM computes the similarity between two histograms $h$ and $h'$ by checking its shape in common. At the $i$th position, if $h$ and $h'$ have the same peak distribution type (e.g., in both histograms the $i$th bin is greater than the $(i+1)$th bin), then WDM adds a reward weight $\omega_i(h, h')$; otherwise WDM subtracts a penalty weight $v_i(h, h')$. Before going to a formal definition of weight functions, we will rely on Fig. 5 for a better understanding.

<figure><img src="image_6.png" /><figcaption>Fig. 5: Possibilities at the $i$th bin.</figcaption></figure>

In Fig. 5, suppose that we are independently comparing $h$ with $h_1$ and $h_2$. Since the peak distribution of these histograms is the same, WDM adds a reward weight in both cases (by virtue of the definition), namely $\omega_i^1$ and $\omega_i^2$, however $h_1$'s bins values differs less from the corresponding on $h$ than those of $h_2$ do. Hence, $\omega_i^1$ must be greater than $\omega_i^2$. Thus, we define a positive weight function as a function $\omega_i : H_i(X) \times H_i(X) \to \mathbb{R}$ such that for all $b_h(i), b_{h'}(i) \in H_i(X)$: (i) $0 < \omega_i(b_h(i), b_{h'}(i)) \le 1$, and (ii) $\omega_i(b_h(i), b_{h'}(i)) = 1$, where $H_i(X)$ is the set of all possible values for $i$th bin of any histogram in $H(X)$.

Now, when comparing $h$ with histograms $h_3$ and $h_4$, both of them have peak distribution different to $h$, so WDM penalizes the comparison by subtracting in both cases a penalty weight, say $v_i^3$ and $v_i^4$. Since $h_4$ deviates more from $h$ at the $i$th bin than $h_3$, it is natural to demand that $v_i^3 < v_i^4$. Following this reasoning, we define a negative weight function as a function $v_i : H_i(X) \times H_i(X) \to \mathbb{R}$ such that for all $b_h(i), b_{h'}(i) \in H_i(X)$: (i) $0 \le v_i(b_h(i), b_{h'}(i)) < 1$, and (ii) $v_i(b_h(i), b_{h'}(i)) = 0$.

Simple examples of positive and negative weight functions are the exponential decay $\omega_i(b_h(i), b_{h'}(i)) := \exp(-|b_h(i) - b_{h'}(i)|/\sigma)$, and the exponential recovery $v(x) = 1 - \exp(-|b_h(i) - b_{h'}(i)|/\sigma)$ with parameter $\sigma$, respectively. Other examples can be obtained by replacing the exponential decay by a strictly decreasing monotonic function $f : \mathbb{R}^+ \to [0, 1]$ with $f(0) = 1$ and the exponential recovery by a strictly increasing monotonic function $g : \mathbb{R}^+ \to [0, 1]$ with $g(0) = 0$. Besides, we can use the minimum and maximum between bin values: $\omega_i(h, h') := \min\{b_h(i), b_{h'}(i)\}/\max\{b_h(i), b_{h'}(i)\}$, and $v_i(h, h') := 1 - (\min\{b_h(i), b_{h'}(i)\}/\max\{b_h(i), b_{h'}(i)\})$. In practice, these last functions tend to have a less efficient behavior; however, no parameters are involved.

We shall see that some members of this family are conditionally positive definite functions (Scholkopf and Smola (2001)), property that allows us to use these measures in algorithms that

compute the similarity through norms arising from a dot product as it is the case of SVM, PCA, Parzen Windows.

**Theorem 1.** Suppose that for each $i \in \{1, 2, \dots, m\}$, $v_i + \omega_i = 1$ and $\omega_i$ is a conditionally positive definite (cpdk). Then, WDM is also cpdk.

The implementation of WDM is very easy and its computation time is linear in the number of bins $m$.

**Algorithm 1: Pseudo-code for WDM**

**Data:** Histograms $h, h'$ of $m$ bins.

**Result:** A similarity value, $wdm$.

**begin**

**for** $i = 1$ **to** $m$ **do**
        peakh = $b_h(i) - b_h(i + 1)$;
        peakh' = $b_{h'}(i) - b_{h'}(i + 1)$;
        **if** sign(peakh) == sign(peakh') **then**
            w = PositiveWeight($b_h(i), b_{h'}(i)$);
            wdm = wdm + w;
        **else**
            v = NegativeWeight($b_{h'}(i), b_{h'}(i)$);
            wdm = wdm - v;

The following proposition shows that WDM satisfies all the structural properties for an extensive class of weight functions.

**Proposition 1.** Let $f_i : \mathbb{R}^+ \to [0, 1]$ be a strictly decreasing monotonic functions such that $f_i(0) = 1$, $1 \le i \le m$. Define $\omega_i(b_h(i), b_{h'}(i)) := f_i(|b_h(i) - b_{h'}(i)|)$ and $v_i(b_h(i), b_{h'}(i)) = 1 - \omega_i(b_h(i), b_{h'}(i))$. Then WDM satisfies all of the four structural properties.

The proofs of theoretical results appear in the Supplementary Material.

Table 2 summarizes the fulfilment of the introduced properties for the most representative measures of the state of art.

<table><caption>Table 2: Fulfilment of properties for the different measures</caption><thead><tr><th></th><th>WDM</th><th>L<sub>q</sub></th><th>χ<sup>2</sup></th><th>H<sub>β</sub></th><th>JD</th><th>QF<sub>Λ</sub></th><th>EMD</th><th>Match</th><th>KS</th><th>MDPA</th></tr></thead><tbody><tr><td>CM</td><td>✓</td><td>✓</td><td>✓</td><td>x</td><td>✓</td><td>✓</td><td>x</td><td>✓</td><td>✓</td><td>x</td></tr><tr><td>DCM</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>x</td><td>✓</td><td>✓</td><td>x</td></tr><tr><td>RP</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>x</td><td>x</td><td>x</td><td>✓</td></tr><tr><td>CPD</td><td>✓</td><td>x</td><td>x</td><td>x</td><td>x</td><td>x</td><td>x</td><td>x</td><td>x</td><td>x</td></tr></tbody></table>

Note also that the structural properties are also valid for dissimilarity measures if we reverse the corresponding inequality.

## 4. Experimental Evaluations

The performance of WDM is evaluated on two popular computer vision tasks: face recognition and content-based image retrieval, where histogram-based descriptors have been traditionally used. There is no attempt to beat the state of art performance on these applications; such purpose is out of the scope of this paper. Our goal here is to fairly compare WDM with other (dis)similarity measures.
## 4.1. Face recognition experiments

We conducted face recognition experiments on both verification and identification tasks.

As a histogram representation, the Local Binary Patterns (LBP) (Ahonen et al. (2006)) and the Local Ternary Patterns (LTP) (Tan and Triggs (2007)) were used. Both descriptors were computed using a neighborhood of eight pixels in a radius of two (8; 2) and the threshold parameter of the LTP operator was set to 0.09 as in Tan and Triggs (2007).

### 4.1.1. Face verification on Life in the Wild (LFW) database

The LFW database (Huang et al. (2007b)) contains 13,233 face images of 5,749 different individuals. It is an extremely challenging dataset composed by face images captured in unconstrained environments with large variations in pose, expression, lighting, clothing, hairstyles and background.

We considered the “image-restricted setting with no outside data” protocol and used the face images aligned by funneling (Huang et al. (2007a)). The evaluation was done through a 10-fold cross validation procedure using the 10 splits provided on the View 2 dataset where each split consists of 600 image pairs randomly selected from the original image set, being 300 pairs of images of the same person (genuine) and the other pairs of images from different persons (impostors). For each pair, a matching value is computed using a (dis)similarity measure over their representations. Such matching values are used to train a linear Support Vector Machine classifier that will be responsible for determining whether a given matching value corresponds to a genuine or an impostor.

All images were photometrically normalized following the preprocessing sequence of Tan and Triggs (2007) and cropped to 81 × 150 pixels and divided into 40 sub-regions of 20 × 15 to extract LBP and LTP features (Ruiz-del Solar et al. (2009)) of 2360 (40 × 59) and 4720 (40 × 118) bins, respectively.

We tested *WDM* using the exponential (*WDM*<sup>σ</sup>) and the minimum-maximum (*WDM*<sup>mmm</sup>) based weight function. We compare to *χ*<sup>2</sup> and Histogram Intersection, which are the measures most frequently used in face recognition. Other measures such as *L*<sub>1</sub>, *L*<sub>2</sub> and Jeffrey Divergence were also included in the comparison. We also tried cross-bin distances such as Match, Kolmogorov-Smirnov and *EMD*, but the results were rather poor and not included in the comparison. The selection of *σ* in *WDM*<sup>σ</sup> is explained in the supplementary material.

The results are listed in Table 3 in terms of the estimated mean classification accuracy (û) and the standard error of the mean (*S*<sub>E</sub>); following the database protocol. As can be seen, *WDM*<sup>σ</sup> achieves the best results for both LBP and LTP descriptors, performing better than *WDM*<sup>mmm</sup>, which was expected in view of the properties of its weight functions. Both variants outperform the rest of the evaluated measures for LTP histograms; and for LBP, although the performance of *WDM*<sup>mmm</sup> decreases a little bit, it is still comparable to the other measures. Similar to the other measures, *WDM* shows to be more discriminative for LTP than for LBP histograms.

The performance suggests that the criteria in which our proposal base the comparison is useful when this kind of descriptors is used for face recognition. Although in terms of û,

<table><caption>Table 3: Results in LFW database in terms of û and *S*<sub>E</sub>.</caption><thead><tr><th></th><th>û ± S<sub>E</sub> (LBP)</th><th>û ± S<sub>E</sub> (LTP)</th></tr></thead><tbody><tr><td>χ<sup>2</sup></td><td>0.6568 ± 0.0071</td><td>0.6538 ± 0.0073</td></tr><tr><td>HI</td><td>0.6530 ± 0.0055</td><td>0.6557 ± 0.0068</td></tr><tr><td>L<sub>1</sub></td><td>0.6425 ± 0.0166</td><td>0.6520 ± 0.0063</td></tr><tr><td>L<sub>2</sub></td><td>0.6435 ± 0.0071</td><td>0.6407 ± 0.0084</td></tr><tr><td>JD</td><td>0.6310 ± 0.0313</td><td>0.6551 ± 0.0063</td></tr><tr><td>WDM<sup>σ=6</sup></td><td>0.6628 ± 0.0052</td><td>0.6711 ± 0.0040</td></tr><tr><td>WDM<sup>mmm</sup></td><td>0.6441 ± 0.0069</td><td>0.6673 ± 0.0063</td></tr></tbody></table>

*WDM*<sup>σ</sup> outperforms just by about one percent *χ*<sup>2</sup> and *HI*, this means that more than 100 image pairs are correctly classified by our method and misclassified by the others. Some examples of these image pairs are shown in Fig. 6.

<figure><img src="image_7.png" /><figcaption>Fig. 6: Examples of (a) genuine and (b) impostor pairs of images corrected classified by *WDM*<sup>σ</sup> but misclassified by both *χ*<sup>2</sup> and *HI* using LTP histograms.</figcaption></figure>

Since better results have been obtained using model learning based methods instead of distance thresholding approaches, we use the simplest one-shot learning (OSL) strategy (Wolf et al. (2008)) to improve the performance. This strategy learns a model of the person in the first image of the pair and tries to classify the second image. Then, the roles of the images are replaced and the procedure repeated. A training set, A, containing face images as negative examples during the OSL, and a training set, B, containing matching and non-matching pairs to learn the decision threshold as before, are required.

Given a pair of images represented by LTP descriptors, we train two SVM classifiers by using either one of the two images as the positive example, and the set A as the negative examples. Afterwards, each SVM classifier is applied to the other image of the pair and a score is obtained. These two classification scores are averaged to take this value as a matching score. This process is repeated to all training image pairs of set B, and a threshold on the obtained scores is also learned using a linear SVM classifier. For each repetition, we use one of the remaining nine splits to construct the set A and eight for the set B.

For learning the underlying one-shot classifiers we used SVM with *WDM*<sup>σ</sup> and *WDM*<sup>mmm</sup>, and a linear kernel. The obtained results are shown in Table 4. Notice that the inclusion of the OSL strategy improves significantly the previous results of LTP descriptor, and in addition, both variants of *WDM* outperform the linear kernel in the SVM classifier.
<table><caption>Table 4: Results in LFW in terms of ū and $S_E$, using OLS.</caption><thead><tr><th></th><th>û ± S<sub>E</sub></th></tr></thead><tbody><tr><td>LTP - OSL + linear SVM</td><td>0.7283 ± 0.0048</td></tr><tr><td>LTP - OSL + WDM<sup>σ=2</sup></td><td>0.7306 ± 0.0041</td></tr><tr><td>LTP - OSL + WDM<sup>mm</sup> SVM</td><td>0.7308 ± 0.0043</td></tr></tbody></table>

<table><caption>Table 5: Recognition rates (%) on Entended Yale B Database.</caption><thead><tr><th>(LBP)</th><th>S1</th><th>S2</th><th>S3</th><th>S4</th><th>S5</th></tr></thead><tbody><tr><td>χ<sup>2</sup></td><td>100</td><td>99.78</td><td>99.61</td><td>98.02</td><td>89.77</td></tr><tr><td>HI</td><td>100</td><td>99.78</td><td>99.42</td><td>95.17</td><td>84.87</td></tr><tr><td>L<sub>1</sub></td><td>100</td><td>99.78</td><td>99.42</td><td>95.17</td><td>84.87</td></tr><tr><td>L<sub>2</sub></td><td>100</td><td>99.78</td><td>97.71</td><td>83.55</td><td>59.38</td></tr><tr><td>JD</td><td>100</td><td>99.78</td><td>99.42</td><td>98.02</td><td>90.75</td></tr><tr><td>WDM<sup>σ=2</sup></td><td>100</td><td>100</td><td>99.61</td><td>98.24</td><td>96.07</td></tr><tr><td>WDM<sup>mm</sup></td><td>100</td><td>100</td><td>99.80</td><td>98.24</td><td>94.81</td></tr></tbody></table><table><thead><tr><th>(LTP)</th><th>S1</th><th>S2</th><th>S3</th><th>S4</th><th>S5</th></tr></thead><tbody><tr><td>χ<sup>2</sup></td><td>100</td><td>99.78</td><td>99.61</td><td>98.90</td><td>91.59</td></tr><tr><td>HI</td><td>100</td><td>99.78</td><td>99.61</td><td>98.02</td><td>87.39</td></tr><tr><td>L<sub>1</sub></td><td>100</td><td>99.78</td><td>99.61</td><td>98.02</td><td>87.39</td></tr><tr><td>L<sub>2</sub></td><td>99.11</td><td>99.78</td><td>96.95</td><td>83.77</td><td>59.80</td></tr><tr><td>JD</td><td>100</td><td>99.78</td><td>99.61</td><td>99.34</td><td>92.43</td></tr><tr><td>WDM<sup>σ=2</sup></td><td>100</td><td>100</td><td>99.80</td><td>99.12</td><td>96.49</td></tr><tr><td>WDM<sup>mm</sup></td><td>100</td><td>100</td><td>100</td><td>99.78</td><td>96.49</td></tr></tbody></table>

### 4.1.2. Face identification on the Extended Yale Face B

The Extended Yale Face Database B (Lee et al. (2005)) is a challenging dataset with extremely difficult illumination problems. It contains images of 38 subjects under 64 illumination conditions, usually divided into five subsets according to the angle of the incident illumination. The larger the angle, the more unfavorable the lighting conditions are, thus S1 contains images with minor illumination variations while the most affected ones are in S5. We have used the face image of each subject with the most neutral light source ('A+000E+00') as gallery and all remaining frontal images as probes.

The original cropped images were resized to 120 × 120 pixels and divided into sub-regions of 8 × 8 pixels to obtain LBP and LTP representations. The recognition is performed by a nearest neighbor classifier in the computed feature space using the same (dis)similarity measures tested in the previous section. The Match distance and the Kolmogorov-Smirnov distance achieved again poor results and were not included in the comparison. The value of $\sigma$ for $WDM^\sigma$ was chosen as before, using only the images from the gallery.

The obtained results in terms of recognition rates using both LBP and LTP histograms are shown in Tables 5(a) and 5(b), respectively. It can be seen that the two variants of $WDM$ outperforms the other measures for both representations, achieving $WDM^{mm}$ a very similar performance to $WDM^\sigma$. Note that, for the easier subsets such as S1, S2 and S3; $WDM$ slightly outperforms the other measures, while for the most difficult subsets, it obtains a remarkable difference. For example, compared to $\chi^2$ and $JD$, which obtain good performance, an improvement of about 5% is achieved.

## 4.2. Image Retrieval experiments

Image retrieval experiments were done using the same benchmark as Pele and Werman (2009). It contains 773 landscape images from the Corel database divided into 10 classes. The number of images on each class ranges from 50 to 100.

The benchmark has 5 query images for each class and the 50 nearest neighbors for each query image are recovered. The distance (or the similarity) of each image to the query image and its reflection is computed and the minimum (or maximum) is taken, respectively.

Two SIFT-like descriptors are used to represent the images: SIFT descriptor (Lowe (2004)) and one of its extensions that includes color information in the representation, called colored SIFT (CSIFT) (Pele and Werman (2009)). Both of them were computed globally on the whole image, with 6 × 8 × 8 bins.

Both, $WDM^\sigma$ and $WDM^{mm}$, were compared to several state of art distances that have been previously evaluated on this benchmark. For $WDM^\sigma$, the value of the parameter $\sigma$ was selected as before, using only the query images. We experimented with three $EMD$ variants: (a) $\widehat{EMD}$ with thresholded ground distance, $\widehat{EMD}^{d_T=2}$ (Pele and Werman (2009)), (b) $SIFT_{DIST}$ (Pele and Werman (2008)) and (c) $EMD-L_1$, which is $EMD$ with $L_1$ as ground distance (Ling and Okada (2007)). We also tried the Quadratic-Chi distance type best performing in Pele and Werman (2010), called Quadratic-Chi-Normalized (QCN) and basic distances such as $L_1$ and $L_2$.

The obtained results are presented in Fig. 7, where the curves represent the average performance over the ten classes using different criteria. As in Pele and Werman (2010), we only present the results for the descriptor (SIFT/CSIFT) with which each measure performs better. This figure shows that $WDM^{\sigma=0.02}$ outperforms all other measures. This variant performs better than $WDM^{mm}$, corroborating the importance of reducing the effect of large bins. However, $WDM^{mm}$ presents also an acceptable performance, being quite comparable with some of the other measures.

<figure><img src="image_8.png" /><figcaption>Fig. 7: (a) Average number of relevant images retrieved vs. number of images retrieved and (b) Average precision-recall curves for the different measures</figcaption></figure>

The two variants of $WDM$ achieve better results with SIFT descriptor than with CSIFT. Nevertheless, the results obtained by $WDM$ using exponential based weighted functions and
CSIFT (not shown in the figure) also outperforms all other measures. Some facts may be overlooked when noticing only the average results. For example, $WDM^{σ=0.02}$ performs better than the other measures for almost all the classes. Only for People in Africa and Food this does not happen, which could be due to existing issues like quantization problems that can be handled better by measures like the *EMD* variants.

Fig. 8 shows the retrieval results examples obtained for one Outdoor Buildings query image which appears on the left. Each row represents the four nearest images retrieved ordered from left to right by their similarity to the query image. The first row corresponds to $WDM^{σ=0.02}$ which is the best performing measure. The second and third rows are for $QCN^{1-\frac{d_{T=2}}{2}}$ and $\widehat{EMD}^{d_{T=2}}$ distances respectively.

<figure><img src="image_9.png" /><figcaption>Fig. 8: Retrieval results for one of the query image of the Outdoor Building class.</figcaption></figure>

It is important to note that the proposed similarity measure outperforms not only the bin-to-bin measures involved in the comparison but also the cross-bin ones. This indicates that basing the comparison on the peak distribution matching is an effective criterion.

## 5. Concluding remarks

This paper proposed a new family of similarity measures for histogram comparison called Weighted Distribution Matching (WDM). It bases the comparison not only in the specific bin values but also in the shape of the histograms. WDM is supported by four structural properties formalized in this work. Our proposal was validated in face recognition and image retrieval tasks. The experimental results showed that WDM outperforms several (dis)similarity measures from state of art. All this makes WDM a promising similarity measure for applications that involve histogram comparison. Future works include to explore the performance of WDM with multi-dimensional histograms and its generalization to handle cross-bin comparisons.

## References

* Ahonen, T., Hadid, A., Pietikäinen, M., 2006. Face description with local binary patterns: Application to face recognition. IEEE Trans Pattern Anal Mach Intell 28, 2037–2041.

* Barla, A., Odone, F., Verri, A., 2003. Histogram intersection kernel for image classification, in: ICIP, pp. 513–516.

* Cha, S.H., Srihari, S.N., 2002. On measuring the distance between histograms. Pattern Recogn 35, 1355–1370.

* Geman, D., Geman, S., Graffigne, C., Dong, P., 1990. Boundary detection by constrained optimization. IEEE Trans Pattern Anal Mach Intell 12, 609–628.

* Hafner, J., Sawhney, J., Equitz, W., Flicker, M., Niblack, W., 1995. Efficient colour histogram indexing for quadratic form distance functions. IEEE Trans Pattern Anal Mach Intell 17, 729–736.

* Huang, G., Jain, V., Learned-Miller, E., 2007a. Unsupervised joint alignment of complex images, in: ICCV, pp. 1–8.

* Huang, G.B., Ramesh, M., Berg, T., Learned-Miller, E., 2007b. Labeled Faces in the Wild: A Database for Studying Face Recognition in Unconstrained Environments. Technical Report 07-49. University of Massachusetts, Amherst.

* Kailath, T., 1967. The divergence and bhattacharyya distance measures in signal selection. IEEE T Commun Techn 15, 52–60.

* Kamarainen, J.K., Kyrki, V., Ilonen, J., Kälviäinen, H., 2003. Improving similarity measures of histograms using smoothing projections. Pattern Recogn Lett 24, 2009–2019.

* Kim, J., Billard, L., 2013. Dissimilarity measures for histogram-valued observations. Commun Stat Theory Methods 42, 283–303.

* Kurtz, C., Ganarski, P., Passat, N., Puissant, A., 2013. A hierarchical semantic-based distance for nominal histogram comparison. Data Knowl Eng 87, 206–225.

* Lee, K.C., Ho, J., Kriegman, D.J., 2005. Acquiring linear subspaces for face recognition under variable lighting. IEEE Trans Pattern Anal Mach Intell 27, 684–698.

* Ling, H., Jacobs, D., 2007. Shape classification using the inner-distance. IEEE Trans Pattern Anal Mach Intell 29, 286–299.

* Ling, H., Okada, K., 2006. Diffusion distance for histogram comparison, in: CVPR, pp. 246–253.

* Ling, H., Okada, K., 2007. An efficient earth mover's distance algorithm for robust histogram comparison. IEEE Trans Pattern Anal Mach Intell 29, 840–853.

* Lowe, D.G., 2004. Distinctive image features from scale-invariant keypoints. Int J Comput Vis 60, 91–110.

* Ma, Y., Gu, X., Wang, Y., 2010. Histogram similarity measure using variable bin size distance. Comput Vis Image Und 114, 981–989.

* Matusita, K., 1955. Decision rules based on the distance for problems of fit two samples and estimation. The Annals of Math Stat 26, 631–640.

* Pele, O., Werman, M., 2008. A linear time histogram metric for improved sift matching, in: ECCV. volume 5304 of LNCS, pp. 495–508.

* Pele, O., Werman, M., 2009. Fast and robust earth mover's distances, in: ICCV, pp. 460–467.

* Pele, O., Werman, M., 2010. The quadratic-chi histogram distance family, in: ECCV. volume 6312 of LNCS, pp. 749–762.

* Puzicha, J., Hofmann, T., Buhmann, J., 1997. Non-parametric similarity measures for unsupervised texture segmentation and image retrieval, in: CVPR, pp. 267–272.

* Rubner, Y., Tomasi, C., Guibas, L.J., 2000. The earth mover's distance as a metric for image retrieval. Int J Comput Vis 40, 99–121.

* Scholkopf, B., Smola, A.J., 2001. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA.

* Shen, H., Wong, A., 1983. Generalized texture representation and metric. Comput Vision Graph 23, 187–206.

* Shirdhonkar, S., Jacobs, D., 2008. Approximate earth mover's distance in linear time, in: CVPR, pp. 1–8.

* Shore, J., Gray, R., 1982. Minimum cross-entropy pattern classification and cluster analysis. IEEE Trans Pattern Anal Mach Intell 4, 11–17.

* Ruiz-del Solar, J., Verschae, R., Correa, M., 2009. Recognition of faces in unconstrained environments: a comparative study. EURASIP J Adv Signal Process vol. 2009, 1–19.

* Strelkov, V., 2008. A new similarity measure for histogram comparison and its application in time series analysis. Pattern Recogn Lett 29, 1768–1774.

* Swain, M., Ballard, D., 1991. Color indexing. Int J Comput Vis 7, 11–32.

* Tan, X., Triggs, B., 2007. Preprocessing and feature sets for robust face recognition, in: CVPR, pp. 1–8.

* Wolf, L., Hassner, T., Taigman, Y., 2008. Descriptor based methods in the Wild, in: Faces in Real-Life Images: Detection, Alignment and Recognition Workshop at ECCV.