Adaptive prediction using a dimensionality reduction process

[0001] The present application is related to the following commonly-owned, concurrently-filed applications: application Ser. No. 12/245,664, filed Oct. 3, 2008, entitled “Dynamic Clustering for Adaptive Prediction Filters”.

[0002] This invention relates generally to video processing, and more particularly to predicting using a dimensionality reduction process.

[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.

[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.

[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.

[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.

[0024] 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.

[0025] Beginning with an overview of the operation of the invention, FIG. 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 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.)

[0026] 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.

[0027] Defining classification filters depends on the relationship between decimated images and their corresponding original resolution images. FIG. 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:

[0028] $\begin{array}{cc}e=\sum _{\overrightarrow{x}}{\left(I\left(\overrightarrow{x}\right)-P\left(\overrightarrow{x}\right)\right)}^2& \left(1\right)\end{array}$
where I(x) is the original image and P(x) is the predicted image, where P(x) is defined as:

[0029] $\begin{array}{cc}P\left(\overrightarrow{x}\right)=\sum _j{L}_j^u{I}^D\left({\overrightarrow{y}}_j^{\overrightarrow{x}}\right)& \left(2\right)\end{array}$
where I^D(y) represents the decimated image.

[0030] FIG. 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 FIGS. 3A-3B.

[0031] 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 FIGS. 3B and 4.

[0032] 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.

[0033] 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:

[0034] $\begin{array}{cc}{\hat{C}}_{\mathrm{xx}}=\frac{1}{m-1}{\mathrm{XX}}^T=\frac{1}{m-1}\sum _{i=1}^m\left({\underset{\_}{v}}_i-\underset{\_}{\hat{\mu }}\right){\left({\underset{\_}{v}}_i-\widehat{\underset{\_}{\mu }}\right)}^T\mathrm{where}& \left(3\right)\\ \underset{\_}{\hat{\mu }}=\frac{1}{m}\sum _{i=1}^m{\underset{\_}{v}}_i& \left(4\right)\end{array}$
is the mean vector.

[0035] 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:
Ĉ_xx=QΛQ^T=QΛQ⁻¹  (5)
Q^T can be replaced with Q⁻¹ because the eigenvectors constitute an orthonormal basis.

[0036] 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=Q^TX  (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.

[0037] 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.

[0038] 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 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 FIG. 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:

[0039] $\begin{array}{cc}e=\sum _{\overrightarrow{x}}{\left(I\left(\overrightarrow{x}\right)-P\left(\overrightarrow{x}\right)\right)}^2& \left(7\right)\end{array}$

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

[0041] $\begin{array}{cc}L={\left(A\right)}^{-1}b\mathrm{where}& \left(8\right)\\ A_{j,k}=\sum _{\overrightarrow{x}}{I}^D\left({\overrightarrow{y}}_j^{\overrightarrow{x}}\right)I^D\left({\overrightarrow{y}}_k^{\overrightarrow{x}}\right)b_k=\sum _{\overrightarrow{x}}{I}^D\left({\overrightarrow{y}}_k^{\overrightarrow{x}}\right)I\left(\overrightarrow{x}\right)& \left(9,10\right)\end{array}$
where A_j,k is the correlation matrix (indices j and k run over two filter taps T) and b_k is the observation vector. I^D represents the decimated image.

[0042] 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,
m=m₁+m₂+ . . . +m_c  (11)
shows the number of pixels in each class. For a given class u,

[0043] $\begin{array}{cc}{L}^u={\left(A^u\right)}^{-1}{b}^u\mathrm{where}& \left(12\right)\\ A_{j,k}^u=\sum _{\overrightarrow{x}|u=S\left(\overrightarrow{x}\right)}{I}^D\left({\overrightarrow{y}}_j^{\overrightarrow{x}}\right)I^D\left({\overrightarrow{y}}_k^{\overrightarrow{x}}\right)b_k^u=\sum _{\overrightarrow{x}|u=S\left(\overrightarrow{x}\right)}{I}^D\left({\overrightarrow{y}}_k^{\overrightarrow{x}}\right)I\left(\overrightarrow{x}\right)\mathrm{where}& \left(13,14\right)\\ u=S\left(\overrightarrow{x}\right)& \left(15\right)\end{array}$
is the prediction filter classification map for the target pixel x.

[0044] FIG. 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.

[0045] FIG. 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 FIG. 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.

[0046] FIG. 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 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.

[0047] FIG. 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.

[0048] 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. FIG. 6 illustrates the distribution of a subset of these pixels based on a partition operation. The axes PC1 605, PC2 605, and PC3 605 correspond to the first three eigenvectors and coordinates of each pixel are the corresponding principal components.

[0049] In another embodiment, at block 230 the method 200 uses clustering to classify pixels into finer groups in the reduced dimensional space using a dynamic validity index. The dynamic validity index is a cost function that measures the compactness of a pixel class and the distance between the classes themselves. The goal of clustering is to minimize the distance between pixels in the same class, which increases the compactness of the class, and maximizing the distance between classes. Empirical data suggests that iterative clustering classifies the pixels efficiently and provides an SNR improvement.

[0050] FIG. 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.

[0051] 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.

[0052] 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.

[0053] At block 1420, the method determines new cluster centroids for each cluster using the pixel assignments.

[0054] 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:

[0055] $\begin{array}{cc}\mathrm{Dynamic}\mathrm{Validity}\mathrm{Index}=\frac{\mathrm{Intra}}{\mathrm{Inter}}=\frac{\frac{1}{N}\sum _{i=1}^k\sum _{x\in C_i}{x-z_i}^2}{{\min }_{i,j}{\left(z_i-z_j\right)}^2}& \left(16\right)\end{array}$
where N is the number of points (data objects), k is the number of clusters, x is the location of a data point, z_i is the cluster center location (centroid) of the i^th cluster and C_i is the set of points in the i^th 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.

[0056] At block 1430, the method assigns new class membership to each point (pixel) in the PC space based on the closest cluster centroid.

[0057] At block 1435, the method determines new cluster centroids of each cluster based on the new class assignments.

[0058] 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

[0059] 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.

[0060] 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.

[0061] After the method 1400 completes the clustering operation at block 230 of FIG. 2, the method 200 uses each member of each cluster to generate the LS filter coefficients, which produces a dynamically clustered LS filter.

[0062] FIG. 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.

[0063] Iterative clustering classifies pixels in the decimated images and generates a different set of LS coefficients for each class. FIG. 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.

[0064] FIGS. 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.

[0065] FIG. 11 illustrates various perspectives 1105-1120 of a distribution divided into thirty-two clusters. Each cluster is represented by a different tone of gray.

[0066] FIG. 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 with the SNR performance 1210 of static clustering LS filters. Approximately 0.6 dB NSR performance increase was obtained over all scenes.

[0067] FIG. 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.

[0068] The particular methods of the invention are described in terms of computer software with reference to a series of flow diagrams illustrated in FIGS. 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 FIGS. 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.

[0069] In one embodiment, as shown in FIG. 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) 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 FIGS. 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.

[0070] One embodiment of a computer system suitable for use as server 701 is illustrated in FIG. 7B. The computer system 710, includes a processor 720, memory 725 and input/output capability 730 coupled to a system bus 735. The memory 725 is configured to store instructions which, when executed by the processor 720, perform the methods described herein. The memory 725 may also store data for/of adaptive prediction using dimensionality reduction. Input/output 730 provides for the delivery and display of the data for/of adaptive prediction using dimensionality reduction or portions or representations thereof, and also the input of data of various types for storage, processing or display. Input/output 730 also encompasses various types of machine-readable media, including any type of storage device that is accessible by the processor 720. One of skill in the art will immediately recognize that the server 701 is controlled by operating system software executing in memory 725. Input/output 730 and related media store the machine-executable instructions for the operating system and methods of the present invention as well as the data for/of adaptive prediction using dimensionality reduction.

[0071] The description of FIGS. 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.

[0072] 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.

[0073] 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.