| |
|
Seeing With OpenCV, Part 4: Face Recognition With Eigenface
(Continued)
|
|
|
|
This article originally appeared in
SERVO Magazine, April 2007.
Reprinted by permission of T & L Publications, Inc.
|
| |
Dimensionality Reduction By PCA
There are many methods for dimensionality reduction. The one that eigenface uses is called Principal Components Analysis, PCA for short.
Line Fitting and PCA
To get an intuition for what PCA does, let's look at a special case of PCA called a "least squares line fit." The lefthand side of
Figure 2
shows an example of fitting a line to three points: the 2D map locations for Los Angeles, Chicago, and New York. (To keep the explanation simple, I've ignored 3D factors such as elevation and the curvature of the earth.)
These three map points are almost, but not quite, on a single line already. If you were planning a trip, that relationship would be useful information. In that sense, a single line expresses something essential about their relationship. A line has only one dimension, so if we replace the points' 2D locations with locations along a single line, we'll have reduced their dimensionality.
Because they're almost lined up already, a line can be fitted to them with little error. The error in the line fit is measured by adding together the square of the distance from each point to the line. The best-fit line is the one that has the smallest error.
|
|
|
|
|
Figure 2. Right: fitting a line to three points is a special case of PCA. Left: to project points from the 2D map onto the 1D line, locate the point on the line that's closest to the 2D point. Bottom: the 1D subspace, and the distances between points in this subspace.
|
|
Defining a Subspace
Although the line found above is a 1D object, it's located inside a larger, 2D space, and has an orientation (its slope). The slope of the line expresses something important about the three points. It indicates the direction in which they're spread out the most.
If we position a rectangular (x,y) coordinate system so that its origin is somewhere on this line, we can write the line equation as simply
y = mx,
where m is the line's slope: dy / dx.
When it's described this way, the line is a subspace of the 2D space defined by the (x,y) coordinate system. This description emphasizes the aspect of the data we're interested in, namely the direction that keeps these points most separated from one another.
The PCA Subspace
This direction of maximum separation is called the first principal component of a dataset. The direction with the next largest separation is the one perpendicular to this. That's the second principal component. In a 2D dataset, we can have at most two principal components.
Since the dimensionality for images is much higher, we can have more principal components in a dataset made up of images.
However, the number of principal components we can find is also limited by the number of data points. To see why that is, think of a dataset that consists of just one point. What's the direction of maximum separation for this dataset? There isn't one, because there's nothing to separate. Now consider a dataset with just two points. The line connecting these two points is the first principal component. But there's no second principal component, because there's nothing more to separate: both points are fully on the line.
We can extend this idea indefinitely. Three points define a plane, which is a 2D object, so a dataset with three data points can never have more than two principal components, even if it's in a 3D, or higher, coordinate system. And so on.
In eigenface, each 50x50 face image is treated as one data point (in a 2,500 dimensional "space"). So the number of principal components we can find will never be more than the number of face images minus one.
Although it's important to have a conceptual understanding of what principal components are, you won't need to know the details of how to find them to implement eigenface. That part's been done for you already in OpenCV. I'll take you through the API for that in next month's article.
Projecting Data Onto a Subspace
Meanwhile, let's finish the description of dimensionality reduction by PCA. We're almost there!
Going back to the map in
Figure 2,
now that we've found a 1D subspace, we need a way to convert 2D points to 1D points. The process for doing that is called projection. When you project a point onto a subspace, you assign it the subspace location that's closest to its location in the higher dimensional space. That sounds messy and complicated, but it's neither. To project a 2D map point onto the line in Figure 2, you'd find the point on the line that's closest to that 2D point. That's its projection.
There's a function in OpenCV for projecting points onto a subspace, so again, you only need a conceptual understanding. You can leave the algorithmic details to the library.
The blue tic marks in
Figure 2
show the subspace location of the three cities that defined the line. Other 2D points can also be projected onto this line. The righthand side of
Figure 2
shows the projected locations for Phoenix, Albuquerque, and Boston.
CONTINUED
1
2
3
Next
|
