Abstract:
A method for removing noise from a video input, prior to encoding includes receiving a frame of a video signal, identifying noise within the frame, and eliminating the noise from the frame. The video frame may then be encoded.

Description:
BACKGROUND 
   This invention relates to digital video technology and, more particularly, to video encoding. 
   Digital video is formed from a sequence of images produced by a video camera. The individual images are called video frames. To produce the illusion of motion, video frames are transmitted at 20 frames per second or higher, such that the human eye does not isolate individual frames. The eye then perceives the video images as a continuous video stream. 
   Transmitting video may use more bandwidth than transmitting audio. A throughput of 75 Mbits per second is common for digital video while an audio transmission might occur at only 75 Kbits per second. A 56 K baud modem transmits up to 56 K bits per second. Thus, before transmitting digital video from computer to computer, an encoding scheme is typically employed. 
   A number of digital video encoding standards are used today. For example, some may use temporal redundancy to encode video. Temporal redundancy is the repetition observed between consecutive video frames. Using temporal redundancy, the changes from one frame to another may be stored instead of storing each entire frame before transmission. 
   Many personal computer-based digital video capture systems produce noisy lines along the edges of video frames. For example, the noise may result from improper handling of closed captioning signals. Alternatively, limitations in the associated hardware devices or software drivers may produce such noise. 
   Before being transmitted across a telephone line or other media, the video frames are typically compressed or encoded. Like all the other pixels of the video frame, the noisy pixels are encoded. The noisy edge pixels may be difficult to encode. The noisy pixels are often random and vary significantly from frame to frame. The temporal redundancy is thus reduced, so more bits may be used to encode the noisy frames than frames without the noise. Further, when a video image is subdivided during the encoding process, the noisy lines along the edges of video frames may result in spurious frequency transform coefficients which are encoded along with the image. After decompression of the encoded noise, particularly at low bit rates, severe ringing artifacts may be visible along the noisy edges of the displayed video frame. 
   Thus, there is a continuing need for a mechanism for encoding video frames that have noise. 
   SUMMARY 
   In accordance with one embodiment of the invention, a method includes receiving a video frame, identifying noise in a first portion of the video frame, and replacing the first portion with a second portion of the video frame. 
   Advantages and other features of the invention will become apparent from the following description, the drawings, and the claims. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a block diagram of the noisy edge removal mechanism according to one embodiment of the invention; 
       FIG. 2   a  is a diagram of a top edge of a video frame according to one embodiment of the invention; 
       FIG. 2   b  is a diagram of a left edge of a video frame according to one embodiment of the invention; 
       FIG. 2   c  a diagram of a bottom edge of a video frame according to one embodiment of the invention; 
       FIG. 2   d  a diagram of a right edge of a video frame according to one embodiment of the invention; 
       FIG. 3  is a diagram of a video frame divided into units according to one embodiment of the invention; 
       FIG. 4  is a flow diagram of calculations performed during noisy edge detection according to one embodiment of the invention; 
       FIG. 5  is a flow diagram of noisy edge analysis and filtration according to one embodiment of the invention; 
       FIG. 6  is a flow diagram of the noisy edge removal mechanism according to one embodiment of the invention; and 
       FIG. 7  is a block diagram of a system using the noisy edge removal mechanism according to one embodiment of the invention. 
   

   DETAILED DESCRIPTION 
   In accordance with one embodiment of the invention, noisy edges in video frames may be removed to achieve higher frame rates and better quality video. The noisy edge removal mechanism may be used with applications which employ digital video encoding of captured content. Examples include video conferencing, video phone, network streaming video, and others. 
   By detecting the presence of noisy edges in a video frame, a noisy line may be removed and replaced by a clean neighboring line prior to encoding. Noise may be removed from the top edge, either side edge, or the bottom edge of the video frame  10  as needed. 
   Turning to  FIG. 1 , a noisy edge removal mechanism  20  may filter noise from a video frame  10  prior to entering a video encoder  18 . In one embodiment of the invention, the noisy edge removal mechanism  20  includes a noisy edge detector  14  and a noisy edge filter  16 . 
   Initially, the noisy edge detector  14  receives a frame  10 . The frame  10  is one of a plurality of frames  10  which make up a stream of video. The noisy edge removal mechanism  20  may be invoked for each frame  10  of the video stream, one at a time. 
   For each frame  10 , the noisy edge detector  14  analyzes one or more edges of the video frame  10 . In one embodiment of the invention, an edge of the video frame  10  is selected, then divided into four equally sized portions. In  FIG. 2   a , the top edge of the video frame  10  is divided into portions  20   a ,  21   a ,  22   a , and  23   a . These portions may be rows of the video frame  10 , for example. 
   In  FIG. 2   b , the left edge of the video frame  10  is divided into portions  20   b ,  21   b ,  22   b , and  23   b . These portions may be columns of the video frame  10 , for example. In  FIG. 2   c , the bottom edge of the video frame  10  is divided into portions  20   c ,  21   c ,  22   c , and  23   c . In  FIG. 2   d , the right edge of the video frame is divided into portions  20   d ,  21   d ,  22   d , and  23   d.    
   Once the edge of the video frame  10  is divided into portions of equal size, the portions are then subdivided into units of equal size. In  FIG. 3 , a part of the video frame  10  of  FIG. 2   a  is subdivided into a plurality of units  24 . Portion  20   a  includes units  24   a ,  24   b ,  24   c ,  24   d ,  24   e , and  24   f . Portion  21   a  includes units  24   g ,  24   h ,  24   i ,  24   j ,  24   k , and  24   l . Portion  22   a  includes units  24   m ,  24   n ,  24   o ,  24   p ,  24   q , and  24   r . Portion  23   a  includes units  24   s ,  24   t ,  24   u ,  24   v ,  24   w , and  24   x.    
   Each unit  24  of the video frame  10  is associated with a value. For example, a video display may be subdivided into pixels. Each pixel commonly has a value associated with the pixel, which may be stored in video memory. Each unit  24  of  FIG. 3  may likewise be associated with a distinct value. 
   In one embodiment of the invention, the noisy edge detector  14  determines the presence of noise based, in part, on comparisons between the values of the units  24  of the video frame  10 . If adjacent units  24  are not similar, for example, noise may sometimes be inferred. So, once the video frame  10  is divided into discrete units  24 , each one of which is assigned a value, mathematical operations may be performed to analyze the video frame  10 . 
   Comparisons between values of the units  24  may be made using mathematical operations. In one embodiment, the values of the units  24  in one portion are compared to the values of the units  24  in a second, adjacent portion. The results of these comparisons are added together, to arrive at a result which is representative of the relationship between the two portions. A second pair of portions is likewise analyzed, supplying a second result, and so on. These results are then compared, and analyzed against one or more threshold values. In one embodiment of the invention, the threshold values may be adaptable to the type of noise or other criteria. 
   In  FIG. 4 , an analysis of the video frame  10 , according to one embodiment of the invention, commences with the selection of an edge of the video frame (top, right, left, or bottom), subdivision of the video frame  10  into portions of equal size, and further subdivision in to units  24  (block  70 ). Although the following examples describe dividing an edge of the video frame  10  into four portions, the analysis hereinafter described may be performed on a larger or smaller number of portions, as desired. 
   A value is associated with each unit  24 . The value may be an 8-bit binary value, a 16-bit binary value, or other value. The values are used to compare each unit  24  with another unit  24  in order to detect the presence of noise in the video frame  10 . 
   Once the edge of the video frame  10  has been subdivided into units  24 , a pair of threshold values, T 1  and T 2 , may be calculated (block  72 ). The threshold values are used to determine whether a value associated with one portion  20 ,  21 ,  22  or  23  of the video frame  10  varies significantly from a value associated with a second portion  20 ,  21 ,  22 , or  23  of the video frame  10 . 
   In one embodiment of the invention, these threshold values are based upon two variables, α and β. The values for α and β may be determined by analyzing one or more video frames  10  in which noise is known to be present. The values for α and β may also be based upon the source of the noise. For example, noise which results from the improper handling of closed captioning signals may produce a certain, predictable type of noise, to which a particular α value may be assigned. Alternatively, certain types of video capture devices may produce noise along the edges of the video frame, and thus a particular α or β variable may be appropriate. The a variable is presumed larger than the β variable, so that both a “stronger” (or larger) threshold value and a “weaker” (or smaller) threshold value may be used to analyze the edge of the video frame  10 . 
   In one embodiment of the invention, once the α and β variables are known, T 1  and T 2  may be calculated based upon the following formulas:
 
 T   1 =(# units/portion)×α
 
 T   2 =(# units/portion)×β
 
where α&gt;β. Because α&gt;β, the threshold value T 1  is greater than the threshold value T 2 .
 
   In addition to being created based upon the type of noise and other criteria, the α and β variables, and thus the threshold values, T 1  and T 2 , may be changed during the analysis of the input video signal. For example, following analysis of the first few video frames  10  of a video signal, the α and β variables may be adjusted, if desired. 
   Looking back at  FIG. 4 , a comparison of units  24  along an edge of the video frame  10  is performed (block  74 ). The comparison may be performed in a number of ways. In one embodiment of the invention, all units  24  of one portion are subtracted from all units  24  of an adjacent portion, to arrive at a plurality of results, the absolute values of which are then added together. This is called the sum of absolute differences, or SAD. 
   For example, looking back at  FIG. 3 , the sum of absolute differences between portions  20   a  and  21   a  is:
 
 SAD   20a21a =|( 24   a − 24   g )+( 24   b − 24   h )+( 24   c − 24   i )+( 24   d − 24   j )+( 24   e − 24   k )+( 24   f − 24   l )+ . . . |
 
where “ 24   a ” means “the value of unit  24   a ,” etc. The sum of absolute differences between portions  21   a  and  22   a  is:
 
 SAD   21a22a =|( 24   g − 24   m )+( 24   h − 24   n )+( 24   i − 24   o )+( 24   j − 24   p )+( 24   k − 24   q )+( 24   l − 24   r )+ . . . |
 
and the sum of absolute differences between portions  22   a  and  23   a  is:
 
 SAD   22a23a =|( 24   m − 24   s )+( 24   n − 24   t )+( 24   o − 24   u )+( 24   p − 24   v )+( 24   q − 24   w )+( 24   r − 24   x )+ . . . |
 
Following these calculations, three values, SAD 20a21a , SAD 21a22a , and SAD 22a23a  result. These SAD values provide a discrete measure for analysis of the portions  20  through  23  of the video frame  10 , not just the units  24  contained therein.
 
   Although the units  24  for four portions are compared to arrive at three SAD results, comparison of five portions to arrive at four SAD results, comparison of six portion to arrive at five SAD results, and so on, may be made. Alternatively, two portions may be compared to arrive at a single SAD result or three portions may be compared to arrive at two SAD results. 
   Turning back to  FIG. 4 , once the SAD values for the portions  20  through  23  are determined, these values may be analyzed as well (block  76 ). In one embodiment of the invention, the “adjacent” SAD values are subtracted from one another, to arrive at one or more difference values, Dn. 
   For example, in the video frame  10  of  FIG. 3 , because there are three SAD values, two difference values, D 1  and D 2 , may be calculated as follows:
 
 D   1   =|SAD   20a21a   −SAD   21a22a |
 
 D   2   =|SAD   21a22a   −SAD   22a23a |
 
The difference value, D 1 , results from calculations related to portions of the video frame  10  which are relatively closer to the edge of the video frame  10 , such as portions  20   a ,  21   a , and  22   a . The difference value, D 2 , results from calculations of portions related to the video frame  10  which are relatively further from the edge of the video frame  10 , such as portions  21   a ,  22   a , and  23   a . Where more than three SAD values are calculated, more difference values may likewise be calculated, as needed.
 
   In one embodiment of the invention, once the difference values, D 1  and D 2 , are calculated, they may then be analyzed against the threshold values, T 1  and T 2 . Recall that the threshold value T 1  is calculated based upon the variable α while the threshold value T 2  is calculated based upon the variable β. In one embodiment of the invention, α is greater than β. Accordingly, T 1  is greater than T 2  in value. Thus, a difference value which is larger than T 1  is presumed to be more likely to have noise than a difference value which is larger than T 2 . 
   In one embodiment of the invention, the presence of noise in a previous video frame  10  is relevant to the analysis of one or more subsequent frames. Recall from  FIG. 1  that the noisy edge detection mechanism  20  receives each video frame  10  of the input video signal, one after another. Thus, the result of the analysis of a prior frame may be used in the analysis of subsequent frames. 
   A Boolean variable, NOISEFOUND, may be used to keep track of noise found in a previous frame. The variable may then be used during analysis of a subsequent frame. Although the variable NOISEFOUND provides information about the detection of noise from a single prior frame, multiple variables may alternatively be included in the analysis of multiple subsequent frames, as desired. 
   In accordance with one embodiment of the present invention, the analysis includes four comparisons between the values, D 1 , D 2 , T 1 , and T 2 , as shown in  FIG. 5 . In one comparison, if D 2  is greater than T 1 , because T 1  is the larger threshold value, noise is presumed to be found (diamond  82 ). Accordingly, two outermost portions, portion  20  and portion  21  of the video frame  10  are replaced with a third portion, portion  22 , which is closer in from the edge of the video frame  10  (block  90 ). 
   For example, in  FIG. 2   c , portions  20   c  and  21   c  is replaced with portion  22   c . The edge of the video frame  10  then includes, from the outside in, portions  20   c ,  20   c ,  20   c , and  23   c  (the fourth portion,  23   c , is not replaced). 
   Next, D 2  is compared to T 2  (diamond  84 ). If D 2  is larger than T 2 , then D 2  is in between the two threshold values, T 1  and T 2 . If, D 2  is between the two threshold values, and noise was found in the previous frame (as denoted by NOISEFOUND being TRUE), noise is presumed to be found (diamond  84 ). The two outermost portions, portion  20  and portion  21 , of the video frame  10  are replaced with a third portion, portion  22 , which is closer in from the edge of the video frame  10  (block  90 ). 
   Next, the difference value D 1  is compared to the threshold values. If D 1  is larger than T 1  (diamond  86 ), a first portion  20  of the video frame  10  is replaced with a second portion  21  which is farther from the edge (block  92 ). For example, in  FIG. 2   d , portion  20   d  is replaced with portion  21   d . The edge of the video frame  10  then includes, from the outside in, portions  21   d ,  21   d ,  22   d , and  23   d.    
   The difference value D 1  is then compared to the second threshold value T 2  (diamond  86 ). If D 1  is in between the two threshold values and noise was found in the previous frame, a first portion  20  of the video frame  10  is replaced with a second portion  21  which is farther from the edge (block  92 ). If D 1  is smaller than both threshold values, T 1  and T 2 , then no noise is presumed, and no action is taken (block  94 ). 
   Recall that D 1  relates to portions  20  through  22  of the video frame  10  which are relatively closer to the edge, while D 2  relates to portions  21  through  23  of the video frame which are relatively farther from the edge. Accordingly, in the analysis of D 1 , the replacement of a single portion  20  with a second portion  21 , occurs (block  92 ), while, in the analysis of D 2 , the replacement of two portions, portions  20  and  21 , with a third portion, portion  22 , occurs (block  90 ). 
   The above calculations identify noise by observing the spatial correlation between the portions  20  through  23  along the edge of the video frame  10 . In other words, how similar portions  20  through  23  are to one another help to identify noise in the video frame  10 . In addition to the calculations, noise detection in the previous frame may be included in analyzing the current frame. Once the noisy edge detector  14  has completed the analysis, the noisy edge filter  16  may replace one or more portions of the video frame  10  with a clean neighboring portion, in one embodiment of the invention. A new video frame  11  may then enter the video encoder  18 . 
   A software program, for implementing one embodiment of the invention, shown in  FIG. 6 , begins by clearing the Boolean variable, NOISEFOUND (block  102 ). NOISEFOUND indicates whether the previous frame required noise removal. An integer variable, FRAME, is also cleared to zero. FRAME keeps track of the current frame. FRAME is incremented (block  104 ). 
   For the current video frame received, the sum of absolute differences for the first four portions  20  through  23  of the video frame  10  is calculated (block  106 ). These calculations result in three values, SAD 2021 , SAD 2122 , and SAD 2223 . Although four portions of the video frame  10  are analyzed in the example, this number may be adjusted to a larger or smaller number, as desired. 
   From the SAD values, two difference values, D 1 , and D 2 , are calculated. D 1  is the absolute value of the difference between SAD 2021  and SAD 2122 . Likewise, the second difference value, D 2 , represents the difference between SAD 2122  and SAD 2223 . The threshold values, T 1  and T 2 , are calculated (block  110 ). Once the calculations D 1 , D 2 , T 1 , and T 2  are completed, analysis of the video frame  10  for noise may begin. 
   In one embodiment of the invention, a series of queries determines whether the difference values D 1  and D 2  exceed the threshold values T 1  and T 2  (diamond  112 ). If the second difference value, D 2 , is greater than the first threshold value, T 1 , then noise has been detected. Accordingly, portions one and two of the video frame  10  are replaced with portion three (block  120 ). Further, the variable NOISEFOUND is set to TRUE (block  122 ), indicating that noise was found on the current frame. During analysis of subsequent frames, the variable NOISEFOUND is again tested. 
   Next, if the second difference value, D 2 , exceeds the second threshold value, T 2 , and the variable NOISEFOUND is TRUE, then noise has again been detected (diamond  114 ). Again, portions one and two are replaced with portions three of the video frame  10  (block  120 ). 
   Where the first two calculations fail to result in noise detection, a second pair of inquiries may be initiated. The first difference value, D 1 , is compared to the first threshold value, T 1  (diamond  116 ). If D 1  is larger, noise has been detected. In contrast to the result in block  120 , however, only portion one is replaced with portion two (block  124 ). Otherwise, D 1  may be compared with the second threshold value, T 2 . If D 1  is greater than T 2  and the variable NOISEFOUND is TRUE, then noise is detected (diamond  118 ). Again, portion one is replaced with portion two (block  124 ). The variable NOISEFOUND is set to TRUE (block  122 ). Otherwise, the variable NOISEFOUND is set to FALSE (block  126 ). 
   Following updates of the variable NOISEFOUND (block  122  and  126 ), the noisy edge removal mechanism  20  inquires whether the last frame has been reached (diamond  128 ). If so, the operation is complete (block  130 ). Otherwise, the variable FRAME is incremented and the process is repeated (block  104 ). 
   In  FIG. 7 , in accordance with one embodiment of the invention, a processor-based system  70  may include a processor  30  coupled to an accelerated graphics port (AGP) chipset  52 . The Accelerated Graphic Port Specification, Rev. 2.0 is available from Intel Corporation of Santa Clara, Calif. The AGP chipset  52  is coupled to a display  58  and a system memory  34 . The AGP chipset  52  is further coupled to a bus  38 , for coupling to other circuitry of the processor-based system  70 . 
   A bridge  36  coupled between the bus  38  and a secondary bus  40  is coupled to a hard disk drive  44 . The noisy edge removal mechanism  20  and the video encoding software  18  may be stored on the hard disk drive  44 . A multi-function, super I/O, or SIO, chip  42 , coupled to the secondary bus  40 , may support several devices in the processor-based system  70 , including a floppy disk drive  46 , a keyboard  48 , a mouse  50  and a modem  64 . Also coupled to the secondary bus  40  is a video capture device  60 . A video input signal  62  may enter the system  70  from the video capture device  60 . 
   The noisy edge removal mechanism  20  may be stored on the hard disk drive  44  such that, upon receiving the video input signal  62 , the noisy edge removal program  20  is loaded into the memory  34  and executed. The video encoder  18 , also stored on the hard disk drive  44  in one embodiment of the invention, may be used to encode the resulting frames. 
   In some embodiments of the invention, a noisy edge removal mechanism may remove noisy edges from a video frame prior to transmission. Where noisy edges are removed from a digital image, temporal prediction between frames of the digital image may result. In a digital image where temporal prediction improves, fewer bits may be used to encode the digital image. Where noisy lines are removed from a digital image, spurious frequency transform coefficients may be reduced. Where fewer bits are used to encode a digital image, a faster frame rate may result or the video quality may improve. 
   While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.