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

Show HN: Trigrad, a novel image compression with interesting results

ruarai.github.io

Post reply on HN
Print view View original

11–20 of 69 posts

Re: Show HN: Trigrad, a novel image compression with interesting results

#11

Post by ezdiy »

ruarai wrote: post #9
ekianjo wrote: post #5

Earlier quoted context omitted.

How does it compare in quality/size vs PNG ? How about using examples where JPG are traditionally bad at, such as pictures with dark gradients leading to blocky artifacts? Would that process be more efficient there?

It's not very comparable to PNG, since they're designed for different types of imagery. I know currently Trigrad cannot handle text at all. In regards to your other comment, it's currently definitely worse than JPEG for vector imagery. However, it handles gradients amazingly. A full colour gradient such as [0] can be made a tenth of the size since only ~500 samples are really needed. [0] http://i.imgur.com/QzW0z2O.pn…

Love how the algorithm is simple compared to iDCT based ones, very good job!

> No text at all

Or indeed anything which poorly maps to gradients. For this I'm thinking about instead of storing pixel values per sample vertex, store only dct coefficient(s) per each tri - result of which gets texture-like-mapped to the tri surface. Think JPEG instead of 8x8 quads using variably sized tris.

JPEG artifacts would then be much more fine grained around edges.

EDIT: It would not need to be as complex as full DCT because a lot of information is carried through tri shape/positioning on edges. The idea is to have "library of various gradient shapes" to pick from, not full 8x8 DCT matrix capable of reconstituting 8x8 bitmap approximations.

Once again, thanks for inspiring implementation.

Re: Show HN: Trigrad, a novel image compression with interesting results

#12

Post by pjtr »

Since the order of the samples doesn't matter, could you sort them somehow so the Gzipped stream of samples can be compressed better? (E.g. sort the color index by component average, by red, by maximum component, ... and sort the point index by color.)

Have you tried struct-of-array (AAA...BBB...) instead of array-of-struct (ABABAB...) layouts?

Re: Show HN: Trigrad, a novel image compression with interesting results

#13

Post by slavik81 »

I really like the look at low sample rates, but the stems on the flowers look rather jaggy even with 100,000 samples.

It would be nice to have the original image for a more detailed comparison. As beautiful as the picture is, the depth-of-field effect makes comparison between the left and right sides of the image a little tricky.

Re: Show HN: Trigrad, a novel image compression with interesting results

#15

Post by ruarai »

pjtr wrote: post #12

Since the order of the samples doesn't matter, could you sort them somehow so the Gzipped stream of samples can be compressed better? (E.g. sort the color index by component average, by red, by maximum component, ... and sort the point index by color.) Have you tried struct-of-array (AAA...BBB...) instead of array-of-struct (ABABAB...) layouts?

I tried your struct-of-array idea, and that's produced an okay improvement ~1%.

Sorting them seems tough as the index of each value must match for each channel, so any sorting would have to occur beforehand. Except that is already sorted by x-y values, and my attempts otherwise have failed to produce results.

Re: Show HN: Trigrad, a novel image compression with interesting results

#17

Post by 1wd »

joshu wrote: post #14

Some more explanation about barycentric coordinate would be appreciated.

Barycentric coordinates are "weights" (u, v, w) that determine a point P on a triangle (A, B, C) by weighting the triangle corner points. You can calculate the cartesian coordinates of P = u * A + v * B + w * C.

Since the weights u+v+w = 1 you actually don't need all three: u = 1-v-w, so P = (1-v-w) * A + v * B + w * C = A + v * (B - A) + w * (C - A).

Re: Show HN: Trigrad, a novel image compression with interesting results

#18

Post by jacobolus »

a_e_k wrote: post #10

Garland and Heckbert had a nice algorithm for this sort of thing in their 1995 paper, "Fast Polygonal Approximation of Terrains and Height Fields." The paper is mainly devoted to height fields, obviously, but at the end they demonstrate that their algorithm is also effective at triangulating color images for Gouraud-shading as well. I'd be curious to know how this stacks up in terms of speed and quality. EDIT: Oh yes…

To the OP: There are also several other tools for scattered data approximation/interpolation developed in the last few decades, both mesh-based and mesh-free. Linear interpolation using barycentric coordinates on a triangulation is fast (and might be the most practical method for this particular use case), but nowhere near as good a result as you can get via other methods.

See e.g. http://scribblethink.org/Courses/ScatteredInterpolation/scat...

Re: Show HN: Trigrad, a novel image compression with interesting results

#19

Post by kobigurk »

This is the difference between someone who actually does something and academic work that claims to achieve something. This is half-done, but it WORKS and you can use it and understand it right now.

I had the opportunity to try and implement a "novel" algorithm for image downscaling. I contacted the authors - one replied that he can't reveal the source code, and the other didn't reply. So I went ahead and invested about 2 weeks implementing and optimizing it to the point where it worked - but the results were far from what we wanted. If they just supplied a demo program where I could see if it worked for our case, it would be much better.

Post reply on HN