JPH11119763A - Bit map high-efficiency encoding system - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a bit map high-efficiency encoding system which can improve the encoding efficiency. SOLUTION: A laterally successive data detection part 15 scans the character color area of bit map data in a bit map data storage memory 11 laterally and a longitudinally successive data detection part 14 scans the character color area of the bit map data longitudinally. On the basis of the data obtained by weighting those data, lateral and longitudinal intermediate decoded data are generated and stored in an intermediate decoded data storage memory 12. Those intermediate decoded data and the difference data obtained by subtracting those intermediate decoded data from the source data are encoded by a run- length encoder 17. At the time of this run-length encoding, pixels less than pixels, which are not in the character color area, are assigned to the pixels in the character color area.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a bitmap high-efficiency encoding system, and more particularly to a bitmap high-efficiency encoding system for efficiently encoding a bitmap in all devices that need to hold bitmap data. .

[0002]

2. Description of the Related Art In a conventional bitmap high-efficiency encoding system, in a device which needs to hold bitmap data (font data), when bitmap data which is image data relating to a font is encoded and held, the data is stored. In order to reduce the capacity as much as possible, run-length encoding is performed and stored. That is, conventionally, for example, variable-length pixels indicating the number of pixels continuous in the vertical or horizontal direction with respect to data obtained by scanning quantized bitmap data in a predetermined vertical or horizontal direction. When,
Variable-length coding using a run-length coding method that obtains a coded output consisting of pixels indicating the value of continuous pixels and pixels having a predetermined number of pixels corresponding to the number of continuous pixels, and the obtained coding Data is output as a pixel stream.

[0003]

However, in the conventional bitmap high-efficiency encoding method, when encoding bitmap data, scanning is performed in a predetermined vertical or horizontal direction regardless of font characteristics. Since the obtained data is encoded, there is a problem that encoding efficiency is poor.

[0004] The present invention has been made in view of the above points,
It is an object of the present invention to provide a bitmap high-efficiency coding scheme capable of improving coding efficiency.

[0005]

According to the present invention, a first storage means for storing bitmap data to be encoded and a bitmap data stored by the first storage means are vertically stored. Vertical intermediate decode data and horizontal intermediate decode having horizontal and vertical lengths of 1 respectively from vertical and horizontal weighted data obtained by separately scanning in the direction and the horizontal direction and further weighting. Generating means for respectively generating data, second storage means for storing vertical intermediate decode data and horizontal intermediate decode data, respectively, bitmap data from the first storage means, and vertical intermediate decode from the second storage means Calculating means for calculating difference data between the data and the horizontal intermediate decoded data; vertical and intermediate decoded data and horizontal intermediate obtained by the difference data and the generating means; And code data is obtained by a structure having encoding means for run-length encoding, respectively.

In the present invention, the bitmap data of the original font to be encoded is scanned in each of the horizontal and vertical directions, and weighting data relating to the length information of the obtained character area is generated. Since vertical intermediate decoded data using a pixel row of one pixel, horizontal intermediate decoded data using a pixel row of one pixel in the vertical direction, and difference data are generated, the vertical intermediate decoded data is generated according to the characteristics of the font. Run-length encoding can be performed on the horizontal intermediate decoded data and the difference data. In particular, since these data often have a shorter length in the colored area than in the non-colored area, by assigning fewer bits to the colored area in the run-length coding than in the non-colored area, the coding efficiency of the bitmap data can be improved. Can be raised.

[0007]

Next, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of an encoding device used in a bitmap efficient coding system according to the present invention. As shown in the figure, the encoding apparatus of this embodiment includes a bitmap data storage memory 11 for storing input bitmap data (original data) to be encoded, and an intermediate memory for storing intermediate decode data to be described later. A decoded data storage memory 12, a bitmap calculator 13, and a vertical continuous data detector 14 that scans the bitmap in the vertical direction and detects the length of a continuous character color area.
A horizontal direction continuous data detection unit 15 that scans the bit map in the horizontal direction and detects the length of a continuous character color area; a weighting operation unit and a memory 16 that performs a weighting operation and stores the weighted data; A run-length encoder 17 for performing run-length encoding on the obtained data and outputting the encoded data;
It comprises a data control unit 18 that controls each unit collectively.
These are connected to each other via a bus 19.

The data control unit 18 has a central processing unit (CP)
U) 181, a read-only memory (ROM) 182 storing a program executed by the CPU 181 for performing a predetermined encoding operation described later, and a work area for executing an encoding algorithm. And a random access memory (RAM) 183. The data control unit 18 selects either horizontal or vertical run-length encoding for the character color area based on the horizontal and vertical length information of the character color area of the input bitmap, and executes the run-length code. Table 17
In the run-length encoding, a smaller number of pixels are assigned to pixels in the character color area than pixels other than the character color area, and only the number of pixels other than the character color area is encoded for a character color area having a length of 1 in the horizontal and vertical directions. I do.

An outline of the operation of this embodiment will be described. For example, a case where kanji bitmap data (font data) shown in FIG. 2 is input and stored in bitmap data storage memory 11 , The horizontal continuous data detector 15 scans the character color area of the bitmap data in the horizontal direction.
4 scans the character color area of the bitmap data in the vertical direction.

[0010] Based on the data obtained by these scans and the data obtained by weighting them, horizontal intermediate decode data as shown in FIG. 3 is generated. The intermediate decode data in the vertical direction as shown is generated and stored in the intermediate decode data storage memory 12, respectively. However, a character area having a length of 1 in the vertical and horizontal directions as shown in FIG. 6 is not included in any of the intermediate decoded data in the vertical and horizontal directions.

Then, the data control unit 18 obtains the sum information (FIG. 5) of the intermediate decoded data of FIGS. 3 and 4, and then obtains the original bitmap data shown in FIG. 2 and the sum information shown in FIG. And the difference data with respect to. This difference data is shown in FIG. Subsequently, the data control unit 18 causes the run-length encoder 17 to horizontally encode the intermediate decode data in the horizontal direction in FIG. 3 in the horizontal direction, and converts the intermediate decode data in the vertical direction in FIG. 4 to the run-length code in the vertical direction. The difference data shown in FIG. 6 is run-length encoded. Note that, at the time of run-length encoding by the run-length encoder 17, a smaller number of pixels are assigned to pixels in the character color area than pixels outside the character color area.

In this embodiment, a memory 11 for storing original data for storing original data, and an intermediate decoded data for storing the original data in order to decompose the run length coding into an area to be applied in the vertical direction and an area to be applied in the horizontal direction. Memory 12 to store
And three types of memories for storing weighting data.

The intermediate decode data storage memory 12 stores the intermediate value of the sum of the vertical intermediate decode data for recording the color area for performing the vertical run length and the horizontal intermediate decode data for recording the color area for performing the horizontal run length. This is a memory for storing decoded data. Further, the weighting data includes, for each pixel in the bitmap data, vertical weighting data which is an integer array having length information continuous in the vertical direction as elements, and integer weighting data having length information continuous in the horizontal direction as elements. The horizontal weighting data, which is an array, is stored in the weighting calculation unit and the memory part of the memory 16.

Next, the operation of this embodiment will be described in more detail with reference to the flowchart of FIG. It is assumed that input bitmap data (original data) is stored in the bitmap data storage memory 11. First, the data control unit 11 initializes intermediate decoded data in the intermediate decoded data storage memory 12 (Step 101).

Subsequently, the character color area of the difference data between the original data and the intermediate decoded data is detected by the horizontal continuous data detecting unit 15.
To detect horizontal continuous length information including pixels of all the character color areas, and stores it in the memory as horizontal weighting data in the weighting calculation unit and the memory 16 (step 102). . Similarly, the character color area of the difference data between the original data and the intermediate decoded data array is scanned in the vertical direction by the vertical continuous data detection unit 14, and the continuous length information including the pixels of all the character color areas in the vertical direction is obtained. Is stored in the memory as vertical weighting data by the weighting calculation unit and the memory 16 (step 103).

Here, first, since the intermediate decoded data array is initialized in step 101, only the original data is scanned in the horizontal and vertical directions, respectively,
6 is weighted data. For example, when the original data is a Chinese character "", the horizontal weighting data array is as shown in FIG. 8 and the vertical weighting data array is as shown in FIG. In FIG. 8, the numerical value indicates the number of pixels in the character region that is continuous in the horizontal direction, the numerical value in FIG. 9 indicates the number of pixels in the character region that is continuous in the vertical direction, and the positions of the numerical values in FIGS. Indicates a colored pixel position.

Subsequently, the maximum value maxlenv of the vertical weighting is obtained from the vertical weighting data array (step 104), and the maximum value maxlenh of the horizontal weighting data is obtained from the horizontal weighting data array (step 105). Here, the maximum value m of the vertical weighting data
axlenv is “6” as shown in FIG. 9, and the maximum value maxlenh of the horizontal weighting data is “5” as shown in FIG.

Subsequently, the above-mentioned maxlenv and maxl
It is determined whether at least one of enh is 2 or more (step 106), and if either one is 2 or more, it is determined whether maxlenv ≧ maxlenh (step 107). Here, maxlen
Since v = 6 and maxlenh = 5, maxlen
Since v ≧ maxlenh, the character color area (corresponding pixel) for which the original data and the intermediate decoded data (vertical) are determined to be run-length is copied to the vertical intermediate decoded data array (step 108).

Thereafter, the sum of the vertical intermediate decode data array and the horizontal intermediate decode data array is compared with the bitmap calculator 1.
3 and store it as intermediate decoded data in the intermediate decoded data storage memory (step 109).
Returning to step 102, vertical weighting data is obtained again based on the original data and the intermediate decoded data.

When maxlenv <maxlenh, the character color area (corresponding pixel) for which the run length is determined to be applied to the original data and the intermediate decoded data (horizontal) is copied to the horizontal intermediate decoded data array (step 108), the bitmap calculator 13 calculates the sum of the vertical intermediate decoded data array and the horizontal intermediate decoded data array, and stores this in the intermediate decoded data storage memory as intermediate decoded data (step 109).

In step 102, the character color area of the difference data between the original data and the intermediate decoded data array is scanned in the horizontal direction to generate horizontal weighting data. In step 103, the difference between the original data and the intermediate decoded data array is generated. Since the character color area of the data is scanned in the vertical direction to generate vertical weighted data, the maximum value maxlenv or m is calculated every time the processing in steps 102 and 103 is performed.
The axlenh decreases and finally becomes 1 at the end. If it is determined in step 106 that both the maximum values maxlenv and maxlenh are 1, the length of the colored region in the vertical direction and the horizontal direction is 1, so that only the intermediate decoded data of the non-colored region is processed by the run-length encoder 17. Each is run-length encoded (steps 111 and 11).
2).

Here, run-length encoding is performed on each of the pixels. Since a colored region often has a shorter length than a non-colored region, a run-length code is assigned by allocating fewer pixels than the non-colored region. Increase the efficiency of conversion. Finally, the difference between the original data and the intermediate decoded data is obtained (step 113), and the difference data is run-length encoded (step 114). At this time, since the horizontal and vertical lengths of the colored area are 1, only the length of the non-colored area is encoded.

Since such a method is used, pixels coded by single pixel coding have higher coding efficiency than run-length coding of the original data. Therefore, when the run-length encoding direction is determined, the following optimization is performed. By comparing the original data and the intermediate decoded data, if the start position and the end position of the color region that is continuous in the vertical or horizontal direction match, it is considered that the intermediate decoded data has already been copied, and a new No data is copied to

If only one of the end position and the start position of a colored area in which the original data and the intermediate decoded data are continuous in the horizontal direction respectively, they are handled as a single pixel. If the start position and the end position of the colored region where the original data and the intermediate decoded data are respectively continuous in the horizontal direction do not coincide with each other, it is treated as a plurality of pixels.

[0025]

Next, the operation of this embodiment will be described in more detail.
This will be described in detail. FIG. 10 shows the shift of each array when the bitmap data "B" of the alphabet is encoded by the method of the present invention. First stage 1 (STAG
In E1), a font of 6 pixels horizontally and 7 pixels vertically is used.
B "bitmap data (original data) 201 is input and stored in the bitmap data storage memory (11 in FIG. 1). Here, an example of one bit per pixel is shown, but one bit per pixel is shown. The same applies to a plurality of bits, and since the intermediate decoded data is initialized (Step 101 in FIG. 7), the horizontal intermediate decoded data 202 and the vertical intermediate decoded data 203 are all set to 0.

Therefore, the difference data between the original data 201 and the horizontal intermediate decoded data 202 and the difference data between the original data 201 and the horizontal intermediate decoded data 202 are all the same as the original data 201, and this is determined in step 102 in FIG. When the horizontal direction weighting data is generated by scanning the character color area of the difference data in the horizontal direction, the horizontal weighting data as indicated by 204 in FIG. 10 is generated, and the character color area is scanned in the vertical direction in step 103 of FIG. Then, when the vertical weighting data is generated, vertical weighting data as indicated by 205 in FIG. 10 is generated. These horizontal weighting data 204,
The value of each pixel of the vertical weighting data 205 is
"1" of 1 indicates a continuous value, and the pixel position is "1".
Is the pixel position where exists.

As shown in FIG. 10, the vertical weighting data 2
05 is "6" and the maximum value maxlenh of the horizontal weighting data 204 is "4".
Since nv> maxlenh, the character color area determined to be run-length from the original data to the vertical intermediate decoded data is copied (steps 104 to 10 in FIG. 7).
8). As a result, the vertical intermediate decoded data is 2 in FIG.
As indicated by reference numeral 06, “1” at the pixel position (character color area determined to perform run length) of the maximum value of the vertical weighting data 205 in the original data 201 is copied data.

On the other hand, the horizontal intermediate decode data is shown in FIG.
The original data indicated by 02 remains unchanged. The vertical intermediate decoded data 206 and the horizontal intermediate decoded data 202 are added to form intermediate decoded data (step 1 in FIG. 7).
09).

Next, difference data between the original data 201 and the above-mentioned intermediate decoded data is obtained. This difference data is data in which the second column from the left in the original data 201 is all 0 as indicated by 207 as difference data of stage 2 (STAGE 2) in FIG. The difference data 207 is scanned in the horizontal direction and weighted to generate horizontal weighting data indicated by 208 in FIG. 10 (step 102 in FIG. 7), and is also scanned in the vertical direction and weighted. As a result, FIG.
209 is generated (step 103 in FIG. 7).

As shown in FIG. 10, the vertical weighting data 2
09 is “2”, and the maximum value maxlenh of the horizontal weighting data 208 is “3”.
Since nv <maxlenh, the character color area determined to be run-length from the original data to the horizontal intermediate decoded data is copied (steps 104 to 10 in FIG. 7).
7, 110).

As a result, the horizontal intermediate decoded data is
As indicated by 210 at 0, “1” at the pixel position of the maximum value of the horizontal weighting data 208 of the original data 201 (the character color area determined to perform run length) is copied.
The other areas are all zero data.
On the other hand, the vertical intermediate decoded data 206 remains unchanged.
The vertical intermediate decoded data 206 and the horizontal intermediate decoded data 210 are added to form intermediate decoded data (step 109 in FIG. 7).

Next, difference data between the original data 201 and the above-mentioned intermediate decoded data is obtained. This difference data is the first data of the original data 201 as indicated by 211 as the difference data of the stage 3 (STAGE 3) in FIG.
The third, sixth, and sixth rows are all 0 data. The difference data 211 is scanned in the horizontal direction and weighted to generate horizontal weighting data indicated by 212 in FIG. 10.
2) In addition, by performing vertical scanning and weighting, vertical weighting data indicated by 213 in FIG. 10 is generated (step 103 in FIG. 7).

As shown in FIG. 10, the vertical weighting data 2
13 is “2”, and the maximum value maxlenh of the horizontal weighting data 212 is “1”, so that the maximum value maxlenv is “2” or more, and
Since nv> maxlenh, the character color area determined to be run-length from the original data to the vertical intermediate decoded data is copied (steps 104 to 10 in FIG. 7).
8).

As a result, the vertically intermediate decoded data is
As indicated by 214 at 0, “1” at the pixel position of the maximum value of the vertical weighting data 213 (the character color area determined to perform run length) in the original data 201 is included in the latest vertical intermediate decoded data 206. The data is copied.

On the other hand, the horizontal intermediate decoded data is shown in FIG.
The original data indicated by 10 remains. The vertical intermediate decoded data 214 and the horizontal intermediate decoded data 210 are added to form intermediate decoded data (step 1 in FIG. 7).
09).

Next, difference data between the original data 201 and the above-mentioned intermediate decoded data is obtained. This difference data is data in which only the sixth pixel in the second row of the original data 201 is 1 and the others are 0, as indicated by 215 as difference data of stage 4 (STAGE 4) in FIG.
Therefore, the difference data 215 is scanned in the horizontal direction and weighted, so that the same horizontal weighted data as the difference data 215 is generated (step 10 in FIG. 7).
2) Also, the same horizontal weighting data as the difference data 215 is generated by being scanned and weighted in the vertical direction (step 103 in FIG. 7).

The maximum value maxlenh of the horizontal weighting data and the maximum value max of the vertical weighting data thus obtained are obtained.
Since both lenv are “1”, first, the vertical intermediate decoded data 214 is run-length encoded (steps 106 and 111 in FIG. 7). As a result, FIG.
7, the run-length coded output “7, 6, 2”
5, 2, 2 "are obtained.

Subsequently, the horizontal intermediate decoded data 210 is run-length coded (step 112 in FIG. 7), whereby the run-length coded output "2,3,9,3" as shown at 218 in FIG. 15, 3, 7 "are obtained.
Further, difference data between the original data 201 and the intermediate decoded data 210 and 214 is obtained (step 11 in FIG. 7).
3), whereby the stage 5 (S
TAG5) is obtained, and the difference data 216 of the single pixel is run-length encoded (step 114 in FIG. 7). As a result, as shown by reference numeral 219 in FIG. 10, a run-length encoded output “11, 30” is obtained.

As described above, in the embodiments and examples of the present invention, in the case of Chinese characters, the encoding efficiency is increased by focusing on the fact that there are many character color regions that are continuous in the vertical and horizontal directions.
A bit map can be reproduced with a storage device having a smaller capacity than before.

Incidentally, a 24 × 24 pixel font (JIS
X0208), the original data, the better run-length encoding in the vertical and horizontal directions for the total of 6877 characters,
It was confirmed that the total number of pixels and the number of pixels per character when run-length encoding was performed according to the method of the present invention are as shown in Table 1.

[0041]

[Table 1] In Table 1 above, “the better run-length encoding in the vertical direction and the horizontal direction” means, for each bitmap data of each character font, the run-length encoding only in the vertical direction and the run-length encoding only in the horizontal direction. Run-length encoding means encoding in which the smaller number of pixels is selected from the encoded output for each character font.

Further, by performing compression and non-compression on the basis of the number of pixels of the original data in units of one character, the coding efficiency can be improved.

[0043]

As described above, according to the present invention,
Since the encoding efficiency can be increased as compared with the related art, the storage capacity of the storage device required for encoding the bitmap data can be reduced as compared with the related art, and therefore, it is relatively simple compared with the related art. Encoding can be performed with an inexpensive configuration.

[Brief description of the drawings]

FIG. 1 is a block diagram of an embodiment of an encoding device used in a bitmap efficient encoding method according to the present invention.

FIG. 2 is a diagram illustrating an example of an original font to be encoded.

FIG. 3 is a diagram showing a bitmap obtained by scanning the font of FIG. 2 in the horizontal direction.

FIG. 4 is a diagram showing a bitmap obtained by scanning the font of FIG. 2 in the vertical direction.

FIG. 5 is a diagram showing the sum of the bitmaps of FIGS. 3 and 4;

FIG. 6 is a diagram showing a difference between the bitmaps of FIGS. 2 and 5;

FIG. 7 is a flowchart for explaining the operation of the embodiment of the method of the present invention.

FIG. 8 is a diagram showing an example of a horizontal weighting data array.

FIG. 9 is a diagram illustrating an example of a vertical weighting data array.

FIG. 10 is a diagram showing data shift according to an embodiment of the present invention.

[Explanation of symbols]

11 Bitmap data storage memory (first storage means) 12 Intermediate decoded data storage memory (second storage means) 13 Bitmap calculator (calculation means) 14 Vertical direction continuous data detector (generation means) 15 Horizontal direction continuous Data detector (generating means) 16 weighting operation part and memory (generating means) 17 run-length encoder (encoding means) 18 data control part (encoding means) 201 original data 202, 210 horizontal intermediate decoded data 203, 206; 214 Vertical intermediate decode data 204, 208, 212 Horizontal weight data 205, 209, 213 Vertical weight data 207, 211, 215, 216 Difference data

Claims (3)

[Claims] A first storage unit for storing bitmap data to be encoded; and a bitmap data stored by the first storage unit, which is separately scanned in a vertical direction and a horizontal direction, respectively. Generating means for respectively generating vertical intermediate decode data and horizontal intermediate decode data whose horizontal and vertical lengths are 1 from the weighted vertical and horizontal weight data obtained by weighting, respectively, vertical intermediate decode data And second intermediate storage means for storing horizontal and intermediate decoded data, respectively; difference data between the bitmap data from the first storage means and the vertical and horizontal intermediate decoded data from the second storage means. Computing means for computing the difference data and the vertical intermediate decoded data and the horizontal intermediate decoded data obtained by the generating means. Bitmap high efficiency coding method, characterized in that it comprises a coding means for run-length encoding, respectively Re. 2. The method according to claim 1, wherein the generation unit includes: a vertical weighting data in which the number of consecutive same values among pixel values obtained by vertically scanning the bitmap data is arranged at the pixel position; Horizontally weighted data in which the number of consecutive same values among the values of each pixel obtained by scanning the bitmap data in the horizontal direction are generated at the pixel position, and these vertical weighted data and horizontal weighted data are generated. When the maximum value of at least one of the weight data is 2 or more, the maximum value area of the weight data having the larger maximum value corresponds to the area corresponding to the bitmap data stored by the first storage means. And a means for updating data obtained by copying the pixel values of the above as the vertical or horizontal intermediate decode data stored in the second storage means. 2. The high efficiency bitmap encoding method according to claim 1, wherein 3. The encoding means executes run-length encoding by assigning a smaller number of bits to pixels in a character color area of the difference data, the vertical intermediate decode data, and the horizontal intermediate decode data than pixels in a non-character color area. 3. The highly efficient bitmap encoding method according to claim 1, wherein