In this assignment, well implement the Newton-Raphson algorithm and use the gradient-based edge detection algorithm from the previous assignment to implement the version of Hough Transform discussed in lectures 21 and 22.

Problem 1: Newton-Raphson Algorithm

Implement the function nra(poly_fexpr, g, n) that takes a function expression of a polynomial and two constants, g and n, where g is the initial guess and n is the number of iterations, and approximates a root of the polynomial specified by poly_fexpr starting with g and iterating the Newton-Raphson algorithm n times. Ten unit tests are given below.

Test 1

Lets approximate 2.

>>> import math

>>> fexpr = make_plus(make_pwr(x, 2.0), make_const(-2.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

1.41421356237

>>> math.sqrt(2)

1.4142135623730951

Test 2

Lets approximate 3.

>>> import math

>>> fexpr = make_plus(make_pwr(x, 2.0),

make_const(-3.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

1.73205080757

>>> math.sqrt(3)

1.7320508075688772

Test 3

Lets approximate 5.

>>> import math

>>> fexpr = make_plus(make_pwr(x, 2.0),

make_const(-5.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

2.2360679775

>>> math.sqrt(5)

2.23606797749979

Test 4

Lets approximate 7.

>>> import math

>>> fexpr = make_plus(make_pwr(x, 2.0),

make_const(-7.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

2.64575131106

>>> math.sqrt(7)

2.6457513110645907

Test 5

Lets approximate a solution to e^x = x².

>>> import math

>>> fexpr = make_e_expr(make_prod(make_const(-1.0), make_pwr(x, 1.0)))

>>> fexpr = make_plus(fexpr, make_prod(make_const(-1.0), make_pwr(x, 2.0)))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

0.703467422498

>>> math.e**(-0.703467422498) (0.703467422498)**2

7.449041383722488e-13

Test 6

Lets approximate 11.

>>> import math

>>> fexpr = make_pwr(x, 3.0)

>>> fexpr = make_plus(fexpr, make_const(-11.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

2.22398009057

>>> 11.0**(1.0/3.0)

2.2239800905693152

Test 7

Lets approximate 6.

>>> import math

>>> fexpr = make_pwr(x, 3.0)

>>> fexpr = make_plus(fexpr, make_const(-6.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

1.81712059283

>>> 6.0**(1.0/3.0)

1.8171205928321397

Test 8

Lets approximate a root of x³ + 2x + 2.

>>> import math

>>> fexpr = make_pwr(x, 3.0)

>>> fexpr = make_plus(fexpr, make_prod(make_const(2.0), make_pwr(x, 1.0)))

>>> fexpr = make_plus(fexpr, make_const(2.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

-0.770916997059

>>> x = -0.770916997059

>>> x**3 + 2*x + 2

9.388045896230324e-13

Test 9

Lets approximate a root of x³ + x 1.

>>> import math

>>> fexpr = make_pwr(x, 3.0)

>>> fexpr = make_plus(fexpr, make_pwr(x, 1.0))

>>> fexpr = make_plus(fexpr, make_const(-1.0))

>>> print(nra(fexpr, make_const(1.0), make_const(10000)))

0.682327803828

>>> x = 0.682327803828

>>> x**3 + x 1

-4.6407322429331543e-14

Test 10

Lets approximate a root of e^(5x) = 10 x.

>>> import math

>>> fexpr = make_e_expr(make_plus(make_const(5.0), make_prod(make_const(-1.0), make_pwr(x, 1.0))))

>>> fexpr = make_plus(fexpr, make_pwr(x, 1.0)) >>> fexpr = make_plus(fexpr, make_const(-10.0)) print(nra(fexpr, make_const(1.0), make_const(10000)))

3.06315259278

>>> x = 3.06315259278

>>> math.e**(5 x) + x 10

-1.298516849601583e-12

Save your implementation of nra() in cs3430_s19_hw11.py. The above unit tests are coded up in cs3430_s19_hw11.py as nra_ut_01(), nra_ut_02(), etc.

Problem 2: Line Detection with Hough Transform

Implement the function ht_detect_lines(img_fp, magn_thresh=20, spl=20) that takes a path to an image file, img_fp, the keyword magn_thresh that specifies a threshold value for gradient edge detection, and the keyword spl that specifies a support level for Hough Transform. The function returns four values the original image array, the image array with all detected lines drawn with blue color, the binary image array with all the edge pixels equal to 255 and non-edge pixels equal to 0, and the hough table.

The unit tests are below. All the images are in img/. In each figure, the left image is the original image, the middle image is the image with detected edges, and the right image is the image with detected lines. Your output for tests 1 7 should be similar to mine. When I say similar, I dont mean to say that your images with detected lines should be identical to mine pixel by pixel. What I mean is that you should be able to detect the same lines, because these images are fairly simple. Tests 8 12 dont have to be the same, because these images are much trickier. But, your implementation should detect at least a couple of meaningful lines in each image.

Save your implementation of ht_detect_lines() in cs3430_s19_hw11.py. Experiment with different values of magn_thresh and spl. The file cs3430_s19_hw11.py contains a test function for the tests below (e.g., ht_test_01() for Test 1, ht_test_02() for Test 2, etc.). Save your best values of magn_thresh and spl in these definitions. When we run unit tests, well call test functions only with the file paths so that for each test magn_thresh and spl will default to your best values.

Test 1

Lets detect lines in EdgeImage 01.jpg. Fig. 1 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/EdgeImage_01.jpg, magn_thresh=35, spl=110)

Test 2

Lets detect lines in EdgeImage 02.jpg. Fig. 2 shows the output images.

Figure 1: Test1: Edges and lines detected in EdgeImage 01.jpg.

Figure 2: Edges and lines detected in EdgeImage 02.jpg.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/EdgeImage_02.jpg, magn_thresh=35, spl=110)

Test 3

Lets detect lines in EdgeImage 03.jpg. Fig. 3 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/EdgeImage_03.jpg, magn_thresh=35, spl=110)

Test 4

Lets detect lines in envelope.jpeg. Fig. 4 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/envelope.jpeg, magn_thresh=35, spl=200)

Figure 3: Edges and lines detected in EdgeImage 03.jpg.

Figure 4: Edges and lines detected in envelope.jpeg.

Test 5

Lets detect lines in horline.png. Fig. 5 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/horline.png, magn_thresh=35, spl=100)

Test 6

Lets detect lines in verline.png. Fig. 6 shows the output images.

Figure 5: Edges and lines detected in horline.png.

Figure 6: Edges and lines detected in verline.png.

Figure 7: Edges and lines detected in cross.png.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/verline.png, magn_thresh=35, spl=100)

Test 7

Lets detect lines in cross.png. Fig. 7 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/cross.png,

magn_thresh=15, spl=200)

Test 8

Lets detect lines in tiles.jpeg. Fig. 8 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/tiles.jpeg,

magn_thresh=20, spl=450)

Test 9

Lets detect lines in kitchen.jpeg. Fig. 9 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/kitchen.jpeg, magn_thresh=15, spl=400)

Figure 8: Edges and lines detected in tiles.jpeg.

Figure 9: Edges and lines detected in kitchen.jpeg.

Figure 10: Edges and lines detected in road01.png.

Figure 11: Edges and lines detected in road02.png.

Test 10

Lets detect lines in road01.png. Fig. 10 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/road01.png,

magn_thresh=10, spl=250)

Test 11

Lets detect lines in road02.png. Fig. 11 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/road02.png,

magn_thresh=10, spl=210)

Test 12

Lets detect lines in road03.png. Fig. 12 shows the output images.

>>> img, lnimg, edimg, ht = ht_detect_lines(img/road03.png, magn_thresh=5, spl=205)

Figure 12: Edges and lines detected in road03.png.