Adaptive Decimation Filter
FIELD OF THE INVENTION
[0002]This invention relates generally to data processing, and more particularly to video encoding.
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] An important and fundamental problem in various video processing applications, such as compression and zooming, is decimation and prediction. Decimation involves generating a smaller version of a source data. A common example is video compression, which uses a decimation filter to decimate an original frame in order to create a decimated frame. To decompress the video frame, a prediction filter generates a target frame from the decimated frame. The quality of the target frame may be expressed by measuring the difference between the original frame and the target frame, which is the prediction error. One existing process used to improve the quality of the target frame is to use an adaptive prediction filter. An adaptive prediction filter is modified with respect to a corresponding decimated frame to improve the quality of the target frame, while the decimation filter remains fixed. A classified
2

prediction filter is a adaptive prediction filter that applies different filters/classes to different pixels/regions in an image.
[0005]Figure 2A illustrates a fixed decimation filter with a decimation factor of 1/4 that reduces the original frame to a decimated frame one quarter the size of the original. Original pixels 205 (unfilled) are each assigned a decimation filter coefficient of 1/4. In other words, to generate the decimated pixel 210, original pixels 205 will be averaged. Figure 2B illustrates a fixed decimation filter with a decimation factor of 1/9. Original pixels 250 (unfilled, plus an original pixel in the same location as target pixel 255) each contribute 1/9 to the value of decimated pixel 255. After applying the decimation filter illustrated in Figure 2A or 2B, the source data has been reduced in size consistent with the decimation factor.
SUMMARY OF THE INVENTION
[0006]An initial decimation filter is applied to an original frame to generate a decimated frame. An optimized prediction filter is extracted from both the decimated frame and the original frame, while the initial decimation filter is held fixed. A predicted from is generated from the optimized prediction filter and the decimated frame, and an optimize decimation filter is extracted from the decimated frame and the predicted frame, while the optimized prediction filter remains fixed.
BRIEF DESCRIPTION OF THE DRAWINGS
[0007]Figure 1 is a diagram illustrating a overview of the operation of an embodiment of an adaptive decimation filter according to the invention;
[0008]Figures 2A and 2B are diagrams illustrating fixed decimation filters as known in the art; [0009]Figure 3 is a diagram illustrating an adaptive decimation filter according to an embodiment of the invention;
[0010]Figure 4 is a data flow diagram illustrating the operation of an adaptive decimation filter according to an embodiment of the invention;
[OOll]Figure 5 is a flow diagram of a filter optimization method to be performed by a computer according to an embodiment of the invention;
3

[0012]Figure 6 is a diagram illustrating the operation of an adaptive decimation filter according to an
embodiment of the invention;
[0013]Figures 7A and 7B are flow diagrams of filter optimization methods to be performed by a computer
according to embodiments of the invention;
[0014]Figure 8 is a diagram illustrating the operation of an adaptive decimation filter according to an
embodiment of the invention;
[0015]Figure 9 is a diagram illustrating the operation of an adaptive decimation filter according to an
embodiment of the invention;
[0016]Figure 10 is a diagram illustrating the operation of an adaptive decimation filter according to an
embodiment of the invention;
[0017]Figures 11A and 1 IB are diagrams of a computer environment suitable for practicing the invention;
[0018]Figure 12 is a diagram of a classified adaptive decimation filter according to an embodiment of the
invention;
[0019]Figure 13 is a flow diagram of a multiple decimation filter extraction method to be performed by a
computer according to an embodiment of the invention;
[0020]Figure 14 is a flow diagram of another multiple decimation filter extraction method to be
performed by a computer according to an embodiment of the invention; and
[0021]Figure 15 is a flow diagram of an initial estimation of decimation filters method to be performed by
a computer according to an embodiment of the invention.
DETAILED DESCRIPTION OF THE INVENTION
[0022]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
4

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.
[0023]Beginning with an overview of the operation of the invention, Figure 1 illustrates one embodiment of adaptive decimation filtering. Original data 100 is encoded at encoder 105 using adaptive prediction and decimation filters. 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 encoder 105 may cause to be sent over network 125 to device 130 to decode and display. For example, data 100 may be live video of a sporting event.
[0024]The predictive strength of a prediction filter or a decimation filter may understood in terms of how similar an original frame is to a reconstruction of that original frame using the prediction filter. Optimizing either a prediction filter or a decimation filter is the process of adjusting the coefficients that make up the filter in a way that decreases the difference between the source frame and the target frame. In other words, reducing the prediction error associated with the target frame.
[0025]Optimizations to a decimation filter are present, indirectly, in the target frame by way of the decimated frame that the prediction filter uses to generate the target frame. As an example, suppose a prediction filter L is used to generate two target frames, P and P'. To generate the target frames, L is applied to two decimated frames, D and D', which were generated by two decimation filters, H and FT. Further suppose that the first target frame, P, has an average prediction error of 0.05 when compared to original image I, while the second target frame P' has an average prediction error of 0.10 when compared to I. Since the same prediction filter L is used to produce both target frames, the difference in accuracy is attributable to the decimated frames and thus the different decimation filters.
5

[0026]Figure 4 is a data flow diagram illustrating the operation of an adaptive decimation filter according to an embodiment of the invention. Encoder context 400 includes original frames 410 and decimated frames 425, which are decimated 415 by an encoder such as encoder 105 and predicted 420 to improve a prediction by measuring the error of the prediction. Encoded data 430 is sent to decoder 405. For example, over network 125. Decoder 105 uses decimated frames 435 and filter coefficients also included in the encoded data 430 to predict 440 predicted frames 445. Predicted frames 445 may be displayed to a user.
[0027]Next, the particular methods of the invention are described in terms of computer software with reference to a series of flow diagrams. Figures 5 and 7 are flow diagrams illustrating methods according to embodiments of an adaptive decimation filter. Encoder 105 may perform the methods illustrated in Figures 5 and 7. The methods constitute computer programs made up of machine-executable instructions illustrated as blocks (acts) 505 until 525 in Figure 5 and blocks 705 to 740 in Figure 7. 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 storage media, including memory such as RAM) [computerized clients (the processor of the clients executing the instructions from machine-readable media). Similarly, the methods to be performed by the server constitute computer programs also made up of machine-executable instructions. Describing the methods by reference to flow diagrams enables one skilled in the art to develop programs including instructions to carry out the methods on a suitable computerized server (the processor of the server executing the instructions from machine-readable storage media).] 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
6

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 5 and 7 without departing from the scope of the invention and that no particular order is implied by the arrangement of blocks shown and described herein.
[0028]Figure 3 is a diagram illustrating adaptive decimation filtering according to an embodiment of the invention. Pixel tap 305 includes pixel regions 325 and 330 and corresponds, through the decimation filter, to decimated pixel 310. To improve the predictive strength of the decimation filter, encoder 105 may optimize the decimation filter by changing the number of pixels included in a pixel tap or the coefficients corresponding to pixels in a pixel tap used to generate a decimated pixel. For example, in a fixed decimation filter with a decimation factor of 1/4, the decimation filter may use a pixel tap such as pixel region 325. Encoder 105 may expand this initial tap to create pixel tap 305, which incorporates additional pixels into the tap. Pixels in region 325 may have coefficients of 0.125, while pixels in region 330 may have coefficients of 0.05, and pixels in corners of the tap may have coefficients of 0.025. By increasing the size of pixel tap 305, more original data is available to generate decimated pixel 310, which in turn may improve the quality of a target frame. The encoder may also vary the filter coefficients according to which original pixels produce a better prediction.
[0029]For example, encoder 105 may also modify a pixel tap to exploit underlying features of the original frame. Pixel tap 315, for example, is elongated in the horizontal direction, and corresponds to decimated pixel 320. The region of the original frame from which pixel tap 315 is drawn may contain a horizontal feature (e.g., a brick in a wall), in which case a horizontally elongated pixel tap such as pixel tap 315 may produce a decimated pixel 320 which provides greater predictive strength to a prediction filter.
7

[0030]Figure 5 illustrates a filter optimization method according to an embodiment of the invention. Encoder 105 may perform filter optimization method 500 to optimize an adaptive decimation filter and an adaptive prediction filter. One obstacle to optimizing both the decimation filter and the prediction filter is that a simultaneous optimization would be a non-linear process. The prediction filter depends on the decimated frame, which is obtained with the decimation filter. An optimized decimation filter provides high prediction strength, where prediction strength depends directly on the prediction filter. The non-linearity of the relationship may be expressed as a function of the prediction and decimation filters:
ID = HI (1)
where ID is the decimated frame, H is the decimation filter, and I is the original frame. The prediction filter may be defined as:
P=L(H)ID (2)
where P is a target frame and prediction filter L is a function of H. Thus, target frame P may be expressed
as:
P = L(H)HI (3)
and prediction error E may be expressed as:
E=(I-Pf = (I-L(H)Hlf (4)
which is a nonlinear function in L and H. To obtain optimal prediction and decimation filters, prediction error E is minimized. Since the error function is nonlinear, no direct method to extract optimal solutions for both the prediction and decimation filters is available.
[0031]In the embodiment illustrated by Figure 5, a recursive process is used to optimizing the prediction and decimation filters. This process uses a linear error function. At block 505, the method 500 selects an initial decimation filter. For example, initial decimation filter may be a fixed decimation filter. At block 515, the method 500 extracts an optimized prediction filter while holding the decimation filter fixed. By keeping the decimation filter fixed, the error function becomes quadratic. Thus, minimizing the prediction error yields linear equations for a solution of the filter, which allows the method to extract an optimized
8

prediction filter for the current decimation filter. Extracting an optimized prediction filter is described in greater detail below in conjunction with Figure 7.
[0032]At block 520, the method 500 extracts an optimized decimation filter while holding the prediction filter extracted in block 515 fixed. By holding the prediction filter fixed, the error function becomes quadratic, allowing the method to extract an optimized decimation filter for the current prediction filter. If at decision 525 the method determines the optimization is complete, the method returns control to, for example, encoder 105. Otherwise, the method returns to block 515 to further optimize the filters. [0033]By using the recursive process described above, the method 500 incrementally improves both the decimation filter and the prediction filter. Since prediction strength depends upon the adaptability of both filters, changes to one filter may make new improvements possible in the other filter. [0034]Figure 6 illustrates the operation of the filter optimization method illustrated in Figure 5. Passes 600, 630, and 655 represent sequential optimizations of prediction and decimation filters. The method 500 decimates original frame 605 with an initial decimation filter 610 to produce decimated frame 620. The method 500 extracts an optimized prediction filter 615 from decimated frame 620, as described in greater detail below in conjunction with Figure 7. During pass 630, the method 500 extracts an optimized decimation filter 640 from original frame 605 while holding prediction filter 615 fixed. The method 500 generates a decimated frame 650 with decimation filter 640 and extracts an optimized prediction filter 645 while holding decimation filter 640 fixed. During pass 655, the method 500 extracts an optimized decimation filter 665 while holding prediction filter 645 fixed. The method 500 generates decimated frame 675 using decimation filter 665. The method 500 extracts an optimized prediction filter 670 using decimated frame 675. The method 500 determines that the results of optimization have saturated and relinquishes control, for example, to encoder 105.
[0035]Figure 7 illustrates a method to be performed according to an embodiment of the invention. At block 705, the method 700 selects an initial decimation filter, such as a fixed decimation filter with the desired decimation factor. At block 710, the method 700 generates a decimated frame by applying the
9

decimation filter to an original frame (e.g., a frame of video). At block 715, the method 700 generates classes for a prediction filter using the decimated frame using one of many processes known in the art. At block 720, the method 700 extracts a classified prediction filter while holding the decimation filter fixed. The method generates an optimized prediction filter by keeping the decimation filter as a fixed variable. [0036]The notation used to describe the filter extraction process is described, followed by the process itself. The original frame signal level is denoted for an individual pixel x as I(x). The decimated frame
signal level is denoted for the decimated pixel y as ID(y), while the set of decimated pixels defined on the prediction filter tap for the prediction of target pixel i, where the j index runs over the filter tap of the prediction filter is y* .
[0037]The prediction of the original frame for the pixel i is P(x) and is defined in the following paragraph. The prediction filter corresponding to the prediction filter class u is denoted as L".
[0038]The prediction filter is derived from the minimization of the prediction error, holding the decimation filter constant. The prediction for the pixel x may be defined as:
P(x) = ^LujID(yJ) (5)
j
while the prediction filter class for the pixel i may be defined as:
u = S(x) (6)
while the prediction error may be defined as:
e = ^(I(x)-P(x))2 (7)
x
A least squares training solution involves computing a correlation matrix and observation vector over all pixels x such that S(x) = u . The least squares solution yields a stable solution when the set of pixels is
large enough for each filter class. The method 700 extracts the prediction filter Lv for some class v from prediction error minimization with fixed decimation using a least squares solution:
10

Sju
2 (i(x) - P(x)j£ -^iD (y) ) (9)
^(I(x)-P(x))ID(fk) = 0 (10)
{x\v=S(x)}
jji(X)iD(yi)= j ZLVjlD(yj)lD(y*) (ii)
K = YuLVMu (12)
The optimized prediction filter for class v may be given by:
Lv=(Av)1bv (13)
where
A)*= HlD(y))lD(yl) (i4)
{x\v=S(x)S
is the correlation matrix for class v and
K= ^I(x)ID(y!) (15)
{x\v=S(x)S
is the observation vector for class v, resulting in v independent matrix equations, one for each class in the filter. The indexes {j, k } run over the prediction filter taps
j = l,2,...T1,k = l,2...T1 (16)
with Tj denoting the size of the prediction filter tap.
[0039]At block 725, the method 700 generates a predicted frame using the prediction filter and the decimated frame.
[0040]At block 730, the method 700 generates classes for the decimation filter from the target frame. The decimation classes may be defined on the original input data, or on the decimated data itself. The following process applies to deriving an adaptive decimation filter using a single class (mono-class).
11

Deriving a multi-class adaptive decimation filter is described in greater detail below in conjunction with Figures 13-15.
[0041] At block 735, the method 700 extracts a classified decimation filter while holding the prediction filter fixed. The method 700 derives the decimation filter from the minimization of the prediction error, keeping the prediction filter fixed. The prediction for the pixel i may be defined as:
P(x) = ^LuJID(y*) (17)
j
the prediction filter class map for the pixel i may be defined as:
u = S(x) (18)
the decimated image may be defined as:
iD(y*)=ZHni(z:h (19)
n
the prediction for the pixel i expressed in terms of the decimation filter may be defined as:
P(x) = Z^HJ(z!h (20)
j "
and the prediction error may be defined as:
e = ^(I(x)-P(x))2 (21)
X
[0042] Accordingly, the method 700 extracts the decimation filter H from prediction error minimization with a fixed prediction filter, as follows:
5H„
& = 0 (22)
L
2 (I(x) - P(x))^ L] X J^f tf ) = 0 (23)
« *■**--* m
^ (I(x) - P(x))^ L'jI(zS ) = 0 (24)
x j x j k n
12

£ I(x)Fm (x) = ^HnZFn (x)Fm (x) (26)
x n x
where
FJx) = ^mH> =0 (39)
SH' ,
15

Therefore, the mono-class decimation described above primarily in conjunction with Figure 7 may be extended to multi-class decimation using the following process:
2 (I(x) - P(x))^ L] X ^rHl3} ) = 0 (40)
x j n OHm
^(I(x)-P(x)) JtL)I(z^) = 0 (41)
x SJ\t=D(yxj)}
Applying the prediction defined in equation 37, the following is obtained for equation 40:
X Y4ux)vJi(zh=YZI^LH:i(^) im1^) (42)
x {j\t=D(yf)} x k n {j\t=D(y])j
Which may also be expressed as:
Xw:(x)=^^XF;(^(x)+Gi(!i/w'}) (43)
x n x
Where:
K(*)= immh (44)
{j\t=D(y])j
The last term in equation 43 is a class-coupling term, defined as:
G'm({H^}) = Y.K(x) Z L*Z**:'<*?) (45)
x {k\v*t} n
Where the decimation class index v in equation in 45 is determined by the class map as follows:
v = D(yt) (46)
The solution structure in equation 43 has the form:
K=THn2 (59)
where equation 54 represents the contribution of class zero, equation 55 represents the contribution of class one, and equation 56 represents the contribution of class two to the L-weighted input signal. [0057] This is unlike the case of multi-class prediction, where the prediction filters for each class may be solved independently. For multi-class prediction, the solution is the same matrix structure for each class, similar to the mono-class decimation filter case.
[0058]Figure 13 illustrates multiple decimation filter extraction using an exact process. In one embodiment, the method 500 may execute the method 1300 at block 520. At block 1305, the method concatenates the decimation filters for each class into a single combined decimation filter. This combined filter may be obtained exactly from a matrix inverse solution. The combined decimation filter may be defined as:
{H<:° , H':1 ,...# r-7;- > K +n = HP (6O>
The index t runs over the number of classes t = 0,1,2... M-1, where Mis the total number of classes. The index n runs over the decimation filter taps n = 0,1, 2...T-1 where Tis the total number of taps. The index/; runs over all the elements of the combined filter/; = 0,1,2 ... MT— 1. Since the combined filter embodies all classes, no class-coupling term is present. At block 1310, the method generates the L-weighted input signal as follows:
i **m>Fm>'"Fm J ^ **p=tT+m ~ **p \P *■)
where
19

Fp=Fp__tT+m= 2>"/ff5j (62)
{j\t=D(yf)}
At block 1315, the method extends the observation vector and correlation matrix into one joint vector and matrix for all classes. The solution equation for the combined filter has the matrix form:
*,=I^A, (63)
n
where the observation vector and correlation matrix are defined as:
x
h«=XFP(*)FJ*) (65)
X
At block 1320, the method extracts the solution for the combined decimation filter by direct matrix inversion:
H = (A)1b (66)
At block 1325, the method de-concatenates the decimation filter coefficients for each class H'n are from
the combined filter:
fiP = HtT+n - > {H<:° , H':1 ,...H<: M-J ; (6?)
The class-coupling term is incorporated into the combined L-weighted input signal. The solution structure
for the extended decimation filter is simply a matrix inversion.
[0059]The exact solution involves inverting the extended correlation matrix, which has a size of
MTxMT . For some cases, the number of taps may exceed 100 for a multi-field tap, and the number of
classes may exceed 128. The produces a large matrix with a correspondingly costly inversion operation.
In certain applications, such as HDTV (high definition TV) or UDTV (ultra definition TV), the
complexity cost may exceed available computational resources.
[0060]Figure 14 illustrates another method of extracting multiple decimation filters according to an
embodiment of the invention. In one embodiment, the method 500 may execute the method 1400 at block
20

520. The method reduces the complexity of the exact method illustrated in Figure 13 by only inverting matrixes for each class. This approximate method treats the class-coupling term as a modified observation vector. The method performs multiple passes to converge on a solution with lower, but similar, performance to the exact method illustrated in Figure 13. [0061]The solution for the multiple decimation filters may be defined as:
K=ZHnAn,>n+G'j{H^}) (68)
n
[0062]At block 1405, the method generates a correlation matrix and observation vector for each class. At block 1410, the method generates some initial values of the decimation filters (described below in greater detail in conjunction with Figure 15), and incorporates the class coupling term as a modification of the observation vector:
K=b'm-Gtm({Hv*t}) (69)
The solution for the multiple decimation filters takes the form:
K=Y.KK,m (70)
n
The method obtains the solution for the decimation filter for each class t as:
Ht=(At)1bt (71)
At block 1415, the method uses the decimation filter for each class to update the class-coupling term. At block 1420, the method generates a modified observation vector. At block 1425, the method uses the modified observation vector to obtain a new solution for the classified decimation filters. At block 1430, the method determines the prediction error given the new decimation filters. At block 1435, the method repeats this process for some number of iterations. Empirical data indicates that the prediction improvement saturates after 2-3 iterations. The prediction error at each stage may be computed to evaluate the effectiveness of the decimation filters at each pass. The complexity for this approximate process is order ~ 2M(T)X where X is a number between -2.4 and 3 depending on the matrix inversion method.
21

This compares favorably with extraction method illustrated in Figure 13, which has an order of complexity of ~ (MT)X, especially for large number of classes M.
[0063]Figure 15 illustrates a method of estimating initial decimation filters 1500 according to an embodiment of the invention. The prediction for a target pixel may involve multiple decimation classes, because the decimation class map is defined on the decimated data as
v = D(yJ) (72)
where x is the target pixel and {j}is the prediction filter tap index. As the tap index j runs over the prediction filter tap, each decimated data point y* may have a different class assigned to it, from the class
map D. The multiple classes associated with the target pixel generates the class-coupling term. [0064]The method introduces an initial estimation of the decimation filters with a map that assigns each target pixel to one decimation class. The method may use different types of assignments. At block 1505, the method obtains a target pixel-to-decimation class map as follows:
v = R(x) (73)
For example:
x(*) = »(yL) (74)
where
Jse„ct=suPjALUj\} (75)
[0065]The target pixel-to-decimation map means that for the target pixel x, the method uses the class associated with the decimated data y * that has the largest prediction filter coefficient. The largest
prediction filter coefficient is found over all the prediction filter tap positions indexed by/ In other embodiments, other definitions for associating a decimation class with a target pixel may be used. At block 1510, the method generates a modified input signal from image and prediction filters. The method generates a modified input signal for each class.
22

[0066] The method uses the target pixel-to-decimation class map to simplify the extraction of the decimation filters. The class coupling term is zero, and the solution has the form:
K=ZHnAn,>n (76)
n
At block 1515, the method modifies the correlation matrix and observation vector to contain the constraint from the map R(x). The modification is in the summation over the target pixels. The summation is now only over a partition of the full input space. In other words, only target pixels corresponding to a specific decimation class are summed.
Mathematically, the method modifies the observation vector and correlation matrix as follows:
K= YJI(x)FtJx) (77)
{x\t=R(x)S
4U= YJF'JXW'JX) (78)
{x\t=R(x)j
where the modified L-weighted input signal is defined as:
K(x)= ^L)I(zS) (79)
{ J select ( x)}
At block 1520, the method obtains the solution for the multiple decimation filters as follows:
H'=(A')1b' (80)
and extracts an initial decimation filter for each class from the modified correlation matrix and the modified correlation vector.
[0067] In one embodiment, as shown in Figure 11 A, a server computer 1101 is coupled to, and provides data through, the Internet 1105. A client computer 1103 is coupled to the Internet 1105 through an ISP (Internet Service Provider) 1107 [[1105]] and executes a conventional Internet browsing application to exchange data with the server 1101. Optionally, the server 1101 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
23

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.
[0068]One embodiment of a computer system suitable for use as server 1101 is illustrated in Figure 1 IB. The computer system 1110, includes a processor 1120, memory 1125 and input/output capability 1130 coupled to a system bus 1135. The memory 1125 is configured to store instructions which, when executed by the processor 1120, perform the methods described herein. The memory 1125 may also store data for adaptive decimation filtering. Input/output 1130 provides for the delivery and display of the data for adaptive decimation filtering or portions or representations thereof, and also the input of data of various types for storage, processing or display. Input/output 1130 also encompasses various types of machine-readable storage media, including any type of storage device that is accessible by the processor 1120. One of skill in the art will immediately recognize that the server 1101 is controlled by operating system software executing in memory 1125. Input/output 1130 and related media store the machine-executable instructions for the operating system and methods of the present invention as well as the data for an adaptive decimation filter.
[0069]The description of Figures 11A-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 1110 [[1140]] 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.
24

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.
[0070] An adaptive decimation filter 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.
25

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
apply an initial decimation filter to an original frame to generate a decimated frame;
extract an optimized prediction filter from the decimated frame and the original frame, wherein the initial decimation filter remains fixed;
generate a predicted frame from the optimized prediction filter and the decimated frame; and
extract an optimized decimation filter from the decimated frame and the predicted frame, wherein the optimized prediction filter remains fixed.
2. The system of claim 1, the instructions further comprising:
generate classes for the optimized prediction filter from the decimated frame.
3. The system of claim 1, the instructions further comprising:
generate classes for the optimized decimation filter from the predicted frame.
4. The system of claim 1, wherein extracting an optimized prediction filter comprises minimizing a prediction error of an initial prediction filter using least squares training.
5. The system of claim 1, wherein extracting an optimized decimation filter comprises minimizing a prediction error of the initial decimation filter using least squares training.
6. A data processing system comprising:
means for applying an initial decimation filter to an original frame to generate a decimated frame; means for extracting an optimized prediction filter from the decimated frame and the original frame, wherein the initial decimation filter remains fixed;
26

means for generating a predicted frame from the optimized prediction filter and the decimated frame; and
means for extracting an optimized decimation filter from the decimated frame and the predicted frame, wherein the optimized prediction filter remains fixed.
7. The data processing system of claim 6, further comprising:
means for generate classes for the optimized prediction filter from the decimated frame.
8. The data processing system of claim 6, further comprising:
means for generate classes for the optimized decimation filter from the predicted frame.
9. The data processing system of claim 6, wherein extracting an optimized prediction filter comprises minimizing a prediction error of an initial prediction filter using least squares training.
10. The data processing system of claim 6, wherein extracting an optimized decimation filter comprises minimizing a prediction error of the initial decimation filter using least squares training.
11. 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