EECS2031-Assignment 1 Solved

Question 1
Question 1A   getchar, int literals, arrays   

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 

-------- 

5       10 

34      68 

534     1068 

-12     -24 

43      86 

-13     -26 7       14 

54      108 

-122    -244 

3245    6490  

                                  Question 1B  getchar, floating point literals, arrays                                        
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 

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  
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.  

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).   

 

0 
1
2
3
4
5 
6 
7
8
9
10
11
 

 

 

 

 

 

 

  

                                                     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
0 
1
2
3
4
5 
6 
7
8
9
10
11
0 
1
2
3 
4
5
6
7
8 
9
10
11 
 

 

 

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 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.

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          

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

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,  

 

 

 

 

 

  

0 
1
2
3
4
5 
6 
7
8
9
10
11
                                                                                                                       image 2                                                    image 1  
                                        0 

3

 

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)      

                                                                                                         𝑷                                               𝟑/𝟏𝟐

 

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 
1
2
3
4
5 
6 
7
8
9
10
11
0 
1
2
3 
4
5
6
7
8 
9
10
11 
                                                                                                                      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)    

                                                                                                          𝑷                                                  𝟕/𝟐𝟒

 

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)   

                                                                                                              𝑷(𝒈𝒓𝒆𝒆𝒏)                                                    𝟓/𝟐𝟒

 

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) 

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