Description
Problem 1: Edge Detection (50 %)
a) Sobel Edge Detector (Basic: 10%)
Implement the Sobel edge detector and apply to Tiger and Pig images as shown in Fig. 1 (a) and (b). Note
that you need to convert RGB images to grey-level image first. Include the following in your results:
Ø Normalize the x-gradient and the y-gradient values to 0-255 and show the results.
Ø Tune the thresholds (in terms of percentage) to obtain your best edge map. An edge map is a
binary image whose pixel values are either 0 (edge) or 255 (background)
b) Canny Edge Detector (Basic: 10%)
The Canny edge detector is an edge detection technique utilizing image’s intensity gradients and nonmaximum suppression with double thresholding. In this part, apply the Canny edge detector [1] to both Tiger
and Pig images. You are allowed to use any online source code such as the Canny edge detector in the
MATLAB image processing toolbox or the OpenCV (i.e. Open Source Computer Vision Library). Generate
edge maps by trying different low and high thresholds. Answer the following questions:
1. Explain Non-maximum suppression in Canny edge detector in your own words.
2. How are high and low threshold values used in Canny edge detector?
Figure 1: Tiger and Pig images
c) Structured Edge (Advanced: 15%)
Apply the Structured Edge (SE) detector [2] to extract edge segments from a color image with online
source codes (released MATLAB toolbox: https://github.com/pdollar/edges). Exemplary edge maps
generated by the SE method for the House image are shown in Figure 2. You can apply the SE detector to
EE 569 Digital Image Processing: Homework #2
Professor C.-C. Jay Kuo Page 2 of 7
the RGB image directly without converting it into a grayscale image. Also, the SE detector will generate
a probability edge map. To obtain a binary edge map, you need to binarize the probability edge map with
a threshold.
1. Please digest the SE detection algorithm. Summarize it with a flow chart and explain it in your
own words (no more than 1 page, including both the flow chart and your explanation).
2. The Random Forest (RF) classifier is used in the SE detector. The RF classifier consists of multiple
decision trees and integrate the results of these decision trees into one final probability function.
Explain the process of decision tree construction and the principle of the RF classifier.
3. Apply the SE detector to Tiger and Pig images. State the chosen parameters clearly and justify
your selection. Compare and comment on the visual results of the Canny detector and the SE
detector.
House Probability edge map Binary edge map (with p>0.2)
Figure 2: The House image and its probability and binary edge maps obtained by the SE detector
d) Performance Evaluation (Advanced: 15%)
Ground Truth 1 Ground Truth 2 Ground Truth 3
Ground Truth 4 Ground Truth 5
Figure 3: Five ground truth edge maps for the Goose image
Perform quantitative comparison between different edge maps obtained by different edge detectors. The
ultimate goal of edge detection is to enable the machine to generate contours of priority to human being.
For this reason, we need the edge map provided by human (called the ground truth) to evaluate the quality
EE 569 Digital Image Processing: Homework #2
Professor C.-C. Jay Kuo Page 3 of 7
of a machine-generated edge map. However, different people may have different opinions about important
edge in an image. To handle the opinion diversity, it is typical to take the mean of a certain performance
measure with respect to each ground truth, e.g. the mean precision, the mean recall, etc. Figure 3 shows 5
ground truth edge maps for the Goose image from the Berkeley Segmentation Dataset and Benchmarks
500 (BSDS 500) [3]. To evaluate the performance of an edge map, we need to identify the error. All pixels
in an edge map belong to one of the following four classes:
(1) True positive: Edge pixels in the edge map coincide with edge pixels in the ground truth. These
are edge pixels the algorithm successfully identifies.
(2) True negative: Non-edge pixels in the edge map coincide with non-edge pixels in the ground
truth. These are non-edge pixels the algorithm successfully identifies.
(3) False positive: Edge pixels in the edge map correspond to the non-edge pixels in the ground truth.
These are fake edge pixels the algorithm wrongly identifies.
(4) False negative: Non-edge pixels in the edge map correspond to the true edge pixels in the ground
truth. These are edge pixels the algorithm misses.
Clearly, pixels in (1) and (2) are correct ones while those in (3) and (4) are error pixels of two different
types to be evaluated. The performance of an edge detection algorithm can be measured using the F
measure, which is a function of the precision and the recall.
Precision 😛 = #True Positive
#True Positive + #False Positive
Recall : R = #True Positive
#True Positive + #False Negative
F = 2 ⋅ P⋅ R
P + R
(1)
One can make the precision higher by decreasing the threshold in deriving the binary edge map. However,
this will result in a lower recall. Generally, we need to consider both precision and recall at the same time
and a metric called the F measure is developed for this purpose. A higher F measure implies a better edge
detector.
For the ground truth edge maps of Tiger and Pig images, evaluate the quality of edge maps obtained in
Parts (a)-(c) with the following:
1. Calculate the precision and recall for each ground truth (saved in .mat format) separately using the
function provided by the SE software package and, then, compute the mean precision and the mean
recall. Finally, calculate the F measure for each generated edge map based on the mean precision
and the mean recall. Please use a table to show the precision and recall for each ground truth, their
means and the final F measure. Comment on the performance of different edge detectors (i.e. their
pros and cons.)
2. The F measure is image dependent. Which image is easier to a get high F measure – Tiger or Pig?
Please provide an intuitive explanation to your answer.
3. Discuss the rationale behind the F measure definition. Is it possible to get a high F measure if
precision is significantly higher than recall, or vice versa? If the sum of precision and recall is a
constant, show that the F measure reaches the maximum when precision is equal to recall.
EE 569 Digital Image Processing: Homework #2
Professor C.-C. Jay Kuo Page 4 of 7
Problem 2: Digital Half-toning (50%)
a) Dithering (Basic: 15%)
Fig. 4 is grayscale image. Implement the following methods to convert it to half-toned images. In the
following discussion, F(i,j) and G(i,j) denote the pixel of the input and the output images at position (i,j),
respectively. Compare the results obtained by these algorithms in your report.
Figure 4: Golden Gate Bridge
1. Random thresholding
In order to break the monotones in the result from fixed thresholding, we may use a ‘random’ threshold.
The algorithm can be described as:
• For each pixel, generate a random number in the range 0 ∼ 255, so called ����(�,�)
• Compare the pixel value with ����(�,�). If it is greater, then map it to 255; otherwise, map it to 0,
i.e.
� �,� = 0 �� 0 ≤ � �,� < ����(�,�)
255 �� ����(�,�) ≤ � �,� < 256
A choice of random threshold could be uniformly distributed random variable. Check your coding
language documentation for proper random variable generator.
2. Dithering Matrix
Dithering parameters are specified by an index matrix. The values in an index matrix indicate how likely
a dot will be turned on. For example, an index matrix is given by
�6 �,� = 1 2
3 0
where 0 indicates the pixel most likely to be turned on, and 3 is the least likely one. This index matrix is
a special case of a family of dithering matrices first introduced by Bayer [4]. The Bayer index matrices
are defined recursively using the formula:
EE 569 Digital Image Processing: Homework #2
Professor C.-C. Jay Kuo Page 5 of 7
�69 �,� = 4�9 �,� + 1 4�9 �,� + 2
4�9 �,� + 3 4�9 �,�
The index matrix can then be transformed into a threshold matrix T for an input gray-level image with
normalized pixel values (i.e. with its dynamic range between 0 and 255) by the following formula:
� �, � = � �, � + 0.5
�6 ×255
where �6 denotes the number of pixels in the matrix. Since the image is usually much larger than the
threshold matrix, the matrix is repeated periodically across the full image. This is done by using the
following formula:
� �,� = 0 �� 0 ≤ � �,� ≤ �(� ����,� ����)
255 �(� ����,� ����) < � �,� < 256
Please create �6, �D, �E6 thresholding matrices and apply them to halftone Fig. 4. Compare your results.
b) Error Diffusion (Basic: 15%)
Convert the 8-bit Fig.4 image to a half-toned one using the error diffusion method. Show the outputs of
the following three variations and discuss these obtained results. Compare these results with dithering
matrix. Which method do you prefer? Why?
1. Floyd-Steinberg’s error diffusion with the serpentine scanning, where the error diffusion matrix is:
1
16
0 0 0
0 0 7
3 5 1
2. Error diffusion proposed by Jarvis, Judice, and Ninke (JJN), where the error diffusion matrix is:
1
48
0 0 0 0 0
0 0 0 0 0
0 0 0 7 5
3 5 7 5 3
1 3 5 3 1
3. Error diffusion proposed by Stucki, where the error diffusion matrix is:
1
42
0 0 0 0 0
0 0 0 0 0
0 0 0 8 4
2 4 8 4 2
1 2 4 2 1
Describe your own idea to get better results. There is no need to implement it if you do not have time.
However, please explain why your proposed method will lead to better results.
EE 569 Digital Image Processing: Homework #2
Professor C.-C. Jay Kuo Page 6 of 7
c) Color Halftoning with Error Diffusion (Advanced: 20%)
Figure 5: The bird image[8]
1. Separable Error Diffusion
One simple idea to achieve color halftoning is to separate an image into CMY three channels and apply
the Floyd-Steinberg error diffusion algorithm to quantize each channel separately. Then, you will have
one of the following 8 colors, which correspond to the 8 vertices of the CMY cube at each pixel:
W = (0,0,0), Y = (0,0,1), C = (0,1,0), M = (1,0,0),
G = (0,1,1), R = (1,0,1), B = (1,1,0), K = (1,1,1)
Note that (W, K), (Y, B), (C, R), (M, G) are complementary color pairs. Please show and discuss the result
of the half-toned color bird image. What is the main shortcoming of this approach?
2. MBVQ-based Error diffusion
Shaked et al. [5] proposed a new error diffusion method, which can overcome the shortcoming of the
separable error diffusion method. Please read [5] carefully, and answer the following questions:
1) Describe the key ideas on which the MBVQ-based Error diffusion method is established and give
reasons why this method can overcome the shortcoming of the separable error diffusion method.
2) Implement the algorithm using a standard error diffusion process (e.g. the FS error diffusion) and
apply it to Fig. 5. Compare the output with that obtained by the separable error diffusion method.
EE 569 Digital Image Processing: Homework #2
Professor C.-C. Jay Kuo Page 7 of 7
Appendix:
Problem 1: Edge detection
Tiger.raw 481x321x3 24-bit color(RGB)
Pig.raw 481x321x3 24-bit color(RGB)
Tiger.jpg 481x321x3 24-bit color(RGB)
Pig.jpg 481x321x3 24-bit color(RGB)
Tiger.mat (containing 5 ground truth images)
Pig.mat (containing 5 ground truth images)
House.png 481x321x3 24-bit color(RGB)
House_binary.png 481×321 logical
House_probmap.png 481×321 8-bit gray
Problem 2: Digital Half-toning
bridge.raw 600×400 8-bit gray
bird.raw 500x375x3 24-bit color(RGB)
Reference Images
Images in this homework are from the BSDS 500 [3], the USC-SIPI image database [6], the Google
images [7] or the ImageNet dataset [8].
References
[1] J. Canny, “A computational approach to edge detection,” IEEE Transactions on pattern analysis and
machine intelligence, no. 6, pp. 679–698, 1986.
[2] P. Dollár and C. L. Zitnick, “Structured forests for fast edge detection,” in Proceedings of the
IEEE International Conference on Computer Vision, 2013, pp. 1841–1848.
[3] P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “Contour detection and hierarchical image
segmentation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 5, pp. 898–916, May 2011.
[Online]. Available: http://dx.doi.org/10.1109/TPAMI.2010.161
[4] B. E. Bayer, “An optimum method for two-level rendition of continuous-tone pictures,” SPIE MILESTONE SERIES MS, vol. 154, pp. 139–143, 1999
[5] D. Shaked, N. Arad, A. Fitzhugh, I. Sobel, “Color Diffusion: Error-Diffusion for Color Halftones”,
HP Labs Technical Report, HPL-96-128R1, 1996.
[6] [Online] http://sipi.usc.edu/database/
[7] [Online] http://images.google.com/
[8] [Online] http://www.image-net.org/
