Kernel PCA for image modeling
HTWG Konstanz, Brauneggerstr. 55, D78462
MaxPlanckInstitute for Biological Cybernetics, Spemannstr. 38, D72076
· Kernel Principal Component Analysis
· Singleframe superresolution using iterative KPCA
Kernel Principal Component Analysis
We investigate the analysis of images based on kernel PCA (KPCA). Memory and time complexity are, however, major obstacles for applying KPCA to huge image databases. The generalized Hebbian algorithm (GHA) provides an efficient implementation of linear PCA with smaller demands on memory complexity. Accordingly, we study the transfer of this property to KPCA by kernelizing the GHA.

The basic idea of KPCA for image analysis is to nonlinearly map the data into a Reproducing Kernel Hilbert Space (RKHS) F and then perform linear PCA in F. The architecture of KPCA for the extraction of the first principal component is depicted in Fig. 1. A patch of a natural image is fed into the KPCA analyzer. A nonlinear map is then applied to map the input into the RKHS F, where the inner product with the principal axis w is computed. These two operations are in practice performed in one single step using the kernel function . By expanding the solution w as a linear combination of mapped samples, KPCA indirectly performs PCA in F only based on the kernel function.
In the original KPCA formulation, the combination coefficients are computed by diagonalizing the Gram matrix for all sample patterns, which is prohibitive for natural images due to memory complexity. As a nonlinear extension of the Hebbian algorithm, the Kernel Hebbian Algorithm (KHA) estimates them iteratively based on the correlation between the mapped patterns and the system output y in F, which can be efficiently computed based on kernels. This relieves the burden of working directly in a possibly very highdimensional RKHSs and storing the whole gram matrix.
Download matlab code containing the KHA and a toy example.


a 
b 
Fig. 2 shows preliminary results: a toy problem: twodimensional data (scattered black dots) overlaid with the contours of three principal components (induced by polynomial kernel) obtained with KPCA and KHA, respectively (3,000 iterations for KHA); b natural image analysis application: preimages of 50 principal components (induced by Gaussian kernel) obtained from the KHA (40,000 image patches, 100 iterations). 
Figs. 3 and 4 show applications of the KHA to image superresolution. The problem is to reconstruct a highresolution image based on a lowresolution image. It requires prior knowledge which in our case will be provided by the kernel principal components of a representative dataset of highresolution image patches. To reconstruct a superresolution image from a lowresolution image which was not contained in the training set, we first scale up the image to the same size as the training images, then map the image into the F, and project it into the KPCA subspace corresponding to a limited number of principal components. This reconstruction in F is projected back into the input space by preimage techniques.
Fig. 3 Face image superresolution based on PCA and KHA using a Gaussian kernel using varying numbers of principal components. 5000 (60 by 60)sized face images were used to perform linear PCA and KHA. The test images were subsampled of a 20 by 20 grid and scaled up to the original scale by turning each pixel into a 3 by 3 square of identical pixels, before doing the reconstruction. 


a 
b 


c 
d 
Fig. 4 Examples of natural image superresolution. (12 by 12) image patches are used for training the KHA. For a realistic natural image superresolution, only highfrequency components of image were reconstructed which are then superimposed on the bicubic interpolation. The lowresolution input image is then divided into a set of (12 by 12)sized windows each of which is reconstructed based on 200 principal components. The problem of this approach is that the resulting image as a whole shows a block structure since each window is reconstructed independently of its neighborhood. To reduce this effect, the windows are configured to slightly overlap into their neighboring windows: a. original image of resolution 284 by 618, b. lowresolution image (142 by 309) stretched to the original size, c. bicubic reconstruction, and d. KHA reconstruction. 
Fig. 5 shows applications of the KHA to image denoising. No clean training images are required. Instead, it is assumed that the noise mainly contaminates the kernel principal components (KPCs) with small eigenvalues. Thus, a truncated KPC expansion of the noisy image leads automatically to a denoising effect. The KHA is trained and tested on the same data set.



a 
b 
c 



d 
e 
Fig.5 Denoising examples. The training data for KHA were obtained by sampling noisy input images at regular intervals. Overlapping windows are averaged in the reconstruction. a. original Lena image, b and c. noisy images generated by adding Gaussian noise (SNR: 7.72dB) and Saltandpepper nise (SNR: 4.94dB), respectively, and d and e: denoised images of b and c based on KHA (SNR: 14.25dB and 12.71dB, respectively). 