Go Back   Computer Forums > General Computing > Programming
Click Here to Login
Join Computer forums Today


Reply
 
Thread Tools Search this Thread Display Modes
 
Old 10-27-2015, 12:51 PM   #1
Solid State Member
 
Join Date: Oct 2015
Location: United Kingdom
Posts: 19
Post 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.
__________________

Kinimod is offline   Reply With Quote
Old 11-06-2015, 09:00 AM   #2
Site Team
 
root's Avatar
 
Join Date: Mar 2004
Posts: 8,004
Default 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."
root is offline   Reply With Quote
Old 11-06-2015, 09:03 AM   #3
Fully Optimized
 
joedaman633's Avatar
 
Join Date: Apr 2012
Location: England, Birmingham
Posts: 1,812
Default 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
joedaman633 is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off



All times are GMT -5. The time now is 02:12 AM.


Powered by vBulletin® Version 3.8.8 Beta 4
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Search Engine Friendly URLs by vBSEO 3.6.0