Choosing video deinterlacing interpolant based on cost

Abstract

Deinterlacing of video involves converting interlaced video to progressive video by interpolating a missing pixel in the interlaced video from other pixels in the video. A plurality of interpolants are provided, each of which interpolates a pixel value from other pixels that are nearby in space and/or time. The data costs of using the various interpolants is calculated. A particular one of the interpolants is chosen based on the data costs associated with the various interpolants. The chosen interpolant is used to interpolate the value of the missing pixel. The interpolated pixel value may be refined based on exemplars. The exemplars may be taken from the video that is being deinterlaced.

1. One or more computer-readable storage devices comprising executable instructions to perform a method of deinterlacing video, the method comprising:
 calculating data costs of using each of a plurality of interpolants to interpolate a pixel of the video; 
 choosing one of said interpolants based on said data costs; 
 applying said one of said interpolants to said pixel to produce an interpolated pixel value; and 
 displaying a result that is based on said interpolated pixel value, a term being calculated based on a pair that comprises said one of said interpolants and a first interpolant used on a first pixel that is in a neighborhood of said pixel, said term being chosen to be a first value where said one of said interpolants and said first interpolant are a spatial-temporal pair, said term being chosen to be a second value that is lower than said first value where said one of said interpolants and said first interpolant are two spatial interpolants or two temporal interpolants. 
 
     
     
       2. The one or more computer-readable storage devices of  claim 1 , wherein said choosing comprises:
 identifying a lowest data cost among said data costs; and 
 choosing said one of said interpolants based on said one of said interpolants being associated with said lowest data cost. 
 
     
     
       3. The one or more computer-readable storage devices of  claim 1 , further comprising:
 calculating said term based on an amount of regularity, in a neighborhood of said pixel, that results from using said interpolant to interpolate said pixel, wherein said choosing is further based on said term. 
 
     
     
       4. The one or more computer-readable storage devices of  claim 1 , wherein said video is interlaced and is at a first resolution, wherein the method further comprises:
 downsampling said video to produce progressive video at a second resolution that is lower than said first resolution, and wherein said calculating of said data costs comprises: 
 using said one of said interpolants to produce an interpolated value of a second pixel within said progressive video; and 
 comparing, for said second pixel, the second pixel's actual value with the second pixel's interpolated value. 
 
     
     
       5. The one or more computer-readable storage devices of  claim 1 , wherein said video comprises interlaced video and is at a first resolution, wherein the method further comprises:
 downsampling said interlaced video to produce progressive video at a second resolution that is lower than said first resolution; and 
 identifying a second pixel within said progressive video that corresponds to said pixel in said interlaced video, wherein said data costs are calculated based on performance of said interpolants in said progressive video at said second pixel. 
 
     
     
       6. The one or more computer-readable storage devices of  claim 1 , wherein the method further comprises:
 calculating a refinement of said interpolated pixel value based on an exemplar, wherein said result is further based on said refinement. 
 
     
     
       7. The one or more computer-readable storage devices of  claim 1 , wherein the method further comprises:
 refining said interpolated pixel value based on an exemplar that is taken from said video. 
 
     
     
       8. The one or more computer-readable storage devices of  claim 1 , wherein each of the interpolants is a Markov Random Field (MRF) label, wherein the video comprises interlaced video with missing pixels, and wherein said choosing comprises:
 finding a labeling of said missing pixels that minimizes data costs. 
 
     
     
       9. A method of interpolating a first pixel in interlaced video that is at a first resolution, the method comprising:
 downsampling said interlaced video to create a first instance of first progressive video that is at a second resolution that is lower than said first resolution; 
 calculating first data costs associated with using each of a plurality of interpolants to interpolate, based on said first instance, a second pixel in said first instance that corresponds in space and time to said first pixel; 
 choosing one of said interpolants based on said first data costs; 
 applying said one of said interpolants to the interlaced video to calculate a first value of the first pixel; 
 displaying second progressive video at the first resolution, said second progressive video comprising said first pixel with an appearance based on said first value, a term being calculated based on a pair that comprises said one of said interpolants and a first interpolant used on a third pixel that is in a neighborhood of said first pixel, said term being chosen to be a second value where said one of said interpolants and said first interpolant are a spatial-temporal pair, said term being chosen to be a third value that is lower than said second value where said one of said interpolants and said first interpolant are two spatial interpolants or two temporal interpolants. 
 
     
     
       10. The method of  claim 9 , wherein said first instance is at a first offset in the interlaced video, wherein a second instance is at a second offset in the interlaced video, and wherein the method further comprises:
 identifying, in said second instance, a fourth pixel that corresponds in space in time to said first pixel; and 
 calculating second data costs associated with using each of said interpolants; wherein said choosing is further based on said second data costs. 
 
     
     
       11. The method of  claim 9 , wherein said calculating of first data costs comprises:
 for a given one of said interpolants, calculating cost values of using said given one of said interpolants at pixels in a neighborhood of said second pixel; and 
 averaging said cost values to produce one of said first data costs that is associated with said one of said interpolants. 
 
     
     
       12. The method of  claim 9 , further comprising:
 calculating a term associated with said one of said interpolants, said term being based on an amount of regularity, in a neighborhood of said first pixel, that results from using said interpolant to interpolate said first pixel, 
 
       wherein said choosing is further based on said term. 
     
     
       13. The method of  claim 9 , wherein said choosing comprises:
 identifying a lowest data cost among said first data costs; and 
 choosing said one of said interpolants based on said one of said interpolants being associated with said lowest data cost. 
 
     
     
       14. The method of  claim 9 , further comprises:
 calculating a refinement of said value of said first pixel based on an exemplar from the interlaced video, wherein said appearance is further based on said refinement. 
 
     
     
       15. A system comprising:
 a display; 
 an input that receives interlaced video comprising a field having scan lines that alternate as present and not-present; 
 an interpolator that interpolates, based on said interlaced video, a pixel of said field that is in a not-present scan line; 
 a refiner that adjusts said pixel from a first value to a second value based on an exemplar from said interlaced video; 
 a mechanism that causes a progressive frame to be shown on said display, said progressive frame comprising said pixel at said second value; and 
 a data cost calculator that calculates a data cost of using each of a plurality of interpolants to interpolate said pixel and chooses one of said interpolants based on which of said interpolants has a lowest data cost; 
 
       said interpolator interpolating said pixel using said one of said interpolants chosen by said data cost calculator, a term being calculated based on a pair that comprises said one of said interpolants and a first interpolant used on a first pixel that is in a neighborhood of said pixel, said term being chosen to be a first value where said one of said interpolants and said first interpolant are a spatial-temporal pair, said term being chosen to be a second value that is lower than said first value where said one of said interpolants and said first interpolant are two spatial interpolants or two temporal interpolants. 
     
     
       16. The system of  claim 15 ,
 said data cost calculator choosing said one of said interpolants from among said plurality of interpolants based on: (a) data costs associated with each of said interpolants, and (b) regularity in a neighborhood of said pixel that results from choosing each of said interpolants; 
 
       wherein said interpolator interpolates said pixel using said one of said interpolants chosen by said data cost calculator. 
     
     
       17. The system of  claim 15 , wherein said interlaced video is at a first resolution, and wherein the system further comprises:
 a downsampler that downsamples said interlaced video to create progressive video at a second resolution that is lower than said first resolution 
 said data cost calculator finding a second pixel within said progressive video that corresponds to said pixel in said interlaced video, uses said interpolants to interpolate said second pixel from said progressive video, and compares an interpolated value of said second pixel with an actual value of said second pixel to calculate data costs associated with each of said interpolants, said data cost calculator choosing one of said interpolants based on said data costs, 
 
       wherein said interpolator interpolates said second pixel using said one of said interpolants chosen by said data cost calculator. 
     
     
       18. The system of  claim 15 , wherein said interlaced video is at a first resolution, and wherein the system further comprises:
 a downsampler that downsamples said interlaced video at a plurality of offsets to create first progressive video and second progressive video, said first progressive video and said second progressive video each being at a second resolution that is lower than said first resolution.