- Encode four Sayood images
(sinan.img, sena.img,
earth.img, omaha.img)
with k=4 to produce four amerDIF compressed
files.
- Decode these four amerDIF compressed files to produce four reconstructed images.
What To Turn In (in the following order, please!)
- Cover sheet with your names, and an explanation of how you tested your coder and decoder with another group, and the problems/bugs you encountered within your group and with the other group.
- In the precise order: sinan, sena, earth, omaha; a table with the SNR and PSNR in decibels of the reconstructed images (use Sayood’s distimg program)
- In the precise order: sinan, sena, earth, omaha; print each original and
its reconstructed image side by side (with help from Sayood's
convpgm program). Each printed image must be at least
3 inches x 3 inches. Label your images as "original" and
"reconstructed k=4", respectively.
- A script showing your source code
(listings with wraparound lines will not be accepted), and its
successful compilation and execution to produce the required amerDIF and reconstructed files. See Project 2 for a properly designed script.
-
Submit a hard copy of the beginning of the files for all four images (for example, the following commands output the first 15 lines of the sena files):
od -Ad -t u1 sena.img | head -15
od -Ad -ct x1 sena_img_k4.ADIF | head -15
od -Ad -t u1 sena_img_k4_RECON-ADIF.img | head -15
- Email me a "zipped" file containing:
-- your four amerDIF and four
reconstructed image files using the naming convention described below.
-- complete source code for your coder and decoder.
--
a README file with instructions how to
compile and execute your programs
--
your makefile (if one was used).
- Grading: 75% correct results; 25% program
documentation; report; testing. NOTE: Vague or meaningless variable names and comments will be significantly penalized.
|
Notes
- An image to be compressed is named <imagename>.img; the
output amerDIF compressed file should be named
<studentlastname>_<imagename>_img_k4.ADIF
- An amerDIF file to be
decompressed is named <studentlastname>_<imagename>_img_k4.ADIF; the output reconstructed
image file should be named <studentlastname>_<imagename>_img_k4_RECON-ADIF.img
- Students may not use or borrow from any publically (or priviately!)
available differential encoding software. Students should use
their own software written for Project 1 and used for Chapter 11's homework.
- Students in different groups may not
collaborate in programming their coder/decoder. However,
each group must test with at least one other group as follows.
Group A uses its coder to encode an .img file,
and gives the compressed "_img_k4.ADIF" file to Group B, which
uses its decoder to decompress the file, and vice versa. The two
groups use a command such as the unix
command "diff" to compare to see if their respective .ADIF and
_RECON-ADIF.img files are bit for bit identical. If the files do
not match, the two groups work together to determine where either or
both programs are at "fault". Once fault is
determined, different groups should not help each other correct the
fault. Document (and submt) the results of your group testing.
- Use the command "od -Ad -t
u1 | head -15" to see inside .img
files.
- Use the command
"od -Ad –ct x1 | head -15" to see inside .ADIF
files.
- You may write your coder/decoder either as "batch"
programs, where all output is written only after the encoding/decoding
is completed, or as "streaming real-time" programs that concurrently
produce the output file while the input is being processed.
- IMPORTANT! Your coder must use the RIGHT method. As explained in class, the WRONG method is
to encode the file by encoding differences between
original pixels. The RIGHT method encodes differences between each original pixel and the previous
reconstructed pixel.
See example below.
|
|
|
WRONG : (Xorign
- Xorign-1)
|
RIGHT : (Xorign
- Xdecodedn-1)
|
|
Xorig
|
110
|
111
|
116
|
114
|
118
|
110
|
111
|
116
|
114
|
118
|
|
Diff
|
-18
|
+1
|
+5
|
-2
|
+4
|
-18
|
-9
|
+4
|
-2
|
+4
|
|
Code
|
-8
|
1
|
5
|
-2
|
4
|
-8
|
-8
|
4
|
-2
|
4
|
|
Binary
|
1000
|
0001
|
0101
|
1110
|
0100
|
1000
|
1000
|
0100
|
1110
|
0100
|
|
Xdecoded
|
120
|
121
|
126
|
124
|
128
|
120
|
112
|
116
|
114
|
118
|
- Be sure you fully understand the above
"WRONG" vs. "RIGHT" concept before continuing!
- Your programs should assume a single initial
"virtual" reconstructed pixel value (i.e., Xdecoded-1) of 128. The first encoded difference
value will be based on the difference: Xorig0 - 128, where
Xorig0 is the first pixel in the .img
file. All other first row pixels will be differenced with the
prior row's last reconstructed pixel. (This approach is suboptimal as discussed on the mid-term.)
- From the above example, you can see that a 4-bit
difference cannot always exactly (i.e., without loss) encode a difference.
Sometimes the difference is larger than the maximum or minimum
value that can be encoded. Here is where loss is introduced.
In these cases, either a difference of -8 or
+7 will be used, and future differences will need to “catch up”
to correct for the loss.
- Sometimes differences will involve
"wraparound." A pixel of 250 plus a difference of +8
results in a pixel of
2, not 258. The following examples help demonstrate
wraparound, when pixel values are close to the extremes of 0 (black)
and 255 (white). In all cases, a coder should choose the code that results in the minimum squared error between the pixel being coded and the eventual reconstructed pixel. You must carefully comment your code where the
following special handling is done.
o
(wraparound
used - example 1: no loss) A black (or
nearly black pixel) adjacent to a previously decoded white (or nearly white)
pixel should encode with no error. For example, suppose Xorign = 2, and Xdecodedn-1 =
254. The difference is 2-254 = -252. Use the code +4. Then Xdecodedn = 2, and the squared error is 0 (2-2)2
[remember: pixel 254 +4 results in pixel 2]
o
(wraparound used - example 2: with
loss) Suppose we want to encode Xorign = 250 and Xdecodedn-1 =
4. The difference is 250-4 = 246. If code +7 is used, then Xdecodedn = 11, and the resulting squared error would be
(250-11)2. If code -8 is used, then
Xdecodedn = 252 [since pixel 4 -8
results in pixel 252], and the resulting squared error would be (250-252)2.
The code that should be used is -8 since it minimizes the squared error.
o
(wraparound not
used) Suppose we want to encode Xorign =
240 and Xdecodedn-1 = 10. The difference is 240-10 =
230. If code +7 is used, then Xdecoded
n
= 17, and the resulting squared error would be (240-17)2.
If code -8 is used, then Xdecodedn = 2,
and the resulting squared error would be: (240-2)2. The code that
should be used is +7 since it minimizes the squared error.
- Your coder should code such that the first
difference will be in the MSB (most significant bits) of the byte.
|
(up to 10 points)
Extra Credit: k=2,3,...,8
- Generalize your k=4 encoder/decoder to work for
any inputted k value in [2,8].
- (submit) A single table of SNR and PSNR values for all values of k for all four images.
- (submit) Encode/decode all four images for all k values. For each image, print out the
original and 7 reconstructed images (at least 3in X 3in), with 4 images per
page for side-by-side comparison in decreasing k value order. Label your images
appropriately.
- (submit) What is the smallest k value for which you would judge the reconstructed image to be observably no different than the original image?
- (submit) A single graph of "SNR vs. k"
for all four images. (What should the SNR be for k=8?)
- (submit) A single graph of "compression
ratio vs. k" for all four images.
- (submit) Email me your .ADIF and _RECON-ADIF.img files
for k=2,...,8 for all 4 images. Use
the naming convention "<studentlastname>_<imagename>_img_k<kvalue>.ADIF", and "<studentlastname>_<imagename>_img_k<kvalue>_RECON-ADIF.img",
respectively. For example, my compressed sinan
image with k=3 would be named
"amer_sinan_img_k3.ADIF" [You MUST use this naming
convention exactly.]
|
(up to 3 points)
Extra, Extra Credit: k=1
- Extend your coder/decoder for the special case
k = 1. With 1 bit, only 2 difference values can be encoded.
If your coder followed the pattern used above for k=2,...,8, the bits 1,0 would encode differences of {-1,0}, respectively, in which case, a coder could not encode a
positive difference. When k=1, use the bits 1,0
to encode differences {-1,+1}, respectively.
This approach does not allow a difference of zero to be encoded without introducing some
error.
- For consistency, always encode a difference of
0 as +1 (using the 0 bit), with the following single exception.
o
Do not
unnecessarily wraparound. If Xorign
= 255 and Xdecodedn-1 = 255, then the difference is 0. If
code +1 is used, then Xdecodedn = 0, and
the resulting squared error is (255-0)2. For this case only,
encode the 0 difference as -1 (using the 1 bit).
- What to turn in: integrate your k=1
results with the Extra Credit above.
|
(up to 10 points)
Extra, Extra, Extra Credit 1: Adaptive encoding (amerDIF
version 2)
- In static encoding, the range of difference
values that can be encoded never changes. In adaptive encoding,
the difference values allowable for encoding the nth
difference depend on what code was used for the n-1st
difference. In regions where the source output is relatively
constant (granular regions), an adaptive encoder/decoder decreases the
range of "encodable" differences. In
regions where source quickly rises or falls (overhead regions), an
adaptive encoder/decoder increases the range of "encodable differences."
- Consider k-bit adaptive encoding for k=2,...,8. In this case, one of the two
"maximum" (positive or negative) encodable
difference values "doubles" for encoding the nth difference
whenever that maximum difference was used to the n-1st
difference, and the other maximum, if necessary, returns to its original
value.
- Consider an example when k=3. For
the first difference, the coder chooses among the differences
{-4,-3,-2,-1,0,+1,+2,+3} using the two's-complement bit patterns
{100,101,110,111,000,001,010,011}, resp.
Suppose the first encoded difference is +3, then the second difference
is encoded from the set {-4,-3,-2,-1,0,+1,+2,+7}. Notice how the
maximum positive difference "doubled". If the second
difference then were encoded using +7, then the third difference would
be encoded from the set {-4,-3,-2,-1,0,+1,+2,+15}. However,
if the third difference is encoded as any value among {-3,-2,-1,0,+1,+2},
the fourth difference is encoded from the original set
{-4,-3,-2,-1,0,+1,+2,+3}, and if the third difference were encoded as
-4, then the fourth difference would be encoded from the set
{-8,-3,-2,-1,0,+1,+2,+3}. Notice here that the maximum negative
difference is doubled.
- The maximum positive (negative) codable value stops doubling when it reaches +127
(-128).
- Here's a coding example (as always assuming a
virtual pixel value of 128.) Before proceeding, be sure to
understand this example:
|
|
Choices
|
-4
|
-4
|
-4
|
-4
|
-4
|
-8
|
-16
|
-32
|
-4
|
-4
|
-4
|
|
|
-3
|
-3
|
-3
|
-3
|
-3
|
-3
|
-3
|
-3
|
-3
|
-3
|
-3
|
|
|
-2
|
-2
|
-2
|
-2
|
-2
|
-2
|
-2
|
-2
|
-2
|
-2
|
-2
|
|
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
|
|
3
|
7
|
15
|
3
|
3
|
3
|
3
|
3
|
7
|
15
|
3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xorig
|
134
|
140
|
139
|
136
|
130
|
120
|
112
|
111
|
116
|
115
|
|
|
Diff
|
+6
|
+9
|
+1
|
-3
|
-6
|
-12
|
-12
|
+3
|
+5
|
-3
|
|
|
Choose Code
|
3
|
7
|
1
|
-3
|
-4
|
-8
|
-16
|
3
|
7
|
-3
|
|
|
Binary
|
011
|
011
|
001
|
101
|
100
|
100
|
100
|
011
|
011
|
110
|
|
|
Xdecoded
|
131
|
138
|
139
|
136
|
132
|
124
|
108
|
111
|
118
|
115
|
|
- Consider the following k=3 decoding example (as
always assuming an initial virtual pixel of 128):
|
|
Input
|
001
|
011
|
011
|
011
|
100
|
100
|
010
|
011
|
011
|
111
|
|
|
Input bit represents
|
1
|
3
|
7
|
15
|
-4
|
-8
|
2
|
3
|
7
|
-1
|
|
|
Xreconstructed
|
129
|
132
|
139
|
154
|
150
|
142
|
144
|
147
|
154
|
153
|
|
- Now consider the special case when k=1. Initially,
the coder can encode a difference in the set {-1,+1}
(with bits 1 and 0, respectively.) In k=1
adaptive encoding, if the first difference encoded is +1 (using a 0 bit), then for the
second difference, the coder chooses among the differences
{-1, +2}. If the first difference is -1 (using a 1 bit), then for the second
difference, the coder chooses among {-2, +1}. If the first
difference is encoded as +1, and the second difference is encoded as +2,
then for the third difference, the coder chooses among {-1, +4}. In
general, if the n-1st
difference is encoded as a positive (negative), then the positive
(negative) value for encoding the nth difference doubles.
- Additionally, the encodable
difference which DOES NOT double returns to -1
or +1, accordingly.
- Codable values stop doubling when they reach +128 or -128.
- Consider the following example:
|
|
Code 0 represents
|
+1
|
+2
|
+4
|
+1
|
+1
|
+1
|
+2
|
+1
|
|
Code 1 represents
|
-1
|
-1
|
-1
|
-2
|
-4
|
-8
|
-1
|
-2
|
|
Xorig
|
129
|
131
|
129
|
125
|
123
|
121
|
120
|
|
|
Diff
|
+1
|
+2
|
-2
|
-5
|
-5
|
-3
|
-5
|
|
|
Choose Code
|
+1
|
+2
|
-1
|
-2
|
-4
|
+1
|
-1
|
|
|
Binary
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
|
|
Xdecoded
|
129
|
131
|
130
|
128
|
124
|
125
|
124
|
|
- The encoder should continue to allow wraparound
if it helps reduce squared error.
- Consider the following decoding example (as
always assuming an initial virtual pixel of 128):
|
|
Input
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
|
|
Input bit represents
|
+1
|
+2
|
+4
|
-1
|
-2
|
+1
|
+2
|
+4
|
+8
|
-1
|
|
|
Xreconstructed
|
129
|
131
|
135
|
134
|
132
|
133
|
135
|
139
|
147
|
146
|
|
- What to do and submit: analogous to the
requirements for the Extra Credit.
- Use .AADIF and .RECON-AADIF.img as the file extensions for "adaptive ADIF"
files.
- Acknowledgment: Thanks to Maitreya Natu for helping design and develop this adaptive
encoding extra credit.
|
(up to 7 points)
Extra, Extra, Extra Credit 2: Visualization
- Analogous to how Project 3 visualized Project
2, demonstrate your decoder using applets. For the k-values and methods
(static and/or dynamic) that you implemented, display each of Sayood's 4 images in three forms: original, ADIF
compressed file (converted to some viewable form), and the _RECON-ADIF.img
image.
- You need not do Extra, Extra, Extra Credit 1 to
get credit for Extra, Extra, Extra Credit 2.
|
|