Solved

compressing 8x8 pixels

Posted on 2003-11-29
14
521 Views
Last Modified: 2012-06-21
I am creating a particular type of file compression schema for a particular computer graphic application and I need some help. I have already designed the schema that I would like to use, but now I need to be able to compress small blocks of pixels (8x8 pixels) without retaining all the JPG headers. Optimally, I need to get instead of the 192 bytes (8x8 block of pixels before compression) something in the order of 15-20 bytes (10:1 compression).
Even more ideally, I would like to get *always* 20 bytes out of an 8x8 block of pixels, no matter what they look like.
Any idea on how to get the simpler code that does achieve this kind of real ration (~20 bytes to represent 64 pixels)?
0
Comment
Question by:franz1999
14 Comments
 
LVL 49

Expert Comment

by:DanRollins
ID: 9843973
Sure.  Use a lossy alogirithm.  Give up fidelity or resolution.

Just average the pixels.
Send a 2x2 block, where each pixel is 24bits (three bytes of RGB)
    2*2*3 = 12 bytes
on the other end, make each pixel into a 4x4 block to get back to the original size.

or discared some of the color information and use a 5+5+6 RGB so color info for each pixel is only 2bytes.  Then
    (2*2_*2 = 8 (2x2 block, averaged) on client make each block 4x4
or
    (4*4)*2 = 32 (4x4 block, averaged) on client make each block 2x2

or discard more of the color information, say 4+4+4 RGB 12bits = 1.5 bytes
    (4*4)*1.5 = 24 (4x4 block, averaged) on client make each block 2x2

-- Dan
0
 

Author Comment

by:franz1999
ID: 9844067
Thanks for yourideas Dan, but we went through those approaches before and we didn't like the results. We want to use JPG. Don't they always say JPG average ratio is 10:1?
Well the idea we have is to use JPG to squeeze 192 bytes (8x8x3) into about 20 bytes. What I am looking for here is some help on how to compress/decompress JPG without using all the headers usually necessary (for interchange JPGs).
The final data structure will be a tree of nodes and each node will have the following structure:
[ 6 bytes -- for position/tree info ] [ 15-20 bytes -- JPG for colors ] [ 15-20 bytes -- JPG for normal vectors ]
The thing I need help with is: how do I squeeze 192 bytes into 15-20? Even better can I make it in a way that it will be always 20 bytes?
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 9844597
LOL!  Maybe you can use magic!  

A file can be compressed in a 10:1 ratio when it is LARGE because then duplicated information can be replaced with table-lookup items.  Tiny images such as 8x8 cannot be compressed 10:1 because there is no way to find long strings of duplicated information to replace.

-- Dan
0
 

Author Comment

by:franz1999
ID: 9844609
When you say so, Dan, are you being serious?
To my knowledge the way JPG works is by using Discrete Cosine Transform, and that should work no matter if you have a large or a small image, shouldn't it?
I might be naive here but I am really looking for such a solution and I believe it can be done, I just don't know how...

0
 
LVL 49

Expert Comment

by:DanRollins
ID: 9844903
I'm not kidding... I think you must be!  

Whether it is LZW or huffman lookup tables or mathematical operations, such a DTC or fractals, *all* compression techniques take advantage of redundancy.  In small images, all you have is the original 'starting point' -- you don't have any additional 'similar' data.  Thus, you can't get rid of that non-existant additional data!

A simple example:
Image that you have a 1-pixel image.  You can encode it "perfectly" with three byte, or use a lossy encoding to save it as 2 bytes (6-5-5 RGB) or even one byte (3-3-2 RGB) -- VERY lossy).

But you want to wave a magic JPG wand over that 1-pixel bitmap.  
Do you think you can possibly get it down to less than three (or maybe two bytes)?  If you think you will get a 20:1 ratio on that 1-pixel image, then you are living in some mystical dreamland where you can send 2.1 bits of data and magically recreate 24 bit of image data.  It aint-a-gunna-happen!  

Now, keep imagining.  If you have a 2-pixel image, it's source data is 6 bytes.  Best case scenario: If both pixesl are the same, you would need some way to indicate that (say,  a 1-byte code) plus the color data for one pixel.  So with lossy 6-5-5 output, you could use 2 bytes (color data)+ 1 byte (flag indicating repeat)= 3 bytes.  So in this rare case, you could achive 6:3 = 2:1 compression.

You can keep going until you get to an 4x4 block:  Source color data is  16x3= 48 bytes.  If all of the pixels are the same you could actually achieve a 48:3 = 16:1 ratio.  In the second-best case - where the top half of the block is one color and the bottom half is another, you are down to a 48:6 = 8:1 ratio.  Even in these two rare cases, you are not getting close to the 20:1 target.

-- Dan
0
 

Author Comment

by:franz1999
ID: 9845222
Dan, what you are saying make sense to me, but let me tell you what I did understand about JPG... I might be totally wrong and you could help me here.
Looking at a book on compression I saw that the DCT uses 64 grayscale predefined blocks (each block is 8x8) and it simply calculates coefficients that need to be multiplied by those blocks so that adding all the factors you get to something as similar as possible to the original block 8x8.
Example: if you have an 8x8 block with all pixels the same color (say blue), then all you need to do is to take the block with all pixels the same intensity and simply multiply it by "blue". A little more interesting example is the case in which the top half of the 8x8 block is, say, yellow, while the bottom half is , say, blue. then you will need to multiply the 8x8 grayscale block with the top half black, by the color yellow and add it to the 8x8 grayscale block with the bttom half black, multiplied by blue.
As you can see the idea is to bring around only these coefficients. If the 8x8 block is not too noisy, then the number of coefficients to be recorded is not too high (and anyway JPG throw away high frequencies --> lossy) and you can achieve a lot of compression, no matter how big is the image.
About your examples, if you have an image 1x1 or 2x2 or even 4x4, JPG will transform it into an 8x8 (size of the smaller block that can be used for compression).

-- Franz
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 9846662
That sounds about right.  So now all you need to do is send a grayscale image of the 64 pixels along with the coefficient data that will transform them into colors.  If you use run-length-limiting and/or huffman compression, and if you limit yourself to 8bbp sampling, you can sometimes get the grayscale block down to just a few bytes, but in most intermediate cases, and *all* complex cases, that 64-bytes of grayscale *alone* will exceed your targetted 20-byte max!  So where are you going to put the coefficient data? .... Maybe you can send it via mental telepathy.

    http://www.wotsit.org/search.asp?page=5&s=graphics
provides some useful links.  this one:
    http://www.wotsit.org/download.asp?f=jpeg
contains a zip file with source code and it contains jpgalgo.txt with a text description of the algorithm.  A more complete descrtipion of the algorithm is here:
    http://www.wotsit.org/download.asp?f=jpeg_c

0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 

Author Comment

by:franz1999
ID: 9846710
First of all this is your 4th comment in a row in which you seem to enjoy making fun of my ideas. I find that highly unprofessional.
If I already knew perfectly about compression I would probably not be here what do you think? So if you know more than me either explain me or not, but please DO NOT make fun of me and my ideas.

Second: the grayscale patterns are WELL KNOWN and do not need to be sent anywhere. If you ever opened a book on compression (ie: Introduction to Data Compression by Khalid Sayood -- page: 386) you will find that the basis matrices for the DCT are 64 well known grayscale patterns.

Is there anybody out there that knows more about JPG and can help me understanding if what I want to do is feasible or not. Thanks

--FG
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 9847349
I apologize if it sounds like I was making fun of you.  I was attempting to describe, in the clearest possible way, that it is *not* possible to get 20:1 compression on small bitmaps, such as 8x8.  It is not feasible.

-- Dan
0
 

Author Comment

by:franz1999
ID: 9870817
Using JPEGLIB I reach a compression of an 8x8 image to a variable length (depending on the image) that goes from 7 to 50 bytes.
0
 

Author Comment

by:franz1999
ID: 9870821
...which is equivalent to 20:1 -- 4:1
i am glad Dan was wrong.
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 9872947
LOL!
If the 8x8 bolock is all the same color, you can easily compress it (jpeg or roll-your-own codec) 192:4 = 48:1 (a simple extrapolation from the 4x4 example I gave).  If each of the 64 pixels is a different color, you will probably get, at best, a 1:1 compression.

I'm glad we had this little chat.

-- Dan
0
 
LVL 9

Expert Comment

by:tinchos
ID: 10286229
No comment has been added lately, so it's time to clean up this TA.
I will leave the following recommendation for this question in the Cleanup topic area:

PAQ with points refunded

Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Tinchos
EE Cleanup Volunteer
0
 

Accepted Solution

by:
SpazMODic earned 0 total points
ID: 10347366
PAQed, with points refunded (150)

SpazMODic
EE Moderator
0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now