Starting from:
$30
EE569-Homework 2 Edge Detection and Digital Half-toning Solved
Problem 1: Edge Detection
(a) Sobel Edge Detector
Implement the Sobel edge detector and apply to Gallery.raw and Dogs.raw images as shown in Fig. 1 (a) and (b). Note that you need to convert RGB images to grayscale image first. The relationship between RGB and grayscale images are provided in the Appendix. Include the following in your results:
(1) Normalize the x-gradient and the y-gradient values to 0-255 respectively and show the results;
(2) Calculate and show the normalized gradient magnitude map;
(3) Tune the thresholds (in terms of percentage) to obtain an edge map with the best visual performance. The final edge map should be a binary image whose pixel values are either 0 (edge) or 255 (background).
(b) Canny Edge Detector
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 Gallery.jpg and Dogs.jpg images from the Berkeley Segmentation Dataset and Benchmarks 500 (BSDS 500) [2]. 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).
(1) Explain the Non-maximum suppression in Canny edge detector in your own words.
(2) How are high and low threshold values used in Canny edge detector?
(3) Generate edge maps by trying different low and high thresholds and discuss your results.
Figure 1: Gallery and Dogs images
(c) Structured Edge
Apply the Structured Edge (SE) detector [3] to extract edge segments from a color image with online source codes (released toolbox in MATLAB: https://github.com/pdollar/edges). Exemplary edge maps generated by the SE method for the Helicopter image from BSDS 500 are shown in Figure 2. You can apply the SE detector to 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 Gallery.jpg and Dogs.jpg 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.
Helicopter Probability edge map (inversed) Binary edge map (with p0.2)
Figure 2: The Helicopter image and its probability and binary edge maps obtained by the Structured Edge detector (d) Performance Evaluation (15%)
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 of a machine-generated edge map. However, different people may have different opinions about the importance of different edges 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 the 5 ground truth edge maps for the Helicopter image. To evaluate the performance of a generated edge map, we need to identify the error. Every pixel in a generated edge map will be belong to either of the following four classes:
(i) True positive: Edge pixels in the edge map coincide with edge pixels in the ground truth. These are edge pixels the algorithm successfully identifies.
(ii) 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.
(iii) 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.
(iv) 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 (i) and (ii) are correct ones while those in (iii) and (iv) are error pixels of two different types. 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 :P = #True Positive
#True Positive + #False Positive
Recall:R = #True Positive (1)
#True Positive + #False Negative
F= 2⋅ P⋅R P+R
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.
Ground Truth 4 Ground Truth 5
Figure 3: Five ground truth edge maps for the Helicopter image
For the ground truth edge maps of Gallery and Dogs images, evaluate the quality of edge maps obtained in Parts (a)-(c) with the following steps:
(1) Calculate the precision and recall for each ground truth (provided 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 - Gallery or Dogs? 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.
Problem 2: Digital Half-toning
(a) Dithering
Figure 4 Light House is a grayscale image. Implement the following methods to convert it to half-toned images. In the following discussion, 𝐹(𝑖, 𝑗) and 𝐺(𝑖, 𝑗) denote the pixel at position (𝑖, 𝑗) in the input and output images respectively. Show and compare the results obtained by the following algorithms in your report.
Figure 4: Light House [4]
1. Fixed thresholding
Choose one value, T, as the threshold to divide the 256 intensity levels into two ranges. An intuitive choice of T would be 128. For each pixel, map it to 0 if it is smaller than T, otherwise, map it to 255, i.e.
0 if 0 ≤ 𝐹(𝑖, 𝑗) < 𝑇
𝐺(𝑖, 𝑗) = )255 if 𝑇 ≤ 𝐹(𝑖, 𝑗) < 256
2. 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 the pixel value 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 from uniformly distributed random variables. Check your coding language documentation for proper random variable generator.
3. 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
𝐼:(𝑖, 𝑗) = ;13 20
where 0 indicates the pixel that is the 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 firstly introduced by Bayer [5]. The Bayer index matrices are defined recursively using the formula:
𝐼:?(𝑖, 𝑗) = @44 ×× 𝐼𝐼??((𝑖𝑖,, 𝑗𝑗)) ++ 31 4 ×4 ×𝐼?(𝐼?𝑖,(𝑗𝑖), 𝑗+) 2D
The index matrix can then be transformed into a threshold matrix T for an input grayscale image with normalized pixel values (i.e. with its dynamic range between 0 and 255) by the following formula:
𝑇(𝑥, 𝑦) = 𝐼 G(𝑥, 𝑁𝑦):+ 0.5 × 255
where 𝑁: denotes the total number of pixels in the threshold matrix, and (𝑥, 𝑦) is the location 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:
𝐺(𝑖, 𝑗) = J 0 𝑖𝑓 𝐹(𝑖, 𝑗) ≤ 𝑇(𝑖 𝑚𝑜𝑑 𝑁, 𝑗 𝑚𝑜𝑑 𝑁)
𝑒𝑟𝑤𝑖𝑠𝑒
Please create 𝐼:, 𝐼R, 𝐼S: threshold matrices and apply them to halftone Light House (Fig. 4). Compare your results.
(b) Error Diffusion
Convert the 8-bit Light House 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 method in part (a). Which method do you prefer? Why?
(1) Floyd-Steinberg’s error diffusion with the serpentine scanning, where the error diffusion matrix is:
1 0 0 0
T0 0 7V
16 3 5 1
(2) Error diffusion proposed by Jarvis, Judice, and Ninke (JJN), where the error diffusion matrix is:
0 0 0 0 0
1 ⎡⎢0 0 0 0 0⎤⎥
48 ⎢⎢03 05 07 75 53⎥⎥
⎣1 3 5 3 1⎦
(3) Error diffusion proposed by Stucki, where the error diffusion matrix is:
0 0 0 0 0
1 ⎡0 0 0 0 0⎤⎥
⎢
42 ⎢⎢02 04 08 84 42⎥⎥
⎣1 2 4 2 1⎦
Describe your own idea to get better results. There is no need to implement it if the time is limited. However, please explain why your proposed method will lead to better results.
(c) Color Halftoning with Error Diffusion
Figure 5: The Rose image [6]
(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 Rose image. What is the main shortcoming of this approach?
(2) MBVQ-based Error diffusion
Shaked et al. [7] proposed a new error diffusion method, which can overcome the shortcoming of the separable error diffusion method. Please read [7] 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 Floyd-Steinberg error diffusion) and apply it to Fig. 5. Compare the output with that obtained by the separable error diffusion method.
Appendix:
RGB to grayscale conversion:
𝑌 = 0.2989 ∗ 𝑅 + 0.5870 ∗ 𝐺 + 0.1140 ∗ 𝐵
Problem 1: Edge detection
Gallery.raw 321x481x3 (Height×Width×Band)
24-bit
color (RGB)
Dogs.raw 321x481x3
24-bit
color (RGB)
Gallery.jpg 321x481x3
24-bit
color (RGB)
Dogs.jpg 321x481x3
Gallery_GT.mat (containing 5 ground truth annotations)
Dogs_GT.mat (containing 5 ground truth annotations)
(The following three are examples)
24-bit
color (RGB)
Helicopter.jpg 321x481x3
24-bit
color (RGB)
Helicopter_prob.png 321x481
8-bit
gray
Helicopter_binary.png 321x481
Problem 2: Digital Half-toning
8-bit
gray
LightHouse.raw 500x750
8-bit
gray
Rose.raw 480x640x3
24-bit
color (RGB)
(a) Sobel Edge Detector
Implement the Sobel edge detector and apply to Gallery.raw and Dogs.raw images as shown in Fig. 1 (a) and (b). Note that you need to convert RGB images to grayscale image first. The relationship between RGB and grayscale images are provided in the Appendix. Include the following in your results:
(1) Normalize the x-gradient and the y-gradient values to 0-255 respectively and show the results;
(2) Calculate and show the normalized gradient magnitude map;
(3) Tune the thresholds (in terms of percentage) to obtain an edge map with the best visual performance. The final edge map should be a binary image whose pixel values are either 0 (edge) or 255 (background).
(b) Canny Edge Detector
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 Gallery.jpg and Dogs.jpg images from the Berkeley Segmentation Dataset and Benchmarks 500 (BSDS 500) [2]. 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).
(1) Explain the Non-maximum suppression in Canny edge detector in your own words.
(2) How are high and low threshold values used in Canny edge detector?
(3) Generate edge maps by trying different low and high thresholds and discuss your results.
Figure 1: Gallery and Dogs images
(c) Structured Edge
Apply the Structured Edge (SE) detector [3] to extract edge segments from a color image with online source codes (released toolbox in MATLAB: https://github.com/pdollar/edges). Exemplary edge maps generated by the SE method for the Helicopter image from BSDS 500 are shown in Figure 2. You can apply the SE detector to 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 Gallery.jpg and Dogs.jpg 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.
Helicopter Probability edge map (inversed) Binary edge map (with p0.2)
Figure 2: The Helicopter image and its probability and binary edge maps obtained by the Structured Edge detector (d) Performance Evaluation (15%)
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 of a machine-generated edge map. However, different people may have different opinions about the importance of different edges 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 the 5 ground truth edge maps for the Helicopter image. To evaluate the performance of a generated edge map, we need to identify the error. Every pixel in a generated edge map will be belong to either of the following four classes:
(i) True positive: Edge pixels in the edge map coincide with edge pixels in the ground truth. These are edge pixels the algorithm successfully identifies.
(ii) 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.
(iii) 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.
(iv) 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 (i) and (ii) are correct ones while those in (iii) and (iv) are error pixels of two different types. 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 :P = #True Positive
#True Positive + #False Positive
Recall:R = #True Positive (1)
#True Positive + #False Negative
F= 2⋅ P⋅R P+R
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.
Ground Truth 4 Ground Truth 5
Figure 3: Five ground truth edge maps for the Helicopter image
For the ground truth edge maps of Gallery and Dogs images, evaluate the quality of edge maps obtained in Parts (a)-(c) with the following steps:
(1) Calculate the precision and recall for each ground truth (provided 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 - Gallery or Dogs? 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.
Problem 2: Digital Half-toning
(a) Dithering
Figure 4 Light House is a grayscale image. Implement the following methods to convert it to half-toned images. In the following discussion, 𝐹(𝑖, 𝑗) and 𝐺(𝑖, 𝑗) denote the pixel at position (𝑖, 𝑗) in the input and output images respectively. Show and compare the results obtained by the following algorithms in your report.
Figure 4: Light House [4]
1. Fixed thresholding
Choose one value, T, as the threshold to divide the 256 intensity levels into two ranges. An intuitive choice of T would be 128. For each pixel, map it to 0 if it is smaller than T, otherwise, map it to 255, i.e.
0 if 0 ≤ 𝐹(𝑖, 𝑗) < 𝑇
𝐺(𝑖, 𝑗) = )255 if 𝑇 ≤ 𝐹(𝑖, 𝑗) < 256
2. 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 the pixel value 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 from uniformly distributed random variables. Check your coding language documentation for proper random variable generator.
3. 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
𝐼:(𝑖, 𝑗) = ;13 20
where 0 indicates the pixel that is the 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 firstly introduced by Bayer [5]. The Bayer index matrices are defined recursively using the formula:
𝐼:?(𝑖, 𝑗) = @44 ×× 𝐼𝐼??((𝑖𝑖,, 𝑗𝑗)) ++ 31 4 ×4 ×𝐼?(𝐼?𝑖,(𝑗𝑖), 𝑗+) 2D
The index matrix can then be transformed into a threshold matrix T for an input grayscale image with normalized pixel values (i.e. with its dynamic range between 0 and 255) by the following formula:
𝑇(𝑥, 𝑦) = 𝐼 G(𝑥, 𝑁𝑦):+ 0.5 × 255
where 𝑁: denotes the total number of pixels in the threshold matrix, and (𝑥, 𝑦) is the location 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:
𝐺(𝑖, 𝑗) = J 0 𝑖𝑓 𝐹(𝑖, 𝑗) ≤ 𝑇(𝑖 𝑚𝑜𝑑 𝑁, 𝑗 𝑚𝑜𝑑 𝑁)
𝑒𝑟𝑤𝑖𝑠𝑒
Please create 𝐼:, 𝐼R, 𝐼S: threshold matrices and apply them to halftone Light House (Fig. 4). Compare your results.
(b) Error Diffusion
Convert the 8-bit Light House 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 method in part (a). Which method do you prefer? Why?
(1) Floyd-Steinberg’s error diffusion with the serpentine scanning, where the error diffusion matrix is:
1 0 0 0
T0 0 7V
16 3 5 1
(2) Error diffusion proposed by Jarvis, Judice, and Ninke (JJN), where the error diffusion matrix is:
0 0 0 0 0
1 ⎡⎢0 0 0 0 0⎤⎥
48 ⎢⎢03 05 07 75 53⎥⎥
⎣1 3 5 3 1⎦
(3) Error diffusion proposed by Stucki, where the error diffusion matrix is:
0 0 0 0 0
1 ⎡0 0 0 0 0⎤⎥
⎢
42 ⎢⎢02 04 08 84 42⎥⎥
⎣1 2 4 2 1⎦
Describe your own idea to get better results. There is no need to implement it if the time is limited. However, please explain why your proposed method will lead to better results.
(c) Color Halftoning with Error Diffusion
Figure 5: The Rose image [6]
(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 Rose image. What is the main shortcoming of this approach?
(2) MBVQ-based Error diffusion
Shaked et al. [7] proposed a new error diffusion method, which can overcome the shortcoming of the separable error diffusion method. Please read [7] 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 Floyd-Steinberg error diffusion) and apply it to Fig. 5. Compare the output with that obtained by the separable error diffusion method.
Appendix:
RGB to grayscale conversion:
𝑌 = 0.2989 ∗ 𝑅 + 0.5870 ∗ 𝐺 + 0.1140 ∗ 𝐵
Problem 1: Edge detection
Gallery.raw 321x481x3 (Height×Width×Band)
24-bit
color (RGB)
Dogs.raw 321x481x3
24-bit
color (RGB)
Gallery.jpg 321x481x3
24-bit
color (RGB)
Dogs.jpg 321x481x3
Gallery_GT.mat (containing 5 ground truth annotations)
Dogs_GT.mat (containing 5 ground truth annotations)
(The following three are examples)
24-bit
color (RGB)
Helicopter.jpg 321x481x3
24-bit
color (RGB)
Helicopter_prob.png 321x481
8-bit
gray
Helicopter_binary.png 321x481
Problem 2: Digital Half-toning
8-bit
gray
LightHouse.raw 500x750
8-bit
gray
Rose.raw 480x640x3
24-bit
color (RGB)
1 file (19.0MB)
