Searching \ for 'Image Compression Algorithm' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=image+compression
Search entire site for: 'Image Compression Algorithm'.

Truncated match.
PICList Thread
'Image Compression Algorithm'
2000\04\24@122532 by Andrew Seddon

picon face
<x-flowed>Hi, I was wondering if one of you PIC programming gurus could help me. I
realise it`s a pretty simple problem but I can`t seem to crack it. I have
written a few different algorithms that should work but all seem to produce
errors. Anyway here`s the problem. What I need to do is compress a B/W
image. I am planning to write it into memory as a sequence of 8 bit numbers
each representing a number of black and white pixels alternating. I.e

10 250 0 250 15 17

which would mean 10 white, 500 black, 15 white, 17 black.

This method was suggested a while back and it seems like a good idea. I am
writing in C2C so some sort of C pseudo code would be really helpfull.

BTW, my memory access is sequential so I can`t use any complicated algo`s. I
thought maybe some sort of counter and a variable that keeps track of black
and white.

My e-mail is spam_OUTseddonaTakeThisOuTspamhotmail.com if you want any more info.

Thanks in advance for any help anybody can give me.

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

</x-flowed>

2000\04\24@202728 by Ian Wilkinson

flavicon
face
On Mon, 24 Apr 2000, Andrew Seddon wrote:
>Hi, I was wondering if one of you PIC programming gurus could help me. I
>realise it`s a pretty simple problem but I can`t seem to crack it. I have
>written a few different algorithms that should work but all seem to produce
>errors. Anyway here`s the problem. What I need to do is compress a B/W
>image. I am planning to write it into memory as a sequence of 8 bit numbers
>each representing a number of black and white pixels alternating. I.e
>
>10 250 0 250 15 17
>
>which would mean 10 white, 500 black, 15 white, 17 black.
>
>This method was suggested a while back and it seems like a good idea. I am
>writing in C2C so some sort of C pseudo code would be really helpfull.
>
>BTW, my memory access is sequential so I can`t use any complicated algo`s. I
>thought maybe some sort of counter and a variable that keeps track of black
>and white.
>

That seems over complex.
Have you thought instead how about 8 bit numbers, first bit of each represents
the colour, then the rest is a 7bit representation of how many pixels are that
colour.

So black=0, white=1
image has 3 black 10 white 1 black 250 white, 50 black would give this:
00000011 {3 black}
10001010 {10 white}
00000001 {1 black}
11111111 {127 white}
11111011 {123 white, making this row total 250}
00110010 {50 black}

This is more efficient than your suggested method, as you are only marking
changes and sections longer than 127 pixels, and not having a byte user even if
the colours did not change.

Assuming you are reading in the pixel colours on by one...
pseudo code would be something like this...
lastcol:=2
count:=0
do
col:=getCol()
if ((col==lastcol) and (count<127)) then
        count++
else
        if (lastcol<2) then output (count or (128 and col))
        count:=1
        lastcol:=col
endif
loop until eof

This should be easy to follow except maybe the
if lastcol<2 then output (count or (128 and col))
This line will output (what ever your output device is, memory, disk, serial
port what ever, it does not matter), the count, now if the colour is white
(col=1) then this part (128 and col) will equal 128 as a boolean and of 128 and
1 should always equal 128, if the colour is black (col=0) then 128 and 0 is 0.
So this part, count or (128 and col), says add 128 to count if col=1 as a
boolean or of count and 128 will result in adding them.

You could just add the numbers, but I like boolean ops...

This should be easy to translate into code.

Just like your code this could actually make the image file bigger under some
instances, but I think it's more likely to produce better compression than
yours.  Also worth looking at is a GIF like compression that makes symbols from
the image and then matches the symbols to the rest of the image.  It does work,
I have the spec here somewhere and built my own compressor from it.

Ian.
--
Rule of Defactualization:
Information deteriorates upward through bureaucracies.

Uptime at 12:54am  up 3 days,  4:05,  2 users,

2000\04\25@121443 by Roland Andrag

flavicon
face
Ian:

> >10 250 0 250 15 17
> >
> >which would mean 10 white, 500 black, 15 white, 17 black.
> >

> That seems over complex.
> Have you thought instead how about 8 bit numbers, first bit of each
represents
> the colour, then the rest is a 7bit representation of how many pixels are
that
{Quote hidden}

even if
> the colours did not change.

Not so! Check the original sequence (10 white, 500 black, 15 white, 17
black) with your 1+7 bit encoding, and you will see that you need more bytes
than the simpler alternating algorythm.  You are looking in the right
direction though.  In general, simply alternating between colours when run
length encoding a black and white image is most efficient.  Depending on how
often the colour changes it may be better to use more or fewer bits at a
time (larger or smaller words).  For example, if the image changes colour on
average each 16 pixels, alternating colour after 4 bits would probably be a
good choice.  Very dependent on the image though.

Roland

2000\04\25@121450 by Andrew Seddon

picon face
<x-flowed>Well I am actually only going to be compressing line art and text, where
there are large patches of white with a few blocks of black in between.
Therefore RLE is a nice simple algo to use, especially as I am compressing
in real time as the data comes in. To decode the pattern I simply spurt the
data (in compressed form) out of a serial port and let some VB coding do the
rest. That`s the theory anyway, can only make it work in raw bitmap form at
the minute :-(.

Any more questions?


{Quote hidden}

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

</x-flowed>

2000\04\25@121454 by Andrew Seddon

picon face
<x-flowed>Thanks for the tips I am going to give your code a try now. Looks like it
should work as I am scanning mainly line art and text, therefore there are
large patches of colour.

Anyway going to go code it now see what happens. Will get back to the list
with any tips/code.


{Quote hidden}

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

</x-flowed>

2000\04\25@121507 by Octavio Nogueira

flavicon
face
>Just like your code this could actually make the image file bigger under
some
>instances, but I think it's more likely to produce better compression than
>yours.  Also worth looking at is a GIF like compression that makes symbols
from
>the image and then matches the symbols to the rest of the image.  It does
work,
>I have the spec here somewhere and built my own compressor from it.

Would you share your code and specs?
I need to compress a gray scale image.


Friendly Regards

Octavio Nogueira
===================================================
TakeThisOuTnogueiraEraseMEspamspam_OUTpropic2.com                  ICQ# 19841898
ProPic tools - low cost PIC programmer and emulator
http://www.propic2.com
===================================================

{Original Message removed}

2000\04\25@141802 by Andrew Seddon

picon face
<x-flowed>The image is mainly text with some line art. Thinking about it there is
probably not that many runs of white between the letters of text, however on
the blank white lines between their obviously will be. Maybe I should think
about having some sort of code for a white line?? I think one of my major
constraints at the minute is that I am compressing in real time as my 4mb
ram has to take the whole A4 page at 200dpi.

This means the main requirement of the algorithm is simplicity which Ian`s
seems to have. I mean a 50% compression would be fine, I`m not looking for
massive gains at the minute, just something that works before I have to hand
my project in!!!

I`ve even managed to muck up the coding of Ian`s suggestion!! Probably
something to do with my 34 seconds of sleep in the last few days.

Any suggestions appreciated..


{Quote hidden}

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

</x-flowed>

2000\04\25@143016 by Andrew Seddon

picon face
<x-flowed>Sure no problem.. I don`t know how usefull anything I come up with will be
for you tho as my image is strictly 1`s and 0`s. You`ll proably need
something a tad more complicated for greyscale.

But if it interests you here`s a little about the system I am using..

           SX52 Microcontroller(PIC like processor)
           CIS Sensor
           4mb ram
           19200 serial port
           Tracking the movement of the CIS with a mouse

At the moment they system is still a complete mess sprawled out on my desk
and the code wouldn`t make much sense at the minute. However I hope to have
something with compression working pretty soon and i`ll be happy to send you
the code. If the interest is there I can post it on the list. It`s a pretty
interesting project so I may make a web page. Who knows, go to get the
bugger working first!!





{Quote hidden}

>{Original Message removed}

2000\04\25@143850 by M. Adam Davis

flavicon
face
If it is text, and you are simply compressing a pre-determined page of it,
perhaps it would be worthwhile to look into saveing the text on the chip and
rendering from bitmaps when you need it.

-Adam

Andrew Seddon wrote:
{Quote hidden}

2000\04\25@150147 by Andrew Seddon

picon face
<x-flowed>Thanks for the suggestion but unfortunately I can`t really use it as there
could be anything on the page. It`s just that in most cases it will be text.
However I wonder if anybody has looked into text recognition with a PIC,
seems like quite an interesting idea.


{Quote hidden}

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

</x-flowed>

More... (looser matching)
- Last day of these posts
- In 2000 , 2001 only
- Today
- New search...