Method and system for predictive scaling of colour mapped images

• US 8,478,038 B2
• Filed: 01/30/2012
• Issued: 07/02/2013
• Est. Priority Date: 08/02/2008
• Status: Active Grant

• Current Assignee: Masimo Corporation
• Original Assignee: Vantrix Corporation
• Inventors: Descarries, Simon
• Primary Examiner(s): Alavi, Amir
• Assistant Examiner(s): CESE, KENNY A
• Application Number:
  US13/361,902
• Publication Number:
  US 20120128245A1
• Time in Patent Office: 519 Days
• Field of Search: None
• US Class Current: 382/166
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403
• CPC Class Codes: H04N 1/3935 with modification of image resolution, i.e. determining the values of picture elements at new relative positions
• CPC Class Codes: H04N 1/644 using a reduced set of representative colours, e.g. each representing a particular range in a colour space
• CPC Class Codes: H04N 7/0135 involving interpolation processes interpolation-based image scaling G06T3/4007; interpolation for video coding H04N19/587, H04N19/59

Abstract

A method for determining a scaled color map of a scaled image is described using the transformation of the original color map and the original image only, independently of the scaled image. A number of colors N in the original color map is determined; and provided N>N_max, all colors in the original color map are reused in the scaled color map. If N<N_min, the number of colors in the original color map is increased. Otherwise, the scaled color map is formed including: selecting a sub-set of colors in the original color map; increasing a number of colors in the selected sub-set; adding the resulting sub-set with increased number of colors to the original color map; and removing duplicate colors, wherein N_min and N_max are respective predetermined minimum and maximum thresholds for a number of colors in the original color map. A corresponding system is also provided.

Claims

1. A method for determining a scaled colour map of a scaled image obtained by scaling an original image, implemented by a computing device having a processor, the method comprising:

obtaining an original colour map of the original image; and

transforming the original colour map into the scaled colour map using the original colour map and the original image only, comprising;

provided N_min<

N<

N_max, forming the scaled colour map, comprising;

(iv-1) selecting a sub-set of colours in the original colour map;

(iv-2) increasing a number of colours in the selected sub-set, thus forming a resulting sub-set of colours; and

(iv-3) adding the resulting sub-set with increased number of colours to the original colour map, comprising determining the increased number of colours in the resulting sub-set of colours as

2. The method of claim 1, wherein the transforming further comprises:

(ii) provided N>

N_max, reusing all colours in the original colour map in the scaled colour map; and

(iii) provided N<

N_min, increasing the number of colours in the original colour map to produce the scaled colour map.

3. The method of claim 2, comprising selecting one or more of the following:

N_min−

4;

N_max=16;

N=4;

N=9;

N≦

16;

M_s=4;

M_s=5;

wherein M_s is a number of colours in the subset of colours.

4. The method as described in claim 1, wherein the original and scaled images are selected from Graphical Interchange Format (GIF), Portable Network Graphic (PNG), and Bitmap (BMP) images.

5. The method as described in claim 2, wherein the steps (iii) and (iv-2) further comprise:

generating combinations of any two colours from the original colour map; and

for each combination, interpolating between said two colours.

6. The method as described in claim 2, wherein the step (iv-1) further comprises:

determining a colour usage vector indicating frequency of use of colours in the original colour map;

generating an octree graph based on the colour usage vector;

parsing the octree graph to select colours to be included in the sub-set.

8. The method of claim 1, further comprising:

for each pixel in the scaled image, assigning a colour index, comprising finding a colour in the scaled color map, which is the closest match to a colour of said each pixel, and assigning an index of the colour in the scaled colour map having the closest match as the colour index for said each pixel.

9. The method of claim 2, wherein the step (iv-1) further comprises determining a number of colours M_s in the selected sub-set of colours as follows:

M_s=N, provided N(N+1)≦

2N_max; and

M_s=M, where M is the smallest number M<

N for which

M(M−

1)≧

2(N_max−

N), provided N(N+1)>

2N_max.

10. A method for scaling an image in a video stream, implemented by a computing device having a processor, the method comprising:

selecting a video frame comprising an image;

determining a delta region of the image, which has been changed compared to a previous video frame; and

determining the scaled colour map of the scaled image as described in the method of claim 1, wherein the original image is the delta region.

11. A method for scaling the original image, implemented by a computing device having a processor, the method comprising:

scaling the original image into the scaled image; and

determining the scaled colour map of the scaled image as described in the method of claim 1.

7. A method for determining a scaled colour map of a scaled image obtained by scaling an original image, implemented by a computing device having a processor, the method comprising:

obtaining an original colour map of the original image; and

transforming the original colour map into the scaled colour map using the original colour map and the original image only, comprising;

provided N_min<

N<

N_max, forming the scaled colour map, comprising;

(iv-1) selecting a sub-set of colours in the original colour map, comprising determining a number of colours M_s in the selected subset of colours as follows

12. A system for determining a scaled colour map of a scaled image obtained by scaling an original image, the system comprising:

a processor and a non-transitory computer readable storage medium having computer readable instructions stored thereon for execution by the processor, causing the processor to;

obtain an original colour map of the original image; and

transform the original colour map into the scaled colour map using the original colour map and the original image only, comprising;

provided N_min<

N<

N_max, forming the scaled colour map;

(iv-1) select a sub-set of colours in the original colour map;

(iv-2) increase a number of colours in the selected sub-set, thus forming a resulting sub-set of colours; and

(iv-3) add the resulting sub-set with increased number of colours to the original colour map, comprising determining the increased number of colours in the resulting sub-set of colours as

13. The system of claim 12, wherein the computer readable instructions further cause the processor to:

(ii) provided N>

N_max, reuse all colours in the original colour map in the scaled colour map; and

(iii) provided N<

N_min, increase the number of colours in the original colour map to produce the scaled colour map.

14. The system of claim 13, wherein the computer readable instructions further cause the processor to select one or more of the following:

N_min=4;

N_max=16;

N=4;

N=9;

N≦

16;

M_s=4;

M_s=5;

wherein M_s is a number of colours in the subset of colours.

15. The system of claim 12, wherein the original and scaled images are selected from Graphical Interchange Format (GIF), Portable Network Graphic (PNG), and Bitmap (BMP) images.

16. The system of claim 13, wherein the computer readable instructions further cause the processor to increase the number of colours in the original colour map or in the selected sub-set of colours as follows:

to generate combinations of any two colours from the original colour map; and

for each combination, to interpolate between said two colours.

17. The method as described in claim 13, wherein the computer readable instructions further cause the processor to select the sub-set of colours in the original colour map as follows:

to determine a colour usage vector indicating frequency of use of colours in the original colour map;

to generate an octree graph based on the colour usage vector;

to parse the octree graph to select colours to be included in the sub-set.

19. The system of claim 13, wherein the computer readable instructions further cause the processor to determine a number of colours M_s in the selected sub-set of colours as follows:

M_s=N, provided N(N+1)≦

2N_max; and

M_s=M, where M is the smallest number M<

N for which

M(M−

1)≧

2(N_max−

N), provided N(N+1)>

2N_max.

18. A system for determining a scaled colour map of a scaled image obtained by scaling an original image, the system comprising:

a processor and a non-transitory computer readable storage medium having computer readable instructions stored thereon for execution by the processor, causing the processor to;

obtain an original colour map of the original image; and

transform the original colour map into the scaled colour map using the original colour map and the original image only, comprising;

provided N_min<

N<

N_max, form the scaled colour map, comprising causing the computer readable instructions to select a sub-set of colours in the original colour map and to determine a number of colours M_s in the selected subset of colours as