Abstract:
A method for three decision mode selection of a thresholding algorithm is disclosed as is a thresholding mode switch having a three decision mode determining capability that is particularly useful for facsimile-copier devices in making printed copies of mixed format documents. The thresholding mode switch uses a reflectance difference algorithm for switching between a gray-scale thresholding algorithm and black-white thresholding algorithm to enhance the quality of prints made of mixed format documents presented for copying. A gradient constant is established for each picture element (pel) of the document then presented for copying and a determination is made at the thresholding mode switch as to which range, of three predetermined ranges, the gradient constant falls within, with this determination being then used to control the thresholding algorithm utilized in making that portion of the copy relating to that particular pel then being copied.

Description:
RELATED APPLICATION 
     This application is a continuation-in-part of my copending United States Application, Ser. No. 939,542, filed Sept. 5, 1978. 
    
    
     This invention relates to a thresholding mode switch and method for mode selection, and, more particularly, relates to a three decision thresholding mode switch and method for mode selection to control copying of mixed format documents. 
     BACKGROUND OF THE INVENTION 
     Devices and methods for copying of documents are well known in the prior art. Included in such prior art are devices and methods for enhancing the optical recognition of characters in documents being copied, and such character recognition devices have commonly included threshold circuitry. Such devices and method are shown, for example, in U.S. Pat. Nos. 3,479,642, 3,534,334 and 3,737,855. 
     It is also well known in the prior art to provide switching between different modes in a facsimile system, and this is shown, for example, in U.S. Pat. Nos. 3,294,896, 3,622,698 and 3,723,649. 
     In connection with facsimile systems, it has also been heretofore suggested that switching can be accomplished between two conditions depending upon whether the portions of a particular document then being copied consists of half-tones or black-and-white matter. A two condition thresholding arrangement is shown, for example, in U.S. Pat. No. 2,255,408, with circuitry being disclosed for switching between line copy and continuous tone detection algorithms based upon the rate of change of reflectance from the portion of the document then being copied. It is also suggested in U.S. Pat. No. 2,255,408 that unnecessary switching can be avoided by averaging the area over which the gradient change is selected. 
     A multiple threshold detector system having three range decision circuitry is also shown in the prior art (see, for example, U.S. Pat. No. 3,723,649), but the circuitry such as shown in U.S. Pat. No. 3,723,649 necessarily includes hysteresis that is operative in the decision logic to provide a change in the binary signal level indicative of a threshold level opposite to that establishing the then existing binary level to accomplish the stated end. 
     Thus, while the prior art shows thresholding mode switching circuits and methods for mode selection, the circuits and methods described are either capable of switching only between two conditions or necessarily require the use of hysteresis where more than two decisions are required. 
     SUMMARY OF THE INVENTION 
     This invention provides an improved thresholding mode switch and method for mode selection having three decision thresholding determining capability without requiring the use of hysteresis, with gradient constants being established for use in determining the thresholding mode to be utilized for each picture element to be copied. A gradient constant is established for each pel of the documents being copied and the value of the gradient constant, with respect to three established ranges, determines the thresholding algorithm used for controlling printing of that portion of copies relating to that particular pel. 
     An object of the present invention is to provide an improved thresholding mode switch. 
     Another object of the present invention is to provide an improved thresholding mode switch for use in making printed copies of mixed format documents. 
     Another object of the present invention is to provide an improved thresholding mode switch having a three decision threshold determining capability. 
     Another object of the present invention is to provide an improved thresholding mode switch having a three decision thresholding determining capability for use in making high quality prints of mixed format documents. 
     Another object of the present invention is to provide a three decision thresholding mode switch for use in a facsimile-copier to enhance the quality of printed copies of mixed format documents. 
     Another object of the present invention is to provide an improved method for determining the optimum mode for copying of mixed format documents. 
     Still another object of the present invention is to provide an improved method for determining the optimum mode for copying of mixed format documents utilizing three decision determination. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above-mentioned and other features and objects of this invention and the manner of attaining them will become more apparent and the invention itself will best be understood by reference to the following description of embodiments of the invention taken in conjunction with the accompanying drawings, the description of which follows. 
     FIG. 1 is a block diagram illustrating data flow for copying mixed format documents utilizing the thresholding mode switch of this invention. 
     FIG. 2 is a block diagram illustrating a particular thresholding mode switch that can be utilized as the thresholding mode switch shown in the block diagram of FIG. 1. 
     FIG. 3 is a block diagram illustrating an alternate embodiment of the invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The thresholding mode switch 7 of this invention is shown in FIG. 1 included in a data flow chart (such as in a facsimile-copier) to illustrate use of the switch to determine and control the mode for printing of copies of mixed format documents. 
     As indicated in FIG. 1, a mixed format document 9 is scanned by scanner 11. Document 9 may, for example, include portions having continuous tone, gray-scale, and line copy. With respect to such documents, while much effort has heretofore been expended to optimize a gray-scale algorithm to achieve high quality copying of continuous tone, previously gray scaled, and line copy documents, an algorithm achieving quality copying of any one format has heretofore resulted in a poor copy of the other two formats. This is due, at least in part, to the difference in the rate of change of reflectance of continuous tone as compared to line copy. Line copy has sharp gradients of reflectance due to the characters being normally either dark or light, while continuous tones usually transition more slowly from darker to light regions and vice versa and hence have a much lower rate of change of reflectance than does line copy. 
     Scanner 11 is preferably a conventional image dissecting scanning device capable of individually scanning each picture element, or pel, and provides an analog electrical signal output that is converted at conventional analog-to-digital converter 13 to a digital output signal that is indicative of each pel processed by scanner 11. 
     As also indicated in FIG. 1, the digital output signal from analog-to-digital converter 13 is coupled to thresholding mode switch 7, the outputs of which control black-white thresholding algorithm circuitry 15 and gray-scale thresholding algorithm circuitry 17 which determine the mode of copying of information copied from converter 13 carried out for each pel at printer 19 to make copy 21. 
     Black-white thresholding algorithm circuitry 15 and gray-scale thresholding circuitry 17 may be conventional and may be, for example, circuitry such as shown in U.S. Pat. Nos. 3,159,815 or 3,830,967. Such circuitry is not involved in this invention, however, except to the extent that the thresholding mode switch of this invention controls the mode of copying carried out by printer 19, which printer may also be conventional. 
     Mode switch 7 utilizes an algorithm that instantaneously recognizes sharp gradients and treats them differently than areas having more gentle transitions. In accomplishing this end, the individual reflectance differences between adjacent picture elements, or pels, as determined by image-dissecting scanning device 11, are determined and the absolute value of these differences is summed over a predetermined number of pels. This sum is then normalized by dividing by the reflectance of the pel then being thresholded. The normalization may be modified by using some function of the pel or a combination of pels as the divisor. The result of this calculation is a constant, referred to hereinafter as the gradient constant, which indicates the rate of change of reflectance with linear displacement of the scanning point, or pel position. By averaging over a number of pels, noise sensitivity is reduced. 
     If the established gradient constant is large, this indicates that the rate of reflectance change is high, requiring that a black-white thresholding algorithm be used for achieving the best possible, or optimum, copy. If, on the other hand, the gradient constant is very small, this indicates that the area being scanned is essentially of constant reflectance and the thresholding mode being used previously to encounter this small constant is continued. If the gradient constant has an intermediate value, this indicates that slow changes in reflectance are occurring and a suitable gray-scale thresholding algorithm is appropriate for achieving the best possible, or optimum, copy. 
     Expressed mathematically, the switching algorithm is: ##EQU1## where F i  =gradient constant for the ith pel, i.e., the pel being thresholded; 
     R i , R j  +1 and R j  =reflectance of the i, j+1, and j pels, respectively; and 
     a and b=arbitrary constants determined by the optimization of the algorithm to the particular application (the integer constants a and b are normally expected to range between minus two to plus five. The size and position of the window is defined by a and b where b&gt;(-a), a being the number of pels behind i and b being the number of pels ahead of i. 
     If: F i  &gt;K 2 , then the thresholding mode is changed to the black-white thresholding algorithm; 
     K 1  ≦F 1  ≦K 2 , then the thresholding mode is changed to the gray-scale thresholding algorithm; or 
     F i  &lt;K 1 , then no change is made in the thresholding mode 
     where K 1  and K 2  are arbitrary constants determined by optimization of the algorithm to the particular application. 
     The constant K 1  is chosen high enough to prevent gray-scaling of the background of the text, while the constant K 2  is chosen low enough to respond to sharp transitions in non-text but high enough to soften contrasts. If K 1  is increased from optimum, there is quicker recognition of changes in format and an increased likelihood of not recognizing slow changes in continuous formats so as to remain in black-white too long. If K 1  is decreased away from optimum, there is an increased probability of applying a low density gray-scaling algorithm to backgrounds of text. If K 2  is increased away from optimum, there will be fuzziness in the copies of characters and gray-scaling of courser halftone screens. If K 2  is decreased away from optimum, the contrast increases in continuous tones and fine screen halftones. 
     Variations of the above expressed algorithm may include the extension to two dimensions to evaluate the gradient constant, and the use of density rather than reflectance to calculate the constant. Density is not directly available from most scanning devices, but if available can be used by applying the definition of density to the equation. Where utilized the density relationship is D=log 1/R or R=10 -D . 
     A specific implementation of thresholding mode switch circuit 7 is illustrated in FIG. 2, where the circuit operates according to the algorithm above set forth except that the numerator and denominator have been squared as opposed to computing absolute values. The switching algorithm for this specific implementation is expressed mathematically as: ##EQU2## Where F i , R i , R j+1 , R j  and a and b have the same meaning as the above expressed algorithm with the aritrary selection of a and b having been made as one and two, respectively. In other words, in the actual example as shown in FIG. 2, there are two pels ahead of i and one pel behind i. 
     As shown in FIG. 2, the analog data coupled from scanner 11 and converted to digital form in analog-to-digital converter 13, is coupled to four bit registers 25, 26, 27 and 28, which registers also receive an input from master clock 30 (divided by four). Four consecutive data bytes (R 1 , R 2 , R 3  and R 4 ) are loaded into the registers 25-28 from converter 13. Each byte is cascaded through the registers as each new data byte is shifted into the circuit. 
     As shown in FIG. 2, register 25 is directly connected with adder 32, register 26 is connected with adder 32 through inverter 33 and is directly connected with adder 35, register 27 is connected with adder 35 through inverter 36 and is directly connected with adder 38, and register 28 is connected with adder 38 through inverter 39. As shown, the data (R 1 , R 2 , R 3  and R 4  in registers 28, 27, 26, and 25, respectively) is transferred to the adders where the quantities R j+1  -R j  are calculated. 
     Adders 32, 35, and 38 are connected with multiplexer 42 which receives the difference outputs R 2  -R 1 , R 3  -R 2 , and R 4  -R 3  from the adders, 38, 35, and 32, respectively. Multiplexer 42 (which is connected with counter 44, which counter is also connected with master clock 30) provides an output to read only memory (ROM) 46 so that the quantities calculated at the adder are channeled through ROM 46. ROM 46 returns the square of the difference (R j+1  -R j ) 2  using a table-look-up scheme. This scheme is one in which the input to the ROMs is an address corresponding to a particular value stored in the ROM, i.e., if the input is a 6 (i.e., storage position 6) the output from ROM 46 would be the value 36 or 6 2 . This scheme is faster in this case than the circuitry required for calculation of squares. These squared differences are then transferred to registers 48, 49 and 50, each of which registers is connected with ring counter 52, and then summed in adders 54 and 55 with the sum ##EQU3## being carried to digital comparators 58 and 59, (i=3, i-a=3-2=1, and i+b=3+1=4 for the specific embodiment shown in FIG. 2). As shown, the outputs of register 48 (R 4  - R 3 ) 2  and register 49 (R 3  -R 2 ) 2  are coupled to adder 54 while the result thereof and the output of register 50 (R 2  -R 1 ) 2  are coupled to adder 55. 
     The second input to comparator 58 and 59 is coupled thereto from multipliers 61 and 62 with multiplier 61 receiving a K 1  input from register 64 and multiplier 62 receiving a K 2  input from register 65. The R 3   2  input is coupled from register 26 through multiplier 66 to multipliers 61 and 62. The values K 1  ×R 3   2  and K 2  ×R 3   2  are calculated in multipliers 61 and 62, respectively, and coupled to comparators 59 and 58, respectively. 
     The logic states of the outputs of comparators 58 and 59 establish the three decision states according to the following table: 
     
         ______________________________________                    Compara-                    ator                    Output              State LevelCondition            No.     58      59______________________________________ ##STR1##            1       0       0 ##STR2##            2       0       1 ##STR3##            3       1       1______________________________________ 
    
     These logic states are interpreted into switching signals for the black-white and gray-scale thresholding circuitry by logic gates 70, 71 and 72 (gates 70 and 72 being AND gates and gate 71 being an OR gate), and by the inverters 75 and 76. State 1 results in the output of AND gate 72 remaining at its previous level and thereby maintaining the previous threshold mode. State 2 results in the output of AND gate 72 being 1 thereby employing gray-scale thresholding. State 3 results in AND gate 72 being 0 thereby employing black-white thresholding, the output being coupled through inverter 74. 
     An alternate embodiment of the thresholding mode switch of this invention is shown in FIG. 3 to include three comparators 58, 59, and 80. As shown, comparators 58 and 59 receive inputs from adder 55 and multipliers 61 and 62 in the same manner as described in connection with the FIG. 2 embodiment. In this embodiment (FIG. 3), comparator 80 receives inputs from adder 55 and multiplier 82. Multiplier 82 receives an input (R 3   2 ) from register 26 through multiplier 66 and a K 3  input from register 84. K 3  is a constant to add a hysteresis effect. The purpose of such hysteresis is to minimize the number of threshold mode changes that occur. 
     The outputs from comparators 58, 59, and 80 are as follows: ##EQU4## The output from comparator 58 (designated A) is coupled to AND gate 88 and NAND gate 89, the output from comparator 59 (designated B) is coupled to AND gate 88 (through inverter 90) and to NAND gate 89, and the output from comparator 80 (designated C) is coupled to NAND gate 89. The output from AND gate 88 is coupled to OR gate 92, while the output of NAND gate 89 is coupled to OR gate 92 through AND gate 93 (which receives a second input from OR gate 92). 
     The output from OR gate 92 is coupled to the gray-scale thresholding circuitry and the black-white thresholding circuitry to control operation thereof with the output designated D controlling gray-scale thresholding and the output designated E being coupled through inverter 95 to control black-white thresholding according to the following: ##EQU5## The logic circuitry acts to achieve the following states: 
     
         ______________________________________      State  Comparator LevelCondition    No.      58       59     80______________________________________F.sub.i &lt; K.sub.1        1        0        0      0K.sub.1 ≦ F.sub.i &lt; K.sub.2        2        1        0      0K.sub.2 ≦ F.sub.i &lt; K.sub.3        3        1        1      0K.sub.3 ≦ F.sub.i        4        1        1      1______________________________________ 
    
     State 1 results in no change in the switch condition. State 2 results in gray-scale thresholding. State 3 results in no change in switch condition, and State 4 results in black-white thresholding. 
     In view of the foregoing, it should be appreciated that this invention provides an improved thresholding mode switch and method for mode selection that are useful in achieving high quality printed copies of mixed format documents.