JP4083670B2 - Image coding apparatus and image coding method - Google Patents

Description

  The present invention relates to an image coding technique used for image compression, transmission, and the like, and more particularly to an image coding technique capable of optimally coding a mixed 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 a character, figure, or illustration are mixed is called a composite image. Conventionally, various encoding methods such as JPEG, GIF, and TIFF have been widely used as techniques for irreversibly compressing mixed images.

  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. Natural images have the property that the correlation between pixels is large and the change in pixel value is continuous. On the other hand, an artificial image generally has a property that there are many sections where pixel values are continuous and the same, and there are also many sharp edges. Due to the difference in pattern properties based on the attribute of the image, it is difficult to optimally encode all the hybrid images with the conventional image encoding method.

  For example, when a hybrid image is encoded by JPEG, mosquito noise occurs in the outline of characters and figures in the artificial image portion, resulting in large visual degradation. This occurs because JPEG concentrates the spectrum in the low band by discrete cosine transformation (hereinafter referred to as “DCT”) and deletes the high band information. On the other hand, methods such as GIF and TIFF are suitable for compression of artificial images, but the encoding efficiency of natural images is lower than that of JPEG.

Therefore, as a technique for optimally encoding such a mixed image, the mixed image is separated into two regions, a discrete gradation region mainly composed of artificial images and a continuous gradation region mainly composed of natural images. Then, based on the characteristics of each region, a technique for encoding using run-length encoding and JPEG has been proposed (see Non-Patent Document 1).
Takeshi Mogi, “Compression of Natural Artificial Mixed Images Based on Region Separation”, The Institute of Electronics, Information and Communication Engineers, IEICE Transactions D-II, Vol.J82-D-II, No.7, p.1150-1160 , July 1999

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

  In addition, if parallel processing is performed in hardware, the speed can be increased. However, in this case, the circuit scale becomes extremely large.

  SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to realize a high-speed encoding process with little visual distortion for a hybrid image and to realize a small-scale circuit even in the case of a configuration for parallel processing by hardware. An object of the present invention is to provide an image encoding technique that can be realized by the above.

  A first configuration of the image encoding device of the present invention includes a scanning unit that scans an original image to be encoded according to a predetermined scanning order, and a one-dimensional original image that the scanning unit generates by scanning the original image. A one-dimensional approximate image in which the accumulated square error or variance of pixel values in a section is divided into a plurality of sections so that the pixel value is equal to or less than a predetermined threshold, and the pixel values in each section are approximated by the average value of the pixel values in the section A plurality of scanning units having a piecewise linear approximation means for generating data, corresponding to a plurality of different scanning orders, and comparing the number of sections divided by the piecewise linear approximation means of each scanning unit; And an optimum scanning selection means for selecting one-dimensional approximate image data having the smallest value.

  According to this configuration, each scanning unit divides the one-dimensional original image into a plurality of sections such that the accumulated square error or variance of pixel values in each section is equal to or less than a predetermined threshold. Then, one-dimensional approximate image data is generated by approximating the pixel values in each section by the average value of the pixel values in the section (hereinafter, this approximation is referred to as “sectioned line type approximation”). The optimum scanning selection means compares the number of sections divided by the piecewise linear approximation means of each scanning unit. Then, one-dimensional approximate image data having the smallest number of sections is selected. In this way, the optimum scan selection means estimates the scan order that minimizes the code amount after encoding as the scan order that minimizes the number of sections divided by the piecewise linear approximation means before the image is encoded. . Then, this is selected as the optimum scanning order. If the one-dimensional approximate image data obtained by the piecewise linear approximation after being scanned in the optimum scanning order is encoded by run length encoding or the like, the original image is optimally encoded.

  By selecting the operation order using the number of sections of the piecewise linear approximation as an index, an image with little change in pixel values other than edges, such as an artificial image such as a document image or graphic image, or an adjacent pixel such as a natural image A scanning order that is optimal for encoding is selected in accordance with the attributes of an image such as an image with many changes in value. Therefore, the original image is made one-dimensional by the scanning order adapted to the property of the image. In the present invention, the piecewise linear approximation is used to approximate the original image for encoding, and an optimal scanning order is selected based on the number of sections in the piecewise linear approximation before complete encoding. Thereby, high-speed encoding processing is possible.

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

  According to a second configuration of the image encoding device of the present invention, in the first configuration, when the piecewise linear approximation unit divides the one-dimensional original image into two sections. The two-division processing for dividing the one-dimensional original image at the division position where the sum of the squared error or variance of the pixel values in both sections is minimized, and for both sections divided by the two-division processing When the accumulated square error or variance of pixel values in the section is greater than or equal to a predetermined threshold, the one-dimensional original image is classified by recursively performing the two-segment processing in the section. .

  As described above, in the present invention, the piecewise linear approximation means recursively executes the above-described two-dividing process and divides the primary original image into small sections. Thereby, the edge part of an image is preserve | saved as a division position at the time of area division. Therefore, even when an image such as an artificial image in which the edge of the image is emphasized is encoded, the visual distortion of the image due to the encoding can be minimized.

  According to a third configuration of the image encoding device of the present invention, in the first or second configuration, the image encoding device includes a subsection dividing unit that divides the one-dimensional original image into a plurality of subsections, and the piecewise linear approximation unit includes: 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.

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

  According to a fourth configuration of the image encoding device of the present invention, in the third configuration, the one-dimensional approximate image data of each small section generated by the piecewise linear approximation means is opposed to two adjacent small sections. When the difference between the average values of the pixel values in the endmost section is equal to or smaller than a predetermined threshold and the length of one section is equal to or smaller than the predetermined threshold, the approximate values of both the sections are calculated as the pixels of both the entire sections. It is characterized by comprising a merging processing means for replacing with an average value.

  Thus, in the present invention, the opposite endmost sections of two adjacent small sections are merged under a certain condition by the merging means. Thereby, useless section division can be reduced and the number of sections in the entire one-dimensional approximate image data can be reduced. Therefore, the encoding 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 less 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 approximation error due to merging becomes large.

  In addition, as a condition for merging two sections, the length of one section is set to a predetermined threshold or less if it is a short section, even if edge information is lost due to merging sections, it is visually noticeable This is because there is virtually no distortion that can be ignored.

  According to a fifth configuration of the image encoding device of the present invention, in any one of the first to fourth configurations, the optimum scanning selection unit is a predetermined number of the piecewise linear approximation units of the scanning units. When the one finishes the one-dimensional approximate image data generation processing, the processing for the segmented line approximation means that has not yet completed the one-dimensional approximate image data generation processing is terminated, and the processing is completed. The number of sections divided by the piecewise linear approximation means of the scanning unit is compared, and one-dimensional approximate image data having the smallest number of sections is selected.

  The time for the piecewise linear approximation process of the piecewise linear approximation means generally increases as the number of sections to be divided increases. Therefore, there is a high possibility that the number of sections of the scanning unit in which the generation process of the one-dimensional approximate image data is completed early is the minimum. Therefore, when the piecewise linear approximation process for a predetermined number of scanning units is completed, the piecewise linear approximation process may be terminated for the remaining scanning units. In this way, by terminating the piecewise linear approximation process for the remaining scanning units, it is possible to quickly terminate the process of the optimum scanning selection means and increase the speed.

  According to a sixth configuration of the image encoding device of the present invention, in any one of the first to fourth configurations, the optimum scan selection unit is one of the piecewise linear approximation units of the respective scan units. The count of the clock is started from the time when the generation process of the dimensional approximate image data is finished, and for the piecewise linear approximation means for which the generation process of the one-dimensional approximate image data is not finished within a predetermined time, the process is terminated, Comparing the number of sections divided by the piecewise linear approximation means of the scanning unit that has completed the processing within the predetermined time, 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 approximate image data generation process is not completed within a predetermined time from the time when one of the piecewise linear approximation means of each scanning unit completes the one-dimensional approximate image data generation process is This is considered to be larger than the number of sections of the one-dimensional approximate image data in the scanning unit in which the piecewise linear approximation process is completed first. Therefore, for such a scanning unit that takes a long processing time, the piecewise linear approximation process is terminated at a predetermined time, whereby the scanning order can be optimally selected and the encoding processing time can be shortened.

  According to a seventh 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 one of the piecewise linear approximation units of the respective scan units. When the generation process of the dimension approximate image data is finished, the number of sections of the one-dimensional approximate image data is transmitted as the reference section number to the other scanning units, and the piecewise linear approximation means of each scanning unit transmits the reference section When the number is received, when the number of sections into which the one-dimensional original image is divided exceeds the number obtained by adding a predetermined value to the reference section number, the generation process of the one-dimensional approximate image data is terminated, and the optimum scan selection means Comparing the number of sections divided by the piecewise linear approximation means of the scanning unit for which the generation process of the one-dimensional approximate image data has been completed, and selecting one-dimensional approximate image data having the smallest number of sections. And butterflies.

  Thus, when the number of sections obtained by adding a predetermined number to the number of reference sections is exceeded, there is little possibility that the number of sections will be less than the number of reference sections even if merge processing is performed thereafter. Therefore, with respect to the scanning unit having such a large number of sections, when the number of sections reaches a predetermined number, the piecewise linear approximation process is terminated so that the scanning order can be optimally selected and the encoding process is performed. Time can be shortened.

  According to a seventh configuration of the image encoding device of the present invention, in any one of the first to seventh configurations, an orthogonal transform unit that performs an orthogonal transform on an original image to be encoded to generate a transformed image, and the transform A quantization means for quantizing the image by adaptive bit allocation to generate a quantized transformed image, 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 And at least one orthogonal transformation unit having run data generation means for generating run data comprising a set of pixel values for the run, and the optimum scan selection means is the piecewise linear approximation means of each scan unit. Is compared with the number of runs generated by the run data generation means of the orthogonal transform unit (hereinafter referred to as “run number”). And selects the image data or run-data.

  According to this configuration, the number of runs output by the orthogonal transform unit is smaller than the number of sections output by each scanning unit for an image having a good compression rate by orthogonal transform, such as a natural image. Accordingly, the optimum scan selection means selects the run data having the minimum number of runs. In this way, one-dimensional approximate image data or run data is selected according to the nature of the image, and more optimal encoding is achieved. As a result, the encoding efficiency is further improved.

  Note that “adaptive bit allocation” means that in a normal image, a large number of bits are assigned to a low frequency side pixel where the power of the pixel signal is concentrated and quantized so that the pixel signal power is reduced to a high frequency component. 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.

  The first configuration of the image encoding method of the present invention is that a one-dimensional original image generated by scanning an original image to be encoded in accordance with a predetermined scanning order is obtained by calculating a cumulative square error or variance of pixel values in each section. A plurality of different piecewise linear approximation processes for dividing the segment values into a plurality of sections so as to be equal to or less than a predetermined threshold and generating one-dimensional approximate image data in which pixel values in each section are approximated by an average value of the pixel values in the section. The first step performed in parallel with each of the scanning orders, the number of sections of each one-dimensional approximate image data obtained by the piecewise linear approximation processing for each scanning order is compared, and the number of sections 1 is the smallest It has the 2nd step which selects dimension approximate image data, and the 3rd step which encodes the selected one-dimensional approximate image data, It is characterized by the above-mentioned.

  According to a second configuration of the image encoding method of the present invention, in the first configuration, when the one-dimensional original image is divided into two sections when the one-dimensional original image is divided in the piecewise linear approximation process. In addition, the two-division processing for dividing the one-dimensional original image at a division position where the sum of the squared error or variance of the pixel values in both sections is minimized, and both sections divided by the two-division processing When the cumulative square error or variance of the pixel values in the section is equal to or greater than a predetermined threshold, the one-dimensional original image is classified by recursively performing the bisection process in the section. To do.

  According to a third configuration of the image encoding method of the present invention, in the first or second configuration, in the first step, orthogonal conversion is performed on the original image to be encoded to generate a converted image, and the converted image Quantized by adaptive bit allocation to generate a quantized transformed image, scan the quantized transformed image with a predetermined path, run lengths of pixels having the same value along the scanning path, and pixel values for the run In the second step, the number of sections of each one-dimensional approximate image data obtained by the piecewise linear approximation process for each scan order, and The number of runs in the run data (hereinafter referred to as “run number”) is compared to select one-dimensional approximate image data having the smallest number of sections or runs, and in the third step, the selected one is selected. The one-dimensional approximation image data or run-data, characterized in that encoding.

  As described above, according to the present invention, by selecting the operation order using the number of sections of the piecewise linear approximation as an index, a change in pixel values other than the edge is made as in an artificial image such as a document image or a graphic image. A scanning order that is optimal for encoding is selected according to the attributes of an image such as an image with a small change in adjacent pixel values such as a small image or a natural image. Therefore, the original image is made one-dimensional by the scanning order adapted to the property of the image.

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

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

  FIG. 1 is an overall configuration diagram of an image encoding apparatus according to Embodiment 1 of the present invention. In FIG. 1, an image coding apparatus according to Embodiment 1 of the present invention includes an image input means 1, an image area dividing means 2, n (n ≧ 2) scanning units 3-1 to 3-n, and an optimum scanning selection. Means 4, encoding means 5, and compressed image data output means 6 are provided.

  The image input means 1 inputs original image data to the 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 the 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 according to a predetermined scanning order determined for each, and performs a piecewise linear approximation process. One-dimensional approximate image data is generated.

  The optimum scanning selection unit 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 having the minimum number of sections. To do. The encoding unit 5 encodes the one-dimensional approximate image data selected by the optimum scanning selection unit 4 according to various encoding methods, and outputs an encoded image. The compressed image data output means 6 outputs the encoded image generated by the encoding means 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 piecewise linear approximation unit 9, and a merge processing unit 10.

  The scanning unit 7 scans each image block divided by the image region dividing unit 2 in accordance with the scanning order determined for each, 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, the pixel value in the image block is stored in each memory address according to the scanning order. The scanning address generator 7b generates scanning coordinates in the image block according to the 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 coordinate 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 piecewise linear approximation means 9 generates a small section approximate image obtained by approximating the small section data generated by the small section dividing means 8 by piecewise linear approximation. The merge processing means 10 merges the small section one-dimensional approximate image data generated by the piecewise linear approximation means 9 by a predetermined method to generate one-dimensional approximate image data. Then, the one-dimensional approximate image data is output to the optimum scanning selection unit 4.

  FIG. 3 is a block diagram showing the configuration of the piecewise linear approximation means 9 of FIG. The piecewise linear approximation unit 9 includes a small section memory 11, a section register 12, a section division processing unit 13, a division processing control unit 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 piecewise linear approximation (hereinafter referred to as “processed section data”) among pixel value data stored in the small section memory 11. The section division processing unit 13 performs section division processing on the processed section data stored in the section register 12. Here, the “section division process” is to divide the processed section data at a position where the sum of the accumulated square errors of the pixel values of both sections becomes minimum when the processed section data is divided into two sections. A process of approximating the data of each divided section with the average value of the pixel values in the section.

  The division processing control unit 14 performs section division processing recursively 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 recursively performs segment division processing so that the accumulated square error of the pixel values in each segment of the segmented small segment data is equal to or less than a predetermined threshold value, respectively, and the one-dimensional approximate 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 showing the configuration of the section division processing unit 13 of FIG. In FIG. 4, the section division processing unit 13 includes an address generation unit 21, a multiplier 22, a square addition accumulator 23, an addition accumulator 24, a multiplier 25, an up counter 26, a divider 27, a subtractor 28, and a division. 29, subtraction accumulator 30, square subtraction accumulator 31, own multiplier 32, down counter 33, divider 34, subtractor 35, divider 36, adder 37, comparison determination unit 38, minimum cumulative error memory 39, A piecewise 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 are provided. The function of each part will be described together with the description of the operation described later.

  FIG. 5 is a block diagram showing the configuration of the merge processing means 10 of FIG. In FIG. 5, the merge processing unit 10 includes a merge process determination unit 51, a merge data generation unit 52, and a merge section register 53.

  The merging process determination unit 51 determines, for each subsection data stored in the subsection approximate image memory 15, that the difference between the average values of the pixel values of the opposite endmost sections in two adjacent subsections is equal to or less than a predetermined threshold value. And whether or not the length of one section is equal to or smaller than a predetermined threshold value is determined. Further, the merged data generation unit 52 uses the approximate value of the opposite endmost sections of the two adjacent small sections for each small section data stored in the small section approximate image memory 15 as the pixel value of the entire both sections. Replace with the average value of. The merge section register 53 temporarily stores the small section data after the merge process is performed.

  The merge processing determination unit 51 includes a first level difference determination unit 61, a second level difference determination unit 62, a pre-boundary segment length determination unit 63, a post-boundary segment length determination unit 64, and a merge processing comprehensive determination unit 65. ing. The merged data generation unit 52 includes two multipliers 66 and 67, two adders 68 and 69, and a divider 70. The functions of these units will be described together with the description of operations described later.

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

  The optimum scanning determination unit 81 is the most segmented one-dimensional approximate image data segmented by the piecewise linear approximation means 9 of each scanning unit 3-i (i = 1,..., N) and merged by the merge processing means. A small number is determined, and the number of the scanning unit (hereinafter referred to as “optimum scanning number”) m is output. The optimum scanning selector 82 selects the one-dimensional approximate image data output from the scanning unit 3-m with the optimum scanning number m and outputs it to the encoding means 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 scanning information encoding unit 91 encodes the optimal scanning number m output by the optimal scanning selection unit 4 by entropy encoding using a Huffman code or the like based on the scanning frequency. The luminance information encoding unit 92 encodes the luminance information of each section of the one-dimensional approximate image data output by the optimum scanning selection unit 4 by entropy encoding using a Huffman code or the like of the difference value of the luminance level. Do. The section length information encoding unit 93 encodes the section length information of each section of the one-dimensional approximate image data output from the optimum scanning selection unit 4 by entropy encoding using a Weil code or the like.

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

When the image encoding apparatus according to the present exemplary 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 image division is completed, the image region dividing means 2 sets 1 to the parameter i representing the number of the image block to be encoded (S3).

  Next, the image area dividing unit 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 piecewise linear approximation process.

  Each of the scanning units 3-1 to 3-n transmits a process end signal to the optimum scan selection unit 4 when the piecewise linear approximation process is completed. The optimum scanning selection means 4 stands by until processing end signals are transmitted from all the scanning units 3-1 to 3-n (S5).

Here, in the piecewise linear approximation process, the one-dimensional original image data scanned and made one-dimensional by the scanning means 7 is divided into a plurality of sections by the piecewise linear approximation means 9, and the pixel values of each section are related to the relevant section. It is approximated by the average value of the pixel values. At this time, the section is divided such that the accumulated square error of the pixel value in each section is equal to or less 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 pixels in section i, l _i ^(k) is the section length of section i, and N _section ^(k) is the total number of sections). It becomes data.

  In addition, 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 optimum scanning selection unit 4 determines the number of sections of the one-dimensional approximate image data generated by each scanning unit 3-1 to 3-n. N _section ^(k) (k = 1,..., N) are compared (S6), and the one-dimensional approximate image data {(c _i ^(m) , l _i ^(m) ) with 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 approximate image data, and the better the coding efficiency.

In this way, the amount of code after encoding is calculated according to the number of sections N _section ^(k) (k = 1,..., N) of the one-dimensional approximate image data obtained by the piecewise linear approximation process before the image is encoded. By selecting one-dimensional approximate image data that is estimated to have the smallest code amount, it is possible to select a scanning order that best suits the image attributes in a short processing time. Further, as described later, since the lane marking type approximation process has a strong tendency to use the edge of the image as a division point of the section, the sharper the image edge, 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 means 5 encodes the selected one-dimensional approximate image data (including information related to 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 compressed image 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 the encoding process.

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

The above is the overall processing flow of the image encoding method according to the present embodiment. Hereinafter, the operation of each unit of the image encoding apparatus will be described in more detail.
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. FIGS. 13A and 13B show the contents of the memory in the scan address generator 7b. In FIGS. 11 to 13, the size of the image block is p × q pixels. In FIG. 9, the scanning of the square area is shown as an example of the scanning, but it is easy to combine the scanning of the square area or to change the scanning to the scanning of the rectangular area.

  When the scanning unit 3-k receives a 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 as shown in FIG. The scan address generator 7b has a memory for storing the scan order. When the scanning unit 3-k performs zigzag scanning as shown in FIG. 11, the memory in the scanning address generator 7b corresponds to the image area memory 7a in ascending order of addresses according to the zigzag scanning order as shown in FIG. The address to be stored 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 pixel data stored at an address input from the scanning address generator 7b. As a result, 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 and generates 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 operations. Each small section data is temporarily stored in the small section memory 11 inside the piecewise linear approximation means 9.

  Next, the piecewise linear approximation means 9 sets a counter i, which is an internal variable, to 1 (S23). This counter i represents the number of the small section data for which the piecewise linear approximation process is performed.

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

Here, the section division processing is a division position where the accumulated square error of the pixel values in the left and right sections is minimized when the section l is divided into two, and the section l is divided into two sections l _l and l _r. This process is divided into Details of this section division processing will be described later.

In the second row of (Equation 1), by performing section division processing on section _l , two divided sections l _l and l _r and cumulative square errors e _{l, min} and e _r of pixel values in each section _, the average c _l of pixel values in _min and each section, c _r is obtained. In (Equation 1), c _l and c _r are omitted because they are not directly related.

In the 3rd to 5th lines of (Equation 1), if the accumulated square error e _{l, min} of the pixel value in the section is greater than a predetermined threshold e _th in the divided left section l _l , the section 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 smaller than the predetermined threshold value e _th , the piecewise linear approximation process is not performed for the section l _l .

In the sixth to eighth lines of (Equation 1), similarly in the divided right section l _r , the cumulative square error _{er, min} of the pixel value in the section is larger than the 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.

Through the piecewise linear approximation process as described above, the i-th small section data is further divided into small section one-dimensional approximate image data composed of f (i) sections. The accumulated square error of the pixel values in each section is suppressed to a predetermined threshold value e _th or less. Therefore, if a sharp edge of the image is included in the section, the accumulated square error in the section cannot be suppressed to be equal to or less than the predetermined threshold value e _th, so that it is divided at the edge portion, and the sharp edge of the image is included in the section. It is divided so that it does not. That is, the edge of an image is preserve | saved as a boundary of an area by the said piecewise linear approximation process.

  The section division processing is performed by the section division processing unit 13, and the recursive processing control as described above is performed by the division processing control unit 14. Further, for a section for which an approximate value is determined by the piecewise linear approximation process, the section length and the average value of the pixel values are stored in the small section approximate image memory 15.

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

  On the other hand, if i> M in step S30, the piecewise line approximation means 9 transmits a processing end signal to the optimum scan selection means 4 (S31). Then, the merge processing is performed on the endmost section of each small section (S32), and the scanning unit 3-k ends the data processing.

  Next, supplementary explanation will be given for the section division processing. FIG. 14 is a flowchart showing section division processing by the section division processing unit 13 in FIGS. 3 and 4, and FIG. 15 is a diagram showing calculation outputs in each node in FIG. 14.

First, when the processed section data {x _i ; i = 1,..., N} having a section length of N is set in the section register 12, a 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 interval register 12 by 1 in ascending order every clock. Accordingly, the pixel value x _i is output to the node (1) which is the output of the interval register 12 with respect to the clock value i (1 ≦ i ≦ N).

The 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} ^ix _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), the addition accumulator 24 stores Σ _{k = 1} ⁱ x _k as an accumulated value.

  The up counter 26 counts the number of clocks. 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 subtraction accumulator 30 and the square subtraction accumulator 31 are set with the values of S _{r, 1} and S _{r, 2} shown in (Equation 2) and (Equation 3). Are 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 generator 21 is also reset (S42). At this time, as the initial values, 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.

Further, when the clock value increases from N + 1 by 1, the address generation unit 21 increases the address value input to the interval register 12 by 1 in ascending order every clock. Accordingly, when the clock value is N + N ₁ +1 (1 ≦ N ₁ ≦ N−1), the pixel value x _N1 is output to the node (1) that is the output of the interval register 12. Nodes (2), (3), (4), and (6) have x _N1 ² , S _{l, 2} = Σ _{k = 1} ^N1 x _k ² , S _{l, 1} = Σ _{k = 1, respectively.} ^N1 x _k and N ₁ are output. The square adder 25 outputs a value S _{l, 1} ² = (Σ _{k = 1} ^N1 x _k ) ² _obtained by squaring the output value of the node (4) to the node (5). Further, the divider 27 outputs a value S _{l, 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 subtractor 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).

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 it 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 1 from N + 1, the down counter 33 decreases the value by 1 from the set value N for each clock. Therefore, when the clock value is N + N ₁ +1 (1 ≦ N ₁ ≦ N−1), NN ₁ is output to the node (12). The divider 34 outputs a value _{Sr, 1} ² / (NN ₁ ) obtained by dividing the output value of the node (11) by the output value of the node (12) to the node (13) (S44). The subtractor 35 outputs a value (Formula 6) obtained by subtracting the value of the node (13) from the value of the node (9) to the node (14).

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). When e <e _min , the comparison / determination unit 38 updates 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 writes 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 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 average values (Equation 8) and (Equation 9) of pixel values in the left and right sections.

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

Then, at the next clock, the counter value N ₁ of the up counter 26 is increased by 1 (S48). The piecewise linear approximation end determination unit 40 determines whether or not the counter value N ₁ exceeds N−1 (S49), and repeats the operations of S43 to S48 until the counter value exceeds N−1.

As a result, the brute force search is performed for the divide point at which the sum of the accumulated square errors of both divided sections is minimized while moving the divided points from the left to the right of the processed section data. 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. The cumulative square error values e _{l, min} , e _{r, min} , average pixel values c _l , c _r , and lengths l _l , l of the left and right intervals at the division point where the sum of the accumulated square errors of _r is retained.

  Therefore, at the time 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 explanation will be given regarding the merging process of the merging processing means. FIG. 16 is a flowchart showing the operation of the merge processing by the merge processing means, and FIG. 17 is a diagram showing the contents of the small section approximate image memory 15.

  This merging process is divided into small section data by the small section dividing means 8 in order to reduce the amount of computation in the recursive process in the piecewise linear approximation process, and M small sections one-dimensionally generated by the piecewise linear approximation process. This is a process of combining the two sections under a predetermined condition based on the level difference and the section length of the sections at each connection boundary when the approximate image data are combined again. By performing this process, the coding amount can be further reduced and the coding efficiency can be improved.

  First, as a premise, the piecewise linear approximation process for the M small section data of the image block is finished, and the M small section one-dimensional approximate image data is stored in the small section approximate image memory 15 as shown in FIG. Yes. In the merging process, the last section (f (i) th section) in the i-th (i = 1,..., N-1) subsection and the first section (first section) in the i + 1th subsection. And merge process.

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

Then, the first level difference determination unit 61 of the merge processing determination unit 51 determines whether the pixel values c _{i, f (i)} and c _{i + 1,1} are the same (S62). If there is, 1 is output to the node (1), otherwise 0 is output to the node (1).

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

Further, the pre-boundary section length determination unit 63 determines whether the section length l _{i, f (i)} is equal to or less than a predetermined threshold value l _th1 , and the post-boundary section length determination unit 64 determines the section length l _{i + 1. , 1} is determined to be less than or equal to a predetermined threshold value l _th2 (S64). The pre-boundary section length determination unit 63 and the post-boundary section length determination unit 64 respectively set 1 to the node (3) when l _{i, f (i)} ≦ l _th1 and l _{i + 1,1} ≦ l _th2 . Output to (4). When l _{i, f (i)} > l _th1 and l _{i + 1,1} > l _th2 , 0 is output to nodes (3) and (4).

  The merge processing overall judgment 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 node (5) is 1, it is determined that both sections are merged. When the value of node (5) is 0, it is determined that both sections are not merged.

Here, a supplementary explanation will be given regarding the above determination method. First, when the pixel values c _{i, f (i)} and c _{i + 1,1} in both sections are equal, there is no particular problem with merging both sections. c _{i, f (i)} , c _{i + 1,1} are not equal, and the absolute value of the difference between the pixel values c _{i, f (i)} , c _{i + 1,1} in both sections | c _{i, If f (i)} −c _{i + 1,1} | is large, it may be an edge of the image, so both sections should not be merged. 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, When both section lengths are long, if the approximate error cumulative square error of both sections becomes large due to the merge, it is strongly recognized visually. Therefore, even if the absolute value | c _{i, f (i)} −c _{i + 1,1} | is small, if both section lengths are long, the sections are not merged. This is judged by threshold _values l _th1 and l _th2 .

As a result, when 1 is output as the output value of the node (5), the merge processing of both sections is performed by the merged data generation unit 52 (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 it to the node (6). The multiplier 67 calculates the product of c _{i + 1,1} and l _{i + 1,1} and outputs the product 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 (Formula 11) to the node (10).

The merged 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 obtained in this way. When 1 is output to the node (5) by the merging processing overall determination unit 65, the value of the first section (c _{i + 1,1,.} l _{i + 1,1} ) is updated with (c ′ _{i + 1,1} , l ′ _{i + 1,1} ). Also, the value (c _{i, f (i)} , l _{i, f (i)} ) of the last section of the i-th subsection data in the subsection approximate image memory 15 is updated with (0,0) and invalid. Processed.

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

  In the first embodiment, in step S5 in FIG. 8, the optimum scanning selection unit 4 waits until all the scanning units 3-1 to 3-n transmit processing end signals. If the processing of all the scanning units 3-1 to 3-n is uniformly waited, the processing time is determined by scanning in the scanning order that takes the most time for the piecewise linear approximation processing, and the processing speed becomes slow. On the other hand, the time required for the piecewise linear approximation process increases as the number of sections divided by the process increases.

Accordingly, in this embodiment, in step S5 in FIG. 8, when the divided linear approximation processing of the scanning unit a predetermined number n ₁ is completed, still divided linear scanning unit segment linear approximation processing has not been completed The approximation process is terminated.

  18 is a block diagram showing the optimum scanning selection unit 4 ′ of the image encoding device according to the second embodiment, FIG. 19 is a flowchart showing an image encoding method according to the second embodiment, and FIG. 20 is an image code according to the second embodiment. It is a flowchart showing operation | movement of the operation unit of a commutation apparatus.

  The optimum scanning selection unit 4 ′ according to the present exemplary embodiment is characterized by including a processing abort determination unit 101. Since other configurations are the same as those described in the first embodiment, description thereof is omitted.

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

  On the other hand, the piecewise linear approximation means 9 of each of the scanning units 3-1 to 3-n has a case where the piecewise linear approximation process has been completed as shown in FIG. In step S75, the piecewise linear approximation process is forcibly terminated.

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 shifting to, it is possible to increase the speed of the image encoding process without reducing 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 configure so that the processing end signal is output when a predetermined time elapses after receiving the processing end signal.

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

The piecewise linear approximation process takes longer as the section division is performed more frequently by the recursion process. Therefore, for a scanning unit in which the piecewise linear approximation process is not finished even after a predetermined time t _max has elapsed since the process end signal was first outputted, the scanning unit that first finished the piecewise linear approximation process 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 the unfinished piecewise linear approximation process when the count value t exceeds the predetermined threshold value t _max , it is possible to increase the processing speed without reducing the encoding efficiency. Become.

In this embodiment, when any one of the scanning units 3-s finishes the piecewise linear approximation process and the number of sections l ^{(s) of} the generated one-dimensional approximate image data is determined, the other scanning units are determined. The number of sections l ^(s) or the number of sections l ^(s) plus a predetermined value l ^(s) + Δl is the reference section number l _st , and the own section number l _i at each time point is the reference section number l It is characterized in that the piecewise linear approximation process is forcibly terminated when it becomes greater than or equal to _st .

  FIG. 22 is a block diagram illustrating the optimum 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, and FIG. 24 is an image code according to the third embodiment. It is a flowchart showing operation | movement of the operation unit of a commutation apparatus.

  The optimum scanning selection unit 4 ″ of the present embodiment is characterized by including a reference section number notifying unit 111. The other configuration is the same as that described in the first embodiment, and therefore the description will be omitted. Omit.

When one of the scanning units 3-s outputs a processing end signal (S91), the optimum scanning selection unit 4 ″ takes in the number of sections l ^(s) of the scanning unit 3-s for which the piecewise linear approximation processing has been completed ( S92) Then, for each of the scanning units 3-1 to 3-n, the number of sections l ^(s) or the number of sections l ^(s) plus a predetermined value l ^(s) + Δl is used as the reference section number. l _st is notified (S93) Note that the number l ^(s) + Δl obtained by adding a predetermined value to the number of sections l ^(s) may be used as a reference here. Since the final number of sections is less than or equal to l ⁽ⁱ⁾ , it is possible to provide a margin in anticipation of that.

When the reference section number l _st is input to each scanning unit 3-i that has not yet completed the piecewise linear approximation process (S101), before performing the section division process (S26) in the piecewise linear approximation process, It is determined whether the number of sections l is equal to or greater than the reference section number _lst (S102). If l <l _st , the section division process is recursively repeated as in the first embodiment (S26 to S28). On the other hand, if l ≧ l _st in step S101, a process interruption signal is output to the optimum scanning selection means 4 ″ (S103), and the piecewise linear approximation process is forcibly interrupted.

The optimum scanning selection unit 4 ″ waits for all the scanning units 3-1 to 3-n to output the processing end signal or the processing interruption signal (S94), and each scanning unit that has output the processing end signal The number of sections of the one-dimensional approximate image data is compared (S95), and the one-dimensional approximate image with the smallest number of sections is selected from among the sections (S7).
The processing other than the above is the same as in the first embodiment.

  In this way, in each scanning unit, the processing speed can be increased without degrading the coding efficiency by forcibly terminating the piecewise linear approximation process when the number of reference sections is exceeded during the piecewise linear approximation process. Can be achieved.

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

  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. The orthogonal transform operation units 120-1 to 120-m include an orthogonal transform unit 121, a quantization unit 122, and a run data generation unit 123.

  The orthogonal transform unit 121 orthogonally transforms the image block input from the image region dividing unit 2 by a predetermined method to generate a transformed image. As the orthogonal transformation, various transformations such as DCT, discrete sine transformation (DST), discrete Fourier transformation, Hadamard transformation, Karoonen-Loeve transformation (KL transformation), Haar transformation, slant transformation, etc. can be used. It is.

  The quantization unit 122 quantizes the transformed image output from the orthogonal transform unit 121 by adaptive bit allocation. This quantized transformed image is referred to as a quantized transformed image. As a result, the low-frequency component in which the spectrum is concentrated is quantized with many bits. Conversely, high-frequency components with low spectral concentration are quantized with a small number of bits.

  The run data generation unit 123 scans the quantized transformation image. The scanning is performed with a zigzag path from the low frequency side to the high frequency side. Since this operation method is widely used in transform coding, it 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 run lengths of pixels having the same value along the scan path and pixel values of the run. This run data is output to the optimum scan 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 in 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. 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 outputting the one-dimensional approximate image data is the same as in the first embodiment.

  In this embodiment, the image area dividing unit 2 outputs each image block to each orthogonal transform unit 120-1 to 120-m. In the orthogonal transform units 120-1 to 120-m, as described above, the orthogonal transform unit 121 generates a transform image, and the quantization unit generates a quantized transform image. Then, the run data generation unit 123 generates run data and outputs it to the optimum scan selection unit 4. In the converted image, when the spectrum is concentrated on the low frequency side, the run length on the high frequency side becomes long. Therefore, the number of runs is reduced. On the other hand, when the degree of concentration of the spectrum is low, the run on the high frequency side is short and the number of runs is large.

  The optimum scanning selection means 4 includes the number of sections of the one-dimensional approximate image data output from each scanning unit 3-1 to 3-n and the number of runs of run data output from each orthogonal transform unit 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 Example 1.

  As described above, in this embodiment, in addition to the one-dimensional approximate image data generated by the scanning unit, the run data generated by the orthogonal transform unit is compared, and the conversion method with the smallest code amount is selected. . Thereby, an optimal conversion method is selected according to the properties of the image, and the image can be encoded with high encoding efficiency.

1 is an overall configuration diagram of an image encoding device according to Embodiment 1 of the present invention. It is a block diagram showing the structure of each scanning unit 3-i (i = 1, ..., n) of FIG. It is a block diagram showing the structure of the piecewise linear approximation means 9 of FIG. It is a block diagram showing the structure of the area division process part 13 of FIG. It is a block diagram showing the structure of the merge process means 10 of FIG. It is a block diagram showing the structure of the optimal scanning selection means 4 of FIG. It is a block diagram showing the structure of the encoding means 5 of FIG. 3 is a flowchart illustrating the overall processing flow of the image encoding method according to the first exemplary embodiment. It is a figure showing the example of the scanning order of each scanning unit. It is a flowchart showing the data processing of the scanning unit 3-k (k = 1, ..., n). It is a figure which shows an example of the scanning order in an image block. It is a figure showing the content of the image area memory 7a. It is a figure showing the content of the memory in the scanning address generator 7b. It is a flowchart showing the division | segmentation process by the division | segmentation process part 13 of FIG. 3, FIG. It is a figure showing the calculation output in each node of FIG. It is a flowchart showing the operation | movement of the merge process by a merge process means. FIG. 4 is a diagram showing the contents of a small section approximate image memory 15. FIG. 10 is a block diagram illustrating an optimum scanning selection unit 4 ′ of the image encoding device according to the second embodiment. 10 is a flowchart illustrating an image encoding method according to the second embodiment. 10 is a flowchart illustrating an operation of an operation unit of the image encoding device according to the second embodiment. 10 is a flowchart illustrating another image encoding method according to the second embodiment. FIG. 10 is a block diagram illustrating an optimum scanning selection unit 4 ″ of an image encoding device according to Embodiment 3. FIG. 23 is a flowchart illustrating an image encoding method according to the third embodiment. 12 is a flowchart illustrating an operation of an operation unit of the image encoding device according to the third embodiment. It is a whole block diagram of the image coding apparatus which concerns on Example 4 of this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Image input means 2 Image area dividing means 3-1 to 3-n Scan unit 4, 4 ', 4 "Optimal scan selection means 5 Encoding means 6 Image compressed data output means 7 Scan means 7a Image area memory 7b Scan address generation 8 Subsection division means 9 Piecewise linear approximation means 10 Merge processing means 11 Subsection memory 12 Section register 13 Section division processing section 14 Division processing control section 15 Subsection approximation image memory 21 Address generation 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 comparison judgment Part 39 Minimum cumulative error memory 40 Completion of piecewise linear approximation Fixed section 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 Merge processing determination section 52 Merge data generation section 53 Merge section register 61 First level difference determination section 62 Second Level Difference Determination Unit 63 Pre-Boundary Section Length Determination Unit 64 Post-Boundary Section Length Determination Unit 65 Merge Processing Overall Determination Unit 66, 67 Multiplier 81 Optimal Scan Determination Unit 82 Optimal Scan Selector 91 Scan Information Encoding Unit 92 Luminance Information encoding unit 93 Section length information encoding unit 94 Encoding information combining unit 101 Processing termination determination unit 111 Reference interval number notification unit 120-1 to 120-m Orthogonal transformation operation unit 121 Orthogonal transformation unit 122 Quantization unit 123 Run / Data generation means

Claims (8)

Scanning means for scanning an 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 such that the accumulated square error or variance of pixel values in each section is equal to or less than a predetermined threshold, A piecewise linear approximation means for generating one-dimensional approximate image data in which a pixel value is approximated by an average value of pixel values in the section;
A plurality of scanning units corresponding to a plurality of different scanning orders,
Optimal scanning selection means for comparing the number of sections divided by the piecewise linear approximation means of each scanning unit and selecting one-dimensional approximate image data with the smallest number of sections ,
The optimum scan selection means starts counting the clock from one of the piecewise linear approximation means of each scanning unit when the one-dimensional approximate image data generation processing is completed, and performs one-dimensional approximation within a predetermined time. For piecewise linear approximation means for which image data generation processing has not been completed, the processing is terminated.
The optimum scanning selection means compares the number of sections divided by the piecewise linear approximation means of the scanning unit that has completed the processing within the predetermined time, and selects one-dimensional approximate image data having the smallest number of sections. it <br/> image coding apparatus according to claim. The segmented linear approximation means, when segmenting the one-dimensional original image,
When the one-dimensional original image is divided into two sections, a two-division process for dividing the one-dimensional original image at a position where the sum of the squared error or variance of pixel values in both sections is minimized, and
If the accumulated square error or variance of pixel values in the interval is equal to or greater than a predetermined threshold for both intervals divided by the 2-division processing, the 2-division processing is recursively performed in the interval, 2. The image encoding apparatus according to claim 1, wherein the one-dimensional original image is segmented. Sub-section dividing means for dividing the one-dimensional original image into a plurality of sub-sections;
3. The image code according to claim 1, wherein the piecewise linear approximation unit generates the one-dimensional approximate image data for the one-dimensional original image of each subsection divided by the subsection division unit. Device. For the one-dimensional approximate image data of each of the subsections generated by the piecewise linear approximation means, the difference between the average values of the pixel values of the opposite endmost sections in the two adjacent subsections is less than or equal to a predetermined threshold value, 4. A merge processing means for replacing an approximate value of both sections with an average value of pixel values of both sections when the length of one section is equal to or less than a predetermined threshold. The image encoding device described. Orthogonal transformation means for performing orthogonal transformation on the original image to be encoded to generate a transformed image;
Quantizing means for quantizing the transformed image by adaptive bit allocation and generating a quantized transformed image;
Run data generation means for scanning the quantized transformed image with a predetermined path and generating run data including a run length in which pixels having the same value continue along the scanning path and a pixel value for the run. ,
Comprising at least one orthogonal transform unit having:
The optimum scanning selection unit compares the number of sections divided by the piecewise linear approximation unit of each scanning unit and the number of runs generated by the run data generation unit of the orthogonal transform unit (hereinafter referred to as “run number”). Te, the image coding apparatus according to any one of claims 1 to 4, characterized in that the number of sections or the number of runs to select the smallest one-dimensional approximation image data or run-data. A one-dimensional original image generated by scanning an original image to be encoded according to a predetermined scanning order is divided into a plurality of sections so that the accumulated square error or variance of pixel values in each section is less than a predetermined threshold. First, a piecewise linear approximation process for generating one-dimensional approximate image data in which pixel values in each section are approximated by an average value of pixel values in the section is performed in parallel corresponding to a plurality of different scanning orders. Steps,
A second step of selecting the one-dimensional approximate image data with the smallest number of sections by comparing the number of sections of each one-dimensional approximate image data obtained by the piecewise linear approximation process for each scanning order;
And, we have a third step of encoding the one-dimensional approximation image data selected,
In the first step, clock counting is started from the time when the piecewise linear approximation process is completed for one scanning order, and the piecewise linear approximation process is performed until a predetermined time elapses from the start of clock counting. For the scan order that has not been completed, the process is terminated, and
In the second step, the number of sections in the scanning order in which the processing is completed within the predetermined time is compared, and the one-dimensional approximate image data in the scanning order having the smallest number of sections is selected. An image encoding method. In the piecewise linear approximation process, when the one-dimensional original image is divided, when the one-dimensional original image is divided into two sections, the sum of squared errors or variances of pixel values in both sections is minimized. When the two-division process for dividing the one-dimensional original image at the division position is performed, and the accumulated square error or variance of the pixel values in the two sections divided by the two-division process is greater than or equal to a predetermined threshold value 7. The image encoding method according to claim 6 , wherein the one-dimensional original image is segmented by recursively performing the two-dividing process in the section. In the first step, a transform image is generated by performing orthogonal transform on the original image to be encoded, the transform image is quantized by adaptive bit allocation to generate a quantized transform image, and the quantized transform image is predetermined. In parallel, a scan is performed in parallel to generate run data consisting of a set of pixel values corresponding to a run length in which pixels having the same value continue along the scan path, and
In the second step, the number of sections of each one-dimensional approximate image data obtained by the piecewise linear approximation process for each scanning order and the number of runs of the run data (hereinafter referred to as “run number”). In comparison, select one-dimensional approximate image data with the smallest number of sections or runs,
The image encoding method according to claim 6 or 7 , wherein in the third step, the selected one-dimensional approximate image data or run data is encoded.

Images