programming编程设计代做、C/C++程序代写、c++语言程序调试

日期：2021-03-07 11:00

PA 6 - Images

In this programming assignment, you will be working with images. You will implement key parts

of an image processing library, which serves to abstract out the low-level details of manipulating

pixels and images. As an extra credit problem, you can then use this library to implement a full

application: green screen substitution. Besides giving you some exposure to images, this

assignment focuses on more advanced data structures, specifically providing practice with

structs and dynamic memory.

Summary

The graphics we have been using throughout this course (such as karel) was built upon open

source graphics libraries (called SDL and STB). For this assignment, we will be leveraging

these same libraries and our own image processing library as an abstraction on top of it. The

extra credit problem illustrates how you could then use this abstraction to efficiently implement

something like green screen substitution.

The starter code for this PA consists of a lot of pre-built code for you to look at and learn from,

including the graphics libraries. Do not feel overwhelmed by this; the code organization is

detailed in General Instructions and you only need to work with very few of the files. The others

are mainly included for your interest.

This assignment only takes about half the time of a normal assignment. You will be asked to

implement the following functions:

To submit the work, please follow the Submission Instructions.

Image create_blank_image(int width, int height) 10 pt

void free_image(Image image) 10 pt

void set_pixel(Image image, int x, int y, Pixel new_pixel) 15 pt

Pixel get_pixel(Image image, int x, int y) 15 pt

void greenscreen(Image* imagePtr, Image small_image) (Extra credit) 15 pt

General Instructions

Setup and Goals

In this assignment, you will look at how images can be represented and manipulated. At the

most fundamental level, images are simply a collection of bits. However, when we want to write

programs that manipulate images, we would like to be able to think about them in a more

convenient way. Rather than saying “change these bits”, we would like to do something like

“change the color of the pixel at coordinate (5,9) to green”.

To achieve this, we need a library of functions that allows us to hide the underlying low-level

details. It should instead provide a convenient interface so we can think about the problem at a

high level of abstraction (pixels and colors rather than bits).

For this programming assignment, you will write the main parts of such a library to work

with images and then use it to implement actual image processing. Make sure you login to the

servers using a method that can show graphical output (i.e., not pure ssh).

Starter Code

To get the starter code for this assignment, execute the following command In your home

directory:

$ getStarter PA6

This will create a new subdirectory, called “PA6”. The different files you find in there are

discussed in the next section.

Code Structure

You will find quite a few files in the startercode. Don’t worry. Most of them you don’t have to

modify. They are there as examples for you to look through and to give you a feel for a larger

software project. In fact, we gave you access to all the code this time, and you could now write a

complete graphical program (like karel) from scratch if you wanted to.

The files are organized as shown in the diagram on the next page. Only the draw.c has a main()

inside, and when compiled together with the appropriate helper files (the ones with a yellow

background), it will yield an executable. You are encouraged to create additional files with a

main() to test your code; the Makefile supports this. However, it is important to note that the

files in yellow should not contain a main(). The files with the red names (manipulate.c and

image_basics.c) are the only ones you need to submit.

Our Image Processing Library

This library provides a number of useful functions to work with images. In this PA, you will be

writing a key part of this library.

image.h: Do not change this file. This is the library header file and needs to be included in any

program that uses our library (such as draw.c). This .h file is important as it defines the data

structures we will be using to represent images: the custom types Image and Pixel. These

will be discussed in detail in Working with Images.

image_basics.c: The code in this file supports basic tasks such as creating a blank image and

setting pixels in an image to a particular color. You will need to implement these functions. The

details are explained in Assignment Details.

image_show.c and image_rw.c: They support displaying images and storing images; they are

already provided for you and don’t need to be modified, but have a look at the code.

framework: This directory contains the files of the supporting graphics libraries. Basically, we

are building our library on top of two existing open source graphics libraries, to provide a more

convenient level of abstraction. If you are interested, this is explained a bit more in Background:

Images in SDL and STB. Those libraries, which are popular in computer game design, are in the

framework folder.

images: This directory contains image files used by our demo programs.

Helper Functions

manipulate.c: For the extra credit part, you are asked to write the image processing function

greenscreen(). It will go in this file. As mentioned before, do not include a main() in this file.

Instead, we can call the function from draw.c or any other test file you may create. To implement

our image processing function, we’ll rely on the image processing library you created in

image_basics.c.

Main C-program

draw.c: This program contains a main(). It is meant to illustrate and test the supporting

functions you created in image_basics.c and manipulate.c. You can modify this file as you

please for testing purposes. We will not ask you to submit it.

Our Debugging Library

The files prototypes.h and prototypes.o are not really part of the main code structure. We have

created them to help you debug and test your code. After you are done implementing your own

code, you won’t need them anymore. If you look in image_basics.c and manipulate.c, you will

notice that the functions you are asked to write are already there, but they call a demo version

of themselves. These demo versions are in prototypes.o, and are basically our solutions. It is

your task to delete the call to the demo code and write your own code instead that implements

the desired functionality.

Compiling Your Code

To compile your code, run the Makefile with the appropriate target (without the .c extension). For

example, to compile draw.c, type:

$ make draw

This will create the executable draw. You can do the same for the other C-program with a

main() that you may wish to create for testing purposes.

Testing Your Code

You will start this PA by writing your own library functions. It is important to test each individual

function thoroughly before moving on to the next one. This divide-and-conquer strategy for

building and verifying your code is an essential part of software design. The library functions

themselves only take a few lines of code, but involve a thorough understanding of the data

structures involved. It is important you struggle through this yourself as much as possible to

solidify your handle on these topics. We have provided you with debugging versions to compare

the behavior of your code against (see Our Debugging Library). You need to write your own

tests. You can do this by modifying draw.c, for example, or by creating your own .c program with

a main() specifically to test your functions.

Since you will be working with dynamic memory, it is advisable to also check that no memory

leaks occur. This is possible with the valgrind tool. The use of valgrind is briefly explained in

Chapter 7. For example, to run it on the executable draw:

$ valgrind ./draw

However, before you do so, you should set the constant SHOW in draw.c to 0 (and recompile).

As a result, the images will not be shown when executing draw (please go through the code in

draw.c and make sure you understand what SHOW does). The reason we have to do this is that

valgrind is not compatible with the image library we are building upon. The output of valgrind will

report any memory leaks.

When writing your own image processing function greenscreen() also make sure to

thoroughly test your code. Again, you can use draw.c as a starting point, but you should expand

it to more test cases (try different image sizes, etc.).

Throughout this PA, do not use global variables.

Working with Images

As mentioned earlier, there is a difference between how we conceptually think about images

and how they are stored internally. Our image processing library is meant to bridge that gap: it

provides an interface that corresponds to how we like to work with images and then translates

that to the actual low-level details under the hood. The low-level details of how to handle images

is done by the SDL and STB graphics libraries we are building on. Basically, they provide a lot

of useful functions for image handling, but they are not intuitive to work with. For example, they

do not store images as 2D objects. The purpose of our library is to enable us to think about

images in a more natural way and provide this as a convenient interface to the user.

We will start with the high-level conceptual view of how engineers typically think and work with

images, and then move to the implementation details of our library.

How We Think about Images

Images are nothing more than a collection of pixels, arranged in a rectangular grid. The

standard labeling convention is shown below. The coordinates are zero-indexed, which means

that the first pixel is at coordinate (0,0). Also, the origin is in the top-left corner, with the y-axis

pointing down. Each pixel is simply a set of RGB values, representing the color of that pixel (see

Background: Representing Colors).

Our Image Representation

It is up to the programmer to choose the data structure they want to use to hold this grid of RGB

values. The choice depends on the specific needs of the program, and often involves a tradeoff

between convenience and memory usage. To store the images in our library, we will be using a

custom data structure that is defined in image.h.

Each pixel in the image is represented by a new type Pixel, which is defined as the struct

shown below. It has the R (red), G (green) and B (blue) values of the pixel as the member fields.

An Image is also defined as a struct. The members width and height contain the dimensions of

the image in number of pixels. For the example in the earlier figure, width is 10 and height 7.

The third member field is a pointer to Pixel and this will be a pointer to dynamic memory.

The pixels member points to a dynamic 1D array of Pixels. The length of this array is the

total number of pixels in Image, so width*height. The pixels of our 2D image are packed into this

array row-wise (row-by-row). For the example below, pixels[0] is the pixel at (x,y)=(0,0), pixels[1]

the pixel at (1,0), pixels[2] the pixel at (2,0), pixels[3] the pixel at (0,1), and so on.

You may wonder why not use a 2D array instead? The reason is that we need a dynamic array

rather than a static one, as we don’t know a priori the dimensions of the image will contain. And

for dynamic memory, it turns out that creating 1D arrays is far easier and less error prone than

creating 2D versions. However, we want to create the illusion that we are working with a 2D

structure, which is much more natural to think about. This is where the library functions you will

be asked to build come in.

typedef struct {

int red;

int green;

int blue;

} Pixel;

typedef struct {

int width;

int height;

Pixel *pixels;

} Image;

Interfacing with Images

The goal of the library functions we are creating in Task 1 - Basic Image Processing Library

Functions is thus to provide a high-level interface to these data structures. With this interface,

image manipulations occur at a high level of abstraction without having to worry about

implementation details (e.g., how pixels are packed in the 1D dynamic array, etc.).

For example, suppose we have the Image called test_image as shown below. We could have

access the pixel at coordinate (0,1) as

However, image processing code would be much easier to write, debug and reason about if we

had a library function get_pixel(image, x, y) that returns the pixel at position (x,y) in an

image:

The benefit is that people can now think about images as 2D grids of pixels at certain

(x,y)-coordinates without having to worry about how they are represented internally.

x = test_image.pixels[3];

x = get_pixel(test_image, 0 , 1);

Assignment Details

Task 1 - Basic Image Processing Library Functions

First, you need to implement a few of the image processing library functions that provide access

to our image data structures (which were described in Interfacing with Images). The main goal is

for you to think through the details of the data structures (structs and dynamic memory

allocation). This is not trivial, as the data structures are reasonably complex. However, these

functions require very few lines of code. The challenge is mainly in understanding how to work

with structs, pointers and dynamic memory. To make your testing easier, we have provided

default implementations (as mentioned in Our Debugging Library).

All of the functions you need to implement here should go in image_basics.c. Your code has to

replace the demo functions calls that are provided.

Create Blank Image

Implement the function below:

Image create_blank_image(int width, int height)

It should create a blank image of a certain width and height. What this means in practice is that

it returns a variable of type Image that has the width and height members set appropriately. It

also needs to allocate the dynamic memory to hold all the Pixel values. When creating this

memory allocation, set all the Pixels to zero .

1

Free the Memory

This function should free the dynamic memory that was allocated with create_blank_image()

above.

void free_image(Image image)

Modify Pixel

This function sets the pixel at coordinate (x,y) to the value new_pixel.

void set_pixel(Image image, int x, int y, Pixel new_pixel)

Note that internally, the pixels of an image are stored in a 1D dynamic array. This function thus

provides the interface from our 2D conceptual view of images to the actual implementation in

specific data structures.

1 Since Pixels are structs, setting them to zero sets all the members of the Pixel struct to zero. This

means that red, green and blue are 0 for each pixel, representing the color black.

Read Pixel

This function does the opposite of set_pixel(). It returns the Pixel value in the image at

coordinate (x,y).

Pixel get_pixel(Image image, int x, int y)

Task 2 - Extra Credit: Green Screen Substitution (Optional)

This task is for extra credit. The goal is to do some interesting processing on an image, using

the functions you developed for the image processing library. Specifically, you need to

implement the following function in manipulate.c:

void greenscreen(Image *imagePtr, Image small_image)

This function does a green screen substitution. The idea is illustrated below. It copies the

non-green pixels of small_image into the top-left corner of the image referred to by

imagePtr. We consider a pixel green when G > 100 and R < 100 and B < 100.

Again, you can run the code in draw.c to see this function in action. Test this on images of

various sizes. Your code will be tested on other images. You may assume that small_image is

always smaller than the base image (so you don’t need to check for this).

Submission Instructions

To submit your assignment, run the following command:

$ submit PA6

This will turn in your files image_basics.c and manipulate.c. We will be testing your functions

with our own main(). Note that these two files cannot contain a main() function themselves.

Background: Representing Colors

Colors can be represented by mixing three

base colors. The way this is done on a

computer is by additive mixing. For example, if

you combine red light and green light, it will

appear as yellow. The image on the right

illustrates this idea. Only three light sources,

red, green and blue, are used to represent

(almost) all colors.

To represent a color on our computer, we only

need to specify the amount of red, green and

blue it contains. These are known as the RGB values. Typically, each of these is a

number between 0 and 255 (i.e., 8 bits). Below are some examples:

If you want to experiment with these

RGB values, most drawing programs

allow you to set them directly. For

example, on the right is a screenshot

from Paint under Windows. Similar

tools exist for iOS as well.

R = 255 G = 255 B = 255 R = 255 G = 255 B = 255

R = 0 G = 255 B = 0 R = 0 G = 0 B = 0

R = 0 G = 0 B = 255 R = 127 G = 127 B = 127

R = 0 G = 0 B = 100 R = 201 G = 237 B = 20

Background: Images in SDL and STB

Open Source Image Libraries

To implement the basic image functionalities, we used open source libraries. Our own library is

essentially a wrapper built on top of those. SDL2 (https://www.libsdl.org/) is a cross-platform

library that transparently wraps OpenGL (on Linux) or DirectX (on Windows). It is popular for

game design, and supports access to sound, interface devices and graphics hardware. Our

karel simulator was built in SDL2. We’re also using stb_image of the STB library

(https://stb.handmade.network/). The needed library are in the framework/ directory of the

starter code.

Why Wrapping these Libraries?

As mentioned earlier, the data structure used to store information does not have to correspond

directly to how we as humans like to think about that information. We saw, for example, how we

could represent our 2D images as a 1D dynamic array. Our library was meant to provide an

interface to make image manipulations convenient and easy to understand.

In principle, we could have decided to build our library functions directly upon the data

representation used by SDL and STB (which will be discussed next). Instead, we created the

Image and Pixel types as they are more intuitive and to give you some practice working with

dynamic memory and structs. But as a result, we also had to convert from the internal data

representation of SDL/STB to our data structures. This is done in image_rw.c and

image_show.c and the code there in turn calls functions you can find in the framework/

subdirectory.

Data Representation

Images are stored in both SDL and STB as dynamic arrays of type uint32_t (integers of 32 bits,

or 4 bytes). As in our Image data type, the pixels are stored in a 1D linear array in a row-wise

order. However, our Image data type has, in addition to the dynamic memory array, two member

fields that contain the dimensions of the image. As a result, we don’t need to store this

information in separate variables.

The type of data in the 1D array is also different, however. In the two open source libraries the

array represents the pixels as uint32_t values, rather than data of type Pixel. These 32-bit

uint32_t values encode the 8-bit R, G and B data for each pixel. There are two ways in which

this encoding is done, with the two libraries using different conventions on the order in which

red, green and blue are encoded.

This is illustrated in the figures below (the numbers underneath represent the bit positions). In

image_rw.c and image_show.c, there are functions that convert our Pixel data type to these

uint32_t representations. Have a look at that code and specifically the functions

pack_pixel_RGB(), unpack_pixel_RGB() and unpack_pixel_BGR(). They are a good example

of bit-wise operations in C.