UNIX and Linux Applications

Hi Everyone,

I am a Ph.D student working on some image processing tasks and I have run into an interesting problem that I thought someone on here might have an idea about. This paper discusses a method to compare two images based upon the amount they can be compressed. [edit] Sorry, since this is my first post, I can't post URLs. So search for;
ON THE CONTRIBUTION OF COMPRESSION TO VISUAL. PATTERN RECOGNITION. Gunther Heidemann

The formula is simply D_comp(I1, I2) = S(I1) + S(I2) - S(I12)

Basically, if I have two images, one.bmp (S(I1)) and two.bmp (S(I2)). If I compress each one, and also combine the two to make S(I12), and compress that, I can feed them into the formula and it tells me how similar they are. Sounds simple enough.

Then, in the description of the theory, it states that a large value for D_comp indicates that the two images are similar, and a value for zero is found when they're not similar. All good so far...(however I would have thought that if two images are identical, combining them would make D_comp closer to zero).

So I have implemented this as a quick test as follows;

Code:

cat one.bmp | gzip -c -9 > one_cat.gz
cat two.bmp | gzip -c -9 > two_cat.gz
cat one.bmp two.bmp | gzip -c -9 > bridges_cat.gz

so;

Code:

gzip -l one_cat.gz two_cat.gz bridges_cat.gz

gives me;

Code:

         compressed        uncompressed  ratio uncompressed_name
             937867             1440054  34.9% one_cat
             907797             1440054  37.0% two_cat
            1846241             2880108  35.9% bridges_cat
            3691905             5760216  35.9% (totals)

Therefore my D_comp value is 937867 + 907797 - 1846241 = -577

Note that this is a negative number, not mentioned in the paper, since I am guessing that there is an assumption that by combining two images S(I12), one would achieve a greater level of compression.

Here are the two images I have tried this on;
one.bmp = once again, I can't post the URL - brooklyn Bridge

two.bmp = once again, I can't post the URL - golden gate bridge

Since these were jpg files, I used image magik to convert them to BMP, so that they were the same byte size. Both images are 800x600 and as you can see from the gzip -l output, the uncompressed file sizes are the same.

So my question is, why would two files produce a smaller total amount of bytes when compressed, than when combined. I would have thought that the gzip algorithm would have been more efficient at compressing the joint image.

Also, when both images are the same;

Code:

cat one.bmp one.bmp | gzip -c -9 > same_cat.gz
gzip -l one_cat.gz same_cat.gz
         compressed        uncompressed  ratio uncompressed_name
             937867             1440054  34.9% one_cat
            1875794             2880108  34.9% same_cat
            2813661             4320162  34.9% (totals)

which results in a value of D_comp -60.

Appologies for the long post. Does anyone know why gzip might do this? Does it look normal? I was thinking it might be something to do with header information that it couldn't compress.

Kind regards,

Martin

gzip isn't suitable. gzip wouldn't know which bits mean what pixels. gzip might also find patterns you don't want, identical things in the wrong places of the image. It's also lossless, so an intensity difference of 1 matters just as much as an intensity difference of 255 as far as it's concerned. It really doesn't know what the picture looks like.

This paper can't have meant lossless compression, or any kind of general compression -- it must have meant some kind of lossy image compression like jpg which doesn't care if the pixels are bit-for-bit identical.

I don't think 'cat' is an appropriate way to combine the images, either.

I think what they're looking for is the resulting size of the image when saved with identical levels of lossy compression. S(I1) and S(I2) should be very similar. What S(I3) is would depend. How does the paper say to combine these images?

Hi Corona688,

The whole idea of compression for image retrieval is that it is a measure of entropy. If the data is completely random, then S(12) should be result in pretty much the same file size as S(1) and S(2), therefore D_comp -> 0 (i.e. D_comp converges to zero).

Your comments about a one DN value difference in a pixel may as well be a 255 difference is touched upon in the paper.

The paper does specifically describe the method in that it uses gzip 1.2.4 and that it uses the LZ77 lossless compression. It also states that the images are raw images, it doesn't elaborate further. I have taken that to mean that they are header-less images, so RGB images with 8bit colour depth converted using image magick.

I agree that cat isn't appropriate, however as a quick test I thought it would still work. It mentions that the images are combined 'as juxtaposition of pixel arrays I1 and I2'. I have taken this to mean appending the two images side by side. So I have tried this, and also one image followed by another.

Since there are lots of papers on this technique, unfortunately most referring back to this one for how it is implemented, I am sure the theory is sound. Of course I am aiming to test that for a few other situations, hence the research. I just think that I am missing some implementation subtly that isn't discussed in the paper. I am still convinced that it is the header.

If someone could explain why two files compressed individually would have a total file size less than if both of them were compressed together, then that would be great. As far as I am aware, that should not happen, even if they are completely random pieces of data.

Thank you

gzip is lossless compression. It has no concept of "pretty much the same".

And? The main issue I have with this is that gzip has no way of understanding which pixels are related to each other; all it has is the order the bytes come in. It looks for nearby repeats of bytes, and nearby repeats of patterns of bytes, and nearby repeats of patterns of patterns of bytes... Just cat-ing the files together places the patterns that should be compressed, if any, nearly as far from each other as possible.

I think they should be combined like this:

Code:

AAAA EEEE
BBBB FFFF
CCCC GGGG
DDDD HHHH
becomes

AEAEAEAE
BFBFBFBF
CGCGCGCG
DHDHDHDH

That places differences to left-and-right pixels closes to each other. If the images were perfectly identical, those repeats would be compressed. You could also try interleaving the columns instead.

You could also do image processing work like subtracting one image from the other, or multiplying them together, or various other things. This is where the real computational work happens, I think, not gzip. gzip would be a very rough-and-ready measuring stick at best, mostly blind to the similarities you want to measure. I'm not convinced. Finding a good way to shuffle and process the images to produce minimum entropy is pretty much the question here, the thing that makes it work, the part that does the actual detection of differences and they didn't bother to describe it. If you find a great way to do that you've already found a way to compare the images, and who cares whether gzip's involved. That could also result in lots of papers banging on the theory, trying to make it work.

I still think lossy image compression would work a whole lot better than a naive implementation with lossless byte-stream compression. Lossy image compression actually cares about spatial arrangement, unlike gzip, and jpg can be told how much niggling small changes should matter.

If they were perfectly random data, it probably wouldn't matter, but it is compressing somewhat -- how repetitive is your image? -- which can cause side-effects.

By the time gzip gets through the first image, it's built up a decent dictionary of small things to substitute for longer sequences; but this dictionary is little to no help compressing the second one -- minor differences are as good as total differences to lossless compression. So it has to ditch the useless entries individually as new ones replace them. This kind of churn reduces efficiency. If it knew in advance the data was going to change so drastically maybe it could've dumped its dictionary and started fresh.