Abstract:
A method and apparatus for assisting in the rotation of digital images is described. The digital image is divided by a separate process into image blocks which are rotated through a predetermined angle. Data moving hardware then processes the image blocks to determine the proper placement of each block in a frame buffer to create a properly rotated image. A set of predetermined values based on characteristics of the input image and the predetermined output image format is provided to the data moving hardware from a value processor. The data moving hardware performs only additions and subtractions. The only multiplication necessary for the method is performed by the processor prior to placement of the rotated image blocks in an output frame buffer. Thus the rate of processing the rotated image blocks is significantly improved.

Description:
FIELD OF THE INVENTION  
         [0001]    The invention relates generally to a method and apparatus for assisting in the rotation of digital image data. In particular, the invention relates to a method of assisting in the placement of rotated image blocks in an image buffer.  
         BACKGROUND OF THE INVENTION  
         [0002]    Document imaging systems (e.g., copiers and fax machines) often represent an image as digital data for use in the reproduction of the original image. Some document imaging systems include an image processing chip which provides an image block rotation assist function for rotation angles which are integer multiples of 90°. The output of this rotation assist function is a version of the input image which has been divided into individually rotated image blocks. Logic is implemented (in software or hardware) independent of the chip to place the rotated image blocks in a frame buffer to create a properly rotated image therein. The logic can be computationally intensive. The problem is further complicated if the frame buffer is larger than the output image (e.g., when placing multiple rotated images onto a single page).  
           [0003]    Since the output bandwidth of these image processing chips is usually high, output data is typically handled by a hardware data moving device (e.g., a DMA controller). When the output of the image processing chip includes rotated image blocks, the required required block placement creates an additional burden on the data moving device. A processor can used to read each output unit (e.g., byte, word) and properly place it in the frame buffer, however, use of the processor can substantially limit the rate at which image blocks are placed in the frame buffer. Hardware can be designed to determine and place the image blocks in memory, but such hardware is usually required to perform multiplication operations to generate the proper frame buffer address. Multiplication operations require a substantial number of digital logic components in the hardware and limit the rate at which image blocks are transferred into memory.  
         SUMMARY OF THE INVENTION  
         [0004]    The present invention relates to a method and apparatus for proper placement of rotated image blocks in an image memory module which can be implemented in simple data moving hardware. A processor provides a set of information to a hardware data mover before an image is processed, and the data mover performs a simple set of operations quickly and without need for multiplication operations or further processor intervention. The processor performs a set of predetermined calculations to generate the set of information for the data mover. A set of simple operations which are independent of the rotation increment (i.e., 0°, 90°, 180° or 270°) are then performed by the data mover to generate single or multiple images within the image memory module. These operations place the rotated image blocks in the proper location in the memory module. Thus, a single process of reduced complexity can be implemented in hardware which requires no processor intervention.  
           [0005]    In one aspect, the invention features a method for assisting in the rotation of a digital image. A set of precalculated values generated by a value processor is received. Rotated image blocks comprised of sub-blocks from an image processor are also received. A destination address for each sub-block is determined according to the precalculated values and each sub-block is stored at its destination address in an image memory module. The generation of the precalculated values can be based on a predetermined rotation angle, an image block size, horizontal and vertical dimensions of the digital image, and an image memory module dimension. In one embodiment, the precalculated values are generated prior to determining each destination address. In another embodiment, each destination address is determined using only addition and subtraction operations. In yet another embodiment, a digital image is received and the rotated image blocks are generated from the digital image.  
           [0006]    In another aspect, the invention features an apparatus for assisting in the rotation of a digital image. The apparatus includes a rotation assist module electrically coupled to a memory module. The rotation assist module includes a value input for receiving precalculated values and a rotated block input for receiving a plurality of rotated image blocks comprising a plurality of sub-blocks. The memory module stores each sub-block at a corresponding destination address generated by the rotation assist module. In one embodiment, a processor for generation of the precalculated values is electrically coupled to the rotation assist module. In another embodiment, the apparatus includes an input module for receiving the digital image and an image processor for generating and rotating the plurality of image blocks.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]    The foregoing and other objects, features and advantages of the invention will become apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings. The drawings are not necessarily to scale, emphasis instead being placed on illustrating the principles of the present invention.  
         [0008]    [0008]FIG. 1 is a block diagram illustrating the process of rotating an image by rotating image blocks and placing the image blocks in an image buffer.  
         [0009]    [0009]FIG. 2 is a block diagram of a conventional apparatus for rotating an image using rotated image blocks.  
         [0010]    [0010]FIG. 3 is a block diagram of an apparatus for rotating an image using rotated image blocks according to the invention.  
         [0011]    [0011]FIG. 4 is a block diagram of a process for printing a rotated version of a scanned image according to the invention.  
         [0012]    [0012]FIG. 5 is a flowchart of a method for determining the proper placement of rotated image blocks in an image buffer according to the invention.  
         [0013]    [0013]FIGS. 6A through 6C illustrate a 90° clockwise rotation of digital image data according the method of the invention.  
         [0014]    [0014]FIGS. 7A through 7C illustrate the placement of 0° rotated image data in a frame buffer for an example where nine digital images are stored in a memory module.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0015]    [0015]FIG. 1 illustrates a process for transforming a digital image  10  into a rotated digital image  18  (rotated clockwise by 90°). The digital image  10  is divided into a series of image blocks  12  identified as A, B, . . . , L. In this example, each image block  12  includes a 3×3 array of pixels  14  identified as a 1 , a 2 , . . . , c 3 . Pixels a 1 , a 2  and a 3  define a three pixel sub-block  16 . Similarly, pixels b 1 , b 2  and b 3  and pixels c 1 , c 2  and c 3  define a second and third sub-block  16 , respectively. In this example, a monochrome image is assumed, thus each pixel  14  has a single intensity represented by a single bit. In color images, each pixel  14  is typically represented by multiple color values and each color value is represented by a series of binary bits. An image processor individually rotates each image block  12  to generate a blockwise rotated image  10 ′ in a line buffer. The data in the line buffer is then provided as a line by line output to a separate processing unit which rearranges the rotated image blocks  12 ′ into a fully rotated image  18  in an image memory.  
         [0016]    Referring to FIG. 2, a conventional apparatus for rotating a digital image  10  includes an image processor  20 , a block processor module  22  (e.g., a CPU) and a memory module  24  (e.g., a frame buffer). The image processor  20  generates rotated image blocks  12 ′ comprising multiple sub-blocks  16 . Sub-blocks  16  can be defined so that the number of bits in each sub-block  16  is equivalent to a byte. These sub-blocks  16  are processed by the CPU  22  and placed in the memory module  24  at the proper destination address.  
         [0017]    Referring to FIG. 3, a digital image rotation device  30  for rotating a digital image  10  includes an image processor  20 , a memory module  24 , a value processor  26  (e.g., a CPU) and a rotation assist module  28 . The rotation assist module  28  can be a field programmable gate array (FPGA), an ASIC or other data moving hardware. A set of predefined calculations are performed by the value processor  26  to generate a set of precalculated values. These precalculated values are provided to the rotation assist module  28  before the rotated image blocks  12 ′ from the image processor  20  are received. The calculations permit the rotation assist module  28  to perform the same operations regardless of the rotation (0°, 90°, 180° or 270°) and also permit more than one fully rotated image  18  to be placed in the image memory  24 .  
         [0018]    The rotation assist module  28  performs a set of operation quickly because multiplication operations are not required. In one embodiment, no further calculations are required from the value processor  26  after generation of the precalculated values. As a result, simple data moving hardware can be used in the rotation assist module  28 .  
         [0019]    [0019]FIG. 4 shows the digital image rotation device  30  of FIG. 3 configured for printing three fully rotated images  18  (90° clockwise rotation in a 3-up format) of three scanned images in a digital copier  40 . An optical scanner  32  scans an image document  36  which includes a digital image  10  to be reproduced in reduced size in triplicate on an output document  38 . The image processor  20  generates pixel values corresponding to the three reduced images  18 , generates rotated image blocks  12 ′ from these pixel values and provides them to the rotation assist module  28  (e.g., FPGA) for rearrangement. Precalculated values from the CPU  26  are used by the rotation assist module  28  to calculate the destination addresses for all the sub-blocks  16  in each of the fully rotated images  18 . The sub-blocks  16  are placed in memory  24  by the rotation assist module  28  and then printed from memory  24  by the printer  34 .  
         [0020]    Table 1 below indicates the values that the value processor  26  supplies to the rotation assist module  28 . Some of the values are defined by the digital image  10  and the memory module  24 , and others are calculated from these values and provided to the rotation assist module  28  so that no multiplication needs to be performed by the rotation assist module  28 . Two types of rotations are considered. The first case includes rotating a single digital image  10  and placing it in the memory module  24 . The second case (i.e., the N-up case) includes generating multiple small images on a single document. The same operations are implemented in the rotation assist module  28  for both cases. An additional offset must be included for the calculation of Start Address (described below) for the second case.  
                                                         TABLE 1                                   0°   90°   180°   270°                                    Start   0   OHD-1   (IVD*BS*OHD)-1   (IHD-1)*BS*OHD       Add-       ress       Incre-   1   BS*OHD   −1   -BS*OHD       ment       1       Incre-   OHD   OHD   -OHD   -OHD       ment       2       Incre-   BS*OHD   −1   -BS*OHD   1       ment       3                  
 
         [0021]    Block size (BS) is the size of an image block  12  expressed in pixels  14 . All image blocks  12  are square, therefore the block size is equivalent to the length in pixels  14  of either image block dimension. The input image horizontal dimension (IHD) is defined as the width in pixels  14  of the digital image  10  divided by the block size. The input image vertical dimension (IVD) is defined as the height in lines of the digital image  10  divided by the block size. The output buffer horizontal dimension (OHD) is defined as the width in bytes of a frame buffer (not shown) in the memory module  24 .  
         [0022]    Calculated values include the Start Address, Increment1, Increment2 and Increment3. The Start Address is defined as the destination address in the memory module  24  where the first sub-block is to be placed and is commonly offset from the actual hardware address of a frame buffer within the memory module  24 . Increment 1, Increment 2 and Increment 3 are values used by the rotation assist module  28  to adjust the destination address for each sub-block  16 .  
         [0023]    The primary difference between the precalculated values supplied to the rotation assist module  28  for the case of a single rotated image  18  and for the N-up case is the value of Start Address. For the N-up case, an additional value called Start Address Offset is calculated and added to the value of Start Address in order to determine the destination address at where the first sub-block  16  of each rotated image  18  is placed. N-Up Row and N-Up column are parameters used to determine the Start Address Offset. N-Up Row and N-Up column represent which row and column, respectively, of the array of N rotated images  18  in which a particular image  18  will be placed. Additional information required for calculating the Start Address Offset includes the width (NWidth) of the array expressed in rotated images  18  and a unique image number (NImg) that identifies which of the N images is currently relevant. For example, if the memory module  24  is to store twelve images  18  arranged as three images  18  in the horizontal dimension and four images  18  in the vertical dimension, then the value of NWidth is three. NRow and NCol are intermediate values used in calculation of Start Address Offset. NRow and NCol are defined as the row and column of the array of N images  18  in which the current image will be placed.  
         [0024]    The Start Address Offset is calculated as follows:  
           N Row=(the quotient of  NImg  divided by  N Width)+1  
           N Col= NImg −(( N Row−1)* N Width)  
         [0025]    N-Up 0° and 180°:  
         [0026]    Start address Offset=((NRow−1)*OHD*IVD*BS)+(((NCol−1)*IHD*BS)/8)  
         [0027]    N-Up 90° and 270°:  
         [0028]    Start Address Offset=((NRow−1)*OHD*IHD*BS)+(((NCol−1)*IVD*BS)/8)  
         [0029]    The operations implemented in the rotation assist module  28  are the same regardless of the rotation angle or the number N of rotated images  18  to be stored in the memory module  24 . Referring to FIG. 5, these operations are depicted in a flowchart  50  comprising a nested loop of steps to generate the destination address of each sub-block  16 . Inner loop  52  is executed each time a sub-block  16  is written to the memory module  24 . Middle loop  54  is executed for each rotated block  12 ′ provided from the image processor  20 . Outer loop  56  is executed once for each image  18  to be stored in the memory module  24 .  
         [0030]    Referring to FIGS. 6A to  6 C as an illustrative example of the rotation assist feature implemented for a 90° clockwise rotation, a 32 pixel by 16 line image  10  is divided into square image blocks  12 . Each image block  12  is defined by an array of 8×8 single bit pixels. Each image block  12  includes eight sub-blocks  16  and each sub-block  16  includes eight bits  14 . The first sub-block  16  of the first image block  12  includes bits  0 ,  32 ,  64  , . . . ,  224  from the first column and the eighth (last) sub-block  16  of the first image block  12  includes bits  7 ,  39 ,  71 , . . . ,  231  from the last column. FIG. 6B illustrates the rotation of the individual image blocks  12  to generate a blockwise rotated image  10 ′. Each sub-block  16   a ,  16   b ,  16   c  in the original image  10  is arranged horizontally. In FIG. 6C, data moving operations performed by the rotation assist module  28  generate a fully rotated image  18  in the memory module.  
         [0031]    Referring to FIG. 7A for another illustrative example, an input document  36  having a digital image  10  is processed to generate an output document  38  having nine reduced size fully rotated images  18  arranged in three rows and three columns. In this example the rotation angle is 0°, the image blocks are 8×8 single bit pixel arrays, the sub-blocks are 8 pixels long (one byte) and the image  10  to be rotated is 24 pixels×16 lines. Referring to FIG. 7B, each box  62   a ,  62   b ,  62   c  represents one output byte. The first number in each box  62   a ,  62   b ,  62   c  is the offset from the start of the output frame buffer in the memory module  24 . The second number in each box  62   a ,  62   b ,  62   c  is the order in which the sub-blocks  16  are provided from the image processor  20 . The second number returns to one at the start of each new output image  18  from the image processor  20 . The larger boxes  64   a ,  64   b ,  64   c  indicate the separation of the individual images  18  within the frame buffer.  
         [0032]    In this example the start address for the eighth image would be calculated as follows:  
         [0033]    Block Size=8  
         [0034]    Input Image Horizontal Dimension=24/8=3  
         [0035]    Input Image Vertical Dimension=16/8=2  
         [0036]    Output Frame Horizontal Dimension=9 bytes  
         [0037]    N-up width in images=3  
         [0038]    N-up image number=8  
         [0039]    N-up Row=(quotient of (NImg/NWidth))+1=(quotient of (8/3))+1=2+1= 3  
         [0040]    N-up Column=NImg−((NRow−1)*NWidth)=8−((3−1)*3)=8−(2*3)=8−6=2  
         [0041]    Start Address Offset=((NRow−1)*OHD*IVD*BS)+(((NCol−1)*IHD*BS)/8)=((3−1)*9*2*8)+(((2−1)*3*8)/8)=291  
         [0042]    Equivalents  
         [0043]    While the invention has been particularly shown and described with reference to specific embodiments, it should be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.