Skip to main content ↑ ↓

Notice

Please note that most of the software linked on this forum is likely to be safe to use. If you are unsure, feel free to ask in the relevant topics, or send a private message to an administrator or moderator. To help curb the problems of false positives, or in the event that you do find actual malware, you can contribute through the article linked here.
Topic: FLAC compression improvement patch (Read 45126 times) previous topic - next topic
0 Members and 1 Guest are viewing this topic.

FLAC compression improvement patch

Reply #50 –
There's an idea I've been knocking around (and I've even implemented it but lost the source) that might help squeeze out some of the bits for a linear predictive coding based lossless audio codec: Replace the windowing/autocorrelation/Levinson Durbin recursion approach with an integer least squares solver. This will give you the optimally quantized filter coefficients (for a given denominator) to minimize the RMS level of the prediction residual. This involves (1) a couple of Householder reflections to reduce the number of linear equations, (2) a lattice reduction to improve the condition and finally (3) a branch-and-bound recursive search for the best integer coefficients. This seems more promising w.r.t. compression than testing different kinds of window functions. Any takers?

FLAC compression improvement patch

Reply #51 –
I'm sorry, I'm not really a math guy. It took me long enough to get this tiny improvement right, coding an entirely new predictor stage would take me months. I usually just try something, if it works I'm happy, if it doesn't I try again. This would be too big a venture to tackle in that way

However, it does sound like a better approach than the current one, which involves too many intermediate steps (signal -> autocorrelation -> lpc -> quantizated lpc) to my taste, so I hope someone might be able to pull this of.
Music: sounds arranged such that they construct feelings.

FLAC compression improvement patch

Reply #52 –
Quote from: SebastianG on
There's an idea I've been knocking around (and I've even implemented it but lost the source) that might help squeeze out some of the bits for a linear predictive coding based lossless audio codec: Replace the windowing/autocorrelation/Levinson Durbin recursion approach with an integer least squares solver. This will give you the optimally quantized filter coefficients (for a given denominator) to minimize the RMS level of the prediction residual. This involves (1) a couple of Householder reflections to reduce the number of linear equations, (2) a lattice reduction to improve the condition and finally (3) a branch-and-bound recursive search for the best integer coefficients. This seems more promising w.r.t. compression than testing different kinds of window functions. Any takers?

It seems the idea is not as easy to implement as it sounds to a mathless person like me. Devs may not see the result very promising. Shouldn't it otherwise been implemented already? Was your implementation directly done to the flac code?
Is troll-adiposity coming from feederism?
With 24bit music you can listen to silence much louder!

FLAC compression improvement patch

Reply #53 –
Quote from: Gregory S. Chudov on
I'm not really good at signal processing theory, but apparently LPC_error is supposed to predict the error between the linear predictor and the original signal, and it does that quite well most of the time. That's the whole point - it lets us choose the best order (FLAC__lpc_compute_best_order) and optionally window function without actually calculating all the residuals. I do it in CUETools.Flake and i like the results. In the version below, compression levels from 2 to 6 choose windows from the set of partial tukey / punchout tukey based on LPC_error.

Would be nice to see how this competes in a lossless codec comparison.

Hi Grigory,
i just tried todays new versions and flake compresses nicely but with flacCL i see no real improvement.
Is troll-adiposity coming from feederism?
With 24bit music you can listen to silence much louder!

FLAC compression improvement patch

Reply #54 –
I haven't updated flacCL yet. Have to clean up what i did with Flake first, e.g. compression levels 9-11 are completely broken right now. I did update ALACEnc though, and it benefits from the new window functions too.
CUETools 2.1.6

FLAC compression improvement patch

Reply #55 –
Thanks,
the Commit for flacCL states "...use new window functions (partial_tukey,... " but is only flake so far.
Have to wait then.
Cheers!
Is troll-adiposity coming from feederism?
With 24bit music you can listen to silence much louder!

FLAC compression improvement patch

Reply #56 –
Quote from: Gregory S. Chudov on
I did update ALACEnc though, and it benefits from the new window functions too.

I don't use ALAC but encoded some albums. Even when i learned ALAC has limitations with your recent version it compresses better as official flac. It needs really much processing power though.
Is troll-adiposity coming from feederism?
With 24bit music you can listen to silence much louder!

FLAC compression improvement patch

Reply #57 –
Looks like the patch has made it into git \o/

edit: any idea why I am getting a "bash: syntax error near unexpected token `('" with
Code: [Select]
flac --best -A tukey(0,5) -A partial_tukey(2) -A punchout_tukey(3) -V file.wav

Freshly compiled from git master on archlinux.

FLAC compression improvement patch

Reply #58 –
Quote from: ChronoSphere on
Looks like the patch has made it into git \o/

edit: any idea why I am getting a "bash: syntax error near unexpected token `('" with
Code: [Select]
flac --best -A tukey(0,5) -A partial_tukey(2) -A punchout_tukey(3) -V file.wav

Freshly compiled from git master on archlinux.


'(' and ')' are special characters. You need to escape them or use quotes.

This should work as far as Bash concerned:
Code: [Select]
flac --best -A 'tukey(0,5)' -A 'partial_tukey(2)' -A 'punchout_tukey(3)' -V file.wav

FLAC compression improvement patch

Reply #59 –
Quote from: ChronoSphere on
edit: any idea why I am getting a "bash: syntax error near unexpected token `('" with

I use this in bash
Code: [Select]
flac --best -A tukey\(0,5\) -A partial_tukey\(2\) -A punchout_tukey\(3\) -V file.wav

Music: sounds arranged such that they construct feelings.

FLAC compression improvement patch

Reply #60 –
Yes, that works, thanks. Should have been obvious I guess ><

Some results:
Code: [Select]
Hi-res album: 24Bit 48kHz stereo
flac --best:       916 355 531 bytes (873,9MB), ratio=0.717, decoding speed=364.682x
flac --best + new: 913 849 364 bytes (871,5MB), ratio=0.715, decoding speed=363.772x
tak -p4m:          892 069 798 bytes (850,7MB), ratio=0,698, decoding speed=214.003x


Code: [Select]
CD-audio (different album)
flac --best:       496 035 472 bytes (473,1MB), ratio=0.600, decoding speed=528.219x
flac --best + new: 493 842 622 bytes (471,0MB), ratio=0.597, decoding speed=526.347x
tak -p4m:          478 046 077 bytes (455,9MB), ratio=0,578, decoding speed=396.918x


No encoding times because I did this in a VM, so I don't think they are useful. Subjectively, the new preset hurts encoding time a lot though, as expected. I think it's a decent decrease in filesize, too bad it still doesn't reach TAK levels, but we knew that from the start.

FLAC compression improvement patch

Reply #61 –
Quote from: ChronoSphere on
Subjectively, the new preset hurts encoding time a lot though, as expected

Those are not the new presets I've proposed though  Could you try the following instead?

edit: it seems that this change makes the exhaustive model search less effective, so I suggest it is dropped from compression levels 7 and 8. That way, encoding improves in 96% of the cases (at least, with my set of files) but the compression speed is kept about the same.

Code: [Select]
flac --best --no-exhaustive-model-search -A tukey\(0,5\) -A partial_tukey\(2\) -A punchout_tukey\(3\) -V file.wav


It should be about as fast as the current preset.

Quote
I think it's a decent decrease in filesize, too bad it still doesn't reach TAK levels, but we knew that from the start.

Indeed, no miracles here.
Music: sounds arranged such that they construct feelings.

FLAC compression improvement patch

Reply #62 –
I just picked the preset you suggested for "x2" here.
Turning off exhaustive search did speed it up, but the compression ratio is worse now:
Code: [Select]
flac --best:            496 035 472 bytes (473,1MB), ratio=0.600
flac --best + noex new: 496 020 936 bytes (473,0MB), ratio=0.600
flac --best + new:      493 842 622 bytes (471,0MB), ratio=0.597


edit: the 24bit cd is even worse:

Code: [Select]
flac --best + noex new: 916 441 883 bytes (874,0MB), ratio=0.717
flac --best:            916 355 531 bytes (873,9MB), ratio=0.717
flac --best + new:      913 849 364 bytes (871,5MB), ratio=0.715

FLAC compression improvement patch

Reply #63 –
Quote from: ChronoSphere on
Turning off exhaustive search did speed it up, but the compression ratio is worse now:

Yes, it doesn't work for all kinds of music. My results were obtained with a list of 43 tracks, one for each track of the list http://xiph.org/flac/comparison.html

Code: [Select]
current -8:          ratio 56.69%, encoding speed 58.8x, decoding speed 399x
proposed -8:         ratio 56.51%, encoding speed 52.7x, decoding speed 401x
propesed -8 with -e: ratio 56.45%, encoding speed 13.5x, decoding speed 397x

So, my results are that the proposed setting will yield 0.19 percentage point (or 0.32%) on average with little speed loss. Depending on the CPU architecture, it might even be a speed increase. Adding -e improves another 0.06 percentage point (0.11%) but add the cost of slowing down the encoding by a factor 4.

Your mileage may vary, and there will undoubtedly be some albums which for which the new setting is worse than the old. My test results (from an older test ran with all the tracks of those 43 CDs) say that 43/43 (100%) of the albums and 578/597 (97%) of all tracks the new settings are an improvement.
Music: sounds arranged such that they construct feelings.

FLAC compression improvement patch

Reply #64 –
If 97% of tracks get an improvement out of it, I guess the exhaustive part can be left to flaccl et al.

FLAC compression improvement patch

Reply #65 –
Hello,

For Windows users, win32 & win64 binaries.

Have fun,

    AiZ

FLAC compression improvement patch

Reply #66 –
Quote from: ChronoSphere on
If 97% of tracks get an improvement out of it, I guess the exhaustive part can be left to flaccl et al.

You can always add -e if you want.

I'd like to get some more feedback. Sure, the files I used for the test seem to form a quite balanced pool, but more testing is better. Here's a Windows 32-bit binary that has the new presets (with the change to -7 proposed by lvqcl), writes 'alpha build libFLAC 1.3.1 20140922' to the vendor strings and prints warnings to the console output.

http://www.audiograaf.nl/misc_stuff/flac-n...HA-UNSTABLE.exe

I hope these warnings are enough to prevent use in production. While the binary passed the test suite, use with caution

edit: AiZ was just a tiny bit faster. Do these binaries have the new presets as well?
Music: sounds arranged such that they construct feelings.

FLAC compression improvement patch

Reply #67 –
The names of the archives (flac-git-9572984-winXX) suggest that they were made from the latest git code (that don't have new presets).

(But they allow to use new window functions)

FLAC compression improvement patch

Reply #68 –
I did a quick test and ran my FLAC library through the ktf's test binary with mode -8. It's not the largest set of files but contains 4700 files, most are 16-bit CD sourced files but some Bandcamp purchases are in 24 bits.
35 files out of the 4700 (0.74%) came out larger with the change and the rest were smaller. Average bitrate for this group is 660 kbps with FLAC 1.2/1.3 and 668 kbps with the change. All these files are 16 bps.
Average bitrate for all files is 975 kbps with the current FLAC and 973 kbps with the proposed change.

FLAC compression improvement patch

Reply #69 –
Quote from: Case on
Average bitrate for all files is 975 kbps with the current FLAC and 973 kbps with the proposed change.

Thanks for the test. Pity that the improvement you see is even smaller than mine, but then again, it's 'free' and as Chronosphere's test show, adding -e might help a little if you don't mind the slow encoding.
Music: sounds arranged such that they construct feelings.

FLAC compression improvement patch

Reply #70 –
I ran another test with -8 -e parameters. Encoding the files took 3 minutes longer than without the -e (154 min for -8, 157 min for -8 -e).
This time no track was larger and my average bitrate for the entire set is 972 kbps.

FLAC compression improvement patch

Reply #71 –
That is strange. I'm not sure what happened, but the encoding should be four times as slow, which follows both from my test results as well as from plain logic. Are you sure those results are correct?
Music: sounds arranged such that they construct feelings.

FLAC compression improvement patch

Reply #72 –
Yes I'm sure. These results are bottlenecked by hard disk speeds. Encoding a single file to null device shows the quadrupled encoding time but with multiple threads running with foobar2000's converter it's still running fast enough.

FLAC compression improvement patch

Reply #73 –
Ran a test on a mixed set of files:

fast/loud music (rock/electro/orchestral)
Code: [Select]
old:   1,26 GB (1.355.082.551 bytes)
new:   1,25 GB (1.352.396.905 bytes) [-2,56MB]
new+e: 1,25 GB (1.351.271.462 bytes) [-3,63MB]


slow/quiet music (piano/electro/acoustic)
Code: [Select]
old:   2,05 GB (2.205.484.811 bytes)
new:   2,04 GB (2.199.431.091 bytes) [ -5,77MB]
new+e: 2,04 GB (2.192.955.490 bytes) [-11,94MB]


set of 812 files (contains some game music rips, 44100 Hz (99.3%); 22050 Hz (0.6%); 48000 Hz (0.1%)):
Code: [Select]
old:   15,0 GB (16.197.346.213 bytes)
new:   15,0 GB (16.127.938.889 bytes) [ -66,19MB]
new+e: 14,9 GB (16.063.133.511 bytes) [-127,99MB]



encoding speeds on a Phenom II X4 975@3.4GHz with foobar, 4 threads, 661MB wav:

in RAMdisk:
Code: [Select]
old:   ~326-335x, 0:12
new:   ~311-350x, 0:12
new+e: ~87-95x, 0:48


same HDD:
Code: [Select]
old:   ~320-340x, 0:12
new:   ~300-340x, 0:13
new+e: ~84-91x, 0:49


That must be one hell of a slow HDD, Case. That, or your encoding speeds are much higher than mine.

FLAC compression improvement patch

Reply #74 –
Comparing a single 661 MB file is quite different than ~150 GB of material. The first compression test was performed from WD Red 6 TB drive to WD Green 2 TB drive (WD20EARX). Source files are unfragmented. The second test with -e parameter was done from the same source but to a different WD Green 2 TB drive (WD20EARS). Of course it's possible disk fragmentation affected results and since I wasn't doing this for speed testing, I was using the machine for other tasks at the same time.