METHOD AND SYSTEM FOR PREDICTIVE SCALING OF COLOUR MAPPED IMAGES

• US 20100027877A1
• Filed: 08/02/2008
• Published: 02/04/2010
• Est. Priority Date: 08/02/2008
• Status: Active Grant

• Current Assignee: Vantrix Corporation
• Original Assignee: Vantrix Corporation
• Inventors: DESCARRIES, Simon
• Granted Patent: US 8,107,724 B2
• Time in Patent Office: Days
• 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 colour mapped image are disclosed. The method performs steps of: 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; 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 colour of the pixel; determining the colour of the pixel based on colours of the contributing pixels and geometric proximity of the pixel to the contributing pixels; establishing correspondence between the colour of the pixel and a colour in the scaled colour map; and determining a corresponding colour map index thereof; and setting the determined colour 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, the method comprising steps of:

(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;

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

(c) for each pixel of the scaled image;

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

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

(iii) establishing correspondence between the colour of the pixel and a colour in the scaled colour map; and

determining a corresponding colour map index thereof; and

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

2. The method as described in claim 1, wherein the step (a) comprises computing a number of colours N in the original colour map.

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

N_max, wherein N_max is a predetermined maximum number of colours.

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

(v) increasing the number 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.

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

(vi) selecting a sub-set of colours, available in the original colour map, for colour enhancement;

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

(viii) removing duplicate colours obtained in the step (vii);

provided N_min<

N<

N_max.

6. The method as described in claim 4, wherein the step (v) comprises:

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

for each combination, interpolating between said two colours.

7. The method as described in claim 5, wherein the step (vi) comprises:

selecting a number of colours M_s in the sub-set of colours according to the following;

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

2N_max;

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;

wherein N is a number of colours in the original colour map, and N_max is a predetermined maximum number of colours.

8. The method as described in claim 7, wherein the step (vi) 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 M_s colours to be included in the sub-set.

9. The method as described in claim 5, wherein the step (vii) comprises:

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

for each combination, interpolating between said two colours.

10. A method for scaling an image in a video stream, comprising steps of:

selecting a video frame comprising an image;

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

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

11. The method as described in claim 1, wherein the step (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.

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

13. The method as described in claim 12, wherein the step (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 wherein the step (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₁, x₁ is a horizontal coordinate of the pixels Q₁₁ and Q₁₂, and x₂ is a horizontal coordinate of the pixels Q₂₁ and Q₂₂.

14. The method as described in claim 12, wherein the step (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 wherein the step (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₂₂.

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

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

24. A computer readable medium having computer readable instructions stored thereon for execution by a processor to perform the steps of the method of claim 1.

17. 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 computer readable medium having computer readable instructions stored thereon for execution by the processor for forming the following;

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;

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;

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

(ii) 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;

(iii) establishing correspondence between the colour of the pixel and a colour in the scaled colour map; and

determining a corresponding colour map index thereof; and

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

18. The system of claim 17, wherein the colour map transformation module further comprises a colour map analyzer module for determining a number of colours N in the original colour map, and comparing the number of colours N with a predetermined thresholds N_min and N_max.

19. The system as described in claim 18, wherein the colour map transformation module further comprises a colour culling module for selecting a sub-set of colors available in the original color map, which are most beneficial for colour enhancement, provided N_min<

N<

N_max.

20. The system as described in claim 19, 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_max, 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.

21. The system as described in claim 20, wherein the colour map enhancement module comprises means for generating combinations of any two colours from the original colour map;

and for each combination, interpolating between said two colours.

22. The system as described in claim 19, wherein the colour culling module comprises means for selecting a number of colours M_s in the sub-set of colours according to the following:

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

2N_max;

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;

wherein N is a number of colours in the original colour map, and N_max is a predetermined maximum number of colours.

23. The system as described in claim 22, wherein the colour culling module further comprises means for:

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 M colours to be included in the sub-set.