Compressing Method for Digital Audio Files

• US 20080215340A1
• Filed: 05/25/2005
• Published: 09/04/2008
• Est. Priority Date: 05/25/2005
• Status: Abandoned Application

• Current Assignee: Hui Lin
• Original Assignee: Hui Lin
• Inventors: Su, Wen-Yu, Chen, Chang-Wci, Wang, Jing-Xin
• Application Number:
  US11/914,453
• Publication Number:
  US 20080215340A1
• Time in Patent Office: Days
• US Class Current: 704/500
• CPC Class Codes: G10L 19/0017 Lossless audio signal coding; Perfect reconstruction of coded audio signal by transmission of coding error G10L19/24 takes precedence
• CPC Class Codes: G10L 19/0204 using subband decomposition

Abstract

A compressing method for digital audio files mainly utilizes a harmonic structure quad tree (HSQT) to re-arrange the frequency coefficient in each frame, and applies concurrent encoding in hierarchical trees (CEIHT) algorithm to increase and simplify the processing speed; the coefficient of the CEIHT is symbolized according to an arithmetic coding; the record of the probability of the symbol is used to determine the number of bits to be stored; the probability is in inverse order of the number of bits requiring storage, and thus increasing the occurrence probability of the symbol may greatly reduce the number of bits to be stored. As a result, the overall compressing method is done in simplified processing procedures and outputting an audio compressed file with a high compression ratio.

Claims

1. A compressing method for a digital audio file, comprising:

writing an audio file signal or analyzing an audio file information prior to encoding procedures;

reading audio raw data;

cutting out a frame from a signal according to a frame size and an overlap-add size;

using a discrete cosine transform or inverse transform,

using a harmonic structure quad tree; and

encoding a frequency coefficient by employing a CEIHT algorithm and arithmetic coding (AC) on said harmonic structure quad tree so as to complete encoding of a frame.

2. The method of claim 1, wherein said means of writing said audio file signal or analyzing said audio file information includes sampling rate, word length, frame size, total number of frame and overlap-add size.

3. The method of claim 1, wherein said discrete cosine transform adopts N point Fast Fourier Transform so as to increase a computing speed.

4. The method of claim 1, wherein said harmonic structure quad tree construction is a tree structure established in accordance with relationships between a magnitude and a power of frequencies in an audio signal.

5. The method of claim 4, wherein said harmonic structure quad tree construction procedure includes the following steps:

a. Selecting a candidate that has not be selected from a candidate list and setting a coefficient thereof as a new root;

b. Setting said coefficient of all multiple indices of said selected candidate as leaves;

c. Writing tree leaves location of quad tree according to a full tree construction sequence;

d. If said selected multiple indices have already been selected, then searching for a substitute indices that has not been selected from a search range of said multiple indices for substitution;

if said coefficient in said search range has all been selected, then skipping the multiple indices location;

e. If the number of trees to be constructed is not yet satisfied, then returning to Step a; and

f. For all remaining coefficients that have not been selected, setting a coefficient with an index of 1 as root and placing the others in sequence so as to construct a complement quad tree.

6. The method of claim 5, wherein said selection means of said candidate selection sequence in said Step a is an absolute value of said coefficient of a discrete cosine transform in said search range, placed from a large value to a small value.

7. The method of claim 1, wherein said CEIHT algorithm includes initialization pass, list initialization pass, sort pass, and refinement pass.

8. The method of claim 1, wherein an occurrence probability of said sampling rate is used to determine a storage bit, the higher the probability, the fewer the bits needed for storage, and vice versa.

9. The method of claim 1, wherein said CEIHT algorithm includes:

a. Threshold initialization pass;

b. List initialization pass;

c. Sort pass;

d. Refinement pass; and

e. Quantization coefficient update pass.

10. The method of claim 9, wherein said threshold initialization pass includes the following steps:

a. Threshold initialization;

b. Searching for a coefficient having the largest absolute value in said tree structure and defining said coefficient as C_max;

c. Calculating coefficient n with a formula;

n=└

log₂(C_max)┘

; and

d. Outputting the value of n, and set 2ⁿ as said initial threshold value.

11. The method of claim 9, wherein said list initialization pass includes the following steps:

a. Setting said list of significant pixels (LSP) as an empty set;

b. For all roots in said list of insignificant pixels (LIP) and said list of insignificant sets (LIS), creating a group for every 3 roots and grouping the remaining roots less than 3 into one group;

c. Placing information of each root in said tree structure in said list of insignificant pixels (LIP); and

d. Placing information of each root in said tree structure in said list of insignificant sets (LIS), and setting an entry in said list of insignificant sets (LIS) as Type-A.

12. The method of claim 9, wherein said sort pass includes the following steps:

a. Determining whether the i-th entry in said list of insignificant pixels (LIP) exists, and if so, then performing said list of insignificant pixels (LIP) process;

otherwise, performing Step b; and

b. Determining whether the i-th entry in said list of insignificant sets (LIS) exists, and if so performing said list of insignificant sets (LIS) process;

otherwise, performing said refinement pass.

13. The method of claim 12, wherein said list of insignificant pixels (LIP) pass includes the following steps:

a. Setting a group size obtained from said entry as G;

b. Determining whether said entry i in the same group in said list of insignificant pixels (LIP) is a significant value S_n(i), and using AC to output a number of C parameters S_n(i) for outputs;

c. Setting Gn as the number when S_n(i) . . . S_n(i+G−

1) is 0;

d. For determining whether S_n(i) in the group is 1, outputting said entry with a positive and negative value of a coefficient, and deleting it from said list of insignificant pixels (LIP), and adding it in said list of significant pixels (LSP),

e. For determining whether S_n(i) in the group is 0, setting Gn as the number for the next group; and

f. Returning to said Step a of sort pass, to determine determining whether the i-th entry in said list of insignificant pixels (LIP) exists, and if not, then performing said list of insignificant sets (LIS) pass.

14. The method of claim 12, wherein said list of insignificant sets (LIS) pass includes the following steps:

a. Setting a group size obtained from said entry as G; and

b. Determining a type of the first entry in said list of insignificant sets (LIS) (Type-A, Type-B and Type-C).

15. The method of claim 14, wherein said Type-A pass includes the following steps:

a. Determining whether a descendant (S_n(D)) in said entry of the same group is significant, and outputting a number of G significant parameters S_n(D) using arithmetic coding (AC);

b. Calculating the number Gn when the number of G significant parameters S_n(D) is 0;

c. Determining whether the set L of children and grandchildren other than the offspring of said entry having S_n(D) of 1 in the same group is an empty set, and if so, then setting S_n(L)=0;

otherwise, determining whether the set L is significant, and using arithmetic coding (AC) to output a number of G-Gn parameters S_n(L) in the same group,

d. If the S_n(D) of the entry in the group is 1, and the corresponding S_n(L) is 1 (as shown in the direction X), then determining whether 4 offspring have significant value (S_n(O)) and outputting S_n(D) of said 4 offspring, and 8 bits using arithmetic coding (AC), and outputting a positive and negative value of said coefficient of said 4 offspring, and adding into said list of insignificant sets (LIS), and setting as type-C, and deleting said entry from said list of insignificant sets (LIS);

e. If S_n(D) of said entry in said group is 1, and the corresponding S_n(L) is 0, then determining whether 4 offspring have significant value (S_n(O)), and outputting with arithmetic coding (AC), if L is not an empty set, then changing said type of said entry to type-B, and placing said entry to the very last of said list of insignificant sets (LIS), if it is an empty set, then deleting said entry from said list of insignificant sets (LIS);

f. Setting the number of entry in said group having S_n(D) of said entry in said group as 0 as Gn, and set to type-A; and

g. Determining whether all entries in said group are determined, and if so, then returning to said step b of sort pass, or performing Step d, or Step e, or Step f depending on the condition.

16. The method of claim 14, wherein said Type-B pass includes the following steps:

a. Outputting S_n(L); and

b. If S_n(L) is 1, then setting the number of offspring O(i) as said group size of G, and adding 4 offspring O(i) to the very last of said list of insignificant sets (LIS), and setting as Type-A, and deleting said entry from said list of insignificant sets (LIS), and performing said step b of sort pass.

17. The method of claim 14, wherein said Type-C pass includes the following steps:

a. Calculating the number Gn where a number of G significant parameters having S_n(D) of 0;

b. Determining whether the set L having children and grandchildren other than the offspring with S_n(D) of 1 in said entity of said same group is an empty set, and if so, then setting S_n(L)=0;

otherwise, determining whether the set L is significant, and using arithmetic coding (AC) to output the parameter value S_n(L) for a number of G-Gn in the same group;

c. If S_n(D) of the entry in the group is 1, and the corresponding S_n(L) is 1 (as shown in the direction X), then determining whether 4 offspring has significant value S_n(O) and outputting the S_n(D) of 4 offspring and 8 bits using arithmetic coding (AC), and outputting a positive and negative value of said coefficient of 4 offspring, and adding to said list of insignificant sets (LIS), and setting as type-C, and deleting said entry from said list of insignificant sets (LIS);

d. If the S_n(D) of the entry in the group is 1, and the corresponding S_n(L) is 0, then determining whether 4 offspring have significant value (S_n(O)), and outputting with arithmetic coding (AC), if L is not en empty set, then changing said type of entry to type-B, and placing said entry in the very last of said list of insignificant sets (LIS), if it is an empty set, then deleting said entry from said list of insignificant sets (LIS);

e. Setting the number of entry in the group having S_n(D) of said entry in said group as 0 as Gn, and setting to type-A; and

f. Determining whether all entries in said group are determined, and if so, then returning to said step b of sort pass, or performing Step d, or Step e, or Step f depending on the conditions a.

18. The method of claim 9, wherein said refinement pass includes the following steps:

a. Determining whether the i-th entry in said list of significant pixels (LSP) exists;

b. For determining whether the current entry is at threshold value 2ⁿ, adding to said list of significant pixels (LSP); and

c. If so, then returning to Step a;

otherwise, outputting the value of the n-th bit of the entry coefficient C_i, and proceeding to determine the next element.

19. The method of claim 9 wherein said quantization coefficient update pass includes the following steps:

a. If the value of n is not equal to 0, then subtracting 1 from said value of n; and

b. Setting a new threshold value at 2ⁿ.

20. The method of claim 1, the corresponding decompressing method comprising:

a. Writing a bit stream and analyzing frame information prior to performing decoding procedures;

b. Reading said bit stream;

c. Writing or analyzing each frame procedure;

d. Obtaining a size of each tree and an original coefficient location after restoring each root location by HSQT;

e. Decoding said original coefficient from encoded coefficient information and said size of tree by employing an Inverse CEIHT+AC, and write to a coefficient location obtained from said HSQT restoration;

f. Using an inverse discrete cosine transform (DCT) to transform signal from frequency domain to time domain; and

g. Performing frame Overlap-add, wherein a window adopts a transformation of Hanning window, the formula is as follows;

$w<br><br>\left(i\right)=\{\begin{array}{cc}<br><br>0.5-0.5<br><br>\cos <br><br>\left(\frac{2<br><br>\mathrm{\pi <br><br>}<br><br><br><br>i}{M}\right),& <br><br>i\in <br><br>\left[0,M/2\right]\\ <br><br>1,& <br><br>i\in <br><br>\left(M/2,N-M/2\right)\\ <br><br>0.5-0.5<br><br><br><br>\cos <br><br>\left(\frac{2<br><br>\mathrm{\pi <br><br>}<br><br>\left(i-N+M\right)}{M}\right),& <br><br>i\in <br><br>\left[N-M/2,N\right]\end{array}$

wherein N is the frame size, M/2 is overlap-add size.