Adaptive Prediction Using a Dimensionality Reduction Process
FIELD OF THE INVENTION
[0002] This invention relates generally to video processing, and more particularly to predicting using a dimensionality reduction process.
COPYRIGHT NOTICE/PERMISSION
[0003] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies: Copyright © 2008, Sony Electronics Inc., All Rights Reserved.
BACKGROUND OF THE INVENTION
[0004] A fundamental problem in video coding is prediction of high resolution images using available low resolution data. Least square (LS) filters are commonly used in these cases, and the LS filter coefficients are used to produce higher resolution images using available low resolution data, possibly from different times.
[0005] Zooming requires utilizing data possibly from different times and combining the available information to obtain a high resolution image for the current time. The training of the LS filters is possible by generating decimated images and finding the best set of LS filters to obtain back the original images minimizing the different between the original and predicted images.
2

[0006] A filter tap is a pattern overlaid on a region of pixels. The pixels overlapping the filter tap form the basis of filter coefficients associated with that pixel.
SUMMARY OF THE INVENTION
[0007] Multi-field taps are defined based on a decimated field. The multi-field taps are used to generate correlation matrices, the elements of which are used to generate covariance matrices. A principal component space is obtained by projecting the correlation matrix elements on to eigenvectors. The principal component space is partitioned into classes and a least square filter set is generated for each class.
BRIEF DESCRIPTION OF THE DRAWINGS
[0008] Figure 1A illustrates one embodiment of adaptive prediction or video processing using a dimensionality reduction process;
[0009] Figure 1B illustrates a relationship between original, decimated, and predicted fields;
[0010] Figure 2 is a flow diagram illustrating a method of adaptive prediction using principal components analysis according to an embodiment of the invention;
[0011] Figures 3A and 3B are diagrams illustrating examples of decimation according to an embodiment of the invention;
[0012] Figure 4 is a diagram illustrating prediction using fields from multiple times according to an embodiment of the invention;
[0013] Figure 5 is a diagram illustrating eigenvector variance coverage according to an embodiment of the invention;
[0014] Figure 6 is a diagram illustrating a principal component space according to an embodiment of the invention;
[0015] Figures 7A and 7B are diagrams of a computer environment suitable for practicing the invention;
[0016] Figure 8 is a diagram illustrating classification performance according to an embodiment of the
invention; 3

[0017] Figure 9 is a diagram illustrating point distribution according to an embodiment of the invention;
[0018] Figures 10A-10D illustrate another point distribution according to an embodiment of the
invention;
[0019] Figure 11 illustrates yet another point distribution from various perspectives according to an
embodiment of the invention;
[0020] Figure 12 is a diagram illustrating another classification performance according to an embodiment
of the invention;
[0021] Figure 13 is a diagram illustrating a performance comparison according to various configurations
of an embodiment of the invention; and
[0022] Figure 14 is a flow diagram illustrating a method of clustering pixels according to an embodiment
of the invention.
DETAILED DESCRIPTION OF THE INVENTION
[0023] In the following detailed description of embodiments of the invention, reference is made to the accompanying drawings in which like references indicate similar elements, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that logical, mechanical, electrical, functional and other changes may be made without departing from the scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.
[0024] Beginning with an overview of the operation of the invention, Figure 1A illustrates one
embodiment of adaptive prediction or video processing using a dimensionality reduction process. Original
data 100 is encoded at encoder 105 using adaptive prediction that incorporates a dimensionality reduction
process. The original data 100 may be video data from a BluRay player, which a user wishes to view on a
standard definition television such as device 120. To accomplish this, encoder 105 may zoom data 100 to
4

produce zoomed data 110, which device 120 is able to decode and display at the appropriate aspect ratio. The encoded data from encoder 105 may take the form of compressed data 115, which is transmitted through network 125 to device 130 to decode and display (e.g., streaming video over the internet.)
[0025] In one embodiment, encoder 105 may classify frames of video data and assign individual prediction filters to each class in the frame. Adaptive prediction with classification involves partitioning the pixels of a frame into a number of classes and adapting a filter to that class. A filter may include coefficients for each pixel which may be used to predict or decimate that pixel. The filter coefficients and the corresponding pixel are related through a filter tap. A filter tap is a pattern overlaid on the corresponding pixel and pixels around that pixel. The pattern defines which pixels will be used to generate coefficients. In one embodiment, Principal Component Analysis (PCA) is used to classify video frames into classes. The PCA may represent each pixel in a low resolution frame with the corresponding correlation matrix elements defined by the filter taps. PCA uses the correlation information for each pixel to group pixels with similar spatiotemporal variations in the images into classes.
[0026] Defining classification filters depends on the relationship between decimated images and their corresponding original resolution images. Figure 1B illustrates a relationship between original, decimated, and predicted fields. Original (target) fields 150, 155, and 160 are decimated 190 and corresponding low resolution fields 165, 170, and 175 are obtained. Information available from the decimated fields is used to obtain prediction 180 and LS filter coefficients 185 that minimize the difference between the original fields 150-160 and the predicted field 180. The prediction error 195 may be defined as:
5
(1) where I(x) is the original image and P(x) is the predicted image, where P(x) is defined as:


where ID(y) represents the decimated image.
[0027] Figure 2 illustrates a method 200 of PCA according to an embodiment of the invention. At block 205, the method decimates the original high resolution (e.g., high definition) fields. Decimation of fields is described in greater detail below in conjunction with Figures 3A-3B.
[0028] At block 210, the method defines multi-field taps over the decimated fields. Multi-field filter taps straddle more than one field of data to be used to generate coefficients for the corresponding pixel. Multi-field filter taps are described in greater detail below in conjunction with Figures 3B and 4.
[0029] At block 215, the method generates correlation matrices that include the cross relationships between the pixels in the multi-field filter taps. Elements of the correlation matrices represent the pixels in the decimated image in a high dimensional space. The method carries the problem over to a lower dimensional space using PCA to classify the pixels more efficiently.
[0030] At block 220, the method generates a covariance matrix of the correlation matrix elements as in equation 3. The method places the correlation matrix elements for each decimated pixel into a column format and generates an observation matrix X with m columns after removing the mean vector from each column. Mean vector removal emphasizes the local changes around the pixels. The method applies eigendecomposition to the covariance matrix of X. The decomposition produces n eigenvectors and n eigenvalues where n is the number of elements in the correlation matrices. The covariance matrix has a rank n which is the smaller of m and n, m being the number of pixels. The covariance matrix of X may be

defined as: *=1 (3)
where

(4)
is the mean vector.
6

Eigendecomposition operation can be summarized as in equation 5. Q includes the eigenvectors in the columns and Λ is a diagonal matrix with the corresponding eigenvalues:

QT can be replaced with Q1 because the eigenvectors constitute an orthonormal basis.
[0031] At block 225, the method projects the matrix X on to eigenvectors by projecting columns of X on to the columns of Q to obtain the principal components and generate a space with the distribution of principal components as in equation 6. The principal components indicate how similar each column of X is to each eigenvector. The matrix P includes the PCs. Each pixel is represented by a predetermined number of eigenvectors.
P - QTX
(6) Filter coefficients are functions of the correlation matrices corresponding to the decimated pixels around the center pixel. The filter tap identifies the filter coefficients. The method classifies the decimated image pixels based on the similarities of the corresponding correlation matrices and generates a different set of filter coefficients for each class. The method obtains eigenvectors using correlation information of a filter tap to represent each decimated image pixel and sorts the eigenvectors according to their eigenvalues.
[0032] The method 200 may use PCA to transform the classification problem into a space with axes defined by the eigenvectors. The method uses the similarity between columns of X (each column represents a different pixel) and the eigenvectors as the coordinates of the decimated pixels in the reduced dimensional space.
[0033] At block 230, the method 200 partitions the PC space into classes. PC space represents the decimated image pixels in the lower dimensional space and regions with similar correlation matrices are grouped together in the PC space. The method initially partitions each of the axes into three regions such
7

that there will be equal number of pixels in each region, which results in a total of twenty-seven regions in three dimensions, with the pixels classified into twenty-seven groups. In other embodiments, the number of classes is not statically defined as 27. Selecting different numbers of classes is described in greater detail below in conjunction with Figure 14.
At block 235, the method generates a least squares (LS) filter for each class. The LS filter minimizes the sum of the squared difference between the original and predicted images over all pixels in the original (target) frame. The method obtains the filter coefficients by taking the partial derivatives with respect to each filter element and forcing it to be zero for each:


(7)

[0034] The method 200, as illustrated in Figure 2, determines the set of coefficients in the filter taps L using the correlations of the pixels determined by the filter taps:

(8)
where


(9, 10)
where Aj,k is the correlation matrix (indices j and k run over two filter taps T) and bk is the observation vector. ID represents the decimated image.
[0035] The method 200 generates the LS filter using an observation vector and an inverse of the correlation matrices. The method uses different LS filters specific to each region. Assuming that there are m pixels and c classes (regions) in the decimated image,


8


(11)
shows the number of pixels in each class. For a given class u,

U \ — 1 IAI
Lu = {Auylb

(12)

where

(13, 14)
where

u = S(x)

(15)

is the prediction filter classification map for the target pixel x.
[0036] Figure 3A is a diagram illustrating decimation for spatial algorithms using a single time period.
Each source pixel identified by filter tap 305 contributes one-quarter of its value to the value of decimated
pixel 310.
[0037] Figure 3B is a diagram illustrating decimation for a spatiotemporal algorithm according to an
embodiment of the invention using two time periods. The decimation operation illustrated in Figure 3B
uses two or more time fields as input to a prediction algorithm. A multi-field filter tap 350 determines
which pixels are drawn from which time fields. The decimation operation uniformly distributes the
decimation with weighted coefficients to generate decimated pixel 355. In other embodiments, more
complex and adaptive decimation algorithms are used.
[0038] Figure 4 is a diagram illustrating a sample spatiotemporal filter tap that uses three fields 405 from
three different time fields. The multi-field filter tap uses nine decimated pixels 410 from each field as


9

input to the prediction filter to predict pixels 415 around center pixel 420. The multi-field filter tap moves
over the decimated image to predict a higher resolution video field. The method may obtain optimized
filter elements through a least squares process.
[0039] Figure 5 illustrates the first nine eigenvectors 505 with the decreasing variance after the method
places them back into matrix form. The percentages 510 indicate how much of the total variance of the
original field each eigenvectors carries.
[0040] In one embodiment, the method obtains improved results using the first three eigenvectors in a
three-dimensional space, representing each of the decimated pixels with three coordinates. Figure 6
illustrates the distribution of a subset of these pixels based on a partition operation. The axes 605, 610,
and 615 correspond to the first three eigenvectors and coordinates of each pixel are the corresponding
principal components.
[0041] In one embodiment, the method obtains improved results using the first three eigenvectors in a
three-dimensional space, representing each of the decimated pixels with three coordinates. Figure 6
illustrates the distribution of a subset of these pixels based on a partition operation. The axes PC1 605,
PC2 605 [[610]], and PC3 605 [[615]] correspond to the first three eigenvectors and coordinates of each
pixel are the corresponding principal components.
[0042] Figure 14 illustrates a method 1400 of clustering pixel classes according to an embodiment of the
invention. The number of clusters, c, is treated as known regardless of the distribution of the pixels in the
PC space. At block 1405, the method determines a number of classes to use.
[0043] At block 1410, the method labels each pixel with a number and selects a uniform distribution of c
numbers in this range. The method uses this uniform selection as initial values for the centroids (weighted
centers) of the c classes to be clustered.
[0044] At block 1415, the method assigns each pixel to the closet centroids (and cluster) based on the
distance of the pixel to each of the centroids.


10

[0045] At block 1420, the method determines new cluster centroids for each cluster using the pixel
assignments.
[0046] At block 1425, the method evaluates the dynamic validity index of the current clustering
configuration. In other embodiments, other cost functions may be used. The dynamic validity index may
be defined as:

where N is the number of points (data objects), k is the number of clusters, x is the location of a data
point, zi is the cluster center location (centroid) of the ith cluster and Ci is the set of points in the ith
cluster. The dynamic validity index includes an intra-cluster term (numerator) and an inter-cluster term
(denominator). The intra-cluster term is the average distance of each point to their corresponding centroid
and measures the average level of compactness of all clusters. The inter-cluster term is the distance
between the pair of clusters that are closest to each other among all pairs of clusters.
[0047] At block 1430, the method assigns new class membership to each point (pixel) in the PC space
based on the closest cluster centroid.
[0048] At block 1435, the method determines new cluster centroids of each cluster based on the new class
assignments.
[0049] At block 1440, the method evaluates the validity index of the new configuration, and compares
this validity index with the validity index generated at block 1425. If the difference between the indexes
exceeds a threshold, the method returns to block 1430 and goes through an additional iteration of
clustering. Otherwise, the method uses the current clustering scheme. During the first iteration, the
method compares the index evaluated at block 1440 with the index evaluated at block 1425. During
subsequent iterations, the method compares the index evaluated at block 1440


11

[0050] The method evaluates the dynamic validity index at each iteration and continues until the change between iterations drops below a threshold. When this occurs, no further assignments are made and the method 1400 uses the current clustering scheme to partition the PC space. Empirical data suggests that between twenty and thirty iterations are required before the results saturate and drop below the threshold. [0051] The method 1400 uses the dynamic validity index to provide a point of comparison for clustering configurations. The method recursively adjusts the class assignments based on the current set of centroids and adjusts the centroids based on the current class assignments. In this way, the method iteratively improves the clustering until the improvement saturates.
[0052] After the method 1400 completes the clustering operation at block 230 of Figure 2, the method 200 uses each member of each cluster to generate the LS filter coefficients, which produces a dynamically clustered LS filter.
[0053] Figure 8 illustrates a comparison 800 of the signal-to-noise ratio (SNR) performance of static clustering 805 and dynamic clustering 810. Red portions of the performance indicate the gain resulting from use of class specific LS filters derived with a dynamic clustering method such as method 1400. [0054] Iterative clustering classifies pixels in the decimated images and generates a different set of LS coefficients for each class. Figure 9 illustrates a sample distribution 900 of pixels of a decimated image in three-dimensional space. Each pixel is represented with principal components one, two, and three. [0055] Figures 10A-10D represent a pair-wise distribution of PC1-2 1005, PC2-3 1010, PC3-4 1015, and PC4-5 1020. These pairs represent projections of a five dimensional distribution on to various two dimensional planes.
[0056] Figure 11 illustrates various perspectives 1105-1120 of a distribution divided into thirty-two clusters. Each cluster is represented by a different tone of gray.
[0057] Figure 12 illustrates the SNR results 1205 obtained using an embodiment of the invention.
Analyses were repeated for every field (sixty times during the video scene) with five dimensional spaces
using the first five eigenvectors. SNR performance 1215 of the dynamic clustering LS filter is compared 12

with the SNR performance 1210 of static clustering LS filters. Approximately 0.6dB NSR performance increase was obtained over all scenes.
[0058] Figure 13 illustrates the results of similar analyses varying parameters of the clustering method. SNR improvements 1305 are obtained as more PCs 1315 are used up until seven PCs. Ninety-nine percent of variance is demonstrably incorporated into the first seven PCs. Performance continued to increase when increasing the number of classes 1310, as would be expected.
[0059] The particular methods of the invention are described in terms of computer software with reference to a series of flow diagrams illustrated in Figures 2 and 14. The methods constitute computer programs made up of machine-executable instructions illustrated as blocks. Describing the methods by reference to a flow diagram enables one skilled in the art to develop such programs including such instructions to carry out the methods on suitably configured machines (the processor of the machine executing the instructions from machine-readable media, including memory.) The machine-executable instructions may be written in a computer programming language or may be embodied in firmware logic. If written in a programming language conforming to a recognized standard, such instructions can be executed on a variety of hardware platforms and for interface to a variety of operating systems. In addition, the present invention is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the invention as described herein. Furthermore, it is common in the art to speak of software, in one form or another (e.g., program, procedure, process, application, module, logic...), as taking an action or causing a result. Such expressions are merely a shorthand way of saying that execution of the software by a computer causes the processor of the computer to perform an action or produce a result. It will be appreciated that more or fewer processes may be incorporated into the methods illustrated in Figures 2 and 14 without departing from the scope of the invention and that no particular order is implied by the arrangement of blocks shown and described herein.


13

[0060] In one embodiment, as shown in Figure 7A, a server computer 701 is coupled to, and provides data through, the Internet 705. A client computer 703 is coupled to the Internet 705 through an ISP (Internet Service Provider) 705 and executes a conventional Internet browsing application to exchange data with the server 701. A server computer 701 may executed the methods illustrated in Figures 2 and 14. Optionally, the server 701 can be part of an ISP which provides access to the Internet for client systems. The term "Internet" as used herein refers to a network of networks which uses certain protocols, such as the TCP/IP protocol, and possibly other protocols such as the hypertext transfer protocol (HTTP) for hypertext markup language (HTML) documents that make up the World Wide Web (web). The physical connections of the Internet and the protocols and communication procedures of the Internet are well known to those of skill in the art. Access to the Internet allows users of client computer systems to exchange information, receive and send e-mails, view documents, such as documents which have been prepared in the HTML format, and receive content. It is readily apparent that the present invention is not limited to Internet access and Internet web-based sites; directly coupled and private networks are also contemplated.
[0061] In one embodiment, as shown in Figure 7A, a server computer 701 is coupled to, and provides
data through, the Internet 705. A client computer 703 is coupled to the Internet 705 through an ISP
(Internet Service Provider) [[705]] 707 and executes a conventional Internet browsing application to
exchange data with the server 701. A server computer 701 may executed the methods illustrated in
Figures 2 and 14. Optionally, the server 701 can be part of an ISP which provides access to the Internet
for client systems. The term "Internet" as used herein refers to a network of networks which uses certain
protocols, such as the TCP/IP protocol, and possibly other protocols such as the hypertext transfer
protocol (HTTP) for hypertext markup language (HTML) documents that make up the World Wide Web
(web). The physical connections of the Internet and the protocols and communication procedures of the
Internet are well known to those of skill in the art. Access to the Internet allows users of client computer
systems to exchange information, receive and send e-mails, view documents, such as documents which 14

have been prepared in the HTML format, and receive content. It is readily apparent that the present invention is not limited to Internet access and Internet web-based sites; directly coupled and private networks are also contemplated.
[0062] The description of Figures 7A-B is intended to provide an overview of computer hardware and other operating components suitable for implementing the invention, but is not intended to limit the applicable environments. It will be appreciated that the computer system 740 is one example of many possible computer systems which have different architectures. A typical computer system will usually include at least a processor, memory, and a bus coupling the memory to the processor. One of skill in the art will immediately appreciate that the invention can be practiced with other computer system configurations, including multiprocessor systems, minicomputers, mainframe computers, and the like. The invention can also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. [0063] Adaptive prediction using dimensionality reduction has been described. Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that any arrangement which is calculated to achieve the same purpose may be substituted for the specific embodiments shown. This application is intended to cover any adaptations or variations of the present invention.
[0064] The terminology used in this application with respect to adaptive prediction using dimensionality reduction is meant to include all of these environments. Therefore, it is manifestly intended that this invention be limited only by the following claims and equivalents thereof.


15

CLAIMS
What is claimed is:
1. A system comprising:
a processor coupled to a bus;
a memory coupled to the processor through the bus; and
instructions executed by the processor from the memory to cause the processor to define multi-field taps based on a decimated field; generate correlation matrixes using the multi-field taps; generate covariance matrixes based on the correlation matrix elements; project the correlation matrix elements onto eigenvectors to obtain a principal component space;
partition the principal component space into classes; and generate a least square filter for each of the classes.
2. The system of claim 1, the instructions further comprising: decimate an original high resolution field to produce a decimated field.
3. The system of claim 2, the instructions further comprising:
reconstruct the original high resolution field for display on a display device.
4. A data processing system comprising:
means for defining multi-field taps based on a decimated field;
means for generating correlation matrixes using the multi-field taps;
means for generating covariance matrixes based on the correlation matrix elements;
means for projecting the correlation matrix elements onto eigenvectors to obtain a principal component space;
means for partitioning the principal component space into classes; and
means for generating a least square filter for each of the classes. 16

5. The system of claim 4, further comprising:
means for decimate an original high resolution field to produce a decimated field.
6. The system of claim 5, further comprising:
means for reconstruct the original high resolution field for display on a display device.
7. A system substantially as herein described with reference to the foregoing description and
the accompanying drawings.

Dated this 1st day of October 2009.

To
The Controller of Patents
The Patent Office
India