Abstract:
Digital image data of high resolution are obtained by synthesizing the scanning signals of two scanners, which scan an original document with mutually different lower resolutions. The synthesis includes transforming the scan signals of the first scanner into a first spectrum and transforming the scan signals of the second scanner into a second spectrum, superposing in predetermined manner versions of the first and second spectrum shifted over the spectral axis, and deriving a third spectrum from the result thereof. Retransformation of the third spectrum produces digital image data with a high resolution.

Description:
BACKGROUND OF THE INVENTION 
     1. Technical Field of the Invention 
     The invention relates to a method and apparatus for generating digital image data. More particularly, this invention relates to digital image generation with, for example, a digital copying machine or a free-standing scanner apparatus. 
     In apparatus of this kind, a document having an image thereon is scanned with an electro-optical converter to generate digital image data which contain a grey value for each image element or pixel. This is usually done with a CCD array, on which a part of the document in the form of a line is projected by an optical imaging system. By moving either the document or the imaging system in a direction perpendicular to the scanning line of the document, the document is scanned completely, line-by-line, in accordance with a usually rectangular raster of pixels. 
     The spatial density or resolution of the pixels is, in practice, on the order of some hundreds of pixels per inch, usually specified as “dpi” (dots per inch). 
     2. Description of Related Art 
     Digital image data of the kind described above can be processed in the spatial domain, but it has also been proposed to process such data in the frequency domain. The latter domain is for instance particularly suited for filtering operations, in which disturbing elements, which often have frequencies outside the range of those of the image information, can be removed easily from the digitised image. 
     In this connection, also the combined use of image data generated from one image by two scanners each having a resolution different from the other, is proposed. 
     For instance, U.S. Pat. No. 5,121,445 describes a method aimed at removing moiré patterns. Patterns of this kind occur when a rastered image is scanned with a scanner, due to the fact that the raster frequency of the image interferes with the scanning frequency (resolution) of the scanner. The interference causes frequency domain sidebands on either side of the spectrum of the original non-rastered image. Also, the entire spectrum, including the sidebands, is periodically repeated as a result of the discrete scanning by the scanner. These sidebands contain information on both the rastering and the scanning. The known method comprises eliminating the side bands as far as possible by comparing the spectra of the image data from the two scanners, so that the original non-rastered image can be reconstructed. Thus, this method not only removes the moiré but also the raster. Effectively, therefore, information present in the scanned image is destroyed. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to retain as far as possible all the information in the scanned image. Another object is to increase the dpi of a scanned image. 
     For a good description of an image it is of course desirable that pixels should have a high spatial density. However, high-resolution systems are expensive, both because of the requirements relating to the CCD array and the requirements relating to the optical imaging system. Therefore, there is a demand for a scanner system which generates image data at high resolution and yet is constructed from simple and hence inexpensive components. The present invention meets this demand. 
     To this end, the method according to the invention includes the following steps: 
     1) generating first digital image data by scanning the image with a scanner having a first resolution f 1 ; 
     2) generating second digital image data by scanning the image with a second scanner having a second resolution f 2  higher than f 1 ; and 
     3) combining the first and second digital image data to form third digital image data, which describes the image with a third resolution f 3  which is higher than f 1  and higher than f 2 . 
     According to one embodiment, step 3) includes the following sub-steps: 
     a) transforming the first digital image data into a first spectrum, and transforming the second digital image data into a second spectrum, which spectra have an amplitude on a spectral axis; 
     b) superposing in a predetermined manner versions of the first and second spectrum shifted over the spectral axis, to give a first combination; 
     c) deriving a third spectrum from the first combination; and 
     d) re-transforming the third spectrum, the result being interpreted as the third digital image data. 
     The invention is based on combining the image data of two scanners, each of which has a relatively low resolution different from the other, to give image data of a higher resolution. This combination is possible in the frequency domain. The digital image data are therefore first transformed thereto with a Fourier transform, whereafter they are processed further. Alternatively, it is possible to subject the image data to a cosine transform and carry out the combination in the cosine domain. 
     These resolutions are preferably selected such that 
     
       
           f 3= f 1+ f 2− G ( f 1,  f 2) 
       
     
     where G(a,b) is the highest common divisor of a and b. On the basis of theoretical considerations, this value of f 3  is the highest frequency at which the results of the method still form a reliable estimate of the original image, i.e., still correspond to the original image, if the latter were scanned at the resolution f 3 . There is, therefore, no point in making f 3  higher, because it does not yield any more information. On the other hand, it is also undesirable to make f 3  lower, because then the information present in the image data is not used to maximum effect. 
     As a marginal condition for the values of f 1  and f 2 , their ratio must be a rational ratio because it is only in that case that the theory on which the processing of the digital image data from the scanner is valid. However, this does not form any limitation, because this is always the case as a result of the discrete form of the scanners. 
     Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention will become more fully understood from the detailed description given hereinbelow and the accompanying drawings which are given by way of illustration only, and thus are not limitative of the present invention, and wherein: 
     FIG. 1 is a diagram showing the principle of the scanner apparatus according to the invention; 
     FIG. 2 is a block schematic of the apparatus according to the invention; 
     FIG. 3A is a simplified spectrum of an original image; 
     FIG. 3B is a spectrum of a scan signal of an image; 
     FIG. 4 is a diagrammatic representation of the process of reconstructing a high-resolution signal from the two lower-resolution scan signals in accordance with the invention; and 
     FIGS. 5A-F are a visualisation of the operations on the spectra during the reconstruction. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     FIG. 1 is a sketch showing the principle of a scanner according to the invention. An original document  1  is transported in a direction  2  at a uniform speed. A lens  3  images the document on two CCD arrays  4  and  5 , each which scan a separate line area, perpendicular to the direction of transport  2 , of the document. Signals are generated by each of the CCD arrays  4 , 5  in accordance with the grey values of image parts or pixels. These signals are converted to digital image data by means of A/D converters. Since the document is transported along the imaging system, the entire document is scanned line-by-line. 
     Generally, a combination of a CCD array and a lens is also termed a “camera”. The scanner device of FIG. 1 thus comprises two cameras. 
     Array  4  scans the document with a resolution f 1  and array  5  does so with a resolution f 2 , which is different from f 1 . This can be effected by using CCD arrays having different CCD densities. Alternatively, different resolutions can be achieved by making the imaging system (the lens) different for each of the arrays, so that one array scans the document with a different enlargement from the other. 
     Instead of the lens in FIG. 1, it is also possible to use a selfoc lens array (an array of imaging optical fibres). 
     It is also possible to scan the document twice with different magnification, using one camera having variable magnification, and to store the signals of the two scans in a memory. The signals with different resolution are then not generated simultaneously, but can be delivered in synchronism by reading out of the memory simultaneously or semi-simultaneously the signals corresponding to the same line position. 
     FIG. 2 is a block schematic of the apparatus according to the invention in the embodiment of FIG.  1 . The CCD arrays  4  and  5  are each connected to an A/D converter  11 ,  12  respectively, to convert their respective analog signals into digital image data. The A/D converter  11  is connected to the delay device  13  for synchronising the image data, so that the image data delivered in the two channels relate to the same linear area on the scanned document. The delay device  13  is connected to a DFT module  14  and the A/D converter  12  is connected to a DFT module  15 . A DFT module performs a discrete Fourier transformation on the image data. 
     The DFT modules  14 , 15  are each connected to a synthesis module  16 . This is intended to combine the transformed image data from the two channels into transformed image data having a higher resolution f 3  in the frequency domain. The operation of the synthesis module will be described hereinafter. 
     The synthesis module  16  is in turn connected to an inverse DFT module  17  for transforming the data from the synthesis module into digital image data having the higher resolution f 3 . 
     The apparatus described here can be constructed as an independent scanner device for scanning documents. Such a construction generates digital image data, which are then delivered via an electrical connection to, for example, a workstation or computer. The apparatus can also form part of a digital copying apparatus, in which the scanner signals are converted to control signals for a printing apparatus, whereby the latter prints a copy of the document on an image support, such as a sheet of paper. The structural elements required for the construction as shown in FIG. 1, although not described above, are generally known to one of ordinary skill in the art. 
     Before discussing the procedure for processing two image signals of spatial frequencies f 1  and f 2  respectively, to form an image signal of spatial frequency f 3 , reference will first be made to FIGS. 3A and B, which show the effect of scanning on the image signal. 
     The basis utilized in the following will be an original image, the spatial progress of the image information of which will be designated the “original signal h”. The spectrum of “h” will be designated “H”. 
     FIG. 3A shows a (simplified) spectrum (H)  21  of the original image (h). When this image is scanned with a spatial frequency fa, a scan signal is generated with a spectrum as shown in FIG.  3 B. This spectrum contains the original spectrum  21  and periodic repetitions  22  of this spectrum at multiples of the scanning frequency fa. When the scanning frequency fa is sufficiently high compared with the extent of the original spectrum, the original image signal can be recovered faultlessly from the spectrum of the scanning signal. If the bandwidth of h is greater than fa/2, then the periodic repetitions of the original spectrum will overlap one another and distortion will occur so that the original image signal h can no longer be recovered faultlessly. This is known as the Nyquist theorem in signal theory. 
     The spectrum H a  of an original signal h scanned at a frequency fa can now be described as:          H   a     =       ∑     k   =     -   ∞       ∞            T   kfa        H                              
     wherein 
     H is the spectrum of h and 
     T s  is a shift operator defined as: (T s f) (t)=f(t−s), where f is any function. 
     This formula is the mathematical representation of what is shown in FIG.  3 B. 
     The process of reconstruction of an approximation of the original signal h from the two scanning signals or, more generally, of the processing of two image signals of frequencies f 1  and f 2  respectively, to form an image signal of frequency f 3 , is shown in FIG.  4 . 
     The reconstruction progresses in four steps. In the first step, the spectra of the scanning signals are calculated by utilizing a Fourier transform. In the second step, a superposition of the spectra of the scanning signals is calculated. In the third step, the result of the superposition is unravelled so that (by approximation) the spectrum H of the original signal remains. The (approximated) original signal is derived from this in the fourth step by inverse Fourier transformation, so that it would appear as if scanning was carried out at the increased frequency f 3 . 
     This procedure will now be explained by reference to a numerical example. The general case will be discussed hereinafter. 
     Two scanning frequencies f 1 =200 dpi and f 2 =300 dpi are used for this example. 
     The various steps of the process as described with reference to FIG. 4 will now be described in greater detail. 
     First Step 
     FIG. 5A shows the spectrum H of an original image h obtained by subjecting the latter to a Fourier transform. FIGS. 5B and 5C respectively show the spectra H 1  and H 2  respectively of the two scanning signals associated with the scanning frequencies f 1  and f 2  respectively. It will be clear that these spectra are not suitable for reconstructing the original signal h faultlessly therefrom, due to the overlapping of the periodic repetitions. 
     Second Step 
     For the purpose of explanation, an auxiliary frequency fx will first be introduced, which is defined as: 
     
       
           fx=K ( f 1,  f 2), 
       
     
     where K denotes the lowest common multiple. 
     In the example, therefore, fx=600 dpi. 
     The following superposition s is selected for the example described: 
     
       
         
           s=T 
           −100 
           H 
           1 
           −H 
           2 
         
       
     
     This choice is based on the following considerations. Assuming that the original signal h was scanned at a frequency fx, i.e. 600 dpi, then the spectrum of the scanning signal was:          H   x     =       ∑   k            T     600                 k          H                              
     It will readily be seen that 
     
       
           H   1 =(1 +T   200   +T   400 ) H   x   
       
     
     
       
           H   2 =(1 +T   300 ) H   x   
       
     
     In order to avoid overlapping as much as possible, there is selected for the superposition a combination in which the shift differences are kept as small as possible. A good choice, therefore, is the above-mentioned combination, because in that case: 
     
       
           T   −100   H   1   −H   2 =( T   −100 −1 +T   100 ) H   x   
       
     
     One period is now cut out of the result s of the superposition by setting equal to zero all the spectra values outside (−fx/2, fx/2), in this example. (−300, 300). The result of this is shown in FIG.  5 D. 
     When the bandwidth of the original signal h is less than 200 dpi, generally (f1+f2−G(f1, f2))/2, where G denotes the largest common divisor, this equation also applies when H x  is replaced by H, because then there is no overlapping of spectra. In the case of larger bandwidths, the resulting signal is distorted. 
     Third Step 
     The resulting spectrum is then unravelled by again subjecting it to a combined shift operator. A good choice for this shift operator is, in this example: 
     
       
         ( T   −200   +T   −100   −T   100   −T   200 ) 
       
     
     The result of this unravelling is shown in FIG.  5 E. 
     A cut-out is made from this spectrum between (−fx, 0), in this example (−600, 0), whereafter a last translation T fx/2 , in this example T 300 , delivers an approximated spectrum H′ of the original signal h. This is shown in FIG.  5 F. 
     Fourth Step 
     An estimate of the original signal h can then be calculated from the spectrum H′ using an inverse Fourier transform. To have the signal available at the required frequency f 3  after transformation, the spectrum H′ is first periodically repeated with period f 3  by using the operator.          ∑     k   =     -   ∞       ∞          T   kf3                            
     and then subjected to inverse Fourier transformation. 
     In practice, this step is carried out in one operation by using a discrete inverse Fourier transform with the correct period. 
     The process has been explained as an example hereinbefore for the case of f1=200 dpi, f2=300 dpi. 
     The process will now be described in general form hereinafter. 
     The scanning frequencies should be so selected that f1/f2 is a rational ratio (this is always the case in practice due to the construction of the scanner with discrete CCD arrays). There are then natural numbers a and b, for which: 
     
       
           f 1= G ( f 1,  f 2)· a   
       
     
     
       
           f 2= G ( f 1,  f   2)·   b   
       
     
     
       
           fx=b·f 1 =a·f 2 
       
     
     where G(f 1 , f 2 ) is the largest common divisor of f 1  and f 2 . 
     First Step 
     The first step comprises Fourier transformation of the signals obtained by scanning with scanning frequency f 1  and f 2  respectively, and is of course the same as the first step described above in the exemplified process. 
     Second Step 
     The invention then defines an operator S=T G(f1, f2)  and operators P a  and P b , for which: 
     
       
           P   a =(1 +S   a   +S   2a   + . . . +S   (b−1)a ) 
       
     
     
       
           P   b =(1 +S   b   +S   2b   + . . . +S   (a−1)b ) 
       
     
     then: 
     
       
         
           H 
           1 
           =P 
           a 
           H 
           3 
         
       
     
     
       
         
           H 
           2 
           =P 
           b 
           H 
           3 
         
       
     
     There are now operators A and B, for which: 
     
       
           A·P   a   +B·P   b   =G ( P   a   , P   b ) 
       
     
     G(P a , P b ) is the largest common divisor of the operators P a  and P b , contained as polynomials in S. 
     A, B and G(P a , P b ) can be found by using the Euclidean algorithm known in mathematics. In the above exemplified case, this would give: 
     
       
           G ( P   a   ,P   b )=1 −S   1   +S   3   −S   4   +S   5   −S   7   +S   8   
       
     
     
       
         
           A=−S 
           1 
         
       
     
       B =1 +S   3   
     The following is now taken as superposition s (again for the general case): 
     
       
           s=S   −(a−1)(b−2)/2 ( A·H   1   +B·H   2 ) 
       
     
     One period is now cut out of the result s of the superposition by making all the spectrum values outside (−fx/2, fx/2) equal to zero. 
     If the bandwidth of the original signal h is limited within the value (f1+f2−G(f1,f2))/2, then the following also applies: 
     
       
           s+S   −(a−1)(b−1)/2   G ( P   a   ,P   b )· H   
       
     
     Third Step 
     The resulting spectrum is then unravelled by subjecting it to the following operator: 
     
       
           S   (1−a−b)/2 (1 −S   1 )(1 +S   1   + . . . +S   a−1 )(1 +S   1   + . . . +S   b−1 ) 
       
     
     From this spectrum a cut-out is made between (−fx,0), whereafter a last translation T fx/2  gives an approximated spectrum H′ of the original signal h. 
     If the bandwidth of the original signal h is limited within the value (f1+f2−G(f1,f2))/2, then the unravelling yields: 
     
       
           H ′=( S   −fx/2   −S   fx/2 ) H   
       
     
     so that H and h are exactly reconstructed. 
     Fourth Step 
     This is again the same as the fourth step described above. This completes the reconstruction. 
     By applying the above techniques it is possible, using two cameras having relatively low resolutions f 1  and f 2  which differ from one another, to construct a scanner device which can deliver digital image signals having a relatively high frequency f 3 . The latter image signals are then synthesised from the signals of the two cameras using the above-described method. 
     It should be noted that the synthesised signal has a frequency content defined by f3=(f1+f2−G(f1,f2)). Selecting a value for f 3  higher than (f1+f2−G(f1,f2)) does not yield a sharper image than that for the value mentioned here. 
     In the example, the (discrete) Fourier transform was utilised. However, other orthogonal transformations, such as, for example, (discrete) cosine transform may be utilised by the invention. The method is not changed as a result, although the operators used may differ. It is within the scope of the skilled man to adapt the operators for other transformations, the person of ordinary skill in the art, in this case, having a wide knowledge of both signal theory and mathematics. 
     The scan signals can also be generated with two-dimensional CCD arrays of different resolutions, or one or two identical two-dimensional arrays with different magnification optics. The image signals can be synthesised, similarly to the above-described method, by a suitable adaptation of the data processing, either by splitting the two-dimensional algorithm into one-dimensional operations, or by adapting the theory for the two-dimensional case. 
     The invention being thus described, it will be obvious that the same may be varied in many ways. Such variations are not to be regarded as departure from the spirit and scope of the invention, and all such modifications as would as would be obvious to one skilled in the art are intended to be included within the scope of the following claims.