Section A – input
The input to your program is the photo taken by the camera in the factory. This is available in a .ppm file called Buttons.ppm. This file is available under Assessments on Stream. Do not edit this file in any way.
If you accidently modify the file then download a fresh copy of the file from Stream.
Your program must be able to work with any such photo. Do not assume a specific number of buttons.
do not assume that buttons will always be in the same place in the photo.
(Hint: Before starting on your program, check that the .ppm file has no errors. Download Buttons.ppm from Stream and convert it to .bmp (or other format) and look at it. The display should look like this:
Just for interest – you can tell that the resolution of the camera is low because of the “stepped” edges to the buttons in the image. Actually, for many problems of this type (i.e. identifying defects in products) it is often better to use a black-and-white photo because the defects stand out more clearly.
Section B – understanding the problem
Like many “real-life” systems, this type of project can never be perfect (which is what makes real-life projects interesting). We do the best we can by noting the following:
Notes about the problem:
1.Buttons appear as white (or light grey) objects on a dark background. This is a black-and-white photo which means every pixel is a shade of grey (i.e. the R, G and B values are the same for each pixel). We define a pixel to be part of a button if its R (or G or B) value is greater than 128.
2.There will always be a few pixels around the edge of a button (depending on the shadows) that are darker than this and will thus not count as part of the button. This does not matter.
3.We need to know how to “identify” a button. Basically we look for pixels where the R value is greater than 128. But we need more than this – see next section below.
4.To draw a box around a button you need to know the minimum and maximum x-value of all pixels in the button and also the minimum and maximum y-value of all pixels. The box then has a top left corner of (xmin, ymin) and a bottom right corner of (xmax, ymax) and so on.
5.Some thought needs to be given to how we define a “damaged” button. This is entirely up to you.
Hint: a damaged button will have less total pixels than an undamaged button.
Section C – the algorithm to identify a button in the image
A button consists of pixels with R value greater than 128 AND the pixels must touch each other. If we work through every pixel, we can identify a button by:
- a) finding a pixel with R value greater than 128
- b) finding all other pixels that connect to that pixel (and have R value greater than 128)
- c) go back to where we were in (a) and continue
The image below is trying to show this. Step (a) is shown in yellow. We start at the top left and work steadily across and down the image until we find a suitable pixel. Step (b) is shown in red – we find all pixels connected to the first one. Step (c) is shown in green – we go back to where we were at step (a) and continue looking for pixels with R value greater than 128. Note that this diagram is to get the idea – the drawing is not perfect.
Now let us look at step (b) in more detail – if we have one pixel in the button, how do we find the others?
Assume that we have found pixel A at location (x, y) with an R value of greater than 128. Thus we know that pixel A is inside a button. We can then work through the pixels that touch pixel A (they are pixels B,C, D and E). Note the locations of these pixels. Pixel B is in the same row of the image as pixel A so has the same y value. But pixel B is one place to the left so it has a x value of x – 1. Pixel E is in the same vertical column of the image as pixel A so has the same x value. But pixel E is one place further down the screen so it has a y value of y + 1. Similarly for the other pixels.
Now that we know how to identify the “next door” pixels of pixel A, we have an algorithm as follows:
Find pixel A at location (x, y) and look for all connected pixels by:
Find pixel B at location (x – 1, y) and look for all connected pixels;
Find pixel C at location (x + 1, y) and look for all connected pixels;
Find pixel D at location (x, y – 1) and look for all connected pixels;
Find pixel E at location (x, y + 1) and look for all connected pixels;
This is a recursive algorithm – find the pixels connected to A by finding the pixels connected to B, etc.
While this may not look like the famous “caves” program, it is essentially the same situation. And we have the same problem. We could develop an infinite loop where pixel A checks pixel B which checks pixel A which checks pixel B, etc. And we solve the problem in the same way, i.e. we put a boolean into each pixel and as soon as we have checked a pixel we exclude it from the search. Do not check that pixel again.
Every recursive function needs a base case. In this case there are two which are:
– return if the pixel you are checking has an R values of 128 or less
– return if this pixel is excluded from the search (i.e. if this pixel has been checked before)
Some astute readers may have noticed that we are going on as if they are FOUR pixels next door to pixel A when in fact there are EIGHT next door pixels. We left out the diagonal pixels. The reason for this is that the recursion eventually works its way through all adjacent pixels. E.g. the pixel that is up and to the left of A is also above B so will be checked when B is checked.
Section D – program design
There was another programmer who used to work at the factory. Unfortunately, that programmer did not study 159.102 at Massey and was therefore unable to complete the project. You may find some interesting ideas in the partially completed program which is called Ass3-start.cpp and is available under Assessments on Stream.
Download the program called Ass3-start.cpp and study it.
You MUST use the class called pixel_class. Note that two of the methods are at the end of the program.
This class is as discussed in the notes but has an extra boolean variable called exclude to assist with the recursive function. This exclude variable is set to false at the start of the program and is set to true if this particular pixel has been checked.
EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!
E-mail: email@example.com 微信:easydue