CN100556138C

CN100556138C - System and method for accelerating arithmetic coding processing speed

Info

Publication number: CN100556138C
Application number: CN 200510109142
Authority: CN
Inventors: 毛清龙; 陈丕崇
Original assignee: Primax Electronics Ltd
Current assignee: Primax Electronics Ltd
Priority date: 2005-10-18
Filing date: 2005-10-18
Publication date: 2009-10-28
Anticipated expiration: 2025-10-18
Also published as: CN1953548A

Abstract

The invention discloses a system and a method for accelerating arithmetic coding processing speed, which are applied to the computing mode of judging the size A (interval size) of an output interval and a base value C (base) by adding a group of computing circuits and a group of computing acceleration tables when input data are two continuous equal pixel values and background values, so that the A and C values which originally can be obtained only by two time pulse computing time can be computed within one time pulse computing time, and the aim of accelerating the arithmetic coding processing speed is further achieved.

Description

Accelerate the system and the method thereof of arithmetic coding processing speed

Technical field

The present invention relates to a kind of system and method thereof of accelerating the arithmetic coding processing speed, particularly relate to and a kind ofly be applied in binary picture joint specialist group (Joint Bi-level Image Experts Group JBIG) is used to compress the system and the method thereof of binary picture data.

Background technology

In the general society of information flow now, the demand of image is increasing, the digitlization of the image trend that is inevitable.Yet but the shared data volume of the image after digitlization is quite huge, and it is too much to take memory, makes data all suitable time-consuming in transmission, in processings, seems very inconvenient in transmission with handling, and is best solution with data compression.

Image Data Compression The Application of Technology prospect is very wide, we can say that all digital type image products all relate to the Image Data Compression technology, and the digitlization of electronic product has been trend of the times.For example, digit type TV set in high definition replaces simulated television, and visual telephone replaces the traditional voice phone, and digital camera replaces film camera or the like.

And the invention of facsimile art and the widely-used develop rapidly that has promoted the binary picture compression algorithm.CCITT (CCITT, the ITU subordinate's of International Telecommunications Union a mechanism) uses at fax class and has set up a series of images compression standard, is exclusively used in compression and transmits binary picture.These standards roughly comprise the CCITT Group 1 and the CCITT Group 3 in 2,1980 years of Group in the later stage seventies 20th century, and CCITT Group 4 in 1984.1993, the common binary picture joint specialist group of setting up of CCITT and ISO (International Standards Organization) was further development of distortionless artwork master shelves compress mode with the compression of binary picture, makes it become more general JBIG standard.

About nineteen sixty-eight, P.Elias has developed the coding method of Shannon and Fano greatly, constructs from the more perfect Shannon-Fano-Elias coding of mathematics viewpoint of measures.Along the idea of this coding method, 1976, J.Rissanen proposed a kind of coding method-arithmetic coding (Arithmetic coding) that can successfully approach comentropy (information entropy) limit.Nineteen eighty-two, Rissanen and G.G.Langdon have improved arithmetic coding together.Afterwards, people combine arithmetic coding again with the partial match estimation model (PPM) that J.G.Cleary and I.H.Witten proposed in 1984.

And arithmetic coding is to play the part of an epochmaking role in JBIG encoding compression mode, and the output of arithmetic coding is a real number between 0 and 1, utilizes this real number, and the decoding end can be deciphered back original information uniquely.And before will encoding, the appearance probability of each symbol must be obtained earlier in the information.

For undistorted compression, the partial match estimation model combines with arithmetic coding, can farthest approach the limit of comentropy.Unfortunately, though arithmetic coding can obtain the shortest code length, the complexity of itself, and have more floating-point operation, and be unfavorable for the hardware realization, also make arithmetic coding all very slow when operation.Even in today that central processing unit (CPU) speed is maked rapid progress, the speed of service of arithmetic coding program also is difficult to satisfy the demand of daily use.

Summary of the invention

The object of the present invention is to provide a kind of system and method thereof of accelerating the arithmetic coding processing speed, when the input data are pixel value such as continuous two-phase and background value, by method provided by the present invention, pulse calculates two adjacent same pixel and is worth pairing real number value in operation time between a period of time, make and originally must be reduced to the computing that only need carry out a packed data and can obtain identical operation result through the step of twice compressed encoding calculating.

To achieve these goals, the invention discloses the system of a kind of quickening arithmetic coding (Arithmetic coding) processing speed, must comprise at least:

Input module is used to read in two adjacent pixels data and background value thereof (CX, context value) and judges whether identical; Memory, be used to store a probability estimated statement and a counting accelerometer, wherein the probability estimated statement is for storing priori probability (prior probability) value LSZ (the interval size that the less symbol of probability occurs, LPS ' s interval Size, wherein LPS is the abbreviation of Less Probable Symbol), counting accelerometer then is store to calculate whole interval big or small A, and base value C is required (the interval big or small 2LSZ2 of the less symbol of probability appears in the interval big or small 1LSZ1+ that the less symbol of probability occurs) that use and the probable value of (the interval big or small 2LSZ2 of the less symbol of probability appears in the interval big or small 1LSZ1-that the less symbol of probability occurs); Selector is used for the background value according to identical neighbor, utilizes the inner one group of computing circuit (comprising: adder, subtracter and comparator) that increases, and judges according to the probability estimated statement and to determine an arithmetic path; And output module, be used for calculating whole interval big or small A, base value C by inquiry probability estimated statement and counting accelerometer according to this arithmetic path.

To achieve these goals, the invention discloses a kind of method of accelerating the arithmetic coding processing speed, comprise the following step:

At first, once read in two pixel value data and background value thereof, then, do you judge that two pixel values are identical? if it is inequality, then carry out compressed encoding and calculate in known arithmetic coding mode, if identical, then again by the background value of selector according to identical neighbor, utilize inner adder, subtracter and the comparator that increases, judge according to the probability estimated statement to determine an arithmetic path; At last, calculate whole interval big or small A, base value C according to this arithmetic path by inquiry probability estimated statement and counting accelerometer.

Following conjunction with figs. and specific embodiment elaborate to feature of the present invention, but not as a limitation of the invention.

Description of drawings

Fig. 1 is a system architecture diagram of the present invention;

Fig. 2 a is the method flow diagram of two pixel data arithmetic codings of known process;

Fig. 2 b once reads the method flow diagram that two pixel datas carry out arithmetic coding for the present invention;

Fig. 3 a, 3b are relatively schematic diagram of the enforcement of an arithmetic coding embodiment on known and the inventive method;

Fig. 4 a, 4b, 4c and 4d the big symbol pixel data of probability occurs and carry out A that changing may appear in arithmetic coding, four kinds of arithmetic path schematic diagrames of C value for the present invention once reads two;

Fig. 5 a, 5b, 5c and 5d the less symbol pixel data of probability occurs and carry out A that changing may appear in arithmetic coding, four kinds of arithmetic path schematic diagrames of C value for the present invention once reads two;

Fig. 6 is a probability estimated statement of the present invention;

Fig. 7 is a counting accelerometer of the present invention;

Fig. 8 a, 8b are relatively schematic diagram of the sequential chart of arithmetic coding when known and the invention process;

Fig. 9 a, 9b be arithmetic coding known during with the invention process sequential chart and the comparison schematic diagram of hsrdware requirements;

Figure 10 is a method flow diagram of the present invention; And

Figure 11 is the comparing data table of the present invention under multiple implementation condition situation.

Wherein, Reference numeral:

110 input modules

120 selectors

130 computing modules

140 output modules

150 probability estimated statements

160 counting accelerometers

170 memories

180 two pixel datas

190 A, the C value

Step 210 is read in two pixel value data and background value

Does step 220 judge that two pixel values are identical?

Step 230 is calculated with the known coding that counts

Step 240 determines arithmetic path by selector according to background value

After step 250 is confirmed arithmetic path, according to probability estimated statement and counting accelerometer

Calculate A, the C value

Embodiment

Please refer to Fig. 1, be system architecture diagram of the present invention.Be with the processing mode difference in past, past is when utilizing arithmetic coding to handle image compression, it all is the mode with in proper order, once can only read a pixel data, shown in Fig. 2 a, when pixel 1 is read in, judge that at first whether the pixel PIX that is read in is for the big symbol (MPS of probability occurring, More Probable Symbol)? if then call out and the big symbol letter formula sign indicating number (CODEMPS) of probability occurs and carry out calculation process; Otherwise, then call out and the less symbol letter of probability formula sign indicating number (CODELPS) occurs and carry out calculation process, just can get one group of A, C value 190 afterwards.

Explain for an embodiment, please refer to Fig. 3 a, this is the schematic diagram of the known data of processed pixels in proper order arithmetic coding, suppose that the probability that " 0 " is occurred is 2/3, and the probability that " 1 " is occurred is 1/3, LSZ=i/3 just, therefore when carrying out calculating the first time, base value C is since 0 calculating, and whole interval big or small A is 1, supposes that the digital picture sign indicating number that will compile is " 000 ", at first read in first yard " 0 ", in very first time pulse operation time, call out the big symbol letter formula yardage of probability occurs and calculate after, can obtain C=0 and A=1, LSZ=1/3; Read in second yard " 0 " again, second time pulse call out in operation time the big symbol letter formula yardage of probability occurs and calculate after, can obtain C=1/3 and A=2/3, LSZ=2/9; Read in trigram " 0 " again, the 3rd time pulse call out in operation time the big symbol letter formula yardage of probability occurs and calculate after, can obtain C=5/9 and A=4/9, LSZ=4/27; Hence one can see that is all 000 trigram pixel data when the real number value of coding gained for real number value between 19/27 to 1.

Input module 110 of the present invention once can read two pixel datas 180, when these two pixel datas 180 not simultaneously, then take the previous well known practice of being put forward, one next deal with in proper order, therefore, input module 110 also comprises a buffer (not drawing among the figure) temporarily to deposit second pixel data, continue again after waiting first pixel data to handle to handle, also can read in a pixel data again judges whether to equate, when if two pixel datas 180 equate, can do you then shown in Fig. 2 b, judge that the pixel PIX that is read in is for the big symbol M PS of probability occurring? if then call out and the big symbol letter formula sign indicating number of probability occurs and carry out calculation process; Otherwise, then call out and the less symbol letter of probability formula sign indicating number occurs and carry out calculation process, thus, just can be between a period of time pulse obtain one group of arithmetic coding A of two pixel datas 180, C value 190 in operation time.Shown in Fig. 3 b, input module 110 once reads two pixel datas " 00 ", after calculating in very first time pulse operation time, can obtain C=0 and A=1, LSZ=4/9; Second time pulse call out in operation time the big symbol letter formula yardage of probability occurs and calculate after, can obtain C=5/9 and A=4/9, LSZ=4/27.

And to reach between a period of time in pulse operation time, obtain the A of the arithmetic coding gained of two pixel datas 180, C value 190 then must be analyzed execution continuously and the big symbol letter formula sign indicating number of probability occur and the less symbol letter of probability formula A that sign indicating number may change, the situation of C value 190 occur.Please refer to Fig. 4 a, Fig. 4 b, Fig. 4 c and Fig. 4 d, this the big symbol pixel data of probability occurs and carries out A that changing may appear in arithmetic coding for once reading two, four kinds of arithmetic path schematic diagrames of C value 190, at first kind of arithmetic path shown in Fig. 4 a, at last Shu Chu A value be A-(LSZ1[ST[CX]]+LSZ2[ST[CX]]), and the C value is constant, and wherein CX is the background value of this input pixel; ST[CX] expression is by the plain current STATE value of forming of CX of 10 bits, each ST[CX] initial value all be 0, next ST[CX] value determine (NMPS or NLPS) by the probability estimated statement; LSZ[ST[CX]] meaning of expression is ST[CX] the LSZ value of the correspondence found from the probability estimated statement; Second kind of arithmetic path shown in Fig. 4 b, Shu Chu A value is LSZ2[ST[CX at last]], and the C value is C+2*A; The third arithmetic path shown in Fig. 4 c, at last Shu Chu A value be (LSZ1[ST[CX]]-LSZ2[ST[CX]]), and the C value is C+A; The 4th kind of arithmetic path shown in Fig. 4 d, Shu Chu A value is LSZ2[ST[CX at last]], and the C value is C+A; Same, please refer to Fig. 5 a, Fig. 5 b, Fig. 5 c and Fig. 5 d, this the less symbol pixel data of probability occurs and carries out A that changing may appear in arithmetic coding, four kinds of arithmetic path schematic diagrames of C value 190, first kind of arithmetic path shown in Fig. 5 a for once reading two, at last Shu Chu A value be A-(LSZ1[ST[CX]]+LSZ2[ST[CX]]), and the C value is constant; Second kind of arithmetic path shown in Fig. 5 b, Shu Chu A value is LSZ2[ST[CX at last]], and the C value is C+2*A; The third arithmetic path shown in Fig. 5 c, at last Shu Chu A value be (LSZ1[ST[CX]]-LSZ2[ST[CX]]), and the C value is C+A; The 4th kind of arithmetic path shown in Fig. 5 d, Shu Chu A value is LSZ2[ST[CX at last]], and the C value is C+A.

And required each calculated value that uses in the computing, please refer to Fig. 6, this is probability estimated statement (the PE table that deposits in the memory 170, Probability Estimation table) 150, deposited the required LSZ that uses in each arithmetic path in the table, NLPS (the probability estimated value of the less symbol of probability appears in the Next LPSprobability-estimation State next one), NMPS (Next MPS probability-estimation State, the probability estimated value of the big symbol of probability appears in the next one) and the SWTCH (target function that whether exchanges, if SWTCH[CX]=1, MPS can be exchanged, promptly 0 be changed to 1 or 1 and be changed to 0) each calculated value, wherein if run into SWTCH=1, this moment is if MPS is a pixel 1, will become pixel 0 by SWTCH, in known mode, when carrying out a pixel data arithmetic coding, can obtain the A of a pixel data compression by inquiry probability estimated statement 150, C value 190 at every turn; Yet, if will make the present invention between a period of time, pulse handle two pixel datas 180 in operation time, please refer to Fig. 7, then also need in memory 170, to increase a counting accelerometer 160, stored calculated value is and handles first kind of arithmetic path and the third arithmetic path in the table, calculating A value need use (LSZ1+LSZ2) and reach (LSZ1-LSZ2) two groups of calculated values, these values are calculated in advance well and left in the memory 170, then can make selector 120 when carrying out the arithmetic path judgement, directly can obtain respective value rapidly by inquiry counting accelerometer 160, add the adder of increase, subtracter and comparator, just can be in four kinds of arithmetic paths, select two pixel datas 180 that read and should be inserted in which arithmetic path and calculate.

Known account form sequential chart, shown in Fig. 8 a, each time pulse can only be handled a pixel data operation time, therefore, suppose that institute's 6 yards pixel datas to be processed are " 001100 ", use known manner just to need 6 time pulses to deal with operation time, and by method of the present invention, please refer to Fig. 8 b, computing module 130 can be according to an arithmetic path of selector 120 decisions, the arithmetic coding of two pixel datas 180 is handled in pulse in operation time between a period of time, only needs 3 time pulse calculation process times altogether.

Further illustrate, please refer to Fig. 9 a and Fig. 9 b, Fig. 9 a is known mode, need to use 6 time pulse operation times, and handle and the big symbol pixel data of probability to occur and need 1 adder, 1 subtracter and 2 comparators, the less symbol pixel data of probability occurs and need 1 adder, 2 subtracters and 2 comparators and handle; The schematic diagram that Fig. 9 b is " 001100 " for processed pixels data of the present invention, the big symbol pixel data of probability appears in processing needs 4 adders, 8 subtracters and 12 comparators, 4 adders of the less symbol pixel data need of probability appear and handle, 11 subtracters and 16 comparators, and with reference to Figure 10, this is a method flow diagram of the present invention, at first, once read in two pixel value data and background value (step 210) thereof by input module 110, do you judge that again two pixel values are identical? (step 220) is if inequality, then carry out compressed encoding and calculate (step 230) in known arithmetic coding mode, if it is identical, then again according to the background value of identical neighbor, judge which situation that belongs to four arithmetic paths, select arithmetic path (step 240) by selector 120, and search probability estimated statement 150 and counting accelerometer 160 by computing module 130, just can calculate the A of these 6 yards binary picture data operation time at 3 time pulses in the arithmetic coding mode, C value 190, and by output module 140 outputs (step 250).Because a time pulse can be handled two identical pixel datas 180 operation time, saved the processing time of half originally.

Therefore, please refer to Figure 11, can clearly understand, use known arithmetic coding compress mode, suppose that processing speed is 1 times, then only need 2 adders, 3 subtracters and 4 comparators also only need use the probability estimated statement 150 that size is 128 characters; And the inventor obtains through repeatedly testing, once reading two identical pixel datas 180 handles, though the probability about 50% that this situation occurs, can reach 2 times acceleration effect under the best circumstances, on average get off to reach to accelerate 30% effect, though the increase in demand on hardware, need use 8 adders, 19 subtracters and 28 comparators, and except that original need use size be the probability estimated statement 150 of 128 characters, also need increase size at memory 170 is the counting accelerometer 160 of 1000 bytes, but handle and compare with once reading three identical above pixel datas, comply with the hardware resource that is increased and come comparatively speaking obviously the present invention to meet economic benefit with the average effect that increases.

Certainly; the present invention also can have other various embodiments; under the situation that does not deviate from spirit of the present invention and essence thereof; those of ordinary skill in the art work as can make various corresponding changes and distortion according to the present invention, but these corresponding changes and distortion all should belong to the protection range of the appended claim of the present invention.

Claims

1. A system for accelerating the processing speed of arithmetic coding, characterized in that, comprising:

An input module, used to read in two adjacent pixel data and their background values at a time;

A probability estimation table, which includes the interval size LSZ of a plurality of symbols with lower probability of occurrence, the estimated probability value NLPS of the next symbol with lower probability of occurrence, the estimated value NMPS of the probability of the next symbol with higher probability of occurrence, and the index function of whether to exchange Calculated value of SWTCH;

A calculation accelerometer, which is used to record a plurality of calculation values for adding and subtracting the interval sizes of symbols with smaller occurrence probability according to the multiple probability values of the probability estimation table in advance;

A selector, when the data of two adjacent pixels read in at one time are the same, in multiple operation paths that can change the size A of a group of overall intervals and the base value C, determine a value according to the background value of the same adjacent pixel computation path; and

A calculation module, used to search the probability estimation table and the calculation acceleration table to calculate the overall interval size A and the base value C of the group according to the calculation path.

2. The system for speeding up arithmetic coding processing according to claim 1, wherein the pixel data is a binary data.

3. The system for speeding up the processing speed of arithmetic coding according to claim 1, characterized in that, the calculation accelerometer includes at least two sets of calculation values of LSZ1+LSZ2 and LSZ1-LSZ2, wherein LSZ1 and LSZ2 are two groups with a relatively low probability of occurrence The interval size of the symbol.

4. The system for accelerating the processing speed of arithmetic coding according to claim 1, characterized in that, when the system reads in two identical adjacent pixel data for processing, it needs to use 8 adders, 19 subtractors and 28 a comparator.

5. A method for accelerating the processing speed of arithmetic coding, characterized in that, comprising the following steps:

Read in two adjacent pixel data and their background values at a time;

When the data of two adjacent pixels read in at one time are the same, in a plurality of operation paths that can change the size A of a group of overall intervals and the base value C, a calculation path is determined according to the background value of the same adjacent pixel; and

According to the calculation path, look up a probability estimation table and a calculation acceleration table to calculate the overall interval size A and base value C of the group;

Among them, the probability estimation table includes the interval size LSZ of multiple symbols with lower probability of occurrence, the estimated probability value NLPS of the next symbol with lower probability of occurrence, the estimated probability value NMPS of the next symbol with higher probability of occurrence, and the index function of whether to exchange Calculated value of SWTCH;

The calculation acceleration table is used to record a plurality of calculation values which are added and subtracted in advance according to the plurality of probability values of the probability estimation table to calculate the interval size of each symbol with a lower probability of occurrence.

6. The method for speeding up arithmetic coding processing according to claim 5, wherein the pixel data is binary data.

7. The method for speeding up the processing speed of arithmetic coding according to claim 5, characterized in that, the calculation accelerometer contains at least two sets of calculated values of LSZ1+LSZ2 and LSZ1-LSZ2, wherein LSZ1 and LSZ2 are two with a relatively low probability of occurrence The interval size of the symbol.

8. The method for accelerating the processing speed of arithmetic coding according to claim 5, characterized in that, when reading in two identical adjacent pixel data for processing in the method, 8 adders, 19 subtractors and 28 comparators.