Abstract:
An improved error-diffusion image processing system and the method thereof adopt the block reading mechanism to replace the row reading mechanism employed in the conventional error-diffusion image processing. This can greatly reduce the memory space required for image processing and increase the operational efficiency. The problem of gaps existing in the block reading mechanism is solved by adding a required error sum (BEsum) in a summed pixel range according to specific position conditions of each block.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of Invention  
         [0002]     The invention relates to an image processing system and the method of the same. In particular, the invention relates to an error-diffusion image processing method that employs block reading to convert a multi-level image to a bi-level image for output and the method thereof.  
         [0003]     2. Related Art  
         [0004]     The multi-level image generally refers to a digital image created by a digital camera, scanner, or computer software. In a monochrome image, each pixel consists of at least two different levels of gray. In a color image, there are many different color planes. Each pixel consists of at least two different levels in each color plane.  
         [0005]     Either monochrome or color images are usually output via a printer or a display device. However, these output devices often describe these multi-level images in a bi-level way. For example, a monochrome image can only be described using black-level and white-level. For a color image, each color plane is described using on-level and off-level. Therefore, before a multi-level image is sent to these output devices for output, it has to be converted into a bi-level image first.  
         [0006]     Such a process of converting a multi-level image into a bi-level image is also called halftoning. The error-diffusion image processing is a widely used conventional halftoning technique. However, the conventional error-diffusion image processing is performed by row reading. That is, the operation is not performed until a whole row of image data are read in. Therefore, it takes a lot of memory space to store the image data. The operation efficiency is also lowered because of the frequent access of data in the memory.  
         [0007]     Since the cost of memory is not cheap and the memory space available in the output devices is limited, the conventional error-diffusion image processing method for converting multi-level images to bi-level images indeed faces the problems of memory space usage and the operation efficiency. Therefore, it is necessary to provide an improved solution to solve these problems.  
       SUMMARY OF THE INVENTION  
       [0008]     In view of the foregoing, the invention provides an improved error-diffusion image processing system and the method thereof. A primary objective of the invention is to adopt a blocking reading scheme in place of the row reading scheme in the prior art for the purpose of saving memory space and increasing the operational efficiency.  
         [0009]     To implement the objective, the primary technique of the invention is to solve the gap problem caused by block reading in the error-diffusion image processing technique. Hence, good image output quality of the multi-level image still remains when converted into a bi-level image.  
         [0010]     The improved error-diffusion image processing system includes: (a) an image partition unit; (b) an operation block processing unit; (c) a summed pixel processing unit; (d) an error-diffusion image processing unit; and (e) a storage unit.  
         [0011]     The improved error-diffusion image processing method executes the following operational steps via the above-mentioned system: (a) dividing a multi-level image into more than one block, each block having a position condition (i, j) and containing more than one pixel; (b) reading in sequence blocks for processing and determining an operation block range according to the position condition (i, j), thus computing the summed error of the block (BEsum); (c) determining the summed pixel range according to the position condition (i, j) of the block, adding the summed error to the summed pixel range; and (d) executing an error-diffusion calculation for each pixel in the block to determine the bi-level output of each pixel and storing the result, and computing the average error (BE) of the block and storing it. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]     The invention will become more fully understood from the detailed description given hereinbelow illustration only, and thus are not limitative of the present invention, and wherein:  
         [0013]      FIG. 1  is a system block diagram of the invention;  
         [0014]      FIG. 2  is a flowchart of the disclosed method;  
         [0015]      FIG. 3  is a schematic view showing the processing order and position conditions in the invention;  
         [0016]      FIG. 4  shows the relation among the logic rules used in the invention;  
         [0017]      FIGS. 5A  to  5 F are schematic views of the logic rules used in the invention;  
         [0018]      FIGS. 6A and 6B  compare results before and after the operation of the invention; and  
         [0019]      FIGS. 7A and 7B  compare another results before and after the operation of the invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]     A system block diagram of the invention is shown in  FIG. 1 . The invention converts a multi-level image  10  from an external input into a bi-level image  70 . Main functional blocks include:  
         [0021]     (a) an image partition unit  20 . It is used to partition the externally input multi-level image, dividing it into many blocks of the same size. Each of the blocks contains many pixels. Each block in the partition is attributed with a fixed position condition (i,j). For example, if the image partition unit  20  divides the multi-level image into m*n blocks, then the corresponding position conditions of the blocks from left to right along the x axis and from up to down along the y axis are (1,1) to (m,n), as shown in  FIG. 3 .  
         [0022]     (b) an operation block processing unit  30 . It is used to read in blocks from the image partition unit  20  according to a processing order (i.e. from left to right along the x axis and from up to down along the y axis). The operation block processing unit  30  contains logic rules for determining an operation block range and computing the summed error (BEsum) associated with each block. The operation block range for computing the summed error is determined according to the position conditions (i, j) of each block.  
         [0023]     (c) a summed pixel processing unit  40 . It is used to determine logic rules for determining a summed pixel range. It adds the summed error (BEsum) obtained by the operation block processing unit  30  into the summed pixel range associated with the block. The method of determining the summed pixel range is also primarily determined by the position condition (i, j) of each block. Once it is determined, the summed error of the block is added to the summed pixel range.  
         [0024]     (d) an error-diffusion processing unit  40 . It is used to execute an error-diffusion calculation for each pixel in the block to determine the bi-level output associated with pixel and to store the result. Since this part belongs to the scope of the prior art, we do not describe it herein.  
         [0025]     Aside from the error-diffusion processing on each pixel of the block, the error-diffusion processing unit  50  has to be able to compute the average error (BE) of the current block and to store it for the summed error calculation needed in subsequent calculations for other blocks.  
         [0026]     The average error (BE) is computed as follows:  
         [0027]     (the sum of accumulated diffusive errors after the error diffusion calculations of all pixels in the block)/(the sum of all pixels in the block).  
         [0028]     The coimputation rules of the diffusive error are as follows: when the value of a pixel is greater than 128, its diffusive error is (the pixel value—255); and when the value of a pixel is smaller than 128, the pixel value is taken as the diffusive error directly.  
         [0029]     (e) a storage unit  60 . It is used to store the bi-level output result and the average error (BE) produced by the error-diffusio processing unit  50 . In fact, the stroage unit  60  can be used to temporarily store the blocks divided by the image partition unit  50 . Using this method, the operation block processing unit  30  has to read in the needed block data from the storage unit  60 .  
         [0030]     Once all the blocks are processed, the converted bi-level image can be output from the storage unit  60 .  
         [0031]      FIG. 2  shows the actual operational steps in the disclosed method.  
         [0032]     (a) The multi-level image is first partitioned into blocks of the same size. Each block is associated with a fixed position condition (i, j), and each block contains many pixels (step  100 ).  
         [0033]     (b) The blocks are read in according to a predetermined sequence for processing. In this case, the position condition (i, j) is used to determined the required operation block range. Afterwards, the determined operation block range is used to compute the summed error (BEsum) of the current block (step  200 ).  
         [0034]     (c) Likewise, the position condition (i, j) of the block is used to determine the symmed pixel range that the current block should be adjusted. Afterwards, the summed error associated with the block is added to the summed pixel range (step  300 ).  
         [0035]     (d) Finally, the error-diffusion calculation of each pixel in the current block is carried out to determine the bi-level output of each pixel, and the result is stored (this part belongs to the prior art). The average error (BE) of the current block is computed and stored for computing the summed error in subsequent calculations of other blocks (step  400 ).  
         [0036]     Each block has to go through steps  200  to  400  before the procedure is complete. Once a block completes the processing, the method further determines whether there is any other unfinished block (step  500 ). If there is, the method returns to step  200  to read in the next block for processing; otherwise, the method has completed the process of converting a multi-level image into a bi-level image. In this case, the complete bi-level image is output.  
         [0037]     Various logic rules for the operations in the invention are seen in  FIG. 4 , which shows one case of the preferred embodiment. It explains the possible variations of the operation block range and the summed pixel range determined from different block position conditions (i, j) and the calculation rules for the summer error.  
         [0038]     The operational logic rules for positioon conditions and operation block range are as follows:  
         [0039]     When i=1, j=1, the operation block range is the block position (1,1), as shown in  FIG. 5A .  
         [0040]     When i=1, j=2, the operation block range is the block positions (1,1) and (1,2), as shown in  FIG. 5B .  
         [0041]     When i=1, j=3, the operation block range is the block positions (1,1), (1,2), and (1,3), as shown in  FIG. 5C .  
         [0042]     When i=1, j≠1, 2, 3, the operation block range is the block positions (1,1), (1,2), and (1,3), as shown in  FIG. 5D .  
         [0043]     When i≠1, j=1, the operation block range is the block postions (i−1, j), (i-1, j+1), and (i-1, j+2), as shown in  FIG. 5E .  
         [0044]     The computation rules for the summed error (BEsum) are as follows:  
         [0045]     When i=1, j=1, the summed error (BEsum) is BE(1,1)* 3, as shown in  FIG. 5A .  
         [0046]     When i=1, j=2, the summed error (BEsum) is BE(1,1)+BE(1,2)*2, as shown in  FIG. 5B .  
         [0047]     When i=1, j=3, the summed error (BEsum) is BE(1,1)+BE(1,2)+BE(1,3), as shown in  FIG. 5C .  
         [0048]     When i=1, j≠1, 2, 3, the summed error (BEsum) is A*BE(1,1)+B*BE(1,2)+C*BE(1,3), as shown in  FIG. 5D .  
         [0049]     When i≠1, j=1, the summed error (BEsum) is A*BE(i-1, j)+B*BE(i-1, j+1)+C*BE(i-1, j+2), as shown in  FIG. 5E .  
         [0050]     Here BE is the so-called average error.  
         [0051]     The operation logic rules for the position conditions and the summed pixel range are as follows:  
         [0052]     When i=1, j=1, the summed pixel range is the last four bits, as shown in  FIG. 5A .  
         [0053]     When i=1, j=2, the summed pixel range is the first four bits and the last four bits, as shown in  FIG. 5B .  
         [0054]     When i=1, j=3, the summed pixel range is the first four bits and the last four bits, as shown in  FIG. 5C .  
         [0055]     When i=1, j≠1, 2, 3, the summed pixel range is the first four bits and the last four bits, as shown in  FIG. 5D .  
         [0056]     When i≠1, j=1, the summed pixel range is the last four bits, as shown in  FIG. 5E .  
         [0057]     In the above-mentioned operation logic rules, we provide the processing rules for special blocks belonging to the first column, the first row, and the first three blocks of the first row, etc.  
         [0058]     For other blocks with non-special position conditions (when i≠1, j≠1, 2, 3), we have the following processing rules.  
         [0059]     In this case, the operation block range with these position condictions has two parts ( FIG. 5F ):  
         [0060]     (a1) block positions (i-1, j−1), (i-1,j), and (i-1, j+1), and  
         [0061]     (b1)block positions (i-1,j), (i-1, j+1), and (i-1, j+2).  
         [0062]     Therefore, the summed error (BEsum) is computed according to different operation blocks as follows:  
         [0063]     (a2) A*BE(i-1, j−1)+B*BE(i-1, j)+C*BE(i-1, j+1); and  
         [0064]     (b2)A*BE(i-1, j)+B*BE(i-1, j+1)+C*BE(i-1, j+2).  
         [0065]     Here A, B, and C are weight values (in this embodiment, A is 1/55, B is 1/85, and C is 1/95, but they can be modified appropriately according to practical needs). 
        The summed pixel range corresponding to the block also contains two parts:        
 
         [0067]     (a3) the first four bits; and  
         [0068]     (b3) the last four bits.  
         [0069]     One learns from here that for a block with normal position conditions, there are two different operation block ranges, thus generating two different summed errors and different summed pixel ranges. (That is, the operation block range of a1 is used to compute the summed error of a2 and added to the summed pixel range of a3. The operation block range of b1 is used to compute the summed error of b2 and added to the summed pixel range of b3.)  
         [0070]     The above-mentioned “the first four bits” refers to the first foru pixels in each row of the block, and “the last four bits” refers to the last four pixels in each row of the block.  
         [0071]     The disclosed system and method of operations indeed can replace the row reading method in the conventional error-diffusion image processing with blocking reading in order to save memory space and to increase operation efficiency. Moreover, the invention solves the gap problem existing in the block reading scheme.  
         [0072]     Please refer to  FIGS. 6A and 7A . It is seen in the drawings that if one simply employs the block processing scheme to perform improved operations on the image, there are many gaps  600  in the output bi-level image, deteriorating the output digital image quality. On the other hand, in  FIGS. 6B and 7B , the invention further uses the proposed technique to process the image. Obviously, the gaps  600  disappear and the invention achieves the complete conversion of a multi-level image to a bi-level image.  
         [0073]     Certain variations would be apparent to those skilled in the art, which variations are considered within the spirit and scope of the claimed invention.