Show HN: Trigrad, a novel image compression with interesting results • Hacker News Board

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

#21

Post by pjtr » Sat, Jul 04, 2015, 8:29 AM UTC

ruarai wrote: post #15

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.

I'm missing where they are sorted by x-y values.

I did a quick and dirty experiment: http://pastebin.com/NjZNRjw1

Seems about 30% smaller than before on http://i.imgur.com/5zwCEF5.png

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

#22

Post by return0 » Sat, Jul 04, 2015, 8:33 AM UTC

Congrats! but beware of Gavin Belson.

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

#23

Post by ruarai » Sat, Jul 04, 2015, 9:16 AM UTC

jacobolus wrote: post #18

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/Sc…

Not sure if that applies for my purposes, since I'm not actually using linear interpolation barycentric coordinates (I don't think that's possible). The barycentric coordinates supply the gradient within themselves.

I may have to read further, though. That's a lot of math.

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

#24

Post by ruarai » Sat, Jul 04, 2015, 9:24 AM UTC

rincewind wrote: post #20

Can you try it with the lenna benchmark image and post the results please?

Here's Lenna reconstructed after 30,000 samples. http://i.imgur.com/hlPonsO.png

The compressed data comes out to 303KB, which isn't that great. It's a pretty noisy image.

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

#25

Post by ruarai » Sat, Jul 04, 2015, 9:30 AM UTC

pjtr wrote: post #21

ruarai wrote: post #15

Earlier quoted context omitted.

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.

I'm missing where they are sorted by x-y values. I did a quick and dirty experiment: http://pastebin.com/NjZNRjw1 Seems about 30% smaller than before on http://i.imgur.com/5zwCEF5.png

Wow, that works pretty well. I was mistaken in thinking that either the Dictionary class or the process of sampling would sort them.

Mind if I merge that? Or you could submit a pull request. Either would be great!

Also, do you know of any resources for learning about how to optimise for gzip compression? Google is just telling me about compression for websites.

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

#26

Post by coolvision » Sat, Jul 04, 2015, 9:47 AM UTC

What about thresholding gradients (with adaptive threshold), storing resulting edges alongside (compressed with RLE f.ex.), and then blending it over the triangle gradients? It could remove some artifacts.

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

#27

Post by ruarai » Sat, Jul 04, 2015, 10:05 AM UTC

boterock wrote: post #16

haven't you tried applying the edge detection filter twice? i think this way the samples are taken not in the edge but before and after the edges, maybe it will end with a blurrier image but with less artifacts.

This doesn't seem to have any benefit unfortunately. It seems like the current approach already produces the before-after edge effect.

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

#28

Post by octatoan » Sat, Jul 04, 2015, 10:06 AM UTC

"Not really well enough to try to push onto people. Current results show that Trigrad can only beat something like JPEG with optimal conditions."

?

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

#29

Post by JoshTriplett » Sat, Jul 04, 2015, 10:06 AM UTC

Very impressive!

How might the final rendering look if it used some of the standard triangle shading techniques? Treat the sample points as coordinates in a mesh, assign colors to those coordinates based on what you sampled, then interpolate colors for the points between those coordinates using something like Gouraud or Phong shading (without the lighting). That might produce a satisfying result with fewer samples.

I wonder if this could be used as an image resizing mechanism? Take a large number of samples, then render the resulting image using those samples and a smaller or larger size. Or, generalizing further: turn the image into samples and associated colors, apply a transform to the sample coordinates, then render.

This also reminds me quite a bit of the algorithm used in http://research.microsoft.com/en-us/um/people/kopf/pixelart/... (for which, sadly, code is not available). I wonder if some of the techniques from there could improve the quality of the results with fewer samples?

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

#30

Post by JosephRedfern » Sat, Jul 04, 2015, 10:17 AM UTC

How are the sample points selected? I get that they're weighted according to edge intensity, but what kind of distribution are you using in cases where there is no edge?

EDIT: I've read the code - it seems to be using random sampling. Still not entirely sure how a point can be placed at a place with absolutely no Sobel response - maybe it can't, which would make sense. My question arose after looking at: https://i.imgur.com/9YHOtQ0.png and then https://i.imgur.com/XRF7mz4.png. It looks like samples have been placed in regions with no response, but perhaps my eyes just can't see the edges.