---
abstract: 'In this paper we target the problem of the retrieval of colour patterns over surfaces. We generalize to surface tessellations the well known Local Binary Pattern (LBP) descriptor for images. The key concept of the LBP is to code the variability of the colour values around each pixel. In the case of a surface tessellation we adopt rings around vertices that are obtained with a sphere-mesh intersection driven by the edges of the mesh; for this reason, we name our method edgeLBP. Experimental results are provided to show how this description performs well for pattern retrieval, also when patterns come from degraded and corrupted archaeological fragments.'
author:
- 'E. Moscoso Thompson and S. Biasotti'
bibliography:
- 'bibliography.bib'
title: 'Edge-based LBP description of surfaces with colorimetric patterns'
---

Introduction
============

Thanks to advances in the modeling techniques and to the availability of cheaper yet effective 3D acquisition devices, we see a remarkable increase of the amount of 3D data available. Many sensors are able to acquire not only the 3D shape but also its *texture*; this is the case, for instance, of the Microsoft Kinect device. The creation of an increasing number of 3D models has opened new opportunities to study the past, by giving access to plenty of representations of artifacts close to their original form. At the same time, Cultural Heritage owns a growing mass of non-interpreted 3D data, which call for innovative solutions for the analysis of data. In this context, local descriptors, feature recognition and similarity measures become indexes to the informative content of 3D models, and are essential to categorize objects and to recognize a style, e.g. to attribute objects to a given society or to a given author. A typical problem the archaeologists face when dealing with collections of fragments is to determine their compatibility. Compatibility is generally determined by multiple factors: geometric correspondence, same material and, possibly, if there are not evidently matching fragments, continuity consideration on the fragment skin (colour, texture) [@gravitate_proc].

Within the large scenario of Cultural Heritage, we focus on the analysis and description of color patterns. The idea is to recognize the same decoration, for instance a repeated lotus leaf, independently of the support (e. g., the surface bending) on which it is depicted. Therefore, this work will contribute to the definition of a compatibility measure among artifacts based on skin decorations. To approach this problem, we consider a novel extension of the Local Binary Pattern description to surface tessellations based on the evolution of the color over concentric circles around a vertex. To determine these circles we adopt a sphere - edge intersection strategy and for this reason we name our approach edgeLBP. As application of the edgeLBP description, we propose the retrieval and classification of color patterns over surfaces.

The remainder of the paper is organized as follows. Section \[sec:star\] briefly reviews the literature on the retrieval of textured images and surfaces. Section \[sec:method\] introduces the elements of our method, i.e. the edgeLBP operator and how we store it in a descriptor. Section \[sec:results\] presents and analyses the retrieval and classification performances of the method over two datasets, while conclusive remarks end the paper, Section \[sec:conclusions\].

State of art {#sec:star}
============

A typical strategy to detect textures on images is to consider local patches that describe the behavior of the texture around a group of pixels. Examples of these descriptions are the Local Binary Patterns (LBP) [@ojala; @ojala02], the Scale Invariant Feature Transform (SIFT) [@Lowe2004] and the Histogram of Oriented Gradients (HOG) [@DaTr05].The generalization of these descriptions to (even textured) surfaces has been explored in several works, such as the PANORAMA views of the 3D objects [@Papadakis2010], the meshHOG [@meshHOG] and the meshLBP [@WerghiTBB16; @WerghiTBB15]. In general, the methods for matching textured 3D shapes adopt a combination of geometric and colorimetric descriptors. Possible choices of the colorimetric descriptors are: feature-vectors, where the color is treated as a general property of the shape, [@Suzuki01], or its subparts in [@garro16]; local or global views of the objects [@WuCLFP08; @Pasqualotto2013]; point-to-point correspondences among sets of feature points (e.g., the CSHOT descriptor [@TombariSS11]); the evolution of the sub-level sets according to the persistent homology settings [@PHOG]. These methods mainly address the shape matching problem without focusing on the surface details and local colorimetric variations. On the contrary, when looking for patterns, locality and scale are the two key aspects. A detailed evaluation and comparison of methods for 3D texture retrieval and comparison can be found in [@Biasotti2016] and several SHREC contests [@Cerri13; @Cerri14; @Giachetti15]. However, all these contests focused on the joint comparison of geometry and texture, without considering the comparison of the purely colorimetric information that characterizes the surface decorations.

At the best of our knowledge, the Mesh Local Binary Pattern (meshLBP) approach [@WerghiTBB16; @WerghiTBB15; @WerghiBB15] is the unique approach that explicitly addresses pattern analysis over surfaces. The meshLBP extends the LBP [@ojala] to triangle meshes. The main idea behind the meshLBP is that triangles play the role of pixels and the 8-neighbor connectivity in an image is ideally substituted by a 6-neighbor connectivity around triangles. Rings on the mesh are computed using a uniform, region growing, triangle-based expansion. From the practical point of view, the meshLBP encodes a pattern efficiently, providing a compact representation of it.

The edgeLBP {#sec:method}
===========

We extend the LBP to surfaces using rings defined on the basis of a sphere-mesh intersection. In Section \[ss:LBP\_imagesc\] we briefly sum up the definition of the LBP definition. Our extension to surface tessellations is described in Section \[ss:edgeLBP\_def\], while Section \[ss:descriptor\] details the edgeLBP descriptor and the distance adopted to compare two descriptors.

Local Binary Pattern for gray-scale images {#ss:LBP_imagesc}
------------------------------------------

The *Local binary pattern (LBP)* and its variants prove to be a good solution for the classification of patterns in images [@LIU2017]. Given a gray-scale image $I$, the LBP describes the pattern in $I$ coding the local variation of the gray-scale values (encoded with a function $h:I\rightarrow [0,255]$) around each pixel of $I$. More extensively, for each pixel $i\in I$, a *ring* of pixels around $i$ (called $ring_i$) is considered (see Figure \[fig:LBP\_ring\]) and a 8-digit binary array $str_i$ defined as follow: $$str_i(j)=\Bigl\{  \begin{array}{ll}   1 & if \quad h(i)<h(i_j)\\
                                        0 & otherwise           \\
                    \end{array}$$ where $i_j$ is the $j-th$ pixel of the ring around $i$, sorted clockwise and starting from the top-left pixel.

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![In (a) the $ring$ of the pixel $i$ is shown; while (b) and (c) show two examples of concentric $ring$s.[]{data-label="fig:LBP_ring"}](pic/multiring_1.jpg "fig:"){width="3.5cm"}   ![In (a) the $ring$ of the pixel $i$ is shown; while (b) and (c) show two examples of concentric $ring$s.[]{data-label="fig:LBP_ring"}](pic/multiring_2.jpg "fig:"){width="3.5cm"}   ![In (a) the $ring$ of the pixel $i$ is shown; while (b) and (c) show two examples of concentric $ring$s.[]{data-label="fig:LBP_ring"}](pic/multiring_3.jpg "fig:"){width="3.5cm"}
                                                                                          (a)                                                                                                                                                                                  (b)                                                                                                                                                                                  (c)
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The LBP operator of a pixel $i$ is defined by: $$LBP(i)=\sum_j str_i(j)\alpha(j),$$ where $\alpha$ is a weight function. Throughout this paper we consider $\alpha_1(j)=1, \forall j$. Notice that in this case, the $LBP(i)$ value is independent of the ordering of $ring_i$. Finally, the LBP descriptor of the pattern in $I$ is defined as the histogram of the values $LBP(i)$.

The LBP operator was extended to multiple rings around each pixel in $I$, see Figure \[fig:LBP\_ring\](b-c). The descriptor of the LBP multi-ring is the concatenation of the histograms of the LBP values of each single ring, e.g., an array or a matrix.

Definition and implementation of the edgeLBP operator {#ss:edgeLBP_def}
-----------------------------------------------------

We extend the multi-ring LBP operator to deal with surface tessellations through a sphere-mesh intersection technique, called the *edge Local Binary Pattern (edgeLBP)*. By a surface tessellation, we mean a polygonal mesh $T=(V,E,F)$, which is a collection of vertices $V$, edges $E$ and faces $F$ defining the surface of an object. In our settings, we assume that the faces of the tessellation are convex polygons; examples of admissible surface representations are triangle and quad meshes, [@BLPPSTZ13a].

We assume that the surface property can be stored as a scalar function $h$ defined on the vertices of the tessellations, formally, $h:V\rightarrow\mathbb{R}$. In our settings, we consider two choices for the function $h$: (i) the *L-channel* from the CIELab color space [@CIELAB_1; @CIELAB_2]; (ii) the gray-scale value defined as $0.21R+0.72G+0.07B$ ($R$, $G$ and $B$ are the channels of the RGB color space).

The concept of ring is crucial for the LBP operator: while a pixel grid has the same connectivity everywhere, surface tessellations can be widely *irregular*, thus the $ring$ definition over them is not obvious. By irregular we mean that the vertices can be non uniformly distributed over the surface and the faces of the tessellation may have different area, shape and number of edges.

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![(a): in blue, two rings defined on the basis of triangles; (b): the ring around the vertex $v$ is defined by mesh vertices (red dots).[]{data-label="fig:bad_rings"}](pic/bad_ring1.png "fig:"){width="5.5cm"}   ![(a): in blue, two rings defined on the basis of triangles; (b): the ring around the vertex $v$ is defined by mesh vertices (red dots).[]{data-label="fig:bad_rings"}](pic/bad_ring2.png "fig:"){width="5.5cm"}
                                                                                                         (a)                                                                                                                                                                                                                (b)
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Figure \[fig:bad\_rings\] depicts two possible $ring$ definitions exclusively made of mesh elements (triangles in Figure \[fig:bad\_rings\](a) and vertices in Figure \[fig:bad\_rings\](b), resp.): in both cases, the irregularity of the mesh elements strongly influences these of rings.

We define the $ring$ of a vertex $v \in V$ as the intersection of the surface tessellation with a sphere of radius $R$ centered in $v$.

  --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![(a): in black, multiple closed curves defined by the set of points $P_i \in \mathcal{R}$; (b): the black dots correspond to the elements $p_i$ of the three central curves in (a).[]{data-label="fig:ring_construction"}](pic/ring_int.png "fig:"){width="5.5cm"}   ![(a): in black, multiple closed curves defined by the set of points $P_i \in \mathcal{R}$; (b): the black dots correspond to the elements $p_i$ of the three central curves in (a).[]{data-label="fig:ring_construction"}](pic/ring_pi.png "fig:"){width="5.5cm"}
                                                                                                                                   (a)                                                                                                                                                                                                                                                                  (b)
  --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Such an intersection is represented by the set of points $\mathcal{R}=\{p_1, p_2, \ldots, p_k\}$ that approximate the intersection between the sphere and the surface. Figure \[fig:ring\_construction\] shows a number of concentric rings over a triangle mesh. To determine a $ring$ around a vertex $v$, we follow a mesh expansion approach driven by the Euclidean distance from the vertex $v$, as summarized in the following steps:

1.  All the edges that are incident in $v$ are added to a list $L$.

2.  Starting from an edge $e=(v,v_1) \in L$, the intersection between $e$ and the sphere centered in $v$ with radius $R$ is evaluated. If there actually is an intersection, it is stored as a new point $p_i$, otherwise, if $e$ completely falls inside the sphere, we add to $L$ all the edges that are incident to $v_1$. The edge $e$ is removed from $L$ and labeled as visited.The value $h(p_i)$ on $p_i$ is given by the linear interpolation of the values that $h$ assumes in $v$ and $v_1$.

3.  The step $2$ is repeated $\forall e \in L$, until the list is empty.

To achieve a multi-ring representation, for any vertex $v \in V$ we consider $N_r$ rings, $\{ring_1^v, \ldots, ring_{N_r}^v\}$. Let $S^v_{l}$ be the surface portion of $T$ that contains $v$ and has the $ring^v_k$ as its boundary, $l=1\ldots N_r-1$, then the relation $S^v_{l} \subset S^v_{l+1}$ holds for each $l$. When extending the edgeLBP evaluation to multiple rings, the algorithm takes advantage of the nested nature of the rings and extracts $S^v_l$ with respect to increasing values of the radius $R$. In general, the sphere-surface intersection can produce multiple, closed curves that bound either a multiple connected or a dis-connected portion of the surface, as detailed in [@blowing_bubbles]. Using a region growing approach, we dynamically consider only the $S^v_l$ components.Therefore, $S^v_l$ is always a connected region that contains $v$; however, it can become multiply connected. If all the $N_r$ components of $S^v_l$ are simply connected and all the $N_r$ rings do not intersect the surface boundary (if any), the $v$ is considered an *admissible* vertex for the edgeLBP, otherwise it is *non-admissible*.

### Ring re-ordering and sampling

Each $ring$ is represented as the piecewise, linear curve $C$ determined by the segments $(p_i,p_{i+1})$, $p_i \in \mathcal{R}$. Then, the curve $C$ is oriented *counter-clockwise* with respect to the vector in $v$ normal to $T$. We select As the starting point for ordering $C$, we select the point $\tilde{p}$ such that: $$\tilde{p}=\operatorname*{argmax}\limits_{p_i\in\mathcal{R}} h(p_i).$$ In case of symmetries around a vertex, multiple choices of the starting point are possible: we select the candidate point that is the farthest from the other elements of $\mathcal{R}$. The stability of the starting point of a $ring$ is confirmed in numerous experiments we performed on meshes of different resolution, where by mesh resolution we mean the number of vertices of the mesh. Figure \[fig:ring\_stab\] shows the vector field generated by the difference between $\tilde{p}$ and $v$ ($\overrightarrow{{\tilde{p}-v}}$) all over the mesh. The orientation of the field indicates the position of $\tilde{p}$. The pictures show a detail of the field over a mesh with $40K$ vertices and two mesh sub-samplings with $16K$ and $8K$ vertices: the overall orientation of the field (and therefore the choice of $\tilde{p}$) is robust to different mesh samplings.

![Arrows represent the starting point of the rings in meshes representing the same surface but sampled with a different number of vertices (40K, 16K and 8K vertices, resp.).[]{data-label="fig:ring_stab"}](pic/unique_quiv.png){width="12cm"}

In case of multiple rings, $\tilde{p}$ is selected only on the biggest ring $ring_{N_r}$; for each concentric ring, the starting point is the point $p_i$, which is the closest one to $\tilde{p}$. Generally the number of elements $p_i \in \mathcal{R}$ varies from one ring to another, because of the increasing radius of the sphere and the irregularity of the tessellation, see Figure \[fig:ring\_construction\](b). To have the same number of elements on every ring, we sample $C$ with $P$ points, where $P$ is a fixed number, called the *spatial resolution*. The results of this sampling is $S$, a set of equidistant samples of $C$, $s_j$ with $j=1, \ldots, P$. In details, the equidistant re-sampling is performed as follows:

-   we set the expected distance $\delta r$ between two successive points in $S$ as $\delta r= \dfrac{2\pi R}{P}$;

-   we set $s_0=\tilde{p}$ and extract the points $s_j$ on $C$ such that $$|s_{j-1}-s_j|\approx \delta r, \qquad j=\{1, \ldots, P\}.$$

The value $h(s_j)$ is linearly approximated from the values the function $h$ assumes on the extrema of the corresponding segment in $C$.

### Choice of the ring radii

With the edgeLBP we are interested to code local variations on the surface, therefore the radius $R$ should be kept small with respect to the overall dimension of the surface. This implies that the choice of the radius $R$ is crucial for the type (and the size) of the patterns we are going to identify; indeed it must be not too large to avoid to mix global and local surface information and not too small to become insignificant. In practice, the multiply connected regions appear in case of topological noise, like small handles and mesh self-intersections; in our experiments over thousands of tessellations we never met meaningful admissibility problems.

We opt for a uniform distribution of the ring radii values. Denoting $R_{max}$ the maximum radius and $N_r$ the number of rings, the value of the ring radii will be $\frac{R_{max}}{N_r}, 2\frac{R_{max}}{N_r}, \ldots, R_{max}$.

                Base models                                                                 Textured models                                                                                           
  --------------------------------------- -------------------------------------- -------------------------------------- -------------------------------------- -------------------------------------- ----------------------------------------
                                                         Class 1                                Class 2                                Class 3                                Class 4                 
   ![image](pic/mod1.png){width="1.4cm"}   ![image](pic/pt1.png){width="1.4cm"}   ![image](pic/pt2.png){width="1.4cm"}   ![image](pic/pt3.png){width="1.4cm"}   ![image](pic/pt4.png){width="1.4cm"}   ![image](pic/cmod1.png){width="1.4cm"}
                                                         Class 5                                Class 6                                Class 7                                Class 8                 
   ![image](pic/mod2.png){width="1.4cm"}   ![image](pic/pt5.png){width="1.4cm"}   ![image](pic/pt6.png){width="1.4cm"}   ![image](pic/pt7.png){width="1.4cm"}   ![image](pic/pt8.png){width="1.4cm"}   ![image](pic/cmod2.png){width="1.4cm"}
                                                                                                                                                                                                      
                                                                                                                                                                                                      

Similarity assessment {#ss:descriptor}
---------------------

Once the function $h$ is evaluated over the sample sets of the rings around $v$, the edgeLBP value on $v$ straightforwardly follows from the classic LBP definition, see Section \[ss:LBP\_imagesc\].

Given the surface tessellation $T$, its *edgeLBP descriptor* is labeled $D_T$. The entry $D_T(n,m)$ is defined as the histogram that counts how many vertices have an edgeLBP value equal to $m$ on the $ring_n$. Since in the experiments we are mostly interested in the distribution of the edgeLBP values, we adopt $\frac{D_T}{n_v}$ as the edgeLBP descriptor, where $n_v$ is the number of the admissible vertices. Through this normalization of $T$ we achieve robustness to the number of vertices of the surface representation.

We define the dissimilarity between two tessellations $A$ and $B$ as the distance between their corresponding edgeLBP descriptors $D_A$ and $D_B$. Since the edgeLBP can be thought as a matrix, any feature vector distance is suitable to evaluate the similarity between two edgeLBP descriptors. We analysed the Euclidean distance between matrices, the *Earth Mover’s Distance* as defined in [@Rubner:2000] and the *Bhattacharyya distance*. The Bhattacharyya distance $d_{Bha}$ between two distributions $\phi$ and $\psi$ of a scalar random variable $X$ has the following definition: $$d_{Bha}(\phi,\psi)=\sqrt{1-BC(\phi,\psi)}, \qquad BC(\phi,\psi)=\sum\limits_{x\in X} \sqrt{\phi(x)\psi(x)},$$ where $BC$ is called the *Bhattacharyya coefficient*. Then, for a set of surface tessellations, the dissimilarity values are stored in a *distance matrix* $DM(i,j)=d(D_i,D_j)$, where $d$ is the distance between the descriptors of the tessellation $i$ and $j$. Diagonal values of $Dist(i,i)$ are zero.

Experimental results {#sec:results}
====================

In this Section we introduce the datasets and the evaluation measures adopted to analyse the retrieval performance of the edgeLBP. We present the edgeLBP performances and discuss its robustness to different tessellations of the same surface.

Dataset
-------

To evaluate the edgeLBP ability of effectively discriminating pattern variations, we used two datasets:

-   the *Cups, Pots and Pans* dataset (or *CPP* for short) is created from triangle meshes in the SHREC’07 Watertight model contest [@SHREC07] and the COSEG [@COSEG:2012] datasets (see Figure \[fig:CCP\_origin\](Left)). The original meshes do not have any texture or colorimetric information. From 20 base models and 10 black and white textures representing a pattern (see Figure \[fig:CCP\_origin\](Center)) we derived 200 models, applying each texture to every model with a semi-automatic algorithm. The proper RGB value was added to the mesh vertices discarding any other colorimetric information (see Figure \[fig:CCP\_origin\](Right)). At the end of this process, each model is covered by one of the 10 patterns for at least the 30% of its surfaces while the rest of the surface is only black or only white. The number of vertices of the $200$ models ranges from $95K$ to $107K$.

-   the *Artifacts* dataset is derived from the laser scans of CH artifacts stored in the STARC repository [@Starck07] and selected as test-beds in the Gravitate EU project [@GRAVITATE_prog]. The colorimetric information comes as a RGB value associated to each mesh vertex. Differently from the CPP dataset, this second dataset contains full-color information, with a predominance of red, yellow and brown nuances. From these fragments we identified 10 classes of different patterns (see Figure \[fig:GRAV\_col\]); then, for each type of pattern, we tailored 4 representative patches coming from different fragments, for a total of 40 patches. Every patch is made of approximately $40K$ vertices.

      ------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------
                                                                        Class 1                                                                                                                                     Class 2                                                                                                                                       Class 3                                                                                                                                      Class 4                                                                                                                                     Class 5
       ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptI.png "fig:"){width="2cm"}    ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptII.png "fig:"){width="2cm"}    ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptIII.png "fig:"){width="2cm"}    ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptIV.png "fig:"){width="2cm"}   ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptV.png "fig:"){width="2cm"}
                                                                        Class 6                                                                                                                                     Class 7                                                                                                                                       Class 8                                                                                                                                      Class 9                                                                                                                                    Class 10
       ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptVI.png "fig:"){width="2cm"}   ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptVII.png "fig:"){width="2cm"}   ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptVIII.png "fig:"){width="2cm"}   ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptIX.png "fig:"){width="2cm"}   ![Representatives of the 10 classes considered in the Artifacts dataset.[]{data-label="fig:GRAV_col"}](pic/cptXb.png "fig:"){width="2cm"}
      ------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------

The edgeLBP algorithm is used to perform colorimetric pattern retrieval on the CCP and Artifact datasets, separately.

Evaluation measures {#ss:eval_mes}
-------------------

The evaluation tests have been performed using a number of classical information retrieval measures, namely the Nearest Neighbor, First Tier, Second Tier, Discounted Cumulative Gain, e-measure, Precision-Recall plot, confusion matrices and tier images.

#### Nearest Neighbor, First Tier, Second Tier {#nearest-neighbor-first-tier-second-tier .unnumbered}

These measures aim at checking the fraction of models in the query’s class also appearing within the top $k$ retrievals. In detail, for a class with $|C|$ members, $k=1$ for the Nearest Neighbor (NN), $k =|C|-1$ for the first tier (FT), and $k = 2(|C| - 1)$ for the second tier (ST). Note that all these values range from 0 to 1.

#### Discounted cumulative gain {#discounted-cumulative-gain .unnumbered}

The Discounted Cumulative Gain (DCG) is an enhanced variation of the Cumulative Gain, which is the sum of the graded relevance values of all results in the list of retrieved objects of a given query. The definition of DCG adopted in this paper can be found in [@Jarvelin2002].

#### Precision-Recall, mAP and e-measure {#precision-recall-map-and-e-measure .unnumbered}

The *Precision* and *Recall* are common measures for retrieval evaluation. Recall is the ratio of the number of relevant records retrieved to the total number of relevant records, while precision is the ratio of the number of relevant records retrieved to the size of the return vector [@salton_evaluation]. Precision and recall always range from 0 to 1. Often, precision and recall are plot as a curve in the reference frame recall vs. precision [@Baeza-Yates:1999]: the larger the area below such a curve, the better the performance under examination. As an additional index, we consider the mean Average Precision (mAP), which is the portion of area under a precision-recall curve. Finally, we consider the *e-measure* $e$ [@Rijsbergen1979], which is a quality measure of the first models retrieved for every query. The e-measure depends on the *Precision* and *Recall* values by the relation: $e=\frac{2}{Precision^{-1}+Recall^{-1}}.$

#### Confusion matrices and Tier images {#confusion-matrices-and-tier-images .unnumbered}

Each classification performance can be associated with a confusion matrix $CM$, that is, a square matrix whose dimension is equal to the number of classes in the dataset. For the row $i$ in $CM$, the element $CM(i,i)$ gives the number of items which have been correctly classified as elements of the class $i$; similarly, elements $CM(i,j)$, with $j\neq i$, count the items which have been misclassified, resulting as elements of the class $j$ rather than elements of the class $i$. Similarly, the tier image $TI$ visualizes the matches of the NN, FT and ST. The value of the element $TI(i,j)$ is: *black* if $j$ is the NN of $i$, *red* if $j$ is among the $(|C|-1)$ top matches (FT) and *blue* if $j$ is among the $2(|C|-1)$ top matches (ST). For an ideal classification matrix, $CM$ becomes the diagonal matrix while the $TI$ clusters the black/red square pixels on the diagonal.

Results {#ss:ris_eval}
-------

In this Section we discuss the retrieval and classification performance of the edgeLBP. For simplicity, we report only the results obtained with the Bhattacharyya distance because in our experiments it performs better than the other distances considered. We performed multiple runs with different settings, changing the number ($N_r$) of rings and the number of samples ($P$) on them, together with different $R$ associated to the $N_r$-th ring (called $R_{max}$). The value of $R$ is based on the size of the patterns in it: we randomly picked 3 models of that dataset and choose one or more $R_{max}$ values that were properly scaled for the dataset. The parameters $N_r$ and $P$ are initially set with what we consider the default settings: $P=15$, $N_r=5$. Similarly we consider $h=L-channel$ of the CIELAB color space as the default setting of the function $h$. Different choices of $h$, $P$ and $N_r$ are discussed for the Artifacts dataset.

#### CPP dataset {#cpp-dataset .unnumbered}

We tested the edgeLBP on this dataset using the default settings and adapting the $R_{max}$ to the size of the wanted pattern ($R_{max}=0.04mm$), in what in this paper is called *Run1*. As baseline methods to compare against the edgeLBP descriptor we consider two variations of the color histograms. *Hist1* outputs descriptors based on a 16-bin histogram normalized on his minimal and maximal $L$ values. *Hist2* is similar, but no normalization is applied to the values of $L$. In addition, we also consider the meshLBP descriptor as implemented in the Matlab toolbox [@meshLBP]. Figure \[fig:ccp\_res\](Top) reports the numerical evaluation measures. Figure \[fig:ccp\_res\](Middle) compares the recall vs precision curves of all the methods. Figure \[fig:ccp\_res\](Bottom) reports the confusion matrix and the tier image of edgeLBP and the meshLBP runs.

[c]{}

[c]{}

                  NN          FT          ST         e          mAP        nDCG
  ----------- ----------- ----------- ---------- ---------- ----------- ----------
   *edgeLBP*   **0.985**   **0.801**   **0.97**   **0.66**   **0.859**   **0.94**
   *meshLBP*     0.94        0.615      0.805       0.54       0.691       0.87
     Hist1        0.3        0.301      0.415       0.27       0.354       0.58
     Hist2       0.61        0.522      0.774       0.51       0.57        0.76

\
\
![Performance evaluation on the CCP dataset. Top: the NN, FT, ST, e-measure, mAP and nDGC evaluation measures. Middle: the Precision-Recall curves. Bottom: the confusion matrix and tier image of the edgeLBP and the meshLBP runs.[]{data-label="fig:ccp_res"}](pic/PR_ccp.png "fig:"){width="10cm"}

\

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
                                                                                                                                             Confusion Matrix                                                                                                                                                                                                                                                                                           Tier Image                                                                                                                                                                                                                                                                                               Confusion Matrix                                                                                                                                                                                                                                                                                                   Tier Image
   ![Performance evaluation on the CCP dataset. Top: the NN, FT, ST, e-measure, mAP and nDGC evaluation measures. Middle: the Precision-Recall curves. Bottom: the confusion matrix and tier image of the edgeLBP and the meshLBP runs.[]{data-label="fig:ccp_res"}](pic/ccp_cm.png "fig:"){width="3cm"}   ![Performance evaluation on the CCP dataset. Top: the NN, FT, ST, e-measure, mAP and nDGC evaluation measures. Middle: the Precision-Recall curves. Bottom: the confusion matrix and tier image of the edgeLBP and the meshLBP runs.[]{data-label="fig:ccp_res"}](pic/ccp_ti.png "fig:"){width="3cm"}   ![Performance evaluation on the CCP dataset. Top: the NN, FT, ST, e-measure, mAP and nDGC evaluation measures. Middle: the Precision-Recall curves. Bottom: the confusion matrix and tier image of the edgeLBP and the meshLBP runs.[]{data-label="fig:ccp_res"}](pic/ccp_cm_meshLBP.png "fig:"){width="3cm"}   ![Performance evaluation on the CCP dataset. Top: the NN, FT, ST, e-measure, mAP and nDGC evaluation measures. Middle: the Precision-Recall curves. Bottom: the confusion matrix and tier image of the edgeLBP and the meshLBP runs.[]{data-label="fig:ccp_res"}](pic/ccp_ti_meshLBP.png "fig:"){width="3cm"}
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The classification and retrieval results obtained over this dataset are very promising and highlight how the edgeLBP encoding captures the pattern distribution over the surface. The edgeLBP overcome simple histogram-based descriptions that, in practice, measure the percentage of color distribution without any control around vertices and also the meshLBP description that bases the ring definition on mesh elements. The positive edgeLBP perfomance is confirmed in the recent SHREC’18 track for gray color patterns [@shrec18].

Artifacts dataset {#artifacts-dataset .unnumbered}
-----------------

This dataset is challenging because of the quality of the original fragments, as their colorimetric patterns are degraded and damaged. Table \[tb:GRA\_res\] reports the NN, FT and ST evaluations for different parameter settings of the edgeLBP. Confusion matrices for the two best radius values are reported in Figure \[fig:ar\_cmti\], along with the relative Tier Images. The number of models in this dataset is too small to consider meaningful the other evaluation measures.

The edgeLBP achieves good retrieval and classification results for most classes. We observed, as expected, that the correctness of the classification is mainly driven by the size of $R$, rather then $P$ and $N_r$. As a final note, we tested our algorithm using gray scale values as $h$ function: the results obtained with it were pretty much the same as those obtained with $h=L$. We think that this is due to which information both $L$ of CieLAB color space and the gray scale encodes.

  ------------------------------------------- ------------------------------------------- ------------------------------------------- -------------------------------------------
                                                                                                                                      
   ![image](pic/ar_cm_run1.png){width="3cm"}   ![image](pic/ar_ti_run1.png){width="3cm"}   ![image](pic/ar_cm_run3.png){width="3cm"}   ![image](pic/ar_ti_run3.png){width="3cm"}
  ------------------------------------------- ------------------------------------------- ------------------------------------------- -------------------------------------------

       Parameter Settings         NN      FT      ST
  ----------------------------- ------- ------- -------
   $P:15, N_r:5, R_{max}:0,2$    0.775   0.789     1
   $P:15, N_r:5, R_{max}:0,3$    0.75    0.811   0.989
   $P:15, N_r:5, R_{max}:0,5$    0.75    0.711   0.889
   $P:15, N_r:5, R_{max}:0,7*$   0.725   0.667   0.756
   $P:12, N_r:7, R_{max}:0,5$    0.75    0.789    0.9
   $P:12, N_r:7, R_{max}:0,2$    0.775   0.856   0.978
   $P:18, N_r:5, R_{max}:0,7$     0.7    0.667   0.744

  : The NN, FT and ST scores for some runs of the edgeLBP on the Artifacts dataset. The $*$ in the fourth row means that in these settings we adopt $h^3$ instead of $h$ (here, $h$ corresponds to the L-channel). $R$ is expressed in $mm$.

\[tb:GRA\_res\]

Robustness over different surface tessellations {#ss:robustness_part}
-----------------------------------------------

The strength of the edgeLBP is its ring definition, which is robust to different surface tessellations: in this Section we experimentally discuss this robustness. To this aim we re-sample the triangles meshes with a decreasing number of vertices. The triangle mesh re-sampling with $x$ vertices is done with the MeshLAB tool [@meshlab] that approximates the original mesh preserving its geometry as much as possible with the given number of vertices (for instance, $x=40K$ vertices). This process generally modifies the mesh connectivity and the area of the triangles, discards the smallest details and keeps the overall shape, unless the number of vertices drastically diminishes and the new vertices are too few to preserve it.

  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                                                                                                                              $40K$                                                                                                                                                                                                                                                         $24K$                                                                                                                                                                                                                                                       $8K$
   ![The degradation of one of the model used to test the robustness of the descriptor of both edgeLBP and meshLBP. The number on each image is the respective vertex resolution.[]{data-label="fig:comparison_model"}](pic/deg_ori.png "fig:"){width="2.45cm"}   ![The degradation of one of the model used to test the robustness of the descriptor of both edgeLBP and meshLBP. The number on each image is the respective vertex resolution.[]{data-label="fig:comparison_model"}](pic/deg1.png "fig:"){width="2.45cm"}   ![The degradation of one of the model used to test the robustness of the descriptor of both edgeLBP and meshLBP. The number on each image is the respective vertex resolution.[]{data-label="fig:comparison_model"}](pic/deg2.png "fig:"){width="2.45cm"}
  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

First, we re-sampled the meshes in the CCP dataset with $40K$ vertices. On this dataset, we compare the outcome of the edgeLBP with the default settings with the meshLBP, see Table \[tb:downgrades\]. If compared with the performances on the original CPP dataset in Figure \[fig:ccp\_res\], the edgeLBP degrades less than the meshLBP, demonstrating of being more robust to mesh degradation and re-sampling.

              NN     FT      ST      e      mAP    nDCG
  --------- ------ ------- ------- ------ ------- ------
   edgeLBP   0.95   0.688   0.857   0.59   0.761   0.9
   meshLBP   0.77   0.517   0.703   0.47   0.58    0.79

  : Evaluation measures of the performances on the CPP dataset resampled with 40K vertices.

\[tb:downgrades\]

Second, we selected 3 patches from the Artifacts dataset and sub-sampled them with $32K$, $24K$, $16K$ and $8K$ vertices (see Figure \[fig:comparison\_model\]).These four meshes are compared against the original patch (that has $40K$ vertices).These four distance values provide an estimate of the error the descriptors do when working with the simplified meshes.

We performed two runs for both the edgeLBP and meshLBP:

-   *Run1: $P=12$, $N_r=7$*. These settings are the setting used by the meshLBP as default. Both meshLBP and edgeLBP are run with these settings. For the edgeLBP we set $R_{max}=0.5mm$.

-   *Run2: $P=15$, $N_r=5$*. These settings are those that we consider default for the edgeLBP. Both the algorithms are run with these settings. As in $run1$, we set $R_{max}=0.5mm$.

Figure \[fig:mesh\_edge\_results\] represents the distance between the original model and its four approximations with respect to both edgeLBP and meshLBP, for all the three original meshes. Since the scale of the distances adopted by the meshLBP and edgeLBP is different, we normalize them with respect the range of the distance values among these patches.

  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                                                                                                                                                     *Run1*
    ![The plots represent the distance of the four simplified meshes from the original ones, with respect to the meshLBP and the edgeLBP descriptors. The labels in the horizontal axis highlight to the number of vertices of the mesh.[]{data-label="fig:mesh_edge_results"}](pic/error_plot_1.png "fig:")
                                                                                                                                                     *Run2*
    ![The plots represent the distance of the four simplified meshes from the original ones, with respect to the meshLBP and the edgeLBP descriptors. The labels in the horizontal axis highlight to the number of vertices of the mesh.[]{data-label="fig:mesh_edge_results"}](pic/error_plot_2.png "fig:")
   ![The plots represent the distance of the four simplified meshes from the original ones, with respect to the meshLBP and the edgeLBP descriptors. The labels in the horizontal axis highlight to the number of vertices of the mesh.[]{data-label="fig:mesh_edge_results"}](pic/legend_meshedge.png "fig:")
  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

From Figure \[fig:mesh\_edge\_results\], we can see that in both runs the edgeLBP produces more stable descriptors, as the errors are lower than those of the meshLBP (except in one case, the model 1 in *Run2*). In our opinion the nature of the ring definition of the two methods is crucial being both methods based on the LBP concept. Indeed, the meshLBP creates rings of different size when the vertex density decreases becoming quite sparse when the number of vertices of the mesh is significantly reduced. This is not the case of the edgeLBP, as the radius of each ring is always the same ($R$), for each mesh.

Discussions and conclusive remarks {#sec:conclusions}
==================================

We defined an extension of the LBP on surfaces, whose strength is the robustness to the surface tessellation. In this paper we used this technique to successfully retrieve and classify colorimetric patterns on mesh surfaces. The edgeLBP also performed the best to the SHREC’18 track on retrieval of colorimetric patterns [@shrec18]. Besides synthetic datasets, we tested our algorithm on samples coming from a challenging dataset made of corrupted and degraded artifacts of the EU GRAVITATE project test beds [@GRAVITATE_prog], achievingpromising results. Further extensions are planned and possible. For instance, it is possible to adopt this approach for the description of geometric patterns, encoding the geometric variations with scalar properties of the mesh, like mean curvature or shape index. Moreover, we think that for full color patterns better results could be achieved using all the colorimetric information, for instance the L, a, and b channels of the CIELab space. In this direction, we are currently working on the extension of the edgeLBP to multidimensional properties. Finally, we think it is worth investigating the automatic recognition and localization of multiple patterns on surfaces. Current experiments are performed on surfaces fully characterized by a single pattern at a time and the similarity distance is defined on the global fragment skin. Next plans include the combination of the shape description step with segmentation techniques and the aggregation of parts made of vertices with similar local descriptions.

Acknowledgments {#acknowledgments .unnumbered}
===============

The work is developed within the research program of the “H2020” European project “GRAVITATE”, contract n. 665155, (2015-2018).
