Description
Machine perception
2021/2022
Create folder assignment6 that you will use during this assignment. Unpack the content of the assignment6.zip that you download from the course webpage the folder. Save the solutions for the assignments as Python scripts assignment6 folder. In order complete the assignment you have present these files the teaching assistant. Some assignments contain questions that require sketching, writing manual calculation. Write these answers down and bring them the presentation as well. The tasks that marked with (cid:70) optional. Without completing them you get at points for the assignment. The maximum total amount of points for each assignment is 100. Each optional task has the amount of additional points written next it.
At the defense, the obligatory tasks must implemented correctly and completely.
If your implementation is incomplete, you will not able defend the assignment.
Introduction
In this assignment we will first work with simple example of the direct PCA method for ease of visualization. We will then experiment with the dual PCA method in the case of compact face description and try some of the nice properties of such description. about the theory of PCA and its applications found in (section pages 507 515).
Exercise Direct PCA method
The primary purpose of the PCA method is reduction of dimensionality. This means that we want find such linear transformation of the input data that will describe the data in low dimensional orthogonal space (which also called subspace) while losing the minimal amount of information needed reconstruct the data. subspace is defined by its basis vectors. Let us first repeat the direct calculation of the basis vectors with the PCA method. we assume that the input data is structured as column vector with size ×
In the algorithm we that in first steps of the PCA method we compute the mean value and the covariance method of the data. These the parameters that define Gaussian distribution. As we will later refer this distribution we should give it little attention. We have already introduced Gaussian distribution in Assignment where we have used special case of such distribution construct Gaussian kernel. In that case the distribution had mean value of zero and diagonal
Algorithm : The direct PCA algorithm.
Build matrix of size × that we combine input entries as sequence:
= . . . , xN ]
Calculate the mean value of the data: µ =
(cid:80)
Center the data: Xd = − µ, − µ, . . . , xN − µ]
Compute the covariance matrix: =
Compute SVD of the covariance matrix:
(cid:80)
− µ)(xi − µ)T =
−1XdXT
d
= USVT The matrix is of size × its columns represent eigenvectors of the matrix The corresponding eigenvalues saved in diagonal matrix and sorted in descending order. The columns in therefore represent orthogonal basis (subspace) while the eigenvalues give us the level of scattering of the data along the corresponding eigenvector.
new input entry xq is projected in the PCA space (subspace) by first centering it
using µ, and then multiply it with the matrix of eigenvectors: = (xq − µ).
The transformation from the subspace the original space is done using equation:
xq = Uy + µ.
Figure displays display of Gaussian distribution, shows the same distri- bution in using ellipse.
covariance matrix with equal covariance along the and axis. The general formula for Gaussian distribution is
=
√
d
2π
(cid:16)
−
exp
− µ)T C−1(x − µ)
(cid:17)
.
Figure shows example of Gaussian distribution where the values the z axis display the probability of Image shows alternative illustration, where we border at which the ellipse contains the of all probability density. Points used compute the mean value and the covariance used draw Gaussian distribution also shown in the right image.
How calculate eigenvectors and eigenvalues analytically?
Let us briefly repeat how calculate eigenvectors and eigenvalues of square matrix with size × analytically. Consider matrix Z, that we get if we multiply unit matrix of size × with constant value, e.g., Z = λI. If we subtract this matrix from and we get determinant 0, we have transformed into singular matrix:
− λI| ≡ 0.
The values that satisfy the equation above called eigenvalues of the matrix For matrix we compute eigenvalues λi. product of eigenvalues equals the determinant of the matrix: = (cid:81)m λi. Each eigenvalue λi corresponds eigenvector Eigenvectors mutually perpendicular (the dot product of eigenvectors is 0).
For eigenvalue λi we compute the eigenvector of size by setting up the following
equation:
− λiI)xi ≡ 0.
The solution of the equation gives us the elements of the eigenvector up the level of scale. That means that the equation solved by infinite number of vectors that only differ in scale. In practice we pick value for the first element and then calculate other elements of the vector. In the end we change the scale of the vector that its length becomes (unit vector). Unit eigenvector for λi is defined as ei = xi/||xi||.
Solve the following assignment by hand for practice: You given points and D(6, Calculate the eigenvectors and eigenvalues for the given of points.
simple example of direct PCA
Write script calculate and visualize PCA from data from the file points.txt (as always, the first column contains the axis and the second column the axis). Plot the points and draw the representation of the Gaussian distribution using drawEllipse from the supplementary material. Follow the Algorithm compute the eigenvectors and eigenvalues of the PCA subspace.
The matrix contains the eigenvectors that represent the basis of our PCA space. Draw the eigenvectors the plot from the previous task. Their origin should lie at the mean of the data µ. Since both vectors have the length better way for visualizing them is multiply each vector with the corresponding eigenvalue1. Draw the first eigenvector with red and the second with green.
Question: What you notice about the relationship between the eigenvectors and the data? What happens the eigenvectors if you change the data add points?
1Eigenvalue tells us the variance of the data along its corresponding eigenvector. If you multiply the eigenvector with the square root of the eigenvalue you will visualize the standard deviation along the eigenvector.
The eigenvalues represent the reconstruction error we incur if we discard the corre- sponding eigenvector. Plot the cumulative graph of the eigenvalues and normalize it the largest value will From the graph determine how many percent of the information will we retain if we discard the second eigenvector. put it differently, what percent of the variance is explained just by using the first eigenvector?
(d) remove the direction of the lowest variance from the input data. This means we will project the data into the subspace of the first eigenvector. We this by transforming the data into the PCA space then setting 0 the components corresponding the eigenvectors we want remove. The resulting points then transformed back the original space. Project each of the input points PCA space, then project them back Cartesian space by multiplying them by the diminished matrix
Question: What happens the reconstructed points? Where is the data projected
For the point qpoint = , calculate the closest point from the input data (using Euclidean distance). Which point is the closest? Then, project all the points (in- cluding qpoint) PCA subspace and remove the variation in the direction of the second vector. Calculate the distances again. Which point is the closest qpoint Visualize the reconstruction.
Exercise The dual PCA method
When analyzing image data, the dimensionality become very large (much larger than the number of elements in the input), the direct method of computing eigenvectors we used previously is longer suitable. E.g. if we have 10000-dimensional data, this would produce covariance matrix of size 10000×10000. we close hitting the limits of computer memory. As the number of data samples is lower than the dimensionality we use the dual PCA method. The main difference between this and the direct approach is is steps and (compare Algorithm Algorithm
For our requirements it is necessary only correctly calculate eigenvectors and eigenvalues up the scale factor. Therefore implement the dual method according
the Algorithm and test it using the data from points.txt. Verify whether you get the same eigenvectors (matrix as with the Algorithm The first eigenvectors should the same as with the Algorithm The Algorithm gives you larger matrix however, all eigenvectors but the first equal zero. For the projection from and the subspace you leave the matrix as it is.
Project the data from the previous assignment the PCA space using matrix and then project the data back again in the original space. If you have implemented the method correctly, you will get the original data (up the numerical error).
Algorithm : The dual PCA algorithm.
Build matrix of size × that we combine input entries as sequence:
= . . . , xN ]
Calculate the mean value of the data: µ =
(cid:80)
Center the data: Xd = − µ, − µ, . . . , xN − µ] Compute the dual covariance matrix: = m−1XT Compute singular value decomposition (SVD) of the dual covariance matrix, = USVT . Then compute the basis of the eigenvector space as: = XdU S(m−1). Note: it is expected that only first few of the (the lower columns of the eigenvectors will differ from 0.
(cid:113)
d Xd.
new input entry xq is projected in the PCA space (subspace) by first centering it
using µ, and then multiply it with the matrix of eigenvectors: = (xq − µ).
The transformation from the subspace the original space is done using equation:
xq = Uy + µ.
Exercise Image decomposition examples
we will use the dual PCA method computer vision problem. In the supplemen- tary material there series of images. Each series contains images of face under different lighting conditions. Your task will analyze each series using the PCA method.
Data preparation: Firstly, we have formulate the problem in way that is compatible with the PCA method. Since PCA operates points in space, we represent grayscale image of size × as point in mn-dimensional space if we reshape it into vector. Write function that reads all the images from of the series transforms them into grayscale reshapes them using np.reshape and stacks the resulting column vectors into matrix of size × mn.
Using dual PCA: Use dual PCA the vectors of images. Write function that takes the matrix of image vectors as input and returns the eigenvectors of the PCA subspace and the mean of the input data.
Note: In step of Algorithm careful when computing the inverse of the as some of the eigenvalues very close 0. Division by zero cause numerical errors when computing matrix inverse. You have take into account that the
matrix is diagonal matrix and must therefore have non-zero diagonal elements. way of solving this numerical problem is that we add very small constant value the diagonal elements, e.g.
Transform the first eigenvectors using the np.reshape function back into matrix and display them as images. What the resulting images represent (both numerically and in the context of faces)?
Project the first image from the series the PCA space and then back again. Is the result the same? What you notice when you change dimension of the vector in the image space (e.g. component with index 0 and display the image? Repeat similar procedure for vector in the PCA space (project image in the PCA space, change of the first components zero and project the image back in the image space and display it as image). What is the difference? How many pixels changed by the first operation and how many by the second2?
Effect of the number of components the reconstruction: Take random image and project it into the PCA space. Then change the vector in the PCA space by retaining only the first first components and setting the remaining components 0. Project the resulting vector back the image space and display it as image. Repeat the procedure for the first and eigenvector. Display the resulting vectors together figure. What you notice?
(d) (cid:70) points) Informativeness of each component: Each eigenvector holds information that defines some aspect of the PCA space. By changing the values of
2visualize the difference by subtracting original image from the reprojected .
vector in periodic way, we observe how different weights for eigenvector affect the reconstructed image.
Use the second series of images for this task. Take the average photo that you compute based all images in the series3. Project the average image PCA space. Then, select of the important eigenvectors and manually its corresponding weight in the projected vector some value of your choice. Project the modified vector back image space and observe the change.
In order the changes easier, write script that goes over range of ues for your selected eigenvector. smoothly change the values, use np.sin and np.linspace as well as some scaling factor show the differences strongly. Also, use plt.draw in combination with plt.pause display the results as animated sequence of images.
Hint: We recommend the value range of about and the scaling factor of around
Modify the script change parameters at the same in circular way (i.e. using both np.sin and np.cos). Experiment with different eigenvector pairs and report your observations.
(cid:70) points) Reconstruction of foreign image: The PCA space is build upon array of data. In this task we will check the effect that the transformation PCA space has image that is not similar the images that were used build the PCA space. Write script that computes the PCA space for the first face dataset. Then load the image elephant.jpg, reshape it into vector and transform it into the precalculated PCA space, then transform it back image space. Reshape the resulting vector back image and display both the original and the reconstructed image. Comment the results.
(f) (cid:70) points) Recognition with subspace: PCA subspaces used in simple object recognition scenario. Generally, if image is similar the images used build the PCA subspace, the reconstruction error incurred when projecting said PCA space should small. In this task, you will try implement simple facial recognition system based this property.
Use camera capture images at the very least) of your face with varying illumination and facial expressions. Resize them common resolution and try align them by location. Construct PCA space from these images. Then, write
value of each pixel equals the average value of the corresponding pixels in all images. In case
of image vectors we dealing simply with their average value.
script that captures images from your webcam, detects faces in them (you use something from OpenCV like Haar cascades) and extracts the regions that contain faces. Reshape these regions correct size, transform them the precalculated PCA space and back image space. Then, based some similarity measure simple norm) and some threshold, decide whether region contains your face not. Display the information the image stream.
Note: You prepare video that demonstrates the performance of your system.
(cid:70) points) Linear discriminant analysis: Based the instructions from the lecture slides (Subspace-based recognition) implement the LDA algorithm and apply it our face database. Make sure that you also address the problem of singularities in high-dimensional data using appropriate pre-processing (also described in the lecture slides). Visualize all the image samples in the PCA subspace and the LDA subspace with different colors for each class demonstrate that the LDA subspace better separates classes.
Note: You pre-scale your image data range [0, in order avoid large values in the subspaces as shown in the image.
References
D. Forsyth and Ponce. Computer Vision: Modern Approach. Prentice Hall,
