EE150Homework 3Due: Tues, April 26 (Before Class)1 Lowe Paper and the KD TreeRead the David Lowe papers from the website (there are two on the lectures page andone on the HW page) and review the notes from class. This is one of the few systemswithin computer vision that actually ‘works’ in practice. It has been implemented andis being used within the real world.1. (5 pts) What is a KD Tree? How does Lowe employ the KD Tree? What sortof computational savings does Lowe achieve by using it? Generate 7 randompoints in 2D and show how the tree would be constructed and the final tree whichis constructed . No need to generate code for this, just draw the Tree(s) byhand. Will the KD Tree always find the optimal match in 2D? If not, illustrate anexample where it fails to find the optimal match.(hint: see www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm for inspi-ration on how to create the tree.)2. (5 pts ) Explain the concept of ‘back-tracking’ and how it can be used to finda better match. What information is being stored to perform the back-tracking?Which is the time complexity (big-O notation) of the new search assuming thatyou perform a maximum of ‘k’ back-tracking steps?2 Constellation ModelWe presented a model in class which aims to model an object by a collection of partsand their relative positions. It is known as the ‘Constellation Model’. Note that we haveonly talked about the shape component of the model, we have not talked about how tomodel the appearance of each part. Below you will be asked to extend the model whichwas presented to make it translation invariant. That is, the model will be able to detectan object which has been translated to any position within an image.1. (7 pts) How could you make the model presented in class translation invariant?Describe method(s) for achieving this invariance. Hint: One possibility, considerboth ordering your detections along the x-axis as well as conditioning on thedetection of a particular part.12. (13 pts) Modify the code presented in class to make it translation invariant. Youshould provide plots which indicate this. I.e., generate translated versions of themodel and show that the hypotheses corresponding to these translated points areachieving a high