Hacker News Reader

Comment by ilaksh | Hacker News Reader

If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I not use a large dictionary shared by the entire catalog and therefore get much smaller file sizes?

Maybe images could be encoded with reference to a common database we share that has the most repetitive data. So perhaps 10mb, 50mb or 100mb of common bits that the compression algorithm could reference. You would build this dictionary by analyzing many many images. Same type of approach could work for video.

View on HN

Well, if we're shipping a common database and you're maximizing transmission efficiency then yes of course.

In information theory, my understanding (which is quite limited) is that when we talk of bits transmitted we can think of it as "uniquely identifying from within the set of total possible messages". So, if you shipped the entire 10,000 image catalog "transmitting" an image from within that catalog would take you a mere, uh, let me count my fingers, 13 bits.

We could go one step further and find some way of hashing all the data together to remove any redundancies and so forth - but the problem alas is about defining arbitrary images :).

What you described tho is kind of what happens with all compression algorithms except on the "micro"/individual image level. You may already be aware but check out Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding for a simple intro.

I am aware that compression algorithms kind of work on this general idea of referencing common bits. Of course I am aware of that.

How do you read my question and interpret simply it as "lets send all of the images in full and then give their index and call it compression?"?? What I suggest is that we take a standard encoding technique like Huffman, or some modification, but rather than creating a table based on data in an individual image, build this code table by analyzing many, many images.

I have read the Wikipedia article on Huffman coding before. However, the details are not really important in regards to my point.

What I am suggesting is that rather than looking at just the bits in individual images and using them to construct a Huffman table or some other kind of reference, look at the bits on many, many images and create a larger reference table. And then of course you may need a local table for things in the image that don't quite correspond to the larger table.

Earlier compression techniques were much more constrained in terms of processing power, RAM, network connectivity etc. and so distributing and using a large table for compression was not practical. I am suggesting that someone who has knowledge of compression engineer a system where 10MB, 50MB, or 100MB of RAM is used and a large common bits file is transmitted, rather than starting with the idea that almost all of the data or all of the data has to be contained in one file. I am not suggesting that an existing compression algorithm could be translated directly into this general concept. I am suggesting an engineering effort starting with different constraints and trade-offs.

I thought about doing something like that for audio, but I think it gets really inefficient with higher sample rates because you end up with so little overlap.

Like this: imagine I've got an array of shorts representing audio data. If I've got two files with similar segments, I've saved one short:

[1, 2, 3, 2, 1, 2, 5] [7, 2, 3, 6, 8, 9, 3]

So I can say that [2, 3] is represented by a new value (z), and can shave a short off of both streams. Then what happens if a new stream comes along with no similarities:

[8, 2, 7, 1, 7, 3, 7]

...you still have to send each value.

Maybe I've just demonstrated that I don't know anything about compression, but I would be interested in working with you on this.

I think I would want to find an existing sparse autoencoder implementation, ideally a project already setup for encoding audio, and start from there. http://www.stanford.edu/class/cs294a/sparseAutoencoder.pdf

*shrug

Lots of different people on this forum, no offense was intended, and like all nerds I get excited when I get to share knowledge.

>How do you read my question and interpret simply it as "lets send all of the images in full and then give their index and call it compression?"??

Because it struck me as analogous, and yeah I'd call that compression - the message length for one is immensely improved.

Okay, so here's my admittedly piss poor understanding of most compression: you either find more intelligent ways to strip bits from the source in ways the consumer won't mind, or you find more intelligent ways to build reference tables given your problem domain.

I'm sure you know this, but the first one is why jpeg/various mpegs are successful: they have complex quantization models that eliminate gradients we won't notice or frequencies we can't hear.

The way you achieve better results is through building better models for how information in your problem domain is related. If we're compressing text and we know the language we can start referencing letter frequencies and index along that and so on.

The way this works in video to my knowledge is, amongst many other complicated things, they take NxN blocks of images and store only the deltas between Y numbers of frames.

So - perhaps you "image reference blob" could build a reference table for all 16x16 px blocks and transmit only the indices for them, and we're back at my original comment. But to my (again, please correct me) understanding those are kind of the only alternatives? Encoding and decoding is an interesting topic.

I very infrequently have to think in binary and I had perhaps too much fun counting to 10,000 on my fingers; my undergraduate was a long time ago and my knowledge on the topic sparse, so I'm interested in hearing more about it.

I don't think this helps. Are you thinking that what, certain 8x8 blocks of pixels appear in photos much more than others? I don't think that's true except for general cases like monochrome blocks or smooth gradients, and you don't need a dictionary to help compress those.

The space of possible JPEGs is vast. You might find that there is less commonality between any given JPEGs than you expect, even considering a corpus of billions, and even when most JPEGs are of similar subjects.

LenPEG actually does just that.

http://www.dangermouse.net/esoteric/lenpeg.html

This look like a "Vector quantization" with a precalculated table. (I have absolutely no video/compression background, someone correct me please)

This is a Huffman table, right? I'm pretty sure this is how MP3s work.

I read it as just being a suggestion (which is not that uncommon) to use inter-file common characteristics to optimize for the common case, at least within a certain context.

JPEG is designed to compress any image. But imagine a new algorithm, gJPEG, which is only designed to compress photographs of grass. And furthermore, you get 100MB of raw buffer space in the executable to store some precomputed data that would be useful to gJPEG doing its work. It's quite possible you could significantly improve on the general performance by factoring out some data that's common to typical grass photographs, so that data could be stored once-and-for-all in the decoder and then omitted from each of your (presumably) billions of individual grass photographs. On the other hand, it's pretty tricky to make it work, so you might not be able to do such a thing effectively.

Why do you suggest that this would only work for photographs in one narrow domain?

I read the proposal as intending to take advantage of similarities among photographs in a particular domain. Lacking such similarity, you're back to the general photo-compression problem.

Reply on news.ycombinator.com