Method and apparatus for changing or mapping video or digital images from one image density to another

• US 6,018,597 A
• Filed: 03/21/1997
• Issued: 01/25/2000
• Est. Priority Date: 03/21/1997
• Status: Expired due to Term

• Current Assignee: Intermec IP Group
• Original Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Inventors: Maltsev, Pavel A., Coffman, Ken
• Primary Examiner(s): ROGERS, SCOTT A
• Application Number:
  US08/821,901
• Time in Patent Office: 1,040 Days
• Field of Search: 382/260, 382/279, 382/298, 382/299, 382/300, 382/305, 358/451, 395/102, 345/439, 345/127, 345/132, 708/300, 708/420, 708/290
• US Class Current: 382/260
• 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

Abstract

A method and apparatus for resizing digital or stored images initially retrieves a one-dimensional sample of the image, such as a line of pixels. A final image size D is determined so that the absolute value of the original sample size M-2^N *D is a minimum, and where N is an integer greater than or equal to 0. The discrete series of pixels in the line are then converted to a continuous function under a cubic convolution interpolation technique. From the continuous function, intermediate pixel values are determined. Pyramid filtering is employed to filter the intermediate pixel values to a final series of pixel values D. The routine is performed along the opposite dimension so as to alter the size of a two-dimensional stored image.

Claims

1. An apparatus for resizing a stored image, the stored image being comprised of a plurality of pixels, the apparatus comprising:

a convolution interpolator coupled to receive the stored image and produce a set of intermediate pixel values based on M number of pixels in the stored image; and

a pyramid filter, coupled to the cubic convolution interpolator, for altering the intermediate pixel values to D number of pixels, wherein D is an integer not equal to M,

wherein the convolution interpolator includes;

a plurality of delay elements for sequentially storing four pixels in the M number of pixels in the stored image;

a plurality of multiplier circuits, each multiplier circuit being coupled to one delay element;

a plurality of memory locations for storing a plurality of coefficients;

a multiplexing circuit coupled between the plurality of multiplier circuits and to the plurality of memory locations, wherein the multiplexing circuit sequentially couples each of the plurality of memory locations to one of the plurality of multiplier circuits, and wherein each of the plurality of multiplier circuits outputs a product signal; and

an adder circuit coupled to the plurality of multiplier circuits and adding the product signals therefrom.

2. An apparatus for resizing a stored image, the stored image being comprised of a plurality of pixels, the apparatus comprising:

a convolution interpolator coupled to receive the stored image and produce a set of intermediate pixel values based on M number of pixels in the stored image; and

a pyramid filter, coupled to the cubic convolution interpolator, for altering the intermediate pixel values to D number of pixels, wherein D is an integer not equal to M,

wherein the pyramid filter includes;

a plurality of delay elements for storing a set of pixels selected from the intermediate pixel values, each set being separated by 2^N pixels of the intermediate pixel values, wherein N is an integer;

a plurality of multiplier circuits, each multiplier circuit being coupled to one delay element;

a plurality of memory locations for storing a plurality of coefficients, wherein each memory location is coupled to one of the multiplier circuits and wherein each of the multiplier circuits outputs a product signal; and

an adder circuit coupled to the multiplier circuits and adding the product signals output therefrom.

3. An apparatus for resizing a stored image, the stored image being comprised of a plurality of pixels, the apparatus comprising:

a convolution interpolator coupled to receive the stored image and produce a set of intermediate pixel values based on M number of pixels in the stored image; and

a pyramid filter, coupled to the cubic convolution interpolator, for altering the intermediate pixel values to D number of pixels, wherein D is an integer not equal to M,

wherein the convolution interpolator circuitry is configured to interpolate the intermediate pixel values based on an equation ##EQU3## wherein w_p is a pixel in the stored image and k(j-p) is defmed by;

k(z)=1-(u+3)|z*z|+(u+2)|z*z*z|, if 0<

|z|<

1;

k(z)=-4+8u|z|-5u|z*z|+u|z*z*z.vertline., if 1<

|z|<

2;

k(z)=0, otherwise, and wherein u is a real number.

4. An apparatus for resizing a stored image, the stored image being comprised of a plurality of pixels, the apparatus comprising:

a convolution interpolator coupled to receive the stored image and produce a set of intermediate pixel values based on M number of pixels in the stored image; and

a pyramid filter, coupled to the cubic convolution interpolator, for altering the intermediate pixel values to D number of pixels, wherein D is an integer not equal to M,

wherein the pyramid filter is configured to filter the intermediate pixel values based on an equation bj=c1*a(2^N j)+c2*a(2^N j+1)+. . . cv*a(2^N j+(v-1)) wherein a(2^N j) . . . a(2^N j+(v-1)) are intermediate pixel values, wherein j=0, . . . , 2^N *D, wherein N and v are integers, and wherein c1 through cv are preselected coefficients that satisfy predetermined rules.

5. An apparatus for resizing a stored image, the stored image being comprised of a plurality of pixels, the apparatus comprising:

a convolution interpolator coupled to receive the stored image and produce a set of intermediate pixel values based on M number of pixels in the stored image; and

a pyramid filter, coupled to the cubic convolution interpolator, for altering the intermediate pixel values to D number of pixels, wherein D is an integer not equal to M,

wherein the cubic convolution interpolator is configured to produce 2^N *D intermediate pixel values based on the M number of pixels in the stored image, wherein N and D are whole numbers selected so that an absolute value of M-2^N *D is a minimum, and wherein the pyramid filter is configured to reduce the 2^N *D intermediate pixel values to D number of pixels and analyze a window of L number of pixels in the 2^N *D intermediate pixel values, and wherein the window jumps 2^N pixels along the 2^N *D intermediate pixel values.

6. A method of reducing the size of a stored image comprising the steps of:

storing an image, the image being comprised of a plurality of pixels, including M number of pixels;

determining a final image size D wherein an absolute value of M-2^N *D is a minimum and N and D are whole numbers;

cubic convolution interpolating the M number of pixels in the stored image;

producing 2^N *D intermediate pixel values based on the M number of pixels in the stored image; and

reducing the 2^N *D intermediate pixel values to D number of pixels based on pyramid filtering, wherein the pyramid filtering analyzes a window of L number of pixels in the 2^N *D intermediate pixel values and jumps the window 2^N pixels along the 2^N *D intermediate pixel values.

7. The method of claim 6 wherein the step of producing includes the steps of:

storing four sequential pixels in the M number of pixels in the stored image;

storing a plurality of coefficients;

sequentially multiplying each of the plurality of memory locations to one of the four stored pixels to produce four products; and

adding the four products.

8. The method of claim 6 wherein the step of reducing includes the steps of:

storing five pixels of the ₂^N *D intermediate pixel values for every 2^N pixels of the intermediate pixel values;

storing five coefficients;

multiplying each coefficient with one of the stored pixel values to produce products; and

adding the five products.

9. The method of claim 6 wherein the step of cubic convolution interpolating includes the step of interpolating the intermediate pixel values based on an equation ##EQU4## wherein w_p is a pixel in the stored image and k(j-p) is defined by:

k(z)=1-(u+3)|z*z|+(u+2)|z*z*z|, if 0<

|z|<

1;

k(z)=-4+8u|z|-5u|z*z|+u|z*z*z.vertline., if 1<

|z|<

2;

k(z)=0, otherwise, and wherein u is a real number between 0.1 and 3.

10. The method of claim 6 wherein the step of reducing includes the step of filtering the intermediate pixel values based on an equation bj=c1*a(2j) +c2*a(2j+1)+c3*a(2j+2)+c4*a (2j+3)+c5*a(2j+4), wherein a(2j) through a(2+4) are intermediate pixel values, wherein j=1, . . . , 2^N *D, wherein c1 through c5 are predetermined coefficients, and wherein c1+c2+c3+c4+c5=1, c1=c5, c2=c4, and c3+c1+c5=c2+c4.

11. The method of claim 6 wherein L=5 and wherein the step of reducing includes the step of filtering the intermediate pixel values based on an equation bj=c1*a(2j)+c2*a(2j+1)+c3*a (2j+2)+c4*a(2j+3)+c5*a(2j+4), wherein a(2j), through a(2j+4) are intermediate pixel values, wherein j=1, . . . , 2^N *D, and wherein c1=c5=-0.125, c2=c4=0.25 and c3=0.75.

12. The method of claim 6 further comprising the step of repeating the steps of producing, and reducing for series of pixels in two dimensions of the stored image.

13. The method of claim 6 wherein the steps are performed in the order of:

storing, determining, cubic convolution interpolating, producing and reducing.

14. A method resizing a stored image, the stored image being comprised of a plurality of pixels, the method comprising:

convolution interpolating the stored image to produce a set of intermediate pixel values based on M number of pixels in the stored image; and

pyramid filtering the intermediate pixel values to produce D number of pixels, wherein D is an integer not equal to M,

wherein convolution interpolating includes;

storing a plurality of sequential pixels in the M number of pixels in the stored image;

storing a plurality of coefficients;

sequentially multiplying each of the plurality of memory locations to one of the plurality of stored pixels to produce products; and

adding the products.

15. A method resizing a stored image, the stored imaie being comprised of a plurality of pixels, the method comprising:

convolution interpolating the stored image to produce a set of intermediate pixel values based on M number of pixels in the stored image; and

pyramid filtering the intermediate pixel values to produce D number of pixels, wherein D is an integer not equal to M,

wherein pyramid filtering includes;

storing a set of pixels selected from the intermediate pixel values, each set being separated by 2^N pixels of the intermediate pixel values, wherein N is an integer;

storing a plurality of coefficients;

multiplying each coefficient with one of the stored pixel values to produce products; and

adding the products.

16. A method resizing a stored image, the stored image being comprised of a plurality of pixels, the method comprising:

convolution interpolating the stored image to produce a set of intermediate pixel values based on M number of pixels in the stored image; and

pyramid filtering the intermediate pixel values to produce D number of pixels, wherein D is an integer not equal to M,

wherein convolution interpolating includes cubic convolution interpolating the intermediate pixel values based on an equation ##EQU5## wherein w_p is a pixel in the stored image and k(j-p) is defined by;

k(z)=1-(u+3)|z*z|+(u+2)|z*z*z|, if 0<

|z|<

1;

k(z)=-4+8u|z|-5u|z*z|+u|z*z*z.vertline., if 1<

|z|<

2;

k(z)=0, otherwise, and wherein u is a real number.

17. A method resizing a stored image, the stored image being comprised of a plurality of pixels, the method comprising:

convolution interpolating the stored image to produce a set of intermediate pixel values based on M number of pixels in the stored image; and

pyramid filtering the intermediate pixel values to produce D number of pixels, wherein D is an integer not equal to M, p1 wherein reducing includes filtering the intermediate pixel values based on an equation bj=c1*a(2j)+c2*a(2j+1)+c3*a(2j+2)+c4*a(2j+3)+c5*a(2j+4), wherein a(2j) through a(2j+4) are intermediate pixel values, wherein j=1, . . . , 2^N *D , wherein c1 through c5 are predetermined coefficients, and wherein c1+c2+c3+c4+c5=1, c1=c5, c2=c4, and c3+c1+c5=c2+c4.

18. A method resizing a stored image, the stored image being comprised of a plurality of pixels, the method comprising:

convolution interpolating the stored image to produce a set of intermediate pixel values based on M number of pixels in the stored image; and

pyramid filtering the intermediate pixel values to produce D number of pixels, wherein D is an integer not equal to M,

wherein pyramid filtering includes altering the intermediate pixel values based on an equation bj=c1*a(2^N j)+c2*a(2^N j+1)+. . . cv*a (2^N j+(v-1)) wherein a(2^N j) . . . a(2^N j+(v-1)) are intermediate pixel values, wherein j=0, . . . , 2^N *D, wherein N and v are integers, and wherein c1 through cv are preselected coefficients that satisfy predetermined rules.

19. A method resizing a stored image, the stored image being comprised of a plurality of pixels, the method comprising:

convolution interpolating the stored image to produce a set of intermediate pixel values based on M number of pixels in the stored image; and

pyramid filteringz the intermediate pixel values to produce D number of pixels, wherein D is an integer not equal to M,

wherein convolution interpolating includes producing 2^N *D intermediate pixel values based on M number of pixels, in the stored image, wherein N and D are whole numbers selected so that an absolute value of M-2^N *D is a minimum, and

wherein pyramid filtering includes analyzing a window of L number of pixels in the 2^N *D intermediate pixel values, wherein the window jumps 2^N pixels along the 2^N *D intermediate pixel values, and reducing the 2^N *D intermediate pixel values to D number of pixels.