Project 1: Color Segmentation

ECE 276A: Sensing & Estimation in Robotics 
Project 1: Color Segmentation
Collaboration in the sense of discussion is allowed, however, the work you turn in should be your own -
you should not split parts of the assignments with other students and you should certainly not copy other
students’ code or papers. See the collaboration and academic integrity statement here: https://natanaso.
github.io/ece276a. Books may be consulted but not copied from.
Submission
You should submit the following two files by the deadline shown on the top right corner.
1. FirstnameLastname P1.pdf on Gradescope: upload your solutions to the theoretical problems
(Problem 1-3). You may use latex, scanned handwritten notes (write legibly!), or any other method
to prepare a pdf file. Do not just write the final result. Present your work in detail explaining your
approach at every step. Also, attach to the same pdf the report for Problem 5. You are encouraged but
not required to use an IEEE conference template1
for your report.
2. FirstnameLastname P1.zip on TritonEd: upload all code you have written for Problem 4 (do not
include the training and test datasets) and a README file with clear instructions for running it. Please
try to generate an executable file from your code following the instructions online2
. While generating an
executable is not required, it will simplify the task of running your code with different library versions
across different platforms.
Problems
In square brackets are the points assigned to each problem.
1. [2 pts] Suppose U and V are independent random variables, each distributed uniformly in the unit interval.
(a) Determine the distributions of the random variables R =
p
−2 log(1 − U) and Θ = 2πV.
(b) Determine the joint distribution of X = R cos Θ and Y = R sin Θ.
2. [2 pts] Consider two color classes {1, 2} and associated feature vectors x ∈ R
m. Let the feature distribution
conditioned on the class label Y be Gaussian, i.e., X|Y = 1 ∼ N (µ1, σ2
Im) and X|Y = 2 ∼ N (µ2, σ2
Im).
(a) What is the expected square intra-class distance E

(X − X0
)
T
(X − X0
) | Y = 1, Y 0 = 1
(both X
and X0 belong to class 1)?
(b) What is the expected square inter-class distance E

(X − X0
)
T
(X − X0
) | Y = 1, Y 0 = 2
(X belongs
to class 1, X0 belongs to class 2)?
(c) Suppose that only one dimension is informative about class values, i.e. µ11 6= µ21 but µ1j = µ2j
for j = 2, . . . , m. What is the ratio of the expected intra-class to inter-class distances under this
assumption? As m increases, what does this ration approach and what does that imply about the
classification accuracy in this case?
3. [4 pts] The Poisson distribution is a discrete probability distribution useful for modeling occurrences per
unit time. For example, in networking, packet arrival density is often modeled using a Poisson distribution.
The probability mass function (pmf) of a Poisson-distributed random variable X is p(x; λ) = λ
x
e
−λ
x!
, where
λ 0 is a parameter specifying the average number of events per interval. It can be shown that λ is the
mean of the Poisson distribution. In this problem, we will estimate the parameter λ from a number of
observed packets per unit time X1, . . . , Xn. Assume that Xi ∼ Poisson(λ).
(a) Show that λˆ := 1
n
Pn
i=1 Xi
is the maximum likelihood estimate of λ and that it is an unbiased
estimator of λ, i.e., E[λˆ] = λ
1https://www.ieee.org/conferences_events/conferences/publishing/templates.html
2https://natanaso.github.io/ece276a/executable.html
1
ECE 276A: Sensing & Estimation in Robotics Due: 11:59 pm, 10/23/17
(b) Your friend in networking hands you a typical plot showing the counts of computers at the university
cluster with different average packet arrival densities:
Your extensive experience in statistics tells you that the plot resembles the pdf of a Gamma distribution. Hence, you believe that a good prior distribution for λ may be a Gamma distribution Γ(α, β)
with pdf3
:
p(λ | α, β) = β
α
Γ(α)
λ
α−1
e
−βλ, λ 0,
Also, if λ ∼ Γ(α, β), then λ has mean α/β and mode (α − 1)/β for α 1. Compute the posterior
distribution of λ after observing the n packet arrival times. Hint: λ
P
i Xi+α−1
e
−λ(n+β)
looks like a
Gamma distribution.
(c) Derive an analytic expression for the maximum a posteriori (MAP) estimate of λ under a Γ(α, β)
prior.
Instead of estimating the parameter λ, next we consider estimating a nonlinear function of λ, namely
η = e
−2λ
from a single sample X ∼ Poisson(λ).
(d) Let ˆη = e
−2X. Show that ˆη is the maximum likelihood estimate of η.
(e) Show that the bias of ˆη is e
λ(1/e2−1) − e
−2λ
(f) It turns out that (−1)X is the only unbiased estimate of η. Prove that it is indeed unbiased and
briefly explain why this is a bad estimator to use. It may be instructive to plot the values of the
MLE and unbiased estimate for X = 1, . . . , 10 (You do not need to hand in the plot).
4. [10 pts] Train a probabilistic color model from image data and use it to segment unseen images, detect
a red barrel, and find the relative distance to the barrel. Given a set of training images, you should
hand-label examples of different colors. From these examples, you should build color classifiers for several
colors (e.g., red, yellow, brown, etc.) and finally a red barrel detector. You should then use your algorithm
to obtain the bounding box of a detected barrel in the image frame and use linear regression to estimate
the distance to the barrel on new test images. Instructions and tips follow.
• Training data: now available at:
https://drive.google.com/open?id=0B241vEW29598NnFyUTZRbWNQYTA
• Test data: released on 10/21/17 at:
https://drive.google.com/open?id=0B241vEW29598TUxGUmVtNVI4VVk
• Hand-label appropriate regions in the training images with discrete color labels. For this project,
we will be especially interested in regions containing the red barrel (positive examples) and images
containing similar colored-areas that are not a barrel (negative examples). If you are ambitious, you
can try to implement automated ways of labeling images, e.g., by unsupervised image segmentation,
or an adaptive region flooding algorithm. Lighting invariance will be an issue, so you should think
carefully about the best color space to use, and perhaps some low-level adaptation on the images.
• Use a learning algorithm to partition the color space into appropriate color class regions. You
must implement and present results from an approach discussed in class (Single Gaussian, Gaussian
Mixture, or Logistic Regression) but you are also free to try other machine learning approaches if
you have time, e.g., decision trees, support vector machines, etc. You need to make your algorithm
3Γ(α) refers to the Gamma function but its particular form is not important for this problem
2
ECE 276A: Sensing & Estimation in Robotics Due: 11:59 pm, 10/23/17
so that it is able to generalize to new images. To prevent overfitting the training images, split
them into training and validation sets. Train your algorithms using the training set and evaluate
their performance on the validation set. This will allow you to compare different parameters for the
probabilistic models and different color space representations.
• Once the color regions are identified, you can use shape statistics and other higher-level features to
decide where the barrel is located in the images. Try all possible combinations of red regions and
compute a ”barrelness” score for each one. Identify the coordinates of abounding box for the regions
with high ”barrelness” score. You should also compute an estimate of the distance to the barrel,
e.g., using linear regression. Your algorithm should be able to quickly classify and display results on
a new set of test images. Write a script to display your test result as follows:
import cv2, os
folder = "testset"
for filename in os.listdir(folder):
# read one test image
img = cv2.imread(os.path.join(folder,filename))
# Your computations here!
blX, blY, trX, trY, d = myAlgorithm(img)
# Display results:
# (1) Segmented image
# (2) Barrel bounding box
# (3) Distance of barrel
# You may also want to plot and display other diagnostic information
cv2.waitKey(0)
cv2.destroyAllWindows()
• Your report should include your test results in the following manner:
ImageNo = [01], BottomLeftX = 507.0605, BottomLeftY = 506.7571,
TopRightX = 662.0208, TopRightY=826.7004, Distance = 5.4418
ImageNo = [02], BottomLeftX = 507.0605, BottomLeftY = 826.7004,
TopRightX = 662.0208, TopRightY=826.7004, Distance = 2.3840
....
• You may rely on some useful python functions for this project:
– hand-labeling: roipoly: https://github.com/jdoepfert/roipoly.py
– conversion: cvtColor: http://docs.opencv.org/3.0-beta/doc/py_tutorials/py_tutorials.html
– region analysis: regionprops: http://scikit-image.org/docs/dev/api/skimage.measure.html
However, do not use any built-in functions that implement a core part of this project
(Gaussian Mixtures, EM, Logistic Regression). If you are not sure, then ask the TAs. Examples of
allowed code:
import cv2
img2 = cv2.cvtColor(img, cv2.COLOR_BGR2YCR_CB)
from skimage import data, util
from skimage.measure import label, regionprops
img = util.img_as_ubyte(data.coins()) 110
label_img = label(img, connectivity=img.ndim)
props = skimage.measure.regionprops(label_img)
5. [6 pts] Write a project report describing your approach to the color segmentation and barrel detection
problem. Your report should include the following sections:
• Introduction: discuss why the problem is important and present a brief overview of your approach
• Problem Formulation: state the problem you are trying to solve in mathematical terms. This
section should be short and clear and should define the quantities you are interested in.
• Technical Approach: describe your approach to color segmentation and barrel detection
• Results: present your training results, test results, and discuss them – what worked, what did
not, and why. Make sure your results include (a) a segmented color image, (b) the bounding box
coordinates of the barrel, (c) the distance to the barrel estimate in meters for each test image.
3