JP3438474B2 - Image processing device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus for processing a digitized image, and more particularly to an image processing apparatus capable of performing spatial filter processing on an image at high speed and at low cost.

[0002]

2. Description of the Related Art An image processing apparatus and a DTP (Desk Top Publicshin) capable of handling an image
g) In systems, printing systems, etc., spatial filter processing may be used for processing such as noise removal and edge sharpening of the input image. This spatial filtering process is performed by, for example, 3 × 3 filter coefficient K (i,
j) (i = −1 to 1, j = −1 to 1), and is performed by calculating the following formula for each pixel P (x, y) in the image. P ′ (x, y) = Σ _{j = −1} ¹ Σ _{i = −1} ¹ K (i, j) × P
(X + i, y + j)

FIG. 3 is an explanatory diagram of an example of filter coefficients used in the spatial filtering process. Filter coefficient K
As (i, j), for example, a filter coefficient as shown in FIG. 3 can be used. Although FIG. 3 shows an example of the filter coefficient when the spatial filter processing is performed using the filter coefficient of the size of 3 × 3, the spatial filter processing is performed using the coefficient matrix of 5 × 5 or other sizes. Sometimes.

When the spatial filter processing is performed according to the above equation, even if the smallest coefficient matrix as shown in FIG. 3 is used, the calculation amount is 9 times multiplication per pixel +
Since 8 additions are required, a very long processing time is required when performing a spatial filter process on a large-capacity image or when using a filter coefficient of a larger size.

Conventionally, as an example of a method for solving this problem, for example, a hardware pipeline configuration is often used. FIG. 21 is a block diagram showing an example of a conventional image processing apparatus that performs spatial filter processing. In the figure, 21 is a FIFO unit, 22 is a coefficient storage unit, 23 is a multiplier, and 24 is an adder.

In the conventional image processing apparatus shown in FIG. 21, the image data to be processed is stored in a FIFO (First-In).
The first-out buffer unit 21 delays the pixel of interest and its neighboring pixels in synchronism with each other, and uses a plurality of multipliers 23 to perform a multiplication process with a coefficient set in the coefficient storage unit 22 in parallel. The result is the result of multiple adders 2
High-speed processing is realized by using 4 to generate an output value by integrating in parallel. However, such a configuration increases the device cost due to hardware such as a plurality of FIFOs, multipliers, and adders, and has a fixed configuration, so that it is flexible such as performing spatial filter processing with an arbitrary coefficient size. It has the drawback of being difficult to use.

On the other hand, as one of methods for speeding up various kinds of image processing, a method has been proposed in which image data is processed in a compressed state without being expanded. For example,
Japanese Patent Laid-Open No. 57-89171 proposes a method in which a black-and-white change point in a binary image is encoded into, for example, run-length data, and the encoded data is used to rotate an arbitrary angle. In Japanese Patent Laid-Open No. 57-100555, 2
Left and right shift processing for one-dimensional coded data of a value image has been proposed, and it is stated that enlargement / reduction, superposition, composition, deletion, etc. are possible. Also, JP-A-58-1424
In Japanese Patent Laid-Open No. 67-67, a binary image is encoded with a black-and-white change point, and a logical operation method between encoded two lines of data is disclosed in Japanese Patent Laid-Open No.
Japanese Patent No. 34669 proposes a logical filtering method for run-length encoded data of a binary image. In addition, "The UtahRaster Too
lkit ", The 3rd. Usenix Wor
kshop on Graphics, Montere
In y California, 1986.11, multi-valued image run-length compressed data is subjected to integer scaling and table processing.

[0008] In these methods, the processing speed can be increased by utilizing the reduction of the amount of data processed and the cost of reading the data due to the compression, and the device cost required for data storage can be reduced. However, regarding the above-mentioned spatial filter processing, a processing method using such compressed data as it is has not been proposed.

[0009]

SUMMARY OF THE INVENTION The present invention has been made in view of the above-mentioned circumstances, and is high-speed, low-cost and flexible by performing spatial filter processing without decompressing run-length compressed image data. An object of the present invention is to provide an image processing apparatus capable of realizing spatial filter processing of various images.

[0010]

According to a first aspect of the present invention, in an image processing apparatus, an image subjected to a spatial filtering process on image data composed of row data expressed in a run length format on a row-by-row basis. The processing device includes multiplication means for multiplying row data by a constant, shift means for shifting the row data to the right or left by N pixels, and addition means for adding a plurality of pieces of row data, the multiplication means, the shift means, and the It is characterized in that the spatial filtering process of the image data represented by the run length is performed by using the adding means.

According to a second aspect of the present invention, in an image processing apparatus for performing spatial filter processing on image data composed of row data expressed in a run length format for each row, a filter is applied to the row data. Multiplication means for multiplying the coefficient, shift means for shifting the row data to the right or left by the number of pixels corresponding to the position in the coefficient matrix of the filter coefficient with respect to the row data multiplied by the filter coefficient, The present invention is characterized by comprising addition means for adding a plurality of row data of the row data shifted by the shift means and the row data multiplied by the filter coefficient by the multiplication means.

According to a third aspect of the present invention, in the image processing apparatus according to the first or second aspect, a storage means for temporarily storing the row data before or after the calculation is further provided. It is a thing.

According to a fourth aspect of the present invention, in the image processing apparatus according to the first or second aspect, the adding means extracts the run data at the left end of the plurality of row data items to be added, and determines the run lengths of the respective run data. The minimum value is obtained by comparison, and the sum of the pixel values of each run is further obtained and paired with the minimum value of the run length and output as new run data, and the minimum value is obtained from the run length of the run data of each row. Is subtracted and the run data having a run length of 0 is repeatedly fetched to the right end of the line.

According to a fifth aspect of the present invention, in an image processing apparatus, an image compression means for converting an input image into line data expressed in a run length format in units of lines, and any one of the first to fourth aspects. The image processing device according to the item (1), and a restoration unit that restores the row data after the spatial filter processing output from the image processing device into an image.

[0015]

FIG. 1 is a block diagram showing a first embodiment of an image processing apparatus of the present invention. In the figure, 1 is an image input unit, 2 is an image storage unit, 3 is an image output unit, 4 is a spatial filter processing unit, 5 is a control unit, 11 is a row data multiplication unit, 12 is a line data shift unit, and 13 is a line. This is a data addition unit. The image input unit 1 inputs the transmitted or accumulated run-length format image data. The image storage unit 2 stores the image data input from the image input unit 1. The image output unit 3 outputs the processing result. The spatial filter processing unit 4 performs spatial filter processing. The control unit 5 controls each unit.

The spatial filter processing section 4 has a row data multiplication section 11, a row data shift section 12, and a row data addition section 13, and performs spatial filter processing on the input run-length format image. The row data multiplication unit 11 reads one row of the run-length converted image data and multiplies the pixel value by the filter coefficient. Line data shift unit 12
Reads one line of the run-length converted image data and shifts the line to the right or left by N pixels. The row data addition unit 13 reads a plurality of rows of run-length converted image data and adds the respective rows.

In FIG. 1, image data is input from the image input unit 1, stored in the image storage unit 2, read out to the spatial filter processing unit 4, spatially filtered, and the image output unit 3 is processed in the order. Sent to and output.

FIG. 2 is an explanatory diagram of an example of run-length format representation of image data. In each of the examples shown in FIGS. 2A and 2B, the image data is shown at the top and the run-length representation of the image data is shown at the bottom. Each rectangle of the image data represents consecutive pixels in the same row, and the numerical value in the rectangle represents the pixel value. In addition, the run length expression is
The number of consecutive pixels having the same pixel value and the pixel value are expressed as a pair. In Figure 2, this pair is separated by a dotted line,
It indicates that the two values are a pair.

The case where the image data for one line shown above in FIG. 2A is given will be described as an example. Since the same pixel values (= 200) are lined up from the top three pixels, the run length expression is "3,200". Next is pixel value 180
Since it is one pixel, it becomes "1,180", and the same processing is performed thereafter to obtain the result shown in the lower part of FIG. Figure 2 (A)
As is clear from the above, such an expression form has an effect of data compression in the case of an image in which the same pixel value is often continuous.

FIG. 2B shows an example of run-length expression that is slightly different from the expression described with reference to FIG.
In this run-length expression, a portion in which the same pixel value is continuous is expressed as a pair of the pixel number and the pixel value, and in a portion having a different pixel value for each pixel, the pixel number of that portion is made negative. The converted value and a plurality of pixel values of the part are described as a pair. The case where the image data shown above in FIG. 2B is given will be described as an example. Since the same pixel values (= 200) are lined up from the top 3 pixels,
The run length expression is “3,200”. Next is 18
Since two pixel values different from 0 and 150 are lined up, the expression becomes "-2,180,150", and the same processing is performed thereafter to obtain the result shown in the lower part of FIG. Although the method is slightly more complicated than the method described with reference to FIG. 2A, the compression rate is often improved in many cases, as can be seen from the example shown in FIG.

In the following embodiments, description will be made on the premise of the run length format shown in FIG. 2A. However, for example, even in the case of the run length format as shown in FIG. , 150 ”is internally expressed as“ 1,
It can be similarly applied if it is controlled so that it is processed by being read as two runs of "180" and "1,150". In other formats, the number corresponding to the number of consecutive one-dimensional same pixel values and its Any expression can be easily applied as long as it is expressed using an amount corresponding to the pixel value.

Such run length conversion is performed for each row. In the following description, the row-by-row data of the image data before conversion or the row-by-row data of the run-length expression after conversion will be referred to as row data.

FIG. 4 is a flow chart showing the outline of the operation in the first embodiment of the image processing system of the invention. Note that, in FIG. 4, the vertical direction of the image is composed of H rows of 0 to H−1, and D _n represents the run-length compressed row data of the _n- th row. In the explanation below,
In order to simplify the description, a spatial filter process using a filter coefficient having a size of 3 × 3 as shown in FIG. 3 will be described. However, the present invention is not limited to this, and can be applied to any filter coefficient value and any filter coefficient size.

In the 3 × 3 size filter processing, when the first row and the last row are processed, accesses to the −1st row and the Hth row which do not actually exist occur. Therefore, in S11, from the image storage unit 2 reads the D _-1 instruction outputs D _0, the instruction to read the D _H performs setting so as to output a D _{H- 1.} Further, in S32, as an initial setting, n is set to 0 in order to set the line to be processed to the 0th row.

Next, in S33, the row data D _n-1 , D _n , and D _{n + 1} are input from the image storage unit 2 to the spatial filter processing unit 4. Since n = 0 is set in the case of the first row, D ₋₁ (= D ₀ ), D ₀ , and D ₁ are input to the spatial filter processing unit 4.

In S34, the spatial filter processing is executed on the row data input in S33, and the result is output to the image output unit 3. The operation of this portion will be described in detail later with reference to FIG.

Next, at S35, 1 is added to n representing the processing target row in order to process the next row. In S36, n is compared with H. If n <H, there is still an unprocessed row, so the process returns to S33 to continue the process, and if n ≧ H, the process ends. .

FIG. 5 is a flow chart showing an example of the spatial filtering process in the first embodiment of the image processing system of the invention. This process is a process performed in S34 of FIG. By the processing shown in S33 of FIG. 4, the run-length compressed row data D _n-1 , D _n , and D _{n + 1} for three rows are input to the spatial filter processing unit 4. Therefore, in S41, the filter coefficient K (-1,1) = is added to D _{n + 1} using the row data multiplication unit 11 _first.
K (1,1) = 0.05 is multiplied, and then the row data shift unit 12 shifts this by 1 pixel to the left and right to create data. Hereinafter, the row data obtained by multiplying and shifting the original data will be expressed as D _n (multiplier, shift pixel number). Here, the number of shift pixels is represented by plus on the right and minus on the left. Details of operations of the row data multiplication unit 11 and the row data shift unit 12 will be described later.

Further, in S42, the row data multiplication unit 1
Multiply D _{n + 1} by ₁ by K (0,1) = 0.1
Create _{n + 1} (0.1, 0). Through the processing of S41 and S42, the arithmetic processing for D _{n + 1} was completed. The created data is D _{n + 1} (0.05, −1), D _{n + 1} (0.
1, 0) and D _{n + 1} (0.05, -1).

Next, in S43, the row data multiplication unit 11
In creating a D _n (0.1, 0) by multiplying the K (-1,0) = K (1,0 ) = 0.1 to D _n, each of which left or right row data shift section 12 It shifts pixel by pixel and D _n (0.
1, −1) and D _n (0.1, 1) are created. further,
In S44, K (0 to D _n in the line data multiplication section 11,
0) = 0.4 is multiplied to create D _n (0.4,0).

Next, in S45, the row data multiplication unit 11
Then, in D _n-1 , K (-1, -1) = K (1, -1) = 0.0
D _n-1 (0.05,0) is generated by multiplying by 5, and this is shifted by 1 pixel to the left and right by the row data shift unit 12 to obtain D _n-1 (0.05, -1), Create D _n-1 (0.05, ₁ ). Further, in S46, the row data multiplication unit 1
D _n−1 multiplied by K (0, −1) = 0.1 by 1
Create _n (0.1, 0).

In S47, the row data adding unit 13 performs S
Dn _{+ 1} (0.05,-) created from 41 to S46
1), D _{n + 1} (0.1, 0), D _{n + 1} (0.05,
1), D _n (0.1, −1), D _n (0.4, 0), D
_n (0.1, 1), D _n-1 (0.05, -1), D _n-1
(0.1, 0) and D _n-1 (0.05, ₁ ) are added to create a spatial filter processing result. Then, this result is output to the image output unit 3, and the filtering process for one line is completed. The details of the operation of the row data adding unit 13 will be described later.

Next, details of the operation of the row data multiplication unit 11 will be described. FIG. 6 shows a first image processing apparatus according to the present invention.
5 is a flowchart showing an example of processing of a row data multiplication unit in the embodiment. The row data multiplication unit 11 sets the run to be processed for the given row data in S51 as the first run of the row data in the run length format. The term "run" as used herein refers to a pair of the number of pixels in which the same pixel value shown in FIG. 2 continues and the pixel value thereof.

Next, in S52, the given multiplier is multiplied by the pixel value portion of the run to be processed. Since one of the filter coefficients is given as the multiplier, the pixel value is multiplied by the given filter coefficient. Next, in S53, it is determined whether or not there are still unprocessed runs. If there are any unprocessed runs, the run to be processed is moved to the current next run in S54 and the process returns to S52.

FIG. 7 is an explanatory diagram of a specific example of the processing of the row data multiplication section in the first embodiment of the image processing apparatus of the invention. FIG. 7 shows a change in run length data due to the multiplication process shown in FIG. Here, the row length data of the run length format is multiplied by the multiplier 0.4. As shown in FIG. 2, in the run-length format row data, runs that are pairs of the number of pixels having the same pixel value and the pixel value are arranged. In each run, the number of pixels is left unchanged and the pixel value is multiplied by 0.4. For example, the first pixel number / pixel value pair (3,200) has 0.
4 is multiplied to obtain (3,80). The same applies hereinafter.

As described above, since the processing is performed in units of runs, the number of multiplications is 1 as compared with the processing in the normal pixel unit.
/ (Compression rate), and high-speed processing is possible.

Next, details of the operation of the row data shift section 12 will be described. FIG. 8 is a flowchart showing an example of processing of the row data shift unit in the first embodiment of the image processing apparatus of the invention. Here, the processing when the row data shift unit 12 shifts N pixels to the right is shown. At this time, the row data shift unit 12 adds N pixels on the left side of the pixel value at the left end of the run-length format row data, and deletes the N pixels on the right side. Such shift processing is executed only by changing the number of pixels in the runs at the left end portion and the right end portion of the row data, and the number of pixels does not change for shifts between runs. Since the run-length format row data does not have position information in the row, the run-length format row data equivalent to the case where the row data of the image data is shifted by such processing is obtained.

The row data input to the row data shift unit 12 adds the movement amount N to the number of pixels in the leftmost run of the row in S61. This adds the number of pixels in the leftmost run. At this time, for example, when a specific value, for example, “0” is added to the left end, a run of “N, 0” may be newly inserted in the left end.

Next, N pixels are deleted from the run at the right end. First, in S62, the number of pixels in the rightmost run of the row is compared with the movement amount N. If the number of pixels <N, S63 is performed.
If the number of pixels = N, the process proceeds to S65, and if the number of pixels> N, the process proceeds to S66. If the number of pixels <N, all the runs are deleted by the shift. Therefore, in S63, a value obtained by subtracting the number of pixels of the rightmost run from the movement amount N is set as a new N, and the rightmost run itself is deleted. Then, the process returns to S62 to repeat the above process. When the number of pixels = N, the run length of the right end run is equal to N, and therefore the right end run itself is deleted in S65, and the process ends. If the number of pixels> N, only some of the pixels in the rightmost run are deleted, so that the run remains and N is subtracted from the number of pixels in the rightmost run in S66, and the process ends.

Although the case where the row data is shifted to the right has been described here, when shifting to the left, the shift process to the left can be performed by reversing the process for the right end run and the process for the left end run. Is.

FIG. 9 is an explanatory diagram of a specific example of the processing of the row data shift section in the first embodiment of the image processing apparatus of the invention. Now, it is assumed that the run-length format row data shown in FIG. Here, consider a case of shifting one pixel to the right, that is, N = 1. First, in S61 of FIG. 8, the shift amount N is changed to the number of pixels (= 3) in the leftmost run
(= 1) is added to make the number of pixels four. Next, in S62, the number of pixels in the rightmost run (= 4) is compared with the shift amount N (= 1). Since N is smaller, the process proceeds to S66, in which N is subtracted from the number of pixels in the rightmost run The number is set to 3, and the process ends. As a result, the run-length row data after the shift as shown in FIG. 9B is obtained.

Further, it is shifted by 4 pixels to the left, that is, N =-
In the case of 4, the processing is performed according to the flowchart in which the right end and the left end in FIG. Number of pixels in the rightmost run (=
The shift amount (= 4) is added to 4) to set the number of pixels to 8.
Next, the number of pixels in the leftmost run (= 3) and the shift amount N (= 1)
And N is larger, so the number of pixels in the leftmost run is subtracted from N, and N is set to 1. Also, the run at the left end is deleted and the process is repeated. This time, the number of pixels in the leftmost run is 1. It is compared with a new shift amount N (= 1), and since they match, the run at the right end is deleted, and the process ends. As a result, the run-length row data after the shift as shown in FIG. 9C is obtained.

As described above, the shift processing of the run-length-converted row data is completed only by the operation on some left and right run data, and therefore the shift processing of the normal image data that has not been run-length converted. Processing can be performed faster than

Next, the operation of the row data adding section 13 will be described in detail. FIG. 10 is a flowchart showing an example of processing of the row data adding unit in the first embodiment of the image processing apparatus of the invention. The row data addition unit 13 performs addition processing on the input two run-length format row data to be added, that is, row 1 and row 2.

In S71, the pixel number and pixel value of the leftmost run of row 1 are substituted into L1 and V1. Similarly, the pixel number and pixel value of the leftmost run of row 2 are substituted into L2 and V2. Next, in S72, a run "L" is performed in which L0 = min (L1, L2) and V0 = V1 + V2 are L0 and V0, respectively, which are the number of pixels and the pixel value.
0, V0 "is generated and output. Next, in S73, L
L0 is subtracted from each of L1 and L2 and substituted into L1 and L2. Next, in S74, L1 is compared with 0. If L1 = 0, the process proceeds to S75, and if L1> 0, the process proceeds to S77.
Since the smaller of L1 and L2 is set to L0 in S72,
L1 after the subtraction is never negative.

When L1 = 0, in S75, it is checked whether or not there is a next run in row 1, and if there is a run, in S76, the number of pixels and the pixel value of the next run in row 1 are respectively set to L.
1, V1 is substituted and the process proceeds to S77, and if there is no run, the process ends.

In S77, L2 is compared with 0 as in S74. If L2 = 0, the process proceeds to S78, and if L2> 0, the process returns to S72. Line 2 in S78
Check if there is a next run, and if there is a run S
At 79, the pixel number and pixel value of the next run in row 2 are set to L
2, V2 is substituted and the process returns to S72. If there is no, the process ends.

FIG. 11 is an explanatory diagram of a concrete example of the processing of the row data adding section in the first embodiment of the image processing system of the invention. 2 shown as row 1 and row 2 in FIG.
The line data in one run length format is the line data addition unit 13
Is added to the two row data.

Explaining in accordance with the flow chart shown in FIG. 10, the leading run of each row is read out in S71 and L1 = 3, V1 = 80, L2 = 4, V2 = 20, and L0 = min in S72. (L1, L2) = min
(3,4) = 3, V0 = V1 + V2 = 80 + 20 = 10
0 is calculated and (number of pixels, pixel value) = (3,100)
Is output as a run.

Next, in S73, L1 = L1-L0 = 3.
-3 = 0, L2 = L2-L0 = 4-3 = 1, and S7
In step 4, L1 = 0 is determined, and the flow advances to step S75. Since there is a next run, that run is read in step S76 and L1 = 1, V
1 = 72 is set. Next, in S77, L2> 0 is determined, and the process returns to S72.

The processing result shown in FIG. 11 can be obtained by performing such processing until the runs in either row are eliminated. In the case of FIG. 11, 17 pixels are included in one row, but with this method, the number of additions is 8 times, and when the same pixel value continues, normal pixels that have not been run-length converted are included. High-speed processing can be expected as compared with the unit addition processing.

Although the addition processing of two rows has been described here, when the number of rows to be added is three or more, it is two.
The addition for each row is repeated, or in the flowchart shown in FIG. 10, the number of pixels and the pixel value of the first run of row m are substituted into Lm and Vm in S71, and L0 = m in S72.
in (L1, L2, ..., Lm), V0 = V1 + V2 + ...
The processing can be performed by setting + Vm, setting Lm = Lm-L0 in S73, and reading the next run if Sm is 0 or less for each Lm.

As described above, by configuring each unit so as to perform the processing with the run-length converted format as it is, an image processing apparatus capable of high-speed spatial filter processing can be realized. Although the filter processing using the 3 × 3 coefficient in FIG. 3 has been described here as an example, the present invention is not limited to this, and the coefficient value and the coefficient size are not limited to this. However, it is possible to realize a flexible processing device capable of arbitrary spatial filter processing with the same configuration.

FIG. 12 is an explanatory diagram of a specific example of the spatial filter processing in the first embodiment of the image processing system of the invention. FIG. 12A shows image data before run length conversion. The actual image is very large, but only 15 pixels × 3 rows are shown here. The numerical value in the rectangle is the pixel value. This image data has been converted to run-length format row data as shown in FIG. The details of the conversion are as described in FIG. Such run-length format row data is stored in the image storage unit 2.

The spatial filter processing section 4 firstly outputs D _n and D
_The 0th row is read as _n-1 , and the row data of the first row is read as Dn _{+ 1} , and calculation is performed. As a result, FIG.
The data of the 0th row in (C) is output. Next, line 0 as D _n-1, line 1 as D _n, reads the second row of row data as D n _{+ 1,} by performing a calculation, the first line of data in FIG. 12 (C) Output. Furthermore, the row data of the first row as D _n−1 and the second row as D _n and D _{n + 1} are read,
Calculation is performed and the data of the second row in FIG. 12C is output. In this way, the run-length format row data after the spatial filter processing as shown in FIG. 12C is obtained.

FIG. 13 is an explanatory diagram of a specific example of the operation of the spatial filter processing section 4 in the first embodiment of the image processing system of the invention. As an example, it is assumed that the run-length format row data shown in FIG. 12B is stored in the image storage unit 2 and the filter coefficient shown in FIG. 3 is applied to the row data of the first row to perform the spatial filtering process. Briefly explain the process of performing. In the flowchart shown in FIG.
In S41, D ₂ is multiplied by a filter coefficient of 0.05, and
Calculate D ₂ (0.05,0) in 3. Further, this D ₂ (0.05, 0) is shifted left and right by 1 pixel each, and
D ₂ (0.05, -1), D ₂ (0.05, 1) in 3
To generate. Further, in S42, D ₂ is multiplied by the filter coefficient 0.1 to calculate D ₂ (0.1, 0) in FIG. Similarly, in S43, D ₁ is multiplied by the filter coefficient of 0.1 to calculate D ₁ (0.1, 0) in FIG. Of D
₁ (0.1, -1), to produce a D ₁ (0.1, 1).
Further, in S44, D ₂ is multiplied by the filter coefficient 0.4 to calculate D ₁ (0.4,0) in FIG. Furthermore, S4
5, D ₀ is multiplied by a filter coefficient of 0.05, D ₀ (0.05, ₀ ) in FIG. 13 is calculated, and each pixel is further shifted left and right by 1 pixel, and D ₀ (0. 05, -1), D ₀
Generate (0.05, 1). In S46,
Multiply D ₀ by the filter coefficient 0.1 to obtain D in FIG.
Calculate ₀ (0.1, ₀ ).

D ₀ (0.0
5, -1), D ₀ (0.05, 1), D ₀ (0.1,
0), D ₁ (0.1, −1), D ₁ (0.1, 1), D
₁ (0.4, 0), D ₂ (0.05, -1), D
₂ (0.05, 1) and D ₂ (0.1, 0) are added in S47. The number of pixels in each first cell is L0 to L8, and the pixel values are V0 to V8. From FIG. 13, L0 = 5
L1 = 7, L2 = 6, L3 = 6, L4 = 8, L5 = 7,
L6 = 8, L7 = 10, L8 = 9, V0 = 5, V1 =
5, V2 = 10, V3 = 10, V4 = 10, V5 = 4
0, V6 = 5, V7 = 5, V8 = 10. L0-L
Since the minimum value of 8 is 5, which is L0, the number of pixels in the first cell of the row data after addition is 5, and the pixel value is 100, which is the sum of V0 to V8.

L0 to L8 are each reduced by 5, and L
1 = 2, L2 = 1, L3 = 1, L4 = 3, L5 = 2, L
6 = 3 and L7 = 5. For L0, the number of pixels of 10 in the next cell is substituted. Further, V0 also becomes 0. Since the minimum value of L0 to L8 after updating is 1 of L2 and L3, the pixel number of the next cell is 1 and the pixel value is 95.

By repeating such processing and performing addition, the row data as shown in the first row of FIG. 12C is obtained. Row data as shown in FIG. 12C is obtained for the 0th row and the 2nd row by similar processing. After the spatial filter processing result as shown in FIG. 12C is obtained, if inverse conversion from the run length format is performed as necessary, image data in bitmap format as shown in FIG. 12D is obtained. can get.

As can be seen by comparing the image data shown in FIGS. 12A and 12D, the image shown in FIG. 12D has a more gradual change in pixel value and is smoothed. It can be seen that filtering has been performed. As described above, by performing the spatial filter processing of the present invention on the run length format data, the same processing as the conventional spatial filter processing on the image data can be performed. Moreover, as mentioned above, the amount of calculation is much smaller than in the past.
High-speed processing is possible.

In the above-described first embodiment, S4 in FIG.
As shown in S1, S43, and S45, the same coefficient value included in each row of the filter coefficients is collectively multiplied so that the number of times of multiplication can be reduced as much as possible. However, like the filter coefficient shown in FIG. 3, in the spatial filter processing, the coefficient is often symmetrical not only in the left and right but also in the upper and lower sides, and the number of multiplications may be further reduced by using such a characteristic. In the second embodiment to be described below, when the filter coefficient has a common coefficient value in different rows, the result of the spatial filter processing for the preceding row is used to further speed up the filtering processing for the subsequent row. The method of conversion will be described.

FIG. 14 is a block diagram showing a second embodiment of the image processing apparatus according to the present invention. In the figure, the same parts as those in FIG. Reference numeral 14 is a row data temporary storage unit. The row filter temporary storage unit 14 is added to the spatial filter processing unit 4 of the second embodiment in addition to the configuration of the first embodiment described above. The row data temporary storage unit 14 temporarily stores a plurality of row data calculated when processing rows before the processing target row. By storing the calculation result in the row data temporary storage unit 14, it becomes possible to reuse the row data across the processing target rows.

FIG. 15 is a flow chart showing the outline of the operation of the second embodiment of the image processing system of the invention. In FIG. 15, the image will be described as being composed of H rows from the 0th row to the (H-1) th row.
Here, for simplification of description, the case where the spatial filter processing is performed using the filter coefficient shown in FIG. 3 as in the first embodiment will be described as an example.

In S81, the variable n indicating the line to be processed
Is set to 0 and the process is started from the 0th line. In S82, the value of the variable n is determined, and if n = 0, then in S83, 1
If ≦ n ≦ H-2, the process proceeds to S86, and if n = H-1, the process proceeds to S88.
Move on to.

When n = 0, there is no row that has been calculated, and calculation must be performed on all three rows. S83
Then, from the image storage unit 2 to the spatial filter processing unit 4, D ₀ , D ₁
Is input, and spatial filter processing is executed in the next S84. D ₁ (0.1,0) calculated at this time and B _{1
= D 1 (0.05, -1)} + D 1 (0.1,0) + D 1
(0.05, ₁ ), obtained as a calculated value of D _-1 B ₀ =
D ₀ (0.05, -1) + D ₀ (0.1,0) + D
₀ (0.05, 1) and the like are stored in the row data temporary storage unit 14. Then, in S85, 1 is added to n and the control is returned to S82.

If 1 ≦ n ≦ H-2 in S82, the process proceeds to S86, D _n and D _{n + 1} are input from the image storage unit 2 to the spatial filter processing unit 4, and the spatial filter is processed in the next S87. Execute the process. Spatial filtering Here, processing in the D _n-1 result _{(D n-1 (0.05,} -
1) + D _n-1 (0.1,0) + D _n-1 (0.05,
1)), D _n (0.1, 0), etc. are calculated and stored in the row data temporary storage unit 14, and therefore calculation is performed using these calculation results. Also, D calculated at this time
_{n + 1} (0.1, 0) or B _{n + 1} = D _{n + 1} (0.05,-
1) + D _{n + 1} (0.1,0) + D _{n + 1} (0.05,1)
The calculation results such as “1” are stored in the row data temporary storage unit 14. As described above, the intermediate result of the processing up to the preceding row is temporarily stored and can be used at the time of processing to another row, whereby the processing can be performed at higher speed. . In this way, the spatial filter processing from the 1st line to the H-2nd line is performed, and then, in S85, n
Is incremented by 1 and control is returned to S82.

In S82, if n = H-1,
Moving to S88, the image storage unit 2 to the spatial filter processing unit 4
_DH-1 is input to and spatial filter processing is executed in the next S89. In the spatial filter processing here, most of the calculation results are stored in the row data temporary storage unit 14, so the calculation is performed using these. Since this H-1 row is the last row, the calculation result is stored in the row data temporary storage unit 1.
It does not need to be stored in 4.

FIG. 16 is a flow chart showing an example of the processing of the 0th row in the second embodiment of the image processing system of the invention. The spatial filter process in S84 of FIG. 15 will be described in more detail with reference to FIG.

First, in S91, the row data multiplication unit 1
In step 1, D ₁ is multiplied by K (−1,1) = K (1,1) = 0.05 to create D ₁ (0.05,0). D by shifting one pixel at a time
₁ (0.05, -1), to create a D ₁ (0.05,1). Next, in S92, the row data multiplication unit 11 multiplies D ₁ by K (0,1) = 0.1 to create D ₁ (0.1,0), which is stored in the row data temporary storage unit 14. Store. Let this stored data be A ₁ . Next, in S93,
In the row data adder 13, D ₁ (0.05, −1), D
₁ (0.1, 0) and D ₁ (0.05, ₁ ) are added, and this data is stored in the row data temporary storage unit 14. Let this stored data be B ₁ . The calculation for D ₁ is now done.

Next, in S94, the row data multiplication unit 11
Then, D ₀ is multiplied by K (−1,0) = K (1,0) = 0.1 to create D ₀ (0.1,0). Each by shifting D ₀ (0.1,-
1) and D ₀ (0.1, 1) are created. Next, in S95, the row data multiplication unit 11 multiplies D ₀ by 0.4 to obtain D
Create ₀ (0.4, ₀ ). Now the calculation for D ₀ is performed.

Since there is no D _-1 data in the 0th row, the calculation is performed using D ₀ . In S96, K (-1,1) = K (1,1) is added to D ₀ in the row data multiplication unit 11.
= 0.05 to create D ₀ (0.05,0),
The row data shift unit 12 shifts this one pixel to the left and right to create D ₀ (0.05, −1) and D ₀ (0.05, 1). Next, in S97, the row data adding unit 13 outputs D ₀ (0.05, −1), D ₀ (0.1, ₀ ), D
₀ (0.05, 1) is added and this data is stored in the row data temporary storage unit 14. _Now , a calculation corresponding to D _-1 has been performed. Let B ₀ be the data stored in the row data temporary storage unit 14. The stored data B ₀ is a calculated value corresponding to D ₋₁ , but D ₀ (0.05, −1), D ₀
Since it is the added value of (0.1, ₀ ) and D ₀ (0.05, 1), it can be used in the subsequent calculation processing.

Next, in S98, B ₀ and B ₁ are read from the row data temporary storage unit 14, and the row data addition unit 13 reads B ₁ , D ₀ (0.1, −1), D ₀ (0.4, 0), D
₀ (0.1, 1), B ₀ are added to generate a spatial filter processing result, and this result is output to the image output unit 3. At this point, the row data temporary storage unit 14 stores A ₁ (= D
₁ (0.1,0)), B ₁ (= D ₁ (0.05, -1)
+ D ₁ (0.1,0) + D ₁ (0.05,1)), B ₀
(= D ₀ (0.05, −1) + D ₀ (0.1,0) + D
₀ (0.05, 1)) is stored. Spatial filter processing of the 0th line is performed by such a procedure, and then, as shown in FIG.
In S85 of 5, n is incremented by 1 and the control is returned to S82.

FIG. 17 is a flow chart showing an example of the processing of the 1st to H-2nd rows in the second embodiment of the image processing apparatus of the invention. In S82 of FIG. 15, 1 ≦ n
If ≦ H−2, the process proceeds to S86, D _n and D _{n + 1} are input from the image storage unit 2 to the spatial filter processing unit 4, and the next S
At 87, the following spatial filtering process is executed.

First, in S101, K (-1,1) = K (1,1) = 0.0 in D _{n + 1} in the row data multiplication unit 11.
Multiply by 5 to create D _{n + 1} (0.05, 0), which is shifted by 1 pixel to the left and right by the row data shift unit 12 to obtain D _{n + 1} (0.05, 0).
_{n + 1 (0.05, -1)} , to create a D n + 1 (0.05,1). Next, in S102, the row data multiplication unit 11 multiplies D _{n + 1} by K (0,1) = 0.1 to obtain D _{n + 1} (0.
1, 0) is created and stored in the row data temporary storage unit 14. _Let this stored data be A _{n + 1} . Then S1
03, the row data adding unit 13 outputs D _{n + 1} (0.0
5, -1), D _{n + 1} (0.1,0), D _{n + 1} (0.0
5, 1) are added, and this data is stored in the row data temporary storage unit 1
Store in 4. _Let this stored data be B _{n + 1} .

Next, in S104, A _n already stored in the row data temporary storage unit 14 by the processing up to the preceding row.
Read out. A _n is D calculated in the process of the previous row
_{n + 1} (0.1, 0), and D _{n in the} current processing target row
It is a value corresponding to (0.1, 0). The read A _n is _divided by the row data shift unit 12 into left and right one pixel each, and D _n (0.
1, −1) and D _n (0.1, 1) are created. Then S1
In 05, K (0 to D _n in the line data multiplication section 11,
0) = 0.4 is multiplied to create D _n (0.4,0).

Next, in S106, B _n-1 already created by the processing from the row data temporary storage unit 14 to the preceding row and S1
B _{n + 1} created in 03 is read out, and the row data addition unit 13
Where B _{n + 1} , D _n (0.1, −1), D _n (0.4,
0), D _n (0.1, 1), and B _n-1 are added to generate a spatial filter processing result, and this result is output to the image output unit 3.

Next, in step S107, the line data temporary storage unit 14 has no longer used B in future processing.
_{The area in which n−1} and A _n are stored is released, and the processing of the nth row is completed. At this point, the line data temporary storage unit 14 stores A
_{n + 1} (= D _{n + 1} (0.1,0)), B _{n + 1} (= D
_{n + 1} (0.05, -1) + D _{n + 1} (0.1,0) + D
_{n + 1} (0.05, ₁ )), B _n (= D _n (0.05,-)
1) + D _n (0.1,0) + D _n (0.05,1)) is stored, and is similarly used in the processing on and after the next row. As described above, the intermediate result of the processing up to the preceding row is temporarily stored and can be used at the time of processing to another row, whereby the processing can be performed at higher speed. . The spatial filter processing from the first line to the H-2nd line is performed in such a procedure, and then S85 of FIG.
At 1, the n is incremented by 1 and the control is returned to S82.

FIG. 18 is a flow chart showing an example of the processing of the (H-1) th line in the second embodiment of the image processing system of the invention. In S82 of FIG. 15, n = H-
In the case of 1, the process proceeds to S88, D _H-1 is input from the image storage unit 2 to the spatial filter processing unit 4, and the spatial filter process is executed in the next S89.

First, in S111, the A data already stored in the row data temporary storage unit 14 by the processing up to the preceding row.
_H-1 is read out, and the row data shift unit 12 shifts it by 1 pixel to the left and right to obtain D _H-1 (0.1, -1), D _H-1 (0.
1, 1) are created. Next, in S112, the row data multiplication unit 11 multiplies _DH-1 by K (0,0) = 0.4 to create _DH-1 (0.4,0). Next, in step S113, the row data storage unit 14 reads B _H-2 and B _H-1, which have been created by the processing up to the preceding row, and the row data addition unit 13 reads B _{H + 1} , D _H-1 (0 .-1, -1), _DH-1 (0.4,
0), D _H-1 (0.1, 1), and B _H-2 are added to generate a spatial filter processing result, and this result is output to the image output unit 3. Although there is no D _H , B _H-2 , which is the result of calculation using D _H-1 , is read from the row data temporary storage unit 14 and processed.

Finally, in S114, the entire area of the row data temporary storage unit 14 is released to end the processing of the (H-1) th row, and return to FIG. 15 to end the entire processing. In this way, by having a means for temporarily storing the intermediate result of the processing up to the preceding row and using it for the processing of another row, some of the operations necessary for the spatial filter processing of each row are The number can be reduced, and the processing can be performed at higher speed.

FIG. 19 is an explanatory diagram of a specific example of the operation of the spatial filter processing section 4 in the second embodiment of the image processing system of the invention. Here, considering the spatial filter processing in which the filter coefficient shown in FIG. 3 is applied to the run-length format row data shown in FIG. 12B, the processing of the first row will be briefly described. In the processing of the 0th row, the row data temporary storage unit 14 stores A ₁ (= D ₁ (0.1,
0)), B ₀ (= D ₀ (0.05, −1) + D ₀ (0.
1,0) + D ₀ (0.05,1)), B ₁ (= D
₁ (0.05, -1) + D ₁ (0.1,0) + D
₁ (0.05, ₁ )) is stored.

D ₂ is newly read and the filter coefficient 0.
05 by multiplying the calculated the D ₂ (0.05,0), D ₂ and further shifted to the left and right _{(0.05, -1), D 2} (0.
05, 1). In addition, the filter coefficient of D ₂ is 0.1.
Is multiplied by to calculate D ₂ (0.1, 0) (= A ₂ ) and stored in the row data temporary storage unit 14. Then, D ₂ (0.
05, -1) + D ₂ (0.1,0) + D ₂ (0.05,
1) is calculated and stored in the row data temporary storage unit 14 as B ₂ .

Next, A ₁ (= D ₁ (0.1,0)) is read out and shifted to the left and right to D ₁ (0.1, −1), D
Calculate ₁ (0.1, 1). Further, D ₁ is multiplied by the filter coefficient 0.4 to obtain D ₁ (0.4,0). Then, B ₂ + B ₀ + D ₁ (0.1, −1) + D ₁ (0.
Calculate 1,1) + D ₁ (0.4,0). As a result, the row data of the first row in FIG. 12C is obtained.

Calculations are also made for each of the 0th and 2nd lines, and the processing result of the spatial filter processing as shown in FIG. 12C is obtained. In the second embodiment, since the row data temporary storage unit 14 is used, the number of calculations is reduced and high speed processing can be realized.

In the second embodiment, as in the first embodiment, the case where the spatial filter processing is performed using the filter coefficients shown in FIG. 3 has been described as an example. In the case where rows having different coefficients include equal coefficient values, details such as the flow of control and what kind of intermediate result is stored in the row data temporary storage unit 14 are different, but basically, FIG. Processing using the configuration shown in is possible.

FIG. 20 is an explanatory diagram of another example of the filter coefficient used in the spatial filter processing. FIG. 20 shows an example of the filter coefficient used for the differential filter processing as another example of the filter coefficient. In the spatial filter processing using such filter coefficients, B _k−1 (= D _k−1 (−1, −1) + D _k−1 (2,
0) + D _k−1 (−1,1)), B _k (= D _k (−1, −)
1) + D _k (2,0) + D _k (−1,1)), B
_{k + 1} (= D _{k + 1} (-1, -1) + D _{k + 1} (2,0) + D
_The row data temporary storage unit 1 stores the three values of _{k + 1} (-1, 1)).
It can be held at 4. In the 0th row, B ₀ and B ₁ may be calculated and B ₀ + B ₀ + B ₁ may be added. Also, 1-
In the H-2nd row, only B _{k + 1} is calculated, B _k-1 and B _{k are} read from the row data temporary storage unit 14, and B _k-1 + B _k + B
_It is sufficient to calculate _{k + 1} . In the H-1 line, B _H-2 ,
B _H-1 is read from the row data temporary storage unit 14 and B _H-2
It suffices to calculate + B _H-1 + B _H-1 . In this way, the spatial filter processing according to the filter coefficient shown in FIG. 20 can be realized using the row data temporary storage unit 14.

For example, in the smoothing filter processing shown in FIG. 3, A _k , A _{k + 1} , B _k-1 , and B are processed in the k-th row.
_In order to hold _k and B _{k + 1} in the row data temporary storage unit 14, a storage area for five rows was required, but in the differential filter processing by the filter coefficient shown in FIG. It is only necessary to temporarily store the product-sum results for three rows, and the processing can be executed with a smaller amount of calculation than in the case of the filter coefficient shown in FIG.

[0088]

As is apparent from the above description, according to the present invention, the image data converted into the run length format can be subjected to the spatial filter processing in the format as it is, and the processing in the normal pixel unit is possible. This enables high-speed processing with a reduced amount of calculation compared to. Furthermore, the required capacity of the image storage unit 2 can be reduced by storing the image data in the run length format, and it is possible to eliminate the need for a plurality of arithmetic units and the like, which are conventionally required, and the device can be constructed at a relatively low cost. It will be possible. Furthermore, the present invention does not depend on a specific filter coefficient or coefficient size, and has the effect that it is possible to realize a flexible processing device capable of performing arbitrary spatial filter processing with the same configuration.

[Brief description of drawings]

FIG. 1 is a block diagram showing a first embodiment of an image processing apparatus of the present invention.

FIG. 2 is an explanatory diagram of an example of run-length format representation of image data.

FIG. 3 is an explanatory diagram of an example of filter coefficients used for spatial filter processing.

FIG. 4 is a flowchart showing an outline of an operation in the first embodiment of the image processing apparatus of the invention.

FIG. 5 is a flowchart showing an example of spatial filter processing in the first embodiment of the image processing apparatus of the invention.

FIG. 6 is a flowchart showing an example of processing of a row data multiplication unit in the first embodiment of the image processing apparatus of the present invention.

FIG. 7 is an explanatory diagram of a specific example of processing of a row data multiplication unit in the first embodiment of the image processing apparatus of the present invention.

FIG. 8 is a flowchart showing an example of processing of a row data shift unit in the first embodiment of the image processing apparatus of the invention.

FIG. 9 is an explanatory diagram of a specific example of processing of a row data shift unit in the first embodiment of the image processing apparatus of the present invention.

FIG. 10 is a flowchart showing an example of processing of a row data adding unit in the first embodiment of the image processing apparatus of the invention.

FIG. 11 is an explanatory diagram of a specific example of processing of a row data adding unit in the first embodiment of the image processing apparatus of the present invention.

FIG. 12 is an explanatory diagram of a specific example of spatial filter processing in the first embodiment of the image processing apparatus of the invention.

FIG. 13 is an explanatory diagram of a specific example of the operation of the spatial filter processing unit 4 in the first embodiment of the image processing apparatus of the present invention.

FIG. 14 is a block diagram showing a second embodiment of the image processing apparatus of the invention.

FIG. 15 is a flowchart showing an outline of an operation in the second embodiment of the image processing apparatus of the invention.

FIG. 16 is a flowchart showing an example of processing of the 0th row in the second embodiment of the image processing apparatus of the invention.

FIG. 17 is a flowchart showing an example of processing of lines 1 to H-2 in the second embodiment of the image processing apparatus of the invention.

FIG. 18 is a flowchart showing an example of processing in the (H-1) th row in the second embodiment of the image processing apparatus of the present invention.

FIG. 19 is an explanatory diagram of a specific example of the operation of the spatial filter processing unit 4 in the second embodiment of the image processing apparatus of the present invention.

FIG. 20 is an explanatory diagram of another example of filter coefficients used for spatial filter processing.

FIG. 21 is a block diagram showing an example of a conventional image processing apparatus that performs spatial filter processing.

[Explanation of symbols]

1 ... Image input device, 2 ... Image storage unit, 3 ... Image output unit,
4 ... Spatial filter processing section, 5 ... Control section, 11 ... Row data multiplication section, 12 ... Row data shift section, 13 ... Row data addition section, 14 ... Row data temporary storage section.

─────────────────────────────────────────────────── ─── Continuation of front page (58) Fields surveyed (Int.Cl. ⁷ , DB name) H04N 1/409 G06T 5/20 H04N 1/419

Claims (5)

(57) [Claims] 1. An image processing apparatus for performing spatial filter processing on image data composed of row data expressed in a run length format on a row-by-row basis. Alternatively, a shift means for shifting to the left by N pixels and an adder means for adding a plurality of row data are provided, and the spatial filter processing of the run-length-expressed image data is performed using the multiplying means, the shift means and the adder means. An image processing device characterized by the above. 2. An image processing apparatus for performing spatial filter processing on image data composed of row data expressed in a run length format on a row-by-row basis, and multiplication means for multiplying the row data by a filter coefficient. Shifting means for shifting the row data to the right or left by the number of pixels corresponding to the position in the coefficient matrix of the filter coefficient for the row data multiplied by the filter coefficient by the multiplying means, and the row shifted by the shifting means. An image processing apparatus comprising: an addition unit that performs addition on a plurality of row data of the data and the row data multiplied by the filter coefficient by the multiplication unit. 3. The image processing apparatus according to claim 1, further comprising storage means for temporarily storing row data before or after calculation. 4. The adding means extracts the run data at the left end of a plurality of row data to be added, compares the run lengths of each row data to obtain the minimum value thereof, and further obtains the sum of the pixel values of each run. The minimum value of the run length is paired and output as new run data, and the minimum value is subtracted from the run length of the run data of each row. The image processing apparatus according to claim 1, wherein the process of extracting the run data is repeated until the right end of the row. 5. An image compression means for converting an input image into line data expressed in a run length format on a line basis,
An image processing apparatus comprising: the image processing apparatus according to any one of claims 1 to 4; and a restoration unit that restores row data output from the image processing apparatus after spatial filtering processing into an image. .