Method and apparatus for arbitrary ratio image reduction

Abstract

Disclosed is a method for re-sampling an input image comprising input samples to produce an output image comprising output samples. The method includes the following steps. A set of kernel values ( 130 ) is determined ( 110 ) based on a position ( 120 ) of an input sample ( 100 ), each kernel value in the set corresponding to a distinct output sample position. Each kernel value in the set is multiplied ( 105 ) by the value of the input sample to form a contribution. Each contribution corresponds to a distinct output sample and is first added ( 145 ) to a value in a corresponding storage location in an output accumulator ( 140 ), the result of the first addition replacing the contents of the storage location in the output accumulator. Each kernel value is also second added ( 135 ) to a storage location in a sliding kernel accumulator ( 150 ), the result of the second addition replacing the contents of the storage location in the sliding kernel accumulator. An accumulated output value, is read from the output accumulator ( 140 ), is divided ( 160 ) by a kernel weight read from the sliding kernel accumulator ( 150 ) to form an output sample at the output sample position. A position of the sliding kernel accumulator is advanced by one value.

1 . A method for re-sampling an input image comprising input samples to produce an output image comprising output samples, said method comprising the steps of:
 (a) determining a set of kernel values based on a position of an input sample, each kernel value in said set corresponding to a distinct output sample position;   (b) multiplying each kernel value in said set by the value of said input sample to form a contribution, each said contribution corresponding to a distinct output sample;   (c) first adding each said contribution to a value in a corresponding storage location in an output accumulator, the result of said first addition replacing the contents of said storage location in the output accumulator;   (d) second adding each kernel value to a storage location in a sliding kernel accumulator, the result of said second addition replacing the contents of said storage location in the sliding kernel accumulator;   (e) reading an accumulated output value from said output accumulator;   (f) reading a kernel weight from said sliding kernel accumulator;   (g) dividing said accumulated output value by said kernel weight to form an output sample at said output sample position; and   (h) advancing said sliding kernel accumulator by one value.   
   
   
       2 . A method according to  claim 1  wherein the kernel values are associated with an arbitrary resealing ratio of the input image. 
   
   
       3 . A method according to  claim 1  wherein said input samples are processed in raster scan order. 
   
   
       4 . A method according to  claim 3 , wherein said output samples are produced in raster scan order. 
   
   
       5 . A method according to  claim 4 , wherein said output accumulator contains a number of values not significantly more than H lines of output, where H is the height in output samples of a vertical interpolation kernel. 
   
   
       6 . A method according to  claim 1  wherein the step (g) comprises the steps of:
 (ga) calculating a residual kernel weight representing the difference between the kernel weight and an ideal kernel weight,   (gb) determining a reciprocal of the kernel weight based on said difference, and   (gc) multiplying said accumulated output value by said reciprocal.   
   
   
       7 . A method according to  claim 1  characterised in that the method is implemented is computer hardware. 
   
   
       8 . A method according to  claim 1  characterised in that the method is computer software implemented. 
   
   
       9 . A method for re-sampling an input image comprising input samples to produce an output image comprising output samples, said method comprising the steps of:
 (a) determining a set of kernel values based on a position of an input sample, each kernel value in said set corresponding to a distinct output sample position;   (b) multiplying each kernel value by the value of said input sample to form a contribution, each contribution in said set corresponding to a distinct output sample;   (c) first adding each said contribution to a value in a storage location in an output accumulator, the result of said first addition being stored in said storage location in the output accumulator;   (d) second adding each kernel value to a storage location in a sliding kernel accumulator, including replacing said value in said storage location in the sliding kernel accumulator with low order bits of a result of said second addition;   (e) reading an accumulated output value from said output accumulator;   (f) reading a residual kernel weight from said sliding kernel accumulator, said residual kernel weight representing the difference between an ideal kernel weight and said kernel weight;   (g) determining a reciprocal of said kernel weight based on said residual kernel weight, and   (h) multiplying said accumulated output value by said reciprocal to form one of said output samples; and   (i) advancing said sliding kernel accumulator by one value.   
   
   
       10 . A method according to  claim 9  wherein the kernel values are associated with an arbitrary resealing ratio of the input image. 
   
   
       11 . A method according to  claim 9  wherein step (g) comprises subtracting said residual kernel weight from the ideal kernel weight to produce the reciprocal. 
   
   
       12 . A method according to  claim 9  wherein step (g) comprises using said residual kernel weight as an index into a table to identify said reciprocal. 
   
   
       13 . Apparatus for re-scaling images, said apparatus comprising:
 an input configured to receive a stream of input samples representing an input image;   an output configured to output a plurality of output samples representing an output image;   a calculator arranged to calculate a set of kernel values, dependent on a position of at least one of said input samples relative to the position of one of said output samples;   a multiplier for multiplying one of said input samples by one of said kernel values to form a contribution;   an output accumulator including a plurality of storage locations and an adder for adding one of said contributions to a value stored in one of said storage locations to form a contribution total to replace said value stored in said one storage location;   a sliding kernel accumulator including a plurality of kernel accumulator storage locations and an adder for adding said kernel values to each of said kernel registers;   an output process by which a contribution total, from one of said storage locations in said output accumulator, is divided by a kernel weight, from one of said kernel registers, to form one of said output samples, and the contents of said kernel accumulator storage locations are advanced by one location.   
   
   
       14 . A system for rescaling an input image, said system comprising:
 a first apparatus according to  claim 13  and operative in one of a horizontal or vertical direction of the input image; and   a second apparatus according to  claim 13  and operative in the other of the vertical and horizontal direction upon an output of the first apparatus to provide a stream of output values representing the rescaled image.   
   
   
       15 . A method for re-sampling an input image comprising input samples to produce an output image comprising output samples, said method comprising the steps of:
 (i) using kernel values based on a position of an input sample to form a contribution to an output sample, the contribution being retained in a sliding output accumulator;   (ii) adding each kernel value to a storage location in a sliding kernel accumulator,   (iii) forming an output sample value by dividing a value from the sliding output accumulator by a value from the sliding kernel accumulator; and   (iv) advancing said sliding kernel accumulator by one value.   
   
   
       16 . A method according to  claim 15  wherein the kernel values are associated with an arbitrary resealing ratio of the input image. 
   
   
       17 . A computer readable medium having a computer program recorded thereon, the program being executable by computer apparatus to re-sample an input image comprising input samples to produce an output image comprising output samples, said program comprising:
 code for determining a set of kernel values based on a position of an input sample, each kernel value in said set corresponding to a distinct output sample position;   code for multiplying each kernel value in said set by the value of said input sample to form a contribution, each said contribution corresponding to a distinct output sample;   code for first adding each said contribution to a value in a corresponding storage location in an output accumulator, the result of said first addition replacing the contents of said storage location in the output accumulator;   code for second adding each kernel value to a storage location in a sliding kernel accumulator, the result of said second addition replacing the contents of said storage location in the sliding kernel accumulator;   code for reading an accumulated output value from said output accumulator;   code for reading a kernel weight from said sliding kernel accumulator;   code for dividing said accumulated output value by said kernel weight to form an output sample at said output sample position; and   code for advancing said sliding kernel accumulator by one value.   
   
   
       18 . A computer readable medium having a computer program recorded thereon, the program being executable by computer apparatus to re-sample an input image comprising input samples to produce an output image comprising output samples, said program comprising:
 code for using kernel values based on a position of an input sample to form a contribution to an output sample, the contribution being retained in a sliding output accumulator;   code for adding each kernel value to a storage location in a sliding kernel accumulator,   code for forming an output sample value by dividing a value from the sliding output accumulator by a value from the sliding kernel accumulator; and   code for advancing said sliding kernel accumulator by one value.