Description
Machine perception
2021/2022
Create folder assignment3 that you will use during this assignment. Unpack the content of the assignment3.zip that you download from the course webpage the folder. Save the solutions for the assignments as Python scripts assignment3 folder. In order complete the exercise you have present these files the teaching assistant. Some assignments contain questions that require sketching, writing manual calculation. Write these answers down and bring them the presentation as well. The tasks that marked with (cid:70) optional. Without completing them you get at points for the exercise. The maximum total amount of points for each assignment is 100. Each optional task has the amount of additional points written next it.
Introduction
For additional explanation of the theory, required for the following assignment, check the slides from the lectures as well as scientific literature these topics version of the book by Forsyth in Ponce also found online – the related theory is located in chapters and
Exercise Image derivatives
The first and the second exercise will deal with the problem of detecting edges in images. way of detecting edges is by analyzing local changes of grayscale levels. Mathematically this means that we computing image derivatives. The downside of image derivative at certain point in the image is that it sensitive image noise. Thus, it is common soften the image beforehand with narrow filter Ib(x, = G(x, ∗ I(x, and only then calculate the derivative.
Usually, Gaussian filter is used smooth the image. As we will use partial derivatives in the following exercises, we will first look at the decomposition of the partial derivative of the Gaussian kernel. 2-D Gaussian kernel written as product of 1-D kernels as:
therefore image filtering for image I(x, formulated as
G(x, = g(x)g(y),
Ib(x, = g(x) ∗ g(y) ∗ I(x,
Taking into account the associative property of the convolution d
dx(g ∗ f ) = ( d
dx ∗ f ,
we write partial derivative of the smoothed image with respect as:
Ix(x, =
δ δx
(cid:104)
(cid:105) g(x) ∗ g(y) ∗ I(x,
=
g(x) ∗
(cid:105) (cid:104) g(y) ∗ I(x,
.
d dx
This means that the input image first filtered with Gaussian kernel with respect and then filter the result with the derivative of the Gaussian kernel with respect Similarly, we define the second partial derivative with respect however, we have remember always filter the image before we perform derivation. The second derivative with respect is therefore defined as partial derivative of already derived image:
Ixx(x, =
(cid:105) (cid:104) g(x) ∗ g(y) ∗ Ix(x,
=
δ δx
g(x) ∗
(cid:105) (cid:104) g(y) ∗ Ix(x,
.
d dx
Follow the equations above and derive the equations used compute first and second derivatives with respect Iy(x, Iyy(x, as well as the mixed derivative Ixy(x,
Implement function that computes the derivative of 1-D Gaussian kernel. The
formula for the derivative of the Gaussian kernel is:
d dx
g(x) =
d dx
exp(−
√
2πσ 2πσ3
2σ2 ) 2σ2 ).
= −
√
exp(−
Implement the function gaussdx(w, sigma) that works the same as function gauss from the previous assignment. forget normalize the kernel. careful as the derivative is odd function, simple sum will not Instead normalize the kernel by dividing the values such that the sum of absolute values is Effectively, you have divide each value by (cid:80) abs(gx(x)).
The properties of the filter analyzed by using impulse response function. This is performed as convolution of the filter with Dirac delta function. The discrete version of the Dirac function is constructed as finite image that has all elements 0 except the central element, which is high value (e.g. 255).
impulse = np.zeros((25,25)) impulse[12,12]=255
Generate 1-D Gaussian kernel and Gaussian derivative kernel D.
What happens if you apply the following operations the impulse image?
First convolution with and then convolution with GT .
First convolution with and then convolution with .
First convolution with D and then convolution with GT .
(d) First convolution with GT and then convolution with D.
First convolution with and then convolution with
Is the order of operations important? Display the images of the impulse responses for different combinations of operations.
(d) Implement function that uses functions gauss and gaussdx compute both
partial derivatives of given image with respect and with respect
Similarly, implement function that returns partial second order derivatives of given image.
Additionally, implement the function gradient_magnitude that accepts grayscale image and returns both derivative magnitudes and derivative angles. Magnitude is calculated as m(x, = (cid:112)(Ix(x, + Iy(x, and angles calculated as φ(x, = arctan(Iy(x, y)/Ix(x, Hint: Use function np.atan2 avoid division by zero for calculating the arctangent function.
Use all the implemented functions the same image and display the results in the same window.
(cid:70) points) Gradient information is often used in image recognition. Extend your image retrieval system from the previous assignment use simple gradient-based feature instead of color histograms. calculate this feature, compute gradient magnitudes and angles for the entire image, then divide the image in × grid. For each cell of the grid compute bin histogram of gradient magnitudes with respect gradient angle (quantize the angles into values, then for each pixel of the cell, add the value of the gradient the bin specified by the corresponding angle). Combine all the histograms get single 1-D feature for every image. Test the new feature the image database from the previous assignment. Compare the new results the color histogram based retrieval.
Exercise Edges in images
of the widely used edge detector algorithms is Canny edge detector. In this exercise you will implement parts of Canny’s algorithm.
Firstly, create function findedges that accepts image and the parameters
sigma and theta.
The function should create binary matrix Ie that only keeps pixels higher than threshold theta:
Ie(x, =
(cid:26) ; Imag(x, ≥ ϑ
0
; otherwise
Test the function with the image museum.png and display the results for different values of the parameter theta. you the parameter that all the edges in the image clearly visible?
Using magnitude produces only first approximation of detected edges. Unfortu- nately, these often wide and we would like only return edges pixel wide. Therefore, you will implement non-maxima suppression based the image deriva- tive magnitudes and angles. Iterate through all the pixels and for each search its 8-neighborhood. Check the neighboring pixels parallel the gradient direction and the current pixel 0 if it is not the largest in the neighborhood (based derivative magnitude). You only need compute the comparison actual pixels, interpolating accuracy is not required.
(cid:70) points) The final step of Canny’s algorithm is edge tracking by hysteresis. Add the final step after performing non-maxima suppression along edges. Hysteresis uses thresholds tlow < thigh, keeps all pixels above thigh and discards all pixels below tlow. The pixels between the thresholds kept only if they connected pixel above thigh.
Hint: Since we looking for connected components containing at least pixel above thigh, you could use something like cv2.connectedComponentsWithStats extract them. Try avoid explicit for loops as much as possible.
Exercise Detecting lines
In this exercise we will look at the Hough algorithm, in particular the variation of the algorithm that is used detect lines in image. For information about the theory look at the lecture slides as well as the literature and web applet that demonstrates the Hough transform, e.g.
We have point in the image p0 = (x0, y0). If we know that the equation of line is = mx + which all the lines that running through the point p0? The answer is simple: all the lines whose parameters and correspond the equation y0 = mx0 If we fix the values (x0, y0), then the variable parameters again describe line, however, this the line is in the space that we also call the parameter space. If we consider new point = this new point also has line in the space. This line crosses the p0 line in point (m(cid:48), n(cid:48)). The point (m(cid:48), c(cid:48)) then defines line in space that connects the points p0 and
Question: Analytically solve the problem by using Hough transform: In space you given points (0, 0), 0), Define the equations of the lines that run through at least of these points.
If we want find all the lines in image using the Hough approach in program, we have proceed as described. The parameter space is first quantized as accumulator matrix. For each edge pixel we draw corresponding line in the space in additive manner (increase the value by All the image elements that lie the same line in the input image will generate lines in the space that will intersect at the same point and therefore increase the value of the same accumulator cell. This means that local maxima in the space define the lines in the input image that contain lot of the detected edge pixels.
In real scenarios the = mx + formulation of line is inefficient. This is especially apparent in the case of vertical lines, there becomes infinite. This problem avoided by different line parametrization, for example using polar coordinates. In this
case the equation of line looks like
cos(ϑ) + sin(ϑ) = ρ.
The algorithm remains less the same, the only difference is that point in the
space generates sinusoid in the (ϑ, ρ) space. For points and ( corresponding curves in the parameter space shown in the figure below.
Create array with single nonzero point. Then, create accumulator array defined by the resolution ρ and ϑ values. Calculate the sinusoid that represents all the lines that pass through the nonzero point in your array. Increment the corre- sponding cells in the accumulator array. Experiment with different positions of the nonzero point how the sinusoid changes. You the number of accumu- lator bins each axis 300 begin with.
Implement the function hough_find_lines that accepts binary image, the number of bins for ϑ and ρ (allow the possibility of them being different) and threshold.
Create the accumulator matrix for the parameter space (ρ, ϑ). Parameter ϑ is defined in the interval from −π/2 π/2, ρ is defined the interval from −D D, where D is the length of the image diagonal. For each nonzero pixel in the image, generate curve in the (ρ, ϑ) space by using the equation for all possible values of ϑ and increase the corresponding cells in Display the accumulator matrix. Test the method your own synthetic images (i.e. some nonzero pixels manually).
Finally, test your function synthetic images, oneline.png and rectan- gle.png. First, you should obtain edge map for each image using either your function findedges some inbuilt function. Run your implementation of the Hough algorithm the resulting edge maps.
The sinusoids usually intersect in only point, resulting in than tected line. Implement function named nonmaxima_suppression_box that checks the neighborhood of each pixel and it 0 if it is not the maximum value in the neighborhood (only consider 8-neighborhood).
(d) Search the parameter space and extract all the parameter pairs (ρ, ϑ) whose cor- responding accumulator cell value is greater than specified threshold threshold. Draw the lines that correspond the parameter pairs using the draw_line function that you find in the supplementary material.
Read the image from files bricks.jpg and pier.jpg. Change the image grayscale and detect edges. Then detect lines using your algorithm. As the results will likely depend the number of pixels that vote for specific cell and this depends the size of the image and the resolution of the accumulator, try sorting the pairs by their corresponding cell values in descending order and only select the top = lines. Display the results and experiment with parameters of Hough algorithm as well as the edge detection algorithm, e.g. try changing the number of cells in the accumulator σ parameter in edge detection obtain results that similar better the ones shown the image below.
(f) (cid:70) points) problem of the Hough transform is that we need new dimension for each additional parameter in the model, which makes the execution slow for
complex models. We avoid such parameters if we reduce the parameter space, e.g. by introducing domain knowledge. Recall from the previous exercise that we get the local gradient angle besides its magnitude. This angle is perpendicular the edge and used limit the scope of the parameter ϑ for specific edge point. We therefore not have increase the values of the cells of the entire range of ϑ (calculate multiple values of ρ), but use the local angle and only work with single (ρ, ϑ) pair for each edge point.
Copy your implementation of the line detector new function and modify the algorithm that it also accepts the matrix of edge angles. Note that the angle values were probably calculated using the np.atan2(dy, dx) function that returns the values between −π and π. You have adjust the angles that they within the [−π/2, π/2] interval. Test the modified function several images and compare the results with the original implementation.
(cid:70) points) Implement Hough transform that detects circles of fixed radius. You test the algorithm image eclipse.jpg. Try using radius somewhere between and pixels.
(cid:70) points) Not all lines accumulate the same number of votes, e.g. if the image is not rectangular, candidates along the longer dimension in better position. Extend your algorithm that it normalizes the number of votes according the maximum number of votes possible for given line (how many pixels does line cover along its crossing of the image). Demonstrate the difference some non- rectangular images where the difference shown clearly.
References
D. Forsyth and Ponce. Computer Vision: Modern Approach. Prentice Hall,
D. Forsyth and Ponce.
Computer vision: modern approach line version). http://www.cs.washington.edu/education/courses/cse455/02wi/ readings/book-7-revised-a-indx.pdf,
Simon Hohl.
Interactive hough transform.
http://dersmon.github.io/
HoughTransformationDemo/.
Woods, Gonzalez, and Wintz. Digital Image Processing, ed. Pearson
Education,
