C代写：CS162 Image

发表于   |   分类于

用libpng处理PNG图像，实现Union Find算法，以及一系列的像素级的运算操作。

Introduction

In this assignment, you will learn to implement UNION FIND algorithm for image processing. Work individually. Follow the guidelines in the syllabus for any discussions with others. You may work in pairs on extra credit contests, but then the extra credit will be divided among the two of you. Extra credit entries must be bug-free to be eligible and turned in on time (no late days).

Files

After downloading the assignment tarball from the course website, extract the files by running:

tar -xvf lab4-handout.tgz

from a terminal window. Some of the files worth looking at are listed below.
Files you won’t necessarily modify:

Makefile
img/
lib/*.h
lib/*.c
libpng_check.c

Files you should modify (and the files denoted by * will be submitted for grading):

* pixel.c
* graph.c
* unionfind.c
unionfind_test.c
* segment.c
segment_test.c

Additionally, you should create a file called:

written.pdf

which contains the answers to the written parts of the assignment. For your convenience, we’ve provided a LATEX template (written.tex).

Submission

To submit your programming assignment, first generate a handin archive lab4-handin.tgz with the command 

make clean && make package

then submit your lab4-handin.tgz file to your Subversion repository (svn) for the class. Once you’ve completed all problems, you should also submit your written.pdf to Gradescope.

Note that your code will not be graded until after the due date. It is your responsibility to test your code on the CSIL machines and proofread your writeup thoroughly before submitting. Code that does not compile will not receive any points.

Image Processing

In this assignment, we will learn to process PNG images. Why PNG you ask? Well, it is a very common (and arguably the best) lossless image compression file format.

Installation

More specifically, we will be using the libpng library to process PNG images using C. In order to compile your code, you will need a library called libpng installed on your system.

You can check if the library has been properly installed on your system by running the command we wrote for you:

$ make checklib
$ ./checklib

You may ignore the “unused parameter” warnings during this checking. If the two commands above successfully generate the file img/uchicago.html that contains the uchicago shield logo, then you may skip this section and start enjoying the fun lab!

However, if the library has not been installed, you have the following options:
If you are running MacOS which has Homebrew installed you can run:

brew install libpng

If you have root access on Linux or Bash for Windows, you can run this:

sudo apt install libpng-dev

If you are running Cygwin, it might be a bit harder, but I suggest installing apt-cyg running:

apt-cyg install libpng-devel

If you are having trouble setting up the environment, it is suggested that you SSH into the CS department machines, which already have this library installed.

Image_util

We have also provided you with a set of functions that read and write PNG files. Please check out lib/image_util.h and lib/image_util.c. You can simply invoke these functions in your code without trying to understand how they work. However, the functions are designed to only read certain types of PNG files for this assignment. So, here are some of the points worth noting

  • The maximum size of the image is 1000 pixels in terms of width and height, which we defined as ROWS, COLS.
  • The color space of the PNG file should be ARGB.

Strict Pixel Graph

In this assignment, we will explore the applications of UNION-FIND technique on processing images represented by strict pixel graphs. One application is determining and labeling the connected components of a spatial data structure. The other is segmenting the pixels of an image into regions, called “segmentation”.

Pixels

To capture the contents of a single pixel, we need to know two things: how opaque or transparent it is, and what color it is. As mentioned above, one common way to do this is called ARGB.

The transparency is stored as an integer in the range [0, 256), where 0 is completely transparent and 255 is completely opaque. This is called the alpha (A) value. The color is stored as three other integers, each also in the range [0, 256), which respectively describe the intensity of the red (R), green (G), and blue (B) color in the pixel.

So a pixel is described by four integers between 0 (inclusive) and 256 (exclusive). One way to represent the four integers that make up a pixel is by packing them inside a 32-bit integer, breaking that integer up into 4 components with 8 bits each:

a0 a1 a2 a3 a4 a5 a6 a7 r0 r1 r2 r3 r4 r5 r6 r7 g0 g1 g2 g3 g4 g5 g6 g7 b0 b1 b2 b3 b4 b5 b6 b7 where:
  • a0 a1 a2 a3 a4 a5 a6 a7 : represents the alpha value (how opaque the pixel is).
  • r0 r1 r2 r3 r4 r5 r6 r7 : represents the intensity of the red component of the pixel
  • g0 g1 g2 g3 g4 g5 g6 g7 : represents the intensity of the green component of the pixel
  • b0 b1 b2 b3 b4 b5 b6 b7 : represents the intensity of the blue component of the pixel

Each 8-bit component can range between a minimum of 0 (binary 00000000 or hex 0x00) to a maximum of 255 (binary 11111111 or hex 0xFF).

We have implemented a set of library functions that deals with the pixel representation above. It is recommended that you inspect the get_red, get_green, get_blue, get_alpha, and make_pixel functions provided in pixel.c.

Images

An image will be stored in a two-dimensional array of pixels, denoted pixels. Thus, the pixel value of the point with x-coordinate as x and y-coordinate as y in the image would be stored at pixels[y][x].
Consider the simple digital image below, in which each pixel’s color is represented by just a single letter for simplicity. Here we can imagine N = brown, G = gray, W = white, B = blue. Therefore,

pixels = {{B,N,N,G}, {B,W,W,W}, {G,G,W,G}, {N,N,N,G}}

For convenience, we will also keep an one-dimensional array pixels’ of pixels to represent the image. Pixels are stored in the array row by row, left to right starting at the bottom left of the image.
For example, for the same image below, we have

pixels = {B,N,N,G,B,W,W,W,G,G,W,G,N,N,N,G}

Task 5.1

In pixel.c, implement the function:

1
pixelID get_pixel_id(unsigned int x, unsigned int y, unsigned int w);

that returns its index to the 1-D pixel array, given the coords of the input pixel and the width of the image.

Task 5.2

In pixel.c, implement the function:

1
unsigned int get_x_coord(pixelID idx, unsigned int w);

that returns the x coordinate value of the pixel, given its index and the width of the image.

Task 5.3

In pixel.c, implement the function:

1
unsigned int get_y_coord(pixelID idx, unsigned int w);

that returns the y coordinate value of the pixel, given its index and the width of the image.

Graphs

Now we define the strict pixel graph of an image to be the pair G = (V, E), where V is the set of pixels, like those shown above in the diagram for the previous exercise. Then E is the set of edges, where an edge e connects v0 = (x0, y0) with v1 = (x1, y1) provided |x0 - x1| + |y0 - y1| = 1 and the colors of the two pixels are the same. The strict pixel graph is undirected.

Task 5.4

In graph.c, implement the function:

1
2
3
graph pixel_graph_new(unsigned int img_width,
                      unsigned int img_height,
                      pixel pixels[ROWS][COLS]);

that allocate enough space for the graph, and initialize its required fields (see below for more details).

Task 5.5

In graph.c, implement the function:

1
void pixel_graph_free(graph G);

that free up the memory used by graph G.

Before you implement the two functions above, you might want to first think about what data you want to store for the graph G = (V, E), and then fill them in the struct pixel_graph_header. For instance, you are free to design any data structure for representing the edge set E of the graph, etc.
Furthermore optionally, depending on your design, you might want to define helper functions for testing your graph implementation, such as:

  • bool is_vertex(graph G, pixelID v);
  • bool is_pixel_graph(struct pixel_graph_header *G);
  • bool pixel_graph_isedge(graph G, pixelID v, pixelID w);
  • Et cetera.

UNION-FIND

Finding Connected Components

As seen from lecture, the UNION-FIND method can be implemented by using a two-dimensional int array of pixelID values, named parentID, to build a forest of up-trees for the current image. Each element of parentID will either be the pixelID value of the parent of the up-tree node, or 1 if the node itself is the root of an up-tree. Initially, before any of the UNION operations, each element of the array should be 1, since every pixel is in its own subset.

Task 6.1

In unionfind.c, implement the function:

1
void up_trees_new(graph G, pixelID parentID[ROWS][COLS]);

that stores the forest of up-trees in the array parentID, given the graph G.

Notice that we have implemented functions for converting pixel indices from/to coordinates in
Section 5. So it will be possible to follow the path from any pixel to the root of its up-tree by repeatedly getting the parent node’s pixelID from the parentID array, and then from the pixelID getting the x and y coordinates of the parent, and then getting the its parent’s pixelID, etc., until the root of the up-tree is reached.

Task 6.2

In unionfind.c, implement the function:

1
pixelID up_trees_find(pixelID parentID[ROWS][COLS], unsigned int w, pixelID idx);

that finds and returns the index of the root of the pixel with pixelID idx in the up-tree.

Task 6.3

In unionfind.c, implement the function:

1
void up_trees_union(pixelID parentID[ROWS][COLS], unsigned int w, pixelID p1, pixelID p2);

that merges the two groups (up-trees) to which pixel p1 and pixel p2 belong, and it should make the one having the smaller pixelID value be the parent of the other.

Now apply your UNION-FIND implementation to the problem of analyzing an image. Your code will merge groups of pixels so that, at the end, each connected component of the strict pixel graph will be represented by one up-tree. To do this, your code should scan the image considering all the pixel pairs for which edges exist (according to the definition of G). Perform FIND-UNION on all such pairs. Starting at (x, y) = (0, 0), check to see if G contains an edge to (x + 1, y) = (1, 0) and/or to (x, y + 1) = (0, 1). If it does, perform the FIND operations (up_trees_find) on the endpoints of this edge, and if the results are different, then UNION (up_trees_union) the two subsets. After processing this pixel, go on to the next (incrementing x). When the first row of pixels is complete, do the same for the second row, etc., until all rows of pixels have been processed.

Task 6.4

In unionfind.c, implement the function:

1
void run_union_find(graph G, pixelID parentID[ROWS][COLS], bool count);

that does the operations described above, and when count is set to true, print out the number of times UNION is called. For example, if we counted to 42, then the output to stdout should look like:

The number of times that the method UNION was called for this image is: 42.

Counting Connected Components

Next, set an integer variable, count, to zero, and do another scan of the parentID array. Each time a root of an up-tree is encountered, increment count.

Task 6.5

In segment.c, implement the function:

1
int count_connected_components(graph G, pixelID parentID[ROWS][COLS]);

that does the operations described above and returns the count. At the end of the scan, print out the value of count with explanatory text as follows (e.g. if counted 42 components):

The number of connected components in this image is: 42.

Note that the number of times UNION was called, plus the number of connected components found should add up to the number of pixels in the image, so you can use this fact in debugging your code.

Labeling Connected Components

Now modify your code (that does the scanning and counting above) so that each time an up-tree root is encountered, not only is the count incremented, but that root is associated with the count in a hash table. Feel free to use what you learned from last lab on hash tables, and apply it here. As some hints, the keys of your hash table could be integers representing the roots’ pixelID values, and the values would also be integers representing the counts, i.e., the connected component numbers.
Write code for another scan of the image, this time doing the following for each pixel:

  • FINDing the root of the pixel’s up-tree;
  • Looking up the count value for that root in the hash table. (Then convert the Integer to an int.) Let’s call the resulting int k.
  • Determine the k th color by calling the provided function get_color(k) in lib/colors.h.
  • Reassign the pixel with the new color.
  • Write the new image to a PNG file.

Task 6.6

In segment.c, implement the function:

1
void label_connected_components(graph G, pixelID parentID[ROWS][COLS]);

that does the operations described above.

Task 6.7

As seen from lectures, there are several optimizations we can do to improve the union and find operation. In unionfind.c, use the “union-by-size” and “pathcompression” techniques to improve union and find, respectively. You might want to keep track of the size of the subtree rooted at each node, which would be updated each time union was called.
Please email your submission to Yongshan.

Trees

So far in the lectures, we have seen three binary tree structures, namely binary heaps, binary search trees, and AVL trees.

Task 7.1

For this question, you will consider the structure of a binary tree as shown below.
You may assume there are specification functions is_bst and is_ordtree that checks if input is a binary search tree, and that the ordering invariant was preserved, respectively:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct tree_node tree;
struct tree_node {
  elem data;
  tree* left;
  tree* right;
};
struct bst_header {
  tree* root;
};
typedef struct bst_header* bst;
bool is_bst(struct bst_header* B);
bool is_ordtree(struct tree_node* T);

Complete the function bst_in_order that prints the elements in a binary search tree B in increasing order according to their keys (Hint: Recursion). You may assume there is a function print_node(T) that takes a non-NULL T of type tree* and prints the contents of that node. You should NOT need to examine the keys in the tree nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bst_in_order(bst B)
//precondition: is_bst(B);
{
  tree_in_order(B→root);
}
tree_in_order(tree* T)
//precondition: is_ordtree(T);
{
  if (T == NULL) return;
  ___________________________;
  ___________________________;
  ___________________________;
  return;
}

Task 7.4

Complete the following function that returns the number of possible binary search trees that can be constructed with exactly n unique keys. (Hint: Recursion.)

1
2
3
4
5
6
7
8
9
10
int num_trees(int n)
//precondition: n >= 0
{
  if (n == 0) return _____________;
  int total = 0;
  for (int i = 0; i < n; i++) {
    total += __________________;
  }
  return total;
}

Task 7.5

Suppose A is an AVL tree, and we wish to insert an element x into the tree.
Notice that we first traverse down the binary tree, and then check for balancing. Suppose during the rebalance step, we observe that the difference in the height of the left and right subtrees is 2. We have the following options:

  1. Perform a rotate left operation on A.
  2. Perform a rotate right operation on A.
  3. Perform a rotate left operation on the left child of A followed by a rotate right on A.
  4. Perform a rotate right operation on the right child of A followed by a rotate left on A.

If x is less than the element at the root of the left subtree, what do we do? What if x is greater than the element at the root of the left subtree?