Please read the general instructions on this page first, and then check the individual tasks for more details. For each task you can download a zip file that contains the code templates you can use for development.

Task | Attempts | Points | Max | Rating | Rec. | Deadline for full points |
---|---|---|---|---|---|---|

IS4: fast solution | ||||||

Using all resources that you have in the CPU, solve the task |
||||||

– | – |
5 + 2 | ★★ | R | 2023-03-26 at 23:59:59 | |

IS6a: fast CPU solution for 1-bit images | ||||||

In this task, the input is always a monochromatic image: each input pixel is either entirely |
||||||

– | – |
5 + 2 | ★★★ | R | 2023-04-16 at 23:59:59 | |

IS6b: fast GPU solution for 1-bit images | ||||||

Port your solution to IS6a to the |
||||||

– | – |
5 + 2 | ★★ | R | 2023-04-16 at 23:59:59 | |

IS9a: better algorithm | ||||||

Design a more efficient algorithm that (at least in typical cases) does not need to try out all possible locations of the rectangle. Implement the algorithm efficiently on the CPU. |
||||||

– | – |
5 + 0 | ★★★ | R | 2023-04-16 at 23:59:59 |

Find the best way to partition the given figure in two parts: a monochromatic rectangle and a monochromatic background. The objective is to minimize the sum of squared errors.

We have already defined the following type for storing the result:

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

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]`

.

In the `Result`

structure, the first four fields indicate the **location** of the rectangle. The upper left corner of the rectangle is at coordinates (`x0`

, `y0`

), and the lower right corner is at coordinates (`x1-1`

, `y1-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.

For each pixel (`x,y`

) and color component `c`

, we define the error `error(y,x,c)`

as follows:

- Let
`color(y,x,c) = data[c + 3 * x + 3 * nx * y]`

. - If (
`x,y`

) is located outside the rectangle:`error(y,x,c) = outer[c] - color(y,x,c)`

. - If (
`x,y`

) is located inside the rectangle:`error(y,x,c) = inner[c] - color(y,x,c)`

.

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.

In IS4, IS6a, and IS6b tasks you are expected to use an algorithm that tries out all possible locations 0 ≤ y0 < y1 ≤ ny and 0 ≤ x0 < x1 ≤ nx for the rectangle and finds the best one. However, for each candidate location you should only perform O(1) operations to evaluate how good this position is. To achieve this, some preprocessing will be needed.

In IS9a you are expected to design a more efficient algorithm that (at least in typical cases) does not need to try out all possible locations of the rectangle. In IS9a your submission will be graded using a structured input that might resemble e.g. a real-world image in which some candidate positions are much better than others.

These examples show the segmentation produced by a correct implementation (right) for some sample images (left). Hover the mouse on the output to better see the segmentation.

Spend some time with pen and paper first to get the math right. You need to find a very efficient way of checking which of the candidate positions are best. There is a fairly straightforward solution in which for each candidate position you will only need to do a few array lookups (to a precomputed array) and a few arithmetic operations to calculate an indicator for the quality of this position.

Remember that the average minimizes the sum of squared errors.

Use the inclusion–exclusion principle to quickly calculate the sum of values within a rectangle — if you can look up the orange and blue sums from a precomputed array, you can also calculate the sum of the gray area:

It may be helpful to organise the loops so that the outer loop tries out different **sizes** of the rectangle, and the inner loop tries all possible **positions** of the rectangle. Then in the innermost loop you only need to be able to compare candidate positions for rectangles with the same size. Precompute everything that you can outside the innermost loops.

Here is one approach: First use a coarse grid, with e.g. 10 × 10 pixels per grid cell. Then try all possible ways to place the rectangle in this coarse grid. Each coarse location represents a set of approx. 10000 fine-grained locations (so it is much faster to try out all possible coarse locations). For each coarse location, calculate the following two estimates (efficiently, in constant time):

**An upper bound:**at most how much is the cost if I place the rectangle in some of the fine-grained locations that are represented by this coarse-grained location?**A lower bound:**at least how much is the cost if I place the rectangle in some of the fine-grained locations that are represented by this coarse-grained location?

After these calculations, you can hopefully rule out a majority of coarse-grained locations: you know that there are other locations where the cost is **at most** some value *s*, so you can then ignore all coarse-grained locations where the cost is **larger than** *s*.

Finally, zoom in to those coarse-grained locations that you have not yet ruled out.