So I was on the ride back from my grandfathers funeral, and I was thinking of different types of tech I could improve on. One thing that came to mind was image compression. Then It dawned on me. What if you could use a single number and a ratio to compress a whole bitmap.
my theory on how this would work can be best explained in pseudo code.
well here I go:
Code:
allBits = 0
bits = imageData("example.png")
addedBits = []
#get the data of the bits in a common form
for (bit in bits){
allBits += bit
addedBits.append(allbits)
}
#get a common ratio to work with
ratio = findRatioFromList(addedBits)
#print the compressed data
print("starting number: "+allbits)
print("ratio:"+ratio)
Anyone have any opinions on how I could make this better, or if i made any mistakes. Please leave feedback
I could rant about Shannon Information Theory all day, but without my audience having a solid theoretical background, the most helpful thing I could say is that you can't use fewer bits to encode something than there are bits of entropy in the uncompressed thing. I don't understand what you're trying to do (and what you mean by a ratio) from the given pseudocode, which would allow me to more precisely refute your proposal.
Well the "ratio" is a ratio that all the numbers in the addedBits array share. so if the array [2,1] then that ratio would be 1/2 or if it were [5,10,20] 2/1. This can then be used to take the added number and calculate the next number and subtract it from the added number leaving the number that would be the next step in the data.
But if you have a single ratio for the entire image, then you can only encode images that follow some very strict pattern, unless I'm still misunderstanding your design.
If you haven't already, look up the tech behind
JPEGmini. It's super cool and I use their software before uploading my photographs on my website - and sometimes other services.
heres an example:
here's a sequence of numbers:
0,1,1,3
when added in order you get:
1,2,4
now they have a common ratio of 2/1 and final number to work with is 4
once you take the inverse of the common ratio, 1/2, and aply it until you reach 0 you get the number sequence:
4,2,1
now find the difference between the numbers in order and you get:
0,1,1,3
wha la!
now i do realize this only works with pictures with a patern but it could still be useful
spud2451 wrote:
So I was on the ride back from my grandfathers funeral, and I was thinking of different types of tech I could improve on. One thing that came to mind was image compression. Then It dawned on me. What if you could use a single number and a ratio to compress a whole bitmap.
People need to deal with grief in their own way I guess.
Oh no, I am sorry to hear that... With regards to your post, yes, it only seems to work with pictures that have a common pattern. This:
1,7,5,1
8,13,14
=35
Does not seem to work...
But perhaps this could be useful for something else...
Well they all do have common ratio or equation that would work right? So in theory it could be applied to anything, the trick is finding the right equation/ratio.
spud2451 wrote:
Well they all do have common ratio or equation that would work right? So in theory it could be applied to anything, the trick is finding the right equation/ratio.
Yes, I suppose it could in theory, but finding the ratio between 8,13,14 could be quite challenging. 
Good find, though! I imagine that this is useful, perhaps we just don't know what it is yet!
i think there's a whole number theory called "Number sequence" that could be applied to this. I may be wrong though.
spud2451 wrote:
Well they all do have common ratio or equation that would work right? So in theory it could be applied to anything, the trick is finding the right equation/ratio.
This sounds like arithmetic coding: https://en.wikipedia.org/wiki/Arithmetic_coding
It sounds a bit like statistical regression stuff, where you try to find an equation that matches the data... but I've not heard of some kind of algorithm that can automatically find an equation that matches absolutely any possible combination of numbers. And I figure it's even possible that such an equation, in some cases, could take more space than the data it's trying to encode.
If the data took on a limited number of possible patterns, that might be different. Lossless audio codecs like FLAC use a principle like that, if I understand them correctly. Raw audio data takes on the form of a wave and therefore usually follows a fairly predictable mathematical pattern, and those codecs take advantage of this and encode the audio as essentially a list of formulas representing a number of samples each, or something like that.
Very nice connection travis. I see your point on how it could take more space to encode it than the image its self (in that cas eyou migh as well do somthing like "0+1+1+3"). But who knows!
I'm pretty sure this becomes very lossy in all but trivial cases, unless I'm misunderstanding what you're trying to explain here. It looks to me like you're reducing a list of integers to a single integer, implying the magnitude of the output is related to that of the input in some computable fashion; it sounds like arithmetic coding to me.
It may be that there are multiple solutions to any given 'compressed' form here, in which case it's a lossy reduction function unless you can constrain the unencoded values with some out-of-band information.
Travis wrote:
If the data took on a limited number of possible patterns, that might be different. Lossless audio codecs like FLAC use a principle like that, if I understand them correctly. Raw audio data takes on the form of a wave and therefore usually follows a fairly predictable mathematical pattern, and those codecs take advantage of this and encode the audio as essentially a list of formulas representing a number of samples each, or something like that.
What you describe seems closer to what typical lossy codecs do, which involves inverse transforms (usually an inverse DCT) to decompose a signal into a set of frequency components. They then apply perceptual algorithms to select the most "important" components and discard the rest (MP3, for example, always takes 13 frequency bands per block IIRC).
FLAC does something somewhat similar, but becomes lossless by virtue of coding residuals from a predicted signal. Each block is assigned a predictor which may fit one of several models such as a constant value (pure DC) or a FIR predictor of up to something like order 11. To decode a signal then, the decoder adds a residual to each sample which is provided in the bitstream. Residuals are delta-coded such that values with smaller magnitude require fewer bits to encode, so a more accurate predictor has smaller encoded residuals.
(I've been programming audio codecs lately. We can observe from the above properties that it's very difficult to do most lossy codecs without floating-point arithmetic (the DCT is not a simple operation), whereas FLAC can be decoded with only integer operations with relative ease.)
Tari wrote:
What you describe seems closer to what typical lossy codecs do, which involves inverse transforms (usually an inverse DCT) to decompose a signal into a set of frequency components. They then apply perceptual algorithms to select the most "important" components and discard the rest (MP3, for example, always takes 13 frequency bands per block IIRC).
FLAC does something somewhat similar, but becomes lossless by virtue of coding residuals from a predicted signal. Each block is assigned a predictor which may fit one of several models such as a constant value (pure DC) or a FIR predictor of up to something like order 11. To decode a signal then, the decoder adds a residual to each sample which is provided in the bitstream. Residuals are delta-coded such that values with smaller magnitude require fewer bits to encode, so a more accurate predictor has smaller encoded residuals.
Ah, I remember the residuals thing with FLAC; I just never completely remembered/understood that part. Are they basically the difference between the values the encoding function produces and the actual original samples? (That is, as if someone were doing statistical regressions on a calc with data that almost but not quite matches a model, and then instead of storing the raw input data points, storing the function and the differences between the function's y value and the original data y at each x of the original data.)
I also wasn't aware that lossy codecs did the same thing, without residuals. That's interesting.
Yeah, it's a simple difference (things get a little fancier with stereo encodings). Let S(x) be the decoded sample x, P be a predictor function and R be a function yielding residuals: S(x) = P(x) + R(x).
There are a couple joint stereo encodings. For example with 'Left-Side' encoding, S(x) is the left channel and if we define f'(x) as a sample function for the right channel, S'(x) = S(x) + P'(x) + R'(x).
JoeYoung wrote:
spud2451 wrote:
So I was on the ride back from my grandfathers funeral
People need to deal with grief in their own way I guess.
Yeah, IKR. I was wondering about that myself.
