Description
Question 1
Question 1A getchar, int literals, arrays (20 pts)
Specification
Complete an ANSI-C program, which should use getchar (only) to read and interpret integer.
Implementation
Download the partially implemented file a1A.c and start from there.
The program:
• should use getchar() to read inputs (from standard in) until EOF is read. The input contains
decimal integer literals separated by one blanks or new line characters. The program interprets each
literal and put into an int array. When “end of file” is reached, the program prints out the value of
each integer and the double of the value.
• assume all literals in the input are valid decimal int literals. Note that the input can contain
negative numbers.
• should not use other input IO functions such as scanf(), fgets(). Only getChar() is allowed to read
input. (So have to read char by char.)
• should not use other library function such as atoi() (So have to convert manually)
• should not use extra array. Only use one array resu[].
• as mentioned in lab, p43 of the K&R book contains an example of interpreting int literals char by
char (on the fly).
Sample Inputs/Outputs: (download – don’t copy/paste – the input file inputA.txt)
red 306 % gcc a1A.c -o a1A
red 306 % a1A
3 12 435
54 -15
7 98 -10 456
^D
——–
3 6
12 24
435 870
54 108
-15 -30
7 14
98 196
-10 -20
456 912
red 308 % a1A < inputA.txt
2
——–
5 10
34 68
534 1068
-12 -24
43 86
-13 -26
7 14
54 108
-122 -244
3245 6490
red 309 % Submit your program by issuing submit 2031ON lab2 lab2D.c
Question 1B getchar, floating point literals, arrays (40 pts)
Specification
Extend the program in 1A, so that it uses getchar (only) to read and interpret floating point literals.
Implementation
Name your program a1B.c. The program:
• should use getchar() to read inputs (from standard in) until EOF is read. The input contains
floating point literals and integer literals separated by one blanks or new line characters. The
program interprets each literal and put into a float array. When “end of file” is reached, the
program prints out the value of each float as well as the value multiplied by 2, as shown in sample
output below.
• assume all floating point literals are valid float/double or int literals (both 2.3, 5, .4
are considered valid). There are no negative numbers.
• should not use other input IO functions such as scanf(), fgets(). Only getChar() is allowed to read
input. (So have to read char by char.)
• should not use other library function such as atoi(), atol(), atof(), strtol(), strtoul(). (So have to
convert manually)
• should not use extra array. Only use one array resu[].
Sample Inputs/Outputs: (download – don’t copy/paste – the input file input2E.txt)
red 306 % gcc a1B.c -o a1B
red 306 % a1B
2.3 4.56
43.3 43 5.3
.3 1.2
^D
——–
2.3000 4.6000
4.5600 9.1200
43.3000 86.6000
43.0000 86.0000
5.3000 10.6000
Submit your program by issuing submit 2031A a1 a1A.c
Or websubmit (see end of this pdf for more info)
3
0.3000 0.6000
1.2000 2.4000
red 307 % cat inputB.txt
3.25 24.54
4.323 4.54
.4
1 0.29
red 308 % a1B < inputB.txt
——–
3.2500 6.5000
24.5400 49.0800
4.3230 8.6460
4.5400 9.0800
0.4000 0.8000
1.0000 2.0000
0.2900 0.5800
Question 2 Probability, bitwise operation, global variables (40pts)
Specification
As you have seen in the lab, a digital image is stored in computer as a collection of its pixel values (as
well as other information). Each pixel exhibits a particular color that consists of three channels: R (red),
G (green) and B (blue). Each pixel value is an integer that incorporates its R, G and B value. Each R, G or
B value is in the range of 0~255. Different combinations of R, G and B values produce different colors. A
pixelated image can abstract the most important information of trivial problems, as shown below.
In this question, you are going to help build a digital image processing system. The system takes as input
the raw information (including pixel values) of one or more source images. The images represent
environments where both safe and unsafe regions exist.
The images may have different sizes, but each image consists of a safe region surrounded by two unsafe
regions, as illustrated below where shaded areas in the images are safe regions, whereas white areas
are unsafe regions. (A safe region can represent, for example, a bridge, and unsafe regions are rivers, or,
a safe region represents a path where no landmines are placed and unsafe regions are full of
landmines.)
The system contains two parts. Part I scans through an input file which contains a set of pixels values of
some sample images and then generates and stores some statistic information of the encountered
colors. The stored information constitutes the database for the different colors in the input images. The
statistic information (database) would be used in part II, specifically in function analysis_display(),
which calculates and displays the probability that each of the colors represents the safe or unsafe
regions of the environment.
Submit your program by issuing submit 2031A a1 a1B.c
Or websubmit (see end of this pdf for more info)
4
Given a simplified example. Assume that the following image has 3 × 4= 12 pixels, where the pixels in
the middle column (i.e. pixel 1, 4, 7, 10) represent safe region (other pixels represent unsafe regions
where landmines are placed).
image1
After scanning all the pixels of this image, you should correctly process and store such info: there are
totally 12 pixels, among which, 4 are ‘safe pixels’ (pixel 1, 4, 7, 10) as they represent the safe region.
Others represent unsafe region. There are 3 red pixels (pixel 4,7, 10), which are all ‘safe pixels’ as they all
belong to (represent) the safe region. There are 2 green pixels (pixel 1, 11), one belongs to safe region
(pixel 1). Based on these information, function analysis_display() will calculate and conclude that
• have scanned/encountered black, white, green and red color
• the probability that a black color represents a safe region in the image is 0
• the probability that a white color represents a safe region in the image is 0
• the probability that a red color represents a safe region in the image is 100%
• the probability that a green color represents a safe region in the image is 50%
Convince yourself that these results make sense, intuitively. E.g., there are three red pixels, all represent
safe region, so the probability that a red color represents a safe region in the image is 100%. There are
two green color pixels, one is in safe region and one is not, thus the probability that a green color
represents a safe region in the image is 50%. In the implementation part, we will see how this is
calculated mathematically.
image 2
image 1
You may have multiple images as data source. In such cases, we can simply take the sum for each
occurrence, and compute as before. Consider the two images shown above. The first image is the same
as above. For the second image, assume it has 4× 3 pixels, and that the pixels in the middle 2 columns
(i.e, pixel 1,2,5,6,9,10) represent the safe region in the image. Others represent unsafe region. For this
example, after scanning all the pixel data, you should correctly calculate that: there are totally 12 + 12
4
7 8
9 10 11
5
6
0 1 2
3
1 2
3 4
7 8
9 10 11
0
5
6
0 1 2 3
4 5 6 7
8 9 10 11
5
pixels, among them, 4 + 6 = 10 are ‘safe pixels’. There are 3 + 4 = 7 red pixels, which are all ‘safe pixels’.
There are 2 +3 = 5 green pixels, among them 1+ 2 = 3 are safe pixels.
Based on this information, function analysis_display() should calculate and conclude that
• have scanned/encountered black, white, green and red color
• the probability that a black color represents a safe region in the images is 0
• the probability that a white color represents a safe region in the images is 0
• the probability that a red color represents a safe region in the images is 100%
• the probability that a green color represents a safe region in the images is 60%
Again, convince yourself that these results make sense. E.g., there are 5 green colors, 3 of them are in
safe region and the other 2 are not. Thus the probability that a green color represent a safe region in the
images is 60%;
Implementation
You are going to implement Part I of the system, given in images.c, and complete Part II, given in
function analysis_display()of file functions.c.
You should complete the main function of images.c. Your implementations should scan through a text
file containing all the pixel data of one or more images, counting relevant occurrences that are
necessary for calculating the above probabilities. These occurrence counts include,
• number of pixels in total,
• number of safe pixels (whatever the color),
• for each particular color scanned, the number of pixels of this color that occurs in the image,
• for each particular color scanned, the number of pixels of this color that are ‘safe pixels’
(representing safe region).
There are two issues that you should consider before you start part I: first, among the input pixels,
which are the safe pixels (pixels representing a safe area in the image), and which are not? Second, how
to store the relevant occurrences for each color? As there could be 256 ×256 × 256 = 16777216 possible
colors.
For the first issue, we assume that the safe region appears in each image as a rectangle spanning the
image perpendicularly, i.e., safe pixels occupy several columns of the image pixels depending on its
width, as shown in the above images. Data for the images are stored in a text file, one image per line, in
the form of
imageWidth imageHeight safeRegionStart safeRegionWidth pixel-0 pixel-1 ……
where imageWidth represents the width of the image (in terms of the number pixels), imageHeight
represents the height of the image, safeRegionStart is the index of the first pixel in the data list that
represents the safe region. That is, the lowest index of safe pixels. Pictorially, this is the pixel on the left
top corner of the rectangle safe region in the image. safeRegionWidth is the width of the safe region
(in terms of the number of pixels). So the two images in the above examples would be stored as
3 4 1 1 pixel-0 pixel-1 pixel-2 …… pixel-12
4 3 1 2 pixel-0 pixel-1 pixel-2 …… pixel-12
Given imageWidth imageHeight safeRegionStart safeRegionWidth, you can use simple
geometry to determine whether a scanned pixel is a safe pixel or not.
6
The second key issue involves how to store different colors encountered. We first look at how each pixel
value incorporates its RGB values. In our case, as you have seen in the lab, each pixel value is an integer
of 32 bits, which has the RGB value and other information compressed and stored in such a way that,
counting from the right most bit, B values occupies the first 8 bits, G occupies the next 8 bits, and R
occupies the next 8 bits. This is shown below. (The left-most 8 bits store other information about the
image, which we are not interested here.)
We need to store the occurrence of different colors in the data. In this program we use arrays to store
occurrences of each possible colors, but potentially any combination of R,G and B is possible, and thus
there are 256 ×256 × 256 = 16777216 possible colors! It would be cumbersome to use an array of size
16777216 to store the colors. One feasible approach is to take the 3 most significant bits of each of the
R, G and B bits, concatenate them, and then put as the lower 9 bits of an integer (other bits are 0), as
shown below. This integer will represent a group of very similar colors. Thus, we have totally 8×8×8 =
512 colors (from binary 00…000000000 ~ 00…111111111) for which we need to store occurrence
information. Therefore, as you see in function.c, we use arrays of length 512, instead of 16777216.
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
00…00000
For part II, most of the work has been implemented for you. You only need to complete the missing part
in function analysis_display() that calculates the probability of a color being in safe region.
For a color in the image, how to calculate this probability, given the statistical information collected in
Part I?
We follow the Baye’s rule, which states that P(A | B ) = 𝑃(𝐵 |𝐴) . 𝑃(𝐴)
𝑃(𝐵)
. For a particular color, the
probability that sthe color represents (part of) the safe region, denoted as P( safeRegion | color) can be
computed as
P(safeRegion | color) =
𝑃(𝑐𝑜𝑙𝑜𝑟 | 𝑠𝑎𝑓𝑒𝑅𝑒𝑔𝑖𝑜𝑛) . 𝑃(𝑠𝑎𝑓𝑒𝑅𝑒𝑔𝑖𝑜𝑛)
𝑃(𝑐𝑜𝑙𝑜𝑟)
where,
P (color | safeRegion) is the probability that color color is observed, given that the safe region is
observed, P(safeRegion) is the probability of the observing the safe region, and P(color) is the
probability of the observing color color.
Each probability can be calculated using the relevant occurrence counts. Take the first image as an
example,
image 2
image 1
0
3
1 2
3 4
7 8
9 10 11
0
5
6
2 3
4 5 6
9
7
P(red | safeRegion) = # red pixel on safe region / # pixel on safe region = 3 / 4
P(safeRegion) = # pixel on safe region / # total pixels = 4 / 12
P(red) = # red pixels / # total pixels = 3 / 12
Thus, P(safeRegion | red) =
𝑷(𝒓𝒆𝒅 | 𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏) ∗ 𝑷(𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏)
𝑷(𝒓𝒆𝒅)
=
𝟑/𝟒 × 𝟒/𝟏𝟐
𝟑/𝟏𝟐
= 1
P(green | safeRegion) = # green pixel on safe region / # pixel on safe region = 1 / 4
P(green) = # green pixels / # all pixels = 2 / 12
Thus, P(safeRegion | green) =
𝑷(𝒈𝒓𝒆𝒆𝒏 | 𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏) ∗ 𝑷(𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏)
𝑷(𝒈𝒓𝒆𝒆𝒏)
=
𝟏/𝟒 × 𝟒/𝟏𝟐
𝟐/𝟏𝟐
= 0.5
image 2
image 1
When we have multiple images as data source, as in the 2nd example, we can simply take the sum for
each occurrence, and compute as before
P(safeRegion) = # safe pixel / # all pixels = (4+6)/ (12+12) =10 / 24
P(red) = # red pixel / # all pixel = (3+4)/(12+12) = 7 / 24
P(red | safeRegion) = # red pixel / # safe pixel = (3+4) / (4 +6) = 7 / 10
Thus, P(safeRegion | red) =
𝑷(𝒓𝒆𝒅 | 𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏) ∗ 𝑷(𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏)
𝑷(𝒓𝒆𝒅)
=
𝟕/𝟏𝟎 × 𝟏𝟎/𝟐𝟒
𝟕/𝟐𝟒
= 1
P(green) = # green pixels / # all pixels = (2+3)/(12+12) = 5 /24
P(green | safeRegion) = # green pixel on safe region / # safe pixel = (1+2)/(4+6) = 3 / 10
Thus, P(safeRegion | green) =
𝑷(𝒈𝒓𝒆𝒆𝒏 | 𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏) ∗ 𝑷(𝒔𝒂𝒇𝒆𝑹𝒆𝒈𝒊𝒐𝒏)
𝑷(𝒈𝒓𝒆𝒆𝒏)
=
𝟑/𝟏𝟎 × 𝟏𝟎/𝟐𝟒
𝟓/𝟐𝟒
= 0.6
More Implementation details
On eClass you are given some text files, each contains one or more lines of pixel values, representing
one or more sample images. The corresponding images are also be given to you (just for your reference,
you don’t need them for coding).
You are going to complete main in images.c. You can implement everything within the main function,
or you can define some subroutines to do some work, e.g., a function to check if a pixel i is in safe
region, a function to extract 3 bits from RGB values and return a new color.
I have defined a macro DEBUG. When DEBUG is defined, some information about the pixels that are
being processed will be displayed. That is, print out information for all the pixels during the process of
building up the database. If you wish to have these messages displayed when you run the program, just
uncomment the #define DEBUG (see sample outputs on eClass)
1 2
3 4
7 8
9 10 11
0
5
6
0 1 2 3
4 5 6 7
8 9 10 11
8
You are also given a program functions.c, which contains some global variables to be used in
image.c.to store the statistical information. Complete the three lines in function
analysis_display() to calculate the probabilities about a current color being in safe region.
Sample output assume debug mode is not on. Uncomment #define DEBUG to see the debug
messages.
red 99% gcc images.c functions.c -Wall
red 100% a.out < image1.dat
scanning pixel data for a new image…..
————- display database —————
[0]: concatenated by 000***** 000***** 000***** (e.g., BLACK, which has r,g,b value 00000000 00000000 00000000)
probability that this color represents safe region is (0/4) * (4/12) / (3/12) –> 0.000 * 0.333 / 0.250 = 0.000
[56]: concatenated by 000***** 111***** 000***** (e.g., GREEN, which has r,g,b value 00000000 11111111 00000000)
probability that this color represents safe region is (1/4) * (4/12) / (2/12) –> 0.250 * 0.333 / 0.167 = 0.500
[448]: concatenated by 111***** 000***** 000***** (e.g., RED, which has r,g,b value 11111111 00000000 00000000)
probability that this color represents safe region is (3/4) * (4/12) / (3/12) –> 0.750 * 0.333 / 0.250 = 1.000
[511]: concatenated by 111***** 111***** 111***** (e.g., WHITE, which has r,g,b value 11111111 11111111 11111111)
probability that this color represents safe region is (0/4) * (4/12) / (4/12) –> 0.000 * 0.333 / 0.333 = 0.000
Totally 4 colors are stored in database
red 101% a.out < image2.dat
scanning pixel data for a new image…..
————- display database —————
[0]: concatenated by 000***** 000***** 000***** (e.g., BLACK, which has r,g,b value 00000000 00000000 00000000)
probability that this color represents safe region is (0/6) * (6/12) / (4/12) –> 0.000 * 0.500 / 0.333 = 0.000
[56]: concatenated by 000***** 111***** 000***** (e.g., GREEN, which has r,g,b value 00000000 11111111 00000000)
probability that this color represents safe region is (2/6) * (6/12) / (3/12) –> 0.333 * 0.500 / 0.250 = 0.667
[448]: concatenated by 111***** 000***** 000***** (e.g., RED, which has r,g,b value 11111111 00000000 00000000)
probability that this color represents safe region is (4/6) * (6/12) / (4/12) –> 0.667 * 0.500 / 0.333 = 1.000
[511]: concatenated by 111***** 111***** 111***** (e.g., WHITE, which has r,g,b value 11111111 11111111 11111111)
probability that this color represents safe region is (0/6) * (6/12) / (1/12) –> 0.000 * 0.500 / 0.083 = 0.000
Totally 4 colors are stored in database
More input and output file are provided on eClass. They are run with debug messages.
Submit your program using submit 2031 a1 images.c functions.c
Make sure your program compiles in the lab environment. The program that does not
compile in the lab will get 0.
All submissions need to be done from the lab
End of assignment 1
Or websubmit (see end of this pdf for more info)
9
In summary, for this assignment you should submit:
a1A.c a1B.c images.c functions.c
At any time and from any directory, you can issue submit -l 2031A a1 to view the list of files that
you have submitted.
Common Notes
All submitted files should contain the following header:
/***************************************
* EECS2031A – Assignment 1 *
* Author: Last name, first name *
* Email: Your email address *
* eecs_username: Your eecs login username *
* York num: Your York student number
****************************************/
Web-submit
To prepare for the coming labtest, for which you will be encouraged to work on your local computer and
submit using websumit, for this assignment you can submit using websubmit. So, in addition to
submitting from the lab, you can also submit from local machine directly. (You should still make sure
that the files compile in the lab environment)
You can submit using websubmit at https://webapp.eecs.yorku.ca/submit/
o login using EECS , not passport York. If you keep on getting prompted to login
using passport York, then clear the cookie and cache of your browser and then try
again. Eventually you should see the page below.
o Once login, select Course: 2031A and then select Assignment: a1
o Then upload files from your local computer.
See this page for more information about web-submit
https://wiki.eecs.yorku.ca/dept/tdb/services:submit:websubmit
Lower case L
Use EECS account
