# Lossy or Lossless Algorithm?

#### Kinimod

##### Solid State Member
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
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.

#### root

##### Site Team
Staff member
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
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
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.``````

#### cb600fshornet

##### Fully Optimized
root, that's an awesome explanation.

Replies
8
Views
1K
Replies
0
Views
530
Replies
2
Views
5K
Replies
2
Views
1K
Replies
6
Views
1K