AU736359B2 - Image interpolation with a continuous 2-dimensional kernel - Google Patents

Description

S&F Ref: 481547

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

u cs r Name and Address of Applicant Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome Ohta-ku Tokyo Japan Actual Inventor(s): Address for Service: Dominic Yip Spruson Ferguson St Martins Tower 31 Market Street Sydney NSW 2000 Image Interpolation with at Continuous 2dimensional Kernel Invention Title: ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Couit-ry 7 [31] Applic. No(s) AU PP7803 [32] Application Date 18 December 1998 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c IMAGE INTERPOLATION WITH A CONTINUOUS 2-DIMENSIONAL KERNEL Field of Invention The present invention relates to a method and apparatus for a resolution conversion implementation that uses samples from a continuous kernel as coefficients in a convolution operation. The invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for a resolution conversion implementation that uses samples from a continuous kernel as coefficients in a convolution operation. The present invention finds application in image processing although its use should not be limited to that field.

o~ooo 0Background of the Invention ~The convolution of two signals is a new signal which has a value at each point which is the integral of the product of an original signal and a filter function shifted so 15 that its origin is at that point. This corresponds to taking a weighted average of the neighbourhood around each point of a signal weighted by a filter centred at that point- and using it for the value at that point. The size of the neighbourhood is determined by the size of the domain over which the filter is non-zero. This is known as the filter's support, S•01 and a filter that is non-zero over a finite domain is said to have a finite support.

•o.

Convolving two Fourier transforms in the frequency domain corresponds exactly to multiplying their inverse Fourier transforms in the spatial domain. The filter function isoftencalled the convolution kernel", the "filter kernel" or often just the "kernel".

Interpolation is defined as the estimation of a function at a particular point from values of the function on either side of the point. Interpolation of image data is used for example in the blending together of two images as for a fade-in, fade-out sequence, for anti-aliasing, for shading and for scaling images from one resolution to another. Kernels may be used as an integral part of the interpolation process.

Two-dimensional interpolation is performed by first interpolating the rows of an image and then interpolating the columns of the image. Pixel data is obtained from an RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF incoming pixel stream, multiplied with convolution kernel coefficients, and summed to produce an intermediate interpolation product. This interpolation product is then stored in one-line stores. The intermediate interpolation results are read out from the line stores to perform column interpolation.

There are problems however, with the method described above. First, the line stores that store the intermediate interpolation results between row interpolation and column interpolation can only be used by the interpolation hardware. As the amount of line stores required increases in proportion to resolution of images, it would be advantageous if these line stores could be shared with other applications, edge map 10 detection for example.

Second, the accuracy of the intermediate interpolation results depends on the .ooooi width of data in the line stores. An increase in accuracy would increase the amount of line stores required significantly.

•It is an object of the present invention to ameliorate one or more disadvantages of the prior art.

Acorin .Summary of the Invention •According to one aspect of the invention there is provided a method of performing image interpolation on a first image to display a second image, the method comprising the steps of: computing pairs of positional indicators for each pixel in said first image, wherein said first image includes pixels arranged in rows and columns; calculating filter values according to said positional indicators, wherein said filter values are calculated utilising one of a plurality of filter functions; storing said pixel values of said first image in a plurality of line stores; interpolating said pixel values within said columns of said first image by using said filter values for each said pixel within each said column of said first image to form a column interpolated image; and RC04 CFP1535AU 481547 [O:\CISRA\R\RC04481547.doc:SaF -3interpolating pixel values within said rows of said column interpolated image using said stored filter values for each said pixel within each said row of said column interpolated image to form said second image.

According to another aspect of the present invention there is provided an apparatus for performing image interpolation on a first image to display a second image, said apparatus comprising: computer means for computing pairs of positional indicators for each pixel in said first image, wherein said first image includes pixels arranged in rows and columns; calculator means for calculating filter values according to said positional indicators, wherein said filter values are calculated utilising one of a plurality of filter ""functions; eeee• storage means for storing said pixel values of said first image in a plurality of line stores; column interpolator means for interpolating pixel values within said columns of said first image by using said filter values for each said pixel within each said column of i said first image to form a column interpolated image; and row interpolator means for interpolating pixel values within said rows of said column interpolated image by using said stored filter values for each said pixel within S. !each said row of said column interpolated image to form said second image.

According to still another aspect of the present invention there is provided a method of performing image interpolation on a first image to display a second image, the method comprising the steps of: inputting dimension values of said first image and said second image; calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values; computing pairs of positional indicators according to said first and second sampling limit values; RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF calculating first and second fractional coordinate values using said positional indicators; calculating filter values using said first and second fractional coordinate values, wherein said filter values are calculated using one of a plurality of filter functions; storing said pixel values of said first image in a plurality of line stores; interpolating pixel values within said columns of said first image by using said filter values for each said pixel within each said column of said first image to form a column interpolated image; and interpolating said pixel values within said rows of said column interpolated 10 image by using said filter values for each said pixel within each said row of said column ••interpolated image to form said second image.

According to still another aspect of the present invention there is provided an apparatus for performing image interpolation on a first image to display a second image, the apparatus comprising: S 15 input means for inputting dimension values of said first image and said second image; •first calculator means for calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values; computing means for computing pairs of positional indicators according to said first and second sampling limit values; second calculator means for calculating first and second fractional coordinate values using said positional indicators; third calculator means for calculating filter values using said first and second fractional coordinate values, wherein said filter values are calculated using one of a plurality of filter functions; storage means for storing said pixel values of said first image in a plurality of line stores; RC04 CFP1535AU 481547 [O:\CISRA\RC\RC041481547.doc:SaF column interpolator means for interpolating pixel values within said columns of said first image by using said filter values for each said pixel within each said column of said first image to form a column interpolated image; and row interpolator means for interpolating said pixel values within said rows of said column interpolated image by using said filter values for each said pixel within each said row of said column interpolated image to form said second image.

According to still another aspect of the present invention there is provided a computer readable memory medium for storing a program for apparatus which processes image data, said processing comprising a process for performing image interpolation on a first image to display a second image, said program comprising: ~code for computing pairs of positional indicators for each pixel in said first .ooo.i image, wherein said first image includes pixels arranged in rows and columns; code for calculating filter values according to said positional indicators, wherein said filter values are calculated utilising one of a plurality of filter functions; code for storing said pixel values of said first image in a plurality of line stores; code for interpolating said pixel values within said columns of said first image by °using said filter values for each said pixel within each said column of said first image to form a column interpolated image; and .i code for interpolating pixel values within said rows of said column interpolated image using said stored filter values for each said pixel within each said row of said column interpolated image to form said second image.

According to still another aspect of the present invention there is provided a computer readable memory medium for storing a program for apparatus which processes image data, said processing comprising a process for performing image interpolation on a first image to display a second image, said program comprising: code for inputting dimension values of said first image and said second image; code for calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values; RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF code for computing pairs of positional indicators according to said first and second sampling limit values; code for calculating first and second fractional coordinate values using said positional indicators; code for calculating filter values using said first and second fractional coordinate values, wherein said filter values are calculated using one of a plurality of filter functions; code for storing said pixel values of said first image in a plurality of line stores; code for interpolating pixel values within said columns of said first image by using said filter values for each said pixel within each said column of said first image to 10 form a column interpolated image; and ~code for interpolating said pixel values within said rows of said column eoooo 1::interpolated image by using said filter values for each said pixel within each said row of said column interpolated image to form said second image.

Brief Description of the Drawings S 15 Embodiments of the invention are described with reference to the drawings, in which: Fig. 1 is a schematic block diagram showing an interpolator in accordance with a preferred embodiment of the invention; .i Fig. 2 is a schematic block diagram of the logic and control unit of Fig. 1; Fig. 3 is a schematic block diagram of the line store module of Fig. 1; Fig. 4 is a schematic block diagram of the column in terpolator of Fig. 1; Fig. 5 is a schematic block diagram showing the row interpolator of Fig. 1; Fig. 6 is a schematic block diagram showing a general purpose computer within which the interpolator of Fig. 1 can be implemented; and Fig. 7 is a flow diagram of a method of interpolation in accordance with the preferred embodiment of the present invention.

Detailed Description The preferred embodiment discloses method and apparatus for performing a twodimensional separable interpolation by first storing the pixels in a plurality of line stores, RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF -7interpolating the columns of the image, and then interpolating the rows of the image. The method described can work with quadratic, cubic, sinc or similar continuous interpolation kernels.

The preferred embodiment overcomes the disadvantages of the prior art by putting the line stores in front of the row and column interpolation hardware, and performs the column interpolation before row interpolation. In this way, the line stores contain raw pixel data, and any other processing elements can use these raw pixel data.

Further, the accuracy of calculation is not limited by the data width of the line stores.

This has the dual benefit of releasing the line stores to be shared with other 10 image processing units and increasing the accuracy of the interpolation. Also, the method disclosed provides an efficient software implementation of interpolation with the above benefits.

Fig. 1 is a schematic block diagram showing an interpolator 100 according to preferred embodiment of the present invention. The interpolator 100 receives digital image pixel data via input 114, for example, from a frame store memory (not shown), one row at a time, and produces interpolated digital image data one row at a time which can ooooo be supplied to a printer or a monitor via line 116. The interpolator 100 includes a logic and control unit 102 which calculates a horizontal sampling increment hH and vertical sampling increment hv for the output image and controls the overall operation of the interpolator 100. The sampling increments h are determined by the input image width and height, and the output image width and height. The interpolator 100 alsoincludes a row interpolator 104, a column interpolator 106, a line store module 108 an interpolation kernel generator 110, and an output buffer 112. In operation, the logic and control unit 102 receives instructions from a central processing unit (see Fig. via lines 118 and 120, regarding the sizes of input and interpolated output images, and pixel-by-pixel interpolation kernel selection scheme. The line store module 108 accepts incoming pixel data row-by-row via line 114 and stores them in its internal line buffers (see Fig. 3) in such a fashion that the last one or more consecutive lines are in one of the internal line buffers. Internal logic in the line store module 108 also retrieves pixel values in the RC04 CFP1535AU 481547 [O:\CISRA\RC\RC041481547.doc:SaF required horizontal coordinate in those buffers containing the last plurality of consecutive lines and provides them to the column interpolator 106. At the same time, the interpolation kernel generator 110 accepts the fractional parts of the current x and y coordinates and kernel selection information from the logic and control unit 102 and generates the required interpolation kernel coefficients.

The column interpolator 106 receives raw pixel data, via lines 122 to 12m (m equals the number of line buffers in the line store module 108), from the line store module 108 and interpolation kernel coefficients, via line 130, from the interpolation kernel generator 110 and performs interpolation in a column direction. The results of column 10 interpolation are stored in the column interpolator 106 until there are enough of them to be interpolated in the horizontal direction. At that time the column interpolator 106 outputs the results to the row interpolator 104 via lines 132 to 13m, and signals the row interpolator 104 to perform interpolation via an internal control bus 140. The direct connection between the column interpolator 106 and row interpolator 104 reduces the amount of memory needed for accurate interpolation. Upon receiving the signal the row S°-interpolator 104 interpolates those intermediate results in a row direction using a plurality of interpolation kernel coefficients received, via line 144, from the interpolation kernel generator 110. It then produces rows of interpolated values to the output buffer 112 via line 142, which is double buffered so that a row of interpolated pixels values can be read out while the next row is being read into the output buffer 112. Double buffering is produced as is known in the art by a pair of buffers 144, 146 and multiplex switches 148.

The logic control unit 102 will now be described with reference to Fig. 2. The logic and control unit 102 includes control logic 202, a row counter 204, a pixel counter 203, a sampling increment calculator 208, an X coordinate calculator 210 and an Y coordinate calculator 212. The output image width and height and the input image width and height are received from a central processing unit (see Fig. via lines 118 and 120.

Initially all modules are stalled by control logic 202 via a stall signal on line 214, the contents of pixel counter 206, row counter 204, X coordinate calculator 210 and Y coordinate calculator 212 are reset to 0, and the horizontal sampling increment hH and the RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF vertical sampling increment h v are calculated by the sampling increment calculator 208 using the following equations: hH input image width/output image width h v input image height/output image height.

When enough valid pixels have come in to perform interpolation indicated by deassertion of the stall signals from line stores 108 and the column interpolator 106, the control logic 202 deasserts the stall signal to all modules via line 214, and the pixel counter 206 begins to increment its content, counting the number of interpolated output pixels generated. At the same time, the pixel counter 206 asks the X coordinate calculator o• 10 210, via a signal on line 216, to add hH to the current x coordinate. The value hH is opassed to the X coordinate calculator 210 from the sampling increment calculator 208 via oo.ooi line 220. When the number of output interpolated pixels reaches the output image width, the pixel counter 206 will ask the row counter 204, via a signal on line 218, to increment its content. At the same time the X coordinate calculator 210 is reset to 0 via line 216, S 15 and the row counter asks the Y coordinate calculator 212 to add the value h v to the content ofY coordinate calculator 212 via a signal line 218. The value h v is passed to the •Y coordinate calculator 212 from the sampling increment calculator 208 via line 222.

This process will continue until the content of row counter 204 reaches output image :height. The current x and y coordinates along with their respective fractional parts and kernel selection information are passed to the interpolation kernel generator 110, via line 150. At that time, the control logic 202 detects whether there are anymore incoming pixels via a signal from the line store module 108 on line 140. If there are, the contents of row counter 204, pixel counter 206 and X and Y coordinate calculators 210,212 are reset to 0, and the whole process is repeated again. If there are no more pixels coming in, the whole logic and control unit 102 becomes idle.

The line stores will now be described in more detail with reference to Fig. 3.

The line stores include a plurality of buffers (301-30m), an input de-multiplexer 310, an output multiplexer 312 and a modulo calculator 314. The modulo calculate 314 calculates the value of current_row modulo k+l, where currentrow is passed from the RC04 CFP1535AU 481547 (O:\CISRA\RC\RC041481547.doc:SaF logic and control unit 102 via line 140, and k is the number of columns required to perform interpolation. The output of the modulo calculator 314 m goes into the input demultiplexer 310 and the output multiplexer 312, via line 318. The input de-multiplexer 310 writes the incoming pixels to the mth buffer. The nth output of the output multiplexer 312 selects the output of the pth buffer, where p is modulo k+l. The buffer controller 316 writes the incoming pixel into the current column, via line 320, and reads the other k buffers at the same location, where the current column is passed from the logic and control unit 102 via line 140. The raw pixel data is passed to the column interpolator 106, via lines 122 to 12m.

The column interpolator 106 will now be described in more detail with reference to Fig. 4. The column interpolator 106 includes k multipliers (401-40k), one k-input oeooe adder 410, an intermediate result FIFO 412, and an intermediate result FIFO controller 414, where k is the number of columns in the interpolation kernel. The multipliers (401- 40k) multiply the incoming pixels P 0 to Pk-1, received from the line store module 108, with the kernel coefficients C O to Ck_1 from the interpolation kernel generator 110. The kernel coefficients C O to Ck_ 1 are passed from the interpolation kernel generator 110 via o:ooo line 130. The adder 410 adds all products together to form the interpolated value in the S*-o column direction. This intermediate interpolated value is then stored in the intermediate results FIFO 412. According to the number of units the x coordinate has advanced, the intermediate results FIFO controller 414 advances the intermediate results FIFO pointer 416 by the same amount. The first I values in the FIFO 412 are supplied to the row interpolator 104 via lines 132 to 138, where 1 is the number of rows of the interpolation kernel.

The row interpolator 104 will now be described in more detail with reference to Fig. 5. The row interpolator 104 includes 1 multipliers (501-501) multiply the intermediate results supplied from the column interpolator 106 with the kernel coefficients from the interpolation kernel generation means 110. The kernel coefficients

C

O to Ck-l are passed from the interpolation kernel generator 110 via line 152. The 1input adder 510 adds the products from all multipliers (501-501) together, and the result is RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF -11the interpolation pixel. The interpolated value will then go to the output buffer 112, via line 142, where one line of pixels will be collected before outputting.

The operation of the interpolation kernel generator or LUT module 110 will now be described in more detail. The module 110 accepts the fractional parts of the current x and y coordinates and the kernel selection information from the logic and control unit 102 via line 150, and evaluates the kernel coefficients according to them. A kernel selector (not shown) selects which kernel is to be used to interpolate the current output pixel, perhaps based on local gradient/edge strength. The method of determining local gradient/edge strength is not further described in this description, as it should be well 10 known for those who are skilled in the art. (For example, one may determine the local go•• edge strength on a particular pixel by applying an edge detection filter on the input image.

.:oooi One such filter is the Prewitt filter). If the module 110 is implemented as a LUT, the kernel selector may select a particular LUT to be used. The fractional parts of the x and y coordinates are then combined to form an address to look up that LUT. If the kernel S 15 coefficients are generated by a plurality of multipliers and adders on the fly, the kernel selector may select some of the inputs to these multipliers/adders. The fractional parts of the x and y coordinates are then fed into these multipliers/ adders.

*Fig. 7 is a flow diagram of a method of interpolation in accordance with a S: °preferred embodiment of the invention. The method commences at step 702 where pairs of positional indicators (x and y coordinates) for each pixel in an incoming image are calculated. The process continues at step 704, where filter values according to the positional indicators are calculated. The filter values are calculated utilising one of a plurality of filter functions. The interpolation kernel generator 110 accepts the fractional parts of the current x and y coordinates and kernel selection information from the logic and control unit 102 and generates the required interpolation kernel coefficient values. At the next step 706, the pixel values of the incoming image are stored in a plurality of line stores. The pixel values are stored in the internal buffers of the line store module 108 in such a fashion that the last one or more consecutive lines are stored in consecutive buffers. The process continues at step 708 where the pixel values within the columns of RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04481547.doc:SaF 12the incoming image are interpolated by using the filter values for each of the pixels within each column of image to form a column interpolated image. The column interpolated image is stored in the column interpolator 106 until there are enough of them to be interpolated in the horizontal direction. At the next step 710, pixel values within the rows of the column interpolated image are interpolated using the stored filter values for each pixel within each row of column interpolated image. The rows of interpolated values are then produced to the output buffer 112.

Once an image has been interpolated using the interpolator 100 of the preferred embodiment it can then be displayed on a video display (see Fig. 6) or similar device.

10 Alternatively, the interpolated image can be stored in a memory device (see Fig. 6) and/or @0 00 further manipulated with an image processor or the like. Further, the interpolated image can be distributed over a computer network such as a local area network (LAN), a wide area network (WAN), an Intranet, and/or the Internet.

:The preferred image interpolator 100 is useful for enlarging and reducing digital log 0 15 images so that such images can be displayed clearly in display devices of various resolutions. The interpolator 100 is advantageous in that the lines stores are positioned in the head of the pipeline to allow it to be shared with other image processing units. The preferred method has the further advantage that due to the direct connection between the go column interpolator and row interpolator, the interpolation can be performed at high accuracy without a large increase in the amount of memory used.

Preferred Embodiment of Apparatus(s) The preferred embodiment is preferably implemented as part of a conventional general-purpose computer system, such as the system 600 shown in Fig. 6, wherein the interpolator 100 of Figs. I to 5 and Fig. 7 may be implemented as part of a plug-in board.

Alternatively, the interpolator 100 may be implemented as part of a video interface 610 or graphics processor (not shown).

The process described with reference to Figs. 1 to 5 and Fig. 7 can also be implemented as software executing on the computer system 600. In particular, the steps of the method are effected by instructions in the software that are carried out by the RC04 CFP1535AU 481547 [O:\CISRA\RC\RCO4481 547.doc:SaF -13computer. The software can be divided into two separate parts; one part for carrying out the method of the preferred embodiment; and another part to manage the user interface between the latter and the user. The software can be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for orientating a character stroke or n-dimensional finite space curves in accordance with the embodiments of the 0 10 invention.

oooo: The computer system 600 has a computer module 602, a video display 616, and input devices 618, 620. In addition, the computer system 600 can have any of a number of other output devices including line printers, laser printers, plotters, and other reproduction devices connected to the computer module 602. The computer system 600 15 can be connected to one or more other computers via a communication interface 608c using an appropriate communication channel 630 such as a modem communications path, a computer network, or the like. The computer network may include a local area network S"(LAN), a wide area network (WAN), an Intranet, and/or the Internet.

The computer module 602 has a central processing unit(s) (simply referred to as a processor hereinafter) 604, a memory 606 which may include random access memory (RAM) and read-only memory (ROM), input/output (IO) interfaces 608, a video interface 610, and one or more storage devices generally represented by a block 612 in Fig. 6. The storage device(s) 612 can include one or more of the following: a floppy disc, a hard disc drive, a magneto-optical disc drive, CD-ROM, magnetic tape or any other of a number of non-volatile storage devices well known to those skilled in the art. Each of the components 604 to 612 and the interpolator 100 are typically connected to one or more of the other devices via a bus 614 that in turn includes data, address, and control buses.

The video interface 610 is connected to the video display 616 and provides video signals from the computer 602 for display on the video display 616. User input to operate RC04 CFP1535AU 481547 [O:\CISRA\R\RC04J481547.doc:SaF -14the computer 602 can be provided by one or more input devices 608. For example, an operator can use the keyboard 618 and/or a pointing device such as the mouse 620 to provide input to the computer 602. As discussed above, the interpolator 100 may be implemented as part of a video interface 610.

The system 600 is simply provided for illustrative purposes and other configurations can be employed without departing from the scope and spirit of the invention. Exemplary computers on which the preferred embodiment can be implemented include the IBM-PC or compatibles, one of the Macintosh (TM) family of PCs, Sun Sparcstation arrangements evolved therefrom or the like. The foregoing oooo are merely exemplary of the types of computers with which the embodiments of the invention may be practiced. Typically, the processes of the embodiments, described herein, are resident as software or a program recorded on a hard disk drive (generally depicted as block 612 in Fig. 6) as the computer readable medium, and read and controlled using the processor 604. Intermediate storage of the program and pixel data 15 and any data fetched from the network can be accomplished using the semiconductor memory 606, possibly in concert with the hard disk drive 12. Intermediate storage of the program and pixel data and any data fetched from the network may be accomplished S"using the semiconductor memory 606, possibly in concert with the hard disk drive 612.

In some instances, the program can be supplied to the user encoded on a CD-ROM or a floppy disk (both generally depicted by block 612), or alternatively could be read by the user from the network via a modem device connected to the computer, for example. Still further, the software can also be loaded into the computer system 600 from other computer readable medium including magnetic tape, a ROM or integrated circuit, a magneto-optical disk, a radio or infra-red transmission channel between the computer and another device, a computer readable card such as a PCMCIA card, and the Internet and Intranets including email transmissions and information recorded on websites and the like. The foregoing are merely exemplary of relevant computer readable mediums. Other computer readable mediums can be practiced without departing from the scope and spirit of the invention.

RC04 CFP1535AU 481547 (O:\CISRA\RC\RC04]481547.doc:SaF The foregoing only describes a small number of embodiments of the present invention, however, modifications and/or changes can be made thereto by a person skilled in the art without departing from the scope and spirit of the invention.

In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04J481547.doc:SaF

Claims (24)

1. A method of performing image interpolation on a first image to display a second image, the method comprising the steps of: computing pairs of positional indicators for each pixel in said first image, wherein said first image includes pixels arranged in rows and columns; calculating filter values according to said positional indicators, wherein said filter values are calculated utilising one of a plurality of filter functions; storing said pixel values of said first image in a plurality of line stores; interpolating said pixel values within said columns of said first image by using 10 said filter values for each said pixel within each said column of said first image to form a "column interpolated image; and interpolating pixel values within said rows of said column interpolated image using said stored filter values for each said pixel within each said row of said column interpolated image to form said second image.

2. A method according to claim 1, further including the step of inputting dimensioh values of said first image and said second image.

3. A method according to claim 2, further including the step of calculating a first sampling increment value, a second sampling increment value, a first sampling limit value _and_a second sampling-limit-value, -for said- first-image,-using said dimension values.

4. A method according to any one of the preceding claims, further including the step of calculating first and second fractional coordinate values using said positional indicators. A method according to any one of the preceding claims, wherein said filter functions are one dimensional functions.

RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF -17-

6. A method according to any one of the preceding claims, wherein a plurality of filter values are calculated simultaneously.

7. An apparatus for performing image interpolation on a first image to display a second image, said apparatus comprising: computer means for computing pairs of positional indicators for each pixel in said first image, wherein said first image includes pixels arranged in rows and columns; calculator means for calculating filter values according to said positional indicators, wherein said filter values are calculated utilising one of a plurality of filter .o 10 functions; o:oo0 storage means for storing said pixel values of said first image in a plurality of line stores; column interpolator means for interpolating pixel values within said columns of said first image by using said filter values for each said pixel within each said column of 15 said first image to form a column interpolated image; and row interpolator means for interpolating pixel values within said rows of said column interpolated image by using said stored filter values for each said pixel within S"each said row of said column interpolated image to form said second image.

8. An apparatus according to claim 7, wherein said means for interpolating said columns is directly connected to said means for interpolating said rows.

9. An apparatus according to claim 7, further including a means for inputting dimension values of said first image and said second image. An apparatus according to claim 9, further including means for calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values.

RC04 CFP1535AU 481547 [O:\CISRA\RC\RC041481547.doc:SaF -18-

11. An apparatus according to any one claims 7 to 10, further including means for calculating first and second fractional coordinate values using said positional indicators.

12. An apparatus according to any one of claims 7 to 11, wherein said filter functions are one dimensional functions.

13. An apparatus according to any one of claims 7 to 12, wherein a plurality of filter values are calculated simultaneously.

14. A method of performing image interpolation on a first image to display a second image, the method comprising the steps of: inputting dimension values of said first image and said second image; calculating a first sampling increment value, a second sampling increment value, 15 a first sampling limit value and a second sampling limit value, for said first image, using said dimension values; computing pairs of positional indicators according to said first and second sampling limit values; calculating first and second fractional coordinate values using said positional indicators; calculating filter values using said first and second fractional coordinate values, wherein said filter values are calculated using one of a plurality of filter functions; storing said pixel values of said first image in a plurality of line stores; interpolating pixel values within said columns of said first image by using said filter values for each said pixel within each said column of said first image to form a column interpolated image; and interpolating said pixel values within said rows of said column interpolated image by using said filter values for each said pixel within each said row of said column interpolated image to form said second image.

RC04 CFP1535AU 481547 [O:\CISRA\RC\RC041481547.doc:SaF -19- A method according claim 14, wherein said filter functions are one dimensional functions.

16. A method according to any one of claims 14 or 15, wherein a plurality of filter values are calculated simultaneously.

17. An apparatus for performing image interpolation on a first image to display a second image, the apparatus comprising: input means for inputting dimension values of said first image and said second image; first calculator means for calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values; 15 computing means for computing pairs of positional indicators according to said .ooo.i first and second sampling limit values; ~second calculator means for calculating first and second fractional coordinate values using said positional indicators; third calculator means for calculating filter values using said first and second fractional coordinate values, wherein said filter values are calculated using one of a plurality of filter functions; storage means for storing said pixel values of said first image in a plurality of line stores; column interpolator means for interpolating pixel values within said columns of said first image by using said filter values for each said pixel within each said column of said first image to form a column interpolated image; and row interpolator means for interpolating said pixel values within said rows of said column interpolated image by using said filter values for each said pixel within each said row of said column interpolated image to form said second image. RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04481547.doc:SaF

18. An apparatus according claim 17, wherein said filter functions are one dimensional functions.

19. An apparatus according to any one of claims 17 or 18, wherein a plurality of filter values are calculated simultaneously.

A computer readable memory medium for storing a program for apparatus which a processes image data, said processing comprising a process for performing image interpolation on a first image to display a second image, said program comprising: code for computing pairs of positional indicators for each pixel in said first image, wherein said first image includes pixels arranged in rows and columns; code for calculating filter values according to said positional indicators, wherein said filter values are calculated utilising one of a plurality of filter functions; 15 code for storing said pixel values of said first image in a plurality of line stores; code for interpolating said pixel values within said columns of said first image by using said filter values for each said pixel within each said column of said first image to form a column interpolated image; and code for interpolating pixel values within said rows of said column interpolated image using said stored filter values for each said pixel within each said row of said column interpolated image to form said second image.

21. A computer readable memory medium for storing a program for apparatus which processes image data, said processing comprising a process for performing image interpolation on a first image to display a second image, said program comprising:: code for inputting dimension values of said first image and said second image; code for calculating a first sampling increment value, a second sampling increment value, a first sampling limit value and a second sampling limit value, for said first image, using said dimension values; RC04 CFP1535AU 481547 [O:\CISRA\RC\RC04]481547.doc:SaF -21 code for computing pairs of positional indicators according to said first and second sampling limit values; code for calculating first and second fractional coordinate values using said positional indicators; code for calculating filter values using said first and second fractional coordinate values, wherein said filter values are calculated using one of a plurality of filter functions; code for storing said pixel values of said first image in a plurality of line stores; code for interpolating pixel values within said columns of said first image by t.o* using said filter values for each said pixel within each said column of said first image to 10 form a column interpolated image; and code for interpolating said pixel values within said rows of said column interpolated image by using said filter values for each said pixel within each said row of said column interpolated image to form said second image.

22. A method of performing image interpolation on a first image to display a second image, substantially as herein described with reference to the accompanying drawings.

23. An apparatus for performing image interpolation on a first image to display a second image, substantially as herein described with reference to the accompanying drawings.

24. A computer readable memory medium for storing a program for apparatus which processes image data, substantially as herein described with reference to the accompanying drawings. Dated 26 November, 1999 Canon Kabushiki Kaisha Patent Attorneys for the Applicant/Nominated Person SPRUSON FERGUSON RC04 CFP1535AU 481547 [O:\CISRA\RC\RC041481547.doc:SaF