Abstract:
A method for encoding and decoding a video signal having frames with blocks comprised of pixels. The method reduces the complexity of the video signal to be encoded by applying a filter scheme to the input data stream in an encoder and later reversing the filter scheme in a decoder. A number of filter schemes may be tested to determine the best filter scheme that most reduces the number of distinct color values per color plane. The best filter scheme is used to filter the data to be encoded. Filter information of the best filter scheme is included in the encoded data to enable the decoder to identify the best filter scheme in order to apply the best filter scheme in reverse to re-create the original data stream.

Description:
TECHNICAL FIELD 
     The present invention relates in general encoding and decoding video data. 
     BACKGROUND 
     An increasing number of applications today make use of digital video for various purposes including, for example, remote business meetings via video conferencing, high definition video entertainment, video advertisements, and sharing of user-generated videos. As technology is evolving, users have higher expectations for video quality and expect high resolution video even when transmitted over communications channels having limited bandwidth. 
     To permit higher quality transmission of video while limiting bandwidth consumption, a number of video compression schemes are noted including formats such as VPx, promulgated by Google Inc. of Mountain View, Calif., and H.264, a standard promulgated by ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG), including present and future versions thereof. H.264 is also known as MPEG-4 Part 10 or MPEG-4 AVC (formally, ISO/IEC 14496-10). 
     These compression schemes generally break the image up into blocks and use one or more techniques to limit the amount of information included in a resulting digital video bitstream for transmission. The bitstream, once received, is then decoded to re-create the blocks and the source images from the limited information. 
     SUMMARY 
     Systems and methods for encoding and decoding a video signal are disclosed. In accordance with one aspect of the disclosed embodiments, a method is provided for encoding video data. The method includes applying a plurality of filter schemes to at least a portion of the data to generate a plurality of filter outputs, each filter output having data indicating the color values included in the filter output. The method also includes determining the color variance of at least some of the plurality of filter outputs using a processor. The method further includes selecting at least one of the plurality of filter schemes based on the color variance of the filter output generated using the selected filter scheme. 
     In accordance with another aspect of the disclosed embodiments, a method is provided for encoding data representing an image that is intended for display on a computer monitor. The method includes applying a plurality of filter schemes to at least a portion of the data to generate a plurality of filter outputs. The method also includes identifying at least one filter output that has a low color variance relative to the other filter outputs using a processor. The method further includes selecting that one of the filter outputs having the low color variance; and encoding the selected filter output. 
     In accordance with another aspect of the disclosed embodiments, a method is provided for decoding a data stream representing a video image. The method includes identifying, within the data stream, filter information indicative of the filter scheme applied to the data during encoding, selecting an anti-aliasing filter based on the filter information using a processor, and filtering the data using the selected anti-aliasing filter. 
     In accordance with another aspect of the disclosed embodiments, a method is provided for reducing the complexity of a data stream to be encoded. The method includes (1) identifying at least one target block from the data stream, (2) obtaining an original set of color values that contains each distinct color value used in the at least one target block, (3) applying a plurality of filter schemes to the at least one target block to generate a plurality of filter outputs using a processor, (4) determining a filtered set of color values for each of the plurality of filter outputs, each filtered set of color values containing each distinct color value used in its associated filter output, and (5) selecting the filter scheme of the filter output that most reduces the complexity of the at least one target block. 
     In accordance with another aspect of the disclosed embodiments, an apparatus for encoding video is provided including a processor and a memory. The processor is configured to (1) apply a plurality of filter schemes to at least a portion of the data stored in memory to generate a plurality of filter outputs, each filter output having data indicating the color values included in the filter output, (2) determining the color variance of at least some of the plurality of filter outputs, and (3) selecting at least one of the plurality of filter schemes based on the color variance of the filter output generated using the selected filter scheme. 
     In accordance with another aspect of the disclosed embodiments, an apparatus for decoding video data is provided including a processor and a memory. The processor is configured to (1) identify, within the data stream, filter information indicative of the filter scheme applied to the data during encoding, (2) select an anti-aliasing filter based on the filter information, and (3) filter the data using the selected anti-aliasing filter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The description herein makes reference to the accompanying drawings wherein like reference numerals refer to like parts throughout the several views, and wherein: 
         FIG. 1  is a diagram of an encoder and decoder system in accordance with one embodiment; 
         FIG. 2  are exemplary specimens of an anti-aliased image and a rasterized image; 
         FIG. 3  is an exemplary block diagram of a encoder; 
         FIG. 4  is an exemplary block diagram of a decoder; 
         FIG. 5  is an exemplary block diagram of the edge sharpening filter of  FIG. 3 ; 
         FIG. 6  is an exemplary block diagram of the blurring filter of  FIG. 4 ; 
         FIG. 7  is an exemplary list of filters used when selecting the filters in  FIGS. 5 and 6 . 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a diagram of an encoder and decoder system  10  for still or dynamic video images. An exemplary transmitting station  12  may be, for example, a computer having an internal configuration of hardware including a central processing unit (CPU)  14  and memory  16 . The CPU  14  is a controller for controlling the operations of transmitting station  12 . The CPU  14  is connected to memory  16  by, for example, a memory bus. The memory  16  may be random access memory (RAM) although any other type of storage can be used. The memory  16  stores data and program instructions which are used by the CPU  14 . The memory  16  can be in the same chip or machine as CPU  14  or located in a separate unit that is coupled to CPU  14  to form an apparatus. Other suitable implementations of transmitting station  12  are possible such as those explained later. 
     A display  18  configured to display still or dynamic video images is connected to transmitting station  12 . The display  18  may be implemented in various ways, including by a liquid crystal display (LCD) or a cathode-ray tube (CRT). The display  18  may also be configured for other uses, such as screencasting. The display  18  can display an anti-aliased image  20 , which in this case is demonstrated by an image of a character glyph “A.” 
     A network  22  connects the transmitting station  12  and a receiving station  24 . The network  22  may, for example, be what is commonly known as the internet. The network  22  may also be a local area network (LAN), wide area network (WAN), virtual private network (VPN), or any other means of transferring data between transmitting station  12  and receiving station  24 . 
     The exemplary receiving station  24  may be a computer having an internal configuration of hardware include a central processing unit (CPU)  26  and a memory  28 . The CPU  26  is a controller for controlling the operations of transmitting station  12 . The CPU  26  is connected to memory  28  by, for example, a memory bus. The memory  28  may be random access memory (RAM). The memory  28  stores data and program instructions which are used by the CPU  26 . Other suitable implementations of receiving station  24  are possible such as those explained later. 
       FIG. 2  shows enlarged exemplary specimens of the anti-aliased image  20  and the rasterized image  20 ′ that anti-aliased image  20  is derived from. As is apparent, the rasterized image  20 ′ appears “jagged” at its edges whereas the anti-aliased image  20  does not. Anti-aliasing techniques are typically employed to avoid the “jagged” appearance of rasterized images and are typically associated with images of character glyphs, but may be applied to other images as will be apparent to those skilled in the art. Anti-aliasing is only an exemplary method of smoothing rasterized image  20 ′. Other techniques similar to or that are a subset of anti-aliasing will be apparent to those skilled in the art. For example, subpixel rendering may be utilized. Typically, the display  18  will include one or more anti-aliased type images such as anti-aliased image  20 . 
     Rasterized images, such as the rasterized image  20 ′, represent an original image (usually a vector-based character glyph) typically by assigning each pixel in the rasterized image  20 ′ one of two color values. Each pixel in the resulting image must have a single color value even if the original character glyph has more than one color value in the area represented by the pixel (as shown in a rasterized image portion  34 ). For example, the areas represented by pixels  34   a - d  might each have two color values in the original character glyph. To be represented in the rasterized image, pixels  34   a - b  are represented by one color value and pixels  34   c - d  are represented by another color value. 
     Anti-aliased images, such as anti-aliased image  20 , represent an original image by assigning each pixel various color values as determined by an anti-aliasing filter. An exemplary anti-aliasing filter can typically assign each pixel in the anti-aliased image  20  multiple shades of color values in between the two original color values in the original character glyph. An example is shown in anti-aliased image portion  36 . In this example, the area represented by pixels  36   b - c  each includes two color values in the original character glyph. The pixels  36   a - d  are each represented in the anti-aliased image  20  by one of the original two color values as shown by pixels  36   a  and  36   d  and also by various shades of color values in between the original two color values as shown by pixels  36   b - c . Anti-aliasing may be implemented using many different types of filters that may, for example, vary the shade of colors used and the number of pixels over which the anti-aliasing filter will have an effect. 
       FIG. 3  shows an exemplary block diagram of an encoder  50  implemented on transmitting station  12 . The encoder  50  takes a raw or uncompressed or partially compressed video signal  52  as input. Input signal  52  is, for example, the digital representation of an image to be encoded. The input signal  52  may alternatively be the representation of a video image or other analogous data. The input signal  52  will include, at least in part, an anti-aliased type image such as anti-aliased image  20 . 
     The input signal  52  typically includes data relating to the color values of pixels of the image or video image it represents. The included pixels can be grouped into blocks, macroblocks, and frames. Blocks and macroblocks are groups of pixels found in an image, typically having dimensions of 16×16 or 8×8 pixels. However, blocks and macroblocks may be of any desirable size. Frames are a group of blocks and macroblocks that together comprise an entire image, such as the entire screen of display  18 . If the input signal  52  represents a dynamic video image, it will include multiple frames, each representing a still image in the dynamic video image. 
     The encoder  50  produces an encoded video signal  54  as output. Encoded video signal  54  is an encoded digital representation of an image that has been encoded by encoder  50 . The encoded video signal  54  is in a format suitable for transmission to the receiving station  24  via network  22 . 
     The encoder  50  includes an edge sharpening filter  56  and an encoding module  58 . Edge sharpening filter  56  selects and applies a filter scheme to a signal derived from input signal  52  with the goal of reducing the complexity of input signal  52 . The complexity of input signal  52  may be decreased, for example, by reducing the color variance in the input signal  52 , such as measured by the number of distinct color values included in the input signal  52 . Data identifying the selected filter scheme is included in the resulting filtered signal. Details of the filter scheme are discussed in more detail later with respect to  FIG. 7 . The resulting filtered signal is then encoded by encoding module  58  into a signal from which the encoded video signal  54  is derived. It may be desirable for encoder operation  50  to include other modules and encoding steps in addition to those listed, such as a pre-processing module or a post-processing module. 
       FIG. 4  shows an exemplary block diagram of a decoder  70  of receiving station  24 . The decoder  70  takes an encoded video signal  72  as input. Encoded video signal  72  is an encoded digital representation of an image (input signal  52 ) that has previously been encoded by encoder  50  on transmitting station  12 . Decoder  70  produces a decoded video signal  74  as output. Decoded video signal  74  is, for example, the digital representation of an image that was previously encoded by encoder  50 . Decoded video signal  74  may alternatively be the representation of a video image or other analogous data. Decoded video signal  74  will include, at least in part, an anti-aliased type image such as anti-aliased image  20 . 
     The decoder  70  includes a decoding module  76  and a blurring filter  78 . The decoding module  76  decodes a signal derived from encoded video signal  72  into a signal comparable to the signal that existed prior to encoding by encoding module  58 . A derivation of the signal decoded by decoding module  76  is then processed by the blurring filter  78 . Blurring filter  78  selects a filter scheme to blur the decoded signal using the filter identification included into the signal by edge sharpening filter  56 . The selected filter scheme is applied to the decoded signal, from which the decoded video signal  74  is derived by the decoder  70 . Details of the filter scheme are discussed in more detail later with respect to  FIG. 7 . 
       FIG. 5  shows an exemplary block diagram of the process performed by edge sharpening filter  56  on a block of pixels selected from the input signal  52  ( 100 ). The first step is to select a color plane ( 102 ). For example, a color plane may be one of red, green, or blue (RGB). Color planes may alternatively be defined using other methodologies. For example, a color plane may be one of Y′ (luma), Cb (blue-difference chroma), or Cr (red-difference chroma) (YCbCr). 
     After the color plane is selected, the edge sharpening filter  56  then determines the color variance of the block of pixels by counting the number of distinct color values found in the block of pixels within that color plane ( 104 ). The “Max” and “Best Filter” variables are then initialized ( 106 ). Max is initialized to the count from step  104 . Best Filter is initialized to nothing (NULL). As explained below, the Best Filter is the filter with the lowest color variance, which in this case is determined as the lowest count of distinct color values. 
     Once initialized for the color plane, the edge sharpening filter  56  selects the next available filter scheme for evaluation ( 108 ). It then applies the filter scheme to the block of pixels being processed ( 110 ). The number of distinct color values found in the filtered block of pixels is then counted ( 112 ) to determine the color variance of the filtered block. Edge sharpening filter  56  then determines whether the count from step  112  is less than the current value of Max ( 114 ). If the value is less, the currently selected filter is the best filter scheme of all of those applied at this point. If so, the variable Max is set to the count from step  112 , and the variable Best Filter is set to the currently selected filter scheme. If the value is not less, then the variables are left unchanged. 
     Edge sharpening filter  56  then determines whether there are additional filter schemes available to be applied ( 118 ). If there are additional filter schemes available, the edge sharpening filter  56  then returns to step  108  to select the next filter scheme. Otherwise, the edge sharpening filter  56  then determines whether there are additional color planes to select ( 120 ). If there are additional color planes available, the edge sharpening filter  56  then returns to step  102  to select the next color plane. Otherwise, the edge sharpening process  100  completes and the edge sharpening filter  56  outputs the filtered signal created using the Best Filter. The output includes data indicating which filter scheme was used (the Best Filter). Process  100  is only illustrative of the implementation of edge sharpening filter  56 . Other suitable implementations are possible. 
     In the disclosed embodiment, determining the color variance of at least some of the plurality of filter output is performed by counting the number of different color values in the filter output. Color variance can be measured in other ways as well. For example, color variance can be determined by calculating the statistical dispersion of color values in at least a portion of the filter output. Alternatively, similar colors can be counted as one color in performing the count of colors. Alternatively, color variance can be determined by determining if the color values in at least a portion of the filter output include a dominant color value. For example, a histogram of color values can reveal that one color or a range of colors are numerically dominant over other colors. 
       FIG. 6  shows an exemplary block diagram of the process performed by blurring filter  78  on the input signal derived from decoding module  76  ( 150 ). The first step in the process is to select a color plane ( 152 ). As described above with respect to the edge sharpening filter  56  process  100 , color planes may be represented through a number of different methodologies, including, but not limited to, RGB and YCbCr representations. After the color plane is selected, blurring filter  78  determines the filter scheme used from the data included in the input signal by the edge sharpening filter  56  ( 154 ). 
     Blurring filter  78  then applies the selected filter scheme to the input signal to reproduce the original anti-aliased type image for the selected color plane ( 158 ). If additional color planes are available in the input signal, the blurring filter  78  returns to step  152  to select another color plane. Otherwise, the blurring filter process  150  completes and the blurring filter  78  then outputs the filtered signal created using the selected filter scheme. Process  150  is only illustrative of the implementation of blurring filter  78 . Other suitable implementations are possible. 
       FIG. 7  shows an exemplary list of filter schemes  180  utilized by edge sharpening filter  56  process  100  and blurring filter  78  process  150 . The list of filters  180  includes data for an index  182  and a filter information  184 . 
     The index  182  represents the identifying value of a filter. This identifying value can be embedded in the output signal from edge sharpening filter  56  to identify which filter was selected to sharpen the raw input signal  52 . Accordingly, the blurring filter  78  can use the same value to select the appropriate reverse filter to recreate the original input signal  52  from the signal derived from the output signal from edge sharpening filter  56 . 
     The filter information  184  represents the scheme of the filter used in the edge sharpening filter  56  to sharpen the input signal  52  and in the blurring filter  78  to blur the signal derived from the output signal from edge sharpening filter  56  (i.e. to reverse the effects of edge sharpening filter  56  to recreate input signal  52 ). The shown structure and content of list of filters  180  is intended to be illustrative only. Other implementations of list of filters  180  are available. 
     A Finite Impulse Response (FIR) filter is a type of filter that could be represented by filter information  184 . A FIR filter will produce at least one output color value for a target pixel (y[n]) based upon the weighted sum of color values of adjoining pixels. The number of input values to the filter is called the number of “taps.” The order of the filter is the number of taps minus one (N). The filter will have a coefficient value associated with each tap position (b i ) which indicates the weight assigned to the color value of each input value (x[n]) when calculating the output color value for the target pixel. An FIR filter as described can be expressed mathematically as the following exemplary convolution kernel: 
     
       
         
           
             
               y 
               ⁡ 
               
                 [ 
                 n 
                 ] 
               
             
             = 
             
               
                 ∑ 
                 
                   i 
                   = 
                   0 
                 
                 N 
               
               ⁢ 
               
                 
                   b 
                   i 
                 
                 ⁢ 
                 
                   x 
                   ⁡ 
                   
                     [ 
                     
                       n 
                       - 
                       i 
                       + 
                       
                         N 
                         2 
                       
                     
                     ] 
                   
                 
               
             
           
         
       
     
     Rows  186   a - c  of list  180  contain exemplary filter information (coefficient values) for the exemplary FIR filter described above. Rows  186   a  and  186   b , for example, contain filter information for a filter implementation having seven taps. Row  186   c , for example, contains filter information for a filter implementation having three taps. The FIR filter implementation described is intended to be illustrative only. A filter implementation can also include those with five taps or nine taps. Other suitable implementations of the FIR filter and other suitable filters in general are available. 
     The operation of encoding can be performed in many different ways and can produce a variety of encoded data formats. The above-described embodiments of encoding or decoding may illustrate some exemplary encoding techniques. However, in general, encoding and decoding are understood to include any transformation or any other change of data whatsoever. 
     The embodiments of transmitting station  12  and/or receiving station  24  (and the algorithms, methods, instructions etc. stored thereon and/or executed thereby) are implemented in whole or in part by one or more processors which can include computers, servers, or any other computing device or system capable of manipulating or processing information now-existing or hereafter developed including optical processors, quantum processors and/or molecular processors. Suitable processors also include, for example, general purpose processors, special purpose processors, IP cores, ASICS, programmable logic arrays, programmable logic controllers, microcode, firmware, microcontrollers, microprocessors, digital signal processors, memory, or any combination of the foregoing. In the claims, the term “processor” should be understood as including any the foregoing, either singly or in combination. The terms “signal” and “data” are used interchangeably. 
     Further, portions of transmitting station  12  and receiving station  24  do not necessarily have to be implemented in the same manner. Thus, for example, edge sharpening filter  56  can be implemented in software whereas encoding module  58  can be implemented in hardware. In one embodiment, for example, transmitting station  12  can be implemented using a general purpose computer/processor with a computer program that, when executed, carries out any of the respective methods, algorithms and/or instructions described herein. In addition or alternatively, for example, a special purpose computer/processor can be utilized which can contain specialized hardware for carrying out any of the methods, algorithms, or instructions described herein. 
     Transmitting station  12  and receiving station  24  can, for example, be implemented on computers in a screencasting system. Alternatively, transmitting station  12  can be implemented on a server and receiving station  24  can be implemented on a device separate from the server, such as a hand-held communications device (i.e. a cell phone). In this instance, transmitting station  12  can encode content using encoder  50  into encoded video signal  52  and transmit encoded video signal to the communications device. In turn, the communications device can then decode the encoded video signal  52  using decoder  70 . Alternatively, the communications device can decode content stored locally on the communications device (i.e. no transmission is necessary). Other suitable transmitting station  12  and receiving station  24  implementation schemes are available. For example, receiving station  24  can be a personal computer rather than a portable communications device. 
     Further, all or a portion of embodiments of the present invention can take the form of a computer program product accessible from, for example, a computer-usable or computer-readable medium. A computer-usable or computer-readable medium can be any device that can, for example, contain, store, communicate, or transport the program for use by or in connection with any computing system or device. The medium can be, for example, an electronic, magnetic, optical, electromagnetic, or a semiconductor device. Other suitable mediums are also available. 
     The above-described embodiments have been described in order to allow easy understanding of the present invention and do not limit the present invention. On the contrary, the invention is intended to cover various modifications and equivalent arrangements included within the scope of the appended claims, which scope is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structure as is permitted under the law.