CSC2503 Assignment 2: Camera Obscura & Robust Estimation solved

$30.00

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment

Description

5/5 - (6 votes)

Part A: Build your own camera obscura
Your task is to turn a room, a box or any other box-shaped space whose lighting you can control into
a real-life camera obscura (a.k.a pinhole camera) by letting light enter that space through a very
small hole. If everything is done right, a sharp image of the scene outside your camera obscura will
be projected upside down on the camera’s back plane. The image may be quite dim but should be
visible to the naked eye (make sure that the scene outside the camera obscura is very bright).
1. Basic operation: After you have constructed your camera obscura and formed a sharp image,
use a digital camera or smartphone to take pictures of your setup and of the image being formed.
Specifically, take pictures of (a) the scene(s) in front of your camera obscura, (b) the corresponding
image formed on the camera obscura’s back plane, and (3) your setup. Your pictures should be
sufficient to convince the TA that you created the camera obscura yourself and that it behaves as
expected.
Since the images formed by your camera obscura will be dim, you will likely need to use a long
exposure to record them with your digital camera. To avoid motion blur, ensure that your digital
camera does not move at all during the exposure (e.g., you may wish to mount your digital camera
on a tripod). If your digital photos are too dim, you may linearly scale them to improve visibility.
2. Experimenting with different pinhole shapes & sizes: Now slightly increase the size of
your camera obscura’s pinhole so that it becomes a disc and the images it forms become blurry.
As before, take a picture of the blurry image, of the scene outside and of the pinhole itself. Finally,
repeat this process for a square-shaped, a cross-shaped and a hexagonal pinhole.
3. Modeling lens-less image formation: If done properly, the images in (2) will differ from
each other and from the sharp image obtained with the tiny pinhole you used in (1). Derive an
expression that relates the “ideal” image I(x, y) of the scene, captured with an infinitely-small
pinhole, to the image IS(x, y) formed when the pinhole’s shape is a 2D curve S. Your derivation
should assume the following: (a) the camera’s front and back planes are parallel to each other;
(b) the pinhole lies on the camera’s front plane; (c) the scene is a Lambertian 2D plane that is
parallel to the camera’s front plane; and (d) the camera’s back plane has infinite size, i.e., x and
y range from −∞ to ∞. Finally, you should comment on why the Lambertian assumption and
the scene’s planarity and parallelism to the camera’s front plane are essential in your derivation.
What to submit for Part A. Write a report that addresses the itemized tasks (1)-(3) above.
Your report should be in PDF format and should include the images requested. LaTeX- or Wordformatted reports are preferred; a hand-written derivation that has been scanned to PDF is also fine
as long as it is very legible. Assume the marker knows the context of all questions, so do not spend
time repeating material in the hand-out or the class notes.
1
Part B: Robustly Fitting Circles
The goal of this part of the assignment is to gain experience using robust estimation to extract simple
image models from noisy image measurements.
To begin: Download the starter code A2handout.zip from the course homepage.
What to submit for Part B. Write a short report addressing each of the itemized questions below.
Pack your PDF report for Part B and the completed Matlab files for each question, along with the
PDF report for Part A, into a file called A2.zip, and submit the zip file electronically.
Robustly Fitting Circles. A geneticist wishes to automatically count cells in microscope images,
such as the one depicted in Fig. 1 (left). The geneticist is especially interested in cells at different
stages of cell division. Here we consider an application of robust estimation that will get us started
on a solution for the geneticist. Cells are actually elliptical but we’ll begin by fitting circles.
Figure 1: Cell image (left), foreground pixels (middle), and fitted cells (right, in red).
The main script in the handout code, called findCellScript.m, reads in a microscope image of cells
(Fig. 1 (left)). We have already preprocessed the cell images to detect foreground cell pixels (Fig. 1
(middle)). We have also labelled the connected sets of foreground pixels, which are read in as a
second image. Finally, the script computes Canny edgels from the foreground mask. The code then
considers each connected component individually, looking for circular cells (see Fig. 1 (right)).
Your job is to fit circles to the edgels obtained from the boundaries of the connected components.
Each fitted circle should correspond to one “cell” including, perhaps, a small circle for a cell bud just
being born, by splitting off from another cell (see Fig. 1 (right)). This is a vague definition of what
constitutes a “cell”. However, if you study Fig. 1 (right) (e.g., by enlarging the electronic copy), it
should be intuitively clear what is meant by a “cell”. Part of your job in this assignment is to decide
on how to operationally define our intuitive notion of one cell.
We aim to fit circles using edgel measurements. Let the k
th edgel be denoted by (~xk, ~nk), where ~xk is
the measured image position and ~nk is the measured edgel normal. The edgel normal points in the
direction of increasing brightness of the foreground regions Fig. 1 (middle); i.e., they point towards
the interior of the cells.
Because cells occur in close proximity, a single connected foreground component will often contain
2
more than one cell. It is therefore natural to formulate circle fitting as a robust estimation problem.
That is, a set of edgel measurements {~xk, ~nk}
N
k=1 from a single connected component will often
correspond to multiple cells. When estimating the parameters of one circle (cell) we can view the
measurements from any other circle (cells) as outliers. To this end we will use the Geman-McLure
(GM) estimator (to be introduced in class next week),
ρ(e, σg) = e
2
σ
2
g + e
2
. (1)
In what follows we are going to take a greedy approach to this problem, finding one circle at a time.
The approach comprises four main steps: 1) quickly generating a set of plausible circle hypotheses,
2) choosing one among them as an initial guess for optimization, 3) robust estimation to optimize
the fit, and 4) the model update, for which we decide whether or not the optimized fit is sufficient
and which edgel measurements are owned by the circle.
Below there are several questions, including some derivations and some programming. To simplify
the programming, the assignment handout includes a partial implementation of the general strategy
outlined above, i.e., findCellScript.m. For the programming parts of the assignment you need to
complete several Matlab m-functions, as described below. You may also make small changes to the
handout code.
1. Noise model: To estimate the parameters of a circle, we’ll focus on the use of the edgel position
measurements ~xk. The key constraint on position measurements is that the distance from the
center to any position on the circle must equal the radius. For measurement ~xk, and a circle with
centre ~xc and radius r, we can write the error as
ek = ||~xk − ~xc||2 − r
2 = ~a T
~xk + b + ~x T
k
~xk . (2)
where ~a ≡ −2~xc and b ≡ ~x T
c ~xc − r
2
. The change in parameterization, from ~xc and r to ~a and b
is convenient because ek is linear in ~a and b. Of course it is straightforward to find the circle’s
centre ~xc and radius r from ~a and b.
To properly formulate an estimator we should understand the nature of the expected errors, ek. To
that end, let’s assume that the observed positions (measurements) are equal to the true positions,
denoted ˆ~xk, plus independent, isotropic Gaussian noise ~m ∼ N (0, σ2
I); i.e.,
~xk = ˆ~xk + ~m , where p(~m) = 1
2πσ2
e
−~mT ~m/2σ
2
. (3)
With this measurement noise model, what is the distribution of the errors ek? How does it depend
on the circle parameters ~xc and r?
2. LS estimator: Suppose we approximate the distribution of the errors, ek, as a mean-zero Gaussian (Normal) distribution. In other words, assume that the only source of error on the RHS of
Eqn. (2) is additive, mean-zero Gaussian noise. What is a reasonable choice for the variance of
the Gaussian noise?
Assuming that you are given a set of independent measurements, {~xk}
N
k=1, all of which arise from
the same circle, a natural way to derive an estimator is to formulate the negative log likelihood
of the measurements. The maximum likelihood estimator is found by minimizing the negative
log likelihood with respect to the unknowns ~a and b. Beginning with this likelihood, derive a
least-squares estimator.
3
3. Circle proposals. The first step of our greedy strategy is to generate a set of circle proposals
for a given set of edgel measurements {(~xk, ~nk)}
N
k=1. For this step you may find it helpful to use
both the position measurements and the normal measurements.
This requires that you complete the m-function getProposals.m (in the circleFit subdirectory).
When finished this function should return a P × 3 array named circles. Each row of circles
corresponds to the parameters (xc, yc, r) of a circle, where ~xc = (xc, yc)
T denotes the image
position of the center of the circle, and r denotes the radius of the circle. Your implementation of
getProposals should attempt to efficiently produce up to numGuesses proposals. The idea is to
quickly find initial guesses from which you can select one to be subsequently refined with the robust
estimator. Since this will be run numerous times, it is essential that this step require minimal
computational effort. In your write up, clearly explain the algorithm you used to automatically
generate circle proposals, along with the reasons why you chose it over other possibilities.
If you have trouble with this step, you can begin by writing getProposals so that it simply
generates proposals from moused-in points (say a center point plus one point on the circle). You
won’t get any marks for this, but it will help you get started on other parts of the problem.
4. Circle selection. The next step in findCellScript.m is to select the best circle from the
proposed circles in the first step (Question 3 above). For example, a good circle might be close
to many edgels in the data. Implement your selection process in the function bestProposal, so
that it chooses a promising circle from the list of proposals. In your write up, clearly describe
how you select the best circle (i.e., be specific about what you mean by “best”), and explain your
reasons for this choice.
5. Robust fitting. Beginning with the best circle from the second step (Question 4) as an initial
guess, the next step is to optimize the fit. To this end, derive an IRLS algorithm for estimating
the circle parameters (~a, b) which (locally) minimize the objective function
O(~a, b) = X
k
ρ(ek(~a, b), σg) . (4)
Here ek is as defined in (2). In your write-up, include the derivation of the these equations for ~a
and b, and clearly describe your IRLS algorithm.
Complete the function fitCircleRobust to implement this IRLS algorithm for robustly fitting
a circle to your edgel data. In order to test your code, you can initially set demoRobustConv to
true. This displays how your code behaves for each initial guess provided by getProposals in the
second step above. Experiment with different values of the robust estimator’s scale parameter σg
(sigmaGM in the code). Ideally, we would choose σ
2
g
to be equal to the variance of the errors ek for
inlier measurements. In practice, describe is a suitable way to choose σg for your implementation.
What goes wrong when σg is much too large or much to small?
Before continuing on, set demoRobustConv back to false.
6. Model update. Finally, given the robustly fit circle, decide if it should be kept in the model
(see the function isGoodCircle). If it is decided that it should be kept, then the handout code
greedily removes the edgels with sufficiently high weights from the data. In your write up, explain
how you would choose a good threshold to be applied to the weights. Also, describe on what basis
your isGoodCircle function decides to keep a new circle, and justify your choice.
These four steps (Questions 3-6) are then repeatedto fit additional circles. The cell finder is now
complete.
4
7. Brief evaluation. Your completed code should now provide a very reasonable first cut at solving
our geneticist’s problem. It should be expected to miss cells that have been significantly cropped
due to the side of the images. Also, small buds on some cells might be missed (see Fig. 1). Other
than these two “failure modes”, your algorithm should work well. What other situations are
observed to cause your algorithm to fail to find a plausible set of circles? Briefly describe what
you might do to try to fix these remaining problems.
5