AU2015201416A1 - Image downscale processing and apparatus - Google Patents

Abstract

- 28 IMAGE DOWNSCALE PROCESSING AND APPARATUS A method for downscaling an image receives a downscaling factor (RSF) to downscale the image, the downscaling factor necessitating at least successive applications of a fixed downscaling filter. An accumulation parameter (S) is determined, based on the number of pixels in the image and the received downscaling factor, to describe a number of successive applications (722,724), beyond a first application (720), of the downscaling filter where expanding of the image is not required (711,712). The method determines, based on the accumulation parameter, at least a subset of pixels (P1-P8) in the image to be used to expand the image, and downscales the image by successively applying the fixed downscaling filter to an expanded image (El) formed by combining pixels in the determined subset (P1-P8) weighted based on (i) a number of pixels in the determined subset and (ii) a contribution parameter (CF) associated with the downscaling factor. QQ1-711A 1 D12Ar:QQ en i Ineler __ - 611 Fig. 6A 1 - I Fig. 6B

Description

IMAGE DOWNSCALE PROCESSING AND APPARATUS TECHNICAL FIELD

[001] The present invention relates generally to image scaling and, in particular, to cascading image scaling with scale factor of 50%. The present invention also relates to a method and apparatus for scaling images, and to a computer program product including a computer readable medium having recorded thereon a computer program for scaling images.

BACKGROUND

[002] Image resizing is a very widely used concept. Many different image resizing filters and algorithms are known, each with its own pros and cons. Different resizing methods typically have trade-offs between processing speed and output quality.

[003] Downsizing using a series of cascaded 50% averaging steps, also known as MIP-mapping, is known to have several benefits. A primary benefit is that many scaling filters, which in the general case are expensive in CPU cycles, simplify to very fast operations at a scale factor of 50%. Only the residual scaling portion necessary to reach the target size needs to use the expensive general filter.

[004] However, cascaded downscaling by 50% has some drawbacks and limitations. One problem is how to perform cascaded 50% downscaling when the number of pixels to be downscaled is odd. One solution is to pad the image by 1 pixel. The classic padding techniques are: clamp, periodic repeat, mirror, 0 or 1. These padding techniques all have a possibility of generating artefacts at the edge of the image where the padding occurs. These artefacts are more frequent and noticeable on images with high-contrast boundaries, such as computer-generated graphs and charts.

SUMMARY

[005] Presently disclosed are methods to scale an image in a more efficient way. The methods operate to ameliorate or eliminate the artefacts associated with boundary conditions during the downscaling process, and specific implementations minimise memory requirements and computation cost.

[006] In accordance with one aspect of the present disclosure, there is provided a method for downscaling an image, the method comprising: receiving a downscaling factor to downscale the image, the downscaling factor necessitating at least successive applications of a fixed downscaling filter; determining, based on the number of pixels in the image and the received downscaling factor, an accumulation parameter describing a number of successive applications, beyond a first application, of the downscaling filter where expanding of the image is not required; determining, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image; and downscaling the image by successively applying the fixed downscaling filter to an expanded image formed by combining pixels in the determined subset weighted based on (i) a number of pixels in the determined subset and (ii) a contribution parameter associated with the downscaling factor.

[007] Accordance to another aspect of the present disclosure, there is provided a method for downscaling an image, the method comprising: receiving a downscaling factor to downscale the image, the downscaling factor necessitating at least successive applications of a fixed downscaling filter; determining, based on the number of pixels in the image and the received downscaling factor, an accumulation parameter describing a number of successive applications of the downscaling filter, beyond a first application, where expanding of the image is not required; determining, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image; and downscaling the image by successively applying the downscaling filter to a plurality of pixel values formed by (i) pixels in the image and (ii) a combination of pixels in the determined subset weighted using a contribution parameter associated with the downscaling factor and a current iteration in the successive application of the downscaling filter.

[008] Typically the contribution parameter associated with the downscaling factor is a contribution of the last pixel along one dimension in the image. Desirably the contribution parameter is further associated with a current iteration in the successive applications of the downscaling filter.

[009] Advantageously expanding of the image further comprises combining pixels in the determined subset, wherein at least some pixels of the determined subset are weighted based on the contribution of the last pixel of the image in the determined subset and the number of pixels in the determined subset.

[0010] In some implementations the method comprises using one accumulation parameter and one contribution parameter for each dimension of the image.

[0011] Generally expansion is performed at a downscaling step where the source number of pixels is odd. The fixed downscaling filter desirably operates according to a power of 2 or by a factor of 2 in each dimension.

[0012] The methods may further comprise, after the successive downscaling applications, downscaling the image by a further downscaling factor to provide a final downscaled image.

[0013] Desirably the fixed downscaling filter forms an intermediate downscaled image, the method further comprising applying a further downscaling filter to the intermediate downscaled image. Preferably the further downscaling filter is a weighted average filter. The further downscaling filter may be a supersampling filter. Advantageously additional blurring is performed in an expansion of the image to compensate for artefacts produced in the final application of the supersampling filter.

[0014] In another aspect, disclosed is a method for downscaling an image, the method comprising: performing either of the above methods to form an intermediate downscaled image; repeating the method at least once on the intermediate downscaled image to form a final successively downscaled image; and downscaling the successively downscaled image by a residual scaling factor between 0.5 and 1.0 to form a final downscaled image.

[0015] Other aspects are also disclosed.

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] At least one embodiment of the present invention will now be described with reference to the following drawings, in which: [0017] Fig. 1 is a diagram illustrating the downscaling process; [0018] Fig. 2 is a diagram illustrating the boundary condition during downscaling process; [0019] Figs. 3 A and 3B illustrate artefacts during the downscaling process; [0020] Fig. 4 is a schematic flow diagram illustrating a method of scaling the image according to the present disclosure; [0021] Fig. 5 is a schematic flow diagram showing a method of calculating the accumulation parameter during the downscaling process; [0022] Figs. 6A and 6B illustrate relationships between source and destination pixel grids for downsampling; [0023] Fig. 7 illustrates a process for calculating the accumulation parameter and virtual pixel value according to one implementation; and [0024] Figs. 8A and 8B collectively form a schematic block diagram representation of a computing system in which the described arrangements can be practised.

DETAILED DESCRIPTION INCLUDING BEST MODE

[0025] Fig. 1 shows the process of downscaling an image, in this example by input downscaling factor (IDF) of 0.167 (16.7%), using or otherwise necessitating cascaded or successive 50% downscaling (i.e. scaling factor = 0.5), followed by a final downscale step with a residual downscale factor between 1.0 and 0.5. This two-pass downscaling method is a technique known to reduce processing time. This technique consists of two different downscaling procedures, as shown in Fig. 1. The first procedure is a cascaded 50% averaging downscaling process which, in this example, includes two 50% downscaling steps 110 and 111. In this disclosure, this first downscaling procedure is only described as using a scale factor of 50% in each dimension, but in general, downscaling by other powers of 2 (such as a scale factor of 25%, or by a factor of 4 in each dimension) is also possible, and shares many of the same benefits and drawbacks.

[0026] The second procedure is a weighted average downscaling process 112 which handles any residual scale factor (RSF) between 0.5 and 1.0, necessary to achieve the desired overall scaling factor.

[0027] In the example of Fig. 1, in the first procedure, the original image 101 is scaled down to half size in both X and Y directions by a 50% downscaling process (110), to produce a first intermediate image 102. The first intermediate image 102 is then scaled down again to half the size in both X and Y directions by a 50% downscaling process (111) to produce a second intermediate image 103. The second intermediate image 103 is then scaled down according to the second procedure to the target size by the weighted average downscaling process (112), to produce a final image 104. The 50% downscaling process can be performed very efficiently as it can be done by simply averaging every two adjacent pixels in each dimension.

[0028] As shown in Fig. 2, pixels 201 represents a scanline of the original image 101; pixels 202 represents a scanline of the first intermediate image 102; 203 represents a scanline of the second intermediate image 103; and pixels 204 represents a scanline of the final image 104. A scaling factor of 50% (210 and 211) is used repeatedly until a further 50% downscaling step would result in an image smaller than the desired target size. The scaling factor required to produce an image of the target size is the residual scaling factor, with a value of between 0.5 and 1.0. For the example of Fig. 2, the residual scaling factor is approximately 66.7% (212).

[0029] This technique has a number of advantages over the traditional one-pass method. Firstly, this approach reduces the complexity of the algorithms. Secondly, the technique is generally faster than a one-pass downscaling filter which is more complicated than a 2x2 averaging window. The technique is more cache-friendly especially when dealing with large images, and also is more suitable for processing of a banded image.

[0030] Downscaling using cascaded 50% averaging steps, also known as MIP-mapping, is known to have performance benefits, and is widely used in areas such as video and image display on screens. A problem however arises when the number of pixels in the width or height of the image to be downscaled is odd - what should the value of the downscaled pixel at the boundary be? As shown in Fig 2, values of Q1 and Rl, being pixels at the edges of the intermediate images, need to be determined during 50% averaging downscaling.

[0031] There are classic padding techniques such as clamp, periodic repeat, mirror, or padding constant value 0 or 1. These padding techniques all have the possibility to generate artefacts. Such artefacts are more frequent and noticeable in images with high-contrast boundaries, such as computer generated graphs and charts.

[0032] Fig. 3 A and 3B show how a typical artefact is caused by a cascading downscaling process using the prior art padding technique described above. In Fig. 3 A, a Page 310 shows an original-size presentation slide 311 on which a chart is printed, having a thin rectangular frame 312 at the edge of the image. Page 320 in Fig. 3B shows the presentation slide 311 printed at a smaller size 321, in order to fit four slides on the same page 320 (the other three slides not being illustrated for clarity). The content of presentation slide 321 is downscaled from the original presentation slide 311 by a scale factor of 0.4. As the result of downscaling process, the original thin frame 312 is printed as a smaller rectangle 322 with faded color. The right edge (323) of the smaller frame (322) however is printed with darker color 323 than the rest of the frame. This is caused by padding ‘ Γ to the right-most pixel of each scanline during the downscaling process.

[0033] Similar artefacts can occur for all other prior art padding methods (clamp, periodic repeat, mirror, or 0), depending on the content of the image to be scaled.

[0034] According to the present disclosure, these artefacts are avoided by choosing a value such as Q1 in Fig. 2 by averaging the final odd pixel PI with an extra “virtual” pixel value El. The value of El is a weighted average of a number of adjacent pixels (PI, ...), in which the number depends on the number of subsequent 50% downscaling steps whose source number of pixels is even. This calculation, together with tracking a contribution factor CF of the final pixel, allows correct weighted averaging to be performed even though at each 50% downscaling step, the only scaling operation is a simple and fast averaging operation of neighbouring pixels.

[0035] Figs. 8A and 8B depict a general-purpose computer system 800, upon which the various arrangements described can be practiced.

[0036] As seen in Fig. 8A, the computer system 800 includes: a computer module 801; input devices such as a keyboard 802, a mouse pointer device 803, a scanner 826, a camera 827, and a microphone 880; and output devices including a printer 815, a display device 814 and loudspeakers 817. An external Modulator-Demodulator (Modem) transceiver device 816 may be used by the computer module 801 for communicating to and from a communications network 820 via a connection 821. The communications network 820 may be a wide-area network (WAN), such as the Internet, a cellular telecommunications network, or a private WAN. Where the connection 821 is a telephone line, the modem 816 may be a traditional “dial-up” modem. Alternatively, where the connection 821 is a high capacity (e.g., cable) connection, the modem 816 may be a broadband modem. A wireless modem may also be used for wireless connection to the communications network 820.

[0037] The computer module 801 typically includes at least one processor unit 805, and a memory unit 806. For example, the memory unit 806 may have semiconductor random access memory (RAM) and semiconductor read only memory (ROM). The computer module 801 also includes an number of input/output (I/O) interfaces including: an audio-video interface 807 that couples to the video display 814, loudspeakers 817 and microphone 880; an I/O interface 813 that couples to the keyboard 802, mouse 803, scanner 826, camera 827 and optionally a joystick or other human interface device (not illustrated); and an interface 808 for the external modem 816 and printer 815. In some implementations, the modem 816 may be incorporated within the computer module 801, for example within the interface 808. The computer module 801 also has a local network interface 811, which permits coupling of the computer system 800 via a connection 823 to a local-area communications network 822, known as a Local Area Network (LAN). As illustrated in Fig. 8A, the local communications network 822 may also couple to the wide network 820 via a connection 824, which would typically include a so-called “firewall” device or device of similar functionality. The local network interface 811 may comprise an Ethernet circuit card, a Bluetooth™ wireless arrangement or an IEEE 802.11 wireless arrangement; however, numerous other types of interfaces may be practiced for the interface 811.

[0038] The EO interfaces 808 and 813 may afford either or both of serial and parallel connectivity, the former typically being implemented according to the Universal Serial Bus (USB) standards and having corresponding USB connectors (not illustrated). Storage devices 809 are provided and typically include a hard disk drive (HDD) 810. Other storage devices such as a floppy disk drive and a magnetic tape drive (not illustrated) may also be used. An optical disk drive 812 is typically provided to act as a non-volatile source of data. Portable memory devices, such optical disks (e.g., CD-ROM, DVD, Blu ray Disc™), USB-RAM, portable, external hard drives, and floppy disks, for example, may be used as appropriate sources of data to the system 800.

[0039] The components 805 to 813 of the computer module 801 typically communicate via an interconnected bus 804 and in a manner that results in a conventional mode of operation of the computer system 800 known to those in the relevant art. For example, the processor 805 is coupled to the system bus 804 using a connection 818. Likewise, the memory 806 and optical disk drive 812 are coupled to the system bus 804 by connections 819. Examples of computers on which the described arrangements can be practised include IBM-PC’s and compatibles, Sun Sparcstations, Apple Mac™ or a like computer systems.

[0040] The method of downscaling an image may be implemented using the computer system 800 wherein the processes of Figs. 4 to 7, to be described, may be implemented as one or more software application programs 833 executable within the computer system 800. In particular, the steps of downscaling an image are effected by instructions 831 (see Fig. 8B) in the software 833 that are carried out within the computer system 800. The software instructions 831 may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part and the corresponding code modules performs the image downscaling methods and a second part and the corresponding code modules manage a user interface between the first part and the user.

[0041] The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer system 800 from the computer readable medium, and then executed by the computer system 800. A computer readable medium having such software or computer program recorded on the computer readable medium is a computer program product. The use of the computer program product in the computer system 800 preferably effects an advantageous apparatus for downscaling an image.

[0042] The software 833 is typically stored in the HDD 810 or the memory 806. The software is loaded into the computer system 800 from a computer readable medium, and executed by the computer system 800. Thus, for example, the software 833 may be stored on an optically readable disk storage medium (e.g., CD-ROM) 825 that is read by the optical disk drive 812. 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 system 800 preferably effects an apparatus for downscaling an image.

[0043] In some instances, the application programs 833 may be supplied to the user encoded on one or more CD-ROMs 825 and read via the corresponding drive 812, or alternatively may be read by the user from the networks 820 or 822. Still further, the software can also be loaded into the computer system 800 from other computer readable media. Computer readable storage media refers to any non-transitory tangible storage medium that provides recorded instructions and/or data to the computer system 800 for execution and/or processing. Examples of such storage media include floppy disks, magnetic tape, CD-ROM, DVD, Blu-ray Disc™, a hard disk drive, a ROM or integrated circuit, USB memory, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 801. Examples of transitory or non-tangible computer readable transmission media that may also participate in the provision of software, application programs, instructions and/or data to the computer module 801 include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.

[0044] The second part of the application programs 833 and the corresponding code modules mentioned above may be executed to implement one or more graphical user interfaces (GUIs) to be rendered or otherwise represented upon the display 814. Through manipulation of typically the keyboard 802 and the mouse 803, a user of the computer system 800 and the application may manipulate the interface in a functionally adaptable manner to provide controlling commands and/or input to the applications associated with the GUI(s). Other forms of functionally adaptable user interfaces may also be implemented, such as an audio interface utilizing speech prompts output via the loudspeakers 817 and user voice commands input via the microphone 880.

[0045] Fig. 8B is a detailed schematic block diagram of the processor 805 and a “memory” 834. The memory 834 represents a logical aggregation of all the memory modules (including the HDD 809 and semiconductor memory 806) that can be accessed by the computer module 801 in Fig. 8A.

[0046] When the computer module 801 is initially powered up, a power-on self-test (POST) program 850 executes. The POST program 850 is typically stored in a ROM 849 of the semiconductor memory 806 of Fig. 8 A. A hardware device such as the ROM 849 storing software is sometimes referred to as firmware. The POST program 850 examines hardware within the computer module 801 to ensure proper functioning and typically checks the processor 805, the memory 834 (809, 806), and a basic input-output systems software (BIOS) module 851, also typically stored in the ROM 849, for correct operation. Once the POST program 850 has run successfully, the BIOS 851 activates the hard disk drive 810 of Fig. 8 A. Activation of the hard disk drive 810 causes a bootstrap loader program 852 that is resident on the hard disk drive 810 to execute via the processor 805. This loads an operating system 853 into the RAM memory 806, upon which the operating system 853 commences operation. The operating system 853 is a system level application, executable by the processor 805, to fulfil various high level functions, including processor management, memory management, device management, storage management, software application interface, and generic user interface.

[0047] The operating system 853 manages the memory 834 (809, 806) to ensure that each process or application running on the computer module 801 has sufficient memory in which to execute without colliding with memory allocated to another process. Furthermore, the different types of memory available in the system 800 of Fig. 8 A must be used properly so that each process can run effectively. Accordingly, the aggregated memory 834 is not intended to illustrate how particular segments of memory are allocated (unless otherwise stated), but rather to provide a general view of the memory accessible by the computer system 800 and how such is used.

[0048] As shown in Fig. 8B, the processor 805 includes a number of functional modules including a control unit 839, an arithmetic logic unit (ALU) 840, and a local or internal memory 848, sometimes called a cache memory. The cache memory 848 typically include a number of storage registers 844 - 846 in a register section. One or more internal busses 841 functionally interconnect these functional modules. The processor 805 typically also has one or more interfaces 842 for communicating with external devices via the system bus 804, using a connection 818. The memory 834 is coupled to the bus 804 using a connection 819.

[0049] The application program 833 includes a sequence of instructions 831 that may include conditional branch and loop instructions. The program 833 may also include data 832 which is used in execution of the program 833. The instructions 831 and the data 832 are stored in memory locations 828, 829, 830 and 835, 836, 837, respectively. Depending upon the relative size of the instructions 831 and the memory locations 828-830, a particular instruction may be stored in a single memory location as depicted by the instruction shown in the memory location 830. Alternately, an instruction may be segmented into a number of parts each of which is stored in a separate memory location, as depicted by the instruction segments shown in the memory locations 828 and 829.

[0050] In general, the processor 805 is given a set of instructions which are executed therein. The processor 805 waits for a subsequent input, to which the processor 805 reacts to by executing another set of instructions. Each input may be provided from one or more of a number of sources, including data generated by one or more of the input devices 802, 803, data received from an external source across one of the networks 820, 822, data retrieved from one of the storage devices 806, 809 or data retrieved from a storage medium 825 inserted into the corresponding reader 812, all depicted in Fig. 8A. The execution of a set of the instructions may in some cases result in output of data. Execution may also involve storing data or variables to the memory 834.

[0051] The disclosed image downscaling arrangements use input variables 854, which are stored in the memory 834 in corresponding memory locations 855, 856, 857. The downscaling arrangements produce output variables 861, which are stored in the memory 834 in corresponding memory locations 862, 863, 864. Intermediate variables 858 may be stored in memory locations 859, 860, 866 and 867.

[0052] Referring to the processor 805 of Fig. 8B, the registers 844, 845, 846, the arithmetic logic unit (ALU) 840, and the control unit 839 work together to perform sequences of micro-operations needed to perform “fetch, decode, and execute” cycles for every instruction in the instruction set making up the program 833. Each fetch, decode, and execute cycle comprises: (i) a fetch operation, which fetches or reads an instruction 831 from a memory location 828, 829, 830; (ii) a decode operation in which the control unit 839 determines which instruction has been fetched; and (iii) an execute operation in which the control unit 839 and/or the ALU 840 execute the instruction.

[0053] Thereafter, a further fetch, decode, and execute cycle for the next instruction may be executed. Similarly, a store cycle may be performed by which the control unit 839 stores or writes a value to a memory location 832.

[0054] Each step or sub-process in the processes of Figs. 4 to 7 is associated with one or more segments of the program 833 and is performed by the register section 844, 845, 846, the ALU 840, and the control unit 839 in the processor 805 working together to perform the fetch, decode, and execute cycles for every instruction in the instruction set for the noted segments of the program 833.

[0055] Fig. 4 is a flow diagram showing a method 400 for scaling an input image at horizontal dimension by a given input scale factor. In practice, the steps of the method 400 must be applied in both the horizontal and vertical directions, as explained below. The method 400, together with its vertical direction complement, form part of the program 833 executable by the processor 805. The method 400 starts at initialisation step 410, where the following parameters are initialised: required scale factor - RSF set to input downscaling factor current image - Cl point to the input image number of current pixels - CP set to number of pixels per scanline in input image contribution factor - CF set to 1 (one).

[0056] After the initialisation, the method 400 continues at scale factor checking step 420, where the processor 805 checks the residual scale factor RSF. Where the processor 805 determines that the residual scale factor (RSF), being the currently required scale factor, is smaller than 0.5 (RSF < 0.5), which means the target image size is smaller than half of the current image, the method 400 proceeds to checking step 440. Otherwise, where the required scale factor (RSF) is greater than or equal to 0.5 (RSF >= 0.5), the method 400 goes to final downscale step 430. At the checking step 440, the number of pixels in a scanline in the current image (CP) is checked by the processor 805. If the number of pixels (CP) in the current scanline is even, the method 400 continues to a 50% downscaling step 480. If at step 440 the number of pixels (CP) in the current scanline is odd, the method goes to step 450. At step 450 an accumulation parameter S is determined by the processor 805. This is preferably done by means of process 500, described later with reference to Fig. 5. Next, at step 460, a value E of a virtual pixel is determined by the processor 805, such that the value E can be averaged together with the last pixel (Pi) on the current scanline in an upcoming 50% downscaling step. The value E is stored in a temporary memory buffer, such as the buffer 859.

[0057] The value of the virtual pixel E is preferably calculated based on the accumulation parameter S according to the following formula:

(Eqn. 1) where: CF is the contribution factor of the last pixel in current scanline; S is the accumulation parameter calculated in step 450 which is the number of subsequent successive 50% downscaling steps where the input number of pixels is even (i.e. the number of successive 50% downscaling steps, beyond or after a first 50% downscaling step, in the sequence of successive steps) immediately before the next application of a 50% downscaling step where the input number of pixels is odd, or no further 50% downscaling steps are required; and

Pi is the pixel value of the 1th pixel from the last pixel in the current scanline. Pi is the last pixel in the current scanline, P2 is the second last pixel in the current scanline, and so on.

[0058] In words, the above formula provides that the value of E is calculated as a weighted average of the last n pixels in the scanline, where the number n depends on the accumulation parameter S such that when S = 0, n = 1; when S = 1, n = 3; when S = 2, n = 7; and so on, with n taking a value one less than the next highest power of 2 each time. The weighted average calculation is equivalent to a direct (non-weighted) average when the contribution factor CF is equal to 1. When CF is less than 1, the contribution of the final pixel to the weighted average (relative to the contribution of each other averaged pixel) is correspondingly reduced. In short, a subset of pixels in the image Pi...Pi is selected for calculating an adjacent virtual pixel E which expands the image at its edge, where the number of selected pixels i depends on the accumulation parameter S. As such the value of the virtual pixel E represents a combination of pixels in the determined subset of pixels Pi ... Pi using the contribution parameter (CF) associated with the fixed downscaling factor and a current iteration in the successive application of the downscaling filter. The combination is a single pixel value E that forms part of the plurality of pixels that are successively downscaled. Typically, a pixel value is a single intensity value for a monochrome image, or a vector of intensity values in the case of a colour image. In the case that a pixel value is a vector, the above formula produces a vector value for the single pixel value E.

[0059] This concept is illustrated by Fig. 7, which shows an exemplary one-dimensional image, having a width of 23 pixels, at various stages throughout the downscaling process. The dashed line 720 is a geometrical representation of the contribution factor CF of the final pixel in each image in the downsample process. The dashed line 720 encompasses the entirety of the final pixel PI of initial image 701 because the contribution factor CF of pixel PI is 1. The dashed line 720 cuts through final pixel Q1 of the first intermediate image 702 because the contribution factor CF of pixel Q1 is 0.5; and so forth. The contribution parameter associated with the downscaling factor is a contribution of the last pixel along one dimension in the image. Here, for a single dimensional image, a single contribution factor is used. For a twodimensional image a contribution factor is determined for each dimension.

[0060] As seen in Fig. 7, an initial image 701 is noted as having an odd pixel count (being 23 in this example), and so a virtual pixel El 710 is calculated preferably using the formula of Eqn. 1 given above. In this case, S = 2, because the next two successive 50% downscaling steps have an input number of pixels 702 and 703 which are even (being 12 and 6 respectively), while the following 50% downscaling step has an input number of pixels 704 which is odd (being 3). The formula of Eqn. 1 therefore assigns a value to El 710 that is equal to the weighted average of values P1...P7, where the weight of pixel Pi is equal to its contribution factor CF, which, initially, is 1, and the weight of all other pixels equal to 1. This is desired, because intermediate pixel 01, with contribution factor CF = 0.875, gets all of its contribution from source pixels PI to P7. That is, the value of 01 must be equal to the average of PI to P7 to produce correct results.

[0061] At this stage, the input image line 701 is to be downscaled by receiving a downscaling factor (RSF) to downscale the image 701 in a manner necessitating successive (in this case 3) applications (i.e. 720, 722 and 724) of a fixed downscaling (50%) filter. The downscaling determines, based on the number of pixels in the image 701 and the received downscaling factor, an accumulation parameter (S) describing a number of successive applications, beyond a first application, of the downscaling filter where expanding of the image is not required and immediately before a successive application of the downscaling filter where expanding of the image is required, or where no further application of the 50% downscaling filter is required. Here, at the input image line 701, the number of successive applications (being 722, 724) after the first application (720) is 2, i.e. S=2, because a third application 726 requires expanding of the image, due to the number of pixels in the associated intermediate image 704 being odd. The process then determines, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image. In Fig. 7, the subset are the pixels PI - P7 and the image is expanded by one pixel, the pixel El 710, that is added as a virtual pixel to the end of the input image run of pixels 701 to create an expanded image having an even number of pixels. The process then downscales the image by applying the fixed downscaling filter to the expanded image where the value of the expanded pixel El 710 is formed by combining pixels in the determined subset PI - P7 weighted based on (i) a number of pixels in the determined subset (i.e. 7 in this case) and (ii) the contribution parameter associated with the downscaling factor. Here, the initial contribution factor for the first downscaling is CF= 1, meaning that each of the pixels PI - P7 contributes equally to the value of the pixel El. Other contribution factors are determined for each respective downscaling as described above. The downscaling by the fixed downscaling factor (50%) then is performed three times (i.e. the first downscaling and then twice more based on the accumulation parameter). For each of the images 702 and 703, the source number of pixels is even, and so expansion of the image is not required in order to perform a 50% downscaling. This process ultimately results in the image 704 which has an odd pixel count. The image 704 may be considered an intermediate image.

[0062] Subsequently, intermediate image 704 also has an odd pixel count, and so another virtual pixel value E2 713 is calculated using the same formula. In this case, S = 1, because the next 50% downscaling step has an input number of pixels 705 which is even, while the following 50% downscaling step has an input number of pixels 706 which is odd. The formula therefore assigns a value to E2 713 equal to the weighted average of values 01...03, with the weight of pixel 01 is equal to its contribution factor CF, which is 0.875, and the weight of all other pixels equal to 1. This is desired, because intermediate pixel HI, with contribution factor CF = 0.71875, gets all of its contribution from source pixels PI to P23; that is, the value of HI must be equal to the average of PI to P23 to produce correct results. This is achieved, despite the calculation of each pixel such as Q1 711, R1 712, G1 714, and HI 715 being a simple average, because the calculation of El and E2 depends on the accumulation parameter S.

[0063] Next at step 470, the current scanline, including the virtual pixel value E calculated in step 460, is scaled down by 50% using an averaging method. The value of the final intermediate pixel produced by the 50% scaling step is the average of the last pixel in the current scanline, and the virtual pixel value E which was calculated in step 460. The intermediate pixel value is stored in-place in the original image buffer to minimise memory usage. The process of step 460 and 470 are repeated for each scanline in the current image until all the scanlines in the current image are scaled down.

[0064] At step 475, the current image pointer (Cl) is updated to point to the intermediate downscaled image which was produced during step 470. The final pixel contribution factor (CF) is halved (since half of the final pixel in the intermediate image produced in step 470 is from a virtual pixel value). The number of current pixels (CP) is incremented by 1 (representing the virtual pixel E calculated in step 460), and then halved (due to the 50% downscaling), and the required scale factor (RSF) is doubled (since scaling with a factor of 0.5 has just been performed), i.e.: CF = — 2 CP = — 2 RSF = RSF X 2 [0065] After these adjustments, the process 400 returns to step 420 to perform a further iteration of the downscaling processes.

[0066] Back at step 440, if the number of pixels (CP) in the current scanline is even, method 400 proceeds to downscaling step 480. At step 480, the current image is scaled down by 50% using an averaging method. The intermediate pixel value is stored in-place in the original image buffer to minimise memory usage. Then, at step 490, the current image pointer (Cl) is updated to point at the intermediate downscaled image which was produced during step 480; the contribution factor (CF) of the final pixel in the scanline is added to 1 (representing the wholly non-virtual second-last pixel with which it is averaged), and then halved (representing the averaging step). The number of current pixels (CP) is halved (due to the 50% downscaling), and the required scale factor (RSF) is doubled (since scaling with a factor of 0.5 has just been performed), i.e.: CF = 2 CP=^ 2 RSF = RSF X 2 [0067] After these adjustments, the process 400 returns to step 420 [0068] Back at decision step 420, for a further iteration, if the required scale factor (RSF) is greater than or equal to 0.5 (RSF >= 0.5), meaning that the target image size is greater than half the size of the current image, then the process 400 continues to the final downscaling step 430.

[0069] Returning to the example of Fig. 7, in this case, the process discussed above is repeated. At the present stage, the current (input) image line 704 is to be downscaled by receiving a downscaling factor (RSF) to downscale the image 704 in a manner necessitation successive (in this case 2) applications (i.e. 726, and 728) of a fixed downscaling (50%) filter. The downscaling determines, based on the number of pixels in the image 704 and the received downscaling factor, an accumulation parameter (S) describing a number of successive applications, beyond a first application, of the downscaling filter where expanding of the image is not required. Here, at the input image line 704, the number of successive applications (being 728) after the first application (726), but immediately before the application of the downscaling filter where expanding of the image 706 is required, or no further applications of the 50% downscaling filter are required, is 1, i.e. S=l. The process then determines, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image. In Fig. 7, at line 704 the subset are the pixels 01-03 and the image is expanded by one pixel, the pixel E2 713, that is added as a virtual pixel to the end of the run of pixels 704 to create an expanded image now having an even number of pixels. This added pixel is called a virtual pixel because even though for all purposes spatial location of the pixel within the image is considered to be at the end of the run of pixels 704, the value of the pixel is preferably not stored in the same memory as the other image pixels 704, but in a separate temporary location such as in buffer 859. The process then downscales the image by applying the fixed downscaling filter to the expanded image where the value of the expanded pixel E2 713 is formed by combining pixels in the determined subset 01-03 weighted based on (i) a number of pixels in the determined subset (i.e. 3 in this case) and (ii) the contribution parameter associated with the downscaling factor. Here, the contribution factor for the first downscaling CF= 0.875, which is used to determine the value of the pixel E2 in the manner described above. Other contribution factors are determined for each respective downscaling as described above. The downscaling by the fixed downscaling factor (50%) then is performed twice (i.e. the first downscaling and then once more based on the accumulation parameter). This results in the image 706 which has an odd pixel count. The image 706 may be considered an intermediate image and then subjected to further iterations of the described process where necessary. Alternatively, the image 706 may then be subjected to the final downscale step 430 to achieve the overall desired downscaling of the input image 701.

[0070] At step 430, a final downscaling operation is performed, using a weighted average filter, and with a scaling factor of RSF. The weighted average filter produces a result for a given destination pixel by examining each source pixel whose area contributes (partially or fully) to the destination pixel region. Each such source pixel value is multiplied by the proportion of the source pixel contained within the destination pixel region, summed together, and normalised to produce the destination pixel value.

[0071] In the final downscaling step 430, determining which source pixels contribute to a given destination pixel region can be done geometrically, by overlaying a scaled destination pixel grid on the source pixels. Each source pixel which intersects with the given destination pixel contributes to the destination pixel. The contribution factor (CF) of the final pixels in a scanline is accounted for in this overlaying step. For example, if CF is 0.75, then the destination pixel grid is overlayed up to three quarter of the edge pixels. This is illustrated in Fig 6A, where a source image 601 containing 6x6 pixels is shown. The right side and bottom edge pixels have a contribution factor (CF) of 0.75, as indicated by the dashed lines 611 and 612. A destination image pixel grid 602 of size 4x4 pixels is also shown. Fig. 6B shows the overlaying of the scaled destination pixel grid 603 onto the source pixel grid 601. The positioning of the right edge and bottom edge of scaled destination pixel grid 603 is determined by the contribution factor (CF) of the final pixels as indicated by the dash line 611 and 612 in Fig. 6A.

[0072] After performing the final downscaling step 430, the process 400 ends.

[0073] It is noted that the example input image has an arbitrarily small odd number of pixels, and in typical situations image sizes will be substantially larger. This notwithstanding, the example of Fig. 7 may be considered to what occurs with the right-edge of a large image.

[0074] It is possible to use filters other than weighted average at step 430. For example, a supersampling filter may be used. A supersampling filter samples a number of points (for example, four) in the source image within the destination pixel region, and averages them to produce a destination pixel value. A supersampling filter is faster than a weighted average filter, but can reduce the quality of the result. In particular, any contributing source pixel which is not incident with any of the sample points will have no actual contribution to the destination pixel. This can have a particular impact on edge pixels with CF < 1, since, unlike any other pixels in the image, these edge source pixels will not contribute to any other destination pixel. In the case of computer generated graphics with a thin high-contrast frame, this can cause the frame to disappear completely on one edge, or, alternatively, to be over-emphasised on one edge, resulting in edge artefacts.

[0075] The additional edge-related artefacts introduced by using a faster supersampling filter can be reduced by applying a blurring operation when calculating the virtual pixel value E in step 460. One way to apply a blurring operation is to add 1 to the accumulation parameter value S, calculated in step 450, before using the accumulation parameter value S to calculate the virtual pixel value E in step 460. This means the value of E is calculated as a weighted average of roughly twice as many neighbouring pixels as is required to produce the un-blurred results. The effect is to distribute high-frequency elements across a broader set of pixels at the edge of the image into each virtual pixel E, thus avoiding over-emphasis of features such as a thin high-contrast frame caused by a supersampling geometry which happens to be unfavourable for a given input image.

[0076] Another approach to applying blurring to mitigate edge-related artefacts introduced by supersampling, but which does not generally remove all edge-related artefacts related to dealing with odd pixel counts in a cascading 50% downscaling system, is to skip accumulation parameter determination step 450, and to perform the virtual pixel calculation step 460 as a simple averaging operation, according to the following formula: CF X Pi + P? E =---- CF + 1 where: (Eqn. 2) CF is the contribution factor of the last pixel in the current scanline;

Pi is the last pixel in the current scanline; and P2 is the second last pixel in the current scanline.

[0077] That is, in this alternative implementation, the virtual pixel value E calculated at step 460 is the weighted average of the last two pixels of the source image, with the final pixel being weighted according to its contribution factor value (CF).

[0078] The approach based upon Equation 2 calculates the virtual pixel value E faster than the originally described process based upon Equation 1, and reduces the majority of artefact problems related to boundary value conditions for odd pixel counts in a cascading 50% downscaling filter.

[0079] A preferred method 500 for calculating the accumulation parameter S, as executed at step 450 of process 400 will now be described with reference to Fig 5. The accumulation parameter S is calculated as the number of successive 50% downscaling steps, following the next one, whose source number of pixels is even. As such, the accumulation parameter describes a number of further successive applications of the downscaling filter where expanding of the image is not required. The method 500 begins at initialisation step 510, where the accumulation parameter S is set to zero: accumulation parameter - S = 0.

[0080] Next, at step 520, a variable of pixel count (PC) is set to be the half of the total value of the number of current pixel (CP) plus one: • 1 CP+l pixel count - PC = [0081] At step 530, the value of pixel count (PC) is checked. If the pixel count (PC) is an even number, the method 500 continues at step 540, where the accumulation parameter S is increased by one: S = S + 1 [0082] At next step 550, the pixel count (PC) is set to half of itself, : PC = ^ 2 [0083] After adjusting the pixel count (PC), the method returns to decision step 530. At step 530, if the pixel count (PC) is an odd number, the method 500 ends and the calculated accumulation parameter S is returned.

[0084] The process 500 can be replaced by any operation which produces the same S value given the same initial PC value. For example, the calculations can be optimised by means of bit inspection operations, or a look-up table can be used to store pre-computed S values for some initial pixel count values.

[0085] The processes 400 and 500 described above have been described in terms of the horizontal dimension only, however, in practice, the steps of these processes are applied in both the horizontal and vertical directions. When applying processes 400 and 500 vertically, the word “scanline” should be read as “column”. The same technique can be performed in two dimensions with one pass for each dimension, or in a single pass operation which processes the two dimensions at same time.

[0086] With single pass processing, the 50% scaling steps 480 and 470 will typically average four pixel values in a square configuration, but only two if 50% scaling is performed only in one dimension. Separate state variables are used for each dimension: RSFV, CPV, and CFV tracking the required scale factor, the number of current pixels, and the contribution factor in the vertical dimension; and RSFh, CPh, and CFh tracking the required scale factor, the number of current pixels, and the contribution factor in the horizontal direction. The vertical and horizontal accumulation parameter Svand Share also calculated separately, since in general their values are different. The previously described equation (Equation 1) is used both to calculate virtual pixels in the horizontal direction, at the right edge 323 of an image, using horizontally adjacent pixels P:

(Eqn. 3) and to calculate virtual pixels in the vertical direction, at the bottom edge 322 of an image, using vertically adjacent pixels P:

(Eqn. 4) [0087] As an example of applying process 400 in two dimensions in a single pass, in step 440, the width CPh of the current image Cl may be even, but the height CPV may be odd.

In this case, each pair of scanlines is downscaled according to step 480 until the final scanline of the image, which has no pair due to the odd pixel count CPV. For each column in the final scanline, the accumulation parameter is determined in the vertical direction in step 450 according to process 500 and a virtual pixel value in the final scanline is calculated in step 460. The 50% downscaling step 470 is applied after every two virtual pixel values are computed.

For example, the first two pixels in the final scanline of the source image are averaged together with the first two virtual pixel values, to produce the first pixel of the final scanline in the output intermediate image.

[0088] In the case where two dimensions are processed in a single pass, and both the width CPh and height CPV of the current image Cl is odd, a special calculation must be made to determine the virtual pixel value in the far bottom corner of the image. In this case, because the virtual pixel value E is the weighted average of horizontal and vertical virtual pixel components Eh and Ey, then: E = CFhEh+CFvEv (Eqn. 5) CFh+CFv V 4 ' where Eh and Ey are calculated according to the formula for E presented when step 460 was previously described. In this case, the “last n pixels in the current scanline” Pn to Pi, used to calculate the horizontal virtual pixel component Eh, are in fact virtual pixels previously calculated in the vertical direction, and the last n pixels in the current column Pn to Pi, used to calculate the vertical virtual pixel component Ey, are virtual pixels previously calculated in the horizontal direction.

[0089] In those instances where S=0, an application of the fixed downscaling filter is applied, via which Eqn. 1 results in a virtual pixel whose value is equal to PI. This step is equivalent to traditional processes (padding with a duplicate pixel value).

INDUSTRIAL APPLICABILITY

[0090] The arrangements described are applicable to the computer and data processing industries and particularly for the downscale processing of images, particularly those formed from graphical descriptions which have sharp edges ordinarily prone to rendering artefacts.

[0091] The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.

[0092] (Australia Only) 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 correspondingly varied meanings.

Claims (20)

1. CLAIMS: The claims defining the invention are as follows:

   1. A method for downscaling an image, the method comprising: receiving a downscaling factor to downscale the image, the downscaling factor necessitating at least successive applications of a fixed downscaling filter; determining, based on the number of pixels in the image and the received downscaling factor, an accumulation parameter describing a number of successive applications, beyond a first application, of the downscaling filter where expanding of the image is not required; determining, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image; and downscaling the image by successively applying the fixed downscaling filter to an expanded image formed by combining pixels in the determined subset weighted based on (i) a number of pixels in the determined subset and (ii) a contribution parameter associated with the downscaling factor.
2. 2. A method for downscaling an image, the method comprising: receiving a downscaling factor to downscale the image, the downscaling factor necessitating at least successive applications of a fixed downscaling filter; determining, based on the number of pixels in the image and the received downscaling factor, an accumulation parameter describing a number of successive applications of the downscaling filter, beyond a first application, where expanding of the image is not required; determining, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image; and downscaling the image by successively applying the downscaling filter to a plurality of pixel values formed by (i) pixels in the image and (ii) a combination of pixels in the determined subset weighted using a contribution parameter associated with the downscaling factor and a current iteration in the successive application of the downscaling filter.
3. 3. A method according to claim 1 or 2, wherein the contribution parameter associated with the downscaling factor is a contribution of the last pixel along one dimension in the image.
4. 4. A method according to claim 2, wherein the contribution parameter is further associated with a current iteration in the successive applications of the downscaling filter.
5. 5. A method according to claim 1 or 2 wherein expanding of the image further comprises combining pixels in the determined subset, wherein at least some pixels of the determined subset are weighted based on the contribution of the last pixel of the image in the determined subset and the number of pixels in the determined subset.
6. 6. A method according to claim 1 or 2, comprising using one accumulation parameter and one contribution parameter for each dimension of the image.
7. 7. A method according to claim 1 or 2 wherein expansion is performed at a downscaling step where the source number of pixels is odd.
8. 8. A method according to claim 1 or 2, wherein the fixed downscaling filter operates according to a power of 2 or by a factor of 2 in each dimension.
9. 9. A method according to claim 1 or 2 further comprising, after the successive downscaling applications, downscaling the image by a further downscaling factor to provide a final downscaled image.
10. 10. A method according to claim 1 wherein the fixed downscaling filter forms an intermediate downscaled image, the method further comprising: applying a further downscaling filter to the intermediate downscaled image.
11. 11. A method according to claim 10, wherein the further downscaling filter is a weighted average filter.
12. 12. A method according to claim 10, wherein the further downscaling filter is a supersampling filter.
13. 13. A method according to claim 12, wherein additional blurring is performed in an expansion of the image to compensate for artefacts produced in the final application of the supersampling filter.
14. 14. A method for downscaling an image, the method comprising: performing the method of claim 1 to form an intermediate downscaled image; repeating the method of claim 1 at least once on the intermediate downscaled image to form a final successively downscaled image; and downscaling the successively downscaled image by a residual scaling factor between 0.5 and 1.0 to form a final downscaled image.
15. 15. A non-transitory computer readable storage medium having a program recorded thereon, the program being executable by a processor to downscale an image, the program comprising: code for receiving a downscaling factor to downscale the image, the downscaling factor necessitating at least successive applications of a fixed downscaling filter; code for determining, based on the number of pixels in the image and the received downscaling factor, an accumulation parameter describing a number of successive applications, beyond a first application, of the downscaling filter where expanding of the image is not required; code for determining, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image; and code for downscaling the image by successively applying the fixed downscaling filter to an expanded image formed by combining pixels in the determined subset weighted based on (i) a number of pixels in the determined subset and (ii) a contribution parameter associated with the downscaling factor.
16. 16. A non-transitory computer readable storage medium having a program recorded thereon, the program being executable by a processor to downscale an image, the program comprising: code for receiving a downscaling factor to downscale the image, the downscaling factor necessitating at least successive applications of a fixed downscaling filter; code for determining, based on the number of pixels in the image and the received downscaling factor, an accumulation parameter describing a number of successive applications of the downscaling filter, beyond a first application, where expanding of the image is not required; code for determining, based on the accumulation parameter, at least a subset of pixels in the image to be used to expand the image; and code for downscaling the image by successively applying the downscaling filter to a plurality of pixel values formed by (i) pixels in the image and (ii) a combination of pixels in the determined subset weighted using a contribution parameter associated with the downscaling factor and a current iteration in the successive application of the downscaling filter.
17. 17. A computer readable storage medium according to claim 15 or 16 wherein the contribution parameter associated with the downscaling factor is a contribution of the last pixel along one dimension in the image, and the contribution parameter is further associated with a current iteration in the successive applications of the downscaling filter.
18. 18. A computer readable storage medium according to claim 15 or 16 wherein for expanding of the image, the program further comprises code for combining pixels in the determined subset, wherein at least some pixels of the determined subset are weighted based on the contribution of the last pixel of the image in the determined subset and the number of pixels in the determined subset, and code for using one accumulation parameter and one contribution parameter for each dimension of the image.
19. 19. A computer readable storage medium according to claim 15 or 16 wherein expansion is performed at a downscaling step where the source number of pixels is odd and the fixed downscaling filter operates according to a power of 2 or by a factor of 2 in each dimension.
20. 20. Computerized apparatus adapted to perform the method of any one of claims 1 to 14.