 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Jan Walzer <jan### [at] lzer net> wrote:
> You know, there does not exists something like the "best" compression ...
> There can't be an algorithm that compresses better in ALL cases than any other
algorithm you choose ...
However, one algorithm can compress in *average* better than another.
--
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> However, one algorithm can compress in *average* better than another.
define "average" ... as you probably know, there are different kind of messurements
...
If you think about the standard [ (x1+x2+x3)/3 ] average, then I wouldn't
swear on this for an infinite set of sources to compress ...
Maybe it _CAN_ be true for a countable, closed set ...
(as for all possible images, where it could be computable) but I'm still not sure
'bout this ...
....
BTW: After thinking a while, I came to the conclusion that your first
statement was not necessarily wrong...
It is of course possible, that one algorithm is worse for every case, than another ...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Wasn't it Jan Walzer who wrote:
>> However, one algorithm can compress in *average* better than another.
>define "average" ... as you probably know, there are different kind of
>messurements ...
>
>If you think about the standard [ (x1+x2+x3)/3 ] average, then I wouldn't
>swear on this for an infinite set of sources to compress ...
>
>Maybe it _CAN_ be true for a countable, closed set ...
>(as for all possible images, where it could be computable) but I'm still not
>sure 'bout this ...
For lossless compression, there are good reasons for believing that the
*overall* average compression should be none whatsoever.
Suppose we compressed all possible images of a given size and colour
depth losslessly. The number of different images would be
height*depth*colour-depth. If our compression is lossless, it must give
a different compressed result for each of the input image files, i.e.
height*depth*colour-depth different compressed files. For these output
files to all be different, their average length would need to be
height*depth*colour-depth bits - which is what we started with.
--
Mike Williams
Gentleman of Leisure
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
No-one said that a compression scheme should use just *one* compression
algorithm.
The simples case of using two algorithms is: First try compressing
with the compression algorithm, and if the result is bigger than the
original, just store the raw image.
This way some of the images will be smaller than the original and some
will be equal. None of the images will be larger than the original.
This way the overall average compression rate will be higher than 1.
--
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Warp" <war### [at] tagpovrayorg> wrote:
> No-one said that a compression scheme should use just *one* compression
> algorithm.
> The simples case of using two algorithms is: First try compressing
> with the compression algorithm, and if the result is bigger than the
> original, just store the raw image.
> This way some of the images will be smaller than the original and some
> will be equal. None of the images will be larger than the original.
> This way the overall average compression rate will be higher than 1.
nope !
you have to store at least one bit more (for every image), telling you which
of the both algorithms to use.
Of course, in practice you could tell this probably tell this from the filename
(*hey-idea*: why not store the whole image-data in the filename ? ;), but in theorie
there's nothing like an "filename". So these additional bits would make the
o-a-c-r at least 1.
Assuming, of course, we're speaking 'bout lossless compression ...
This all is coveres by the chapter about kolmogorov-complexity...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Wasn't it Warp who wrote:
> No-one said that a compression scheme should use just *one* compression
>algorithm.
> The simples case of using two algorithms is: First try compressing
>with the compression algorithm, and if the result is bigger than the
>original, just store the raw image.
> This way some of the images will be smaller than the original and some
>will be equal. None of the images will be larger than the original.
> This way the overall average compression rate will be higher than 1.
The logic still holds. The data plus the information telling you which
decoding system to use must span all possible images, so information
theory strongly suggests that on average you get no compression.
There are some people who dispute this reasoning. For example ZeoSyc
seem to be claiming that they have invented a lossless compression
algorithm that can compress random data by a factor of 100. Their
algorithm is currently secret, pending patent application.
--
Mike Williams
Gentleman of Leisure
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mike Williams <mik### [at] nospamplease> wrote:
> The logic still holds. The data plus the information telling you which
> decoding system to use must span all possible images, so information
> theory strongly suggests that on average you get no compression.
In fact, every image file has to contain at least the information about
its dimensions. Generally at least 4 bytes are used to define the dimensions
of the image.
Besides this, it usually contains information about the pixel depth (ie.
how many bits per pixel it has).
This means that taking every possible image (ie. every possible pixel
combination), on average you get a *bigger* file than the plain raw image.
The *only* way of getting an average of no compression is that we only
use fixed-sized images with fixed-sized pixel depth.
But in this case the size of the file itself is the piece of information we
need to know if the compression algorithm was used or if the image is raw:
If the size of the file is exactly what is needed to contain the raw image
data, then compression was not used. If the size of the file is smaller, then
compression was used.
In this case we get an average file size which is smaller than the original
file size.
> There are some people who dispute this reasoning. For example ZeoSyc
> seem to be claiming that they have invented a lossless compression
> algorithm that can compress random data by a factor of 100.
I think this is theoretically impossible, as shown in this thread.
Of course if they say that *some* images can be compressed by a factor of
100, then it's believable. However, it's nothing fancy: Just take a huge
image with one color and compress it with whatever algorithm you like. You
can easily get a compression factor of 100000:1 if you want.
--
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Warp" <war### [at] tagpovrayorg> wrote:
> Just take a huge image with one color and compress it with whatever
> algorithm you like. You can easily get a compression factor of
> 100000:1 if you want.
Heheh ... yes ... create a GIF file of 4096x4096, 2-Bit with one
color. Attach this on a mail, that goes to an Outlook user ... *g
He is lucky, if he doesn't use the preview-function ..
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <3c96337b@news.povray.org> , "Jan Walzer" <jan### [at] lzernet> wrote:
> Heheh ... yes ... create a GIF file of 4096x4096, 2-Bit with one
> color. Attach this on a mail, that goes to an Outlook user ... *g
>
> He is lucky, if he doesn't use the preview-function ..
A true color PNG image of the same size will work even better...
BTW, such a 1 bit GIF is about 11 KB and a 24 bit PNG about 78 KB, so it could
really work!
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> wrote:
> BTW, such a 1 bit GIF is about 11 KB and a 24 bit PNG about 78 KB, so it could
> really work!
I just tried to compress a 4096x4096 image to PNG with pngcrush (using its
brute force search for the best compression settings).
At 24 bits per pixel the image file is 58540 bytes long, and at 8 bits
per pixel it's 2131 bytes long.
(I really wonder why the 24-bit image is so big. Why not three times the
size of the 8-bit version?)
--
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
