COMP0005 Algorithms Coursework 2
Algorithms作业代写 Compare the performance of quicksort and heapsort for various input sizes, from 100K to 10M. Perform the experiment 10 times
1.ompare the performance of quicksort and heapsort for various input sizes,Algorithms作业代写
from 100K to 10M. Perform the experiment 10 times, where each time, the input is randomized. Plot 10 graphs, one for each run. Comparison should be based on (i) number of comparisons and exchanges, and (ii) run time. Average the results of the 10 runs and plot a single graph of the average (time or total number ofcomparisons and exchanges) together with the standard deviation. Discuss the
2.When our eyes view a scene, the left and right eyes see slightly different things. The left and right images are known as a stereo pair. By matching corresponding points in the two images, we are able to infer depth. Theattached paper http://www.bmva.org/bmvc/1992/bmvc-92-035.pdf proposes using a dynamic programming algorithm to perform stereo matching. Implement the algorithm.Algorithms作业代写
Please note first the following points:
- We will only focus our study on grayscale images, i.e. only one scalar value by pixel (pixel intensity). Therefore, vectors and matrices collapse to scalar valuesin that specific case (specifically, the covariance matrix becomes the variance).
- The algorithm given on page 341 will allow you to do the forward pass and thus build the cost matrix. The parameters to tune the model are givenin
the « Experimental Results » section. Be careful, you will need to store which of the three costs (see paper) have been chosen for each i and j to reconstruct the optimal match:Algorithms作业代写
1] C(i-1,j-1)+c(z1i,z2j), i.e. pixels i and j do match;
2] C(i-1,j)+occlusion, i.e. pixel i is unmatched;
3] C(i,j-1)+occlusion, i.e. pixel j is unmatched.
You will need to implement the backward pass to infer depth. This part is not documented in the paper but follow the following procedure:
Starting from i=M and j=N (and until i=0 and j=0), you will move along one of the three arrows starting from the current point:
-going up: if pixel i isunmatched;
-going left: if pixel j isunmatched;
-going upper left: if pixels i and j
The distance between pixel i and j (if they match) is linked to the depth and is called disparity. As an output of the algorithm, you should display the disparity map (showing the disparity for each pixel).Algorithms1代写
To study the algorithm, create a synthetic random dot stereogram:
(i)create a 512×512 image A of random black and white pixels (0 and 255 as pixel values),
(ii)create a second 256×256 image B of random black and white pixels (0 and 255as pixel values),
(iii)now create a left image L by placing the 256×256 image B into the 512×512 image A such that the top-left corner of the 256×256 image B starts at(124,128),
(iv)now create the right image R by placing the top-left corner of the 256×256 image B at(132,128).Algorithms作业代写
You should apply the stereo matching algorithm on the pair of images (L,R). Provide results for the additional images provided here as well.
Please comment on the results and answer the following questions:
–Why do matching errors occur for the binary random dotstereograms?
–Investigate how the algorithm performs on other images as the occlusion costis varied.
–For string matching, what is the equivalent ofocclusion?
其他代写：java代写 function代写 web代写 编程代写 数学代写 algorithm代写 python代写 project代写 dataset代写 analysis代写 C++代写 代写CS 金融经济统计代写 essay代写 assembly代写 program代写 code代写 作业代写
