Method and system for predictive scaling of colour mapped images

• US 8,107,724 B2
• Filed: 08/02/2008
• Issued: 01/31/2012
• Est. Priority Date: 08/02/2008
• Status: Expired due to Fees

• Current Assignee: Vantrix Corporation
• Original Assignee: Vantrix Corporation
• Inventors: Descarries, Simon
• Primary Examiner(s): Le, Vu
• Assistant Examiner(s): CESE, KENNY A
• Application Number:
  US12/185,081
• Publication Number:
  US 20100027877A1
• Time in Patent Office: 1,277 Days
• Field of Search: None
• US Class Current: 382/162
• 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 scaling an original color mapped image are disclosed. The method performs steps of: transforming the original color map into the scaled color map based on the original color map and the original image independently of the scaled image; scaling the original image into the scaled image; for each pixel of the scaled image: determining a set of contributing pixels in the original image, which define a color of the pixel; determining the color of the pixel based on colors of the contributing pixels and geometric proximity of the pixel to the contributing pixels; establishing correspondence between the color of the pixel and a color in the scaled color map; and determining a corresponding color map index thereof; and setting the determined color map index in the scaled pixel map. A corresponding system for scaling digital images is also provided.

Claims

1. A method of scaling an original image, having an original colour map and original pixel map, into a scaled image having a scaled colour map and a scaled pixel map, implemented by a computing device having a processor, the method comprising:

(a) transforming the original colour map into the scaled colour map based on the original colour map and the original image independently of the scaled image, comprising;

provided N_min <

N<

N_max, wherein N is a number of colours in the original colour map, and N_min and N_max are respective predetermined minimum and maximum numbers of colours;

(a-i) selecting a sub-set M_s of colours available in the original colour map, for colour enhancement, 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;

(b) scaling the original image into the scaled image; and

(c) for each pixel of the scaled image;

(c-i) determining a set of contributing pixels in the original image, which define a colour of the pixel;

(c-ii) determining the colour of the pixel based on colours of the contributing pixels and geometric proximity of the pixel to the contributing pixels;

(c-iii) establishing a correspondence between the colour of the pixel and a colour in the scaled colour map, and determining a corresponding colour map index thereof; and

(c-iv) setting the determined colour map index in the scaled pixel map.

2. The method as described in claim 1, wherein the step (a) further comprises re-using the original colour map as the scaled colour map provided N>

N_max.

3. The method as described in claim 1, wherein the step (a) further comprises:

(a-ii) increasing the number N of colours available in the original colour map to produce the scaled colour map provided N <

N_min, wherein N _min is a predetermined minimum number of colours.

4. The method as described in claim 3, wherein the step (a-ii) comprises:

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

for each combination, interpolating between said two colours.

5. The method as described in claim 1, wherein the step (a) further comprises:

(a-iii) increasing the number of colours for the selected sub-set of colours; and

(a-iv) removing duplicate colours obtained in the step (a-iii).

6. The method as described in claim 5, wherein the step (a-iii) comprises:

generating combinations of any two colours from the sub-set of colours; and

for each combination, interpolating between said two colours.

7. The method as described in claim 1, wherein the step (a-i) 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; and

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

8. 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

performing the steps of the method of claim 1, wherein the original image is the delta region.

9. The method as described in claim 1, wherein the step (c-ii) comprises one of the following:

assigning the colour of the pixel equal to the colours of the contributing pixels provided the colours of the contributing pixels are the same;

or

assigning the colour of the pixel by interpolating colours between the contributing pixels.

10. The method as described in claim 9, wherein the interpolating colours between the contributing pixels comprises bi-linear interpolating.

11. The method as described in claim 10, wherein:

the step (c-i) comprises determining first (Q₁₁), second (Q₁₂), third (Q₂₁) and fourth (Q₂₂) contributing pixels located in vertices of a rectangle surrounding the pixel (P₁) and having respective colours f(Q₁₁), f(Q₁₂), f(Q₂₁) and f(Q₂₂); and

the step (c-ii) comprises determining the colour f(P₁) of the pixel (P₁) as follows;

f(P₁)=f(Q₁₁)(x₂−

x)/(x₂−

x₁)+f(Q₂₁)(x−

x₁)/(x₂−

x₁)

provided f(Q₁₁) =f(Q₁₂) and f(Q₂₁) =f(Q₂₂) and wherein x is a horizontal coordinate of the pixel P_l, x_l is a horizontal coordinate of the pixels Q₁₁ and Q₁₂, and x₂ is a horizontal coordinate of the pixels Q₂₁ and Q₂₂.

12. The method as described in claim 10, wherein:

the step (c-i) comprises determining first (Q₁₁), second (Q₁₂) , third (Q₂₁) and fourth (Q₂₂) contributing pixels located in vertices of a rectangle surrounding the pixel (Q) and having respective colours f(Q₁₁), f(Q₁₂), f(Q₂₁) and f(Q₂₂); and

the step (c-ii) comprises determining the colour f(Q) of the pixel (P₁) as follows;

f(P₁)=f(Q₁₁)(y₂−

y)/(y₂−

y₁)+f(Q₁₂)(y−

y₁)/(y₂−

y₁)

provided f(Q₁₁) =f(Q₂₁) and f(Q₁₂) = f(Q₂₂) and wherein y is a horizontal coordinate of the pixel P₁, y₁ is a horizontal coordinate of the pixels Q₁₁ and Q₂₁, and y₂ is a horizontal coordinate of the pixels Q₁₂ and Q₂₂.

13. The method as described in claim 1, wherein the step (c-iii) comprises finding the closest match in the scaled colour map.

14. 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.

15. A system for scaling an original image, having an original colour map and original pixel map, into a scaled image having a scaled colour map and a scaled pixel map, the system comprising:

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

a colour map transformation module for transforming the original colour map into the scaled colour map based on the original colour map and the original image independently of the scaled image, comprising;

a colour culling module for selecting a sub-set M_s of colors available in the original color map, for colour enhancement, as follows;

provided N_min <

N<

N_max, wherein N is a number of colours in the original colour map, and N_min and N_max are respective predetermined minimum and maximum numbers of colours;

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;

a pixel selection module for scaling the original image into the scaled image;

a colour interpolation module for determining, for each pixel of the scaled image;

a set of contributing pixels in the original image, which define a colour of the pixel; and

the colour of the pixel based on colours of the contributing pixels and geometric proximity of the pixel to the contributing pixels; and

a colour map index generation module for;

establishing a correspondence between the colour of the pixel and a colour in the scaled colour map, determining a corresponding colour map index thereof, and setting the determined colour map index in the scaled pixel map.

16. The system as described in claim 15, wherein the colour map transformation module further comprises a colour map enhancement module for increasing the number of colours available in the original colour map to produce the scaled colour map provided N<

N_min, and for increasing the number of colours in the selected sub-set of colours provided N_min <

N<

N_max, and for removing duplicate colours.

17. The system as described in claim 16, wherein the colour map enhancement module is configured to generate combinations of any two colours from the original colour map;

and for each combination, interpolate between said two colours.

18. The system as described in claim 15, wherein the colour culling module is further configured to:

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

generate an octree graph based on the colour useage vector;

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

19. A non-transitory computer readable storage medium having computer readable instructions stored thereon for execution by a processor causing the processor to:

(a) transform the original colour map into the scaled colour map based on the original colour map and the original image independently of the scaled image, comprising;

provided N_min <

N<

N_max, wherein N is a number of colours in the original colour map and N_min and N_maxare respective predetermined minimum and maximum numbers of colours;

(a-i) selecting a sub-set M_s of colours available in the original colour map, for colour enhancement, 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;

(b) scale the original image into the scaled image; and

(c) for each pixel of the scaled image;

(c-i) determine a set of contributing pixels in the original image, which define a colour of the pixel;

(c-ii) determine the colour of the pixel based on colours of the contributing pixels and geometric proximity of the pixel to the contributing pixels;

(c-iii) establish a correspondence between the colour of the pixel and a colour in the scaled colour map, and determine a corresponding colour map index thereof; and

(c-iv) set the determined colour map index in the scaled pixel map.

20. A method for transforming an original colour map of an original image into a scaled colour map of a scaled image, implemented by a computing device having a processor, the method comprising:

selecting a sub-set M_s of colours available in the original colour map, for colour enhancement, as follows;

provided N_min <

N<

N_max, wherein N is a number of colours in the original colour map, and N_min and N_max are respective predetermined minimum and maximum numbers of colours;

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.

21. The method as described in claim 20, further comprising re-using the original colour map as the scaled colour map provided N>

N_max.

22. The method as described in claim 20, further comprising increasing the number N of colours available in the original colour map to produce the scaled colour map provided N <

N_min.

23. The method as described in claim 20, further comprising:

increasing the number of colours for the selected sub-set of colours; and

removing duplicate colours obtained in said step of increasing provided N_min <

N<

N_max.

24. A system for transforming an original colour map of an original image into a scaled colour map of a scaled image, comprising:

a computer having a processor and a non-transitory computer readable storage medium having computer readable instructions stored thereon, forming;

a colour map transformation module, selecting a sub-set M_sof colours available in the original colour map, for colour enhancement, as follows;

provided N_min <

N<

N_max, wherein N is a number of colours in the original colour map, and N_min and N_max are respective predetermined minimum and maximum numbers of colours;

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.

25. The system as described in claim 24, wherein the colour map transformation module further comprises a colour map enhancement module for increasing the number of colours available in the original colour map to produce the scaled colour map provided N<

N_min, and for increasing the number of colours in the selected sub-set of colours provided N_min<

N<

N_max, and for removing duplicate colours.