Question 3 (12 points): Purpose: To practice building a recursive algorithm, to review arrays and list comprehensions, to do some- thing real Degree of Difficulty: Tricky, Dr Stanley style Representing the complexity of curves in two dimensional space is often done by calculating a fractal di- mension. For a curve in 2D space, calculating the fractal dimension returns a number between 1 la line) and 2 (a filled 2D shape). The closer the number is to two, the gnarlier and more complex the curve. This kind of calculation has direct application in geomatics, image processing, and spatial analytics Some simple fractal curves can have their fractal dimension calculated from first principles. Most, however, require an approximation One popular approximation is the box counting method. 2 Box counting covers an image with boxes, like tiles, then asks how many boxes contain the curve. The pro- cess is repeated for ever smaller boxes, until enough points are found to calculate the dimension according to: (1) dimor(s) Log(N) log(1/0) where dimor (S) is the fractal dimension, N, is the number of boxes containing the curve at the scale of . and 1/e is the inverse of the scale. In the following exercise, the scaling factor is always so the inverse will always be 2. A classic example of fractal dimension is determining the complexity of the British coastline. as shown in Fig 1 Knowing that we have to make a bunch of boxes and count pixels in them isn't necessarily recursive. You could imagine dividing an image up into squares, like tiles, then counting each iteratively from top left to bottom right, like reading in English However, this can lead to issues if your increment or origin shifts. A potentially more principled way of making smaller squares is called a quadtree expansion In a quadtree expansion, you take the original image, and divide it into four equal squares. (This often requires padding the image to be exactly square, but we will ignore this issue and assume we have a perfectly square image). Each square made from the first square is then further subdivided into four smaller squares and so on, until a minimum number of pixels remains in each square. This forms a special kind of data strutture called a tree, where the parent is made of four children and so on down the line, making something that looks like a Christmas tree. By ensuring that all smaller squares are exactly contained in larger squares, issues related to origin and resolution choice can be reduced. An example of a quadtree geometry and part of the resulting tree are shown in Fig. 27 Program Design You have been provided with a starter file (a8q3-starter.py) which contains several functions. The first function open image uses the PIL library to open an image, convert it to a numpy array, and make it binary (black and white) . The output of this function is a numpy array containing 1 for not part of a curve) or 0 (for part of a curve). Curves are drawn black on white, simply because they look cooler that way. The second function calculates whether or not a numpy array contains at least one zero by using the special numpy function texttttallo which literally checks to see if all elements of the provided array are not zero Because we know that the curve is zero, if anl) retums False then an image must contain at least some of the curve. Finally, you have been given a plot and fit function plot_line_fit which take x and y arrays in this case the log of the inverse scale and box count) and plots those points and the best fittine through them. The slope of the line (which is an approximation of the dimension according to the equation above) is returned. Finally you have also been given the header of the main recursive function you have to write splat_into_four, which takes an image, an integer corresponding to the level (how many splits) and list Question 3 (12 points): Purpose: To practice building a recursive algorithm, to review arrays and list comprehensions, to do some- thing real Degree of Difficulty: Tricky, Dr Stanley style Representing the complexity of curves in two dimensional space is often done by calculating a fractal di- mension. For a curve in 2D space, calculating the fractal dimension returns a number between 1 la line) and 2 (a filled 2D shape). The closer the number is to two, the gnarlier and more complex the curve. This kind of calculation has direct application in geomatics, image processing, and spatial analytics Some simple fractal curves can have their fractal dimension calculated from first principles. Most, however, require an approximation One popular approximation is the box counting method. 2 Box counting covers an image with boxes, like tiles, then asks how many boxes contain the curve. The pro- cess is repeated for ever smaller boxes, until enough points are found to calculate the dimension according to: (1) dimor(s) Log(N) log(1/0) where dimor (S) is the fractal dimension, N, is the number of boxes containing the curve at the scale of . and 1/e is the inverse of the scale. In the following exercise, the scaling factor is always so the inverse will always be 2. A classic example of fractal dimension is determining the complexity of the British coastline. as shown in Fig 1 Knowing that we have to make a bunch of boxes and count pixels in them isn't necessarily recursive. You could imagine dividing an image up into squares, like tiles, then counting each iteratively from top left to bottom right, like reading in English However, this can lead to issues if your increment or origin shifts. A potentially more principled way of making smaller squares is called a quadtree expansion In a quadtree expansion, you take the original image, and divide it into four equal squares. (This often requires padding the image to be exactly square, but we will ignore this issue and assume we have a perfectly square image). Each square made from the first square is then further subdivided into four smaller squares and so on, until a minimum number of pixels remains in each square. This forms a special kind of data strutture called a tree, where the parent is made of four children and so on down the line, making something that looks like a Christmas tree. By ensuring that all smaller squares are exactly contained in larger squares, issues related to origin and resolution choice can be reduced. An example of a quadtree geometry and part of the resulting tree are shown in Fig. 27 Program Design You have been provided with a starter file (a8q3-starter.py) which contains several functions. The first function open image uses the PIL library to open an image, convert it to a numpy array, and make it binary (black and white) . The output of this function is a numpy array containing 1 for not part of a curve) or 0 (for part of a curve). Curves are drawn black on white, simply because they look cooler that way. The second function calculates whether or not a numpy array contains at least one zero by using the special numpy function texttttallo which literally checks to see if all elements of the provided array are not zero Because we know that the curve is zero, if anl) retums False then an image must contain at least some of the curve. Finally, you have been given a plot and fit function plot_line_fit which take x and y arrays in this case the log of the inverse scale and box count) and plots those points and the best fittine through them. The slope of the line (which is an approximation of the dimension according to the equation above) is returned. Finally you have also been given the header of the main recursive function you have to write splat_into_four, which takes an image, an integer corresponding to the level (how many splits) and list