Data coding method and device, and data coding program

• US 7,254,273 B2
• Filed: 12/26/2001
• Issued: 08/07/2007
• Est. Priority Date: 12/28/2000
• Status: Expired due to Fees

• Current Assignee: Evolvable System Research Institute Incorporated, National Institute of Advanced Industrial Science and Technology (Government of Japan)
• Original Assignee: Evolvable System Research Institute Incorporated, National Institute of Advanced Industrial Science and Technology (Government of Japan)
• Inventors: Higuchi, Tetsuya, Sakanashi, Hidenori
• Primary Examiner(s): Alavi; Amir
• Application Number:
  US10/450,835
• Publication Number:
  US 20050100232A1
• Time in Patent Office: 2,050 Days
• Field of Search: 382/156, 382/159, 382/160, 382/165, 382/173, 382/190, 382/209, 382/218, 382/232, 382/233, 382/244, 382/246, 382/253, 382/238, 375/240.01, 375/240.16, 375/240.22, 375/240.23, 341 50- 52, 341/55, 341/87, 341/95
• US Class Current: 382/238
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 1/4105 for halftone screened pictures
• CPC Class Codes: H04N 1/417 using predictive or differential encoding
• CPC Class Codes: H04N 1/52 Circuits or arrangements for halftone screening

Abstract

A data compression method uses a template. In the template, the template optimizing is performed by an artificial intelligent technique (such as a genetic algorithm). The artificial intelligent techniqiue is applied to segments defined by diving input data into uniform segment units. The compression method contributes to enhancing the prediction accuracy. The data is compressed using the results of optimization, and a database is updated to improve the compression efficiency and speed of the subsequent processings. By updating a database by using an optimized template, a template for improving the prediction accuracy is obtained quickly without applying any artificial intelligent technique.

Claims

1. A predictive data coding apparatus for still images containing a template generating means comprising:

a database means that stores template information relating with positions of reference pixels together with the attribute parameters of the data;

a looking up means to look up template information in said database means using said attribute parameters as looking up keys;

a deciding means that decides whether optimization should be carried out or not according to a capability of the template that is obtained by said looking up means;

a template optimizing means that generates the optimum template by using an optimization method that uses one or both of the code compression rate and the entropy as an estimation function and

a registering means that registers the template information that is outputted from said template optimizing means to said database means wherein;

a prediction of the value of a pixel in said image information is carried out by using the status of pixels that surround said pixel,

said template with higher accuracy is generated through statistical processing and through analysis, assuming the dithering type used for generating the image to be compressed and additionally selecting reference pixels out of ideally placed pixels of the dither images by using a database in which relationship between the assumed dithering type and the template,

and said image information is coded by using the result of said prediction.

2. A predictive data coding apparatus as claimed in claim 1, wherein the optimization method used for said template optimization is either one of the enumeration method, the genetic algorithm, the evolution strategy, the hill-climbing method, the annealing method, the taboo seeking method and the greedy algorithm.

3. A predictive data coding apparatus as claimed in claim 1, wherein said looking up means contains a temporary template generating means that generates a temporary template by analyzing the inputted data and a re-looking up means that searches said database means based on said template information.

4. A predictive data coding apparatus as claimed in claim 1, wherein said data coding apparatus further contains a dividing means that divides the inputted data into a plural number of blocks according to features of the inputted data;

a compressing means that compresses the inputted data based on the template that is outputted from said template generating means and

a composing means that composes the output data of said compressing means, said template information and said block information.

5. A predictive data coding method for still images that codes data by using templates that are generated by a template generating method that contains a looking-up step to look up template information in the database which stores template information relating with positions of reference pixels together with the attribute parameters of the data, by using attribute parameters as looking-up keys;

a deciding step to decide whether template optimization should be carried out or not according to a capability of the template obtained as the result of said looking-up step,

a generating step to generate the optimum template by an optimization method using either one of or both of the code compression rate and the entropy when decision is made that optimization should be done, and

a registering step to register the template information of the optimized template into said database, wherein;

a prediction of the value of a pixel in said image information is carried out by using the status of pixels that surround said pixel,

said template with higher accuracy is generated through statistical processing and through analysis, assuming the dithering type used for generating the image to be compressed and additionally selecting reference pixels out of ideally placed pixels of the dither images by using a database in which relationship between the assumed dithering type and the template,

and said image information is coded by using the result of said prediction.

6. A predictive data coding method as claimed in claim 5, wherein said optimization method is either one of the enumeration method, the genetic algorithm, the evolution strategy, the hill-climbing method, the annealing method, the taboo seeking method and the greedy algorithm.