The implementation of the least square algorithm requires matrix algebra setup.
For that, we could either use a predefined matrix library or make our own multiplication and inverse functions. We chose the latter because it was not
4.3 Binary Extraction 43
hard to implement and we wanted to make sure that we did it right and had complete control.
To name them all, we have
• MatrixInverse
MatrixMultiplicationare self explanatory. GetMinor, is a method to get the submatrix from a matrix. A submatrix is obtained by deleting a number of rows or columns in any given matrix.
In the implementation, we define two-dimensional array and instantiate the ma-trices defined in the design section. We create the normalized path lengths by taking the Pythagorean distance between each points and dividing each addi-tional length with the number of points (as noted in3.2)
Next we setup the matrix from all the lengths and the matrices composed by the x- and y-values, respectively. After this, it is a matter of multiplying all the matrices together, which result in our control points’ respective x- and y-values.
The overall implementation of the least square algorithm is very similar to the formulas defined in the design section3.4. The implementation can be furtherly checked on Appendix C, which is also very similar to the implementation from Jim Herold [Her12].
4.3 Binary Extraction
In Unity3D, the first thing we need to know is how to access a camera de-vice’s pixels. Then we need to edit and manipulate them through scripting (see Scripting API [API14b]).
We see thatWebcamTexturealong withWebcamDevicehas a way of getting color pixels from the camera with a defined size. We chose to work with 160x120 because we believe it is sufficient. We could, in principle, work with larger resolution. It would affect performance and enhance precision of reading from the paper. We chose this resolution because we saw it suitable for real-time
generation.
The color pixels we get can be thought of as a matrix with each cell consisting of a vector of size 4 containing RBGA colors.
Figure 4.2: Color pixels. Each color consists of RGBA values.
4.3.1 Color identification
Most of the pixels that we take from the camera snapshot, will naturally be white with black lines, indicating the road. We assume that the camera is pointed right at the paper, with no background colors on the edges. If we decided to take the edges into consideration and focus on user experience, we would rather run into a detailed image analysis of the snapshot. As we had limited time, we decided to keep it simple.
From the readings of the pixels, we simply take their RGBA color values, and define them as black, if they exceed a certain threshold. In this way, we can easily get the values we want to manipulate with and omit the other color values.
We set all the black color pixels to 1 and other ones to 0. Here is an example of such a reading (Figure4.3a).
4.3.2 Scaling
The way we do scaling is by taking one spot and transforming it into a many.
When scaling with a factorf, the size of the set will be scaled with a factorf2. So in the example of a factor of 4, we get a binary data with a size which is 16 times as big.
When creating the scaled binary, we take the values from the small binary and insert them in the bigger binary as shown on Figure 4.4. We can setup the
4.3 Binary Extraction 45
(a)Thick road (b)Thin road
Figure 4.3: Thick and thin road.
Figure 4.4: The result after scaling with a factor of 2
following relations for the index of the old values (x, y)and new values(x0, y0) wheresis the scale.
x0 ∈[x;x+s−1] y0∈[y;y+s−1]
We then have to do every combination of(x0, y0)in order to get all values in the scaled binary data.
4.3.3 Thickening
When we do thickening, we do not want the size of the binary array to grow any bigger. We just want the neighbours of any 1s in the binary data to become 1s.
Figure 4.5: The result after one iteration of thickening
We start off by creating a copy of the reference binary array. We will only make changes is only in the copy binary, and at the end of each iteration we use the copy becomes the reference array. We traverse every field in the reference array and check if the value is 1. If it is, we will change its neighbours 1.
4.3.4 Thinning
As mentioned earlier, we want to go from a thick road to a thin road . To thin, we simply define the filters (Figure3.8) as mentioned in section3.5, and apply them. Additionally, we want the road to keep its width the way the snapshot is taken, so we don’t omit this information. Instead of setting the thinned black pixel to 1, we increment it for each time the filter is detected. That means if we have the first case on Figure3.8, the below number will be set to 2, indicating that the road width here is 2. We continue the thinning in both directions so we get the full picture (Figure4.3b).
4.3.5 Zhang-Suen thinning
The way we decided to implement this algorithm, was to have an input and output array. Thereby any changes made to one array would not affect calcula-tions. At the end of each iteration of the algorithm, all the values of the output array are copied to the input array, and we start over with the new values, until no further changes are detected.