CPSC 425 Fitting Data to a Model 20/21 (Term 1) Practice Questions
Multiple Part True/False Questions. For each question, indicate which of the statements, (A)–(D), are true and which are false? Note: Questions may have zero, one or multiple statements that are true.
Question 1 There are advantages to using a hash table rather than an accumulator array to store votes in a Hough transform. Which of the following statements are true and which are false?
(A) It is faster to enter each vote into a hash table.
(B) There are more votes in each bin when the fitted model is present.
(C) Less storage is required since empty bins in a hash table are not represented explicitly.
(D) It is not necessary to predict the maximum range of each parameter in ad- vance in order to determine the array size.
Solution : (A) False, (B) False, (C) True, (D) True.
Question 2 Both the Hough transform and RANSAC are techniques for fitting
data to a model. Which of the following statements are true? Which are false?
(A) RANSAC performs better than the Hough transform as the number of pa-
rameters in the model increases.
(B) The Hough transform performs better than RANSAC as the number of out-
liers increases significantly over 50%.
(C) Performance of the Hough transform improves when the points used to fit
to the model are more distinctive.
(D) Foraparticulardataset,RANSACfinds,atmost,oneinstanceofthemodel. On the other hand, the Hough transform can find more than one instance, if multiple instances exist.
Solution: (A) True, (B) True, (C) True, (D) True. Short Answer Questions.
Question 3 The title of the Efros and Leung paper that formed the basis for As- signment 4 is, “Texture synthesis by non-parametric sampling.”
(a) In the context of CPSC 425, what does the term non-parametric mean?
Solution : Non-parametric means that no assumptions are made about the particular functional form a model (or representation) takes.
(b) In the context of the Efros and Leung paper, is the use of the term non- parametric in the title appropriate? (Briefly justify your answer).
Solution : Yes, use of the term is consistent, and therefore appropriate. Efros and Leung sample texture directly from windows in the image. They make no assumptions about the functional form an analytic or synthetic model of the texture might take.
Question 4 Suppose we want to fit a circle to a set of points using RANSAC. Assume that 75% (i.e., 3/4) of the points are outliers. How many random samples of 3 points are needed to detect the circle with 95% probability? (Note: In an exam setting, you wouldn’t need to compute an actual number, but just show how it would be computed if you had a scientific calculator available).
Solution : Let k be the number of samples. The fraction of inliers is 1/4. The number of points to define the hypothesis is 3. Therefore, the probability a sample of 3 points is correct is (1/4)3 = 1/64 and the probability all k samples will fail is (1 − 1/64)k = (63/64)k. Accordingly, we want (63/64)k < 0.05 (good enough for answer). Continuing,
Thus, 191 random samples are required.
k ln(63/64) < k > k >
ln(0.05) ln(0.05)/ ln(63/64) 190.22507