JP2000217005A - Data coding method/decoding method, data coder/decoder, and image data recording system using the data coding method/decoding method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a data coding/decoding method by which a sufficient compression rate can be ensured with a memory whose capacity is saved for image data, the color of which is frequently changed for a short period, which have recently been used in many fields, to provide a coder/decoder, image data recording system and a recording medium that records the method. SOLUTION: This coder 17/decoder 18 receives one run length value L. Let the case that the value L is coincident with a just preceding run length value in the same color be an event P and the case that the value L is not coincident, be an event Q, then a code denoting the value L is generated on the occurrence of the event Q. On the other hand, on the occurrence or the consecutive occurrence of the event P, a number of replication code corresponding to the number of replications N that is the consecutive occurrence number of the event P is generated.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an encoding / decoding method and apparatus used for compressing / decompressing data used for storing image data in a printer, for example, and more particularly to saving frame buffer capacity in a printer or the like. Encoding and decoding method and apparatus optimal for a so-called memory saving mechanism,
The present invention relates to a system and a recording medium.

[0002]

2. Description of the Related Art In recent years, a printing apparatus such as a laser beam printer compresses or encodes image data for printing and temporarily accumulates the image data, and expands or decodes image data to perform actual printing while storing necessary memory. A so-called memory saving technique for reducing the number of pixels is widely used. Since the basic purpose of such a memory-saving technique is cost reduction by reducing the required memory amount, it is not preferable to provide complicated dedicated hardware for this compression / decompression, and
It is widely practiced to cause a microprocessor that controls the apparatus to perform these compression / decompression processes using software. A number of techniques have been disclosed for the image data compression system and apparatus. In general, when a two-dimensional still image is to be compressed, a high compression ratio can be achieved by using a two-dimensional compression that performs compression in consideration of data correlation in the sub-scanning direction or a predictive coding method that uses an arithmetic code. It is well known that it can be obtained. However, when these methods are executed by software using a microprocessor, the processing speed is slow, and it is becoming difficult to adapt to a memory saving mechanism as the resolution and speed of printing are improving year by year.
Therefore, when a microprocessor performs compression and decompression, it is common to use a relatively simple method called one-dimensional compression.

With regard to such conventional one-dimensional compression, MH codes used in run-length compression, facsimile machines and the like are widely known. These methods have a disadvantage that a sufficient compression ratio cannot be obtained for image data in which the color (black and white) frequently changes in a short cycle (run), such as a pseudo halftone image obtained by computer processing. However, in recent years, it has been difficult to adopt these methods in a memory-saving mechanism, especially in recent years, with the increase in opportunities for printing image data due to advances in personal computers and networks. It is becoming. Also, it should be noted that the two-dimensional compression method, the predictive coding method, the MH coding method, and the like have a drawback that a relatively large capacity reference means such as a line buffer, a probability table, and a code table is required. It is.
For example, a resolution of 1200 dpi (dot / inch),
At a printing speed of 25 ppm (pages / minute), the pixel frequency generally exceeds 100 MHz. It is very difficult to operate the encoding / decoding hardware circuit including the above-mentioned reference means at such a frequency, and in order to overcome this, the circuit is operated at a low frequency by parallelizing the circuit. However, since it is necessary to perform parallel processing including a table and the like, there is a disadvantage that a large-scale circuit is required and the cost is increased.

In order to improve the compression ratio for image data in which colors frequently change in a short cycle as described above,
An encoding technique having a feature of detecting repeatability of image data and run length is also known. For example, Japanese Patent No. 2683506 discloses a method of efficiently controlling image data in which white and black words appear regularly in a relatively short period by using a control word capable of describing both the length of a white word and the length of a black word. A method and an apparatus for compressing data are disclosed. In this method, a certain word length (byte) is defined, data units that are all white are treated as white words, and those that are not all white are treated as black words, and the number of repeated occurrences, the contents of black words, control words, etc. Since encoding is performed in word length units, no special code table is required for encoding and decoding, and processing can be performed in word length units, which is excellent in that sufficient processing performance can be expected even with microprocessor processing. I have. However, since the repeatability is detected in units of word strings, a high compression ratio can be achieved only when the repetition period and the word length included in the target image data match or are multiples. Therefore, there is a disadvantage that a sufficient compression ratio cannot be obtained for general image data.

Japanese Patent Application Laid-Open No. 9-65147 stores run-length values for each of white and black. Methods and apparatus are disclosed for improving compression ratio and processing speed by generating. The run-length value is stored for each color, and it is considered that the likelihood of coincidence when the current value and the immediately preceding value are compared is relatively high. However, obviously, the compression rate is improved only when the amount of data is sufficiently smaller than the code word to be encoded when the repetition code generated when the run length coincides does not coincide. Assigning shorter codewords to repetition codes lengthens codewords with run lengths that are relatively inconsistent, and therefore has a sufficient compression ratio for image data in which colors change frequently in short periods. Has the disadvantage that it is difficult to obtain a code set with According to the embodiment of the specification, the code set is similar to the MH code, and it is difficult to expect high speed such as the run length coding method by the processing by the microprocessor. Is provided for each color, so that when comparing and storing run-length values, it is necessary to perform a process of selecting a reference / storage destination according to the color, which hinders high-speed processing by the microprocessor. There is also the disadvantage of becoming

[0006]

In the above-described conventional image encoding and decoding method and apparatus, although a high compression ratio can be achieved for a specific image, the color frequently changes in a short cycle. There is a problem in that it is difficult to obtain a sufficient compression ratio with respect to various image data.
Therefore, an object of the present invention is to solve such a problem. That is, even for image data in which colors that have been heavily used in recent years change frequently in short cycles,
An object of the present invention is to provide a data encoding method / decoding method, a data encoding device / decoding device, and an image data recording system using the data encoding method / decoding method that can secure a sufficient compression ratio with a memory saving. I do.

[0007]

According to a first aspect of the present invention, there is provided a data encoding method comprising the steps of inputting an alternate run-length numerical sequence for each color obtained by scanning data. A coding method for converting a run length value into a predetermined code sequence and outputting the run length value when a predetermined run length value is input and the run length value matches the immediately preceding run length value of the same color. In addition, an event that does not match is set as a non-matching event, a number of consecutive matching events is set as a repetition number, and when the matching event or a series of matching events occurs, a repetition number code corresponding to the repetition number is generated. When the mismatch event occurs, a code indicating the value of the run length numerical value is generated. According to a second aspect of the present invention, in the data encoding method according to the first aspect, a code corresponding to the number of repetitions is generated for the coincidence event or a series of coincidence events, and the run is performed for the non-coincidence event. The control content for generating the sign indicating the value of the length numerical value includes an initialization step of storing an initial value in a repetition number storage means for storing the repetition number, and the control step corresponding to the occurrence of the coincidence event. An increasing step of increasing the value of the number of repetitions stored in the number-of-repetitions storage means, and the value of the number of repetitions stored in the number-of-repetitions storage means corresponding to the occurrence of the mismatch event at the time is not an initial value in case of,
After outputting a code indicating the value of the number of repetitions, the value of the number of repetitions stored in the number-of-repetitions storage unit is returned to an initial value, and the value of the run-length value is indicated when the number of repetitions is the initial value. A code generation step of generating a code, a repetition step of repeating the increasing step and the code generation step until the encoding of the target data is completed, and at the time when the encoding of the data to be encoded is completed, And outputting a code indicating the value of the number of repetitions if the value of the number of repetitions is not the initial value.

According to a third aspect of the present invention, in the data encoding method according to the first or second aspect, the control for discriminating the coincidence event and the non-coincidence event stores and refers to a run length numerical value corresponding to the number of colors. An initializing step of storing a predetermined initial value in the run length value storing means A and the run length value storing means L, and a time when the predetermined run length numerical value is inputted to each of the run length value storing means L. An identification step in which a case where the run-length numerical value matches the value stored in the run-length value storage means A is a coincidence event, and a case where the value is not coincident is a mismatch event; and after the identification step, Before the next run length value input, the value of the run length value storage unit L is stored in the run length value storage unit A, and then the run length value storage unit L is stored. Characterized by comprising a step of storing the value of said predetermined run length value. According to a fourth aspect of the present invention, in the data encoding method according to the third aspect, a run length measurement is started in the run length value storage means A in an initialization stage of control for identifying the coincidence event and the mismatch event. In this case, an initial value is set, which means that the color starts with a color different from the target color.

According to a fifth aspect of the present invention, there is provided a data encoding apparatus for inputting an alternate run-length numerical sequence for each color obtained by scanning data, converting the run-length numerical sequence into a predetermined code sequence, and outputting the converted code sequence. A run length value storage means L for inputting and storing a predetermined run length value, a run length value storage means A for storing a run length value immediately before the same color as the run length value, and a run length value storage means A; Determining means for determining whether or not the value matches the immediately preceding run-length value of the same color; and storing the number of repetitions in which the match is repeated when the value of the run-length value matches the immediately preceding run-length value of the same color. A repetition number storage means for generating a code indicating the number of repetitions, and a repetition number code generating means for generating a code indicating the number of repetitions, and the run length value when the value of the run length value does not match the immediately preceding run length value of the same color. Characterized by comprising a run-length code generation means for generating a code indicating the value of Goes numeric. According to a sixth aspect of the present invention, in the data encoding apparatus according to the fifth aspect, a code indicating the value of the run-length numerical value is generated in response to the mismatch event, and the code corresponds to the match event or a series of match events. A data encoding device for generating a code corresponding to the number of repetitions, wherein the repetition number storage means stores a repetition number, and the repetition number calculating means increases a value of the repetition number every time the coincidence event occurs If the value of the number of repetitions at the time of occurrence of the mismatch event is not the initial value when the mismatch event occurs, the code indicating the value of the number of iterations is output, and then the value of the number of iterations is returned to the initial value. A run-length code generating means for generating a code indicating the value of the run-length numerical value at the time when the number of repetitions is an initial value, and repeating the operations of the respective means until the encoding of the data to be encoded is completed. System And a repetition number code generation means for outputting a code indicating the value of the number of repetitions when the value of the number of repetitions is not the initial value when the encoding of the target data is completed. It is characterized by the following.

According to a seventh aspect of the present invention, in the data encoding apparatus according to the fifth or sixth aspect, a run length value storage means L for inputting and storing the run length numerical value, and a run length value immediately before the same color as the run length numerical value. The run-length value storage means A for storing the run-length numerical value and the repetition number storage means for storing the repetition number are constituted by general-purpose registers of a microprocessor. An image data recording system according to an eighth aspect of the present invention is characterized in that the data encoding method according to any one of the first to fourth aspects is applied to an image forming apparatus. An image data recording system according to a ninth aspect of the present invention is characterized in that the image forming apparatus according to the eighth aspect is a printer. According to a tenth aspect of the present invention, there is provided a data decoding method according to any one of the first to fourth aspects, wherein a code sequence obtained by scanning code sequence data generated by using the data encoding method according to any one of the first to fourth aspects. And a decoding method for decoding and outputting an alternate run-length numerical sequence for each color, wherein the input code sequence is a code generated by the run-length code generation means. Is output, and if the input code string is a code generated by the number-of-repetitions code generation means, the last run-length value of the same color is output by the number of repetitions represented by the number-of-repetitions code. It is characterized by doing.

According to an eleventh aspect of the present invention, in the data decoding method of the tenth aspect, a decoding-side run-length value storage means A for storing and referencing a run-length value corresponding to the number of colors, and a decoding-side run-length. An initialization step of storing the same initial value in the value storage means L as at the time of encoding;
Decoding to obtain a numerical value indicated by the code and its attribute;
When the attribute of the numerical value indicated by the code is the run-length code, the numerical value indicated by the code is output as a run-length numerical value, and the decoding-side run-length value storing means is stored in the decoding-side run-length value storing means A. After storing the content of L, storing the run-length numerical value in the decoding-side run-length value storing means L; and storing the number of repetitions when the attribute of the numerical value indicated by the code is the repetitive code.・
The value of the number of repetitions is stored in the number-of-repetitions storage means for reference, and the value stored in the decoding-side run-length value storage means A is regarded as a run-length value until the value of the number of repetitions becomes an initial value. After outputting the value stored in the decoding-side run-length value storage means L in the decoding-side run-length value storage means A, the run-length numerical value or the decoding value is stored in the decoding-side run-length value storage means L. A step of storing the value stored in the number-side run-length value storage means A and repeating the process of reducing the value stored in the number-of-repetitions storage means by a predetermined value; and the data of the code string to be decoded ends. A step of repeating the steps from inputting and decoding the predetermined code unit to obtain a numerical value indicated by the code and its attribute to repeating a process of reducing the value of the repetition number by a predetermined value. That. A data decoding apparatus according to a twelfth aspect of the present invention is a data decoding apparatus using the data decoding method according to the eleventh aspect, wherein: a code string storage unit that stores an input code string for each code unit; When the code of the code unit is the run-length code, a run-length value generating unit that generates a run-length value represented by the run-length code; and when the input code unit is the repetition number code, Decoding side run length value storage means A
And run-length value output means for outputting the run-length value immediately before the same color stored in the same number as the number of repetitions represented by the code.

According to a thirteenth aspect of the present invention, in the data decoding apparatus according to the twelfth aspect, the decoding-side run-length value storage means A and the decoding-side run-length storage means for storing and referring to run-length numerical values for the number of colors Length value storage means L, decoded numerical value / attribute determining means for inputting / decoding a predetermined code unit to obtain a numerical value indicated by the code and its attribute, and attribute of the numerical value decoded by the decoded numerical value / attribute determining means Is the run-length code, the numerical value is output as a run-length numerical value. If the attribute of the numerical value decoded by the decoded numerical / attribute determination means is the repetition number code, the repetition number is used. The run-length value generation means for outputting the value stored in the decoding side run-length value storage means A as a run-length numerical value until the value of If the attribute of the numerical value obtained is the repetition number code, a decoding side repetition number storage unit that stores and stores the numerical value, and a process of reducing the value of the repetition number stored in the decoding side repetition number storage unit Means for calculating the number of repetitions corresponding to the number of repetitions, control for storing the same initial value in each of the storage means as in encoding, and storage for the decoding-side run-length value L in the decoding-side run-length value storage means A After storing the value stored in the decoding-side run-length value storage means L, storing the run-length numerical value or the value stored in the decoding-side run-length value storage means A. And control means for controlling the repetition number calculating means to repeat the operation until the data of the code string is completed. According to a fourteenth aspect of the present invention, in the data decoding device according to the twelfth or thirteenth aspect,
Decoding-side run-length value storage means L for inputting and storing a run-length value; decoding-side run-length value storage means A for storing the immediately preceding run-length value of the same color as the run-length value; The number storage means is constituted by a general-purpose register of a microprocessor.

According to a fifteenth aspect of the present invention, in the data encoding method according to any one of the first to fourth aspects, the first code encoded by the data encoding method is 4 bits. A bit width, identified by the 4-bit number being less than 10, a value obtained by adding 1 to the number is a form of the code corresponding to the run-length number, and the second code is 8 The run length corresponding to the run length value, which has a bit width, is identified by the value of the upper 4 bits preceding in the code string being a predetermined value of 10 or more, and adding 11 to the value of the lower 5 bits. One type of code, the third code is at least 8 bits wide and 4
Are identified by the value of the preceding upper 4 bits in the code string being a predetermined value of 10 or more, and for each of the 4 bits following the 4 bits, 8 in the value of the 4 bits. A value obtained by adding 43 to a numerical value obtained by concatenating the lower 3 bits of each 4 bits upward until the above numerical value is detected is one form of the code corresponding to the run-length numerical value. Has a bit width,
The four-bit number is identified by being a predetermined value of 10 or more, and is a type of the code corresponding to the number of repetitions being one, and the fifth code has a four-bit width, A 4-bit numerical value is identified by a predetermined value of 10 or more, and is a type of the code corresponding to the number of repetitions being 2. The sixth code is at least 8 bits wide and a multiple of 4. Is identified by the value of the upper 4 bits preceding in the code string being a predetermined value of 10 or more, and for each of the 4 bits following the 4 bits, a numerical value of 8 or more in the 4-bit value A value obtained by adding 4 to a numerical value obtained by concatenating the lower 3 bits of each 4 bits toward the upper side until is detected is one form of the repetition number code corresponding to the repetition number.

According to a sixteenth aspect of the present invention, in the data decoding method according to the tenth or eleventh aspect, the first code decoded by the data decoding method has a 4-bit width, and A number is identified by being less than 10, and a value obtained by adding 1 to the number is a form of the code corresponding to the run-length number, and the second code is 8
The run length corresponding to the run length value, which has a bit width, is identified by the value of the upper 4 bits preceding in the code string being a predetermined value of 10 or more, and adding 11 to the value of the lower 5 bits. A form of code
Has a bit width that is at least an 8-bit width and a multiple of four, and is identified by the fact that the value of the preceding upper four bits in the code string is a predetermined value of 10 or more, and each of the four bits following the four bits , A value obtained by adding 43 to a numerical value obtained by concatenating the lower 3 bits of each 4 bits upwards until a numerical value of 8 or more is detected in the 4-bit value is a form of the code corresponding to the run-length numerical value. And the fourth code has a width of 4 bits, and is identified by a 4-bit numerical value being a predetermined value of 10 or more, and is a form of the code corresponding to the number of repetitions being 1. The fifth code has a 4-bit width, is identified by the 4-bit number being a predetermined value of 10 or more, and is a form of the code corresponding to the number of repetitions being 2. , The sixth sign is less Identified by also has an 8-bit wide bit width as a multiple of 4 in a predetermined value of the upper 4 bit value is 10 or more preceding the code sequence,
For each of the 4 bits following the 4 bits, a value obtained by adding 4 to a numerical value obtained by concatenating the lower 3 bits of each 4 bits upwards until the value of 8 or more is detected in the value of the 4 bits is the number of repetitions. Is a form of the repetition number code corresponding to.

The present invention according to claim 17 is the invention according to claim 5 or 6.
The data encoding device according to the above, further comprising an encoding unit that generates the first to sixth codes. According to an eighteenth aspect of the present invention, in the data decoding apparatus according to the twelfth or thirteenth aspect, the data decoding apparatus further comprises decoding means for decoding the first to sixth codes. The image data recording system according to the nineteenth aspect of the present invention is the tenth aspect, the eleventh aspect or the fifteenth aspect.
Wherein the data decoding method according to any one of the above is applied to an image forming apparatus. An image data recording system according to a twentieth aspect of the present invention is characterized in that the image forming apparatus according to the nineteenth aspect is a printer. A computer-readable recording medium according to a twenty-first aspect of the present invention stores a program for causing a computer to execute the data encoding method according to any one of the first to fourth aspects or the fifteenth aspect. It is characterized by the following. According to a twenty-second aspect of the present invention, there is provided a computer-readable recording medium storing a program for causing a computer to execute the data decoding method according to the tenth, eleventh, or seventeenth aspect. Features.

According to a first aspect of the present invention, there is provided a data encoding method configured to reduce the number of generated codes.
It is possible to provide an encoding method capable of obtaining a sufficiently high compression ratio even for image data in which colors frequently change in a short period, such as pseudo halftone images obtained by computer processing. According to the data encoding method configured as described above, according to claim 2, by performing the control by software processing by a microprocessor, the substitution and addition are performed so that a sufficiently high processing speed can be expected. And an encoding method that can be realized by simple control such as comparison and branching. According to the third aspect of the present invention, the data encoding method configured as described above is based on color so that a sufficiently high processing speed can be expected even if the control is performed by software processing by a microprocessor. Judgment / branch is unnecessary, and
It is possible to provide an image data encoding method that can be realized by simple control such as substitution, comparison, and branching.

According to the fourth aspect of the present invention, there is provided a data encoding method which does not require a code representing that a run-length value is 0, and therefore has a higher compression ratio. Can be provided. According to the data encoding device configured as described above, according to claim 5, it is possible to provide an image data encoding device that can achieve a higher compression rate. According to the data encoding apparatus configured as described above, according to claim 6, substitution, subtraction, In addition, it is possible to realize an image data encoding apparatus which can be realized by simple control such as comparison and branching, and which has simple processing and very high speed. According to the data encoding device configured as described above, according to claim 7, it is possible to provide an image data encoding device that can expect an extremely high processing speed. According to the data recording system configured as described above, according to claim 8, it is possible to provide a data recording system using an image data encoding method applicable to various cases.

The image forming apparatus configured as described above has
According to the ninth aspect, the present invention is a printer, and therefore, it is possible to provide a high-speed and memory-saving printer. A method for decoding data configured as described above is described in claim 10.
According to this method, it is possible to provide a data decoding method that can achieve quick and memory-saving. According to the data decoding method configured as described above, according to claim 11, a memory-saving and quick image data decoding method can be provided. According to the data decoding device configured as described above, according to the twelfth aspect, it is possible to provide a decoding device capable of quickly saving image data with less memory. According to the data decoding device configured as described above, it is possible to provide a data decoding device capable of quick data decoding and saving memory. The data decoding apparatus configured as described above can perform high-speed data processing and can also be used as a memory included in a processor, as described in claim 14, and has a memory-saving data decoding apparatus. Can be provided.

In the data encoding method configured as described above, a special table reference is not required at the time of encoding generation, and these processes are substituted, added, subtracted, shifted, and ANDed. And a code set that can be realized by simple control such as comparison and branching.
It is possible to provide an image data encoding method that can expect a sufficiently high processing speed even if the control is performed by software processing by a microprocessor. Furthermore, each code to be introduced has a code length of 4 bits or a multiple thereof so that the processing can be easily implemented in hardware.
By combining hardware processing and software processing, it is possible to provide an image data encoding method capable of adapting the same encoding method to a wide performance range. The encoding and decoding method of data configured as described above does not require a special table reference at the time of numerical decoding as described in claim 16, and substitutes those processes for addition, subtraction, shift, logical product, and Introducing a code set that can be realized by simple control such as comparison and branching, and provides an image data decoding method that can expect a sufficiently high processing speed even if the control is performed by software processing by a microprocessor. Can be. Furthermore, each code to be introduced has a code length of 4 bits or a multiple thereof so that the processing can be easily implemented in hardware. By combining hardware processing and software processing, the same decoding method can be widely used. A method for decoding image data that can be adapted to a performance range can be provided.

The data encoding device configured as described above can provide an encoding device that performs extremely efficient data processing in image encoding, as described in claim 17. The data decoding device configured as described above can provide a decoding device that performs extremely efficient data processing in decoding an image, as described in claim 18. The data recording system configured as described above can provide an image data recording system that can appropriately cope with an image in which color alternation is intense, such as pseudo halftone, as described in claim 19. The image forming apparatus configured as described above can provide an image forming apparatus that can appropriately cope with an image in which color alternation is intense, such as a pseudo halftone, as described in claim 20. Claim 2
The computer-readable recording media described in 1 and 22 allow a computer to read a program by using the recording medium and execute the program.

[0021]

Embodiments of the present invention will be described in detail with reference to the drawings. FIG. 1 is a diagram for explaining the basic principle of the present invention. The principle described below is common to all claims of the present invention, and sufficiently high compression is applied to image data in which colors frequently change in a short cycle, such as a pseudo halftone image by computer processing. Invented with the intention of gaining a rate. FIG. 1 shows an example in which image data to be compressed starts with 6 dots of white, then 3 dots of black, and so on. When the run length numerical value measurement is started from white, an alternate run length numerical value sequence for each color obtained by scanning the image data becomes a value as shown in “Run length L” in the figure, and this value is transmitted to the encoding device. Assume that they are sequentially input. A case where the value of the run-length numerical value L matches the run-length numerical value immediately before the same color is referred to as a coincidence event P (hereinafter referred to as event P), and a case where the values do not coincide is referred to as a non-coincidence event Q (hereinafter referred to as event Q). A continuous number is defined as a repetition number N (N ≧ 1). For each run-length numerical value L, whether it becomes event P or event Q is shown in the column of “event” in FIG. The value of the number of repetitions N for each event P is shown in the column of "number of repetitions N" in FIG. Strictly speaking,
Since the first six dots of white and the first three dots of black of the image data do not have a run length value immediately before the same color,
It is impossible to judge the above event unless some method definition is given.
Assume that

According to the present invention, an L code indicating the value of the run length numerical value L is generated for the event Q, and corresponding to the repetition number N for the event P or a series of events P. Generate an N code. Whether the generated code is an L code or an N code is shown in the “Code” column in FIG. From the figure, it can be seen that, as can be easily determined, a total of six codes are generated for a total of ten run-length numerical values L input, and the number of codes can be reduced. It can be easily understood that the probability that the event P occurs and the probability that the event P continues should be sufficiently high for the above-described principle to achieve the intended effect. According to the observations made by the inventor of the present application, the event P
Is about 15%, and the probability that event P continues is 25
%, But when these are compressed with the MH code, 9%
A compression ratio of about 0% is obtained. However, as the number of elements in which the color frequently changes in a short cycle increases in shading, pattern graphics such as pie charts, or pseudo-halftone images such as photographic images, the probability of occurrence of event P and The probability that P continues is significantly improved, and conversely,
It has been observed that the compression rate by the MH code tends to decrease significantly. The occurrence probability of the event P in the image data having the lowest compression ratio of 38% with the MH code being 38% is 9
4% and the probability that event P was continuous was 99%. In other words, a significant improvement in the compression ratio cannot be expected for image data that can originally be expected to have a high compression ratio, but a significant improvement in the compression ratio is expected for image data in which a low compression ratio poses a problem. Which is at least 1
This can be said to be a very suitable property for a memory saving mechanism in which the memory capacity capable of compressing image data for a page is a major factor controlling cost.

FIG. 2 is a block diagram showing an embodiment in which the encoding apparatus and the decoding apparatus according to the present invention are applied to an image forming apparatus. FIG. 2 shows a known printer device 1 to which the present invention is applied. Image data from a host machine 2 such as a personal computer is input to the controller 4 via the host I / F 3. An example of the image data at this time corresponds to the run length numerical value L shown in FIG. 5 is an operational panel, 6 is a panel I /
F and 7 are font ROMs, 8 is an NV-RAM, 9 is an option RAM, and 10 is an engine I / F for sending data to the printer engine 11. 12 is, for example, F
It is an input device for introducing a program written on a recording medium 13 introduced from a D, an IC card, or a network into the printer device 1. 14 is a program ROM, 15 is a RAM, 16 is a CPU as control means
The program ROM 14, RAM 15, CP
The encoding device 17 and the decoding device 18 which are the most main features of the present invention are constituted by U16, and these portions are surrounded by a thick black frame in the figure.

The encoding device and the decoding device of the present embodiment
3 (a) and 3 (b). FIG. 3A shows the internal configuration of the encoding apparatus according to the present invention, wherein 19 is a run-length storage means A, 20 is a run-length storage means B, 21 is a run-length storage means L, 22 is a discriminating means, and 23 is a repeater. Numeral storage means and calculation means, 24 is a run-length code generation means, 25 is a repetition number code generation means, and 26 is an encoding means. The operation of this configuration will be described later with reference to FIG. FIG. 3B relates to a method and an apparatus for decoding a code string encoded by the encoding method and the apparatus described above. 30 is decoding-side run-length storage means A,
31 is a decoding-side run-length storage means B, and 27 is a decoding numerical / attribute discriminating storage including a decoding numerical / attribute discriminating means for discriminating a numerical value and an attribute of a code string upon decoding, and a decoding numerical / attribute storing means for storing. 28, decoding means; 29, run-length value generating means including decoding-side run-length value storage means L and decoding-side run-length value output means; 32, decoding-side iteration number storage means and decoding-side arithmetic means. . The operation related to this configuration will be described later with reference to FIG.

FIG. 4 is a flowchart showing an embodiment of the encoding method according to the present invention. Although this figure is also an embodiment of claim 1, it also includes each step of code generation according to claim 2 and each step of event identification according to claims 3 to 4. First, the symbols used in FIG. A and B are temporary storages for storing and referring to run-length numerical values for the number of colors. C
Means a constant substituted into A and B in the initialization stage. L is a temporary storage for storing and referring to a run length numerical value obtained by scanning the image data.
N is a temporary storage for storing and referring to the number of repetitions, that is, a continuous number of the events P. When the present embodiment is configured by software, the above A, B, L, and N
Although a suitable temporary storage means may be used, it is particularly preferable to use a general-purpose register of a microprocessor from the viewpoint of improving the processing speed. In addition, the constant C and each stage of control may use a suitable storage means as a program, ie, an instruction code.

Hereinafter, the operation of the present embodiment will be described with reference to the steps shown in FIG. At the start of encoding, first, step 10
, A predetermined constant C is substituted for A and B, and “0” is substituted for N. In this embodiment, the same value C is substituted for A and B, but different values may be substituted for A and B.
Next, in step 11, one run length numerical value is acquired and stored in L. Next, in step 12, A
Is compared with the value of the run-length numerical value L. If they match, the process branches to step 16; if they do not match, the process branches to step 13. This determination corresponds to the identification of the event P and the event Q. When A and L match, that is, in the event P, in step 16, the value of the number of repetitions N is increased by "1". This processing is nothing more than counting N to generate an N code representing the number of repetitions N when the event P occurs, and suspending code generation. If A and L do not match, that is, if it is event Q, first, N is compared with "0" in step 13, and if N is not "0", that is, if code generation is suspended. In step, an N code corresponding to the N value at that time is generated in step, and the value of N is returned to “0” in step 15, thereby canceling the hold state. If N is “0” in step 13 following step 15 or in step 13, that is, at a time when code generation is not suspended, an L code corresponding to the L value at that time is generated in step 17.

After the above-described processing corresponding to the event P or the event Q, in step 18, the content of A is updated to the value of B at that time, and the value of B is updated to the value of L at that time. I do. Next, it is determined in step 19 whether or not the processing for all the target image data has been completed. If the image data remains, the control branches to step 11 and repeats the control to step 18 to repeat the image data. When the process is completed, the process proceeds to step 20. N in step 20
Is compared with “0”. If N is not “0”, that is, if code generation is suspended, an N code corresponding to the N value at that time is generated in step 21 to change the suspension state. To eliminate. If N is "0" in step 20 following step 21 or in step 20 before, that is, at the time when code generation is not suspended, the encoding process is completed. By the above explanation,
According to the present embodiment, an L code indicating the run length numerical value L is generated for the event Q with only simple control, and an N code corresponding to the number of repetitions N is generated for the event P or a series of the events P. Can be generated. In particular, event P
In determining the event Q, the temporary storage of A and B is not specified for each color, but a method of sequentially moving the colors regardless of the color is used, as is apparent from step 18. In addition, the judgment based on the color is unnecessary in step 12, which can contribute to high-speed processing.

In the description relating to FIG. 1, since the first run-length value and the second run-length value do not have a run-length value immediately before the same color, an event is determined unless some system definition is given. However, in the present embodiment, as can be easily understood by tracing the flow chart, the first run-length value is the initial value of A and the second run-length value is Is compared with the initial value of B, and it can be seen that event P is determined when they match, and event Q is determined when they do not match. According to a fourth aspect of the present invention, "0" is substituted as the initial value of the A. If this content is applied to the present embodiment, it is possible to obtain a feature that the event P occurs when the first run-length value is “0”, as is clear from the above description. Generally, when scanning at least one dot of image data to generate alternate run length values for each color, the run length value becomes “0” when the measurement starts from white and the image starts from black. And only when the image starts from black and the image starts from white, and it can be seen that either one can be determined if the measurement start color is determined. The run length value after that is "1"
With the above values, it is understood that the frequency of occurrence of the value “0” is extremely low. Then, when this run-length value of “0” is regarded as an event P and is encoded by N code,
It is possible to obtain a feature that it is not necessary to represent a value “0” in the L code. The code set described below does not actually define an L code representing “0”.

In the above description, the details of the run length measurement shown in step 11 and the procedure for determining the end of data shown in step 19 and the code generation shown in steps 14, 17 and 21 are described. Various control procedures are omitted. The measurement of the run length and the determination of the end of the data related thereto are well known to those skilled in the art and will not be described.
In order to show a control procedure regarding code generation, it is necessary to define a specific code set first, and this will be described later. FIG. 5 is a flowchart showing one embodiment of the decoding method according to the present invention. First, the symbols used in FIG. A and B are temporary storages for storing and referring to run-length numerical values for the number of colors. C is a constant assigned to A and B in the initialization stage. L
Is a temporary storage for storing and referring to a run length numerical value obtained by scanning image data. N is a temporary storage for storing and referring to the number of repetitions, that is, a continuous number of the events P. W is temporary storage for storing and referring to a numerical value decoded from a code unit. V is the W
Is a temporary storage for flag information indicating whether the content is a run-length numerical value (V = 0) or the number of repetitions (V = 1). As in the case of the above-described encoding method, when the present embodiment is configured by software, the above-mentioned A, B, L, and N may use appropriate temporary storage means. It is preferable to use a general-purpose register from the viewpoint of improving the processing speed. In addition, the constant C and each stage of control may use a suitable storage means as a program, that is, an instruction code.

Hereinafter, the operation of the present embodiment will be described with reference to the respective steps shown in FIG. Upon the start of decoding, first, in step 30, a predetermined constant C is substituted for A and B. In order for correct decoding to be performed, the constant assigned to each of them must match the value assigned to the temporary storage of the same name in encoding. Next, in step 31, one code unit is read and decoded, and the numerical value decoded into W is stored in V as an attribute of the numerical value, that is, whether or not the number of repetitions. next,
In step 32, the attribute of the numerical value W is determined using the value of the V, and if it is a run-length numerical value (V = 0) processing 38
If the number of repetitions is (V = 1), the flow branches to step 33. When the run-length value is obtained, first, in step 38, the value of W is substituted for L and output as a run-length value. In step 39, the value of A is updated to the value of B at that time. , B are updated to the current value of L, and the process proceeds to step 40. When the number of repetitions is obtained, first, in step 33, the value of W is set to N
Then, in step 34, the value of A at that time is substituted for L and output as a run-length numerical value. Then, in step 35, the value of A is updated to the value of B at that time. Is updated to the current value of L, then the value of N is reduced by "1" in step 36, and
In step 7, the value of N is checked, and steps 34 to 36 are repeated until N becomes "0".
Then, the process proceeds to step 40.

Next, in step 40, it is determined whether or not the processing for all the target code strings has been completed. If code data remains, the control branches to step 31 and repeats the control to step 40. The decoding process ends when the code data ends. From the above description, according to the present embodiment, it can be understood that the original run-length numerical sequence can be generated from the code sequence data composed of the L code and the N code with only simple control. However, it should be noted that the present embodiment does not specify a specific numerical value decoding means, and is not in an optimum state. That is, if the means and this embodiment are combined to form a series of processes, there is no necessity to go through temporary storage such as W or V. In the above description, the procedure for returning the run-length numerical output to the image data shown in steps 34 and 38 and the procedure for determining the end of the data shown in step 40 related thereto and the detailed control procedure for step 31 are omitted. It is. The drawing means and the data end determination related thereto are well known to those skilled in the art and will not be described. In order to show the control procedure relating to the numerical value decoding means, it is necessary to define a specific code set first, which will be described later.

FIG. 6 is a diagram showing an embodiment of a code set used in the encoding / decoding method of the present invention. As shown in the figure, the code set according to the present embodiment includes six types of code units. The third code format L3 from the first code format L1
Are the L codes representing the run-length numerical values, and the fourth code format N1 to the sixth code format N3 are the N codes representing the number of repetitions. The first code format L1 has a 4-bit width, and is identified by the fact that the 4-bit value is less than “10”, and a value obtained by adding “1” to the value corresponds to the run-length value L. The second code format L2 has an 8-bit width, is identified by the value of the preceding upper 4 bits in the code string being “11” or “12”, and adds “11” to the value of the lower 5 bits. The calculated value corresponds to the run length numerical value L. The third code format L3 is at least 8
It has a bit width that is a multiple of 4 in bit width, and is identified by the value of the preceding upper 4 bits in the code string being “12”, and for each of the 4 bits following the 4 bits,
The lower three bits of each of the four bits are concatenated upward, ie, the value obtained by adding "43" to the connected numerical value until the numerical value of "8" or more is detected in the 4-bit value is the run-length numerical value L. Corresponding to

The mathematical expression described at the right end of the third code format L3, that is, L = {Fn,..., F1, F0} +43, is a typical hardware description language, Verilog;
(Cadence, U.S.A.) is used, which means that elements such as Fn separated by commas are connected in the order described in parentheses to form one numerical value. . The fourth code format N1 has a 4-bit width and is identified by the fact that the 4-bit value is “13”, which corresponds to the repetition number N being “1”. The fifth code format N2 has a 4-bit width, and is identified by the fact that the 4-bit value is "14".
Is "2". The sixth code format N3 has a bit width of at least 8 bits and a multiple of 4, and the value of the preceding upper 4 bits in the code string is “1”.
5 ", each 4 bits following the 4 bits.
As for the bits, the lower three bits of each of the four bits are concatenated toward the upper side until a numerical value equal to or more than "8" is detected in the value of the four bits, that is, the connected numerical value is "4".
Corresponds to the number of repetitions N. The mathematical expression described at the right end of the sixth code format N3, that is, N = {Fn,.
1, F0｝ +4 is a representation using a typical hardware description language, for example, Verilog (registered trademark of Cadence Corporation, USA), and each element such as Fn separated by a comma in parentheses. Are concatenated in the described order to form one numerical value.

Although the code corresponding to the number of repetitions N of "3" is not explicitly shown, the N1 code (N = 1) and the N2 code (N =
2) shall be used in combination. The code amount composed of these combinations is 8 bits, which is the same as the minimum code amount of the code in the N3 format. By using this combination expression, it is possible to increase the range corresponding to the N3 code having a certain code amount. This is because it becomes possible. In addition, although the code with which the run-length numerical value is "0" is not specified, it is preferable that the code itself be unnecessary by using the invention described in claim 4. However, it should be noted that the code format of the present embodiment does not restrict the expressible value range in principle, and there is a feature that any integer can be expressed if an L3 code or an N3 code is used. The reason is that the temporary storage used for the process of decoding a numerical value has a finite bit width, while the length of the L3 code or the N3 code is not limited. This is because it is possible to generate a code such that “0” or a negative number is generated by carry.

According to the observations made by the inventor of the present application, a very excellent compression ratio was observed by encoding using the code set of the present embodiment. A compression ratio almost equivalent to that of the MH system is observed for image data containing only characters, and a compression ratio significantly higher than that of the MH system for image data such as a pseudo halftone image whose color frequently changes in a short cycle. Was observed. As described above, the compression ratio of the image data whose compression ratio by the MH code was the lowest during observation was 38%,
With this method, it was improved to 92%. With the introduction of the specific code set embodiment, the embodiment of the L code generation method, the embodiment of the N code generation method, and the decoding method for the coding method will be described below on the assumption that this code set is used. In the following, embodiments of the numerical decoding method will be sequentially described.

FIG. 7 is a flowchart showing an embodiment of control for generating a run-length code in response to the event Q. This is a concrete example of step 17 in FIG. 4 described above, and converts one input run-length numerical value L into one of the L1 to L3 formats of the code set described in FIG. In the figure, the substitution expression “K (n) ← X;” means that the lower “n” bits of “X” are output as a code. “W” is temporary storage used for the process of generating the L3 code. When the L code generation process is started, that is, when a certain run-length numerical value L is input, first, in step 50, it is determined whether or not the run-length numerical value L is equal to or less than "10". If it is equal to or less than "10", in step 51, the lower 4 bits of the value obtained by subtracting "1" from the run-length value L are output as a code, and the code generation process ends. The generated code is 4 bits wide, and as a result of this subtraction,
The value is less than “10”, and the value obtained by adding “1” to the value represents the run length numerical value L.
It turns out that it is nothing but a sign. If it is determined in step 50 that the run length value L is equal to or greater than "11", then in step 52, it is determined whether the run length value L is equal to or less than "42".
If it is equal to or less than “42”, in step 53,
Lower 8 of the value obtained by adding “149” to the run length numerical value L
The bit is output as a code, and the code generation process ends.
An assignment expression “K” that associates a run-length numerical value L with a code value
(8) ← L + 149 ”is replaced with“ K (8) ← L−11 + 16 ”.
It can easily be understood that this is nothing but the above-mentioned L2 code when expanded to "0".
L ≦ 42 ”, so“ 0 ≦ L−11 ≦ 31 ”
It corresponds to the numerical value part F of the L2 code, that is, the lower 5 bits, and if “160” is represented by a binary number, “10100
000 ", and the upper three bits correspond to a code-specific constant.

If it is determined in step 52 that the run length numerical value L is a numerical value equal to or greater than "43", first in step 54, the numerical value "12" is
Output as the sign of the bit. If “12” is expressed in a binary number, it is “1100”, which is nothing but a constant for identifying the start of the L3 code. Next, at step 55, a value obtained by subtracting "43" from the run-length value L is substituted for W. Hereinafter, using this value of W, L
The control for generating the numerical part of the three codes is as follows.
It is determined whether the value of W is less than “8” in
If the value is equal to or greater than "8", in step 57 the lower 4 bits of the value obtained by ANDing the W value and the constant "7" for each bit.
The bit is output as a code, and the value of W is updated in step 58 with the value shifted to the lower side, that is, right by 3 bits. In step 56, until the value of W is less than "8", 57 and step 58 are repeated, and when the value of W becomes less than "8" in step 56, the lower 4 bits of the value obtained by adding a constant "8" to W are output as a code in step 59 to generate a code. It includes each stage of terminating the process. If the constant "7" is represented by a binary number, it is "0111", and the code generated in step 57 is always a numerical value less than "8".
On the other hand, if the constant “8” is expressed in binary, it is “1000”, and the code generated in step 59 is always “8”.
The above numerical values indicate that the sign is the last one of the numerical values.

FIG. 8 is a flowchart showing an embodiment of the control for generating the N code corresponding to the number of repetitions in response to the event P or the continuation of the event P. This is a concrete example of the steps 14 and 21 in FIG. 4 described above, and the number of repetitions N as one input is changed to one of the N1 to N3 forms of the code set shown in FIG. Convert. As in FIG. 7, in FIG. 7, the substitution expression “K (n) ← X;”
This means that the lower “n” bits of “X” are output as codes. “W” is temporary storage used for the process of generating the N3 code. When the N code generation process is started, that is, when a certain number of repetitions N is input, first, at step 60, it is determined whether or not the N value is less than “3”. That is, when N is “1” or “2”, in step 61, the N
The lower 4 bits of the value obtained by adding "12" to the value are output as a code, and the code generation processing ends. The code to be generated is 4 bits wide, and if the value of N is “1”, “13”, N
Is "14" when the value is "2", and it can be seen that there is no other than the N1 code and N2 code, respectively. If it is determined in step 60 that the run length value L is a value equal to or greater than "3", it is next determined in step 62 whether the N value is "3". If there is, in step 63, the lower 8 bits of the constant "222" are output as a code, and the code generation process ends. If the constant “222” is expressed in binary, it is “11011110”.
“1101” (N = 1) code and the N2 code “111”
0 "(N = 2), which corresponds to the value of N being" 3 "as described above.
The two codes may be higher and the N1 code may be lower. Therefore, the constant used in step 63 is "237".
That is, it may be a binary number “11101101”.

If it is determined in step 62 that the run length numerical value L is a numerical value equal to or greater than "4", first, in step 64, a numerical value "15" is output as a 4-bit code. If “15” is expressed in binary, “11”
11 ″, which is nothing but a constant for identifying the start of the N3 code.
A value obtained by subtracting “4” from the N value is substituted for W. Hereinafter, the control for generating the numerical part of the N3 code using the value of W is performed by first determining in step 66 whether the value of W is less than “8”. In step 67, the lower 4 bits of the value obtained by ANDing the W value and the constant "7" for each bit are output as a code, and then in step 68, the value of W is shifted to the lower side, that is, 3 bits to the right. The value is updated with the bit-shifted value.
Steps 67 and 68 are repeated until the value of “<8” is less than “8”.
Is smaller than "8", in step 69, the lower 4 bits of the value obtained by adding the constant "8" to W are output as a code, and the code generation process is terminated. If the constant “7” is expressed in binary, it is “0111”, and the code generated in step 57 is always “8”.
, Which indicates that the sign representing the numerical fragment of W is continuous. On the other hand, if the constant "8" is represented by a binary number, it is "1000", and the code generated in step 69 is always "1000". It becomes a numerical value of 8 "or more, which clearly indicates that the sign is the last one of the numerical part.

FIG. 9 is a flowchart showing an embodiment of control for inputting one code unit from the code string data generated by the above-mentioned encoding method and decoding it into a run-length numerical value or a repetitive numerical value. This is a concrete example of step 31 in FIG. 5 described above. From one input code unit, the decoded numerical value W and the contents of the W are the run-length numerical values (V =
0) or the number of repetitions (V = 1). In the figure, the substitution expression “K ← code input;” is such that four bits of code string data are sequentially substituted into the lower four bits of the temporary storage K, and “0” is added to the upper part according to the bit width of K. "Means what is replenished.
Note that “U” is temporary storage used for numerical restoration of the L3 code or the N3 code. When the numerical decoding process is started, first, in step 70, the first four bits of the code are input and substituted into K. Next, in step 71,
It is determined whether or not the K value is less than "13". As is apparent from FIG. 6, this discrimination identifies whether the target code for which the numerical value is to be restored is a run-length numerical value (K ≦ 12) or a repetitive numerical value (K> 12). If K is less than "13" in step 71, that is, if the sign is a run-length numerical value, first, step 7
In step 2, "0" is stored in the flag V to indicate that the value W to be decoded thereafter is a run-length numerical value. Next, at step 73, it is determined whether or not the K value is less than "10". If the K value is less than “10”, it is determined that the code is the L1 code.
Is substituted with a value obtained by adding "1" to the K value, and the numerical value decoding process is terminated. If K is equal to or greater than 10 in step 73, it is determined in step 75 whether the K value is "12". If the K value is not “12”, it is determined that the code is the L2 code.
In step 76, the value obtained by shifting K by 4 bits to the left is substituted for W, and the next 4 bits of code are read into K,
A value obtained by subtracting a constant “149” from the value obtained by adding the K to the W is substituted for W, and the numerical value decoding process ends. These processes for the L2 code are performed by converting the value of the 8-bit code to a constant “14”.
9 is used as the decoded value, and the inverse operation of step 53 in FIG. 6 in which the value obtained by adding a constant “149” to the run-length numerical value in the encoding is easily obtained. It can be understood that if the K value is "12" in step 75, it is determined that the code is the L3 code, so first in step 77 a constant "43" is stored in the temporary storage U. This is an offset value to be added in order to decode a numerical value obtained from the following numerical part into a run-length numerical value. In encoding, prior to encoding of the numerical part, a constant “4” is calculated from the run-length numerical value.
6 to reduce the value of "3". In the control for decoding the numerical value part, first, "0" is stored in W in step 82, and
In step 83, the next 4 bits of the code are read into K. Then, in step 84, it is determined whether or not the value of K is less than "8". The K value is added to
In step 84, the value of W is updated with a value shifted by 3 bits to the upper side, that is, to the left. Steps 83 to 86 are repeated until the value of K is less than "8" in step 84. When the value of K becomes equal to or more than "8" in step 87, K is added to W in step 87, the constant "8" is reduced, and the value obtained by adding the U value is substituted for W to perform numerical decoding processing. finish.

On the other hand, if K is equal to or greater than "13" in step 71, that is, if the code is the number of repetitions, "1" is first stored in the flag V in step 78,
This indicates that the value W to be decoded thereafter is the number of iterations. next,
In a step 79, it is determined whether or not the K value is "15". If the K value does not coincide with “15”, it is determined that the code is the N1 code or the N2 code. The process ends. Thus, it can be easily understood that the number of repetitions "1" is decoded when the input code is N1 ("13"), and the number of repetitions is "2" when the input code is N2 ("14"). If the K value is "15" in step 79, it is determined that the code is the N3 code. In step 81, "4" is assigned to the temporary storage U.
The numerical value is decoded using the control from step 82 to step 87 described above for the code, and is substituted for W, thereby terminating the numerical value decoding process. In the embodiment of the numerical value decoding control, the decoded numerical value W and the contents of the W are the run-length numerical values (V =
0) or a repetition value (V = 1). However, as described above, it is not necessary to separate the decoding control and the numerical decoding control, and it is rather natural to integrate them. The same thing can be said of the encoding procedure described with reference to FIG.
This also applies to the code generation procedure described using.
In the case of integration, there is no necessity to adopt the input / output method as described above, and it is possible to change to a simpler procedure. However, what procedure is ultimately optimal is largely dependent on the embodiment and can be easily optimized by those skilled in the art, so that detailed examples will be omitted. . In the above embodiment, the control procedure of the encoding and decoding method according to the present invention has been described. Hereinafter, a specific example of the encoding and decoding operations will be described with reference to the drawings.

FIG. 10 is a diagram for explaining an example of the encoding operation according to the present invention. As shown in the figure, the image data to be compressed starts with three dots of black,
An example is shown in which dots are white, and so on. The run length measurement shall start with white. In FIG.
Although zero run-length numerical values are shown, the run-length numerical value input first becomes "0" because the measurement starts from white, and thereafter, the ten numerical values shown continue, so that a total of 11 run-length numerical values are obtained. The length value will be entered. The table below the figure showing the ten run-length numerical values is a table for explaining the encoding operation in the order of steps. In the tabular form, the “stage” column is a column showing symbols for describing the encoding steps in steps from “S1” to “S12”. Each stage from "S1" to "S11" corresponds to a point in time when the total of 11 run-length numerical values have been input, and "S12" corresponds to a point in time at which encoding ends. The “L” column indicates the run length numerical value input at each time point from “S1” to “S11”, and the “B” column indicates the contents of the temporary storage B at each time point from “S1” to “S11”. In the “A” column, “S11” is used instead of “S1”.
Represents the contents of the temporary storage A at each time point of “L =
The “A” column indicates “L = L” at each time point from “S1” to “S11”.
A "represents whether or not A is satisfied. The case where" A "is satisfied corresponds to the occurrence of the event P, and the case where it is not satisfied (NO) corresponds to the occurrence of the event Q." N " The column indicates the contents of the temporary storage N at each time from "S1" to "S11", and the "sign generation" column indicates the contents of the codes to be generated up to the next stage. The “hexadecimal)” column indicates the generated code in hexadecimal.

As described above, the L values input from step S1 to step S11 are "0", "3",
"41", and the values shown in the table. The initial value “0” is substituted for A and B, and during the transition of each stage, A
Is substituted for the value of B, and the value of L is substituted for B, so that the values of A and B in steps S1 through S11 are as shown in the table. In steps S2, S3, and 9, L and A
Do not coincide with each other, and an event Q occurs. However, in other stages except for step S12, the event P coincides with each other and an event P occurs. Event P
Does not generate a code at each stage in which occurs, the value of the number of repetitions N is increased by “1”, and the value is reflected in the next stage. For example, as a processing result of the event P detected in step S1, no code is generated, and in step S2, N
= 1 is only reflected. Further, when five events P are consecutive as in steps S4 to S8, no code is generated in the corresponding period, and N is determined in step S9.
= 5 is only reflected.

At the stage S2 when the event Q first occurs, N
Is "1", first, an N1 code ('D') is generated, "0" is substituted for N, and then an L1 code ('2') representing "L = 3" is generated. Is done. Next, at the stage S3 when the event Q occurs, since the value of N has returned to "0", only the L2 code ('BE') representing "L = 41" is generated. Next, in the step S9 in which the event Q occurs, the value of N is "5".
A code ('F9') is generated, "0" is substituted for N,
Next, an L3 code ('C02E') representing “L = 443”
Is generated. In step S10 and step S11, two run-length numerical values are input. In both cases, the event P occurs, and the input is completed while the code generation is suspended. At the stage S12 when the input is completed, the value of N is "2", so the N2 code ('E') representing "N = 2"
Is generated, and the encoding is completed.

FIG. 11 is a diagram for explaining an operation example of L3 code generation according to the present invention. Step S9 of FIG.
The following describes an example of encoding the run-length value “L = 443” into a code “C02E” (hexadecimal number) corresponding to each stage of the code generation control in FIG. In the tabular form, the "stage" column is a column showing symbols for describing the code generation steps in steps from "T1" to "T10", and the numbers in parentheses are written in parentheses in FIG. Corresponding to the step symbol. The "value of W" column is a column indicating the value of the temporary storage W in each step in binary and decimal numbers. “Judgment of W <8”
The column is a column indicating the determination result of step 56 in FIG.
The “code generation (hexadecimal)” column is a column indicating the code generated at the corresponding stage in hexadecimal. When the encoding process is started, since L> 42, first, at step T1, 'C' (hexadecimal), which is a constant for identifying the L3 code, is output as a 4-bit code. Next, in step T2, the value "L-43", that is, "400" is substituted for W. Next, in step T3, since “W ≧ 8”, the following step T3
In step 4, the lower 4 bits of the logical product of W and the constant "7", that is, '0' (hexadecimal) is output as a sign, and the subsequent step T5
, A value obtained by shifting W to the right by 3 bits, ie, “50”
To update W. Next, in step T6, since “W ≧ 8”, in the following step T7, the lower 4 bits of the logical product of W and the constant “7”, that is, '2' (hexadecimal) is output as a sign, and the following step T8 , The W is updated with a value obtained by shifting W to the right by 3 bits, that is, “6”. Next, in step T9, since “W <8”, in the subsequent step T10, W
, The lower 4 bits of the value obtained by adding “8” to the output, that is, 'E' (hexadecimal number) is output as a code, and the coding is completed.

FIG. 12 is a diagram for explaining an example of data decoding operation. An example will be described in which code string data output as a result of the encoding operation example shown in FIG. 12 is sequentially input, and an alternate run-length value sequence is output for each color. In the tabular form, the “stage” column shows a symbol for describing the decoding step by steps from “Y1” to “Y14”, and “code input (16
Column) shows the code inputted at the corresponding stage in hexadecimal, the column "L" shows the run length numerical value, and the column "N"
The column represents the value of the temporary storage N of the number of iterations at each time point,
The “B” column represents the value of the temporary storage B at each time point, and the “A” column represents the value of the temporary storage A at each time point. When decoding is started, “0” is substituted into A and B as initial values. Next, in step Y1, the code 'D' is read, and since this is an N1 code, "1" which is a decoded value of the code is substituted for N. Since the input is the number of repetitions, the value of A is substituted into L and output as a run-length numerical value in step Y2, and N is subtracted from N by "1". And B is updated with the value of L. Since N has become "0", next, in step Y3, code "2" is read. Since this is an L1 code, "3" which is the decoded value of the code is substituted for L, and the run-length numerical value is obtained. And updates A with the value of B and B with the value of L, respectively.

Next, in step Y4, the code 'BE' is read, and since this is an L2 code, the decoded value of the code "41" is substituted for L and output as a run-length value, and A is output. With the value of B, B is updated with the value of L, respectively. Next, at step Y5, the code 'F9' is read, and since this is an N3 code, “5” which is the decoded value of the code is substituted for N. Next, in steps Y6 to Y10, the value of A is substituted for L and output as a run length numerical value.
Is updated with the value of L for a total of five times until N becomes “0”. Next, in step Y11, the code 'C02E' is read, and since this is an L3 code,
Substitute “443”, which is the decoded value of the code, into L, and output it as a run-length numerical value. Since the input is the number of repetitions, next, in step Y12, the code 'E' is read. Since this is an N2 code, "2" which is the decoded value of the code is substituted for N. Since the input is the number of iterations,
Next, in steps Y13 to Y14, the value of A is substituted into L and output as a run-length numerical value. N is a value obtained by subtracting "1" from N, A is the value of B, and B is the value of L. Are repeated two times in total until N becomes "0". It is apparent from the "L" column of the table that, by the above operation, a total of 11 run-length numerical values input to the encoding processing in the example of FIG. 12 are sequentially decoded.

[0048]

According to the present invention, as described above, according to the first aspect, the number of codes to be generated is reduced, and the period in which colors are short, such as a pseudo halftone image obtained by computer processing, is reduced. Thus, it was possible to provide an encoding method capable of obtaining a sufficiently high compression ratio even for image data that frequently changes. According to the second aspect, the control is performed by software processing by a microprocessor, so that a sufficiently high processing speed can be expected. Therefore, the control is realized by simple control such as assignment, addition, and comparison / branch. And a coding method that can perform the above. According to the third aspect, judgment and branching based on color are unnecessary, and substitution and comparison are performed so that a sufficiently high processing speed can be expected even if the control is performed by software processing by a microprocessor. -It has been possible to provide an image data encoding method which can be realized by simple control such as branching. According to the fourth aspect, it is possible to provide an encoding method that eliminates the need for a code representing that the run-length value is 0, and thus makes it possible to use a code set having a higher compression ratio.

According to the fifth aspect, an image data encoding apparatus capable of achieving a higher compression rate can be provided. According to claim 6, even if the control is performed by software processing by a microprocessor, a simple control such as substitution, subtraction, and comparison / branch can be realized so that a sufficiently high processing speed can be expected. Has been simplified and an extremely high-speed image data encoding apparatus can be provided. According to the seventh aspect, it is possible to provide an image data encoding device that can expect an extremely high processing speed. According to the eighth aspect, a data recording system using an image data encoding method applicable to various cases can be provided. According to the ninth aspect, a high-speed and memory-saving printer can be provided.

According to the tenth aspect, it is possible to provide a data decoding method capable of achieving quick and memory saving. According to the eleventh aspect, a memory-saving and quick image data decoding method can be provided. According to the twelfth aspect, it is possible to provide a decoding device capable of quickly decoding image data with a small amount of memory. According to the thirteenth aspect, a data decoding device capable of quick data decoding and saving memory can be provided. According to the fourteenth aspect, it is possible to provide a data decoding device that can perform data processing at a high processing speed and can also be used as a memory inherent in a processor, and save memory. According to the fifteenth aspect, a code set that does not require a special table reference at the time of encoding generation, and that can realize such processing by simple control such as assignment, addition / subtraction, shift, logical product, and comparison / branch is introduced. Therefore, it is possible to provide an image data encoding method that can expect a sufficiently high processing speed even if the control is performed by software processing by a microprocessor. Furthermore, each code to be introduced has a code length of 4 bits or a multiple thereof so that the processing can be easily implemented in hardware. By combining hardware processing and software processing, the same encoding method can be used. An image data encoding method that can be adapted to a wide performance range can be provided.

According to the sixteenth aspect, there is no need to refer to a special table at the time of numerical decoding, and these processes are substituted.
A code set that can be realized by simple control such as addition, subtraction, shift, logical product, and comparison / branch is introduced. A method for decoding data can be provided. Furthermore, each code to be introduced has a code length of 4 bits or a multiple thereof so that the processing can be easily implemented in hardware. By combining hardware processing and software processing, the same decoding method can be widely used. A method for decoding image data that can be adapted to the performance range can be provided. According to the seventeenth aspect, an image data encoding device capable of performing extremely efficient data processing in image encoding can be provided. According to claim 18,
An image data decoding device capable of performing extremely efficient data processing in image decoding can be provided. Claim 1
According to No. 9, it was possible to provide an image data recording system capable of appropriately coping with an image having a violent alternation of colors such as a pseudo halftone. According to the twentieth aspect, it is possible to provide an image forming apparatus that can appropriately cope with an image having a violent alternation of colors such as a pseudo halftone. According to claims 21 and 22, the program can be read by a computer by using the recording medium, and the program can be executed.

[Brief description of the drawings]

FIG. 1 is an explanatory diagram for explaining a basic principle of the present invention.

FIG. 2 is a configuration diagram illustrating an embodiment in which an encoding device and a decoding device according to the present invention are applied to an image forming apparatus.

FIGS. 3A and 3B are explanatory diagrams showing an encoding device and a decoding device of the present invention.

FIG. 4 is a flowchart illustrating an embodiment of an encoding method according to the present invention.

FIG. 5 is a flowchart illustrating an embodiment of a decoding method according to the present invention.

FIG. 6 is a diagram showing one embodiment of a code set used in the encoding / decoding method of the present invention.

FIG. 7 is a flowchart illustrating an embodiment of control for generating a run-length code in response to an event Q according to the present invention.

FIG. 8 is a flowchart showing an embodiment of control for generating an N code corresponding to the number of repetitions in response to an event P or a continuation of the event P according to the present invention.

FIG. 9 is a flowchart illustrating an example of control for inputting one code unit from code string data generated by the encoding method according to the present invention and decoding the code unit into a run-length numerical value or a repetitive numerical value.

FIG. 10 is an explanatory diagram illustrating an operation example of encoding according to the present invention.

FIG. 11 is an explanatory diagram illustrating an operation example of L3 code generation according to the present invention.

FIG. 12 is an explanatory diagram illustrating an operation example of data decoding according to the present invention.

[Explanation of symbols]

1 printer device, 2 host machine, 3 host I
/ F, 4 controllers, 5 operational panels, 6 panel I / F, 7 font ROM, 8NV-
RAM, 9 optional RAM, 10 engine I /
F, 11 printer engine, 12 input device, 13
Recording medium, 14 program ROM, 15 RAM, 16
CPU, 17 encoding device, 18 decoding device, 19
Run-length storage means A, 20 run-length storage means B, 21 run-length storage means L, 22 discriminating means,
23 repetition number storage / operation means, 24 run length code generation means, 25 repetition number code generation means, 26 encoding means, 27 decoded numerical value / attribute determination storage means, 28 decoding means, 29 run length numerical value generation means

Claims (22)

[Claims] An encoding method for inputting an alternate run-length numerical sequence for each color obtained by scanning data, converting the run-length numerical sequence into a predetermined code sequence, and outputting the code sequence, wherein a predetermined run-length numerical value is input. At times, the case where the value of the run-length value matches the immediately preceding run-length value of the same color is set as a coincidence event, and an event that does not match is set as a non-match event, and the number of consecutive matching events is set as the number of repetitions. When a coincidence event or a series of coincidence events occurs, a repetition number code corresponding to the repetition number is generated, and when the mismatch event occurs, a code indicating the value of the run-length numerical value is generated. Data encoding method. 2. A control content for generating a code corresponding to the number of repetitions for the coincidence event or a series of coincidence events, and generating a code indicating the value of the run-length numerical value for the mismatch event. Comprises an initialization step of storing an initial value in a repetition number storage means for storing the repetition number, and increasing a value of the repetition number stored in the repetition number storage means in response to the occurrence of the coincidence event. If the value of the number of repetitions stored in the number of repetitions stored in the number-of-repetitions storage unit is not an initial value in response to the occurrence of the mismatch event at that time, a code indicating the value of the number of repetitions is output. A code generation step of returning the value of the number of repetitions stored in the number-of-repetitions storage unit to an initial value, and generating a code indicating the value of the run-length numerical value when the number of repetitions is the initial value; Encoding of Until the repetition step of repeating the increasing step and the code generation step, and when the coding of the data to be coded is completed, if the value of the number of repetitions is not the initial value, A code output step of outputting a code indicating a value. 3. The control for discriminating a coincidence event and a non-coincidence event is performed by storing a predetermined initial value in a run-length value storage unit A and a run-length value storage unit L for storing and referring to run-length numerical values for the number of colors. At the initialization stage for storing, and when the predetermined run-length value is input to each of the run-length value storage means L, the run-length value matches the value stored in the run-length value storage means A. An identification step for identifying a case as a coincidence event and a non-coincidence as a non-coincidence event. After the identification step, the run-length value is stored in the run-length value storage means A at a time before the next run-length value input. Storing the value of the predetermined run length numerical value in the run length value storing means L after storing the value of the length value storing means L. The data encoding method according to claim 1 or 2. 4. In the initialization stage of the control for identifying the coincidence event and the non-coincidence event, the run-length value storage means A starts with a color different from the target color when the run-length measurement is started. 4. The data encoding method according to claim 3, wherein an initial value is set. 5. An encoding device for inputting an alternate run-length numerical sequence for each color obtained by scanning data, converting the run-length numerical sequence into a predetermined code sequence, and outputting the code sequence. A run length value storage means L for storing the run length value, and a run length value storage means A for storing the immediately preceding run length value of the same color as the run length value
Determining means for determining whether or not the value of the run-length value matches the immediately preceding run-length value of the same color; and determining whether the value of the run-length value matches the immediately preceding run-length value of the same color. A repetition number storage means for storing the number of repetitions to be repeated, a repetition number code generating means for generating a code indicating the number of repetitions, and if the value of the run length value does not match the immediately preceding run length value of the same color, A data encoding apparatus comprising: run length code generation means for generating a code indicating the value of the run length numerical value. 6. Data encoding for generating a code indicating the value of the run-length numerical value corresponding to the mismatch event, and generating a code corresponding to the number of repetitions corresponding to the matching event or a series of matching events. An apparatus, comprising: a repetition number storage means for storing a repetition number; a repetition number calculation means for increasing a value of the repetition number each time the coincidence event occurs; and an occurrence of the mismatch event when the mismatch event occurs If the value of the number of iterations at the time is not the initial value,
A run-length code generation unit that returns a value of the number of repetitions to an initial value after outputting a code indicating the value of the number of repetitions, and generates a code indicating the value of the run-length value at the time when the number of repetitions is the initial value. A control unit for performing control to repeat the operation of each unit until the encoding of the data to be encoded is completed, and a case where the value of the number of repetitions is not the initial value at the time when the encoding of the target data is completed. 6. The data encoding apparatus according to claim 5, further comprising: a repetition number code generation unit that outputs a code indicating the value of the repetition number. 7. A run length value storage means L for inputting and storing the run length value, a run length value storage means A for storing a run length value immediately before the same color as the run length value, and a repetition number. 7. The data encoding device according to claim 5, wherein the repetition number storage means is constituted by a general-purpose register of a microprocessor. 8. An image data recording system, wherein the data encoding method according to any one of claims 1 to 4 is applied to an image forming apparatus. 9. An image forming apparatus according to claim 8,
An image data recording system, being a printer. 10. The method according to claim 1, wherein:
A data decoding method for inputting a code string obtained by scanning code string data generated using the data encoding method described in the section, decoding the data into an alternate run-length numerical string for each color, and outputting the decoded data. If the input code string is a code generated by the run-length code generation means, a run-length value represented by the code is output, and the input code string is generated by the repetition number code generation means. In the data decoding method, the run-length numerical value immediately before the same color is output for the number of repetitions represented by the repetition number code. 11. The data decoding method according to claim 10, wherein the decoding side run length value storage means A and the decoding side run length value storage means L for storing and referring to the run length numerical values for the number of colors. An initialization step of storing the same initial value as at the time of initialization, a step of inputting / decoding a predetermined code to obtain a numerical value indicated by the code and its attribute, and the attribute of the numerical value indicated by the code is the run-length code. In this case, the numerical value indicated by the code is output as a run-length numerical value, and the contents of the decoding-side run-length value storing means L are stored in the decoding-side run-length value storing means A. Storing the run length numerical value in the storage means L; and, if the attribute of the numerical value indicated by the code is the repetition code, storing the run number in the repetition number storage means for storing and referring to the repetition number. Until the value of the number of iterations becomes the initial value, and outputs the numerical value stored in the decoding side run-length value storage means A as a run-length numerical value;
After storing the value stored in the decoding-side run-length value storage unit L in the decoding-side run-length value storage unit A, the run-length value or the decoding-side run is stored in the decoding-side run-length value storage unit L. Storing the value stored in the length value storage means A and repeating the process of reducing the value stored in the repetition number storage means by a predetermined value; and until the data of the code string to be decoded ends, A data decoding method comprising: a step of inputting and decoding a predetermined code unit to obtain a numerical value indicated by the code and its attribute, and a step of repeating a process of reducing the value of the number of repetitions by a predetermined value. . 12. A data decoding apparatus using the data decoding method according to claim 11, wherein code string storage means for storing an input code string for each code unit, and wherein the code of the code unit is the run-length code. A run length value generating means for generating a run length numerical value represented by the run length code when the code is a code; and a run length value storing means for decoding when the input code unit is the repetition number code. A data decoding apparatus comprising: run-length value output means for outputting the run-length numerical value immediately before the same color stored in A for the number of repetitions represented by the code. 13. The data decoding apparatus according to claim 12, wherein said decoding-side run-length value storage means A and said decoding-side run-length value storage means L for storing and referring to run-length numerical values for the number of colors. , A decoded numerical value obtained by inputting and decoding a predetermined code unit to obtain a numerical value indicated by the code and its attribute
When the attribute of the numerical value decoded by the attribute discriminating means and the decoded numerical value / attribute discriminating means is the run-length code, the numerical value is output as a run-length numerical value. If the attribute of the decoded numerical value is the repetition number code, the value stored in the decoding side run length value storage means A is output as a run length numerical value until the value of the repetition number becomes an initial value. A run-length value generating unit that performs decoding, if the attribute of the numerical value decoded by the decoded numerical value / attribute determining unit is the repetition number code, a decoding-side repetition number storage unit that stores and stores the numerical value; A repetition number calculating means for repeating the process of reducing the value of the repetition number stored in the decoding side repetition number storage means in accordance with the repetition number, and control for storing the same initial value in each of the storage means as at the time of encoding;
After storing the value stored in the decoding-side run-length value storage means L in the decoding-side run-length value storage means A, the run-length value or the decoding-side run is stored in the decoding-side run-length value storage means L. Control means for storing the value stored in the length value storage means A, and control means for controlling the repetition number operation means to repeatedly operate until the data of the code string to be decoded is completed. Data decoding device. 14. A decoding-side run-length value storage means L for inputting and storing a run-length value, a decoding-side run-length value storage means A for storing the immediately preceding run-length value of the same color as the run-length value, 14. The data decoding apparatus according to claim 12, wherein the number-of-repetitions storage means for storing the number is constituted by a general-purpose register of a microprocessor. 15. The first code encoded by the data encoding method has a 4-bit width, is identified by the fact that the 4-bit value is less than 10, and adds 1 to the value. The value is a form of the code corresponding to the run-length numerical value, and the second code has an 8-bit width, and is identified by the value of the preceding upper 4 bits in the code string being a predetermined value of 10 or more. A value obtained by adding 11 to the value of the lower 5 bits is a form of the run-length code corresponding to the run-length numerical value, and the third code has a bit width of at least 8 bits and a multiple of 4; The leading 4 bits in the code string are identified by being a predetermined value of 10 or more.
For each of the 4 bits following the bit, the value obtained by adding 43 to the numerical value obtained by concatenating the lower 3 bits of each 4 bits upwards until the numerical value of 8 or more is detected in the 4-bit value corresponds to the run length numerical value. The fourth code has a 4-bit width, and the 4-bit value is 1
The fifth code has a 4-bit width, and is identified by being a predetermined value equal to or greater than 0, and is a form of the code corresponding to the number of repetitions being 1.
A sixth code is identified by being a predetermined value equal to or greater than 0, and is a form of the code corresponding to the number of repetitions being 2. The sixth code has a bit width of at least 8 bits and a multiple of 4. Then, the value of the preceding upper 4 bits in the code string is identified by being a predetermined value of 10 or more.
For each of the 4 bits following the bit, the value obtained by adding 4 to the number obtained by concatenating the lower 3 bits of each 4 bits upward until a value of 8 or more is detected in the 4-bit value corresponds to the number of repetitions. The data encoding method according to claim 1, wherein the data encoding method is a form of the repetition number code. 16. A first code decoded by the data decoding method has a 4-bit width, is identified by the fact that the 4-bit value is less than 10, and a value obtained by adding 1 to the value is a run-time value. A second code having a width of 8 bits, identified by a value of the preceding upper 4 bits in the code string being a predetermined value of 10 or more, and A value obtained by adding 11 to the value of the bit is one form of the run-length code corresponding to the run-length numerical value. The third code has a bit width of at least 8 bits and a multiple of 4, and It is identified that the value of the preceding upper 4 bits is a predetermined value of 10 or more.
For each of the 4 bits following the bit, the value obtained by adding 43 to the numerical value obtained by concatenating the lower 3 bits of each 4 bits upwards until the numerical value of 8 or more is detected in the 4-bit value corresponds to the run length numerical value. The fourth code has a 4-bit width, and the 4-bit value is 1
The fifth code has a 4-bit width, and is identified by being a predetermined value equal to or greater than 0, and is a form of the code corresponding to the number of repetitions being 1.
A sixth code is identified by being a predetermined value equal to or greater than 0, and is a form of the code corresponding to the number of repetitions being 2. The sixth code has a bit width of at least 8 bits and a multiple of 4. Then, the value of the preceding upper 4 bits in the code string is identified by being a predetermined value of 10 or more.
For each of the 4 bits following the bit, the value obtained by adding 4 to the number obtained by concatenating the lower 3 bits of each 4 bits upward until a value of 8 or more is detected in the 4-bit value corresponds to the number of repetitions. 12. The data decoding method according to claim 10, wherein the repetition number code is in one form. 17. The apparatus according to claim 5, further comprising: an encoding unit configured to generate the first to sixth codes.
Or the data encoding device according to 6. 18. The apparatus according to claim 12, further comprising decoding means for decoding the first to sixth codes.
Or the data decoding device according to 13. 19. An image data recording system, wherein the data decoding method according to any one of claims 10, 11, and 15 is applied to an image forming apparatus. 20. An image data recording system according to claim 19, wherein the image forming apparatus is a printer. 21. A computer-readable recording medium on which a program for causing a computer to execute the data encoding method according to claim 1 is recorded. . 22. A computer-readable recording medium storing a program for causing a computer to execute the data decoding method according to claim 10. Description: