In this paper, we compare performance of several dimension reduction techniques, namely SVD, NMF and SDD.The qualitative comparison is evaluated on a collection of bars. We compare the quality of these methods from on the base of the visual impact. We also compare dimension reduction techniques SVD and HO-SVD on tensors - 3D bars. V. Sn´aˇsel, K. Richta, J. Pokorny´ (Eds.): Dateso 2008, pp. 49-60, ISBN 978-80-248-1746-0.
In order to perform object recognition (no mater which one) it is necessary to learn representations of the underlying characteristic components. Such components correspond to object-parts, or features. These components can occur in different configurations to form many distinct images. Identifying the underlying components which are combined to form images is thus essential for learning the perceptual representations necessary for performing object recognition.
The application area of feature extraction on binary datasets addresses many
problem areas, such as association rule mining, itemsets used for market basket analysis,
discovery of regulation patterns in DNA microarray experiments, etc. For simplicity
sake we used the wellk-nown bars problem (see e.g. [
In this paper we will concentrate on the last category – other feature extraction methods which use known dimension reduction techniques and clustering for automatic feature extraction.
In this paper we will use the bars collection as a benchmark collection. The bars
problem (and its variations) is a benchmark task for the learning of independent image
features (Fo¨ildia´k [
8
One of the well-known methods of feature extraction is the singular value decomposition (SVD) which was already successfully used for automatic feature extraction.
We extended the bars problem to 3 dimensions, using planes instead of lines. The input cube contains several planes, which may or may not be parallel to x, y and z axes.
The straightforward approach to image indexing is to transform the 2D images into
a single vector. This is often done by concatenating all the rows of an image into a
single image vector [
The rest of this paper is organized as follows. The second section explains dimension reduction methods, which were used for classic 2D bars problem. The third section mentions CubeSVD, which was originaly used for the 3D bars problem. Then in the fourth section we describe experimental results and finally in the section five we made some conclusions. 2
We used four promising methods of dimension reduction for our comparison – Singular Value Decomposition (SVD), Semi-Discrete Decomposition (SDD) and Non-negative Matrix Factorization (NMF). All of them are briefly described bellow. 2.1
SVD [
Formally, we decompose the matrix of images A by singular value decomposition (SVD), calculating singular values and singular vectors of A.
We have matrix A, which is an n × m rank- r matrix (where m ≥ n without loss of generality) and values σ1, . . . , σr are calculated from eigenvalues of matrix AAT as σi = √λi. Based on them, we can calculate column-orthonormal matrices U = (u1, . . . , un) and V = (v1, . . . , vn), where U T U = In a V T V = Im, and a diagonal matrix Σ = diag(σ1, . . . , σn), where σi > 0 for i ≤ r, σi ≥ σi+1 and σr+1 = · · · = σn = 0.
The decomposition
A = U ΣV T is called singular decomposition of matrix A and the numbers σ1, . . . , σr are singular values of the matrix A. Columns of U (or V ) are called left (or right) singular vectors of matrix A.
Now we have a decomposition of the original matrix of images A. We get r nonzero singular numbers, where r is the rank of the original matrix A. Because the singular values usually fall quickly, we can take only k greatest singular values with the corresponding singular vector coordinates and create a k-reduced singular decomposition of A.
Let us have k (0 < k < r) and singular value decomposition of A
A = U ΣV T ≈ Ak = (UkU0) We call Ak = UkΣkVkT a k-reduced singular value decomposition (rank- k SVD). Instead of the Ak matrix, a matrix of image vectors in reduced space Dk = ΣkVkT is used in SVD as the representation of image collection. The image vectors (columns in Dk) are now represented as points in k-dimensional space (the feature-space ). represent the matrices Uk, Σk, VkT . 2.2
The SDD is one of other LSI methods, proposed recently for text retrieval in [
To improve the required storage size and query time, the semi-discrete decomposition was defined as
A ≈ Ak = XkDkYkT , (3) where each coordinate of the matrices Xk and Yk is constrained to have entries from the set ϕ = {−1, 0, 1}, and the matrix Dk is a diagonal matrix with positive coordinates.
The SDD does not reproduce A exactly, even if k = n, but it uses very little storage with respect to the observed accuracy of the approximation. A rank- k SDD (although from mathematical standpoint it is a sum on rank- 1 matrices) requires the storage of k(m + n) values from the set {−1, 0, 1} and k scalars. The scalars need to be only single precision because the algorithm is self-correcting. The SDD approximation is formed iteratively.
The optimal choice of the triplets (xi, di, yi) for given k can be determined using greedy algorithm, based on the residual Rk = A − Ak−1 (where A0 is a zero matrix). 2.3
The NMF [
The original NMF method tries to minimize the Frobenius norm of the difference between A and A0k using Wm,iHn ||V − W H||2F as the criterion in the minimization problem.
Recently, a new method was proposed in [
Hj problem. This approach is yields better results for sparse matrices.
Unlike in SVD, the base vectors are not ordered from the most general one and we have to calculate the decomposition for each value of k separately. A tensor is a higher order generalization of a vector. Vector is a first order tensor and a matrix is a second order tensor. The order of a tensor A ∈ RI1×I2×···×IN is N. Elements of A is denoted as ai1...in...iN where 1 ≤ in ≤ IN . Two basic operations are for calculation of CubeSVD: the unfolding of a tensor A A(n) and the mode-n product of a tensor A and matrix M A ×(n) M .
The operation unfolding unfolds the tensor A into matrix A(n) along order N. Each
column of tensor A(n) is composed of ai1...in...iN where in varies and the order indices
are fixed. The operations unfolding are illustrated in Figure 2 for third order tensor. See
[
The n-mode product of a tensor A ∈ RI1×I2×···×IN by a matrix M ∈ RJn×In is an I1 × I2 × · · · × In−1 × Jn × In+1 × · · · × IN -tensor of which the entries are given by (A ×n M )i1···in−1jnin+1···iN =
X ai1···in−1inin+1···iN mjnin
in
See [
Matrix SVD can be rewritten as A = Σ ×1 V (1) ×2 V (2) in terms of n-mode
products. CubeSVD is a generalization of SVD and was described in [
A = S ×1 V1 ×2 V2 ×3 · · · ×N VN as illustrated in Figure 3 for N = 3.
S is called core tensor. S is in general a full tensor, instead of being pseudodiagonal
(this would mean that nonzero elements could only occur when the indices i1 = i2 =
· · · = iN ). S has the property of all-orthogonality [
kSin=1k ≥ kSin=2k ≥ · · · ≥ kSin=Ink ≥ 0 4
For testing of above mentioned methods, we used generic collection of 1600 32 × 32 black-and-white images containing different combinations of horizontal and vertical lines (bars). The probabilities of bars to occur in images were the same and equal to 10/64, i.e. images contain 10 bars in average. An example of several images from generated collection is shown in Figure 4.
Many of tested methods were able to generate a set of base images or factors, which should ideally record all possible bar positions. However, not all methods were truly successful in this.
With SVD, we obtain classic singular vectors, the most general being among the first. The first few are shown in Figure 5. We can se, that the bars are not separated and different shades of gray appear.
The NMF methods yield different results. The original NMF method, based on the adjustment of random matrices W and H provides hardly-recognizable images even for k = 100 and 1000 iterations (we used 100 iterations for other experiments). Moreover, these base images still contain significant salt and pepper noise and have a bad contrast. The factors are shown in Figure 6. We must also note, that the NMF decomposition will yield slightly different results each time it is run, because the matrix(es) are pre-filled with random values.
The SDD method differs slightly from previous methods, since each factor contains only values {−1, 0, 1}. Gray in the factors shown in Figure 8 represents 0; −1 and 1 are represented with black and white respectively.
The base vectors in Figure 8 can be divided into three categories: 1. Base vectors containing only one bar. 2. Base vectors containing one horizontal and one vertical bar. 3. Other base vectors, containing several bars and in some cases even noise. 5
For testing of CubeSVD method, we use several collections of 8 × 8 × 8 3-dimensional cubes. We create 2 types of test collections. The first type contains 2 collections with 15 cubes each which were used for local feature extraction (each cube was decomposed separately). The first collection contains cubes which are crossed by 2 perpendicular planes (Figure 9a). The second collection contains cubes crossed by 3 planes - 2 perpendicular and 1 skewed (Figure 9b). The resulting number of singular values was between 1 and 8 (full CubeSVD).
The second type contains 4 collections with 1000 cubes each which were used for collection-based feature extraction. The first collection contains cubes with one skewed plane, second collection contains cubes with 2 skewed planes and so on. Example cubes for each collection is depicted in Figure 10.
As a measure for comparing similarity between original and reduced cubes we used the Frobenius norm (without calculating the square root)
F 2(O, R) = X X X(O[i, j, k] − R[i, j, k])2 i j
k 5.1
In the first experiment we applied CubeSVD and SVD algorithm on the first two collections for extracting local features. Results for the first collection with 2 perpendicular planes are depicted in Figure 11 for 6 singular values and are depicted on Figure 12 for 2 singular values. Values of Frobenius norm are shown in tables 1 and 2.
It can be seen CubeSVD extracts all of the original bars in Figure 11, while the SVD with the same rank ignored one of the bars, while reconstructing the other two more sharply. This is even more visible in Figure 12, where all bars in CubeSVD are slightly recorded, but classic SVD reconstructs one of the bars perfectly, adding noise to other areas. We see, that this behavior leads to lower Frobenius norm in Tables 1 and 2 for th classic SVD, which satisfies the condition that the value for SVD should be minimal for given rank k. 6
Since the CubeSVD method provided only one singular value for planes parallel to the axes, which was to be expected, the experiments were done on planes both perpendicular and skewed.
It seems, that the original SVD performed better than CubeSVD, based on the Frobenius norm, but the visual inspection of reduced tensors shows the reason – whilst the horizontal bars were reconstructed nearly perfectly, the vertical ones deteriorated more quickly. On the other hand, the CubeSVD tried to minimize the overall error.
We are currently studying the collection-based feature extraction of 3D bars, where the number of singular values ranges from 1 to 512 for 8 × 8 × 8 cubes, compared to 8 singular values for high-order SVD. The classic SVD results for 1 to 8 singular values mentioned in previous section are not satisfactory.
We are currently extending our CubeSVD implementation to support tensors of 4 and mode dimensions and preparing to test the High-order SDD and NMF methods against their 2D counterparts.