Compression processing apparatus and compression processing method

A dividing unit divides respective symbol sequences of input data applied with zigzag scan and a run-length process into a plurality of subsets having similar frequencies of occurrence, depending on a difference in frequencies of occurrence. A table creating unit scans each subset and creates a Huffman coding table for each subset. A coding unit executes a process for performing Huffman coding on each subset by using the Huffman coding table created for the subset, for all of the subsets in the plurality of subsets.

CROSS-REFERENCE TO RELATED APPLICATIONS

The present application is a U.S. national stage application claiming the benefit of International Application No. PCT/JP2008/002065, filed on Jul. 31, 2008, the entire contents of which is incorporated herein by reference in its entirety.

TECHNICAL FIELD

The present invention relates to a compression processing apparatus and a compression processing method which compress data.

BACKGROUND ART

Conventionally, Huffman coding is known as one of the most efficient reversible compression techniques in data compression techniques (D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE, no. 40, pp. 1098-1101, September 1952).

General Huffman coding first creates a coding table suitable for target data by carefully examining all coding target symbol sequences before performing a compression process, and performs the compression process by using the created coding table again for similar symbol sequences.

However, since this method needs to scan the data twice for performing the compression, online real time compression becomes difficult. Moreover, if there are many types of the coding target symbol sequences and there is a bias in frequencies of occurrence thereof, improvement of a compression ratio may not be expected.

The static Huffman coding is the most common form of implementation in both software and hardware. In addition, in order to execute a coding process in real time, the static Huffman coding previously examines frequencies of occurrence of data from a large number of pieces of sample data, prepares an existing table created based on a result thereof, and performs the coding.

The dynamic Huffman coding has been developed in order to improve the online compression which has been a challenge in the conventional Huffman coding, and compression suitable for arbitrary symbol sequences without an existing table, which has been a challenge in the static Huffman coding. The dynamic Huffman coding updates a Huffman tree each time a symbol is processed, and performs the coding by using the tree composed at that time point.

DISCLOSURE OF THE INVENTION

In the conventional dynamic Huffman coding, however, there are several problems in compression efficiency and a real time property. Specifically, the dynamic Huffman coding needs to transmit first-occurring symbols which are not coded, along with coded data, due to the nature of its algorithm, which increases a data amount thereof.

Moreover, in the dynamic Huffman coding, since the Huffman tree does not grow sufficiently for a certain period from the beginning of the compression, the compression ratio is often low. The same also applies to a case where a data occurrence distribution is changed during the compression.

Furthermore, due to data locality, if a short code has been assigned to a symbol which has occurred in a concentrated manner and the symbol does not occur subsequently, the compression efficiency may be even lower than the static Huffman coding as the data amount becomes large.

To solve this, the coding table may be periodically refreshed; however, discarding a data occurrence probability in the past also adversely leads to degraded compression efficiency. Moreover, since the Huffman tree is updated at the time of each coding, the process requires a longer time. Consequently, even though online processing is possible, the dynamic Huffman coding may not be suitable for applications requiring the real time property.

It is, therefore, desired to provide a compression processing apparatus which can improve the compression efficiency.

Moreover, it is desired to provide a compression processing method which can improve the compression efficiency.

The compression processing apparatus is a compression processing apparatus compressing input data and outputting compressed data, and is provided with a dividing unit and a coding unit. The dividing unit divides a plurality of elements included in a population having the input data into a plurality of subsets by using a feature of each element. The coding unit performs Huffman coding on coding target data for each subset by using a plurality of Huffman coding tables provided corresponding to the plurality of subsets, and outputs the compressed data.

The compression processing apparatus may be further provided with a table creating unit. The table creating unit creates the plurality of Huffman coding tables by executing, for all of the plurality of subsets, a process for examining a frequency of occurrence of the coding target data included in one subset and creating the Huffman coding table corresponding to the one subset.

The coding unit may perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables.

The compression processing apparatus may be further provided with a table retaining unit and an updating unit. The table retaining unit retains first and second coding tables each consisting of a plurality of Huffman codes. The updating unit updates one coding table which is not used for the Huffman coding on the input data, in the first and second coding tables, depending on a frequency of occurrence of the coding target data so that the coding target data with a highest frequency of occurrence is converted into a shortest Huffman code. In addition, when a compression ratio of the compressed data is equal to or less than a threshold, the coding unit may perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables, based on the other coding table in the first and second coding tables, and when the compression ratio becomes larger than the threshold, the coding unit may perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables, based on the one coding table updated by the updating unit.

The updating unit may update the one coding table by counting the frequency of occurrence for all of the coding target data, executing a process for, each time the frequency of occurrence for one of the coding target data reaches a maximum value, assigning a new Huffman code having a shorter length to the one of the coding target data for which the frequency of occurrence has reached the maximum value earlier in order thereof, for all of the coding target data.

The updating unit may calculate the compression ratio based on the compressed data outputted from the coding unit, and, when the calculated compression ratio has become larger than the threshold, or when the new Huffman code has been assigned to all of the coding target data, the updating unit may generate an exchanging signal for exchanging the coding table and output the exchanging signal to the coding unit. The coding unit may exchange the coding table in response to the exchanging signal, and perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables, based on the exchanged coding table.

The compression processing apparatus may be further provided with an image segmenting unit. The image segmenting unit segments an image into a plurality of images based on target objects included in the image and generates a plurality of input data. In addition, the dividing unit executes a process for dividing a plurality of elements included in a population having one of input data in the plurality of input data, into a plurality of subsets by using a feature of each element, for all of the plurality of input data. The coding unit may execute a process for performing the Huffman coding on coding target data for each subset by using a plurality of Huffman coding tables provided corresponding to the plurality of subsets divided from the one of input data, and outputting the compressed data, for all of the plurality of input data.

Moreover, the compression processing method is a compression processing method compressing input data and outputting compressed data, and is provided with a first step of a dividing unit dividing a plurality of elements included in a population having the input data into a plurality of subsets by using a feature of each element; and a second step of a coding unit performing Huffman coding on coding target data for each subset by using a plurality of Huffman coding tables provided corresponding to the plurality of subsets, and outputting the compressed data.

The compression processing method may be further provided with a third step of a table creating unit creating the plurality of Huffman coding tables by executing, for all of the plurality of subsets, a process for examining a frequency of occurrence of the coding target data included in one subset and creating the Huffman coding table corresponding to the one subset.

In the second step, the coding unit may perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables.

The compression processing method is further provided with a third step of an updating unit updating one coding table which is not used for the Huffman coding on the input data, in first and second coding tables each having a plurality of Huffman codes, depending on a frequency of occurrence of the coding target data so that the coding target data with a highest frequency of occurrence is converted into a shortest Huffman code, and in the second step, when a compression ratio of the compressed data is equal to or less than a threshold, the coding unit may perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables, based on the other coding table in the first and second coding tables, and when the compression ratio becomes larger than the threshold, the coding unit may perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables, based on the one coding table.

The third step may include a first substep of the updating unit counting the frequency of occurrence for all of the coding target data; and a second substep of the updating unit updating the one coding table by executing a process for, each time the frequency of occurrence for one of the coding target data reaches a maximum value, assigning a new Huffman code having a shorter length to the one of the coding target data for which the frequency of occurrence has reached the maximum value earlier in order thereof, for all of the coding target data.

The third step further includes a third substep of the updating unit calculating the compression ratio based on the compressed data outputted from the coding unit; and a fourth substep of, when the compression ratio calculated in the third substep has become larger than the threshold, or when the new Huffman code has been assigned to all of the coding target data, the updating unit generating an exchanging signal for exchanging the coding table and outputting the exchanging signal to the coding unit, and in the second step, the coding unit may exchange the coding table in response to the exchanging signal, and perform the Huffman coding on the coding target data for each subset while creating the plurality of Huffman coding tables, based on the exchanged coding table.

The compression processing method is further provided with a third step of an image segmenting unit segmenting an image into a plurality of images based on target objects included in the image and generating a plurality of input data, and in the first step, the dividing unit may execute a process for dividing a plurality of elements included in a population having one of input data in the plurality of input data, into a plurality of subsets by using a feature of each element, for all of the plurality of input data, and in the second step, the coding unit may execute a process for performing the Huffman coding on coding target data for each subset by using a plurality of Huffman coding tables provided corresponding to the plurality of subsets divided from the one of input data, and outputting the compressed data, for all of the plurality of input data.

The compression processing apparatus or the compression processing method divides the input data into the plurality of subsets depending on a difference in frequencies of occurrence of respective symbol sequences, creates the Huffman coding table for each subset in the divided plurality of subsets, and performs the Huffman coding for each subset by using the created Huffman coding table.

As a result, a shorter Huffman code is assigned to the coding target data included in each subset, than a case of using the conventional Huffman coding.

Therefore, the compression ratio can be improved.

BEST MODE FOR CARRYING OUT THE INVENTION

Embodiments of the present invention will be described in detail with reference to the drawings. It should be noted that the same or equivalent portions in the drawings are assigned with the same reference characters and descriptions thereof are not repeated.

FIG. 1is a schematic block diagram showing a configuration of a compression processing apparatus according to Embodiment 1 of the present invention. With reference toFIG. 1, a compression processing apparatus10according to Embodiment 1 of the present invention comprises a processing unit1, a dividing unit2, a table creating unit3and a coding unit4.

The processing unit1performs segmentation into a plurality of pixels, RGB to YCbCr conversion/sampling, level shift, discrete cosine transform, quantization, and a zigzag scan/run-length process, on an original image, in a compression method using conventional Huffman codes. In addition, the processing unit1outputs data applied with the zigzag scan and the run-length process to the dividing unit2as input data.

The dividing unit2divides the input data received from the processing unit1into a plurality of subsets depending on a feature (frequency of occurrence) of each element included in the input data, and outputs the divided plurality of subsets to the table creating unit3and the coding unit4.

The table creating unit3receives the plurality of subsets from the dividing unit2. In addition, the table creating unit3examines the frequency of occurrence of coding target data included in one subset, and based on the examined frequency of occurrence, creates a Huffman coding table for one subset by using a conventional Huffman tree construction method. The table creating unit3executes this process for all the subsets in the plurality of subsets, and creates a plurality of the Huffman coding tables for the plurality of subsets. Then, the table creating unit3outputs the created plurality of Huffman coding tables to the coding unit4.

The coding unit4receives the plurality of subsets from the dividing unit2, and receives the plurality of Huffman coding tables from the table creating unit3. In addition, the coding unit4performs Huffman coding on the coding target data included in the plurality of subsets by using the plurality of Huffman coding tables, and outputs compressed data. In this case, the coding unit4performs the Huffman coding on the coding target data included in one subset by using the Huffman coding table created corresponding to one subset. In addition, the coding unit4executes this process for all the subsets in the plurality of subsets, and performs the Huffman coding on all of the coding target data included in the plurality of subsets.

FIG. 2is a conceptual diagram showing conventional Huffman coding. Moreover,FIG. 3is a conceptual diagram showing the Huffman coding in the compression processing apparatus10shown inFIG. 1. With reference to FIG.2, a population U consisting of the input data consists of a plurality of elements represented by white circles, white squares and white triangles, and all of the plurality of elements belong to a subset A.

Therefore, in the conventional Huffman coding, since one Huffman coding table is created for the subset A, if the number of the elements is large and there are many types thereof, it requires time to create the Huffman coding table, and it also becomes difficult to improve compression efficiency.

On the other hand, as shown inFIG. 3, in the Huffman coding according to the present invention, the plurality of elements belonging to the population U are divided into their respective features and divided into several subsets B, C and D. In addition, the Huffman coding table is created for each of the subsets B, C and D, and the created Huffman coding table is used to perform the Huffman coding for each of the subsets B, C and D.

In this way, in the Huffman coding according to the present invention, since the Huffman coding is performed for each subset, a compression ratio can be improved. Moreover, since the Huffman coding table is created for each subset and a compression process is performed for each subset, even if the number of the elements is large, coded data can be immediately obtained.

FIG. 4is a conceptual diagram of image compression in the compression processing apparatus10shown inFIG. 1. With reference toFIG. 4, if an image is compressed, the processing unit1in the compression processing apparatus10segments an original image into a plurality of elements, and performs the RGB to YCbCr conversion and the sampling on each of the segmented plurality of elements.

Then, the processing unit1in the compression processing apparatus10performs the level shift of a result of the sampling, and then performs the discrete cosine transform (DCT).

Subsequently, the processing unit1in the compression processing apparatus10performs the quantization, zigzag-scans the quantized data from top left toward bottom right in the original image, and also performs the run-length process.

Then, the dividing unit2in the compression processing apparatus10divides the input data (which means “the data applied with the zigzag scan and the run-length process”, and the same applies to the followings) into the plurality of subsets, and the table creating unit3creates the Huffman coding table for each of the plurality of subsets divided by the dividing unit2, and the coding unit4performs the Huffman coding for each subset by using the plurality of Huffman coding tables created by the table creating unit3, and outputs the compressed image.

Therefore, a block of “DIVIDE INPUT DATA INTO SUBSETS” and a block of “HUFFMAN CODING FOR EACH SUBSET” are points different from a conventional image compression method.

Here, a method of dividing the input data into the plurality of subsets in the dividing unit2of the compression processing apparatus10will be described. For example, if the input data consists of a symbol sequence of “ATAACCCCGG”, the dividing unit2divides the symbol sequence of “ATAACCCCGG” into a symbol sequence of “ATAA” and a symbol sequence of “CCCCGG”, depending on a difference in frequencies of occurrence of respective symbols.

In the data after the zigzag scan and the run-length process have been performed, portions in which similar symbol sequences such as the symbol sequence of “ATAA” and the symbol sequence of “CCCCGG” have been arranged are arranged in a distributed manner. Therefore, with reference to the symbol sequences after the zigzag scan and the run-length process have been performed, the dividing unit2gathers the similar symbol sequences together and divides the input data into the plurality of subsets.

In this way, the dividing unit2divides the data applied with the zigzag scan and the run-length process into the plurality of subsets, depending on a difference in the frequencies of occurrence of respective symbol sequences.

FIG. 5is a diagram for explaining a specific example of the division into the subsets. With reference toFIG. 5, the original image is a landscape picture consisting of a sky portion, a mountain portion and a ground portion. In such the original image, the frequencies of occurrence of the respective symbol sequences are different in the sky portion, the mountain portion and the ground portion. Therefore, depending on the difference in the frequencies of occurrence of the respective symbol sequences, the dividing unit2divides data of the original image into a subset A consisting of the sky portion, a subset B consisting of the mountain portion, and a subset C consisting of the ground portion.

In addition, the table creating unit3scans the subset A consisting of the sky portion to create a Huffman coding table A for the subset A, scans the subset B consisting of the mountain portion to create a Huffman coding table B for the subset B, and scans the subset C consisting of the ground portion to create a Huffman coding table C for the subset C.

Then, the coding unit4performs the Huffman coding on the coding target data included in the subset A consisting of the sky portion by using the Huffman coding table A, performs the Huffman coding on the coding target data included in the subset B consisting of the mountain portion by using the Huffman coding table B, and performs the Huffman coding on the coding target data included in the subset C consisting of the ground portion by using the Huffman coding table C.

In the conventional Huffman coding, regardless of a difference in the data such as the sky portion, the mountain portion and the ground portion, the Huffman coding has been performed by using a previously defined Huffman coding table. Alternatively, in the conventional Huffman coding, the Huffman coding has been performed by using the Huffman coding table created after the entire image has been scanned.

However, according to these methods, a bit length of a Huffman code to be assigned becomes gradually longer as types of the data included in a figure are increased, and a size of the compressed data tends to be increased.

In contrast to this, in a method according to the present invention, since the Huffman coding is performed by using each of the Huffman coding tables A, B and C optimized for each of the sky, the mountain and the ground, optimal Huffman codes with a short bit length can be assigned for each subset of the image. Therefore, the compression ratio can be improved.

FIG. 6is a diagram for explaining another specific example of the division into the subsets. With reference toFIG. 6, the original image is a snapshot of people consisting of a background portion and a people portion. In such the original image, the frequencies of occurrence of the respective symbol sequences are different in the background portion and the people portion. Therefore, depending on the difference in the frequencies of occurrence of the respective symbol sequences, the dividing unit2divides the data of the original image into a subset D consisting of the background portion, and a subset E consisting of the people portion.

In addition, the table creating unit3scans the subset D consisting of the background portion to create a Huffman coding table D for the subset D, and scans the subset E consisting of the people portion to create a Huffman coding table E for the subset E.

Then, the coding unit4performs the Huffman coding on the coding target data included in the subset D consisting of the background portion by using the Huffman coding table D, and performs the Huffman coding on the coding target data included in the subset E consisting of the people portion by using the Huffman coding table E.

Also in this case, in the method according to the present invention, the compression ratio can be improved more than the conventional Huffman coding due to the same reason as the above described reason.

FIG. 7is a flowchart for explaining a compression processing method in Embodiment 1. With reference toFIG. 7, when a series of operations are started, the processing unit1in the compression processing apparatus10executes the RGB to YCbCr conversion, the sampling, the level shift, the discrete cosine transform, the quantization and the zigzag scan/run-length process on the original image, and generates a coding target data group (=the input data) (step S1).

In addition, the dividing unit2extracts the similar symbol sequences from the coding target data group received from the processing unit1, and generates the subset (step S2).

Then, the table creating unit3scans within the subset generated by the dividing unit2, and creates the Huffman coding table (step S3).

Subsequently, the coding unit4receives the subset from the dividing unit2, and receives the Huffman coding table from the table creating unit3. In addition, the coding unit4performs the Huffman coding on the coding target data within the subset by using the Huffman coding table (step S4).

Then, it is determined whether or not the Huffman coding has been terminated for all the subsets (step S5), and if the Huffman coding has not been terminated for all the subsets, the series of operations return to step S2, and the above described steps S2to S5are repeatedly executed.

In addition, in step S5, if it is determined that the Huffman coding has been terminated for all the subsets, the series of operations are terminated.

As described above, according to Embodiment 1, the compression processing apparatus10divides the input data into the plurality of subsets depending on the difference in the frequencies of occurrence of the respective symbol sequences, creates the Huffman coding table for each subset in the divided plurality of subsets, and performs the Huffman coding for each subset by using the created Huffman coding table.

As a result, a shorter Huffman code is assigned to the coding target data included in each subset, than a case of using the conventional Huffman coding. Therefore, the compression ratio can be improved.

FIG. 8is a schematic block diagram of the compression processing apparatus according to Embodiment 2. With reference toFIG. 8, in a compression processing apparatus10A according to Embodiment 2, the dividing unit2, the table creating unit3and the coding unit4in the compression processing apparatus10shown inFIG. 1have been replaced with an encoder11and an optimizer12, and others are the same as the compression processing apparatus10.

The encoder11retains two coding tables each consisting of the Huffman codes. In addition, when not receiving an exchanging signal EXC for exchanging the coding table from the optimizer12, the encoder11performs the Huffman coding on the input data received from the processing unit1by using one coding table in the two coding tables, and outputs the compressed data. Moreover, when receiving the exchanging signal EXC from the optimizer12, the encoder11exchanges from one coding table to the other coding table in the two coding tables, performs the Huffman coding on the input data, and outputs the compressed data.

In parallel with the Huffman coding in the encoder11, the optimizer12updates the coding table which is not used for the Huffman coding of the input data by the encoder11, and also generates and outputs the exchanging signal EXC to the encoder11.

FIG. 9is a configuration diagram of the encoder11and the optimizer12shown inFIG. 8. With reference toFIG. 9, the encoder11includes a CAM (Content Addressable Memory)111, a selector112, and coding tables113and114. The optimizer12includes an assigning module121and a switching module122.

The CAM111stores a plurality of memory symbols, and a plurality of addresses associated with the plurality of memory symbols, respectively. The plurality of memory symbols consist of symbols which can be inputted to the CAM111. When receiving each input symbol constituting the input data from the processing unit1, the CAM111searches the stored plurality of memory symbols, detects the memory symbol matching the input symbol, and also detects the address associated with the detected memory symbol. In addition, the CAM111outputs the detected address as a matching address MAdd to the selector112and the assigning module121in the optimizer12.

When not receiving exchanging signals EXC1and EXC2(a kind of the exchanging signal EXC) from the assigning module121and the switching module122in the optimizer12, respectively, the selector112outputs the matching address MAdd received from the CAM111to the active table113, and when receiving the exchanging signals EXC1and EXC2from the assigning module121and the switching module122, respectively, the selector112outputs the matching address MAdd received from the CAM111to the shadow table114.

Each of the active tables113and114consists of a plurality of addresses and a plurality of code words. The plurality of code words are associated with the plurality of addresses, respectively. In addition, each of the plurality of code words consists of the Huffman code.

When receiving the matching address MAdd from the selector112, the coding table113serves as the active table. In addition, the coding table113reads the code word associated with the received matching address MAdd, and outputs the read code word as the compressed data.

Moreover, when not receiving the matching address MAdd from the selector112, the coding table113serves as the shadow table.

The coding table114consists of the same configuration as the coding table113, and serves the same function as the coding table113.

It should be noted that each of the coding tables113and114consists of an SRAM (Static Random Access Memory).

When receiving the matching address MAdd from the CAM111, the assigning module121counts the number of times of receiving the matching address MAdd from the CAM111, and when the counted count value reaches a maximum value Count_MAX, the assigning module121generates a new address instead of the matching address MAdd and a new code word by a method to be described below, and updates the coding table114(=the shadow table) with the new address and the new code word which have been generated. Moreover, the assigning module121outputs the new code word to the switching module122. Furthermore, when the count values for all the matching addresses MAdd received from the CAM111have reached the maximum values Count_MAX, the assigning module121generates and outputs the exchanging signal EXC1to the selector112.

The switching module122receives the new code word from the assigning module121, and receives the code word (referred to as “old code word”, and the same applies to the followings) outputted as the compressed data from the coding table113(or the coding table114) serving as the active table.

In addition, the switching module122calculates the compression ratio based on the new code word and the old code word, and when the calculated compression ratio becomes larger than a threshold, the switching module122generates and outputs the exchanging signal EXC2to the selector112and the assigning module121.

FIG. 10is a configuration diagram of the assigning module121shown inFIG. 9. With reference toFIG. 10, the assigning module121includes a decoder1200, counters1201to120n(n is an integer equal to or larger than 2), an address encoder1211, an address counter1212, an address register1213, a multiplexer (MUX)1214, an address pointer1215, a base table1216and a controller1217.

The decoder1200decodes the matching address MAdd received from the CAM111in the encoder11, and outputs the decoded matching address MAdd to the counter (any of the counters1201to120n) provided corresponding to the matching address MAdd.

The counters1201to120nare provided corresponding to n addresses stored in the CAM111. For each of the counters1201to120n, the maximum value Count_MAX has been previously set. This maximum value Count_MAX is decided depending on the type of the data which is a Huffman coding target.

When receiving the matching address MAdd from the decoder1200, each of the counters1201to120ncounts the number of times of receiving the matching address MAdd, and when the count value reaches the maximum value Count_MAX, each of the counters1201to120ngenerates an overflow signal OFL, and outputs the generated overflow signal OFL to the address encoder1211, the address counter1212and the controller1217.

Moreover, when receiving a reset signal RSET from the controller1217, each of the counters1201to120nresets the count value.

The address encoder1211retains addresses with which the counters1201to120nare associated, respectively. In addition, when receiving the overflow signal OFL from any of the counters1201to120n, the address encoder1211encodes the address with which the counter (any of the counters1201to120n) which has outputted the overflow signal OFL is associated, and outputs the encoded address as an address Add_old to be updated in the shadow table114, to the address register1213and the multiplexer1214.

The address counter1212receives the overflow signal OFL from any of the counters1201to120n, and receives a maximum address Add_old_MAX among the addresses Add_old to be updated, from the address register1213. In addition, when receiving the overflow signal OFL, the address counter1212sequentially generates updated addresses Add_new in a range equal to or less than the maximum address Add_old_MAX, and outputs the generated updated addresses Add_new to the address pointer1215.

This updated address Add_new indicates an address to be designated in the base table1216, and as described below, the base table1216assigns the address in ascending order of bit length of the code word, and stores the plurality of code words.

Therefore, the address counter1212generates the updated addresses Add_new in the range equal to or less than the maximum address Add_old MAX, in order from a small address.

Moreover, when receiving the exchanging signal EXC2from the switching module122, the address counter1212generates addresses Add0to Addn in order from “0”, and outputs the generated addresses Add0to Addn to the multiplexer1214and the address pointer1215.

The address register1213retains only the maximum address Add_old_MAX among the addresses Add_old received from the address encoder1211, and also outputs the retained maximum address Add_old_MAX to the address counter1212.

When receiving the addresses Add_old from the address encoder1211, the multiplexer1214outputs the received addresses Add_old to the shadow table114.

Moreover, when receiving the addresses Add0to Addn from the address counter1212, the multiplexer1214outputs the received addresses Add0to Addn to the coding table114(=the shadow table).

When receiving the updated addresses Add_new from the address counter1212, the address pointer1215designates addresses matching the received updated addresses Add_new, in the base table1216.

Moreover, the address pointer1215receives the addresses Add0to Addn from the address counter1212, and receives the n addresses with which the counters1201to120nwhich have outputted the overflow signal OFL are associated, from the controller1217. In addition, the address pointer1215designates addresses not matching the addresses from the controller1217, among the addresses Add0to Addn received from the address counter1212, in the base table1216.

The base table1216stores the plurality of addresses and the plurality of code words. In addition, the plurality of code words are associated with the plurality of addresses, respectively. In this case, the base table1216stores the plurality of code words in ascending order of bit length of the code word. Therefore, the code word with a shortest bit length is associated with a minimum address, and the code word with a longest bit length is associated with a maximum address.

When the address is designated by the address pointer1215, the base table1216outputs the code word associated with the designated address, as a new code word C_new, to the coding table114(=the shadow table) and the switching module122.

When receiving the overflow signal OFL from all of the counters1201to120n, the controller1217generates the exchanging signal EXC1, outputs the generated exchanging signal EXC1to the selector112in the encoder11, and also sequentially outputs the n addresses with which the counters1201to120nwhich have outputted the overflow signal OFL are associated, to the address pointer1215.

Moreover, when outputting the exchanging signal EXC1, or when receiving the exchanging signal EXC2from the switching module122, the controller1217generates and outputs the reset signal RSET to the counters1201to120n.

FIG. 11is a configuration diagram of the switching module122shown inFIG. 9. With reference toFIG. 11, the switching module122includes a subtractor1221, an adder1222, a comparator1223, an accumulation register1224and a signal generator1225.

The subtractor1221receives the code word C_new from the assigning module121, and receives a code word C_old from the coding table113(or the coding table114) serving as the active table. In addition, the subtractor1221subtracts the code word C_new from the code word C_old, and outputs a result of the subtraction to the adder1222.

The adder1222receives the subtraction result from the subtractor1221, and receives an accumulated value from the accumulation register1224. In addition, the adder1222adds the subtraction result to the accumulated value, and outputs a result of the addition to the accumulation register1224.

The comparator1223receives the code word C_new from the assigning module121, and receives the code word C_old from the coding table113(or the coding table114) serving as the active table. In addition, the comparator1223compares the bit length of the code word C_new with the bit length of the code word C_old, and when the bit length of the code word C_new is shorter than the bit length of the code word C_old, the comparator1223generates an enable signal EN for activating the accumulation register1224, and outputs the generated enable signal EN to the accumulation register1224. It should be noted that when the bit length of the code word C_new is equal to or longer than the bit length of the code word C_old, the comparator1223does not output the enable signal EN to the accumulation register1224.

When receiving the enable signal EN from the comparator1223, the accumulation register1224retains the addition result received from the adder1222, as the accumulated value, and also outputs the retained accumulated value to the adder1222and the signal generator1225.

For the signal generator1225, a threshold of the compression ratio has been previously set. In addition, the signal generator1225compares the accumulated value received from the accumulation register1224with the threshold, and when the accumulated value becomes larger than the threshold, the signal generator1225generates the exchanging signal EXC2, and outputs the generated exchanging signal EXC2to the selector112in the encoder11and the controller1217in the assigning module121.

The accumulation register1224is activated by the enable signal EN only when the bit length of the code word C_new is shorter than the bit length of the code word C_old, and outputs the accumulated value to the signal generator1225. In addition, when the accumulated value is larger than the threshold of the compression ratio, the signal generator1225generates the exchanging signal EXC2. Moreover, since the accumulated value is a value in which the subtraction result of the subtraction of the code word C_new from the code word C_old has been accumulated, the accumulated value indicates an accumulated value in which the bit length of the compressed data has been shortened. In the present invention, this accumulated value is referred to as “compression ratio”.

Therefore, the signal generator1225compares the compression ratio with the threshold, and when the compression ratio is larger than the threshold, the signal generator1225generates the exchanging signal EXC2.

FIG. 12is another configuration diagram of the switching module122shown inFIG. 9. Moreover, as shown inFIG. 12, if a calculating unit1226such as an ALU (Arithmetic Logic Unit) has been used instead of the subtractor1221, without using the comparator1223, the value of the accumulation register can be finely adjusted by exercising ingenuity in calculation of C_old and C_new. For example, if the bit length of C_new is longer than C_old, the subtraction result becomes negative. However, the value is also accumulated, and thereby it also becomes possible to keep an efficient code word. Moreover, better effects may be obtained by using not only the subtraction but also the addition or multiplication.

FIG. 13is a diagram for explaining operations in the Huffman coding by using one coding table113. Moreover,FIG. 14is a diagram for explaining operations in the Huffman coding by using the other coding table114. It should be noted that the selector112is omitted inFIGS. 13 and 14.

With reference toFIG. 13, when not receiving the exchanging signal EXC1or EXC2, the selector112selects the coding table113. Therefore, the coding table113serves as the active table, and the coding table114serves as the shadow table.

The coding table113consists of addresses [0000] to [1111] and code words [00002] to [fffef]. In addition, each of the code words [00002] to [fffef] is the Huffman code, and a plurality of the code words [00002] to [fffef] are associated with a plurality of the addresses [0000] to [1111], respectively.

When receiving [01100101] as the input symbol from the processing unit1, the CAM111searches a plurality of memory symbols [10000001], [10000010], . . . , [11111010] which have been stored, detects the memory symbol=[01100101] matching the input symbol=[01100101], and outputs the address=[0011] associated with the detected memory symbol=[01100101], as the matching address MAdd via the selector112to the coding table113serving as the active table.

When receiving the matching address MAdd=[0011], the coding table113detects the code word=[00043] associated with the address=[0011] matching the received matching address MAdd=[0011], and outputs the detected code word=[00043] as the compressed data.

With reference toFIG. 14, when receiving the exchanging signal EXC1or EXC2, the selector112exchanges the coding table to be used from the coding table113to the coding table114. Therefore, the coding table114serves as the active table, and the coding table113serves as the shadow table.

The coding table114consists of the addresses [0000] to [1111] and code words [00023] to [fffef]. In addition, each of the code words [00023] to [fffef] is the Huffman code, and a plurality of the code words [00023] to [fffef] are associated with the plurality of the addresses [0000] to [1111], respectively.

When receiving [01100101] as the input symbol from the processing unit1, the CAM111outputs the matching address MAdd=[0011] via the selector112to the coding table114, by the same operations as the above described operations.

When receiving the matching address MAdd=[0011], the coding table114detects the code word=[00002] associated with the address=[0011] matching the received matching address MAdd=[0011], and outputs the detected code word=[00002] as the compressed data.

In this way, the encoder11uses the coding table113or the coding table114to convert the input symbol=[01100101] into the code word=[00043] or [00002].

Also if an input symbol other than the input symbol=[01100101] has been inputted, the encoder11converts the input symbol into the code word by the above described operations.

Therefore, the Huffman coding can be readily performed on the input symbol by configuring the encoder11with the CAM111and the two coding tables113and114.

FIG. 15is a diagram for explaining the update of the coding table114serving as the shadow table. It should be noted that, inFIG. 15, a number in parentheses in the code word represents the bit length of the code word.

When all of the counters1201to120nhave outputted the overflow signal OFL, or when the compression ratio has become larger than the threshold, roles of the active table and the shadow table are exchanged between the two coding tables113and114.

In addition, in the coding tables113and114and the base table1216, the same addresses and the same code words have been originally set as default settings.

For example, if the counter1203associated with the address=[0010] outputs the overflow signal OFL by the above described method, the address encoder1211encodes the address with which the counter1203is associated, and outputs the address=[0010] to the address register1213and the multiplexer1214.

In addition, when receiving the address=[0010] from the address encoder1211, the address register1213compares the already retained address with the address=[0010], and if the already retained address is larger than the address=[0010], the address register1213maintains the retention of the already retained address, and if the already retained address is smaller than the address=[0010], the address register1213retains the address=[0010] instead of the already retained address. Then, the address register1213outputs the address=[0010] as the maximum address Add_old MAX to the address counter1212.

The address counter1212receives the overflow signal OFL from the counter1203, and receives the maximum address Add_old_MAX from the address register1213. In addition, the address counter1212generates the updated addresses Add_new in the range equal to or less than the maximum address Add_old_MAX, in ascending order of address value, and outputs the generated updated addresses Add_new to the address pointer1215.

The multiplexer1214outputs the addresses Add_old received from the address encoder1211, to the coding table114serving as the shadow table.

On the other hand, the address pointer1215designates the address matching the updated address Add_new in the base table1216, and the base table1216outputs the code word=[00002] associated with the address designated by the address pointer1215, as the code word C_new, to the coding table114(=the shadow table) and the switching module122.

Then, the coding table114(=the shadow table) receives the address Add_old=[00002] from the multiplexer1214in the assigning module121, and receives the code word C_new=[00002] from the base table1216. In addition, the coding table114(=the shadow table) overwrites the code word=[001e5(5)] associated with the address=[0010], with the code word C_new=[00002(2)]. A coding table114-1(=the shadow table) is thereby updated to a coding table114-2(=the shadow table), and the code word associated with the address=[0010] is shortened by three bits (seeFIG. 15).

Then, similarly, the code word=[fff4f(16)] associated with the address=[1110] is overwritten with the code word=[00023(3)], and the coding table114-2(=the shadow table) is updated to a coding table114-3(=the shadow table). The code word associated with the address=[1110] is thereby shortened by 13 bits.

Subsequently, similarly, the coding table114-3(=the shadow table) is updated to a coding table114-4(=the shadow table). This overwriting of the code word in the coding table114(=the shadow table) is repeated until the last counter (any of the counters1201to120n) outputs the overflow signal OFL, or until the compression ratio becomes larger than the threshold.

After the address counter1212has received the overflow signal OFL from the last counter (any of the counters1201to120n) and has outputted the updated addresses Add_new to the address pointer1215, or when the address counter1212has received the exchanging signal EXC2from the switching module122, the address counter1212sequentially generates the addresses starting from “0”, and outputs the generated addresses to the multiplexer1214and the address pointer1215.

Moreover, the controller1217sequentially outputs the n addresses with which the counters1201to120nwhich have outputted the overflow signal OFL are associated, to the address pointer1215.

Then, the address pointer1215designates the addresses not matching the addresses from the controller1217, among the addresses received from the address counter1212, in the base table1216. In addition, the base table1216reads and outputs the code words associated with the designated addresses to the coding table114(=the shadow table).

On the other hand, the multiplexer1214outputs the addresses outputted from the address counter1212, to the coding table114(=the shadow table).

Then, the coding table114(=the shadow table) receives the addresses from the multiplexer1214and the code words from the base table1216, and based on the received addresses and code words, overwrites the code words which have not been overwritten with the code words in the process of the overwriting, with the code words received from the base table1216.

As a result, as shown inFIG. 15, in the overwrite, the code words associated with the addresses=[0000], [0001], . . . , [0011] are overwritten with the code words=[00fe8], [00fa9], [03f9a], respectively. The coding table114-4(=the shadow table) is thereby updated in a sequential manner to coding tables114-5,114-6and114-7(=the shadow tables), and redundant code words are eliminated. This process is performed until a value of the maximum address Add_old_MAX.

In the above described update of the coding table114(=the shadow table), the assigning module121outputs shorter code words in order of the reception of the overflow signal OFL, to the coding table114(=the shadow table), and updates the coding table114(=the shadow table). Therefore, the assigning module121assigns the code word with the shorter length to one of the coding target data for which the count value of the frequency of occurrence has reached the maximum value earlier in order thereof.

Moreover, the above described update of the coding table114(=the shadow table) is performed in parallel with the operations of converting the input symbol into the Huffman code in the encoder11by the above described method by using the coding table113(=the active table).

It should be noted that, when the coding table113serves as the shadow table, the coding table113is also updated by the above described method.

FIG. 16is a flowchart for explaining operations in the encoder11and the optimizer12shown inFIG. 9.

With reference toFIG. 16, when a series of operations are started, the CAM111in the encoder11receives the input symbol (step S11), and compares the received input symbol with the memory symbol (step S12).

In addition, if the CAM111in the encoder11detects the address associated with the memory symbol matching the input symbol, the CAM111in the encoder11outputs the detected address as the matching address MAdd to the selector112and the assigning module121. In addition, the selector112in the encoder11outputs the matching address MAdd to the coding table113(=the active table) and the assigning module121(step S13).

Subsequently, the coding table113(=the active table) in the encoder11outputs the code word associated with the address matching the matching address MAdd (step S14).

Then, it is determined whether or not all of the input symbols have been converted into the Huffman codes (step S15), and if all of the input symbols have not been converted into the Huffman codes, the series of operations return to step S11, and the above described steps S11to S15are repeatedly executed in the encoder11.

On the other hand, in step S15, when it has been determined that all of the input symbols have been converted into the Huffman codes, the series of operations are terminated.

After step S13, in the optimizer12, the counter (any of the counters1201to120n) associated with the matching address MAdd increments a counter value by “1” (step S16), and the counter (any of the counter1201to120n) determines whether or not the counter value is the maximum value (step S17).

In step S17, when it has been determined that the counter value is not the maximum value, the switching module122determines whether or not the compression ratio is equal to or less than the threshold, by the above described method (step S18).

In step S18, when it has been determined that the compression ratio is equal to or less than the threshold, the series of operations return to step S16, and the above described steps S16to S18are repeatedly executed.

On the other hand, in step S18, when it has been determined that the compression ratio is larger than the threshold, the series of operations proceed to step S22.

On the other hand, in step S17, when it has been determined that the counter value is the maximum value, new Huffman codes are assigned to the coding table114(=the shadow table) by the above described method (step S19), and the coding table114(=the shadow table) is updated with the new Huffman codes (step S20).

Then, it is determined whether or not all of the counter values are the maximum values (step S21), and when all of the counter values are the maximum values, the series of operations proceed to step S22.

On the other hand, in step S21, when it has been determined that at least one of all of the counter values is not the maximum value, the series of operations proceed to step S16.

When it has been determined in step S18that the compression ratio is larger than the threshold, or when it has been determined in step S21that all of the counter values are the maximum values, the coding table is exchanged (step S22). In addition, the series of operations proceed to step S13.

It should be noted that the above described steps S11to S15are executed by the encoder11, and the above described steps S16to S22are executed by the optimizer12. Therefore, the operations in the optimizer12are performed in parallel with the operations in the encoder11.

FIG. 17is a diagram for specifically explaining the Huffman coding in the compression processing apparatus10A shown inFIG. 8.

With reference toFIG. 17, the encoder11receives the input data after the zigzag scan and the run-length process have been performed in the processing unit1.

In addition, the encoder11performs the Huffman coding on each symbol constituting the input data by using the coding table113(=the active table) by the above described method. Here, in a case of performing the Huffman coding on a background portion in a person's image shown inFIG. 17, the encoder11performs the Huffman coding on coding target data in the background portion by using the coding table113(=the active table) as long as the compression ratio is equal to or less than the threshold. Therefore, the encoder11performs the Huffman coding on the coding target data in the background portion while creating a Huffman coding table suitable for the Huffman coding on the background portion, by using some code words stored in the coding table113(=the active table).

Then, when receiving coding target data in a face portion in the person's image, the encoder11performs the Huffman coding on the coding target data in the face portion by using the coding table113(=the active table) as long as the compression ratio is equal to or less than the threshold, and if the compression ratio becomes larger than the threshold, the encoder11exchanges to the coding table114(=the shadow table) and performs the Huffman coding on the coding target data in the face portion. Therefore, when the encoder11performs the Huffman coding on the coding target data in the face portion, the encoder11performs the Huffman coding on the coding target data in the face portion while creating a Huffman coding table suitable for the Huffman coding on the face portion, by using some code words stored in the coding table113(=the active table) or some code words stored in the coding table114(=the shadow table).

The same also applies to a case where the encoder11performs the Huffman coding on coding target data in a body portion in the person's image.

As a result, the encoder11and the optimizer12perform the Huffman coding on the input data inputted from the processing unit1, and thereby segment the person's image into subsets of the background portion, the face portion and the body portion, and also perform the Huffman coding on the subsets of the background portion, the face portion and the body portion, respectively, while creating the Huffman coding tables suitable for the subsets of the background portion, the face portion and the body portion, respectively.

In this case, the encoder11constitutes the dividing unit2and the coding unit4shown inFIG. 1, and the encoder11and the optimizer12constitute the table creating unit3shown inFIG. 1.

Therefore, the compression processing apparatus10A (seeFIG. 8) according to Embodiment 2 consists of the same configuration as the compression processing apparatus10(seeFIG. 1) according to Embodiment 1.

FIG. 18is a flowchart for explaining the compression processing method in Embodiment 2.

With reference toFIG. 18, when a series of operations are started, the processing unit1in the compression processing apparatus10A executes the RGB to YCbCr conversion, the sampling, the level shift, the discrete cosine transform, the quantization and the zigzag scan/run-length process on the original image, and generates the coding target data group (=the input data) (step S31).

In addition, the processing unit1outputs the coding target data to the encoder11(step S32), and the encoder11detects the address associated with the memory symbol matching the coding target data (=the input symbol) received from the processing unit1, and outputs the detected address as the matching address MAdd to the optimizer12.

In addition, the optimizer12counts the number of times of receiving the matching address MAdd, and thereby counts the frequency of occurrence for each coding target data (step S33).

Then, the optimizer12determines whether or not there is the coding target data for which the frequency of occurrence reaches the maximum value (=the maximum value Count_MAX), by determining whether or not any of the counters1201to120nhas outputted the overflow signal OFL (step S34). In this case, when any of the counters1201to120nhas outputted the overflow signal OFL, the optimizer12determines that there is the coding target data for which the frequency of occurrence reaches the maximum value (=the maximum value Count_MAX), and when any of the counters1201to120ndoes not output the overflow signal OFL, the optimizer12determines that there is no coding target data for which the frequency of occurrence reaches the maximum value (=the maximum value Count_MAX).

In step S34, when it has been determined that there is the coding target data for which the frequency of occurrence reaches the maximum value (=the maximum value Count_MAX), the optimizer12updates the coding table114(=the shadow table) by the above described method, and assigns a short Huffman code to a corresponding code (step S35).

After step S35or in step S34, when it has been determined that there is no coding target data for which the frequency of occurrence reaches the maximum value (=the maximum value Count_MAX), the optimizer12determines whether or not the number of times of new assignment of the Huffman code has exceeded a threshold, by determining whether or not all of the counters1201to120nhave outputted the overflow signal OFL (step S36).

In this case, when all of the counters1201to120nhave outputted the overflow signal OFL, the optimizer12determines that the number of times of the new assignment of the Huffman code has exceeded the threshold, and when at least one of the counters1201to120ndoes not output the overflow signal OFL, the optimizer12determines that the number of times of the new assignment of the Huffman code has not exceeded the threshold.

In step S36, when it has been determined that the number of times of the new assignment of the Huffman code has exceeded the threshold, the encoder11exchanges the active table from the coding table113to the coding table114, and performs the Huffman coding on the coding target data while creating a new Huffman coding table in the exchanged coding table114(step S37).

On the other hand, in step S36, when it has been determined that the number of times of the new assignment of the Huffman code has not exceeded the threshold, the encoder11performs the Huffman coding on the coding target data by using the Huffman coding table which has already been created by using the coding table113(step S38).

After step S37or step S38, it is determined whether or not the coding of all of the coding target data has been terminated (step S39). In step S39, when it has been determined that the coding of at least one of the coding target data has not been terminated, the series of operations return to step S32, and the above described steps S32to S39are repeatedly executed until it is determined in step S39that the coding of all of the coding target data has been terminated.

In step S39, if it is determined that the coding of all of the coding target data has been terminated, the series of operations are terminated.

As described above, in Embodiment 2, the compression processing apparatus10A performs the Huffman coding on the coding target data while dividing the input data into the subsets and creating the Huffman coding tables suitable for the divided subsets.

Therefore, the Huffman coding can be performed on the coding target data at high speed, and also the compression ratio can be improved.

Others are the same as Embodiment 1.

It should be noted that, in Embodiment 2, the coding tables113and114constitute “table retaining unit”, and the optimizer12constitutes “updating unit”.

FIG. 19is a schematic block diagram of the compression processing apparatus according to Embodiment 3. With reference toFIG. 19, a compression processing apparatus10B according to Embodiment 3 is equal to a compression processing apparatus that an image segmenting unit5is added to the compression processing apparatus10shown inFIG. 1, and others are the same as the compression processing apparatus10.

The image segmenting unit5segments original image data into a plurality of image data based on target objects in the original image, and outputs the segmented plurality of image data to the processing unit1.

In the compression processing apparatus10B, the processing unit1processes the plurality of image data inputted from the image segmenting unit5, for each of the image data by the above described method, and outputs a plurality of input data corresponding to the plurality of image data, to the dividing unit2.

Moreover, in the compression processing apparatus10B, the dividing unit2executes a process for dividing into a plurality of subsets for each of the input data, for all of the input data in the plurality of input data, and the table creating unit3executes a process for creating a plurality of Huffman coding tables suitable for the plurality of subsets divided for each of the input data, for all of the input data in the plurality of input data, and the coding unit4executes a process for performing the Huffman coding on coding target data included in the plurality of subsets for each of the input data, for each subset, by using the plurality of Huffman coding tables suitable for the plurality of subsets, for all of the input data in the plurality of input data.

An image segmentation method in the image segmenting unit5shown inFIG. 19will be described. The image segmenting unit5segments an image into a plurality of images, for example, by using a region growing type segmentation algorithm.

This region growing type segmentation algorithm is a method of segmenting the image, for example, by repeating a process for deciding a leader cell from 3×3 pixels and for performing region growing from a region of the decided leader cell to regions of peripheral pixels having relatively large connection weights, until no leader cell exists.

FIG. 20is a diagram for explaining an image segmentation method. The image segmenting unit5segments one frame into images of the respective target objects by a region growing type image segmentation method.

This region growing type image segmentation method handles behavior of an oscillator for each pixel in an oscillator network of the LEGION model (D. L. Wang, and D. Terman, “Image segmentation based on oscillator correlation,” Neural Computation, Volume 9(4), pp. 805-836 (1997)), in four states of Self-Excitation, Self-Excitable, Excitation and Inhibition. In addition, this region growing type image segmentation method consists of four steps of initialization, self-excitation, excitation and inhibition.

The image segmenting unit5receives an input image consisting of a 3×3 configuration shown in (a) ofFIG. 20. The image segmenting unit5calculates eight inter-pixel connection weights CW1to CW8among nine pixels constituting the input image, and retains the calculated eight connection weights CW1to CW8corresponding to each inter-pixel in a memory (embedded in the image segmenting unit5). It should be noted that, in (b) ofFIG. 20, eight connection weights between a pixel of (2,2) and peripheral pixels are shown.

Then, the image segmenting unit5reads the eight connection weights CW1to CW8retained in the memory, and calculates a sum SUM(CW) of the read eight connection weights CW1to CW8. The image segmenting unit5determines whether or not the calculated sum SUM(CW) is larger than a threshold φPfor deciding the leader cell. It should be noted that, in the present application, SUM means calculation of a sum represented by sigma notation in mathematics.

When the image segmenting unit5has determined that the sum SUM(CW) is larger than the threshold φP, the image segmenting unit5sets a pixel at a center of the connection weight calculation as the leader cell, and sets a leader cell flag pij=1. On the other hand, when the image segmenting unit5has determined that the sum SUM(CW) is equal to or less than the threshold φP, the image segmenting unit5does not set the pixel at the center of the connection weight calculation as the leader cell, and sets the leader cell flag pij=0.

The image segmenting unit5executes this process by setting each of the nine pixels of the input image as the pixel at the center of the connection weight calculation, and decides the leader cells (see (c) ofFIG. 20).

Then, the image segmenting unit5causes one of the leader cells to perform the self-excitation (excitation flag xij=1) (see (d) ofFIG. 20). If cells (k,l)εNijcorresponding to eight pixels adjacent to each cell (i,j) have performed the excitation, the image segmenting unit5calculates a sum SUMεNijΛxkl=1Wij;klof the connection weights between the cell (i,j) and the cells (k,l), and if the calculated sum SUM(k,l)εNijΛxkl=1Wij;klis larger than a threshold φZand the cell (i,j) has not yet belonged to any segmented region (label flag lij=0), the image segmenting unit5automatically causes the excitation (xij=1) (excitation of dependent, the region growing) (see (e) ofFIG. 20). According to this excitation-of-dependent process, the region is widened, and as shown in (f) ofFIG. 20, when there is no cell which newly performs the excitation, segmentation of one region is terminated.

Then, in order to save this segmented region, as shown in (g) ofFIG. 20, the image segmenting unit5writes a label number for identifying the segmented region, to the cell which has performed the excitation, sets the label flag (lij=1) indicating that the cell which has performed the excitation is a cell which has already been segmented, and performs an inhibition process (xij=0, pij=0).

When the inhibition process is terminated, the image segmenting unit5returns to a self-excitation process again for the segmentation of the next region. The image segmenting unit5repeatedly executes the above described process until no leader cell exists, and segments each region. After all of the leader cells have performed the excitation, the image segmenting unit5performs labeling to all of the regions, and terminates the image segmentation of one frame (see (h) ofFIG. 20).

FIG. 21is a flowchart for explaining the image segmentation method using the region growing type segmentation algorithm.

With reference toFIG. 21, when a series of operations are started, the image segmenting unit5calculates respective inter-pixel connection weights among a plurality of pixels constituting one frame, and also decides the leader cells by the above described method (step S41).

The image segmenting unit5determines whether or not a self-excitable cell has been detected (step S42), and when the image segmenting unit5has determined that the self-excitable cell has been detected, the image segmenting unit5performs the self-excitation by the above described method (step S43).

Then, the image segmenting unit5determines whether or not the cell in the excitation exists (step S44), and when the cell in the excitation exists, the image segmenting unit5performs the excitation of dependent in periphery (the region growing) by the above described method (step S45). The series of operations return to step S44, and steps S44and S45are repeatedly executed until no cell in the excitation exists in step S44.

In step S44, when it is determined that no cell in the excitation exists, the image segmenting unit5performs termination of the excitation of dependent, and decision of the region, by the above described method, and also performs the labeling (the inhibition) (step S46). Then, the series of operations return to step S42, and steps S42to S46are repeatedly executed until it is determined in step S42that no self-excitable cell is detected.

In step S42, if it is determined that no self-excitable cell is detected, the series of operations are terminated.

It should be noted that the image segmenting unit5repeatedly executes the flowchart shown inFIG. 21, and segments each frame into the images of the respective target objects.

FIG. 22is a flowchart for explaining the compression processing method in Embodiment 3. In the flowchart shown inFIG. 22, steps S51to S53have been added to steps S2to S5of the flowchart shown inFIG. 7, and others are the same as the flowchart shown inFIG. 7.

With reference toFIG. 22, when a series of operations are started, the image segmenting unit5in the compression processing apparatus10B segments the original image into the plurality of images according to the flowchart shown inFIG. 21(step S51).

The processing unit1executes the RGB to YCbCr conversion, the sampling, the level shift, the discrete cosine transform, the quantization and the zigzag scan/run-length process on one image in the plurality of images, and generates the coding target data group (=the input data) (step S52).

Then, the above described steps S2to S5are sequentially executed. In step S5, if it is determined that the coding has been terminated for all of the subsets, it is determined whether or not the coding has been terminated for all of the images (step S53).

In step S53, when it has been determined that the coding has not been terminated for all of the images, the series of operations return to step S52, and the above described steps S52, S2to S5, and S53are repeatedly executed until it is determined in step S53that the coding has been terminated for all of the images.

In step S53, if it is determined that the coding has been terminated for all of the images, the series of operations are terminated.

FIG. 23is a schematic block diagram showing another configuration of the compression processing apparatus according to Embodiment 3. The compression processing apparatus according to Embodiment 3 may be a compression processing apparatus10C shown inFIG. 23.

With reference toFIG. 23, the compression processing apparatus10C is equal to a compression processing apparatus that the image unit5is added to the compression processing apparatus10A shown inFIG. 8, and others are the same as the compression processing apparatus10A.

The image segmenting unit5has been described above. Therefore, the compression processing apparatus10C segments the original image into the plurality of images with a focus on the target objects, and for each of the segmented plurality of images, executes the division into the plurality of subsets, and a process for performing the Huffman coding on all of the coding target data included in the plurality of subsets while creating the plurality of Huffman coding tables suitable for the plurality of subsets, and compresses the original image data.

FIG. 24is a flowchart for explaining another compression processing method in Embodiment 3. In the flowchart shown inFIG. 24, steps S51to S53have been added to steps S32to S39of the flowchart shown inFIG. 18, and others are the same as the flowchart shown inFIG. 18.

With reference toFIG. 24, when a series of operations are started, the above described steps S51and S52are sequentially executed, and then the above described steps S32to S39are sequentially executed. In step S39, if it is determined that the coding of all of the coding target data has been terminated, the above described step S53is executed, and in step S53, if it is determined that the coding has been terminated for all of the images, the series of operations are terminated.

As described above, Embodiment 3 is characterized in that the original image is segmented into the plurality of images with a focus on the target objects, and for each of the segmented plurality of images, the original image data is compressed by using the compression processing method according to Embodiment 1 or the compression processing method according to Embodiment 2.

Since the segmentation of the original image is performed so that each target object is extracted, each segmented image consists of similar image data. Therefore, the data compression can be flexibly performed by applying the Huffman coding according to Embodiments 1 and 2 to these respective images.

For example, the landscape picture shown inFIG. 5is segmented into three images of an image consisting of the sky, an image consisting of the mountain, and an image consisting of the ground. As a result, since each image in the three images consists of symbol sequences having similar frequencies of occurrence, the Huffman coding table which flexibly addresses each image can be created. Therefore, the data compression can be flexibly performed.

It should be noted that, in the above description, it has been described that the image segmentation is performed by using the region growing type image segmentation method, which, however, is not limited thereto in the present invention, and the image segmentation may be performed by using methods described in (1) to (4) as follows.(1) B. Jaehne, “Digital Image Processing 5th revised and extended edition,” Springer-Verlag, pp. 427-440, 2001.(2) J. C. Russ, “The Image Processing Handbook,” CRC PRESS, pp. 371-429, 1999.36(3) T. Braeunl, S. Feyrer, W. Rapf, and M. Reinhardt, “Parallel Image Processing,” Springer-Verlag, 2000.(4) W. Y. Ma, and B. S. Manjunath, “Edgeflow: a technique for boundary detection and segmentation,” IEEE Transactions on Image Processing, vol. 9 (8), pp. 1375-1388, 2004.

Others are the same as Embodiments 1 and 2.

In the above described Embodiments 1 to 3, the case of compressing the image data has been described, which, however, is not limited thereto in the present invention, and the compression processing apparatus and the compression processing method according to the present invention may compress text data and audio data by the above described methods.

The embodiments disclosed this time should be considered as an exemplification in all regards, and not as limitative. It is intended that the scope of the present invention is shown by the claims, not by the descriptions of the above described embodiments, and all changes within the meaning and scope equivalent to the claims are included therein.

INDUSTRIAL APPLICABILITY

The present invention is applied to a compression processing apparatus which can improve compression efficiency. Moreover, the present invention is applied to a compression processing method which can improve the compression efficiency.