Method for expanding contracted video images

• US 5,799,113 A
• Filed: 01/19/1996
• Issued: 08/25/1998
• Est. Priority Date: 01/19/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lee, Ming-Chieh
• Primary Examiner(s): VU, KIM Y
• Application Number:
  US08/588,951
• Time in Patent Office: 949 Days
• Field of Search: 382/233, 382/244, 382/298, 382/254-256, 382/261-265, 358/261.3, 358/432, 358/451, 358/528
• US Class Current: 382/256
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform

Abstract

Contraction and expansion of video images are important capabilities for multi-media, television picture-in-picture functionality, digital video archiving, browsing, and video transmission. A video image expansion process is used to expand contracted images. The video image expansion process uses a non-linear median filter to interpolate the original pixel values of the contracted image. The non-linear median filter provides good approximations of the original pixel values including pixel values in high contrast regions, such as boundary regions. The video image expansion process is fast, and provides excellent results for low bitrate video coding used for contracting and expanding video images. The video compression image expansion scheme is used with video compression encoding schemes such as MPEG to produce high quality expanded video images from contracted video images.

Claims

1. A method of expanding a contracted image from a contracted set of original pixels to an expanded set of pixels representing an approximation of an original image, comprising;

identifying locations for a plurality of reconstituted pixel locations within the contracted set of original pixels;

for each of a plurality of said identified locations, applying non-linear median filtering to a subset of the contracted set of original pixels therearound to determine a reconstituted pixel value for said identified location, said subset including each original pixel within a predetermined distance of said identified location; and

assigning the first reconstituted pixel values to said identified locations;

wherein each original pixel in the expanded set of pixels that is within said predetermined distance of an identified location is used in determining a reconstituted pixel value for said location, and wherein the expanded set of pixels includes reconstituted pixels produced by the foregoing method, and original pixels not processed by the foregoing method.

2. The method of claim 1 further comprising:

applying linear filtering to the contracted set of original pixels to determine second reconstituted pixel values for selected second reconstituted pixel locations; and

assigning the second reconstituted pixel values to the selected second reconstituted pixel locations.

3. The method of claim 1 wherein the non-linear median filter is applied to a selected group of pixels in the contracted set of original pixels to determine each of the first reconstituted pixel values, each selected group of pixels being within a predefined vicinity of one of the selected first reconstituted pixel locations.

4. The method of claim 3 wherein the predefined vicinity for each of the selected first reconstituted pixel locations extends to the nearest pixels in the contracted set of original pixels.

5. The method of claim 3 wherein the predefined vicinity for each of the selected first reconstituted pixel locations extends to the adjacent pixels in the contracted set of original pixels.

6. A computer readable medium having stored therein instructions for causing a computer to execute the method of claim 1.

7. The method of claim 1 in which said subset includes an even number of original pixels.

8. The method of claim 1 in which said contracted set of original pixels comprises the original image having complete rows and columns of pixels omitted therefrom.

9. The method of claim 1 wherein a plurality of said subsets consists of an even number of original pixels.

10. In a method of expanding a contracted image from a contracted set of original pixels with pixel values to an expanded set of pixels representing an approximation of an original image, the contracted set of original pixels comprising the original image having complete rows and columns of pixels removed therefrom, the method including inserting reconstituted pixel locations into the contracted set of original pixels, the improvement comprising:

identifying plural selected groups of pixels, each of which groups includes a first reconstituted pixel location and all of the original pixels within a predetermined distance thereof; and

assigning to the first reconstituted pixel location within each selected group of pixels a first reconstituted pixel value that is uniform with the pixel values of a majority subset of the plural pixels of the contracted set of original pixels within the group;

wherein the expanded set of pixels includes reconstituted pixels produced by the foregoing method, and original pixels not processed by the foregoing method.

11. A computer readable medium having stored therein instructions for causing a computer to execute the method of claim 10.

12. The method of claim 10 in which said contracted set of original pixels comprises the original image having complete rows and columns of pixels omitted therefrom.

13. A method of expanding a contracted video image from a contracted set of original pixels to an expanded set of pixels representing an approximation of an original video image using filtering, the method comprising:

(a) determining the size of the final expanded image;

(b) extracting a group of pixel values from the set of original pixels;

(c) determining the location of a pixel to be reconstituted from said group of pixels;

(d) determining whether said reconstituted pixel location is positioned between an opposed pair of pixels from said group of pixels, and if so,

assigning a value for said reconstituted pixel location using a first filter on the opposed pair of pixels from said group of pixels, and if not,

assigning a value for said reconstituted pixel location using a second filter, different from the first filter, on said group of pixels; and

(e) repeating steps (b)-(d) until enough pixel values have been assigned to reconstituted pixel locations to expand said contracted image to said determined final expanded image size.

14. The method of claim 13 where the extracting step includes extracting a group of four pixels from the set of original pixels.

15. The method of claim 13 where assigning a value for said reconstituted pixel location using a first filter includes using a bi-linear filter.

16. The method of claim 13 where assigning a value for said reconstituted pixel location using a second filter includes using a non-linear median filter.

17. The method of claim 13 where the reconstituted pixel location is positioned between an opposed pair of pixels in the same row.

18. The method of claim 13 where the reconstituted pixel location is positioned between an opposed pair of pixels in the same column.

19. A computer readable medium having stored therein instructions for causing a computer to execute the method of claim 13.

20. The method of claim 13 where the reconstituted pixel location is positioned at the intersection of a row and a column of pixels.

21. A method of providing reconstituted pixel values within a group of original pixel values, the method comprising:

(a) determining a set of pixel values within a group of original pixel values to be reconstituted;

(b) determining a location of a pixel value to be reconstituted from said set of pixels values;

(c) for the pixel location determined in step (b), applying non-linear median filtering to a subset of the original pixels around the pixel location to determine a reconstituted pixel value for the pixel location, the subset including each original pixel within a predetermined distance of the pixel location; and

(d) repeating steps (a)-(c) until all reconstituted pixel locations in said set of pixels have been assigned a value.

22. A computer readable medium having stored therein instructions for causing a computer to execute the method of claim 21.

23. A method of providing reconstituted pixel values within a group of original pixel values, the method comprising:

(a) determining a set of pixel values within a group of original pixel values to be reconstituted;

(b) determining a location of a pixel value to be reconstituted from said set of pixels values;

(c) determining whether said reconstituted pixel location is positioned between an opposed pair of pixels from said original group of pixels, and if so,

assigning a value for said reconstituted pixel location using a first filter on the opposed pair of pixels from said original group of pixels, and if not,

assigning a value for said reconstituted pixel location using a second filter, different from the first filter, on said group of pixels, the second filter being a non-linear median filter; and

(d) repeating steps (a)-(c) until all reconstituted pixel locations in said set of pixels have been assigned a value.

24. The method of claim 23 where the first filter is a bi-linear filter.

25. A computer readable medium having instructions for performing the steps of claim 23.