4 ms·
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 ref
by ilaksh 13y ago
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.
- pit 13y agoThis is a Huffman table, right? I'm pretty sure this is how MP3s work.
- _delirium 13y agoI 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.
- ilaksh 13y agoWhy do you suggest that this would only work for photographs in one narrow domain?
- _delirium 13y agoI 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.
- phillmv 13y agoWell, 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 http://en.wikipedia.org/wiki/Huffman_coding for a simple intro.
- ilaksh 13y agoI 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.
- bratao 13y agoThis look like a "Vector quantization" with a precalculated table. (I have absolutely no video/compression background, someone correct me please)
- jl6 13y agoThe 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.
- lmm 13y agoI 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.
- orkoden 13y agoLenPEG actually does just that. http://www.dangermouse.net/esoteric/lenpeg.html http://www.dangermouse.net/esoteric/lenpeg.html