Computer Forums Lossy or Lossless Algorithm?
 Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 10-27-2015, 11:51 AM #1 Solid State Member   Join Date: Oct 2015 Location: United Kingdom Posts: 19 Lossy or Lossless Algorithm? Hello everyone, I'm doing past papers for my computing as I have an assessment tomorrow. When going through a past paper I came across an algorithm and it asks me to determine whether this algorithm is performing a lossy or lossless compression of images. Here's the algorithm: SET pixelPrev TO " " SET runLength TO 0 SET counter to 0 REPEAT RECEIVE pixelColour[counter] FROM (INTEGER)file1 IF pixelPrev ≠ pixelColour[counter] THEN SEND pixelColour[counter] TO file2 SEND runLength TO file2 SET pixelPrev TO pixelColour[counter] SET runLength TO 0 END IF SET counter TO counter + 1 SET runLength TO runLength + 1 END IF UNTIL end of file1 I can't figure it out. I was wondering if someone could explain this to me. __________________
 11-06-2015, 08:00 AM #2 Site Team     Join Date: Mar 2004 Posts: 7,872 Re: Lossy or Lossless Algorithm? I believe that the algorithm is lossless, as literally no data is lost. lets take it line by line. (we'll imagine that this is a picture file say a bit map, a picture of a white table cloth for example) - so it's mostly a sea of white, but may have a few imperfections, like dust on it. if you look at each pixel it'd go, Code: ```w w w b w w w w w w w w b w w w w w w w w w w w w w w w w w w w``` where w is white pixels in the picture, and b is a black smudge on the table cloth. Code: ```SET pixelPrev TO " " SET runLength TO 0 SET counter to 0``` that's just clearing everything out, making sure that there are no data in the buffers, that would show as artifacts in your picture. Code: `REPEAT` here is the start of a loop Code: `RECEIVE pixelColour[counter] FROM (INTEGER)file1` we take a pixel from the file, (in the example this would be w) Code: `IF pixelPrev ≠ pixelColour[counter] THEN` if this the same as the data in pixelprev? - no because that's empty Code: `SEND pixelColour[counter] TO file2` so we record that pixel value. Code: `SEND runLength TO file2` and a position Code: `SET pixelPrev TO pixelColour[counter]` then save that value.to our register. Code: ```SET runLength TO 0 END IF``` and increment various counters. Code: ```SET counter TO counter + 1 SET runLength TO runLength + 1 END IF UNTIL end of file1``` and repeat... Code: ```REPEAT RECEIVE pixelColour[counter] FROM (INTEGER)file1``` Get that pixel value (second w) Code: `IF pixelPrev ≠ pixelColour[counter] THEN` in this case, the value w is the same as the previous value. s now nothing is recorded and the counters are incremented Code: ```SET counter TO counter + 1 SET runLength TO runLength + 1 END IF UNTIL end of file1``` and repeat... ...repeat 3 will also get pixel value w which is the same as pixel value 1 and pixel value 2 so nothing is recorded Code: ```REPEAT RECEIVE pixelColour[counter] FROM (INTEGER)file1 IF pixelPrev ≠ pixelColour[counter] THEN``` well now the pixel value is b, so not the same as w Code: `SEND pixelColour[counter] TO file2` so we record the new pixel value. and the position that those pixel colours start to run on that line from. Code: ```SEND runLength TO file2 SET pixelPrev TO pixelColour[counter] SET runLength TO 0 END IF``` now.... Code: ```w w w b w w w w w w w w b w w w w w w w w w w w w w w w w w w w``` is reduced to Code: ```w1 b4 w5 w1 b5 w6 w1 w1``` 32 bytes compressed into 16, (a 50 percent data reduction) - file headers would need to be formed as well though. your compressed file is a new format. Code: ```L8 w1 b4 w5 w1 b5 w6 w1 w1``` so the total file would be something like that, where L8 says that each raster line is 8 pixels long. - so now the file is 18bytes it's not quite half compression, but you get the picture... its lossless because I can reconstruct the exact original by reading the file. L8 (lines are 8 pixels wide) w1 starts pixel 1 with white b4 there is a black at pixels 4, w5 white again at pixel five, there is nothing else, and I know it should be 8 lines long, so line 1 - wwwbwwww w1 b5 w6 (white from 1-4 then black at 5, then white from 6 line 2 - wwwwbwww w1 all white wwwwwwww w1 all white wwwwwwww A lossy compression is one like jpg, you notice when you zoom in the edges are fuzzy. the end result for a jpeg picture which was a sea of white with a few black pixels would take. [code]w w w b w w w w w w w w b w w w w w w w w w w w w w w w w w w w[code] and change it so something that said, loads of white, a grey smudge and loads of white. [code]L8 w w g5 w6 w w[code] 32 bytes into ten bytes, complete with header information. an extra almost 20% of compression but you can clearly see that data has been lost. For viewing photos it mostly doesn't matter.... (and bear in mind an ipad takes photos at 3264 x 2448 (and printed at 72 pixels per inch would be 45" x 34" (that's a 56" diagonal) When we view them on a 10" screen, they are so reduced that we really don't notice (read our eyes cannot possible perceive!) the reduction in quality from real life caused by the missing information. __________________ __________________ I didn’t fight my way to the top of the food chain to be a vegetarian… Im sick of people saying 'dont waste paper'. If trees wanted to live, they'd all carry guns. "The inherent vice of capitalism is the unequal sharing of blessings; The inherent vice of socialism is the equal sharing of miseries."
 11-06-2015, 08:03 AM #3 Fully Optimized   Join Date: Apr 2012 Location: England, Birmingham Posts: 1,552 Re: Lossy or Lossless Algorithm? root, that's an awesome explanation. __________________ Athlon II x4 645 || 1TB 7200rpm HDD || EVGA GTX 650Ti OC || 8GB DDR3 RAM || Windows 7 Home x64 i5 4210M || 500GB Samsung EVO 850 SSD || GeForce 825M || 16GB DDR3 RAM || Windows 10 x64

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

All times are GMT -5. The time now is 05:54 AM.