List is a basic data structure where each item in the List can be identified by

Question

List is a basic data structure where each item in the List can be identified by an index. This is a number saying where the item is relative to the first item in the List. Lecture 14, slide 25, introduced a basic data structure called a Table. An item in a Table is identified by using 2 indices. The first index says which row in the Table the item is in and the second index says which column of the Table the item is in.

A Table can be used to store an image, such as a picture taken by a digital camera. In a greyscale image, the pixel value is a small number in the range from 0 to 255 or from 0 to 2047. 0 often represents black and the largest integer value represents white. In a colour image, the pixel value might be a list of 3 integers where these integers represent how red, green or blue the pixel colour is. The following is an example of a 4 x 4 grey scale image of a black square against a white background

  Figure 1

We can use the following notation when describing pixels in an Image_Table:

Image_Table[ row, column ] is the pixel in the row given by row and the column given by column;

Pixel.row – is the row in the Table for Pixel

Pixel.column is the column in the Table for the Pixel.

An important operation in image processing is to put pixels into groups where pixels in the same group have similar pixel values and are spatially connected. Two pixels, A and B, are spatially connected if there is a chain of pixels that starts at A and ends at B where every pixel in the chain is a neighbour of the pixels that immediately precede or follow it.

For example, in the following group of pixels, the pixel P has 8 neighbours: NW, N, NE, W, E, SW, S and SE

Figure 2: neighbours of P

How do we determine whether two pixel values are similar enough for us to say they belong to the same group? One way of doing this is to use the nearest-neighbour principle:

Pixels A and B belong to the same group if B is the nearest neighbouring pixel to A or A is the nearest neighbouring pixel to B.

Referring to Figure 2, the nearest neighbouring pixel of P is the pixel from NW, N, NE, W, E, SW, S, and SE whose pixel value is closest to the value of P.

Note: there may be more than one nearest neighbouring pixel.

Finally, a Group_Image, G, is an image where G[row, column ] is the number of the group to which Image_Table [ row, column ] belongs. The numbering for groups can start at 0 and ends at n-1 where n is the number of groups.

(a) Use the nearest neighbouring pixel principle to put the pixels in the following images into groups. For each image, show the corresponding Group_Image and give the number of distinct groups.

(b) Consider the following module for grouping pixels in an image stored in a Table.

Module Add_2_group ( Image_Table, Pixel_A, Pixel_B, Group_of_Pixels ) {

// Pixel_A, Pixel_B and Pixel_C are pixels in Image_Table.

// Pixel_A and Pixel_B are assumed to be neighbours

// Group_of_Pixels is a list of Pixels.

  If ( Pixel_B is in Group_of_Pixels )

return

  If ( ( Pixel_A is a nearest_neighbouring_pixel to Pixel_B )

or ( Pixel_B is a nearest_neighbouring_pixel to Pixel_A ) )

{

Add Pixel_B to Group_of_Pixels

For each Pixel_C which is a neighbour of Pixel_B

{

If ( Pixel_C is not in Group_of_Pixels )

Add_2_Group ( Image_Table, Pixel_B, Pixel_C, Group_of_Pixels )

}

}

}

(i) Trace the execution and show what is produced when Image_Table is the image in Figure 1, Group_of_Pixels is initially empty, Pixel_A is the pixel in the top-left corner and Pixel_B is the pixel that is 1 row down and 1 column across from Pixel_A.

For each call on the module, show the parameters that are involved in the call and the values in Group_of_Pixels that are returned.

(ii) Trace the execution and show what is produced when Image_Table is the image in Figure 1, Pixel_A is the pixel that is 1 row down and 1 column across from the pixel in the top-left corner and Pixel_B is the pixel that is in the same row but next column across from Pixel_A. Group_of_Pixels contains one pixel only, Pixel_A.
For each call on the module, show the parameters that are involved in the call and the values in Group_of_Pixels that are returned.

(c) Write a module, Group_Pixels ( Image_Table, Group_Image ) which is given an image stored in Image_Table. The module should use Add_2_Group from part (b) of this task. The module should return the number of distinct image groups it finds while Group_Image should show for each pixel in Image_Table the group number of the group to which it belongs.

Pls write in Pseudo Code form, thx

Explanation / Answer

a)THE 256 POSSIBLE GRAY INTENSITY VALUES ARE:

0=BLACK

128=MID-GRAY

255=WHITE

In order to get a better idea of pixel intensity values, we have taken the 15 x 15 pixel block.

Pixel intensity values for image 15x15:

150 154 160 157 106 140 147 142 141 147 132 150 171 117 136
144 159 125 121 157 143 132 136 153 138 155 164 169 162 152
190 175 169 155 161 136 152 158 141 162 147 153 161 168 169
185 203 139 161 151 159 145 167 179 167 150 155 165 159 158
151 153 163 152 160 152 164 131 131 51 124 152 154 145 143
164 162 158 167 157 164 166 139 132 138 119 148 154 139 146
147 148 143 155 169 160 152 161 159 143 138 163 132 152 146
66 129 163 165 163 161 154 157 167 162 174 153 156 151 156
162 173 172 161 158 158 159 167 171 169 164 159 158 159 162
163 164 161 155 155 158 161 167 171 168 162 162 163 164 166
167 167 165 163 160 160 164 166 169 168 164 163 165 167 170
172 171 170 170 166 163 166 170 169 168 167 165 163 163 160
173 172 170 169 166 163 167 169 170 170 170 165 160 157 148
167 168 165 173 173 172 167 170 170 171 171 169 162 163 162
200 198 189 196 191 188 163 168 172 177 177 186 180 180 188

>The fundamental unit on a computer is a bit. A bit (binary unit) takes either the value 0 or 1.
> Since each bit takes on one of two values and 8 bits make a byte, we can use the multiplication principle to realize that there are 28 = 256 possible bytes. We represent these bytes in base 2.
> For example, the intensity 125 can be written as

125 = 64 + 32 + 16 + 8 + 4 + 1
    = 0 x 128 + 1 x 64 + 1 x 32 + 1 x 16 + 1 x 8 + 1 x 4 + 0 x 2 + 1 x 1
    = 0 x 27 + 1 x 26 + 1 x 25 + 1 x 24 + 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20
    = 011111012

>The American Standard Code for Information Exchange (ASCII) has assigned each of the 256 possible bytes to each keyboard character.
> If an image of size M x N pixels is stored in raw format on a web server or digital camera, then aside from some header information, the file consists of M x N x 8 bits (zeros and ones) where the rows of the image are concatenated to form one long bit stream.
> For our example image, the bit stream has length 768 x 512 x 8 = 3,145,728 bits.

>Color images require more storage space than grayscale images. Pixels in grayscale images need just one byte to indicate the intensity of gray needed to render the pixel on screen,It turns out that any color can be built using the correct combination of red, green, and blue.
> Thus, pixels in color images are represented by three values (r,g,b). The values indicate the intensity of red, green, and blue, respectively, needed to render the pixel on screen. The range of intensities is exactly the same as grayscale images - 0 means none of the color appears in the pixel and 255 indicates the highest level of the color is evident in the pixel.
> For example, the triple(128, 0, 128) would represent a medium purple while (255, 215, 0) represents gold

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.