search

ejmahler / rust_dct

Rust library to compute the main four discrete cosine transforms
Apache License 2.0
38 stars 6 forks source link

Multidimensional DCTs #2

Open abonander opened 5 years ago

abonander commented 5 years ago

I'm looking to upgrade/replace the naive DCT implementation in my img_hash crate.

However, I need a 2 dimensional DCT, which I know I can implement with a row-column algorithm of 1D DCTs but I'm wondering if it's possible to produce an optimized 2D DCT.

I imagine, though, this would require RustFFT to implement a 2D FFT algorithm.

ejmahler commented 5 years ago

Hey Austin,

I'm not aware of any 2D-specific DCT (or FFT) algorithms that are faster than computing a 1D DCT (or FFT), then transposing, and computing another 1D FFT/DCT.

I know of some optimizations that I'm planning on implementing in the future that will help in the case of 2D DCTs. For example, right now we allocate scratch space every time we need to convert a DCT problem to FFT - but if the "process_dctx" methods could take a scratch buffer as a parameter, the same scratch buffer could be reused

Multiple dimension FFTs seem to be a common request, so I'm considering writing it purely out of convenience. But if I do, it own't be in the next few weeks, so don't let that hold you up. If I do, I can leave an issue in img_hash for you to switch over.

On Wed, Dec 26, 2018 at 9:37 AM Austin Bonander notifications@github.com wrote:

I'm looking to upgrade/replace the naive DCT implementation in my img_hash crate https://github.com/abonander/img_hash/blob/29c9d582adf3e367a54b8d2d1b271fd557b11a19/src/dct.rs .

However, I need a 2 dimensional DCT, which I know I can implement with a row-column algorithm of 1D DCTs but I'm wondering if it's possible to produce an optimized 2D DCT.

I imagine, though, this would require RustFFT to implement a 2D FFT algorithm.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ejmahler/rust_dct/issues/2, or mute the thread https://github.com/notifications/unsubscribe-auth/ABGmep88Nohae-F8pMvBzPKpjL1c9oPoks5u84mygaJpZM4ZhzoR .

abonander commented 5 years ago

An advantage of my naive implementation is that it doesn't require transposing rows to columns; I use an adapter type to wrap the math to index columns directly. I also precompute the DCT coefficients since the matrix size is known ahead of time. It's probably worth benchmarking against using your 1D implementation with a transposition step.

ejmahler commented 5 years ago

What size and type DCT do you typically need? The comment in your code mentions 3x3 but I suspect that’s just an example.

On Wed, Dec 26, 2018 at 12:46 PM Austin Bonander notifications@github.com wrote:

An advantage of my naive implementation is that it doesn't require transposing rows to columns; I use an adapter type to wrap the math to index columns directly. I also precompute the DCT coefficients since the matrix size is known ahead of time. It's probably worth benchmarking against using your 1D implementation with a transposition step.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/ejmahler/rust_dct/issues/2#issuecomment-450000015, or mute the thread https://github.com/notifications/unsubscribe-auth/ABGmerB8Y5-4i5gmHJ6DQbVkxfQ49G-Sks5u87YBgaJpZM4ZhzoR .

abonander commented 5 years ago

@ejmahler actually the default is 8x8 but the idea is to have any user-configurable dimensions. In fact that default would be 16x16 because the algorithm does the DCT on a double size image and then crops to the lower corner to cut out high frequency information.