Abstract:
A code parser decodes coded compressed image information into an intermediate code. A code expander operating asynchronously relative to the code parser decompresses the compressed image information in accordance with such decoded information. A window register in the code parser has a length at least as long as the longest code in the intermediate code. When the intermediate code indicates a pattern in one line in a raster scan of an image corresponding to a pattern in an immediately preceding line, the window register and associated circuitry scan the one line and provide for the decompression in such line in accordance with the decompression at the corresponding positions in the preceding line. Such associated circuitry may include two memories, one for even scan lines and the other for odd scan lines. Alternate ones of the memories are activated for information comparison between adjacent lines during alternate line scans. When the same color is to be printed at a number of successive positions in a line, a counter is set to count such number in the expanded line. During this count, the same color is output. The code parser requests successive codes from an external source and acknowledges the receipt of such successive codes. The code expander receives new codes and expansion instructions from the code parser and acknowledges the receipt of such codes. Under certain circumstances, the code parser may not operate on the next code until the code expander has decompressed the information represented by the previous code.

Description:
This is a continuation of application Ser. No. 081,473 filed Aug. 4, 1987, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     This invention relates to apparatus for decoding and decompressing image coded compressed image information. More particularly, this invention relates to apparatus for decoding and decompressing coded compressed image information efficiently and reliably without any back tracking in the input compressed code stream or reference image information. 
     Imagery which has been rasterized and digitized can be compressed using Huffman coding techniques (reference 1) to encode &#34;features&#34; of the images. Features which are typically encoded are run-lengths of a given color within a given raster line and color change correlation between successive raster lines. Using the Huffman coding technique, these features are encoded into a set of binary codes of variable length based on the statistics of a set of sample images. Examples of this image compression technique are the CCITT Group III and Group IV algorithms. These algorithms are well known in the prior art. 
     The CCITT Group III and Group IV compression algorithms typically result in a relatively high compression ratio of the number of binary bits contained in the original image to the number of binary bits contained in the compressed image. For black and white (binary pel) imagery containing text, symbols and graphics, the compression ratio can typically range from 5:1 to 50:1. The processing, identification and reconstruction can be performed by software. 
     The CCITT Group III and Group IV compression algorithms are frequently used to minimize the storage and transmission requirements of equipment which handles scanned images, such as facsimile equipment. Because the image expansion apparatus should produce expanded images at a rate commensurate with the speed of the image output device, such as a printer or raster display, with which it communicates, it is advantageous to utilize high speed image electronics for image decompression. The input rate of image output devices can range from two hundred thousand (200,000) pels (pixels) per second for a facsimile machine to one hundred million (100,000,000) pels (pixels) per second for a laser printer or Cathode Ray Tube (CRT) display. 
     In order to reconstruct the coded images, known as expansion or decompression, the code stream is processed, individual digital code words identified and the encoded features of the original image reconstructed. CCITT Group III and Group IV decompression has been implemented with software operating on a standard computer or microprocessor. The decompression speed of software operating on microprocessor and using CCITT Group III and Group IV algorithms, while adequate for facsimile equipment, is frequently many times slower than the speed of high speed output devices such as a laser printer. As a result, high speed output equipment must utilize specialized image decompression circuitry. 
     This invention relates to direct circuit means of decompressing imagery which has been compressed by using CCITT Group III, CCITT Group IV or similar algorithms which employ Huffman coding or modified Huffman coding to compress run lengths of a given color and color change correlation between successive raster lines. Such direct circuit means operates on a digital basis. Such direct circuit means is preferably constructed of identical semiconductor technology as a microprocessor. Because of its specialized structure, such circuit means preferably utilizes a comparable number of logic gates, but achieves a processing speed many times greater than the processing speed obtained by a microprocessor in providing decompression. 
     In one embodiment of the invention, a code parser decodes coded compressed image information. The image information may be disposed on a document or on a cathode ray tube. A code expander operating asynchronously relative to the code parser decompresses the compressed image information in accordance with the decoding of such information by the code parser. A code window register in the code parser has a length at least as long as the longest code in the coded compressed image information. When the code indicates a compression in one line in a raster scan corresponding (or substantially corresponding) to a compression in a previous line in the raster scan, the reference window register and associated circuitry scan the line and provide for the decompression in the line being scanned in accordance with the decompression at the (substantially) corresponding positions in the preceding line (reference 2). 
     The associated circuitry may include two memories, one for even scan lines and the other for odd scan lines. Other embodiments of this invention may use a common shared memory to storage. Alternate ones of the memories are activated for information comparison between adjacent lines during alternate line scans. When the same color is to be printed at a number of successive positions in the line being scanned, a counter is set to indicate such number and to count such number as the line is being scanned. During this count, the same color is output. 
     The code parser requests successive codes from an external source and acknowledges the receipt of such successive codes. The code expander receives new codes and expansion instructions from the code parser and acknowledges the receipt of such codes. Under certain circumstances, the code parser may not operate on the next code until the code expander has decompressed the information represented by the previous code. The code expander provides the decompressed image information at its output. 
    
    
     In the drawings: 
     FIG. 1 is a schematic diagram in block form of a code parser and a code expander and the interrelationship between them to constitute one embodiment of the invention for decompressing previously compressed image information; 
     FIG. 2 is a schematic diagram illustrating in block form the code parser of FIG. 1 in additional detail; 
     FIG. 3 is a schematic diagram illustrating in block form the code expander of FIG. 1 in additional detail; 
     FIGS. 4-7 set forth modified Huffman codes for CCITT Groups III and IV compression algorithms; 
     FIG. 8 is table of possible code instructions for expanding or decompressing the coded compressed image information; and 
     FIG. 9 is a table for setting Group III and Group IV colors in a color register shown in FIG. 3. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 illustrates the overall structure of the decompression circuit which can be viewed as two sequential logical circuits, the code parser 2 and the code expander 6, The code parser 2 and the code expander 6 operate asynchronously to decompress imagery as a flow-through process without backtracking and without using external memory for storing intermediate data or control information. When decompressed, the imagery may be recorded on a document but it can also be provided on a display member such as a cathode ray tube. 
     The code parser 2 identifies and separates individual code words from the code stream and creates a control program containing one or more instructions which have operation code and operand information. Such operation code and operand information are used to control programs created by the code parser 2 to generate the features specified by the code stream to reconstruct the compressed image. 
     CODE PARSER, GENERAL 
     The code parser 2 receives the code stream representing the compressed image to be decompressed. The code parser identifies and extracts code words which are of variable length without separation codes and which are characteristic of Huffman codes. The input code stream may be either serial or parallel on predefined data word boundaries as would be characteristic of an internal computer data bus or memory organization. 
     At the same time that the code words are identified and separated from the input compressed image code stream 1, the length of the current code word is determined. The reference for determining the next code word is simultaneously moved to the first bit following the current code word in the input code stream. The codes are identified by using a sliding window which inputs to the code identification logic a subset of the code stream equal in length to the longest code word (FIG. 2). 
     As a result of the structure of the Huffman codes, a unique determination can generally be made of each code word by using the sliding window. However, since the CCITT Group III and Group IV codes are modified Huffman codes, in certain circumstances the code words cannot be identified uniquely until the result of the previous code word has been determined. In case ambiguity exists in determining the code word from the input code stream, logic is provided within the code parser 2 to cause the code parsing process to pause until the code expander 6 has finished processing the previous code word. The code parser 2 continues to process code information until (a) a code is encountered which designates the end of the code stream for a given image, (b) the code expander has output an image of a predesignated size or (c) an erroneous code is encountered within the input code stream. 
     CODE EXPANDER, GENERAL 
     The code expander 6 is an independent self-contained sequential logic circuit which can be programmed to create rasterized imagery. In one embodiment of this invention, the code expander 6 operates in conjunction with the code parser 2 to expand a compressed image by using a sequence of programs or instructions created by the code parser. Huffman algorithms typically encode a variety of features. In particular, in the case of CCITT Group III and Group IV codes, the features are (1) color runs of either black or white of unlimited lengths within a given raster line (horizontal mode) (2) vertical or almost vertical correlation between color change positions in sequential raster lines (vertical mode) and (3) constant color in a raster line associated with a color change in a previous raster line (pass mode). 
     As a result, the code expander 6 operates in several modes associated with the features to be expanded. These modes depend upon the operation code and operand data input provided to the code expander 6 by the code parser 2. The code expander 6 has a code expansion sequencer 24 (FIG. 3) which produces control signals in response to the input operation code and the operand for each type and size of feature to be expanded. The input program is processed one instruction at a time, resulting in the creation of a rasterized image feature by the code expander 6 for each instruction which is processed. The concatenation of all the features generated by the code expander 6 in sequence results in the generation of the complete expanded image 7. 
     The code expander 6 maintains a reference line memory representing a previous raster line. Since the current raster line is generated at the same time that the previous raster line is referenced and since the code expander operates in a flow-through manner without backtracking, the data being created in representation of the current line is written into the current line memory (36 or 37 in FIG. 3) incrementally as the reference line is accessed, creating a new reference line for subsequent processing. 
     The output of the expanded image 7 is created sequentially by introducing a single bit into a shift register in synchronous relationship with a clock signal for each pel (pixel) being created. The color of the output bit is determined by sequential logic which uses a previous starting color and the current expansion instruction to determine the starting color for the start of the next instruction to be processed (FIG. 9). The expanded image data may be output in parallel from the shift register 32 in FIG. 3. 
     Two (2) sequential logic units control the output of a sequence of pels (pixels) for each instruction being processed depending upon the type of instruction. One logic unit controls horizontal color run-length output by counting the number of pels generated and halting when the run-length of pels is completed. A second logic unit controls pel output in response to features which are based on vertical or almost vertical correlation and also, in the case of CCITT Group III and Group IV codes, the pass mode. This logical unit utilizes a scanning window to reference the previous raster line and to identify the appropriate vertical correlation condition associated with the expansion instruction being processed. As the sliding window is moved relative to the previous raster line, pels (pixels) are output to form the current line being expanded. The size of the sliding window allows pels in directions forward and backward of the direction of pel generation to be referenced in order to determine the position of the correlation feature in the reference line. The purpose of this is to halt the processing of the current instruction being processed by the code expander when a halt condition is reached in the reference line. 
     As shown in FIG. 1, the code parser 2 and the code expander 6 operate in accordance with coded information introduced to them. For example, the code parser 2 receives the compressed image code 1, data acknowledge signal 8 and next color signal 60 and processes this information. The code parser 2 also receives a code acknowledge signal 5 from the code expander 6. The code parser 2 transmits a data request signal 9. The code expander 6 receives expansion instructions 3 and a new code 4 from the code parser 2 and processes this information to decompress the compressed information. 
     The code parser 2 receives the compressed image code 1 and detects this code. The detection of the code is enhanced by coded information relating to the length of the code. When the code has been detected, the code parser 2 passes instructions 3 to the code expander 6 to expand (or decompress) the compressed information in accordance with the detected code. When the code expander 6 receives the instructions to expand the compressed information, the code expander transmits a signal 5 to the code parser 2 to acknowledge that it has received such instructions. 
     At the same time, the code parser 1 sends data request signal 9 to the apparatus providing the compressed data so as to request the submission to the code parser of the information representing the subsequent code information. When the new information has been transmitted to the code parser 2, the code parser 2 receives a signal 8 acknowledging that such new information has been transmitted to the code parser. 
     CODE PARSER, DETAILED DESCRIPTION 
     The code parser 2 (FIG. 2) includes a buffer shift register 10 which receives the compressed image code data 1 typically in parallel words compatible with computer bus or data storage format. The buffer shift register 10 can optionally receive serial input data via serial input 50. The buffer shift register 10 maintains a data word so as to provide a code window register 11 with a continuous stream of data 17 without being interrupted as each code word is shifted out of the code window register 11 after it has been identified. The code window register 11 contains a sliding window of code bits at least as large as the longest possible code word. 
     Code identification logic 12 receives parallel code data through a sliding window 19 from the code window register 11 and determines whether a valid code word, aligned to the most significant bit of the code window register, is present in the code window register. The code identification logic 12 can provide this determination by using look-up tables whose size is equal to 2 raised to a power equal to the length of the longest possible code word. Optionally other forms of logic can be used to identify codes. FIGS. 4, 5, 6 and 7 contain and constitute code tables for CCITT Groups III and IV modified Huffman codes. These tables are known in the prior art. The code identification logic 12 generates as an output an expansion code instruction 20 and inputs this instruction to an expansion instruction register 13. The code information within the code window register 11 is also input to code length logic 14 which determines the length 51 of the identified code 20 and outputs the determined length to a shift counter 22. 
     If no valid code is present within the code window 19, an error signal is generated by the code identification logic 12. If a valid code, i.e. no error, is identified within the code window 19, parser control sequential logic 55 sends a load signal 53 to the shift counter 22 and also enables, as by a signal 21, a shift clock 16 to commence the generation of a clock 18. In this way, the code window 19 can be shifted to the start of the next code word as determined by the code length of the previous code word. 
     The shift counter 22 counts downwardly from the value of the previous code length and signals the parser control logic 55 that a terminal count 54 has been achieved. This enables the next code word to be identified. As each code word is identified and after the resulting expansion instruction has been loaded into the expansion instruction register 13, a new code signal 4 (FIGS. 1 and 2) is asserted. This new code signal 4 notifies the code expander 6 (FIG. 1) that a new expansion instruction is present. The code expander acknowledges the receipt of the expansion instruction via the code acknowledge signal 5 (FIGS. 1, 2 and 3). 
     The parser control logic 55 in FIG. 2 suspends further code identification until the control instruction has been accepted by the code expander 6. However, the shift clock 16 can operate, shifting the next instruction into place while the parser control 55 is waiting for the code acknowledge signal 5 from the code expander 6. The next instruction can be shifted into place under such circumstances since the current expansion instruction 3 is maintained within the instruction register 13. The parser control 55 generates requests for new data via the data request signal 9 (FIGS. 1 and 2) from the input code stream whenever a complete data word has been shifted out of the buffer shift register 10. When new data has been input, the parser control 55 receives the data acknowledge 8 signal from the external source. If no data is available, the parser control suspends the operation of the shift clock 16 until a new data word becomes available. 
     CODE EXPANDER, DETAILED DESCRIPTION 
     The code expander 6 receives code expansion instructions. A possible set of these instructions is defined in FIG. 8. These instructions contain operation codes or parameter data as in the case of horizontal or vertical Group III and Group IV modes. Expansion operation codes are received by a code expansion sequencer 24 (sequential logic). Depending upon the expansion mode (horizontal, vertical or pass), the code expansion sequencer 24 controls the loading of parameter data into either a run length counter 27 or a vertical and pass mode register 33 with appropriate load signals 39 and 47, respectively. 
     For Group III and Group IV codes, the code expansion sequencer 24 sets the color in the color register 29 in accordance with the logic shown in FIG. 9. Once the parameter data has been loaded into the appropriate one of registers 27 and 33, the code expansion sequencer 24 enters into the operate mode, thereby enabling the expansion clock 28. The expansion clock 28 generates a clocking signal to an even line pel (pixel) counter 35, an odd line pel counter 38, a line length pel counter 26, a reference window register 30 and an output shift register 32. The reference window register 30 and the output shift register 32 operate to shift data. 
     The even line pel counter 35 generates addresses which input to the even line memory 36 in order to access the image data from the previous line whenever an odd line is being expanded. The odd line pel counter 38 generates addresses in order to input expanded data to the odd line memory 37 whenever an odd line is being expanded. The even and odd line memories 36 and 37 switch roles as each successive line is expanded. Thus, one line memory becomes the reference line and the other line memory receives the expanded line output. Although two (2) memories 37 and 38 are shown in FIG. 3, it will be appreciated that the memories 37 and 38 may be consolidated into a single memory with expanded capacity. Actually, a direct comparison may even be made between the signals in one line and the signals in a memory from a previous line. 
     The code expansion sequencer 24 maintains control over the selection of the even line and odd line memories 36 and 37 by controlling an output mux (multiplexer) 34 and providing even line input enable and odd line input enable signals 45 and 56 for each successive line expanded. The output from the output mux 34 is input to the reference window register 30 serially as at 57. The reference window register 30 provides a sliding window which passes over the reference line at each instant to provide access from vertical and pass halt logic 31 to reference image data both forward of, and previous to, the current expanded image pel being output as at 62. 
     The vertical and pass halt logic 31 determines the pel (pixel) position which completes the processing of a code based on color changes in the reference (previous) raster line. The parameter stored within the vertical and pass mode register 33 determines the particular position, within the sliding window relative to the expanded line pel position, that a color change results in a halt condition in the continued generation of a particular color. 
     The expansion clock 28 continues to operate until one of three conditions occurs: 
     1. A halt condition is determined by the vertical and pass mode halt logic 31 in pass or vertical mode; 
     2. The run length counter 27 completes the count of a run length in horizontal mode; or 
     3. The line length pel counter 26 has reached a count equal to the length of an image raster line. 
     Coincident with each clock cycle of the expansion clock 28, a pel (pixel) is output. 
     When the line length count is reached, the code expansion sequencer 24 resets the line length pel counter 26 to the line length value stored in the line length register 25, switches the roles of the even and odd line memories 35 and 36 and awaits a request from the code parser of FIG. 2 for a new instruction. 
     For a given line being expanded, when the pel output stream reaches a position such that the reference window includes the last pel of the previous line, a special provision within the vertical and pass halt logic 31 handles end-of-line processing. To account for image changes after the reference pel in a line, the end-of-line logic treats the data within the reference window register 30 as if both white-to-black and black-to-white color changes have occurred after such last reference pel. 
     As a result of the asynchronous relationship between the code parser 2 (FIG. 1) and the code expander 6, the two are able to operate in an overlapped manner such that the input code stream can be processed by the code parser while the code expander is outputting the expanded image stream. As can be observed by a review of the CCITT Group III and Group IV run length codes, the color of a run length should be known apriori before a unique run length code can be identified in the code stream in certain circumstances. To handle this situation, the code parser 2 is able to decide when a unique code can be identified without knowing the color apriori. In this circumstance, the code parser can proceed to identify the next code word in the code stream. When the code word cannot be uniquely identified without knowing the next color, the code parser code identification logic 12 in FIG. 2 does not make a determination of the code word until the code expander has completed the expansion of the previous code word and the ending color can be determined. The ending color is unknown for a given expansion code only if the completion of the current line could occur and the starting color for the subsequent code would normally be black as prescribed in FIG. 9. 
     Although this invention has been disclosed and illustrated with reference to particular embodiments, the principles involved are susceptible for use in numerous other embodiments which will be apparent to persons skilled in the art. The invention is, therefore, to be limited only as indicated by the scope of the appended claims. 
     REFERENCES 
     (1) EIA Standard RS-465, Group 3 Facsimile Apparatus for Document Transmission, Electronic Industries Association, May 1981. 
     (2) FED-STD-1065, Telecommunications: Facsimile Coding Schemes and Coding Control Functions For Group 4 Facsimile Apparatus.