Programming Parallel Computers 2020

Exercise IS: image segmentation

Detailed specification

You need to implement the following function:

Result segment(int ny, int nx, const float* data)

Here data is a color image with ny*nx pixels, and each pixel consists of three color components, red, green, and blue. In total, there are ny*nx*3 floating point numbers in the array data.

The color components are numbered 0 <= c < 3, x coordinates are numbered 0 <= x < nx, y coordinates are numbered 0 <= y < ny, and the value of this color component is stored in data[c + 3 * x + 3 * nx * y].

Correct output

The function has to return an instance of the following structure that indicates the optimal segmentation:

struct Result {
    int y0;
    int x0;
    int y1;
    int x1;
    float outer[3];
    float inner[3];
};

The first four fields indicate the location of the rectangle. The upper left corner of the rectangle is at coordinates (x0y0), and the lower right corner is at coordinates (x1-1y1-1). That is, the width of the rectangle is x1-x0 pixels and the height is y1-y0 pixels. The coordinates have to satisfy 0 <= y0 < y1 <= ny and 0 <= x0 < x1 <= nx.

The last two fields indicate the color of the background and the rectangle. Field outer contains the three color components of the background and field inner contains the three color components of the rectangle.

Objective function

For each pixel (x,y) and color component c, we define the error error(y,x,c) as follows:

The total cost of the segmentation is the sum of squared errors, that is, the sum of error(y,x,c) * error(y,x,c) over all 0 <= c < 3 and 0 <= x < nx and 0 <= y < ny.

Your task is to find a segmentation that minimizes the total cost.