JP2004312693A - Image encoding apparatus and image encoding method - Google Patents

Abstract

Provided is an image encoding technique capable of realizing a high-speed encoding process with less visual distortion of a hybrid image.
A scanning means for scanning an original image to be encoded in accordance with a predetermined scanning order, and a one-dimensional original image generated by scanning the original image by the scanning means are obtained by calculating a cumulative square error of a pixel value in each section. Alternatively, a segmented linear approximation unit 9 that divides into a plurality of sections so that the variance is equal to or less than a predetermined threshold, and generates one-dimensional approximate image data in which pixel values in each section are approximated by an average value of pixel values in the section. Are provided in correspondence with a plurality of different scanning orders, and the number of sections divided by the segmented linear approximation means 9 of each scanning unit 3 is compared to obtain a one-dimensional approximation having the smallest number of sections. An optimal scanning selecting means 4 for selecting image data.
[Selection diagram] Fig. 1

Description

  The present invention relates to an image encoding technology used for image compression and transmission, and more particularly to an image encoding technology capable of optimally encoding a hybrid image in which an artificial image and a natural image are mixed.

  An image in which a natural image such as a photograph and an artificial image such as characters, figures, and illustrations are mixed is referred to as a mixed image. As a technique for irreversibly compressing a hybrid image, various encoding schemes such as JPEG, GIF, and TIFF have been widely used.

  On the other hand, the nature of the pattern in the image differs depending on whether the original image to be encoded is a natural image or an artificial image. The natural image has a property that the correlation between pixels is large and the pixel value change is continuous. On the other hand, an artificial image generally has the property that there are many continuous sections with the same pixel value and many sharp edges. Due to such a difference in pattern properties based on image attributes, it is difficult for the above-described conventional image encoding method to optimally encode all hybrid images.

  For example, when a hybrid image is encoded by JPEG, mosquito noise is generated in the outline of a character or figure in an artificial image portion, and visually large deterioration occurs. This occurs because JPEG concentrates the spectrum in the low frequency band by discrete cosine transformation (hereinafter referred to as “DCT”) and deletes the high frequency band information. On the other hand, methods such as GIF and TIFF are suitable for compressing artificial images, but have lower coding efficiency for natural images than JPEG.

Therefore, as a technique for optimally encoding such a hybrid image, a hybrid image is divided into two regions: a discrete-tone region mainly composed of an artificial image and a continuous-tone region mainly composed of a natural image. However, a technique for encoding using run-length encoding and JPEG based on the characteristics of each region has been proposed (see Non-Patent Document 1).
Takeshi Mogi, "Compression of Natural and Artificial Mixed Images Based on Segmentation," IEICE, IEICE Transactions D-II, Vol.J82-D-II, No.7, p.1150-1160 , July 1999

  However, in an image coding method in which a hybrid image is separated into two regions, a discrete gradation region mainly composed of an artificial image and a continuous gradation region mainly composed of a natural image, the calculation in the region division calculation of the image is performed. The amount increases. Therefore, it is not suitable for high-speed image compression.

  If parallel processing is performed by hardware, it is possible to increase the speed. However, in this case, the circuit scale becomes extremely large.

  Therefore, an object of the present invention is to realize a high-speed encoding process with little visual distortion of a hybrid image, and to realize a small-scale circuit even in a case of performing parallel processing by hardware. It is an object of the present invention to provide an image coding technique which can be realized by the above.

  A first configuration of an image encoding apparatus according to the present invention includes a scanning unit that scans an original image to be encoded in a predetermined scanning order, and a one-dimensional original image generated by scanning the original image by the scanning unit. A one-dimensional approximation image obtained by dividing the interval into a plurality of sections so that the cumulative square error or variance of the pixel values in the section is equal to or less than a predetermined threshold, and approximating the pixel value in each section by the average value of the pixel values in the section. A plurality of scanning units each having a plurality of scanning units corresponding to a plurality of different scanning orders, and comparing the number of sections divided by the dividing line-type approximation means of each scanning unit, And an optimal scanning selecting means for selecting the minimum one-dimensional approximate image data.

  According to this configuration, each scanning unit divides the one-dimensional original image into a plurality of sections such that the cumulative square error or variance of the pixel values in each section is equal to or less than a predetermined threshold. Then, one-dimensional approximation image data in which pixel values in each section are approximated by an average value of pixel values in the section (hereinafter, this approximation is referred to as “segmented linear approximation”) is generated. The optimum scanning selection means compares the number of sections divided by the segmented linear approximation means of each scanning unit. Then, one-dimensional approximate image data having the minimum number of sections is selected. As described above, the optimal scan selection unit estimates the scan order in which the code amount is minimum after encoding as the scan order in which the number of sections divided by the segmented linear approximation unit is minimum before the image is encoded. . Then, this is selected as the optimum scanning order. If the one-dimensional approximation image data scanned by the optimal scanning order and obtained by the piecewise linear approximation is then encoded by run-length encoding or the like, the original image is optimally encoded.

  If the operation order is selected using the number of sections of the segmented line approximation as an index, an image in which pixel values other than edges change little like an artificial image such as a document image or a graphic image, or an adjacent pixel like a natural image An optimal scanning order for encoding is selected according to the attribute of an image such as an image whose value changes frequently. Therefore, the original image is one-dimensionalized in a scanning order adapted to the properties of the image. Further, in the present invention, a segmented linear approximation is used to approximate an original image for encoding, and an optimal scanning order is selected based on the number of sections in the segmented linear approximation before performing complete encoding. This enables high-speed encoding processing.

  In the present invention, the operation order is selected by comparing the number of sections of the one-dimensional approximate image data obtained by performing the piecewise linear approximation. Thus, the algorithm is simple and can be realized with a small-scale circuit configuration even when the configuration is such that parallel processing is performed by hardware.

  According to a second configuration of the image encoding apparatus of the present invention, in the first configuration, when the segmented linear approximation unit divides the one-dimensional original image into two sections when dividing the one-dimensional original image, Performing a two-segment process of dividing the one-dimensional original image at a segment position where the sum of accumulated square errors or variances of pixel values in both segments is minimized, and performing two segments in the two-segment process. When the cumulative square error or variance of pixel values in the section is equal to or larger than a predetermined threshold, the one-dimensional original image is divided by performing the two-division process recursively in the section. .

  As described above, in the present invention, the segmented line type approximation unit recursively executes the above-described two-segment processing to divide the primary original image into small sections. Thereby, at the time of section division, the edge portion of the image is stored as the division position. Therefore, even when encoding an image in which the edges of the image are enhanced such as an artificial image, visual distortion of the image due to the encoding can be minimized.

  A third configuration of the image encoding apparatus according to the present invention, in the first or second configuration, further includes a small section dividing unit configured to divide the one-dimensional original image into a plurality of small sections. The one-dimensional approximate image data is generated for the one-dimensional original image of each small section divided by the small section dividing means.

  As described above, the one-dimensional original image is divided into small sections by the small section dividing means, and the piecewise linear approximation means performs the piecewise linear approximation for each small section, thereby reducing the amount of calculation performed by the piecewise linear approximation means. Therefore, the encoding process can be sped up. In particular, when recursive processing is used for piecewise linear approximation, the amount of calculation can be significantly reduced by dividing into small sections.

  In a fourth configuration of the image encoding device according to the present invention, in the third configuration, the one-dimensional approximation image data of each of the small sections generated by the piecewise linear approximation unit is opposed to each other in two adjacent small sections. If the difference between the average values of the pixel values in the end section is equal to or less than a predetermined threshold value and the length of one of the sections is equal to or less than the predetermined threshold value, the approximate value of both sections is calculated as the pixel value of the entirety of both sections. It is characterized by comprising merging processing means for replacing with an average value.

  As described above, in the present invention, the opposing extreme end sections of two adjacent small sections are merged under a certain condition by the merging means. This can reduce unnecessary section division and reduce the number of sections in the entire one-dimensional approximate image data. Therefore, the coding efficiency is improved.

  Here, as a condition for merging the two sections, the difference between the average values of the pixel values in both sections is equal to or smaller than a predetermined threshold value. When the difference between the average values of the pixel values in both sections is large, This is because the increase in the approximation error due to the merging increases.

  As a condition for merging two sections, the length of one section is set to be equal to or less than a predetermined threshold value in a short section even if edge information is lost due to merging of sections. This is because practically negligible distortion occurs.

  In a fifth configuration of the image encoding apparatus according to the present invention, in any one of the first to fourth configurations, the optimum scanning selection unit may include a predetermined number of the segmented line approximation units of each scanning unit. At the time when the one-dimensional approximation image data generation process has been completed, the one-dimensional approximation image data generation process for which the one-dimensional approximation image data generation process has not been completed is terminated and the process is terminated. The method is characterized in that the number of sections divided by the segmented linear approximation means of the scanning unit is compared, and one-dimensional approximate image data having the smallest number of sections is selected.

  In general, the time for the segmented line approximation processing by the segmented line approximation means increases as the number of sections to be segmented increases. Therefore, there is a high possibility that the number of sections of the scanning unit in which the generation processing of the one-dimensional approximate image data has been completed early is the minimum. Therefore, when the segmented line approximation processing of a predetermined number of scanning units is completed, the segmented line approximation processing may be terminated for the remaining scanning units. In this way, by terminating the piecewise linear approximation processing for the remaining scanning units, the processing of the optimum scanning selection unit can be terminated early, and the processing speed can be increased.

  According to a sixth configuration of the image encoding apparatus of the present invention, in any one of the first to fourth configurations, the optimum scan selection unit is configured such that one of the segmented line approximation units of each scanning unit is one. The clock counting is started from the time when the generation processing of the one-dimensional approximate image data is completed, and the processing is discontinued for the segmented line type approximation means for which the one-dimensional approximate image data generation processing is not completed within a predetermined time. The method is characterized in that the number of sections divided by the segmented linear approximation means of the scanning unit that has completed the processing within the predetermined time is compared, and one-dimensional approximate image data having the smallest number of sections is selected.

  The number of sections of the scanning unit in which the one-dimensional approximation image data generation processing is not completed within a predetermined time from the time when one of the segmented linear approximation means of each scanning unit has completed the one-dimensional approximate image data generation processing is as follows: It is considered that the number is larger than the number of sections of the one-dimensional approximate image data in the scanning unit in which the piecewise linear approximation processing is completed first. Therefore, for such a scanning unit that requires a long processing time, by terminating the piecewise linear approximation processing at a predetermined time, it is possible to optimally select a scanning order and shorten the encoding processing time.

  According to a seventh aspect of the image encoding apparatus of the present invention, in the configuration of any one of the first to fourth aspects, the optimum scan selecting means is such that one of the segmented line approximation means of each scanning unit is one. When the generation processing of the one-dimensional approximation image data is completed, the number of sections of the one-dimensional approximation image data is transmitted to the other scanning units as the number of reference sections, and the section line type approximation means of each scanning unit transmits the reference section. When receiving the number, when the number of sections obtained by dividing the one-dimensional original image exceeds the number obtained by adding a predetermined value to the number of reference sections, the generation processing of the one-dimensional approximate image data is terminated, and Compares the number of sections divided by the segmented linear approximation means of the scanning unit after the generation processing of the one-dimensional approximate image data, and selects the one-dimensional approximate image data having the smallest number of sections. And butterflies.

  As described above, when the number of sections exceeds the number of reference sections plus a predetermined number, it is unlikely that the number of sections will be less than the number of reference sections even if the merge processing or the like is performed thereafter. Therefore, for the scanning unit having such a large number of sections, the optimal selection of the scanning order can be performed by terminating the piecewise linear approximation processing when the number of sections reaches a predetermined number, and the encoding processing can be performed. Time can be reduced.

  A seventh aspect of the image encoding apparatus according to the present invention is the image encoding apparatus according to any one of the first to seventh aspects, wherein: the orthogonal transform means for performing an orthogonal transform on an original image to be encoded to generate a transformed image; Quantizing means for quantizing an image by adaptive bit allocation to generate a quantized transformed image, and a run length in which the quantized transformed image is scanned along a predetermined path, and pixels having the same value continue along the scanning path, and At least one orthogonal transformation unit having run data generation means for generating run data consisting of a set of pixel values for the run, wherein the optimal scan selection means comprises: the segmented linear approximation means for each scan unit. Are compared with the number of runs generated by the run data generating means of the orthogonal transform unit (hereinafter referred to as “run number”), and the number of sections or one-dimensional ones having the minimum number of runs is compared. And selects the image data or run-data.

  According to this configuration, the number of runs output by the orthogonal transformation unit is smaller than the number of sections output by each scanning unit for an image such as a natural image having a good compression ratio by orthogonal transformation. Therefore, the optimum scan selecting means selects the run data having the minimum number of runs. In this way, one-dimensional approximation image data or run data is selected depending on the nature of the image, and more optimal encoding is achieved. As a result, the coding efficiency is further improved.

  Note that "adaptive bit allocation" means that in a normal image, a large number of bits are allocated to pixels on the low frequency side where the power of the pixel signal is concentrated and quantized, and the pixel signal power is reduced to a high frequency component having a small power. On the other hand, it means quantization with a small number of bits. This adaptive bit allocation is a widely used method in transform coding.

  A first configuration of the image encoding method according to the present invention is that a one-dimensional original image generated by scanning an original image to be encoded according to a predetermined scanning order is obtained by calculating a cumulative square error or a variance of pixel values in each section. A segmented linear approximation process for generating one-dimensional approximation image data in which a plurality of sections are divided so as to be equal to or less than a predetermined threshold and pixel values in each section are approximated by an average value of pixel values in the section, A first step performed in parallel with each of the scanning orders, and comparing the number of sections of each one-dimensional approximation image data obtained by the piecewise linear approximation processing with respect to each of the scanning orders, to determine whether the number of sections is the smallest one. The method has a second step of selecting the one-dimensional approximate image data and a third step of encoding the selected one-dimensional approximate image data.

  A second configuration of the image encoding method according to the present invention is the image processing method according to the first configuration, wherein the one-dimensional original image is divided into two sections when the one-dimensional original image is divided in the segmented linear approximation processing. In addition, a two-division process of dividing the one-dimensional original image at a division position where the sum of the accumulated square errors or the variances of the pixel values in both the intervals is minimized, and the two segments divided by the two-division process are performed. In the case where the cumulative square error or variance of pixel values in the section is equal to or greater than a predetermined threshold, the two-dimensional processing is recursively performed in the section to partition the one-dimensional original image. I do.

  In a third configuration of the image encoding method according to the present invention, in the first or second configuration, in the first step, a transformed image is generated by performing an orthogonal transform on an original image to be encoded, and the transformed image is generated. Is quantized by adaptive bit allocation to generate a quantized conversion image, the quantized conversion image is scanned along a predetermined path, and a run length in which pixels of the same value continue along the scanning path, and a pixel value for the run. Scanning is performed in parallel to generate run data consisting of a set of .times..times..times..times..times..times..times..times..times..times..tim- es..times..times..times..times..times. The number of runs of the run data (hereinafter referred to as “run number”) is compared, and one-dimensional approximate image data having the smallest number of sections or runs is selected. In the third step, the selected one-dimensional approximate image data is selected. The one-dimensional approximation image data or run-data, characterized in that encoding.

  As described above, according to the present invention, a change in pixel values other than edges, such as an artificial image such as a document image or a graphic image, is performed by selecting an operation order using the number of sections of the segmented line approximation as an index. The optimal scanning order for encoding is selected according to the attributes of an image such as an image having a small change and an image having a large change in adjacent pixel values such as a natural image. Therefore, the original image is one-dimensionalized in a scanning order adapted to the properties of the image.

  In addition, by using a piecewise linear approximation for approximating the original image for encoding, and before performing complete encoding, by selecting an optimal scanning order based on the number of sections in the piecewise linear approximation, High-speed encoding processing becomes possible.

  Hereinafter, the best mode for carrying out the present invention will be described with reference to the drawings.

  FIG. 1 is an overall configuration diagram of an image encoding device according to Embodiment 1 of the present invention. In FIG. 1, an image encoding apparatus according to a first embodiment of the present invention includes an image input unit 1, an image area dividing unit 2, n (n ≧ 2) scanning units 3-1 to 3-n, and optimal scanning selection. It has means 4, encoding means 5, and compressed image data output means 6.

  The image input means 1 is for inputting data of an original image to an image input device. As the image input means 1, an image pickup device such as a CCD device, an image storage device such as a television receiver, a magnetic disk device, or the like is used. The image area dividing means 2 divides an image input from the image input means 1 into a plurality of small areas (image blocks). Each scanning unit 3-i (i = 1,..., N) scans each image block divided by the image area dividing means 2 and performs a segmented line type approximation process in a predetermined scanning order determined respectively. 1. Generate one-dimensional approximate image data.

  The optimal scanning selecting means 4 compares the number of sections of the one-dimensional approximate image data generated by each scanning unit 3-i (i = 1,..., N) and selects the one-dimensional approximate image data of the minimum number of sections. I do. The encoding unit 5 encodes the one-dimensional approximation image data selected by the optimal scanning selection unit 4 according to various encoding methods, and outputs an encoded image. The image compression data output unit 6 outputs the encoded image generated by the encoding unit 5. As the compressed image data output means 6, an image transmitter, an image storage device, or the like is used.

  FIG. 2 is a block diagram showing the configuration of each scanning unit 3-i (i = 1,..., N) in FIG. The scanning unit 3-i (i = 1,..., N) includes a scanning unit 7, a small section dividing unit 8, a segmented line approximation unit 9, and a merging processing unit 10.

  The scanning means 7 scans each image block divided by the image area dividing means 2 in accordance with the scanning order determined respectively, and generates a one-dimensional original image. The scanning means 7 comprises an image area memory 7a and a scanning address generator 7b. In the image area memory 7a, pixel values in an image block are stored in each memory address in accordance with the scanning order. The scanning address generator 7b generates scanning coordinates in an image block according to a scanning order determined for each of the scanning units 3-i (i = 1,..., N). The image area memory 7a scans the image block by acquiring the pixel value at the scanning coordinates from the image block.

  The small section dividing unit 8 further divides the one-dimensional original image generated by the scanning unit 7 into a plurality of small sections (hereinafter, the original image data in each small section is referred to as “small section data”). The segmented line approximation unit 9 generates a small segment approximation image obtained by approximating the small segment data generated by the small segment division unit 8 by the segmented line approximation. The merging processing unit 10 merges the small section one-dimensional approximate image data generated by the piecewise linear approximation unit 9 by a predetermined method to generate one-dimensional approximate image data. Then, the one-dimensional approximation image data is output to the optimal scanning selection unit 4.

  FIG. 3 is a block diagram showing a configuration of the segmented linear approximation means 9 of FIG. The segmented line type approximating means 9 includes a small section memory 11, a section register 12, a section division processing section 13, a division processing control section 14, and a small section approximate image memory 15.

  The small section memory 11 stores the small section data divided by the small section dividing means 8. The section register 12 stores data of a section to be subjected to a piecewise linear approximation (hereinafter, referred to as “processed section data”) among the pixel value data stored in the small section memory 11. The section division processing unit 13 performs section division processing on the section data to be processed stored in the section register 12. Here, the “section division processing” is to divide the processing section data at a position where, when the processing section data is divided into two sections, the sum of the accumulated square errors of the pixel values of both sections is minimum. In addition, it refers to a process of approximating data of each divided section with an average value of pixel values in the section.

  The division processing control unit 14 recursively performs the section division processing on the small section data stored in the small section memory 11 by the section division processing unit 13. Then, the division processing control unit 14 performs the section division processing recursively so that the cumulative square error of the pixel value in each section of the divided small section data is equal to or less than a predetermined threshold, and performs the one-dimensional approximation image. Generate data. The small section approximate image memory 15 stores the one-dimensional approximate image data generated by the division processing control unit 14.

  FIG. 4 is a block diagram illustrating a configuration of the section division processing unit 13 in FIG. In FIG. 4, the section division processing unit 13 includes an address generation unit 21, a square multiplier 22, a square addition accumulator 23, an addition accumulator 24, a square multiplier 25, an up counter 26, a divider 27, a subtracter 28, and a division unit. , A subtraction accumulator 30, a square subtraction accumulator 31, a self-multiplier 32, a down counter 33, a divider 34, a subtractor 35, a divider 36, an adder 37, a comparison judging unit 38, a minimum cumulative error memory 39, It includes a segmented linear approximation end determination unit 40, a left error register 41, a right error register 42, a left level register 43, a left section length register 44, a right level register 45, and a right section length register 46. The function of each unit will be described together with the operation description described later.

  FIG. 5 is a block diagram showing the configuration of the merging processing means 10 of FIG. In FIG. 5, the merging processing unit 10 includes a merging process determining unit 51, a merged data generating unit 52, and a merging section register 53.

  The merging process determination unit 51 determines that, for each of the small section data stored in the small section approximate image memory 15, the difference between the average values of the pixel values of the opposing extreme end sections in two adjacent small sections is equal to or less than a predetermined threshold value. And whether the length of one section is equal to or less than a predetermined threshold value. Further, the merged data generation unit 52 calculates, for each of the small section data stored in the small section approximate image memory 15, the approximate value of the opposing extreme end section in two adjacent small sections to the pixel value of the entire two sections. The process of replacing with the average value is performed. The merging section register 53 temporarily stores the small section data after the merging process has been performed.

  The merging process determining unit 51 includes a first level difference determining unit 61, a second level difference determining unit 62, a pre-boundary section length determining unit 63, a post-boundary section length determining unit 64, and a merging process comprehensive determining unit 65. ing. Further, the merged data generation unit 52 includes two multipliers 66 and 67, two adders 68 and 69, and a divider 70. The function of each of these units will be described together with the operation description described later.

  FIG. 6 is a block diagram showing the configuration of the optimum scanning selection means 4 of FIG. In FIG. 6, the optimal scanning selecting means 4 includes an optimal scanning determining unit 81 and an optimal scanning selector 82.

  The optimum scanning determination unit 81 is the one-dimensional approximate image data of the one-dimensional approximate image data that is divided by the segmented linear approximation unit 9 of each scanning unit 3-i (i = 1,..., N) and merged by the merge processing unit. A small number is determined, and the number (hereinafter, referred to as “optimal scanning number”) m of the scanning unit is output. The optimal scanning selector 82 selects the one-dimensional approximate image data output by the scanning unit 3-m of the optimal scanning number m, and outputs it to the encoding unit 5.

  FIG. 7 is a block diagram showing the configuration of the encoding means 5 of FIG. 7, the encoding unit 5 includes a scanning information encoding unit 91, a luminance information encoding unit 92, a section length information encoding unit 93, and an encoded information combining unit 94.

  The scan information encoding unit 91 encodes the optimal scan number m output from the optimal scan selection unit 4 by entropy encoding using a Huffman code or the like based on the scan frequency. The luminance information encoding unit 92 encodes the luminance information of each section in the one-dimensional approximation image data output by the optimal scanning selection unit 4 by entropy encoding using a Huffman code of a luminance level difference value or the like. Do. The section length information encoding unit 93 performs encoding by entropy encoding using Weyl code or the like on the section length information of each section in the one-dimensional approximate image data output by the optimal scanning selection unit 4.

  The image encoding method of the image encoding apparatus according to the present embodiment configured as described above will be described below. FIG. 8 is a flowchart illustrating a flow of the entire processing of the image encoding method according to the first embodiment.

When the image encoding device in the present embodiment encodes an original image, first, data of the original image is input to the image input unit 1 (S1). When an original image is inputted, then the image area dividing unit 2 divides the original image into image blocks of _{M b-number (M b> 1) (S2} ). When the division of the image is completed, the image region dividing means 2 sets 1 to a parameter i representing the number of the image block to be encoded (S3).

  Next, the image area dividing means 2 outputs a scanning start instruction to each of the scanning units 3-1 to 3-n (S4). Thereby, each of the scanning units 3-1 to 3-n starts scanning of the image block and the segmented line type approximation process.

  Each of the scanning units 3-1 to 3-n transmits a processing end signal to the optimum scanning selection means 4 when the piecewise linear approximation processing is completed. The optimal scanning selection means 4 waits until a processing end signal is transmitted from all the scanning units 3-1 to 3-n (S5).

Here, in the segmented-line approximation processing, the one-dimensional original image data scanned and made one-dimensional by the scanning unit 7 is divided into a plurality of sections by the segmented-line approximation unit 9, and the pixel value of each section is set in the section. Is approximated by the average value of the pixel values in. At this time, the section is divided so that the cumulative square error of the pixel value in each section is equal to or smaller than a predetermined threshold σ _th ² . Therefore, the one-dimensional approximate image data generated by each scanning unit 3-k (k = 1,..., N) is ｛(c _i ^(k) , l _i ^(k) ); i = 1,. _section ^(k) ｝ (where c _i ^(k) is the average value of the pixels in section i, l _i ^(k) is the section length of section i, and N _section ^(k) is the total number of sections). Data.

  Each of the scanning units 3-1 to 3-n scans an image block in a different scanning order. As the scanning order, for example, various scanning orders such as raster scanning, zigzag scanning, spiral scanning, and Hilbert scanning as shown in FIG. 9 can be used.

When the processing end signals are transmitted from all the scanning units 3-1 to 3-n, the optimal scanning selecting unit 4 determines the number of sections of the one-dimensional approximate image data generated by each of the scanning units 3-1 to 3-n. N _section ^(k) (k = 1,..., N) are compared (S6), and one-dimensional approximate image data ｛(c _i ^(m) , l _i ^(m) ) having the smallest number of sections; i = 1, .., N _section ^(m) ｝ (m = argmin _k N _k ) is selected (S7). This is because the smaller the number of sections N _section ^(k) , the smaller the code amount of the one-dimensional approximation image data, and the better the coding efficiency.

As described above, before the image is encoded, the code amount after encoding is determined by the number of sections N _section ^(k) (k = 1,..., N) of the one-dimensional approximate image data obtained by the piecewise linear approximation processing. Is estimated, and the one-dimensional approximate image data that is estimated to have the smallest code amount can be selected in a short processing time, and the scanning order most suitable for the attribute of the image can be selected. Also, as described later, since the edge of the image has a strong tendency to be the division point of the section in the segmented line approximation processing, the sharper the edge of the image, the better the image edge is stored in the one-dimensional approximate image data. Therefore, in an image having a sharp edge such as an artificial image, visual distortion at the edge of the image can be minimized.

  Next, the encoding unit 5 encodes the selected one-dimensional approximate image data (including information on the scanning order) by a normal method such as a Huffman encoding method or a run-length encoding method (S8). Then, the encoded data of the i-th image block is output by the image compression data output means 6 (S9).

Then, the image coding apparatus, the value of the parameter i is incremented by 1, i is between equal to or less than M _b (S11), it repeats the operations from the step S4 to S10, for all image blocks Perform encoding processing.

  Finally, in step S11, when the parameter i becomes larger than Mb, the image encoding process ends.

The above is the overall processing flow of the image encoding method in the present embodiment. Hereinafter, the operation of each unit of the image encoding device will be described in more detail.
FIG. 10 is a flowchart showing the data processing of the scanning unit 3-k (k = 1,..., N), FIG. 11 is a diagram showing an example of the scanning order in the image block, and FIG. 12 shows the contents of the image area memory 7a. FIG. 13 is a diagram showing the contents of the memory in the scan address generator 7b. 11 to 13, the size of the image block is p × q pixels. Note that FIG. 9 shows scanning of a square area as an example of scanning, but it is easy to extend or combine these square area scans or scan them with a rectangular area.

  When the scanning unit 3-k receives the scanning start instruction from the image area dividing unit 2, first, the scanning unit 7 scans the image block to generate a one-dimensional original image (S21).

  At this time, the pixel values of the original image are stored in the image area memory 7a in the order shown in FIG. The scanning address generator 7b has a memory for storing the scanning order. When the scanning unit 3-k performs the zigzag scanning as shown in FIG. 11, the memory in the scanning address generator 7b stores the correspondence of the image area memory 7a according to the zigzag scanning order as shown in FIG. Address is stored. Then, the scanning address generator 7b sequentially outputs the addresses of the image area memory in the scanning order according to the clock. The image area memory 7a outputs the pixel data stored at the address input from the scan address generator 7b. Thus, a one-dimensional original image scanned in a predetermined scanning order is generated.

  Next, the small section dividing means 8 equally divides the one-dimensional original image into M (M> 1) small sections to generate small section data (S22). This small section division is performed in order to perform a recursive section division process described later with a small number of calculations. Each small section data is temporarily stored in a small section memory 11 inside the segmented line type approximation means 9.

  Next, the piecewise linear approximation unit 9 sets a counter i as an internal variable to 1 (S23). This counter i indicates the number of the small section data to be subjected to the segmented line type approximation processing.

  Next, the section line type approximation means 9 sets the small section data of the i-th small section 1 in the section register 12 (S25). Then, the section division processing unit 13 and the division processing control unit 14 perform the segmented line approximation processing on the i-th small section data (S26 to S28). This piecewise linear approximation is performed by a recursive algorithm such as (Equation 1).

Here, the section division processing is a division position where when the section l is divided into two, the cumulative square error of the pixel values in the left and right sections is minimized, and the section l is divided into two sections l _l , l _r Refers to the process of dividing into The details of this section division processing will be described later.

In the second line of (Equation 1), the section l is subjected to the section dividing process, so that the two divided sections l _l and l _r and the cumulative square errors e _{l, min} and e _r of the pixel values in each section are obtained. _, the average c _l of pixel values in _min and each section, c _r is obtained. Incidentally, are omitted because the (number 1), c _l, not directly related to the c _r.

In the third to fifth rows of (Equation 1), if the cumulative square error e _{l, min} of the pixel values in the divided left section l _l is larger than a predetermined threshold value e _{th in} the section l _l , About _l l, a recursive partitioned linear approximation processing. On the other hand, if the cumulative square error e _{l, min} is equal to or less than the predetermined threshold value e _th , the section line approximation processing is not performed for the section l _l .

The 6-8 line (number 1), also in section l _r of the divided right, cumulative square error e _r of the pixel values within the _interval, if _min is greater than a predetermined threshold value e _th , for the interval l _r, recursively performs division linear approximation, the cumulative square error e _r, if _min is equal to or less than a predetermined threshold value e _th, for the section l _r, divided linear approximation is not performed.

By the above piecewise linear approximation processing, the i-th small section data is further divided into small section one-dimensional approximate image data including f (i) sections. Then, the cumulative square error of the pixel value in each section is suppressed to a predetermined threshold value _eth or less. Therefore, if a sharp edge of the image is included in the section, the cumulative square error in the section cannot be suppressed to the predetermined threshold value e _th or less, so that the section is divided at the edge portion, and the sharp edge of the image is included in the section. Are divided so that they are not That is, the edge of the image is stored as the boundary of the section by the above-described segmented line type approximation processing.

  The section division processing is performed by the section division processing unit 13, and the control of the recursive processing as described above is performed by the division processing control unit 14. In addition, for the section in which the approximate value is determined by the segmented line approximation processing, the average value of the section length and the pixel value is stored in the small section approximate image memory 15.

  When the piecewise linear approximation processing for the i-th small section data is completed, the piecewise line type approximation means 9 increments the value of the counter i by 1 (S29). If the value of i is not larger than M (S30), the processes of steps S25 to S29 are repeated again.

  On the other hand, if i> M in step S30, the segmented linear approximation unit 9 transmits a processing end signal to the optimal scan selection unit 4 (S31). Then, the merging process is performed for the end section of each small section (S32), and the scanning unit 3-k ends the data processing.

  Next, a supplementary explanation will be given of the section dividing process. FIG. 14 is a flowchart showing the section dividing process by the section dividing section 13 of FIGS. 3 and 4, and FIG. 15 is a diagram showing the calculation output at each node of FIG.

First, when the processing section data {x _i ; i = 1,..., N} whose section length is N is set in the section register 12, the clear signal is input to the square addition accumulator 23 and the addition accumulator 24. , The accumulated values of both accumulators are cleared to zero. The up counter 26 is also reset. Then, the address generation unit 21 increases the address value input to the section register 12 by one in ascending order every clock. Along with this, the node (1) is the output of the interval register 12, the pixel value x _i is output to the clock value i (1 ≦ i ≦ N) .

The square multiplier 22 outputs a value x _i ² obtained by squaring the pixel value x _i input from the node (1) to the node (2). The square addition accumulator 23 accumulates the output value of the node (2) every clock. Therefore, when the clock value is i (1 ≦ i ≦ N), Σ _{k = 1} ⁱ x _k ² is stored in the square addition accumulator 23 as an accumulated value.

Similarly, the addition accumulator 24 accumulates the output value of the node (1) every clock. Therefore, when the clock value is i (1 ≦ i ≦ N), 加 算_{k = 1} ⁱ x _k is stored in the addition accumulator 24 as an accumulated value.

  The up counter 26 counts the number of clocks, and when the clock value is i (1 ≦ i ≦ N), i is output to the node (6).

When the clock value i is changed from 1 to N, the adder accumulator 24 is stored in the S _{r, 1} value (number 2), the square sum accumulator 23, S _{r, 2} (Equation 3) The value is stored. The count value of the up counter 26 is N.

When the clock value becomes N + 1, the values of the addition accumulator 24 and the square addition accumulator 23 are set in the subtraction accumulator 30 and the square subtraction accumulator 31, respectively. That is, at the clock value N + 1, the values of S _{r, 1} and S _{r, 2} shown in (Equation 2) and (Equation 3) are set in the subtraction accumulator 30 and the square subtraction accumulator 31, respectively. Is output to the nodes (10) and (9) (S41).

  At the same time, a clear signal is input to the addition accumulator 24 and the square addition accumulator 23, and the accumulated values of both accumulators are cleared to 0 again. Further, the count value N of the up counter 26 is set in the down counter 33, and this is output to the node (12). The up counter 26 is reset again. Further, the address value generated by the address generation unit 21 is also reset (S42). At this time, the value of the left section length register 44 is set to 0, the value of the right section length register 46 is set to N, and the value of (Equation 4) is set to the minimum cumulative error memory 39 as initial values.

Further, when the clock value increases by one from N + 1, the address generation unit 21 increases the address value input to the section register 12 by one in ascending order every clock. Along with this, the node (1) is the output of the interval register 12, when the clock value is N + N ₁ +1 in (1 ≦ N ₁ ≦ N1), the pixel value x _N1 is output. Then, nodes (2), (3), (4), and (6) have x _N1 ² , S _{l, 2} = Σ _{k = 1} ^N1 x _k ² , S _{l, 1} = Σ _{k = 1} ^N1 x _k, N ₁ is output. The square adder 25 outputs a value S _{l, 1} ² = (Σ _{k = 1} ^N1 × _k ) ² _obtained by squaring the output value of the node (4) to the node (5). Further, the divider 27 outputs a value _{Sl, 1} ² / N ₁ obtained by dividing the output value of the node (5) by the output value of the node (6). Divider 29 outputs the node values S _{l, 1} / N ₁ divided by the output value of the node (6) the output value of (4) to the node (16). This is the average value of the pixel values of the left sections of length N _1. The subtracter 28 outputs a value (Equation 5) obtained by subtracting the output value of the node (7) from the output value of the node (3) to the node (8).

Further, the square subtraction accumulator 31 subtracts the output value of the node (2) from the set value every clock and outputs the result to the node (9). Therefore, when the clock value is N + N ₁ +1 (1 ≦ N ₁ ≦ N−1), S _{r, 2} = Σ _{k = N1 + 1} ^N × _k ² is output to the node (9). The subtraction accumulator 30 subtracts the output value of the node (1) from the set value every clock and outputs the result to the node (10). Therefore, when the clock value is N + N ₁ +1 (1 ≦ N ₁ ≦ N−1), S _{r, 1} = Σ _{k = N1 + 1} ^N × _k is output to the node (10). Squaring unit 32 outputs the node value S _{r, 1} ² which squares the output value of (10) to the node (11). On the other hand, when the clock value increases by one from N + 1, the down counter 33 decreases the value from the set value N by one for each clock. Therefore, when the clock value is N + N ₁ +1 (1 ≦ N ₁ ≦ N−1), NN ₁ is output to the node (12). Divider 34 outputs node node output value (11) (12) a value S _r divided by the output value _{of, 1} ² / (NN ₁₎ to the node (13) (S44). The subtractor 35 outputs a value (Equation 6) obtained by subtracting the value of the node (13) from the value of the node (9) to the node (14).

Further, the divider 36 outputs a value S _{r, 1} / / (NN ₁ ) obtained by dividing the output value of the node (10) by the output value of the node (12) to the node (17). This is the average value of the pixel values of the right section of length NN _1.

  The adder 37 outputs a value (Equation 7) obtained by adding the output value of the node (8) and the output value of the node (14) to the node (15) (S45). This is the sum of the accumulated square errors of the left and right sections.

The comparison determination unit 38 compares the output value e of the node (15) with the determination value e _min stored in the minimum cumulative error memory 39 (S46). Then, when e <e _min , the comparison determination unit 38 updates the value of the determination value e _min stored in the minimum cumulative error memory to the output value e of the node (15). At the same time, the comparison determination unit 38 temporarily sets each of the left error register 41, the right error register 42, the left level register 43, the right level register 45, the left section length register 44, and the right section length register 46 to a write state. I do. Thus, the left error register 41 and right error register 42, respectively, the node (8), the output value e _l of the node _{(14), min,} e _{r, min} is captured and stored. The left level register 43 and the right level register 45 capture and store the average values (Equation 8) and (Equation 9) of the pixel values in the left and right sections.

The left section length register 44 and the right section length register 46 receive and store the output values l _l = N ₁ and l _r = NN _{1 of} the nodes (6) and (12), respectively (S47). ).

Then, the counter value N ₁ of the up-counter 26 at the next clock is increased by 1 (S48). Category linear approximation end determining unit 40, the counter value N ₁ is determined whether exceeds N-1 (S49), and repeats the operation of the S43~S48 until the counter value exceeds N-1.

Thus, while moving the division point from left to right of the section data to be processed, the division point that minimizes the sum of the accumulated square errors of both division sections is brute-force searched. When the brute force search is completed, the left error register 41, the right error register 42, the left level register 43, the right level register 45, the left section length register 44, and the right section length register 46 have both divided sections. accumulated squared error value e _l of the left and right sections at the division point where the sum is minimum cumulative square _{error, min,} e _{r, min,} average value c _l of the pixel values, c _r, and the length l _l of the section, l _r is retained.

  Therefore, when the above processing is completed, the section division processing unit 13 outputs the values held in these registers to the division processing control unit 14 (S50), and ends the operation.

  Finally, a supplementary description of the merging process of the merging processing means will be given. FIG. 16 is a flowchart showing the operation of the merging process by the merging processing means, and FIG. 17 is a diagram showing the contents of the small section approximate image memory 15.

  This merging process is performed by dividing the data into small section data by the small section dividing means 8 in order to reduce the amount of calculation in the recursive processing in the piecewise line approximation processing, and generating M pieces of one-dimensional data generated by the piecewise line approximation processing. When the approximate image data is combined again, the two sections are combined under predetermined conditions according to the level difference and the section length of the section at each connection boundary. By performing this processing, the coding amount is further reduced and the coding efficiency is improved.

  First, as a premise, the piecewise linear approximation processing for M pieces of small section data of an image block is completed, and M pieces of small section one-dimensional approximate image data are stored in the small section approximate image memory 15 as shown in FIG. I have. In the merging process, the last section (f (i) th section) in the i-th (i = 1,..., N-1) small section and the first section (first section) in the i + 1-th small section Is performed.

In the merging process, first, the merging processing means 10 sets i = 1 (S60), and from the small-section approximate image memory 15, stores the last section (i = 1,..., N-1) in the i-th (i = 1,... The pixel value c _{i, f (i)} and the section length l _{i, f (i) of the f (i)} th section) and the pixel value c _i of the first section (the first section) in the (i + 1 ₎ th small section ₊₁ and ₁ and the section length l _{i + 1} and ₁ are read (S61).

Then, the first level difference determining unit 61 of the merging process determining unit 51 determines whether or not the pixel values c _{i, f (i)} and c _{i + 1,1} are the same (S62). If so, 1 is output to the node (1), and if they are not the same, 0 is output to the node (1).

In addition, the second level difference determination unit 62 determines whether the absolute value of the difference between the pixel values c _{i, f (i)} and c _{i + 1,1} is equal to or smaller than a predetermined threshold Δc _th (S63). ), | C _{i, f (i)} −c _{i + 1,1} | ≦ Δc _th , outputs 1 to the node (2), and | c _{i, f (i)} −c _{i + 1,1} If |> Δc _th , 0 is output to node (2).

Further, the pre-boundary section length determining unit 63 determines whether the section length l _{i, f (i)} is equal to or less than a predetermined threshold l _th1 , and the post-boundary section length determining unit 64 determines that the section length l _{i + 1 , 1} is less than or equal to a predetermined threshold l _th2 (S64). Then, the pre-boundary section length determining unit 63 and the post-boundary section length determining unit 64 respectively _assign 1 to the node (3) when l _{i, f (i)} ≦ l _th1 and l _{i + 1,1} ≦ l _th2 . (4), and outputs 0 to the nodes (3) and (4) when l _{i, f (i)} > l _th1 and l _{i + 1,1} > l _th2 .

  The merging process comprehensive determination unit 65 performs a logical operation of (1) ∨ ((2) ∧ ((3) ∨ (4))) on the logical values output to the nodes (1) to (4), The calculation result is output to the node (5). That is, when the value of the node (5) is 1, it is determined that both sections are to be merged, and when the value of the node (5) is 0, it is determined that both sections are not to be merged.

Here, the above-mentioned determination method will be supplementarily described. First, when the pixel values c _{i, f (i)} and c _{i + 1,1} of both sections are equal, there is no particular problem in merging both sections. In the case where c _{i, f (i)} and c _{i + 1,1} are not equal, the absolute value | c _i, of the difference between the pixel values c _{i, f (i)} and c _{i + 1,1} in both sections _{If f (i)} −c _{i + 1,1} | is large, both sections should not be merged because they may be image edges. This is determined by the threshold value Δc _th .

On the other hand, even _if the absolute value | c _{i, f (i)} −c _{i + 1,1} | of the difference between the pixel values c _{i, f (i)} and c _{i + 1,1} in both sections is small, In the case where both sections are long, if the approximate error cumulative square error of both sections becomes large due to the merging, it becomes strongly recognized visually. Therefore, even when the absolute value | c _{i, f (i)} −c _{i + 1,1} | is small, merging of sections is not performed when both section lengths are long. This is determined by threshold _values l _th1 and l _th2 .

As a result, when 1 is output as the output value of the node (5), the merging data generation unit 52 performs the merging process of both sections (S65). The multiplier 66 of the merged data generation unit 52 calculates the product of c _{i, f (i)} and l _{i, f (i)} and outputs the result to the node (6). The multiplier 67 calculates the product of c _{i + 1,1} and l _{i + 1,1} and outputs the result to the node (7). The adder 68 adds the output value of the node (6) and the output value of the node (7) and outputs the result to the node (8). The adder 69 adds l _{i, f (i)} and l _{i + 1,1} and outputs (Equation 10) to the node (9).

  Further, the divider 70 multiplies the output value of the node (8) by the output value of the node (9), and outputs (Expression 11) to the node (10).

The merging section register stores the sum l ′ _{i + 1,1} of the section lengths of both sections and the average value c ′ _{i + 1,1} of the pixel values of both sections, thus obtained. Then, when 1 is output to the node (5) by the merging process comprehensive determination unit 65, the value (ci _{+ 1,1} , _... , _{C1 + 1,1} , _... ) Of the (i + 1) th small section data of the small section approximate image memory 15 l _{i + 1,1} ) is updated with (c ′ _{i + 1,1} , l ′ _{i + 1,1} ). Also, the value (ci _{, f (i)} , li _{, f (i)} ) of the last section of the i-th small section data in the small section approximate image memory 15 is updated with (0, 0) and becomes invalid. Processing is performed.

  In the present embodiment, the cumulative square error is used as an evaluation criterion for determining whether or not to divide a section in the piecewise linear approximation processing, but a variance value other than the cumulative square error may be used.

  In the first embodiment, in step S5 in FIG. 8, the optimal scan selection unit 4 waits until the processing end signals are transmitted from all the scan units 3-1 to 3-n. If the processing of all the scanning units 3-1 to 3-n is waited uniformly, the processing time is determined by the scanning in the scanning order that requires the longest time for the piecewise linear approximation processing, and the processing speed is reduced. On the other hand, the time required for the segmented line-type approximation processing increases as the number of sections divided by the processing increases.

Therefore, in the present embodiment, at step S5 in FIG. 8, at the point in time when the predetermined number n ₁ of the scanning units have completed the segmentation line-type approximation processing, the division units of the scanning units for which the division line-type approximation processing has not been completed yet. The feature is that the approximation processing is terminated.

  FIG. 18 is a block diagram illustrating an optimal scanning selecting unit 4 ′ of the image encoding device according to the second embodiment, FIG. 19 is a flowchart illustrating an image encoding method according to the second embodiment, and FIG. It is a flowchart showing operation | movement of the operation unit of a conversion apparatus.

  The optimal scanning selecting means 4 'of this embodiment is characterized in that it comprises a processing discontinuation determining unit 101. The other configuration is the same as that described in the first embodiment, and a description thereof will not be repeated.

As shown in FIG. 19, the processing discontinuation determination unit 101 counts the number of processing end signals output from each of the scanning units 3-1 to 3-n, and determines that the number of output processing end signals is a predetermined number. Once the threshold is exceeded n ₁ (S71), and outputs the processed abort signal (S72). Further, when the processing discontinuation determining unit 101 outputs the processing termination signal, the optimal scanning determination unit 81 outputs the one-dimensional approximate image data of the minimum number of sections from among the operation units that have already output the processing end signal. Select (S73). Other operations are the same as those in the first embodiment.

  On the other hand, as shown in FIG. 20, the segmented line-type approximation means 9 of each of the scanning units 3-1 to 3-n is a case where the processing termination signal is received and the segmented line-type approximation processing is not yet completed. , The piecewise linear approximation processing is forcibly terminated (S75).

Thus, without waiting until all of the scanning units 3-1 to 3-n to end the segment linear approximation, when the divided linear approximation of arrival n ₁ single scanning unit has been completed, the encoding process By moving to, it is possible to speed up the image encoding process without lowering the encoding efficiency.

In the present embodiment, processing abort determination unit 101, when the divided linear approximation of arrival n ₁ single scanning unit has been completed, it is assumed that outputs a processed abort signal, as another method, the first It is also possible to output a processing end signal when a predetermined time has elapsed after receiving the processing end signal.

FIG. 21 is a flowchart illustrating another image encoding method according to the second embodiment. When a processing end signal is output from any one of the scanning units (S81), the processing discontinuation determination unit 101 resets the internal counter t to 0 (S82) and starts counting (S83). Then, when the count value t exceeds the predetermined threshold value _tmax (S84), a processing termination signal is output (S72). The subsequent operation is the same as that described above.

The segmented-line approximation process takes longer as the section division is performed more frequently by the recursive process. Accordingly, for a scanning unit in which the segmented-line approximation processing has not been completed even if a predetermined time _tmax or more has elapsed since the processing end signal was first output, the scanning unit that has finished the segmented-line approximation processing first outputs. It may be considered that the number of sections of the one-dimensional approximate image data does not fall below. Therefore, by forcibly terminating an unfinished piecewise linear approximation process when the count value t exceeds a predetermined threshold value _tmax , it is possible to speed up the process without lowering the encoding efficiency. Become.

In this embodiment, when any one of the scanning units 3-s completes the piecewise linear approximation processing and the number l ^(s) of sections of the generated one-dimensional approximation image data is determined, the other scanning units are determined. The number of sections l ^(s) or the number l ^(s) + Δl obtained by adding a predetermined value to the number of sections l ^(s) is defined as the number of reference sections l _st , and the number of sections l _i at each point is the number of reference sections l _The feature is that the piecewise linear approximation processing is forcibly terminated when the value becomes _st or more.

  FIG. 22 is a block diagram illustrating an optimal scanning selecting unit 4 ″ of the image encoding device according to the third embodiment, FIG. 23 is a flowchart illustrating an image encoding method according to the third embodiment, and FIG. 24 is an image encoding according to the third embodiment. It is a flowchart showing operation | movement of the operation unit of a conversion apparatus.

  This embodiment is characterized in that the optimum scanning selecting unit 4 ″ includes a reference section number notifying unit 111. Since other configurations are the same as those described in the first embodiment, the description will be omitted. Omit.

When any one of the scanning units 3-s outputs the processing end signal (S91), the optimum scanning selecting unit 4 ″ captures the number l ^(s) of sections of the scanning unit 3-s for which the segmented line approximation processing has been completed (S91). S92) Then, for each of the scanning units 3-1 to 3-n, the number of sections l ^(s) or the number l ^(s) + Δl obtained by adding a predetermined value to the number of sections l ^(s) is determined as the number of reference sections. notifying the l _st (S93). here, the set to be possible if the reference number l ^(s) + Δl obtained by adding a predetermined value to the number of segments l ^(s) is by the merging process Since the final number of sections is equal to or less than l ⁽ⁱ⁾ , it is possible to allow a margin in anticipation of that.

When the reference section number l _st is input (S101), each of the scanning units 3-i, for which the segmented line approximation processing has not been completed yet, performs the current section division processing (S26) in the segmented line approximation processing. It is determined whether or not the number of sections 1 is equal to or greater than the number of reference sections l _st (S102). If l <l _st , the section dividing process is recursively repeated as in the first embodiment (S26 to S28). On the other hand, if l ≧ l _st in step S101, a processing interruption signal is output to the optimal scanning selection means 4 ″ (S103), and the segmented linear approximation processing is forcibly interrupted.

The optimal scanning selection unit 4 ″ waits for all of the scanning units 3-1 to 3-n to output the processing end signal or the processing interruption signal (S94), and outputs the processing end signal of each scanning unit. The number of sections of the one-dimensional approximate image data is compared (S95), and a one-dimensional approximate image having the least number of sections is selected from among them (S7).
The other processes are the same as in the first embodiment.

  As described above, in each scanning unit, the processing speed can be increased without lowering the encoding efficiency by forcibly terminating the piecewise-line approximation processing when the number of reference sections is exceeded during the processing of the piecewise-line approximation. It is possible to achieve.

  FIG. 25 is an overall configuration diagram of an image encoding device according to Embodiment 4 of the present invention. In FIG. 25, an image input unit 1, an image area dividing unit 2, a scanning unit 3-1 to 3-n, an optimal scanning selecting unit 4, an encoding unit 5, an image compressed data output unit 6, a scanning unit 7, a small section division The means 8, the piecewise linear approximation means 9, and the merging processing means 10 are the same as those in FIG. 1 of the first embodiment.

  The present embodiment is characterized in that m orthogonal transform units 120-1 to 120-m are provided in parallel with the scanning units 3-1 to 3-n. Each of the orthogonal transformation operation units 120-1 to 120-m includes an orthogonal transformation unit 121, a quantization unit 122, and a run data generation unit 123.

  The orthogonal transformation unit 121 performs an orthogonal transformation on the image blocks input from the image area dividing unit 2 by a predetermined method to generate a transformed image. Various orthogonal transformations such as DCT, discrete sine transformation (DST), discrete Fourier transformation, Hadamard transformation, Karhunen-Loeve transformation (KL transformation), Haar transformation, Slant transformation, etc. can be used. It is.

  The quantization means 122 quantizes the transformed image output from the orthogonal transformation means 121 by adaptive bit allocation. This quantized transformed image is called a quantized transformed image. As a result, quantization is performed with a large number of bits for a low-frequency component where the spectrum is concentrated. Conversely, quantization is performed with a small number of bits for high-frequency components with low spectral concentration.

  The run data generator 123 scans the quantized transformed image. Scanning is performed along a zigzag path from the low frequency side to the high frequency side. This method of operation is widely used in transform coding and will not be described further here. The run data generation unit 123 performs the above-described scanning, and generates run data including a set of a run length in which pixels of the same value continue and a pixel value of the run along the scanning path. This run data is output to the optimal scanning selection means 4.

  The operation of the image coding apparatus according to the present embodiment configured as described above will be described below.

  First, the process is the same as that of the first embodiment until an image is input to the image input unit 1 and the image area dividing unit 2 outputs an image block. Further, each image block is input to the scanning units 3-1 to 3-n, and the operation of the scanning units 3-1 to 3-n to output one-dimensional approximate image data is the same as in the first embodiment.

  In the present embodiment, the image area dividing means 2 also outputs each image block to each of the orthogonal transform units 120-1 to 120-m. In the orthogonal transformation units 120-1 to 120-m, as described above, the orthogonal transformation means 121 generates a transformed image, and the quantization means produces a quantized transformed image. Then, the run data generation unit 123 generates run data and outputs the generated run data to the optimal scan selection unit 4. When the spectrum is concentrated on the low frequency side in the converted image, the run length on the high frequency side becomes longer. Therefore, the number of runs is reduced. Conversely, when the spectral concentration is low, the runs on the high frequency side are short and the number of runs is large.

  The optimum scanning selecting means 4 is configured to calculate the number of sections of the one-dimensional approximate image data output from each of the scanning units 3-1 to 3-n, and the number of runs of the run data output from each of the orthogonal transformation units 120-1 to 120-m. Compare. Then, one-dimensional approximate image data or run data having the minimum number of sections or runs is selected. Then, the encoding means 5 encodes the selected one-dimensional approximate image data or run data. The following is the same as in the first embodiment.

  As described above, in the present embodiment, in addition to the one-dimensional approximation image data generated by the scanning unit, the run data generated by the orthogonal transform unit is compared with each other, and the conversion method that minimizes the code amount is selected. . As a result, an optimal conversion method is selected according to the properties of the image, and the image can be encoded with high encoding efficiency.

FIG. 1 is an overall configuration diagram of an image encoding device according to a first embodiment of the present invention. FIG. 2 is a block diagram illustrating a configuration of each scanning unit 3-i (i = 1,..., N) in FIG. 1. FIG. 3 is a block diagram illustrating a configuration of a piecewise linear approximation unit 9 of FIG. 2. FIG. 4 is a block diagram illustrating a configuration of a section division processing unit 13 in FIG. 3. FIG. 3 is a block diagram illustrating a configuration of a merge processing unit 10 of FIG. 2. FIG. 2 is a block diagram illustrating a configuration of an optimum scanning selection unit 4 in FIG. 1. FIG. 2 is a block diagram illustrating a configuration of an encoding unit 5 in FIG. 1. 5 is a flowchart illustrating a flow of an entire process of an image encoding method according to the first embodiment. FIG. 3 is a diagram illustrating an example of a scanning order of each scanning unit. It is a flowchart showing the data processing of the scanning unit 3-k (k = 1, ..., n). FIG. 3 is a diagram illustrating an example of a scanning order in an image block. FIG. 4 is a diagram showing the contents of an image area memory 7a. FIG. 7 is a diagram showing the contents of a memory in a scanning address generator 7b. 5 is a flowchart illustrating a section dividing process performed by the section dividing unit 13 of FIGS. 3 and 4. FIG. 15 is a diagram illustrating a calculation output at each node in FIG. 14. It is a flowchart showing operation | movement of the merging process by a merging processing means. FIG. 3 is a diagram illustrating the contents of a small section approximate image memory 15. FIG. 14 is a block diagram illustrating an optimal scanning selection unit 4 ′ of the image encoding device according to the second embodiment. 11 is a flowchart illustrating an image encoding method according to a second embodiment. 13 is a flowchart illustrating the operation of the operation unit of the image encoding device according to the second embodiment. 13 is a flowchart illustrating another image encoding method according to the second embodiment. FIG. 14 is a block diagram illustrating an optimal scanning selection unit 4 ″ of the image encoding device according to the third embodiment. FIG. 23 is a flowchart illustrating an image encoding method according to the third embodiment. 13 is a flowchart illustrating the operation of the operation unit of the image encoding device according to the third embodiment. FIG. 13 is an overall configuration diagram of an image encoding device according to a fourth embodiment of the present invention.

Explanation of reference numerals

DESCRIPTION OF SYMBOLS 1 Image input means 2 Image area division means 3-1-3-n Scanning unit 4, 4 ', 4 "Optimal scan selection means 5 Encoding means 6 Image compression data output means 7 Scanning means 7a Image area memory 7b Scan address generation 8 Small section dividing means 9 Separating line type approximating means 10 Merging processing means 11 Small section memory 12 Section register 13 Section dividing processing section 14 Division processing control section 15 Small section approximating image memory 21 Address generating section 22, 25, 32 Self-multiplier 23 square addition accumulator 24 addition accumulator 26 up counter 27,29,34,36,70 divider 28,35 subtractor 30 subtraction accumulator 31 square subtraction accumulator 33 down counter 37,68,69 adder 38 Part 39 Minimum cumulative error memory 40 End of piecewise linear approximation Determining unit 41 Left error register 42 Right error register 43 Left level register 44 Left section length register 45 Right level register 46 Right section length register 51 Merging processing determining unit 52 Merging data generating unit 53 Merging section register 61 First level difference determining unit 62 second level difference determination section 63 pre-boundary section length determination section 64 post-boundary section length determination section 65 merge processing overall determination section 66, 67 multiplier 81 optimal scanning determination section 82 optimal scanning selector 91 scanning information encoding section 92 luminance Information encoding section 93 Section length information encoding section 94 Encoding information synthesis section 101 Processing discontinuation determination section 111 Reference section number notification section 120-1 to 120-m Orthogonal transformation operation unit 121 Orthogonal transformation means 122 Quantization means 123 Run / Data generation means

Claims (11)

Scanning means for scanning the original image to be encoded according to a predetermined scanning order;
The one-dimensional original image generated by scanning the original image by the scanning unit is divided into a plurality of sections so that the cumulative square error or variance of pixel values in each section is equal to or less than a predetermined threshold, and Segmented linear approximation means for generating one-dimensional approximation image data in which pixel values are approximated by an average value of pixel values in the section;
A plurality of scanning units having a plurality of corresponding to a plurality of different scanning order,
Optimal scan selection means for comparing the number of sections divided by the segmented linear approximation means of each scanning unit and selecting one-dimensional approximate image data having the minimum number of sections;
An image encoding device comprising: The dividing line-type approximating means is used to classify the one-dimensional original image,
When the one-dimensional original image is divided into two sections, a two-division process of dividing the one-dimensional original image at a division position where a sum of accumulated square errors or variances of pixel values in both sections is minimized,
If the cumulative square error or variance of the pixel values in the section is greater than or equal to a predetermined threshold for both sections divided into two by the two-partitioning process, the two-partitioning process is performed recursively in the section, 2. The image encoding apparatus according to claim 1, wherein the one-dimensional original image is divided. A small section dividing means for dividing the one-dimensional original image into a plurality of small sections;
3. The image code according to claim 1, wherein the piecewise linear approximation unit generates the one-dimensional approximate image data for a one-dimensional original image of each small section divided by the small section division unit. 4. Device. The one-dimensional approximation image data of each of the small sections generated by the piecewise linear approximation means has a difference between the average values of the pixel values of the opposing extreme end sections of two adjacent small sections that is equal to or less than a predetermined threshold value, 4. The apparatus according to claim 3, further comprising: merging processing means for, when the length of one of the sections is equal to or less than a predetermined threshold value, replacing an approximate value of both of the sections with an average value of pixel values of both of the sections. An image encoding device according to claim 1. The optimal scan selecting means is configured to execute the one-dimensional approximation image data generation processing when a predetermined number of the segmented linear approximation means of each scanning unit has completed the one-dimensional approximate image data generation processing. For the segmented line-type approximation unit that has not been completed, the process is terminated, and the number of sections divided by the segmented line-type approximation unit of the scanning unit for which the process has been completed is compared. The image encoding apparatus according to claim 1, wherein data is selected. The optimal scanning selection means,
One of the segmented linear approximation means of each of the scanning units starts counting clocks at the time when the one-dimensional approximate image data generation processing ends, and ends the one-dimensional approximate image data generation processing within a predetermined time. For the segmented linear approximation unit that has not been performed, the process is terminated, and the number of sections divided by the segmented linear approximation unit of the scanning unit that has completed the process within the predetermined time is compared. The image encoding apparatus according to claim 1, wherein the one-dimensional approximate image data is selected. The optimal scanning selection means,
When one of the segmented linear approximation means of each of the scanning units completes the one-dimensional approximation image data generation process, the number of sections of the one-dimensional approximation image data is used as a reference section number for the other scanning units. Send,
The sectioning line approximation means of each scanning unit, when receiving the reference section number, when the number of sections obtained by dividing the one-dimensional original image exceeds the number obtained by adding a predetermined value to the reference section number, the one-dimensional approximation image As well as terminating the data generation process,
The optimal scan selecting means compares the number of sections divided by the segmented linear approximation means of the scanning unit after the generation processing of the one-dimensional approximate image data is completed, and selects one-dimensional approximate image data having the minimum number of sections. The image encoding apparatus according to claim 1, wherein Orthogonal transformation means for performing orthogonal transformation on an original image to be encoded to generate a transformed image,
Quantizing means for quantizing the transformed image by adaptive bit allocation to generate a quantized transformed image,
A scan data scanning unit that scans the quantized transform image along a predetermined path, and a run data generation unit that generates run data including a set of a run length in which pixels having the same value continue along the scan path and pixel values for the run. ,
And at least one orthogonal transformation unit having
The optimal scan selection unit compares the number of sections divided by the segmented linear approximation unit of each scanning unit with the number of runs generated by the run data generation unit of the orthogonal transform unit (hereinafter, referred to as “run number”). The image encoding apparatus according to claim 1, wherein one-dimensional approximate image data or run data having the minimum number of sections or runs is selected. The one-dimensional original image generated by scanning the original image to be encoded according to a predetermined scanning order is divided into a plurality of sections such that the cumulative square error or variance of the pixel values in each section is equal to or less than a predetermined threshold. A first method in which a piecewise linear approximation process of generating one-dimensional approximation image data in which a pixel value in each section is approximated by an average value of pixel values in the section is performed in parallel with each of a plurality of different scanning orders. Steps,
A second step of comparing the number of sections of each one-dimensional approximate image data obtained by the piecewise linear approximation processing for each of the scanning orders and selecting the one-dimensional approximate image data having the smallest number of sections;
And a third step of encoding the selected one-dimensional approximate image data. In the segmented linear approximation processing, when the one-dimensional original image is divided into two sections when the one-dimensional original image is divided, the sum of accumulated square errors or variances of pixel values in both sections is minimized. A two-division process for dividing the one-dimensional original image at the division position is performed. For both sections divided by the two-division processing, when the cumulative square error or variance of pixel values in the section is equal to or more than a predetermined threshold value, 10. The image encoding method according to claim 9, wherein the one-dimensional original image is divided by recursively performing the two-division process in the section. In the first step, a transform image is generated by performing an orthogonal transform on the original image to be coded, and the transform image is quantized by adaptive bit allocation to generate a quantized transform image. While scanning along the path, the scan is performed in parallel to generate a run length consisting of a set of pixel values for the run length and the run of pixels having the same value along the scanning path,
In the second step, the number of sections of each one-dimensional approximation image data and the number of runs of the run data (hereinafter, referred to as “run number”) obtained by the piecewise linear approximation processing for each scanning order. By comparison, select the one-dimensional approximate image data with the smallest number of sections or runs,
11. The image encoding method according to claim 9, wherein in the third step, selected one-dimensional approximate image data or run data is encoded.

Images