2020 Computer VisionAssignment 1: Disparity estimation1 IntroductionIn this practical you will research, implement and test some image filteringoperations for the purpose of estimating the disparity between two images.Image filtering is a fundamental step in many computer vision tasks, and youwill find it useful to have a firm grasp of how it works. Furthermore, practicalexperience with image matching will give you insight into and appreciationof the challenges of matching between images, which is a fundamental precursorto a number of problems in computer vision. The main aims of thepractical are:• to understand how images are stored and processed in memory;• to gain exposure to the challenges and limitations of finding correspondencesbetween images;• to test your intuition about image filtering by running some experiments;and• to report your results in a clear and concise manner.This assignment relates to the following ACS CBOK areas: abstraction,design, hardware and software, data and information, HCI and programming.2 SetupIn this assignment, you will write a report and some code. While you arerequired to submit both, you will be graded based on your report only.There are many software libraries that can perform image filtering, but werecommend using either:• Matlab: installed on University computers, and available on your homecomputer via ADAPT; Figure 1: A pair of stereo images from the Middlebury Stereo dataset illustratingone patch correspondence; ω denotes the size of each patch that isused for per-pixel comparison between the two images.• Python and the OpenCV library https://opencv.org/: which is free,but not pre-installed on the University computers.Either option will serve you well, and both have inbuilt image processingfunctions which you are free to use. If you are not familiar with the softwareyou will be using, allow yourself time to learn it! The assignments in thiscourse require a relatively small amount of coding to complete, but you willneed to understand what you are doing and the software you are using.3 Patch match for disparity estimationA fundamental task in computer vision involves finding corresponding pointsbetween two or more images. Correspondences identify the same scene-pointthat is visible in two (or more) images. This is illustrated in Figure 1 whichdepicts the connection of the same point on the motor-cycle between the twoviews. Correspondences are used in a number of contexts, including imageinterpolation and 3D reconstructionBecause the two images depict a similar scene from different view-points,the corresponding patches do not share the same x, y pixel co-ordinates.Instead, they can be represented as a disparity map d : [x, y] → d(x, y) = [δx, δy] and the pixel [x, y] in the first image is said to be incorrespondence with the pixel [x0, y0] = [x + δx, y + δy] in the second. Thisrepresentation is illustrated in Figure 2, where the two images from Figure1 are composited to illustrate that corresponding scene-points do not sharecorresponding pixel co-ordinates. However, the correspondence between thescene point p can be represented by a displacement vector d(p) to yield thecorresponding pixel co-ordinates in the second image.The disparity map can be estimated by finding, for every point in the firstimage, the point in the second image with the greatest similarity. Given twopoints [x, y] and [x0, y0] for the first and second images respectively, one way2pd(p)Figure 2: Correspondences can be represented by a displacement vector forevery pixel in one image. Here, the disparity d(p) for pixel p in the leftimage is added to the co-ordinates of p to give the pixel co-ordinates in theright image of Figure 1.to measure their image similarity is given by the sum of squared differences:(1)for some particular patch size ω. Note that this score is 0 if every correspondingpixel in the two patches are identical, and therefore maximisingsimilarity corresponds, in this instance, to minimising s(·): (2)Exhaustively searching every pair of pixels between two images is extremelytime-consuming, and a number of approaches have been described to quicklyfind approximate solutions.The ‘Patch-Match Algorithm’1is one such approach that exploits spatialcoherence by iteratively propagating and then refining hypothesised correspondences.An overview of the algorithm is as follows:1. initialise d(·) with random displacements2. for every pixel p:(a) d(p) ← offset with maximum similarity selected from those in theneighbourhood of p(b) update d(p) by searching a sequence of randomly chosen pointsfrom a diminishing window around d(p)1PatchMatch: a randomized correspondence algorithm for structural image editing,C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman, in ACM SIGGRAPH,pages 1–11, July 2009first image second imageFigure 3: Displacement vectors are propagated by considering neighbourhoodoffsets. Note that only the pixels above and to the left of p are consideredbecause the sweep direction begins, in this instance, from the top leftcorner.3. repeat (2) until convergenceThere are implementation details in how the offsets are chosen from theneighbourhood around a given pixel, related to the order in which the pixelsare updated, and how the random search updates the displacement; thesedetails will be described below.PatchMatch begins with a randomly initialised displacement field d(·)which assigns a random correspondence for every pixel in the first image.The algorithm improves this estimate by processing each pixel in turn and,under the assumption that a pixel’s displacements are likely to be similar,considers the displacements of its neighbours to determine if their displacementis superior. For a given pixel p, the displacement is propagated byd(p) = arg minwhere D = {d(p), d(p−[1, 0]), d(p−[0, 1])} include the displacements aboveand to the left of pixel p. This process is illustrated in Figure 4.The displacement is then refined by searching a sequence of randomoffsets δ, greedily updating the base displacement if the similarity improves:d(p) ←(d(p) + δiif s(p, p + d(p) + δi) (4)The displacement δiis given by δi = καiRi where R is a random variablefrom the uniform distribution in [−1, +1] × [+1, −1], α = 0.5 to controlthe speed with which the search area decreases, and κ is a suitably largewindow size. The process of updating the search window size and locationis illustrated in Figure 4.The algorithm proceeds by sweeping the image, propagating and searchingpixel disparities as it goes, until convergence. In practice, the sweep4search iteration 1 search iteration 2Figure 4: Displacements are updated by randomly searching within a diminishingwindow around the current best displacement.direction is alternated in each pass. The set D in (3) considers disparitiesabove and to the left of a given pixel when the search direction is from thetop-left to the bottom-right of the image; but on alternate passes—when thesearch begins from the bottom-right—the set D is defined by the disparitiesto the right and below the given pixel.This practical will ask you to implement and experiment with the Patchmatchalgorithm to understand the challenges of finding correspondencesbe代写Disparity estimation作业、Python编程语言作业调试、代写Python课程设计作业 代写留学生tween two images. Please note that the programming aspect is not particularlyonerous, and the aim of this assignment is to run experiments totest your hypothesis about the performance of patch match against a varietyof different types of image and how the underlying parameters affects performance.Accordingly, we expect you to implement this particular variantdescribed above rather than use any existing PatchMatch implementation toensure that you are able to perform the required experiments and analysiswith respect to the algorithm described here.The key to the report is to test your hypothesis about the behaviour ofthe system and to support your conclusions with evidence. The aim of thepractical is to understand the challenges with estimating correspondences,rather than simply implement the PatchMatch algorithm. When conductingyour experiments, clearly articulate what hypothesis you are testing byexplaining why a particular patch or stereo pair was chosen and try to givesome insight into why a particular outcome was observed. Finally, please beassured that computing correspondences is a challenging problem, and youshould anticipate that your results to be incorrect for some cases, so pleasedo not be discouraged if your results are not perfect. Discovering where itdoes and does not work is the point of the practical!53.1 Task 1First, read through the rest of the instructions for this assignment, andthen return to this section. Create or download several a minimum of threepairs of test images that you will experiment with. The Middlebury stereodataset http://vision.middlebury.edu/stereo/data has a large numberof stereo pairs. (The images from Figure 1 is from this dataset.) Thisdataset includes image pairs with ground truth disparity which may be usefulin understanding the problem and to determine if your implementation isworking. Many of the images from the Middlebury dataset are high resolutionand therefore will take a non-trivial amount of time to evaluate, so youmight want to consider down-sampling the images to reasonable resolutionbefore conducting your experiments.Note that the Middlebury dataset only has ‘narrow-baseline’ stereo pairswhere the camera has not moved significantly between each frame. Youshould consider experimenting with two images that are not of identicalscenes, e.g. a stereo pair where the camera has moved significantly, thelighting or exposure has changed, or the scene changes between frames. Oneexcellent source of wide-baseline image pairs is carefully selected frames ofan image sequence taken by a moving camera! Experimenting with differentclasses of image pairs will help gain insight into the problems of computingcorrespondences, and help enrich your report.Your report should:1. include the pairs of images and;2. explain why that pair was chosen: ie. what hypothesis in the followingtwo tasks do you think it will help illustrate?3.2 Task 2To explore how the similarity score evaluates candidate points, manuallyselect a point in one image and exhaustively compute (1) for every pixel inthe second image. You can visualise this as a colour-coded image where thecolour (or intensity) at pixel [x, y] corresponds to the similarity between thepatch around [x, y] in the second image against your selected patch in thefirst image. For each score distribution, identify the point that minimises(1) and compare it to the scene-point that you expect to match.Experiment with a number of different stereo pairs–particularly of sceneswhere the exposure/lighting changes between frames and a variety of differentscene points. The Middlebury dataset is an excellent resource becauseyou can compare how the score distribution is affected (or not?) by thechange in exposure. In performing your experiments, consider both the sumof squared differences as described in (1) and a variant where both imagesare transformed by subtracting their mean and dividing by the standard6deviation for each channel of each image independently(5)where I¯ is the mean of image I.While the easiest way to select a source point is to use an image editor(e.g. GIMP www.gimp.org) to identify the pixel co-ordinates, be awarethat different image processing libraries may use the different co-ordinatesystems: we recommend you carefully check that the source patch used isthe one you intended.Consider the following questions in your report:1. Describe how the score distribution is affected by the choice of scenepoint.Do all scene points have the same characteristic? If not, whynot; it so, why did you expect that to be the case?2. Describe how the score distribution is affected by change in patchsize. Is there a single best patch size for all scene-points? Are therecases where a smaller or larger patch size have different advantages ordisadvantages?3. Did the image transform in (5) affect the results in any of the experiments?Why, or why not?3.3 Task 3Implement the Patch Match algorithm described above to compute densecorrespondences. Visualise the disparity as a grey-scale image, where theintensity corresponds to the magnitude of the estimated disparity. Finally,reconstruct the source image using the disparity map and reverse mappingpixels from the second image. Reverse mapping involves assigning the colourat pixel p from the pixel at p + d(p) in the second image (although thereare other approaches to this, too).Optionally, you can visualise the correspondences between the two imagesby plotting them side-by-side and drawing a sparse set of lines betweencorrespondences, similar to the illustration in Figure 1. This might giveyou some greater insight into whether PatchMatch is correctly identifyingcorresponding pixels.In your report, consider the following questions:1. Did the propagation and random search improve, or otherwise affect,the estimated correspondence for the points you experimented with inTask 2? Why do you think that the results were or were not different?2. What relationship—if any—can you identify between the disparitymagnitude and the scene structure? What discrepancies can you identifyin the disparity image and how can they be explained?73. Compare your reconstructed image results to the original input. Isthe source image exactly recreated correctly, or have errors been introduced:and if so, why?3.4 Task 4 (for Masters’ students only)Run a median filter on the disparity image and observe how the disparity isaffected by varying the window size. In your report, consider1. What are the advantages of the median filter, and in what cases doesit adversely affect the results?4 AssessmentHand in your report and supporting code/images via the MyUni page. Uploadtwo files:1. report.pdf, a PDF version of your report. The report should answereach task in a separate section. Make sure you answer each questionlisted at the end of each task, and include results (images or figures)to back up your answers.2. code.zip, a zip file containing your code and test images. Make sureyou include all the code you have written and your test images. Yourmark will be based on your report - the code will just be used to checkyour work.The prac is worth 10% of your overall mark for the course. It is due onMonday March 30 at 11.59pm.John Bastian3rd March 20208转自：http://www.daixie0.com/contents/3/4894.html