# Dataset Denoising Based on Manifold Assumption

Authors: Zhonghua Hao; Shiwei Ma; Hui Chen; Jingjing Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Learning the knowledge hidden in the manifold-geometric distribution of the dataset is essential for many machine learning algorithms. However, geometric distribution is usually corrupted by noise, especially in the high-dimensional dataset. In this paper, we propose a denoising method to capture the “true” geometric structure of a high-dimensional nonrigid point cloud dataset by a variational approach. Firstly, we improve the Tikhonov model by adding a local structure term to make variational diffusion on the tangent space of the manifold. Then, we define the discrete Laplacian operator by graph theory and get an optimal solution by the Euler–Lagrange equation. Experiments show that our method could remove noise effectively on both synthetic scatter point cloud dataset and real image dataset. Furthermore, as a preprocessing step, our method could improve the robustness of manifold learning and increase the accuracy rate in the classification problem.


---

## Body

## 1. Introduction

Since objects vary gradually in the real world, the manifold assumption indicates that the data points depict the state of an object should distribute on a smooth low-dimensional manifold embedded in high-dimensional observation space [1]. Dimensionalities of the manifold are key factors that control variation of the object state. For example, in Figure 1, the images of the rotational duck toy distribute on a one-dimensional manifold (a curve) embedded in high-dimensional pixel space. Each image depicts a particular state of the duck. Although the pixel values change dramatically at these images, humans could discover easily that they are controlled by one key factor: rotation of the duck.Figure 1
Image dataset of the rotational duck toy distributes on a one-dimensional manifold [2]. The red points correspond to noiseless images. The green point correspond to the noise image.Learning the knowledge hidden in the manifold-geometric distribution of a high-dimensional dataset is essential in many machine learning algorithms. For example, manifold learning algorithms aim to discover the nonlinear geometric structure dataset by preserving different local geometric properties [3–8]. The embedding results can be further used in data visualization, motion analysis, and classification [9, 10]. Moreover, much research takes manifold assumption as a constraint condition in its objective function [11, 12]. It is worth noting that manifold assumption is applied to explain why deep learning works well recently [13–15]. This research indicates deep learning could capture the manifold structure of one kind of knowledge by powerful nonlinear mapping.However, noise is inevitable in data acquisition. For example, in Figure1, the noiseless images of the rotational duck toy (red points) should lie on a curve embedded in the pixel space. However, due to the long exposure time and camera shake, the duck becomes “brighten” and “small” in the image. The corresponding noise data point, which is marked by “N” and green color in Figure 1, does not lie on the curve because pixel values change dramatically in the noise image.Noise makes machine learning models fragile and hard to train. For example, the outlier points are difficult to handle in the classification and clustering task. Machine learning model needs to become more complex to get proper results [13]. In manifold learning algorithms, noise points make recovered embeddings difficult to capture the true manifold-geometric distribution of the dataset. The reason is that the “short circuit” phenomenon arises easily in the noise dataset which destroys the local linear structure of the manifold [16].In this paper, we propose a novel denoising method based on manifold assumption. Our aim is to obtain the data points that lie on the noiseless manifold through noise data points. Compared with the existing denoising methods, our method has two contributions worth being highlighted:(1)
Our method makes use of manifold-geometric distribution information of the dataset. Therefore, this method works for a dataset rather than a single data point.(2)
Our method improves the Tikhonov model to make the variational diffusion on the tangent space of the manifold for a high-dimensional nonrigid point cloud dataset.Our method could capture the “true” geometric structure of the noise dataset. After denoising, the key factors that control the geometric distribution of the dataset are maintained and the characteristics of individual points are removed as noise. As a preprocessing step, our method could improve the robustness of manifold learning and increase the accuracy rate in the classification problem.The rest of the paper is organized as follows: a brief review of the research on the manifold assumption is outlined in Section1. Section 2 describes the motivation and details of the proposed method. In Section 3, experiments are conducted on both synthetic and real data to evaluate our method. Section 4 concludes remarks and a discussion of future work.


## 2. Related Work

Existing denoising methods always work for the noise in a single data point, such as “Gaussian noise” or “pepper noise” [17, 18] in an image. However, these methods could not deal with the noise that distorts the geometric distribution of the dataset, such as the noise duck toy image (green point) caused by longer exposure time and camera shake in Figure 1.Only a few studies exist to deal with this problem. Gong et al. [19] proposed a local linear denoising method. This method removed noise by projecting noise data points to the tangent space of manifold which is estimated by the principal component analysis method firstly. Then, local denoised patches are aligned to get the global denoising dataset. However, the principal components may be distorted because they are calculated by the neighborhood of noise data points, which could lead to a wrong denoising result. Hao et al. [16] also utilized principal component analysis and projection method to find the noiseless data points. Therefore, it has the same problem. Moreover, many machine learning methods proposed the noise-resistant model for outliers but did not discuss denoising as an independent problem [7, 20]. For example, Zhang et al. [7] proposed an adaptive neighborhood selection method by the shrink and expand strategy to resist noise on the neighborhood of manifold.In this paper, we propose a denoising method for the dataset. This method improves the Tikhonov method by adding a local structure term. The optimal solution is obtained by minimizing the objective function through a variational diffusion approach.


## 3. Proposed Approach

LetF=f1,f2,…,fm be the noise dataset. fx∈RD is the x-th data point in F. D is the dimension number of fx. Let U=u1,u2,…,um be the noiseless dataset we want to obtain. ux∈RD is the x-th data point in U. fx=ux+ξx, ξx∈RD is the noise of fx. The goal is to recover U from F.We illustrate our method in three steps: firstly, introduce to inspiration and motivation; then, construct the objective function by improving the Tikhonov model; and finally, optimize the objective function and get the solution by taking discrete operators.


### 3.1. Inspiration and Motivation

Manifold assumption claims that the noiseless data pointux that depicts the object state (the blue points in Figure 2) should lie on a smooth manifold U (blue surface in Figure 2) embedded in observation space. However, noise points fx (red points) distribute on the noise manifold ℱ. The denoising problem is how to obtain ux on Ufrom fx on ℱ.Figure 2
Illustration of the idea of our method: obtain the noiseless blue points that lie on smooth manifold (blue surface) from the noise red points that distribute on an irregular surface (noise manifold).


### 3.2. Objective Function

The objective function is formulated in this part. Firstly, we illustrate the Tikhonov model briefly in image denoising which is similar to our problem. Then, the challenge of our problem is shown. Finally, we improve the Tikhonov model and construct the objective function for our problem.


#### 3.2.1. Tikhonov Model in the Image Denoising Problem

Our problem is similar to the image denoising problemfx,y=ux,y+ξx,y, where x and y are row and column numbers of a pixel in an image. fx,y and ux,y are pixel values at row xand column y in noise and noiseless image, respectively. ξx,y is the noise. In Figure 2, if we regard the x, y, and z coordinate of fx as row number, column number, and pixel value, then the red manifold F depicts the pattern of noise image. Therefore, the image denoising problem is to find a noiseless image U from ℱ.The Tikhonov model is one of the most classical variational models to deal with this problem [21]:(1)Eu=minu12∫|Ωu−f2dx+α2∫|Ω∇u2dx,where Ω is the image domain and dx is the area element (pixel) in Ω. ∇u is the gradient of ux. The first term ∫Ωu−f2 is “data term” that measures the Euclidean distance between ℱ and U. The second term ∫Ω∇u2dx is “smooth term” that measures the noise strength of U. Since these two terms have opposite effect, the parameter α balances these two terms. If α is small, U is close to ℱ but the noise strength is large. On the other hand, the noise becomes small but the image pattern of U is “unlike” ℱ.


#### 3.2.2. The Challenge of Our Problem

In the image denoising problem, the gradient operator is defined as [21](2)∇u=ux,y−ux−1,y,ux,y−ux,y−1T.When minimizing the “smooth term”∫Ω∇u2dx in (1), the pixel values in the image became the same, whereas the image area does not change since x and y are fixed.However, in our problem, the dataset is nonrigid and high-dimensional cloud points. Letux=ux1,ux2,…,uxD∈RD be a data point. D is the dimension number of ux. Suppose Nux is the neighborhood of ux which is determined by the KNN method:(3)Nux=uyi∈Nux,i=1,…,k.Naturally, the gradient operator is defined as(4)∇u=ux−uy1,ux−uy2,…,ux−uykT.Therefore, the “smooth term” in (1) is(5)∫Ω∇u2=∫Ω∫Nuxux−uyi2dydx.When minimizing an objective function, the “smooth term” makesux and uyi become the same point. Therefore, the “cluster” phenomenon arises in the dataset—some points are brought close together and the other points are pushed away. Therefore, the geometric structure of the manifold U (blue surface in Figure 2) will shrink to a few point clusters rather than becoming smooth. Therefore, the Tikhonov model could not be applied directly to solve our problem.


#### 3.2.3. Our Objective Function

To deal with this problem, we maintain the geometric distribution ofU by keeping the tangent linear structure when minimizing the objective function. Since the neighborhood of the manifold could be regarded as tangent space (the blue plane in Figure 3), we make the neighborhood structure of U the same as ℱ.Figure 3
Local weights in the neighborhood.Wu is the weight of the linear representation of ux by uyi that are in the neighborhood of ux. Wf is the weight of the linear representation of fx by fyi that are in the neighborhood of fx.The weight of local linear representation is utilized to depict the geometric structure of the neighborhood. The weightWf of data point fx is defined as(6)fx=∑i=1kWfifyi,where fyi∈Nfx and Wfi is the i-th component of Wf between fx and fyi. Similarly, the linear representation weight of ux is defined as Wu.The local linear structure can be maintained if we setWu the same as Wf. Then, fx could only move along the normal space of manifold when minimizing the “smooth term” in the objective function because the tangent geometric structure is fixed by Wu. Therefore, we add a “local structure term” in the Tikhonov model:(7)∫Ωux−∫NuxWfifyidy2dx,where ∫NuxWfifyidy is the linear reconstruction of ux. Thus, our objective function is(8)Eu=min12∫Ωu−f2dx+α2∫Ω∇u2dx+β2∫Ωu−WfN2dx,where α and β are balance parameters.


### 3.3. Optimal Solution

In this part, we get optimalu by minimizing objective function (8). The solution in the continuous form is calculated firstly. Then, the discrete operator is defined and plugged to get a discrete solution.


#### 3.3.1. Solution in Continuous Form

To get optimalu, we calculate the derivative of (8) with respect to u by variational approach and set it to zero:(9)E′ε=ddεEu+εη,∇u+ε∇u=ddε12∫Ωu+εη−f2dx+α2∫Ω∇u+ε∇η2dx+β2∫Ωu+εη−WfN2dx=∫Ωηu−fdx+α∫Ω∇η∇udx+β∫Ωηu−WfNdx=∫Ωηu−fdx+α∫∂Ωn⟶η∇uds−α∫ΩηΔudx+β∫Ωηu−WfNdx=η∫Ωu−f−αΔu+βu−WfNdx+α∫∂Ωn⟶η∇uds.Therefore, the Euler–Lagrange equation ofu is(10)u−f−αΔu+βu−WfN=0.Then,(11)u=f+βWfN+αΔu1+β.And the boundary condition is(12)n⟶∇u=0.


#### 3.3.2. Solution in Discrete Form

To get the discrete solution, we define the discrete Laplacian operator in (11) by spectral graph theory [22]. Firstly, the gradient of ux is defined as(13)∇wGux,y=uyi−uxWdx,yuyi∈Nux,i=1,…,k.This gradient is ak-dimensional vector because there are k data points in Nux. The subscript “wG” is abbreviated to “weighted graph.” Wdx,y is a weight vector. The component Wdx,yi should be important if ux and uyi are near. On the contrary, the component should be unimportant if ux and uyi are far away. Therefore, we define Wdx,y as(14)Wdx,y=1σ2πexp−dx,y2σ2,where dx,y is the vector of Euclidean distance between ux and uyi∈Nux. σ is the variance of dx,y. For the convenience of calculations, we set wx,y=Wdx,y. Therefore, the discrete gradient of ux is(15)∇wGux,y=uy−uxwx,yuy∈Nux.Consequently, the gradient of a vectorvx,y is (the derivation procedure is listed at “Notice” at the end of this capture):(16)∇wGv=−∑y∈Nxvy,x−vx,ywx,y.Letvx,y=∇wGux,y=uy−uxwx,y, therefore, the discrete Laplace operator of ux can be defined by(17)ΔwGu=∇wG∇wGu=∑y∈Nxuy−ux⋅wx,y−ux−uywx,y=2∑y∈Nxuy−uxwx,y.We plug the discrete Laplace operator into (11). The solution of our object energy function (8) is(18)uxk+1=fx+β∑y∈NxWx,yfy+2α∑y∈Nxuyk−uxkwx,y1+β,where the superscripts k and k+1 are the iteration step. The initial value of u is set to f. The optimal u is obtained by iteration, which ends up when Eu<ε, where Eu is the objective function value and ε is a small error we set. The boundary condition (12) could be ignored because the dataset is scattered and nonrigid cloud points.Notice:The gradient of a vectorv could be derived as follows:(19)∑x∈Ω∇wGu⋅v=∑x∈Ω∑y∈Nxuy−uxwx,yvx,y=12∑x∈Ω∑y∈Nxuy−uxwx,yvx,y+∑x∈Ω∑y∈Nxuy−uxwx,yvx,y=12∑x∈Ω∑y∈Nxuxvy,x−vx,ywx,y+12∑x∈Ω∑y∈Nxuyvx,y−vy,xwx,y=∑x∈Ω∑y∈Nxvy,x−vx,ywx,yux=−∑x∈Ω∇wGv⋅u.Therefore,(20)∇wGv=−∑y∈Nxvy,x−vx,ywx,y.


## 3.1. Inspiration and Motivation

Manifold assumption claims that the noiseless data pointux that depicts the object state (the blue points in Figure 2) should lie on a smooth manifold U (blue surface in Figure 2) embedded in observation space. However, noise points fx (red points) distribute on the noise manifold ℱ. The denoising problem is how to obtain ux on Ufrom fx on ℱ.Figure 2
Illustration of the idea of our method: obtain the noiseless blue points that lie on smooth manifold (blue surface) from the noise red points that distribute on an irregular surface (noise manifold).


## 3.2. Objective Function

The objective function is formulated in this part. Firstly, we illustrate the Tikhonov model briefly in image denoising which is similar to our problem. Then, the challenge of our problem is shown. Finally, we improve the Tikhonov model and construct the objective function for our problem.


### 3.2.1. Tikhonov Model in the Image Denoising Problem

Our problem is similar to the image denoising problemfx,y=ux,y+ξx,y, where x and y are row and column numbers of a pixel in an image. fx,y and ux,y are pixel values at row xand column y in noise and noiseless image, respectively. ξx,y is the noise. In Figure 2, if we regard the x, y, and z coordinate of fx as row number, column number, and pixel value, then the red manifold F depicts the pattern of noise image. Therefore, the image denoising problem is to find a noiseless image U from ℱ.The Tikhonov model is one of the most classical variational models to deal with this problem [21]:(1)Eu=minu12∫|Ωu−f2dx+α2∫|Ω∇u2dx,where Ω is the image domain and dx is the area element (pixel) in Ω. ∇u is the gradient of ux. The first term ∫Ωu−f2 is “data term” that measures the Euclidean distance between ℱ and U. The second term ∫Ω∇u2dx is “smooth term” that measures the noise strength of U. Since these two terms have opposite effect, the parameter α balances these two terms. If α is small, U is close to ℱ but the noise strength is large. On the other hand, the noise becomes small but the image pattern of U is “unlike” ℱ.


### 3.2.2. The Challenge of Our Problem

In the image denoising problem, the gradient operator is defined as [21](2)∇u=ux,y−ux−1,y,ux,y−ux,y−1T.When minimizing the “smooth term”∫Ω∇u2dx in (1), the pixel values in the image became the same, whereas the image area does not change since x and y are fixed.However, in our problem, the dataset is nonrigid and high-dimensional cloud points. Letux=ux1,ux2,…,uxD∈RD be a data point. D is the dimension number of ux. Suppose Nux is the neighborhood of ux which is determined by the KNN method:(3)Nux=uyi∈Nux,i=1,…,k.Naturally, the gradient operator is defined as(4)∇u=ux−uy1,ux−uy2,…,ux−uykT.Therefore, the “smooth term” in (1) is(5)∫Ω∇u2=∫Ω∫Nuxux−uyi2dydx.When minimizing an objective function, the “smooth term” makesux and uyi become the same point. Therefore, the “cluster” phenomenon arises in the dataset—some points are brought close together and the other points are pushed away. Therefore, the geometric structure of the manifold U (blue surface in Figure 2) will shrink to a few point clusters rather than becoming smooth. Therefore, the Tikhonov model could not be applied directly to solve our problem.


### 3.2.3. Our Objective Function

To deal with this problem, we maintain the geometric distribution ofU by keeping the tangent linear structure when minimizing the objective function. Since the neighborhood of the manifold could be regarded as tangent space (the blue plane in Figure 3), we make the neighborhood structure of U the same as ℱ.Figure 3
Local weights in the neighborhood.Wu is the weight of the linear representation of ux by uyi that are in the neighborhood of ux. Wf is the weight of the linear representation of fx by fyi that are in the neighborhood of fx.The weight of local linear representation is utilized to depict the geometric structure of the neighborhood. The weightWf of data point fx is defined as(6)fx=∑i=1kWfifyi,where fyi∈Nfx and Wfi is the i-th component of Wf between fx and fyi. Similarly, the linear representation weight of ux is defined as Wu.The local linear structure can be maintained if we setWu the same as Wf. Then, fx could only move along the normal space of manifold when minimizing the “smooth term” in the objective function because the tangent geometric structure is fixed by Wu. Therefore, we add a “local structure term” in the Tikhonov model:(7)∫Ωux−∫NuxWfifyidy2dx,where ∫NuxWfifyidy is the linear reconstruction of ux. Thus, our objective function is(8)Eu=min12∫Ωu−f2dx+α2∫Ω∇u2dx+β2∫Ωu−WfN2dx,where α and β are balance parameters.


## 3.2.1. Tikhonov Model in the Image Denoising Problem

Our problem is similar to the image denoising problemfx,y=ux,y+ξx,y, where x and y are row and column numbers of a pixel in an image. fx,y and ux,y are pixel values at row xand column y in noise and noiseless image, respectively. ξx,y is the noise. In Figure 2, if we regard the x, y, and z coordinate of fx as row number, column number, and pixel value, then the red manifold F depicts the pattern of noise image. Therefore, the image denoising problem is to find a noiseless image U from ℱ.The Tikhonov model is one of the most classical variational models to deal with this problem [21]:(1)Eu=minu12∫|Ωu−f2dx+α2∫|Ω∇u2dx,where Ω is the image domain and dx is the area element (pixel) in Ω. ∇u is the gradient of ux. The first term ∫Ωu−f2 is “data term” that measures the Euclidean distance between ℱ and U. The second term ∫Ω∇u2dx is “smooth term” that measures the noise strength of U. Since these two terms have opposite effect, the parameter α balances these two terms. If α is small, U is close to ℱ but the noise strength is large. On the other hand, the noise becomes small but the image pattern of U is “unlike” ℱ.


## 3.2.2. The Challenge of Our Problem

In the image denoising problem, the gradient operator is defined as [21](2)∇u=ux,y−ux−1,y,ux,y−ux,y−1T.When minimizing the “smooth term”∫Ω∇u2dx in (1), the pixel values in the image became the same, whereas the image area does not change since x and y are fixed.However, in our problem, the dataset is nonrigid and high-dimensional cloud points. Letux=ux1,ux2,…,uxD∈RD be a data point. D is the dimension number of ux. Suppose Nux is the neighborhood of ux which is determined by the KNN method:(3)Nux=uyi∈Nux,i=1,…,k.Naturally, the gradient operator is defined as(4)∇u=ux−uy1,ux−uy2,…,ux−uykT.Therefore, the “smooth term” in (1) is(5)∫Ω∇u2=∫Ω∫Nuxux−uyi2dydx.When minimizing an objective function, the “smooth term” makesux and uyi become the same point. Therefore, the “cluster” phenomenon arises in the dataset—some points are brought close together and the other points are pushed away. Therefore, the geometric structure of the manifold U (blue surface in Figure 2) will shrink to a few point clusters rather than becoming smooth. Therefore, the Tikhonov model could not be applied directly to solve our problem.


## 3.2.3. Our Objective Function

To deal with this problem, we maintain the geometric distribution ofU by keeping the tangent linear structure when minimizing the objective function. Since the neighborhood of the manifold could be regarded as tangent space (the blue plane in Figure 3), we make the neighborhood structure of U the same as ℱ.Figure 3
Local weights in the neighborhood.Wu is the weight of the linear representation of ux by uyi that are in the neighborhood of ux. Wf is the weight of the linear representation of fx by fyi that are in the neighborhood of fx.The weight of local linear representation is utilized to depict the geometric structure of the neighborhood. The weightWf of data point fx is defined as(6)fx=∑i=1kWfifyi,where fyi∈Nfx and Wfi is the i-th component of Wf between fx and fyi. Similarly, the linear representation weight of ux is defined as Wu.The local linear structure can be maintained if we setWu the same as Wf. Then, fx could only move along the normal space of manifold when minimizing the “smooth term” in the objective function because the tangent geometric structure is fixed by Wu. Therefore, we add a “local structure term” in the Tikhonov model:(7)∫Ωux−∫NuxWfifyidy2dx,where ∫NuxWfifyidy is the linear reconstruction of ux. Thus, our objective function is(8)Eu=min12∫Ωu−f2dx+α2∫Ω∇u2dx+β2∫Ωu−WfN2dx,where α and β are balance parameters.


## 3.3. Optimal Solution

In this part, we get optimalu by minimizing objective function (8). The solution in the continuous form is calculated firstly. Then, the discrete operator is defined and plugged to get a discrete solution.


### 3.3.1. Solution in Continuous Form

To get optimalu, we calculate the derivative of (8) with respect to u by variational approach and set it to zero:(9)E′ε=ddεEu+εη,∇u+ε∇u=ddε12∫Ωu+εη−f2dx+α2∫Ω∇u+ε∇η2dx+β2∫Ωu+εη−WfN2dx=∫Ωηu−fdx+α∫Ω∇η∇udx+β∫Ωηu−WfNdx=∫Ωηu−fdx+α∫∂Ωn⟶η∇uds−α∫ΩηΔudx+β∫Ωηu−WfNdx=η∫Ωu−f−αΔu+βu−WfNdx+α∫∂Ωn⟶η∇uds.Therefore, the Euler–Lagrange equation ofu is(10)u−f−αΔu+βu−WfN=0.Then,(11)u=f+βWfN+αΔu1+β.And the boundary condition is(12)n⟶∇u=0.


### 3.3.2. Solution in Discrete Form

To get the discrete solution, we define the discrete Laplacian operator in (11) by spectral graph theory [22]. Firstly, the gradient of ux is defined as(13)∇wGux,y=uyi−uxWdx,yuyi∈Nux,i=1,…,k.This gradient is ak-dimensional vector because there are k data points in Nux. The subscript “wG” is abbreviated to “weighted graph.” Wdx,y is a weight vector. The component Wdx,yi should be important if ux and uyi are near. On the contrary, the component should be unimportant if ux and uyi are far away. Therefore, we define Wdx,y as(14)Wdx,y=1σ2πexp−dx,y2σ2,where dx,y is the vector of Euclidean distance between ux and uyi∈Nux. σ is the variance of dx,y. For the convenience of calculations, we set wx,y=Wdx,y. Therefore, the discrete gradient of ux is(15)∇wGux,y=uy−uxwx,yuy∈Nux.Consequently, the gradient of a vectorvx,y is (the derivation procedure is listed at “Notice” at the end of this capture):(16)∇wGv=−∑y∈Nxvy,x−vx,ywx,y.Letvx,y=∇wGux,y=uy−uxwx,y, therefore, the discrete Laplace operator of ux can be defined by(17)ΔwGu=∇wG∇wGu=∑y∈Nxuy−ux⋅wx,y−ux−uywx,y=2∑y∈Nxuy−uxwx,y.We plug the discrete Laplace operator into (11). The solution of our object energy function (8) is(18)uxk+1=fx+β∑y∈NxWx,yfy+2α∑y∈Nxuyk−uxkwx,y1+β,where the superscripts k and k+1 are the iteration step. The initial value of u is set to f. The optimal u is obtained by iteration, which ends up when Eu<ε, where Eu is the objective function value and ε is a small error we set. The boundary condition (12) could be ignored because the dataset is scattered and nonrigid cloud points.Notice:The gradient of a vectorv could be derived as follows:(19)∑x∈Ω∇wGu⋅v=∑x∈Ω∑y∈Nxuy−uxwx,yvx,y=12∑x∈Ω∑y∈Nxuy−uxwx,yvx,y+∑x∈Ω∑y∈Nxuy−uxwx,yvx,y=12∑x∈Ω∑y∈Nxuxvy,x−vx,ywx,y+12∑x∈Ω∑y∈Nxuyvx,y−vy,xwx,y=∑x∈Ω∑y∈Nxvy,x−vx,ywx,yux=−∑x∈Ω∇wGv⋅u.Therefore,(20)∇wGv=−∑y∈Nxvy,x−vx,ywx,y.


## 3.3.1. Solution in Continuous Form

To get optimalu, we calculate the derivative of (8) with respect to u by variational approach and set it to zero:(9)E′ε=ddεEu+εη,∇u+ε∇u=ddε12∫Ωu+εη−f2dx+α2∫Ω∇u+ε∇η2dx+β2∫Ωu+εη−WfN2dx=∫Ωηu−fdx+α∫Ω∇η∇udx+β∫Ωηu−WfNdx=∫Ωηu−fdx+α∫∂Ωn⟶η∇uds−α∫ΩηΔudx+β∫Ωηu−WfNdx=η∫Ωu−f−αΔu+βu−WfNdx+α∫∂Ωn⟶η∇uds.Therefore, the Euler–Lagrange equation ofu is(10)u−f−αΔu+βu−WfN=0.Then,(11)u=f+βWfN+αΔu1+β.And the boundary condition is(12)n⟶∇u=0.


## 3.3.2. Solution in Discrete Form

To get the discrete solution, we define the discrete Laplacian operator in (11) by spectral graph theory [22]. Firstly, the gradient of ux is defined as(13)∇wGux,y=uyi−uxWdx,yuyi∈Nux,i=1,…,k.This gradient is ak-dimensional vector because there are k data points in Nux. The subscript “wG” is abbreviated to “weighted graph.” Wdx,y is a weight vector. The component Wdx,yi should be important if ux and uyi are near. On the contrary, the component should be unimportant if ux and uyi are far away. Therefore, we define Wdx,y as(14)Wdx,y=1σ2πexp−dx,y2σ2,where dx,y is the vector of Euclidean distance between ux and uyi∈Nux. σ is the variance of dx,y. For the convenience of calculations, we set wx,y=Wdx,y. Therefore, the discrete gradient of ux is(15)∇wGux,y=uy−uxwx,yuy∈Nux.Consequently, the gradient of a vectorvx,y is (the derivation procedure is listed at “Notice” at the end of this capture):(16)∇wGv=−∑y∈Nxvy,x−vx,ywx,y.Letvx,y=∇wGux,y=uy−uxwx,y, therefore, the discrete Laplace operator of ux can be defined by(17)ΔwGu=∇wG∇wGu=∑y∈Nxuy−ux⋅wx,y−ux−uywx,y=2∑y∈Nxuy−uxwx,y.We plug the discrete Laplace operator into (11). The solution of our object energy function (8) is(18)uxk+1=fx+β∑y∈NxWx,yfy+2α∑y∈Nxuyk−uxkwx,y1+β,where the superscripts k and k+1 are the iteration step. The initial value of u is set to f. The optimal u is obtained by iteration, which ends up when Eu<ε, where Eu is the objective function value and ε is a small error we set. The boundary condition (12) could be ignored because the dataset is scattered and nonrigid cloud points.Notice:The gradient of a vectorv could be derived as follows:(19)∑x∈Ω∇wGu⋅v=∑x∈Ω∑y∈Nxuy−uxwx,yvx,y=12∑x∈Ω∑y∈Nxuy−uxwx,yvx,y+∑x∈Ω∑y∈Nxuy−uxwx,yvx,y=12∑x∈Ω∑y∈Nxuxvy,x−vx,ywx,y+12∑x∈Ω∑y∈Nxuyvx,y−vy,xwx,y=∑x∈Ω∑y∈Nxvy,x−vx,ywx,yux=−∑x∈Ω∇wGv⋅u.Therefore,(20)∇wGv=−∑y∈Nxvy,x−vx,ywx,y.


## 4. Experiments

In this section, we evaluate our algorithm on both the synthetic scatter point cloud dataset and real image dataset. Then, this method is utilized as a preprocess step for manifold learning and classification task. The major parameters of our algorithm include (1) the neighborhood sizek; (2) the smooth term weight α; and (3) the local structure term weight β.


### 4.1. Experiments on Synthetic 3D Scatter Cloud Data

In this part, we test our algorithm on the classical “swiss roll” dataset. The data points are sampled from 2D manifold randomly embedded in the 3D space like a swiss roll cake. Figures4(a) and 4(b) at first row are noiseless and noise dataset at [−8, 10] and [0, 0] viewpoint, respectively. It is obvious that noise data points distribute around the “swiss roll” manifold but do not lie on it exactly. Our goal is to recover the noiseless dataset in Figure 4(a) by the noise dataset in Figure 4(b). In this experiment, we set the number of data points n=1300, KNN parameter k = 12, and the noise parameter NI=1. The MATLAB code of the swiss roll dataset is listed in Table 1.Figure 4
Denoising results with different parameters. (a) Noiseless dataset. (b) Noise dataset. (c) and (d) Denoising results withα=1 and β=1. (e) and (f) Denoising results with α=3 and β=1. Large α eliminates noise, but “cluster” phenomenon arises. (g) and (h) Denoising results with α=0.3 and β=1.
(a)(b)(c)(d)(e)(f)(g)(h)Table 1
MATLAB code for the noise swiss roll dataset.
Input: the number of datasets:n; noise parameter: NIOutput: swiss roll dataset, noiseless and noiset=3∗pi/2∗1+2∗randn,1;Height = 30∗rand (n, 1);Noiseless data =t⋅∗costheightt⋅∗sint;Noise data =t⋅∗costheightt⋅∗sint+NI∗randnn,3;The second, third, and fourth rows in Figure4 are denoising results by our method with α and β equal to (1, 1), (3, 1), and (0.3, 1), respectively. For ease of viewing, we set the denoising datasets at [−8, 10] and [0, 0] viewpoints in the left and right columns. In the right column, it is easy to see that the denoising data points are closed to the tangent space of manifold compared with (b), which show that our method is effective. Among them, (f) seems to be the best result because the denoising points are the nearest to manifold compared with (d) and (h). However, the “cluster” phenomenon arises in the denoising dataset; some points are close together and the other points are pushed away, which is easy to see in (e). The reason is that the large smooth parameter (α=3) makes geometric distribution distort when minimizing the objective function. Conversely, the “cluster” phenomenon in (g) is not serious when we set a small parameter α=0.3, but the noise is large.To conduct a quantitative comparison between noise and denoising datasets, we assess the quality of the denoising datasets by mean square error (MSE) and tangent distance error (TE). MSE is a widely used index which measures the average squared Euclidean distance difference between two datasets:(21)MSE=1N∑i=1Nui−ui∗2,where N is the point number of the dataset. ui and ui∗ are a noise data point and corresponding noiseless data point.The tangent distance error (TE) measures the distance of ui to the tangent space of the manifold. A small TE indicates that ui lies on the manifold and noise is weak. On the contrary, the noise strength is large if TE is big. For the convenience of calculations, we approximate TE as the Euclidean distance between ui and its nearest data point in the noiseless dataset. The tangent distance error (TE) is defined as(22)TE=1N∑i=1Nui−minui∗dui,ui∗2,s.t.ui∗∈U∗,where N is the number of data points, ui and ui∗ represent the denoising data point and noiseless data point, respectively. U∗ is the noiseless dataset.To evaluate our algorithm, we test seven sets ofα and β ranging from 0 to 10. MSE and TE are listed in Tables 2 and 3. When α and β equal 0, the “data term” is the only term remaining in the objective function (8). Therefore, the denoising dataset is the same as the noise dataset and the value at (α = 0, β = 0) is the errors of the noise dataset. While α is small and β is large, the “data term” and “local structure term” maintain the geometric structure of the noise dataset. Therefore, the errors at the upper right of the table are close to the errors of the noise dataset. While α is large and β is small, the “smooth term” plays a major role. It could lead to a “cluster” phenomenon which distorts the geometric structure of the dataset and make errors large at the bottom left of the table. It is able to see that the errors near the diagonal of tables are much smaller than the others.Table 2
MSE of our method (10−1).
α β00.20.50.8131002.532.532.532.532.532.532.530.22.362.302.252.272.302.352.490.53.002.672.442.342.332.282.400.83.773.182.762.552.462.262.3414.283.523.002.732.602.302.3339.637.295.544.674.222.822.301028.421.515.311.910.65.372.91Table 3
ET of our method (10−2).
α β00.20.50.8131002.012.012.012.012.012.012.010.21.701.731.741.801.811.911.950.51.681.671.691.701.701.801.910.81.741.691.661.671.681.721.8911.801.721.691.651.661.721.8732.422.121.931.821.801.661.71104.553.733.142.602.471.891.65


### 4.2. Experiments on the Image Dataset

In this part, we test our method on two real image datasets: MNIST handwritten number dataset [23] and “LLE face” dataset. Image is regarded as a point in pixel space. For example, the image in the MNIST dataset could be regarded as a point in 784-dimensional space because it has 784 pixels. Therefore, the only difference between this part to experiment 3.1 is that the dimensionality of image-point is much higher than the synthetic scatter point in 3D space.We analyze denoising images both from the subjective and objective aspects. Firstly, our method is applied to raw image datasets. Ideally, key factors that control the geometric distribution of the dataset could be maintained and the characteristics in individual images are removed as noise. Since there is no ground truth of the raw image dataset, we could only evaluate results by eyes subjectively. Secondly, we add several types of noise in an image and utilizeMSE to measure the denoising images by our method and classical image denoising methods objectively.


#### 4.2.1. Experiments on the Raw Image Dataset

We select “number 3” and “number 4” datasets in MNIST which contain 1010 and 982 images, respectively. The size of each image is28∗28 pixels. The “LLE face” dataset contains 1965 face images with different expressions and shooting angles. The size of each image is 28∗20 pixels.Figure5 shows 110 images in the “handwritten number 3” dataset. The left side is original images and the right side is the corresponding denoising images by our method. In this experiment, k=15, α=0.8, and β=1. Four typical images are marked with a box and listed in Figure 5. It can be seen that the blurring strokes become clear and the posture of number in the image is maintained.Figure 5
Denoising for the MNIST number 3 dataset. Original images and corresponding denoising images are listed in the left column and right column. The blurring strokes become clear.
(a)(b)Figure6 shows the 110 images in the “handwritten number 4” dataset. The left and right sides are original images and the corresponding denoising images by our method, respectively. In this experiment, k=15, α=8, and β=1. It can be seen that the denoising images maintain the main factors, such as the angularity of number “4.” And the individual characteristics are removed after denoising; for example, the difference of stroke width becomes small after denoising. Four typical images are marked with a box and listed in Figure 6. It is obvious that the margin of “head” of number “4” becomes large in the first two images after denoising. In the third image, the stroke width becomes broad. In the fourth image, the “bend” at the upside of the stroke is removed.Figure 6
Denoising for the MNIST number 4 dataset. Original images and corresponding denoising images are listed in the left column and right column. The stroke widths become similar, and the posture of number 4 is maintained.
(a)(b)Figure7 shows the denoising result for the LLE face dataset. This dataset contains 1965 face images and the size of each image is 28∗20 pixels. In this experiment, k=15, α=3, and β=0.8. [4] shows that this dataset distributes on the manifold that spans by two key factors: head pose and expression, where the expression reflects by lip shape in images.Figure 7
Denoising for the LLE face dataset. (a) Noise images. (b) Denoising images. Four corresponding typical images are listed. The posture of the head in the first two images is fixed after denoising. The head gets bigger in the third image. The eyes become open in the fourth image.
(a)(b)It can be seen that these two factors are maintained after denoising and the characters in the individual image are removed as noise. Four typical images are marked with a box and listed in Figure7. In the first two images, the head twists to the left and right slightly in the original dataset whereas the head pose is fixed after denoising. In the third image, the original head seems to be smaller than the other images which may be caused by camera shake. The corresponding denoising image enlarges the face, and the cheek and chin became “fat.” In the fourth image, the eyes are “open” after denoising.


#### 4.2.2. Experiments on the Noise Image

In this part, we add several different types of noise to an LLE face image. Then, our method and three classical image denoising methods are applied to these noise images. Finally,MSE is utilized to evaluate denoising images.Figure8 shows the denoising images by four denoising methods for five types of noise. The first column is a raw LLE face image. Brightness noise, Gaussian noise, salt and pepper noise, rotation noise, and scaling noise are added to the raw image which are shown in the second column, top to bottom row. The MATLAB code of noise model is listed in Table 4.Figure 8
Denoising images’ comparison. Three classical image denoising methods and our method are applied to image with five types of noise. Our method could eliminate this noise, whereas the classical image denoising methods could not deal with brightness noise, rotation noise, and scaling noise.Table 4
MATLAB code for the noise model.
Brightness noiseNoiseImage=Image×1.3Gaussian noiseNoiseImage=imnoiseImage″,localvar″,sizeImage∗0.5Salt and pepper noiseNoiseImage=imnoise,″salt&pepper″Rotation noiseNoiseImage=imrotateImage,20,″bicubic″,″crop″Scaling noiseNoiseImage=imresizeImage,1.4,″nearest″Three classical denoising methods, mean filtering, median filtering, and Tikhonov method are utilized to deal with these noise images. The corresponding denoising images are listed in the third, fourth, and fifth columns in Figure8. The images in the last column are denoising results by our method. MSE is listed below each image. In this experiment, the size of the raw LLE face image is 28∗20 pixels. In mean filtering, the size of the filter is 2∗2 pixels. In median filtering, the size of the filter is 3∗3 pixels. In the Tikhonov method, the smooth parameter is 0.3. The parameters in our method are set to k=15, α=3, and β=3.It can be seen that three classical denoising methods have no effect on brightness noise, rotation noise, and scaling noise. These noises still exist in denoising images. TheMSE even becomes larger after denoising in contrast to the noise image whereas our method has a good effect. For example, the rotation face is fixed at the fourth row and sixth column and MSE becomes smaller.The reason is that classical image denoising methods make use of the pattern information in a single image. They could not “see” the geometric distribution information of the whole image dataset whereas our method removes noise by drawing noise data points back to the noiseless manifold-geometric distribution of the image dataset.


### 4.3. Denoising Dataset for Manifold Learning

In this part, we utilize our method as a preprocessing step and compare the recovered low-dimensional embeddings of noise and denoising datasets on several manifold learning algorithms. In this experiment,α, β, and k are 1, 0.8, and 13.Figures9(a) and 9(b) are noise “swiss roll” dataset and the ground truth of the noise dataset. Figures 9(c) and 9(d) are embeddings of the noise and denoising dataset by Isomap. Figures 9(e) and 9(f) are embeddings of the noise and denoising dataset by LTSA. Figures 9(g) and 9(h) are embeddings of the noise and denoising dataset by HLLE. It is obvious that embeddings of the noise dataset could not reflect the geometric distribution of manifold since the neighborhoods easy to result in the “short circuit” phenomenon. By taking the denoising dataset, all the three manifold methods could get the proper embeddings. The results of Isomap result in the “hole” phenomenon because the calculated geodesic distance is always larger than it really is.Figure 9
Embeddings of the noise dataset. (a) Noiseless dataset. (b) Ground truth. (c) and (d) Embeddings of the noise and denoising dataset by Isomap. (e) and (f) Embeddings of the noise and denoising dataset by LTSA. (g) and (h) Embeddings of the noise and denoising dataset by HLLE.
(a)(b)(c)(d)(e)(f)(g)(h)To conduct a quantitative comparison, we assess the quality of the embeddings by three indexes: embedding error, trustworthiness error, and continuity error [8]. The embedding error E measures the squared distance from the recovered low-dimensional embeddings to the ground truth coordinates which could be defined as(23)E=∑n=1Nyn−yn∗2,where N is the number of data points and yn and yn∗ represent the embedding coordinates and ground true coordinates, respectively. This index tends to measure global structure distortion of the manifold.The trustworthiness errorT and continuity error C measure the local geometric structure distortion. The trustworthiness error measures the proportion of points that are too close together in the low-dimensional embedding and continuity error measures the proportion of points that are pushed away:(24)Tk=100×2Nk2N−3k−1∑n=1N∑m∈Unkrn,m−k,Ck=100×2Nk2N−3k−1∑n=1N∑m∈Vnkr^n,m−k,where k is the point number in the neighborhood, rn,m is the rank of the point um in the ordering according to the pairwise distance from point un in the high-dimensional space, and r^n,m is the rank of the point ym in the ordering according to the pairwise distance from point yn in low-dimensional embedding. The variables Unk and Vnk denote the neighborhood points of um in low-dimensional embedding and high-dimensional space, respectively.We test our method on several dimension reduction methods. The noise swiss roll dataset contains 1300 points. Here, we setα, β, and k to 1, 0.8, and 13. The best embedding results among several trials are selected in this experiment. The embedding error, trustworthiness error, and continuity error are listed in Tables 5–7, respectively. To show the effectiveness of our method, the errors of noise dataset, denoising dataset, and noiseless dataset are listed in three rows. It could be seen that the errors become small by taking the denoising dataset in Isomap, LLE, HLLE, LTSA, and AML. However, LE and LPP have a poor performance by taking denoising dataset.Table 5
Embedding error.
IsomapLLEHLLELTSALELPPAMLNoise dataset227.3217.880.21313.06189.5153.2189.0Denoising dataset32.7660.1331.7931.71135.4145.825.34Noiseless dataset28.7954.6313.4225.8087.29147.924.70Table 6
Trustworthiness error.
IsomapLLEHLLELTSALELPPAMLNoise dataset12.7811.464.4313.9127.488.3912.84Denoising dataset2.993.290.941.234.128.341.09Noiseless dataset1.622.090.290.924.086.740.88Table 7
Continuity error.
IsomapLLEHLLELTSALELPPAMLNoise dataset5.963.341.144.875.892.514.44Denoising dataset1.832.110.520.672.292.300.60Noiseless dataset1.571.880.240.492.342.430.44


### 4.4. Classification Experiment

In this part, we utilize our method as a preprocessing step and compare the accuracy rate of the original dataset and denoising dataset in the classification task. MNIST handwritten number dataset is selected which contains 60000 images with ten classes from numbers 0 to 9. Each class has about 6000 images and the size of each image is28∗28 pixels. To get the denoising dataset, we utilize our denoising method for these ten classes, respectively.In this experiment, we specify different numbers of images in each class as training data and utilize the remaining images as test data both in the original dataset and denoising dataset. A simple one-hidden-layer neural network is adopted as a classifier. The input layer has 784 units corresponding to the pixels in an image. The output layer has 10 units corresponding to ten categories from number zero to nine. We set 25 units in the hidden layer including a bias unit. The parameters of the network are trained by the BP method.For each classification task, we repeat 10 times and list the mean accuracy rate in Figure10. The labels “original dataset” and “denoising dataset” are raw MNIST dataset and denoising dataset with our method. The x-coordinate is the number of training images in each class and the y-coordinate is the accuracy rate. The blue and red lines are the accuracy rate of the original dataset and denoising dataset, respectively. It is obvious that the accuracy rate goes down as the number of training images decreases in each class. The performance of the denoising dataset is much better than the original dataset, especially when the training number is less than 50 in each class. The accuracy is above 96% even when there are only 10 training images in each class for the denoising dataset.Figure 10
Accuracy rate by taking different numbers of training images.The reason is that the individual characters are removed in the denoising dataset, which is shown in Figures5–7 in Section 3.2.1. The denoising datasets that distribute on a “clean” manifold expanded by key factors of the dataset could make machine learning algorithm easy to learn the geometric distribution knowledge of the dataset. It also illustrates that there is some kind of essential features to the classifier that is captured by our method.


## 4.1. Experiments on Synthetic 3D Scatter Cloud Data

In this part, we test our algorithm on the classical “swiss roll” dataset. The data points are sampled from 2D manifold randomly embedded in the 3D space like a swiss roll cake. Figures4(a) and 4(b) at first row are noiseless and noise dataset at [−8, 10] and [0, 0] viewpoint, respectively. It is obvious that noise data points distribute around the “swiss roll” manifold but do not lie on it exactly. Our goal is to recover the noiseless dataset in Figure 4(a) by the noise dataset in Figure 4(b). In this experiment, we set the number of data points n=1300, KNN parameter k = 12, and the noise parameter NI=1. The MATLAB code of the swiss roll dataset is listed in Table 1.Figure 4
Denoising results with different parameters. (a) Noiseless dataset. (b) Noise dataset. (c) and (d) Denoising results withα=1 and β=1. (e) and (f) Denoising results with α=3 and β=1. Large α eliminates noise, but “cluster” phenomenon arises. (g) and (h) Denoising results with α=0.3 and β=1.
(a)(b)(c)(d)(e)(f)(g)(h)Table 1
MATLAB code for the noise swiss roll dataset.
Input: the number of datasets:n; noise parameter: NIOutput: swiss roll dataset, noiseless and noiset=3∗pi/2∗1+2∗randn,1;Height = 30∗rand (n, 1);Noiseless data =t⋅∗costheightt⋅∗sint;Noise data =t⋅∗costheightt⋅∗sint+NI∗randnn,3;The second, third, and fourth rows in Figure4 are denoising results by our method with α and β equal to (1, 1), (3, 1), and (0.3, 1), respectively. For ease of viewing, we set the denoising datasets at [−8, 10] and [0, 0] viewpoints in the left and right columns. In the right column, it is easy to see that the denoising data points are closed to the tangent space of manifold compared with (b), which show that our method is effective. Among them, (f) seems to be the best result because the denoising points are the nearest to manifold compared with (d) and (h). However, the “cluster” phenomenon arises in the denoising dataset; some points are close together and the other points are pushed away, which is easy to see in (e). The reason is that the large smooth parameter (α=3) makes geometric distribution distort when minimizing the objective function. Conversely, the “cluster” phenomenon in (g) is not serious when we set a small parameter α=0.3, but the noise is large.To conduct a quantitative comparison between noise and denoising datasets, we assess the quality of the denoising datasets by mean square error (MSE) and tangent distance error (TE). MSE is a widely used index which measures the average squared Euclidean distance difference between two datasets:(21)MSE=1N∑i=1Nui−ui∗2,where N is the point number of the dataset. ui and ui∗ are a noise data point and corresponding noiseless data point.The tangent distance error (TE) measures the distance of ui to the tangent space of the manifold. A small TE indicates that ui lies on the manifold and noise is weak. On the contrary, the noise strength is large if TE is big. For the convenience of calculations, we approximate TE as the Euclidean distance between ui and its nearest data point in the noiseless dataset. The tangent distance error (TE) is defined as(22)TE=1N∑i=1Nui−minui∗dui,ui∗2,s.t.ui∗∈U∗,where N is the number of data points, ui and ui∗ represent the denoising data point and noiseless data point, respectively. U∗ is the noiseless dataset.To evaluate our algorithm, we test seven sets ofα and β ranging from 0 to 10. MSE and TE are listed in Tables 2 and 3. When α and β equal 0, the “data term” is the only term remaining in the objective function (8). Therefore, the denoising dataset is the same as the noise dataset and the value at (α = 0, β = 0) is the errors of the noise dataset. While α is small and β is large, the “data term” and “local structure term” maintain the geometric structure of the noise dataset. Therefore, the errors at the upper right of the table are close to the errors of the noise dataset. While α is large and β is small, the “smooth term” plays a major role. It could lead to a “cluster” phenomenon which distorts the geometric structure of the dataset and make errors large at the bottom left of the table. It is able to see that the errors near the diagonal of tables are much smaller than the others.Table 2
MSE of our method (10−1).
α β00.20.50.8131002.532.532.532.532.532.532.530.22.362.302.252.272.302.352.490.53.002.672.442.342.332.282.400.83.773.182.762.552.462.262.3414.283.523.002.732.602.302.3339.637.295.544.674.222.822.301028.421.515.311.910.65.372.91Table 3
ET of our method (10−2).
α β00.20.50.8131002.012.012.012.012.012.012.010.21.701.731.741.801.811.911.950.51.681.671.691.701.701.801.910.81.741.691.661.671.681.721.8911.801.721.691.651.661.721.8732.422.121.931.821.801.661.71104.553.733.142.602.471.891.65


## 4.2. Experiments on the Image Dataset

In this part, we test our method on two real image datasets: MNIST handwritten number dataset [23] and “LLE face” dataset. Image is regarded as a point in pixel space. For example, the image in the MNIST dataset could be regarded as a point in 784-dimensional space because it has 784 pixels. Therefore, the only difference between this part to experiment 3.1 is that the dimensionality of image-point is much higher than the synthetic scatter point in 3D space.We analyze denoising images both from the subjective and objective aspects. Firstly, our method is applied to raw image datasets. Ideally, key factors that control the geometric distribution of the dataset could be maintained and the characteristics in individual images are removed as noise. Since there is no ground truth of the raw image dataset, we could only evaluate results by eyes subjectively. Secondly, we add several types of noise in an image and utilizeMSE to measure the denoising images by our method and classical image denoising methods objectively.


### 4.2.1. Experiments on the Raw Image Dataset

We select “number 3” and “number 4” datasets in MNIST which contain 1010 and 982 images, respectively. The size of each image is28∗28 pixels. The “LLE face” dataset contains 1965 face images with different expressions and shooting angles. The size of each image is 28∗20 pixels.Figure5 shows 110 images in the “handwritten number 3” dataset. The left side is original images and the right side is the corresponding denoising images by our method. In this experiment, k=15, α=0.8, and β=1. Four typical images are marked with a box and listed in Figure 5. It can be seen that the blurring strokes become clear and the posture of number in the image is maintained.Figure 5
Denoising for the MNIST number 3 dataset. Original images and corresponding denoising images are listed in the left column and right column. The blurring strokes become clear.
(a)(b)Figure6 shows the 110 images in the “handwritten number 4” dataset. The left and right sides are original images and the corresponding denoising images by our method, respectively. In this experiment, k=15, α=8, and β=1. It can be seen that the denoising images maintain the main factors, such as the angularity of number “4.” And the individual characteristics are removed after denoising; for example, the difference of stroke width becomes small after denoising. Four typical images are marked with a box and listed in Figure 6. It is obvious that the margin of “head” of number “4” becomes large in the first two images after denoising. In the third image, the stroke width becomes broad. In the fourth image, the “bend” at the upside of the stroke is removed.Figure 6
Denoising for the MNIST number 4 dataset. Original images and corresponding denoising images are listed in the left column and right column. The stroke widths become similar, and the posture of number 4 is maintained.
(a)(b)Figure7 shows the denoising result for the LLE face dataset. This dataset contains 1965 face images and the size of each image is 28∗20 pixels. In this experiment, k=15, α=3, and β=0.8. [4] shows that this dataset distributes on the manifold that spans by two key factors: head pose and expression, where the expression reflects by lip shape in images.Figure 7
Denoising for the LLE face dataset. (a) Noise images. (b) Denoising images. Four corresponding typical images are listed. The posture of the head in the first two images is fixed after denoising. The head gets bigger in the third image. The eyes become open in the fourth image.
(a)(b)It can be seen that these two factors are maintained after denoising and the characters in the individual image are removed as noise. Four typical images are marked with a box and listed in Figure7. In the first two images, the head twists to the left and right slightly in the original dataset whereas the head pose is fixed after denoising. In the third image, the original head seems to be smaller than the other images which may be caused by camera shake. The corresponding denoising image enlarges the face, and the cheek and chin became “fat.” In the fourth image, the eyes are “open” after denoising.


### 4.2.2. Experiments on the Noise Image

In this part, we add several different types of noise to an LLE face image. Then, our method and three classical image denoising methods are applied to these noise images. Finally,MSE is utilized to evaluate denoising images.Figure8 shows the denoising images by four denoising methods for five types of noise. The first column is a raw LLE face image. Brightness noise, Gaussian noise, salt and pepper noise, rotation noise, and scaling noise are added to the raw image which are shown in the second column, top to bottom row. The MATLAB code of noise model is listed in Table 4.Figure 8
Denoising images’ comparison. Three classical image denoising methods and our method are applied to image with five types of noise. Our method could eliminate this noise, whereas the classical image denoising methods could not deal with brightness noise, rotation noise, and scaling noise.Table 4
MATLAB code for the noise model.
Brightness noiseNoiseImage=Image×1.3Gaussian noiseNoiseImage=imnoiseImage″,localvar″,sizeImage∗0.5Salt and pepper noiseNoiseImage=imnoise,″salt&pepper″Rotation noiseNoiseImage=imrotateImage,20,″bicubic″,″crop″Scaling noiseNoiseImage=imresizeImage,1.4,″nearest″Three classical denoising methods, mean filtering, median filtering, and Tikhonov method are utilized to deal with these noise images. The corresponding denoising images are listed in the third, fourth, and fifth columns in Figure8. The images in the last column are denoising results by our method. MSE is listed below each image. In this experiment, the size of the raw LLE face image is 28∗20 pixels. In mean filtering, the size of the filter is 2∗2 pixels. In median filtering, the size of the filter is 3∗3 pixels. In the Tikhonov method, the smooth parameter is 0.3. The parameters in our method are set to k=15, α=3, and β=3.It can be seen that three classical denoising methods have no effect on brightness noise, rotation noise, and scaling noise. These noises still exist in denoising images. TheMSE even becomes larger after denoising in contrast to the noise image whereas our method has a good effect. For example, the rotation face is fixed at the fourth row and sixth column and MSE becomes smaller.The reason is that classical image denoising methods make use of the pattern information in a single image. They could not “see” the geometric distribution information of the whole image dataset whereas our method removes noise by drawing noise data points back to the noiseless manifold-geometric distribution of the image dataset.


## 4.2.1. Experiments on the Raw Image Dataset

We select “number 3” and “number 4” datasets in MNIST which contain 1010 and 982 images, respectively. The size of each image is28∗28 pixels. The “LLE face” dataset contains 1965 face images with different expressions and shooting angles. The size of each image is 28∗20 pixels.Figure5 shows 110 images in the “handwritten number 3” dataset. The left side is original images and the right side is the corresponding denoising images by our method. In this experiment, k=15, α=0.8, and β=1. Four typical images are marked with a box and listed in Figure 5. It can be seen that the blurring strokes become clear and the posture of number in the image is maintained.Figure 5
Denoising for the MNIST number 3 dataset. Original images and corresponding denoising images are listed in the left column and right column. The blurring strokes become clear.
(a)(b)Figure6 shows the 110 images in the “handwritten number 4” dataset. The left and right sides are original images and the corresponding denoising images by our method, respectively. In this experiment, k=15, α=8, and β=1. It can be seen that the denoising images maintain the main factors, such as the angularity of number “4.” And the individual characteristics are removed after denoising; for example, the difference of stroke width becomes small after denoising. Four typical images are marked with a box and listed in Figure 6. It is obvious that the margin of “head” of number “4” becomes large in the first two images after denoising. In the third image, the stroke width becomes broad. In the fourth image, the “bend” at the upside of the stroke is removed.Figure 6
Denoising for the MNIST number 4 dataset. Original images and corresponding denoising images are listed in the left column and right column. The stroke widths become similar, and the posture of number 4 is maintained.
(a)(b)Figure7 shows the denoising result for the LLE face dataset. This dataset contains 1965 face images and the size of each image is 28∗20 pixels. In this experiment, k=15, α=3, and β=0.8. [4] shows that this dataset distributes on the manifold that spans by two key factors: head pose and expression, where the expression reflects by lip shape in images.Figure 7
Denoising for the LLE face dataset. (a) Noise images. (b) Denoising images. Four corresponding typical images are listed. The posture of the head in the first two images is fixed after denoising. The head gets bigger in the third image. The eyes become open in the fourth image.
(a)(b)It can be seen that these two factors are maintained after denoising and the characters in the individual image are removed as noise. Four typical images are marked with a box and listed in Figure7. In the first two images, the head twists to the left and right slightly in the original dataset whereas the head pose is fixed after denoising. In the third image, the original head seems to be smaller than the other images which may be caused by camera shake. The corresponding denoising image enlarges the face, and the cheek and chin became “fat.” In the fourth image, the eyes are “open” after denoising.


## 4.2.2. Experiments on the Noise Image

In this part, we add several different types of noise to an LLE face image. Then, our method and three classical image denoising methods are applied to these noise images. Finally,MSE is utilized to evaluate denoising images.Figure8 shows the denoising images by four denoising methods for five types of noise. The first column is a raw LLE face image. Brightness noise, Gaussian noise, salt and pepper noise, rotation noise, and scaling noise are added to the raw image which are shown in the second column, top to bottom row. The MATLAB code of noise model is listed in Table 4.Figure 8
Denoising images’ comparison. Three classical image denoising methods and our method are applied to image with five types of noise. Our method could eliminate this noise, whereas the classical image denoising methods could not deal with brightness noise, rotation noise, and scaling noise.Table 4
MATLAB code for the noise model.
Brightness noiseNoiseImage=Image×1.3Gaussian noiseNoiseImage=imnoiseImage″,localvar″,sizeImage∗0.5Salt and pepper noiseNoiseImage=imnoise,″salt&pepper″Rotation noiseNoiseImage=imrotateImage,20,″bicubic″,″crop″Scaling noiseNoiseImage=imresizeImage,1.4,″nearest″Three classical denoising methods, mean filtering, median filtering, and Tikhonov method are utilized to deal with these noise images. The corresponding denoising images are listed in the third, fourth, and fifth columns in Figure8. The images in the last column are denoising results by our method. MSE is listed below each image. In this experiment, the size of the raw LLE face image is 28∗20 pixels. In mean filtering, the size of the filter is 2∗2 pixels. In median filtering, the size of the filter is 3∗3 pixels. In the Tikhonov method, the smooth parameter is 0.3. The parameters in our method are set to k=15, α=3, and β=3.It can be seen that three classical denoising methods have no effect on brightness noise, rotation noise, and scaling noise. These noises still exist in denoising images. TheMSE even becomes larger after denoising in contrast to the noise image whereas our method has a good effect. For example, the rotation face is fixed at the fourth row and sixth column and MSE becomes smaller.The reason is that classical image denoising methods make use of the pattern information in a single image. They could not “see” the geometric distribution information of the whole image dataset whereas our method removes noise by drawing noise data points back to the noiseless manifold-geometric distribution of the image dataset.


## 4.3. Denoising Dataset for Manifold Learning

In this part, we utilize our method as a preprocessing step and compare the recovered low-dimensional embeddings of noise and denoising datasets on several manifold learning algorithms. In this experiment,α, β, and k are 1, 0.8, and 13.Figures9(a) and 9(b) are noise “swiss roll” dataset and the ground truth of the noise dataset. Figures 9(c) and 9(d) are embeddings of the noise and denoising dataset by Isomap. Figures 9(e) and 9(f) are embeddings of the noise and denoising dataset by LTSA. Figures 9(g) and 9(h) are embeddings of the noise and denoising dataset by HLLE. It is obvious that embeddings of the noise dataset could not reflect the geometric distribution of manifold since the neighborhoods easy to result in the “short circuit” phenomenon. By taking the denoising dataset, all the three manifold methods could get the proper embeddings. The results of Isomap result in the “hole” phenomenon because the calculated geodesic distance is always larger than it really is.Figure 9
Embeddings of the noise dataset. (a) Noiseless dataset. (b) Ground truth. (c) and (d) Embeddings of the noise and denoising dataset by Isomap. (e) and (f) Embeddings of the noise and denoising dataset by LTSA. (g) and (h) Embeddings of the noise and denoising dataset by HLLE.
(a)(b)(c)(d)(e)(f)(g)(h)To conduct a quantitative comparison, we assess the quality of the embeddings by three indexes: embedding error, trustworthiness error, and continuity error [8]. The embedding error E measures the squared distance from the recovered low-dimensional embeddings to the ground truth coordinates which could be defined as(23)E=∑n=1Nyn−yn∗2,where N is the number of data points and yn and yn∗ represent the embedding coordinates and ground true coordinates, respectively. This index tends to measure global structure distortion of the manifold.The trustworthiness errorT and continuity error C measure the local geometric structure distortion. The trustworthiness error measures the proportion of points that are too close together in the low-dimensional embedding and continuity error measures the proportion of points that are pushed away:(24)Tk=100×2Nk2N−3k−1∑n=1N∑m∈Unkrn,m−k,Ck=100×2Nk2N−3k−1∑n=1N∑m∈Vnkr^n,m−k,where k is the point number in the neighborhood, rn,m is the rank of the point um in the ordering according to the pairwise distance from point un in the high-dimensional space, and r^n,m is the rank of the point ym in the ordering according to the pairwise distance from point yn in low-dimensional embedding. The variables Unk and Vnk denote the neighborhood points of um in low-dimensional embedding and high-dimensional space, respectively.We test our method on several dimension reduction methods. The noise swiss roll dataset contains 1300 points. Here, we setα, β, and k to 1, 0.8, and 13. The best embedding results among several trials are selected in this experiment. The embedding error, trustworthiness error, and continuity error are listed in Tables 5–7, respectively. To show the effectiveness of our method, the errors of noise dataset, denoising dataset, and noiseless dataset are listed in three rows. It could be seen that the errors become small by taking the denoising dataset in Isomap, LLE, HLLE, LTSA, and AML. However, LE and LPP have a poor performance by taking denoising dataset.Table 5
Embedding error.
IsomapLLEHLLELTSALELPPAMLNoise dataset227.3217.880.21313.06189.5153.2189.0Denoising dataset32.7660.1331.7931.71135.4145.825.34Noiseless dataset28.7954.6313.4225.8087.29147.924.70Table 6
Trustworthiness error.
IsomapLLEHLLELTSALELPPAMLNoise dataset12.7811.464.4313.9127.488.3912.84Denoising dataset2.993.290.941.234.128.341.09Noiseless dataset1.622.090.290.924.086.740.88Table 7
Continuity error.
IsomapLLEHLLELTSALELPPAMLNoise dataset5.963.341.144.875.892.514.44Denoising dataset1.832.110.520.672.292.300.60Noiseless dataset1.571.880.240.492.342.430.44


## 4.4. Classification Experiment

In this part, we utilize our method as a preprocessing step and compare the accuracy rate of the original dataset and denoising dataset in the classification task. MNIST handwritten number dataset is selected which contains 60000 images with ten classes from numbers 0 to 9. Each class has about 6000 images and the size of each image is28∗28 pixels. To get the denoising dataset, we utilize our denoising method for these ten classes, respectively.In this experiment, we specify different numbers of images in each class as training data and utilize the remaining images as test data both in the original dataset and denoising dataset. A simple one-hidden-layer neural network is adopted as a classifier. The input layer has 784 units corresponding to the pixels in an image. The output layer has 10 units corresponding to ten categories from number zero to nine. We set 25 units in the hidden layer including a bias unit. The parameters of the network are trained by the BP method.For each classification task, we repeat 10 times and list the mean accuracy rate in Figure10. The labels “original dataset” and “denoising dataset” are raw MNIST dataset and denoising dataset with our method. The x-coordinate is the number of training images in each class and the y-coordinate is the accuracy rate. The blue and red lines are the accuracy rate of the original dataset and denoising dataset, respectively. It is obvious that the accuracy rate goes down as the number of training images decreases in each class. The performance of the denoising dataset is much better than the original dataset, especially when the training number is less than 50 in each class. The accuracy is above 96% even when there are only 10 training images in each class for the denoising dataset.Figure 10
Accuracy rate by taking different numbers of training images.The reason is that the individual characters are removed in the denoising dataset, which is shown in Figures5–7 in Section 3.2.1. The denoising datasets that distribute on a “clean” manifold expanded by key factors of the dataset could make machine learning algorithm easy to learn the geometric distribution knowledge of the dataset. It also illustrates that there is some kind of essential features to the classifier that is captured by our method.


## 5. Conclusion and Future Work

We propose a denoising method for the dataset rather than a single data point. This method is inspired by the manifold assumption. A local structure term is added in the Tikhonov model to make the noise points diffuse on the tangent space of the manifold. Our method could prominent the major factors hidden in the dataset and remove characteristics of the individual data point. Experiments show that our method could eliminate noise effectively on both synthetic scatter point cloud dataset and real image dataset. And as a preprocessing step, our method could improve the robustness of manifold learning and increase the accuracy rate of the classification problem. However, the parameters are sensitive in this model because the optimal solution is calculated by iteration. The geometric distribution of the dataset is distorted when the smooth term parameter is large. On the contrary, the noise intensity is still large after denoising. Our future work will focus on this problem.



---

*Source: 6432929-2021-01-18.xml*