SAC-NMF-Driven Graphical Feature Analysis and Applications

Abstract

Feature analysis is a fundamental research area in computer graphics; meanwhile, meaningful and part-aware feature bases are always demanding. This paper proposes a framework for conducting feature analysis on a three-dimensional (3D) model by introducing modified Non-negative Matrix Factorization (NMF) model into the graphical feature space and push forward further applications. By analyzing and utilizing the intrinsic ideas behind NMF, we propose conducting the factorization on feature matrices constructed based on descriptors or graphs, which provides a simple but effective way to raise compressed and scale-aware descriptors. In order to enable part-aware model analysis, we modify the NMF model to be sparse and constrained regarding to both bases and encodings, which gives rise to Sparse and Constrained Non-negative Matrix Factorization (SAC-NMF). Subsequently, by adapting the analytical components (including hidden variables, bases, and encodings) to design descriptors, several applications have been easily but effectively realized. The extensive experimental results demonstrate that the proposed framework has many attractive advantages, such as being efficient, extendable, and so forth.

1. Introduction

Feature space analysis has, all the time, attracted broad attention, due to its fundamental role in assisting graphical tasks, such as shape understanding, recognition, decomposition, etc. [1,2,3]. Undoubtedly, effective tools or techniques for analyzing the feature space are always demanding, especially part-aware or meaning bases. The well-known techniques usually factorize the original feature space/matrix into bases and coefficients (in product form) or main and residue parts (in additive form). However, there rarely exists any factorization result that is visually meaningful or part-aware, which could afford a more intuitive understanding of the geometric shape. Although deep learning methods [4,5] have achieved great successes, the feature maps obtained as the intermediate products (that actually act as bases and the inputs for the next layer of the network) could not promise to be part-aware. Therefore, we propose factorizing the feature space of three-dimensional (3D) models into meaningful and part-aware hidden variables and bases to facilitate further graphical applications.

The task of feature analysis mainly depends on suitable representations of the data concerned. A proper representation should be capable of making the latent structure of the data explicit, so that further analytical works can be more easily carried out. The techniques to factorize the feature space include Principle Component Analysis (PCA) [6], Eigenvalue Decomposition (EVD) [7], Independent Component Analysis (ICA) [8], Low-rank and Sparse decomposition (LRS) [9], Vector Quantization (VQ) [10], etc. In addition to the above feature bases, the local and global signal-based bases, e.g., wavelets [11] and Fourier functions [12], are also frequently used by the researchers. All of the these bases have, to varying extents, helped in enabling the related graphical applications. However, since the calculating operations in the above factorization processes are not constrained to addition, the obtained bases or encodings are either global-defined or with negative signs. Inspired by the Non-negative Matrix Factorization (NMF)-driven applications (esp. face recognition) in computer vision [13,14,15,16] and the related work to factorize the affinity matrix in graphics [17], we propose encoding the 3D model with part-aware bases that afford visually meaningful tools for further applications.

NMF has been receiving increasing attention during the recent years for its ability to decompose the original images into meaningful objects or parts. Starting from the initial introduction of NMF in face recognition [13], it has seen numerous variations during these years. Because the standard NMF has some intrinsic shortcomings, e.g., it is only applicable to nonnegative data and the interpretability of parts-based presentation is weak, and it fails to fully explore the latent structure of concerned data and labeling information. Therefore, a series of variations [18,19,20] have been proposed. Although the variations have dug out more regarding the intrinsic nature of the data, the formats of data concerned are mostly constrained to images, which is not natural to be extended to 3D models. Therefore, we propose introducing NMF in order to analyze the feature space of 3D models, and the format of feature matrix is more general and more extendable when compared to images or signals.

In this paper, we propose a novel framework for conducting feature analysis on 3D models and push forward further graphical applications, as shown in Figure 1. We introduce Sparse and Constrained Non-negative Matrix Factorization (SAC-NMF) onto the feature matrix, which may be extracted from one single model or a pair of models, depending on specific applications. This kind of feature space analysis can undoubtedly enable joint analysis across the models concerned. By introducing the SAC-NMF, we could afford additive and part-aware bases, encodings, and hidden variables, which can be adapted for the construction of various descriptors according to applications. The applications that are concerned in our paper mainly include symmetry detection, correspondence analysis, segmentation, and saliency detection. The contributions of our paper can be summarized as the following three items:

• We propose a simple, but efficient, framework for conducting feature analysis on 3D models by introducing NMF onto a feature matrix.
• We introduce the SAC-NMF to achieve sparse and part-aware analytical components (bases, encodings, and hidden variables) for feature analysis.
• We adapt analytical components to construct descriptors to empower various applications, including symmetry detection, correspondence, segmentation, and saliency detection.

2. Related Work

The most related works include the researches on NMF and its variations as well as the bases for feature space analysis.

Standard NMF. NMF [13] was first proposed for acquiring explicit representations for the face images. The constraint of non-negativity enforces both the bases and encodings to be non-negative, naturally making the data in only additive fashion, which is more physically soundable when comparing to other representations achieved by PCA, VQ, and so on. Additionally, the additive fashion also makes the decomposition results more interpretable, with human’s perception in part-based representation. In addition to non-negativity, the low-rank and sparse properties of the factorization results of NMF are also appealing to the researchers. The sparse encodings provide natural descriptors for further applications. Additionally, the applications on image recognition and classification [21,22,23,24,25,26,27] pushed by NMF inspire us to introduce it for feature space analysis.

The Modified Versions of NMF. Because increasing attentions have been paid to the exploitation of NMF, numerous modified versions have been proposed for specific applications. The standard NMF model only learns non-negative base images in Euclidean space; however, the latent structure contained has not been well exploited. The later works have found that the high-dimensional data actually lie on a nonlinear and low-dimensional manifold [18,19], thus the modified versions of NMF are proposed for catching the key information of the structure. Cai et al. [28] proposed a method to preserve the local structure of the data via graph constructed based on the k nearest neighbors, which describes the local geometry. Aditionally, at the same time, Gu et al. proposed the NPNMF method [20] to capture the local geometric variations via neighbors, and this is based on the idea that each single data point can be represented by its neighbors. A series of supervised versions of NMF have been raised in order to take advantage of the labeled knowledge. Fisher NMF [29] was introduced by dividing the inter-class and intra-class scatters via adding a regularization term. Later on, Zafeiriou et al. [30] also introduced the scatters of inter-class and intra-class to be the discriminant constraint, inducing the discriminant version of NMF.

Bases for Feature Analysis. Bases play essential rules in feature space analysis for applications in various areas. The well-known bases in graphical applications mainly include the eigen functions [7], the principle vectors got from PCA [6], etc. Additionally, the signal-based bases mainly include the wavelets and graph wavelets [11,31], which are localized, and the flourier bases [12], which are globalized. The above bases for feature space are known to be capable of representing the data and providing information for further graphical applications. In the realistic applications, the bases are preferred to be parts-aware or visually meaningful. However, the above bases seem to be inexplicable for the real problems. Furthermore, the non-negativity property of NMF can induce the purely additive operations in the factorization process, which can cater to the human perception that parts are combined in an additive fashion to form an object well. Hence, object-based or part-aware bases for feature analysis are demanding.

3. Construction of NMF-Based Analytical Components

3.1. Standard NMF Model

The standard NMF model was proposed in the area of computer vision for face recognition, where the data matrix consists of facial images. We denote the data matrix as $\mathbf{I}\in {\mathbb{R}}^{M\times N}$, each column of which represents one of the N images with M pixel values. Subsequently, the standard NMF model aims to factorize it into two non-negative matrices, and we denote them as $\mathbf{W}\in {\mathbb{R}}^{M\times K}$ and $\mathbf{H}\in {\mathbb{R}}^{K\times N}$ (where K is generally chosen, so that $(M+N)K<MN$ and $K<min\{M,N\}$). The standard NMF model is given, as follows:

$$\underset{\mathbf{W},\mathbf{H}}{min}{\Vert \mathbf{I}-\mathbf{W}\mathbf{H}\Vert }_F^{2}s.t.\mathbf{W}\ge 0and\mathbf{H}\ge 0,$$

(1)

where, the ${\Vert ·\Vert }_F$ denotes the Frobenius norm. The constraint of nonnegativity on $\mathbf{W}$ and $\mathbf{H}$ enables NMF to obtain part-aware representations of the images. A number of researches have been carried out on the applications of NMF to images or texts; however, rare has been done to transfer the factorization ideas onto 3D models or general kind of data matrix.

3.2. Analytical Components

Before introducing NMF to 3D model analysis, we first conduct the in-depth analysis on the NMF model and the obtained analytical components. Additionally, this will provide more insights on how NMF functions on the data matrix.

Basis and Encodings. The optimization of NMF model actually seeks to find the approximate reconstruction of the data matrix as $\mathbf{I}\approx \mathbf{W}\mathbf{H}$. For any i and j, the element-wise approximation can be expressed as:

$${\mathbf{I}}_{ij}\approx \sum _k^K{\mathbf{W}}_{ik}{\mathbf{H}}_{kj}$$

(2)

We follow the original notions (as in [13]) on the factorization results in order to name the columns $\{w_k={\mathbf{W}}_{\cdot ,k}\}$ ($k\in (1,2,\cdots ,K)$) of $\mathbf{W}$ as the bases and the columns $\{h_l={\mathbf{H}}_{\cdot ,l}\}$ ($l\in (1,2,\cdots ,N)$) of $\mathbf{H}$ as the encodings. The bases actually are the alternative representations of the data. As for the data matrix that consists of facial images, the bases are the parts-based images as visualized in Figure 1. One encoding from $\mathbf{H}$ consists of the coefficients by which a facial image is represented with a linear combination of the basis images. Additionally, an encoding is in one-to-one correspondence with a image in the data matrix. The part-aware bases and encodings can help to analyze the data in the data matrix from the aspects of factorization and reconstruction.

Visible and Hidden Variables. Subsequently, we analyze the components in $\mathbf{I}$ and $\mathbf{H}$ in a row-wise way. The rows $\left\{{\mathbf{I}}_{i,\cdot }\right\}$ ($i\in (1,2,\cdots ,M)$) of $\mathbf{I}$ are named as the visible variables, as can be seen in Figure 2. Additionally, the rows $\left\{{\mathbf{H}}_{j,\cdot }\right\}$ ($j\in (1,2,\cdots ,K)$) of $\mathbf{H}$ are named as the hidden variables. One visible variable in the data matrix consisting of images actually refers to the value of one pixel. The matrix element ${\mathbf{W}}_{ij}$ quantifies the amount of influence that the j-th hidden variable ${\mathbf{H}}_{j,\cdot }$ has on the i-th visible variable ${\mathbf{I}}_{i,\cdot }$, as shown in the lower part of Figure 2. The fan-out connections between one hidden variable and all of the visible variables demonstrate that one single hidden variable influences multiple visible variables, which can also be seen from the relationship ${\mathbf{I}}_{i,\cdot }={\sum }_{j=1}^K{\mathbf{W}}_{ij}{\mathbf{H}}_{j,\cdot }$, as can be seen from the network. Because $\left\{{\mathbf{W}}_{ij}\right\}$ are restricted to be nonnegative, only additive operations are allowed. Additionally, this enables the coaction of the visible variables and parts-based factorization results, which inspires us to introduce the NMF to general feature matrix.

4. SAC-NMF on Feature Space

4.1. Construction of Feature Matrix on 3D Model

As can be seen from the above section, the elements of the data matrix for NMF are well organized (esp. the visible variables are pixels of the images, which are organized in order). For the 3D model, we propose constructing the data matrix based on the descriptions of vertices or facets. Actually, various kinds of descriptors can be incorporated, we, in this paper, mainly introduce two methods to construct the data matrix (here, referring to the feature matrix $\mathbf{F}\in {\mathbb{R}}^{M\times N}$), namely, descriptor-based and graph-based methods.

Firstly, we introduce the descriptor-based method. The visible variables in the data matrix correspond to the values of certain pixels, as shown in the above section. Inspired by this, we propose to incorporate the multi-scale descriptors into $\mathbf{F}$. Take the Heat Kernel Signatures (HKSs) [32] as an example. For a given point x on the model, its HKS can be denoted as $HKS(x,t)=k_t(x,x)$ ($t>0$). The HKS describes the local geometry of scale t around point x. Therefore, if different values of t are set, we can obtain the multi-scale descriptions of x. The $ij$-th element of $\mathbf{F}(i,j)$ is assigned with $HKS(t_i,x_j)$, namely, the $t_i$ scale descriptor of the j-th vertice of the model, as shown in Figure 3. The visible variables are the rows of the feature matrix, namely, $HKS(t_i,\dot{)}$ ($i=1,2,\cdots ,M$), which can be visualized as in Figure 3a (the parameter M can be empirically set as 200 for the HKSs descriptors). As for different applications, the multi-scale descriptor-based feature matrix can be constructed in various ways, we will demonstrate more on this in the next section.

Subsequently, we introduce the graph-based way to construct the feature matrix. The feature matrix now is defined as the affinity matrix of the nodes consisting of the facets of the mesh models. Given the facets of the model concerned as $\left\{f_i\right\}$ ($i=1,2,\cdots ,N$), we denote the affinity between the i-th and the j-the facet as ${\mathbf{A}}_{ij}$. Here, $\mathbf{F}=\mathbf{A}$ and $\mathbf{A}\in {\mathbb{R}}^{N\times N}$, which is defined as:

$${\mathbf{A}}_{ij}=\left\{\begin{array}{ccc}{e}^{(-\frac{d(c_i,c_j)}{{\sigma }_c^2}-\frac{\left|\right|n_i-n_j{\left|\right|}^2}{{\sigma }_n^2})}\hfill & & if{f}_{i}and{f}_{j}areadjacent\hfill \\ e^{(-\frac{d(c_i,c_j)}{{\sigma }_c^2})}\hfill & & else\hfill \end{array}\right.,$$

(3)

where $c_i$ and $n_i$ denote the centroid and normal of $f_i$, $d(c_i,c_j)$ denotes the geodesic distance between the two facets, and the variance parameters can be empirically set as ${\sigma }_c=mean\left(d(c_i,c_j)\right)(i,j\in 1,...,N)$ and ${\sigma }_n=0.1$. The i-th visible variable of $\mathbf{A}$ is the affinity between the i-th facet and other facets, as shown in Figure 3c. Additionally, each column of $\mathbf{A}$ can also be seen as a descriptor of the facet concerned.

4.2. SAC-NMF Model

As stated in Section 2, the NMF model can induce the coaction among the visible variables. Thus, we can utilize this property of NMF in order to analyze the feature matrix from the perspective of factorization. Take the data matrix $\mathbf{F}=HKS$ as an example, different scales of descriptions are overlapped, as shown in Figure 3a, in other words, the high-dimensional descriptor for each vertice is redundant in multi-scale description. By conducting NMF on $\mathbf{F}$, we can obtain the hidden variables as shown in Figure 3f. Here, the 3D model is rendered with vertices’ color values as each of the hidden variable (with the colormap ranging from blue to red). It is clear that NMF induces the low-dimensional encodings that correspond to the high-dimensional HKSs descriptors. At the same time, NMF helps to obtain the relatively isolated hidden variables through coaction among visible variables. However, there still exists overlap cases among the hidden variables.

Therefore, we propose adding sparse and norm constraints on both the bases and the encodings. The $l_1$-norm is a well-known selection for inducing sparsity. Accordingly, we first propose penalizing the $\mathbf{W}$ with $l_1$-norm to enhance the coactions. However, the drawback of $l_1$-norm should be considered. That is, the correlated elements could not be guaranteed to be simultaneously set to be non-zero in the result, which is due to that the $l_1$-norm can only induce sparseness but not smoothness. In comparison, $l_2$-norm is capable of inducing smoothness but not sparseness. This inspires us to simultaneously incorporate the two kinds of norms to formulate our SAC-NMF, as follows:

$$\begin{array}{cc}\hfill & \underset{\mathbf{W},\mathbf{H}}{min}{\Vert \mathbf{F}-\mathbf{W}\mathbf{H}\Vert }_F^2+\sum _{i=1}^N(\frac{\alpha }{2}\Vert w_i{\Vert }_2^2+\beta \Vert w_i{\Vert }_1)+\sum _{i=1}^K(\frac{\lambda }{2}{\Vert h_i\Vert }_2^2+\gamma {\Vert h_i\Vert }_1)\hfill \\ \hfill & s.t.\mathbf{W}\ge 0and\mathbf{H}\ge 0,\hfill \end{array}$$

(4)

where $\alpha$, $\beta$, $\lambda$, and $\gamma$ are the parameters to control the related items, and they could be set according to the specific needs of different applications, which will be stated in the next section. Figure 3g shows the hidden variables that were achieved via our SAC-NMF. It is clear that the hidden variables are more isolated compared to those in Figure 3f, thus making the low-dimensional descriptors (encodings) more discriminative. Additionally, the function of our sparsity and norm constraints will be further demonstrated in the applications. More factorization results of our SAC-NMF on $\mathbf{F}=HKS$ are shown in Figure 4.

Additionally, we devise the multiplicative updating rules for the above sparse NMF model, as follows:

$$\left\{\begin{array}{c}\mathbf{W}=\mathbf{W}\ast \frac{\mathbf{F}{\mathbf{H}}^T}{\mathbf{W}\mathbf{H}{\mathbf{H}}^T+\alpha \mathbf{W}+\beta }\hfill \\ \mathbf{H}=\mathbf{H}\ast \frac{{\mathbf{W}}^T\mathbf{F}}{{\mathbf{W}}^T\mathbf{W}\mathbf{H}+\lambda \mathbf{H}+\gamma }\hfill \end{array}\right.,$$

(5)

where $\mathbf{W}\ast \mathbf{H}$ and $\frac{\mathbf{W}}{\mathbf{H}}$ are the element-wise multiplication and division operators of matrices $\mathbf{W}$ and $\mathbf{H}$, respectively. The above multiplicative updating rules are easy to be implemented and they can achieve relatively stable results. However, the algorithm is not guaranteed to converge to a stationary point. As an alternative, non-negative quadratic programming (NNQP) may be adopted in order to solve $\mathbf{W}$ and $\mathbf{H}$ alternatively, as stated in [16].

5. SAC-NMF-Driven Graphical Applications

In this section, we will demonstrate how to apply our SAC-NMF model to our feature matrices constructed in different ways. Additionally, various applications including symmetry detection, correspondence, segmentation, and saliency detection will be introduced.

5.1. Symmetry Detection and Correspondence

Firstly, we introduce how to apply our SAC-NMF model that is based on descriptor-based feature matrix to symmetry detection and correspondence.

Here, the descriptor-based feature matrix is constructed via another two multi-scale descriptors. One is based on the local-to-global contours describing the shape context, and the other is a heat-diffusion-based description. For the first part, as done in [33], we introduce bi-harmonic distance [34] in order to set the contours for each vertex. The bi-harmonic distance between vertex $v_i$ and $v_j$ (as stated in [34]) is defined as:

$$D_{bh}{(i,j)}^2=\sum _{k=1}^{m_1}\frac{{({\chi }_k\left(i\right)-{\chi }_k\left(j\right))}^2}{{\lambda }_k^2},$$

(6)

where $\left\{{\lambda }_k\right\}$ and $\left\{{\chi }_k(·)\right\}$ denote the first $m_1$ non-zero eigenvalues and their related eigenfunctions of the Laplacian–Beltrami Operator [35]. Subsequently, the contours around each vertex can be achieved, and the contours are capable of depicting the multi-scale geometric feature very well. Additionally, we then exploit the contour-based statistics to depict the local neighborhood of each vertex. For the set of points on each contour, we compute the Euclidean distances between the points and their barycenter, and denote them as $\left\{d_i\right\}$. Additionally, we introduce the probability distribution based on $\left\{d_i\right\}$. With these preparation, we can finally define a local-to-global multi-scale descriptor for each vertex $v_i$ as:

$${\mathbf{f}}_i^1={[c_1,{cs}_1,c_2,{cs}_2,...,c_k,{cs}_{m_2}]}^T,$$

(7)

where $c_j$ is the perimeter (with normalization) of the j-th contour, ${cs}_j$ is the statistics of this contour based on the distances $\left\{d_i\right\}$, and $m_2$ denote the contours’ number. Through extensive experiments, we find that the statistics of ${cs}_j={\{c{s}_j^h\}}_{h=1,...,15}$ with $m_2=100$ can afford ideal results. It can be seen that the shape context that is constructed in this way captures the local-to-global geometric variations very well. Besides, with all of the models normalized in the unit boxes, the shape context holds the favorable properties of both scale-invariant and rotation-invariant.

As for the second part of the descriptor, we introduce the Wave Kernel Signatures [36] in order to describe the multi-scale geometric feature of the model from the perspective of physics-driven heat diffusion. Subsequently, the second part of the descriptor can be denoted as:

$$\begin{array}{c}\hfill {\mathbf{f}}_i^2={[WK{S}_{t_1},WK{S}_{t_2},...,WK{S}_{t_l}]}^T,\end{array}$$

(8)

where, $t_1$ to $t_l$ denote the time scales, and l is empirically set to 100 in all of our experiments. Finally, the above two parts are assembled together to contribute to the final multi-scale shape descriptor, as:

$${\mathbf{f}}_i={\left[{{\mathbf{f}}_i^1}^T{{\mathbf{f}}_i^2}^T\right]}^T.$$

(9)

Here, we just show two different ways of designing the multi-scale descriptors, and more alternatives can be incorporated to meet the needs of different applications.

Symmetry Detection. Symmetry detection is one of the most classical graphical applications and discriminative descriptors play essential roles in the detection of symmetric elements. Here, in our paper, we demonstrate the discrimination of our descriptors designed based on the hidden variables from feature matrix constructed based on Equation (9) and the SAC-NMF with the parameters set as $(\alpha ,\beta ,\lambda ,\gamma )=(0.8,0.1,0.1,0.4)$. Because symmetry detection is processed on one single model, we design the descriptors for symmetry analysis as $s_p=\frac{\overline{h_i}}{max\left\{\overline{h_i}\right\}}$ ($p\in 1,...,N$), where $\left\{\overline{h_i}\right\}$ is a subset of $\left\{h_i\right\}$ containing the top $max\left\{h_i\right\}$ values of $\left\{h_i\right\}$ (which we empirically select the top 80% values). Subsequently, we define the distance between two vertexes as:

$$S(p,q)=\Vert s_p-s_q{\Vert }^2.$$

(10)

With this distance measurement, we could obtain a vector in order to measure the similarities between the vertex concerned and all the other vertexes on the model. Additionally, naturally, the minimum value among the vector refers to the most probable symmetric point on the same model. However, if the minimum value is larger than a threshold (which can be empirically set as 10% of the maximum value of the vector), then the vertex concerned is supposed to be a non-symmetric vertex, namely, it does not have a symmetric point within the model itself. With these settings, our method can efficiently figure out the symmetry on each model, as shown in Figure 5. In order to make the illustration visually clear, we just show several representative symmetric pairs in this figure. We can easily see that, by utilizing our discriminative descriptors, the simple distance measurement can afford ideal detection results. It should be emphasized that, in addition to the global symmetric model in Figure 5a, for the partial symmetric model shown in Figure 5b–d, our method can detect the partially symmetric part exactly.

Correspondence. Our framework to analyze the feature space is extendable to multiple models; here, we demonstrate its extendability via correspondence between two models. When considering the specific need of correspondence analysis, we construct the feature matrix by assembling the descriptors from both of the two concerned models, which is denoted as ${\mathbf{F}}_c=\left[{\mathbf{F}}^1{\mathbf{F}}^2\right]$, where ${\mathbf{F}}^i$ is constructed as in Equation (9). Subsequently, the hidden variables are achieved via SAC-NMF (with the parameters set as $(\alpha ,\beta ,\lambda ,\gamma )=(0.8,0.1,0.1,0.6)$) on ${\mathbf{F}}_c$. We denote the hidden variables here as ${\mathbf{H}}_c=\left[{\mathbf{H}}^1{\mathbf{H}}^2\right]$. Afterwards, the feature space of the two models can be represented with the shared bases and encodings, make the co-analysis of the two models possible. Here, we specifically design the descriptors based on ${\mathbf{H}}_c$ in the same way as introduced in symmetry analysis. As we all know, the symmetry problem in correspondence should not be neglected. Thus, in order to deal with the symmetry problem, we turn to detect the symmetric points on the each model firstly, and then select the vertices that are non-symmetric. Subsequently, we introduce the technique in [37] to consider angle compatibilities among assignments to solve the problem. With these settings, our method achieves the ideal results, as shown in Figure 6. It is clear that, even for the complex cases as in (a) and (d), the correspondences that are detected by our method are still meaningful and exact.

5.2. Segmentation and Saliency Detection

In this subsection, we will demonstrate how to apply our framework to the problem of segmentation and saliency detection. Here, we utilize the graph-based feature matrix, as introduced in the previous section, namely, $\mathbf{F}=\mathbf{A}$. Because the feature matrix is square matrix, the bases obtained can be visualized on the model, as will be shown later.

Segmentation. Segmentation is a direct application of our SAC-NMF-based feature analysis. Each column of $\mathbf{A}$ is actually the descriptor of the concerned facet depicting the relationship between the concerned facet and the other facets, as we stated in the previous section. Thus, when the SAC-NMF is conducted, we can directly obtain the cluster information from the encodings $\left\{{\mathbf{H}}_{\cdot ,l}\right\}$ ($l\in (1,2,\cdots ,N)$). That is, the segmentation that the i-th facet belongs to is $ma{x}_j\left\{{\mathbf{H}}_{j,i}\right\}$. The bases obtained and the segmentation results on the tele-alien and armadillo models are as shown in Figure 7. It is clear that the bases are part-aware and isolated from each other due to the constraints in the SAC-NMF model. With such bases, the corresponding encodings naturally provide the clustering information.

Saliency Detection. As for the application of saliency detection, we also utilize the same settings (the construction of feature matrix and parameters in SAC-NMF model) as those in segmentation. Numerous researches have proposed different viewpoints towards evaluation criterions on 3D saliency, including local geometric changes, curvatures, global sparseness, etc. Here, we propose defining the saliency from a more natural aspect, namely, the main parts constituting the model should be considered to be salient. Additionally, the bases obtained in our work are part-aware, so we add up the main bases in order to form the 3D saliency. That is, the saliency values of the facets on the 3D model as assigned as $su{m}_j\left\{\overline{w_j}\right\}$, where $\left\{\overline{w_j}\right\}$ is a subset of $\left\{w_i\right\}$ containing the top $max\left\{w_j\right\}$ values of $\left\{w_j\right\}$ (which we empirically select the top 50 % values). Figure 8 shows the illustrations of saliency detection results that are based on the sum of bases, and the last column shows the saliency detection results on the three models. In order to show the additive bases for saliency detection, we illustrate the saliency with an increasing number of feature bases, which also demonstrates the character of our saliency detection results.

6. More Experiments and Discussion

In this section, we will demonstrate more about the properties and performances of our framework through experiments conducted in different aspects. All of our experiments were conducted on a 3.5 GHz Intel^® Core™ i7 computer with 16 GB memory (Santa Clara, CA, USA). The run time for each separate functional section of our framework is listed in

Table 1. Run Time for Each Functional Section.

Model	Vertices	Timing (s)
		Descriptor	Factorization	Symmetry
Dinosaur	14 K	3.42	2.40	1.22
Dog	26 K	4.94	3.63	1.78
Armadillo	34 K	6.28	4.87	2.56
Santa	75 K	8.73	6.82	3.51
Dragon	430 K	16.54	17.62	5.02

and, here, for the applications, we just show the run time for symmetry detection (for visual clearness).

6.1. Parameter Settings

The parameters in our framework mainly include the those in the construction of descriptors (M, ${\sigma }_c$, ${\sigma }_n$, l) and those in SAC-NMF model ($(\alpha ,\beta ,\lambda ,\gamma )$ and K). Most of the above parameters can be set empirically, and the control parameters $(\alpha ,\beta ,\lambda ,\gamma )$ can be set according to applications, and values around $(0.8,0.1,0.1,0.4)$ can afford ideal results. Here, we mainly demonstrate the setting and influence of parameter K, which is a key parameter that controls the number of the bases and encodings. Here, we adopt the HKS-based feature matrix for analysis. From the different rows of Figure 9, it can be seen that. when K is set to different values, the obtained hidden variables change gradually. Larger values correspond to more specific coactions among the descriptors, which affords more detailed part-aware hidden variables. In our paper, we propose an automatical method to set K, which is set due to the maximum value of $h_i$. We denote $mean\left\{\mathbf{H}\right\}$ as the mean value of $\mathbf{H}$, and, if $max\left\{h_i\right\}<mean\left\{\mathbf{H}\right\}$ during the iterative optimization process, the iteration process stops.

6.2. Properties of Our Framework

This section will demonstrate the properties of the proposed framework, which mainly include the robustness and discrimination. Firstly, we show the joint hidden variables on two deformable centour models as shown in the first row of Figure 10. Here, the joint feature matrix is constructed based on HKSs. Because the HKSs descriptors are mainly based on the eigenvalues and eigenfunctions, and the models under isometric deformation share the same eigenvalues and eigenfunctions, the shared features on the two models can be exactly detected. Subsequently, we show the case when the factorization is carried on models with large variations. As can be seen in the second row of Figure 10, the dog model and cat model have relatively large variations in the geometric shapes, but they also have similarities. By constructing the feature matrix based on multi-scale contours (with the descriptions based on contour perimeters distance distribution), the joint feature analysis is as done in the application of correspondence. The joint analytical components can figure out the joint key features on the two models, as shown in Figure 10. We just show four similar body parts that were detected on the two models for visual clearness. It is clear that the robustness of our framework can help to empower the correspondence detection between models holding large shape variations or even from different categories.

6.3. Comparisons

Because the main purpose of our framework is proposing new feature bases and descriptors for further graphical applications. This section will mainly make comparisons with the related works in the acquisition of feature bases, and the comparisons on the application results will also be shown. Firstly, we compare our encodings with the eigen functions achieved via EVD [7], the multi-scale HKSs [32], and global intrinsic symmetric invariant functions (GISIFs) proposed in [38] as shown in Figure 11. We construct the contours in order to show the value variations of these bases. The blue areas with no contour represent the zero-value regions. It can be seen that our bases are more sparse and parts-aware when comparing to the others.

Subsequently, we make comparisons on the bases’ robustness to model quality. Here, we compare with GISIFs [38], since the bases in this work are also proposed to detect symmetry on 3D models. Figure 12 shows the bases achieved by GISIFs and our method. The bases achieved on low-quality models are highlighted with the dark rectangles, and the high-quality models are highlighted with the red rectangles). It is clear that GISIFs performs unstably on the low-quality model with obvious asymmetry, while our method achieves stable factorization results, which are visualized to be symmetric and part-aware, thus can help to detect symmetry when models are not provided in high quality.

In order to further demonstrate the characteristics of our framework, we also make comparisons with the most related work of Mcgraw et al. [17] and Liu et al. [39] in segmentation and with the related works in saliency detection. The segmentation results of [17,39] are shown in (a) and (b), respectively, as can be seen from Figure 13. Spectral mesh segmentation presented in [39] can achieve idea results for most models; however, it requires SVD decomposition process together with kmeans clustering, which are time consuming. Sparse-NMF on affinity [17] can achieve ideal results when the segments’ boundaries are distinct as the chair in Figure 13a, while it cannot promise good results on the others. Additionally, our method can achieve ideal segmentation results on different model due to the design of feature matrix and SAC-NMF. To make quantitative comparisons, we utilize the evaluations introduced in the Princeton Segmentation Benchmark, which consists of models from Human, Cup, Glasses, and so on. Here, we show the segmentation errors in

Table 2. Comparisons on Segmentation (Per-category Rand Index errors of segmenting the Princeton Shape Benchmarks ).

Method	Human		Cup		Glasses		Plane		Ant
	Reduced	Normal	Reduced	Normal	Reduced	Normal	Reduced	Normal	Reduced	Normal
Mcgraw  [17]	17.9	12.6	15.6	13.6	14.4	10.1	18.6	11.5	4.7	3.9
Liu  [39]	22.9	17.6	35.8	23.6	20.4	14.2	25.6	18.6	6.5	4.7
Ours	11.9	12.3	9.9	9.9	10.1	9.8	9.2	9.2	2.2	1.9

. It is clear that, our method can achieve the relative low segmentation errors on both the normal models and reduced models. Additionally, this also demonstrates the robustness of our method to the number of vertices on the 3D models.

Last but not least, we make comparisons with Lee et al. [40], Wu et al. [41], and Song et al. [3] in saliency detection. As can be seen from Figure 14, our proposed saliency detected based on the part-aware feature bases can figure out the salient regions, which bridges the local details and global structures of the model concerned. Additionally, this is in accordance with human’s perception in the recognition of salient objects.

7. Conclusions and Discussion

This paper has presented a framework for acquiring new feature bases and encodings via SAC-NMF conducted in the feature space. Our framework generalizes both the feature space set up on 3D models and the NMF model for factorizatin-based analysis. To set up the feature matrix, we propose the descriptor-based and graph-based methods for multi-scale feature description, setting the base for SAC-NMF in order to realize the coaction between different scales. Our SAC-NMF adds the norm and sparseness constraints on both the bases and encodings, providing the alternatives for different applications. Our paper has made full use of the analytical components (bases, encodings, and hidden variables) in order to construct descriptors for a series of applications. The extensive experiments in our paper have demonstrated the extendability, robustness, and stability of our framework.

Because of the page limit of the paper, a further wide exploration of applications of our framework is beyond its scope. Accordingly, our future work will concentrate more on the construction of feature space for specific applications and the modification of NMF model to cater to the need of different applications.