Lossy or Lossless Algorithm?

Kinimod

Solid State Member
Messages
19
Location
United Kingdom
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. :ermm:
 

root

Site Team
Staff member
Messages
8,181
Location
UK
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.
 
Top