Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Image Compression with Singular Value Decomposition

timbaumann.info

Post reply on HN
Print view View original

21–30 of 47 posts

Re: Image Compression with Singular Value Decomposition

#21

Post by ntr-- »

I worked on a very interesting project aligning point clouds using SVD, for a pair of point clouds of the same scene that are not aligned:

- select 3+ pairs of matching points in each cloud (tops of trees, edges of a building etc)

- calculate the vector to the centroid of each cloud

- use SVD to calculate the rotation that gives a minimum distance when applied from the source to the target

- translate and rotate the source cloud to the target

I did this using the rust nalgebra^1 crate after reading a very helpful paper^2 detailing the process. I had planned to build the rust lib into WASM so the process could be run alongside the browser based point cloud visualiser we were using, but had limited time and instead used Neon^3 to build a native binding for our nodejs server to use.

^1 https://docs.rs/nalgebra/latest/nalgebra/linalg/struct.SVD.h...

^2 https://igl.ethz.ch/projects/ARAP/svd_rot.pdf

^3 https://github.com/neon-bindings/neon

Re: Image Compression with Singular Value Decomposition

#22

Post by VHRanger »

frazar0 wrote: post #14

One issue with SVD is its significant time complexity compared to, for example, the Discrete Cosine Transform used in JPEG

SVD is used more for mathematical elegance than practicality (like ordinary least squares)

In data science most traditional usecases for SVD are superceded by other algorithms (UMAP is especially popular these days).

Re: Image Compression with Singular Value Decomposition

#23

Post by sfpotter »

bee_rider wrote: post #18
daturkel wrote: post #9

Funny enough, I did this same project (minus the fancy web interface) for a numerical linear algebra course in college—except I had to do it in Matlab. It's worse than just about any "real" image compression algorithm, but it works! (Plus you get lossless compression if your image is low-rank.)

It is interesting that lossy compression algorithms are better, despite the Eckart–Young–Mirsky theorem. I guess “best low rank approximation under unitarily invariant norms“ doesn’t mean much to eyeballs though.

Eckart-Young-Mirsky just relates to approximation by low rank matrices, and it says that the error is best in terms of the operator norm, i.e. the action of the approximation is closest.

When you’re trying to compress an image you’re trying to optimize something quite different, so it is actually not too surprising.

Re: Image Compression with Singular Value Decomposition

#25

Post by foooobaba »

ntr-- wrote: post #21

I worked on a very interesting project aligning point clouds using SVD, for a pair of point clouds of the same scene that are not aligned: - select 3+ pairs of matching points in each cloud (tops of trees, edges of a building etc) - calculate the vector to the centroid of each cloud - use SVD to calculate the rotation that gives a minimum distance when applied from the source to the target - translate and rotate the…

This is cool, I briefly read through the paper, one thing I’m curious of is how hard it would be to add ability to do scale transformation (eg zoom in/zoom out) in addition to translation and rotational transformations. Would it be as simple as just adding a scale factor to the optimization objective and rework a bit of the math?

Re: Image Compression with Singular Value Decomposition

#26

Post by nighthawk454 »

foooobaba wrote: post #25
ntr-- wrote: post #21

I worked on a very interesting project aligning point clouds using SVD, for a pair of point clouds of the same scene that are not aligned: - select 3+ pairs of matching points in each cloud (tops of trees, edges of a building etc) - calculate the vector to the centroid of each cloud - use SVD to calculate the rotation that gives a minimum distance when applied from the source to the target - translate and rotate the…

This is cool, I briefly read through the paper, one thing I’m curious of is how hard it would be to add ability to do scale transformation (eg zoom in/zoom out) in addition to translation and rotational transformations. Would it be as simple as just adding a scale factor to the optimization objective and rework a bit of the math?

I think you're looking for the Procrustes transform, which uses SVD to optimize a minimal transform for rotation, translation, _and_ scale.

https://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem

Re: Image Compression with Singular Value Decomposition

#27

Post by foooobaba »

nighthawk454 wrote: post #26
foooobaba wrote: post #25

Earlier quoted context omitted.

This is cool, I briefly read through the paper, one thing I’m curious of is how hard it would be to add ability to do scale transformation (eg zoom in/zoom out) in addition to translation and rotational transformations. Would it be as simple as just adding a scale factor to the optimization objective and rework a bit of the math?

I think you're looking for the Procrustes transform, which uses SVD to optimize a minimal transform for rotation, translation, _and_ scale. https://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem

Wow, yes this looks like it will do the job!

Re: Image Compression with Singular Value Decomposition

#30

Post by chpatrick »

foooobaba wrote: post #25
ntr-- wrote: post #21

I worked on a very interesting project aligning point clouds using SVD, for a pair of point clouds of the same scene that are not aligned: - select 3+ pairs of matching points in each cloud (tops of trees, edges of a building etc) - calculate the vector to the centroid of each cloud - use SVD to calculate the rotation that gives a minimum distance when applied from the source to the target - translate and rotate the…

This is cool, I briefly read through the paper, one thing I’m curious of is how hard it would be to add ability to do scale transformation (eg zoom in/zoom out) in addition to translation and rotational transformations. Would it be as simple as just adding a scale factor to the optimization objective and rework a bit of the math?

https://web.stanford.edu/class/cs273/refs/umeyama.pdf
Post reply on HN