Computer Forums Lossy or Lossless Algorithm?

 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: 8,096 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,824 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