CS3430-Assignment 11 Newton-Raphson Algorithm and Line Detection with Hough Transform Solved

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
√

Let’s 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
√

Let’s 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
√

Let’s 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
√

Let’s 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
Let’s approximate a solution to e−x = x2.

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
Let’s 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
Let’s 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
Let’s approximate a root of x3 + 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
Let’s approximate a root of x3 + 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
Let’s approximate a root of e(5−x) = 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 don’t 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 don’t 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, we’ll 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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
Let’s 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.