Post by thread:Image Compression Algorithm

<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_OUTseddonaTakeThisOuThotmail.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>

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,

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}> 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. 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

<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}>From: "alok dube" <.....alokdubeKILLspam@spam@hotmail.com> >To: seddonaKILLspamHOTMAIL.COM >Subject: Re: Image Compression Algorithm >Date: Tue, 25 Apr 2000 12:22:13 IST > >how the hell do u plan to decode the pattern?.. i may have a very random >image pattern.. then ur algo doesnt make too much sense.. >Alok > > > >>From: Andrew Seddon <.....seddonaKILLspam.....HOTMAIL.COM> >>Reply-To: pic microcontroller discussion list <EraseMEPICLISTspam_OUTTakeThisOuTMITVMA.MIT.EDU> >>To: PICLISTspam_OUTMITVMA.MIT.EDU >>Subject: Image Compression Algorithm >>Date: Mon, 24 Apr 2000 09:10:16 PDT >> >>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@seddonaKILLspamhotmail.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>

<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}>From: Ian Wilkinson <KILLspamwilkoKILLspamSGTWILKO.F9.CO.UK> >Reply-To: pic microcontroller discussion list <RemoveMEPICLISTTakeThisOuTMITVMA.MIT.EDU> >To: spamBeGonePICLISTspamBeGoneMITVMA.MIT.EDU >Subject: Re: Image Compression Algorithm >Date: Tue, 25 Apr 2000 00:54:24 +0100 > >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, ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com </x-flowed>

<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}>From: Roland Andrag <RemoveMErandragTakeThisOuTICON.CO.ZA> >Reply-To: pic microcontroller discussion list <PICLISTEraseME.....MITVMA.MIT.EDU> >To: EraseMEPICLISTMITVMA.MIT.EDU >Subject: Re: Image Compression Algorithm >Date: Tue, 25 Apr 2000 10:16:29 +0200 > >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 > > 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. > >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 ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com </x-flowed>

<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}>From: Octavio Nogueira <RemoveMEnogueiraEraseMEEraseMEAJATO.COM.BR> >Reply-To: pic microcontroller discussion list <RemoveMEPICLISTspam_OUTKILLspamMITVMA.MIT.EDU> >To: RemoveMEPICLISTTakeThisOuTspamMITVMA.MIT.EDU >Subject: Re: Image Compression Algorithm >Date: Tue, 25 Apr 2000 07:36:48 -0300 > > >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 >=================================================== >EraseMEnogueiraspamspamBeGonepropic2.com ICQ# 19841898 >ProPic tools - low cost PIC programmer and emulator >http://www.propic2.com >=================================================== > >{Original Message removed}

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}> > 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.. > > >From: Roland Andrag <RemoveMErandragKILLspamICON.CO.ZA> > >Reply-To: pic microcontroller discussion list <PICLISTSTOPspamspam_OUTMITVMA.MIT.EDU> > >To: spamBeGonePICLISTSTOPspamEraseMEMITVMA.MIT.EDU > >Subject: Re: Image Compression Algorithm > >Date: Tue, 25 Apr 2000 10:16:29 +0200 > > > >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 > > > 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. > > > >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 > > ________________________________________________________________________ > Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

<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}>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: > > > > 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.. > > > ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com </x-flowed>