Filters in Image Processing Edge Detection David Svoboda email: svoboda@fi.muni.cz Centre for Biomedical Image Analysis Faculty of Informatics, Masaryk University, Brno, CZ CQIA November 15, 2019 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 1/65 Outline Q Fundamentals Q First Derivative Based Q Second Derivative Based Q Template Based Q Scale-Space Based Q Edge Evaluation Methods David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 2 / 65 Fundamentals O O Vm» vJ David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 3 / 65 Motivation Edge detection - the most commonly used operation in image analysis. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 4 / 65 Motivation What is an edge? • black-white interface • texture interface black-white interface with colour interface David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 5 / 65 Motivation What is an edge? variance based edge David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 6 / 65 Motivation What is an edge? There is a number of possible definitions of an edge: • step edge - the edge is simply a change in grey level occurring at one specific location • ramp edge - the actual position of the edge is considered to be the center of the ramp • roof edge - lambda shaped signal 9 line edge - S impulse in signal • variance (texture) base edge - a change in variance levels Notice: Edges are significant and abrupt changes in a signal. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 7 / 65 Edge Detection Principal Approaches • First derivative based • Gradient magnitude - strength of an edge: W(x,y) df_ dx df_ dy or max df_ dx df_ dy • Gradient direction - direction perpendicular to an edge: W(x,y) or 9 = tan -1 Í dy_ dx Second derivative based - zero crossings of the second derivative Template matching based David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 8 / 65 First Derivative Based O O Vm» vJ David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 9 / 65 First Derivative Based Analysis High-frequent 1-D perturbation f(x) = es\n (^j become arbitrary small for s —> 0. However, its derivative rit \ 1 (x f(x) = - cos (72 exceeds all bounds. Notice: High-frequent fluctuations (noise) in the original signal can create unbounded perturbation in its derivatives. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 10 / 65 First Derivative Based Analysis Interpretation in the Fourier domain a ID T dmf • 2D Qtn+nf T ( ^ ^ ) (üüx,üüy) = {2TTÍUJx)n{2TTÍUJy)mJ:{f){uJx,UJy) dxndy m Derivatives in the spatial domain lead to the multiplication in the Fourier domain. Thus, high-frequency components (e.g. noise) are amplified. Remedy: Perform lowpass (e.g. Gaussian smoothing) filtering before computing derivative! David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 11 / 65 First Derivative Based Gradient Estimator \Vf(m,n)\ = y/(Axf(m, n)f + (Ayf(m, n)f Version 1 Version 2 Axf(m,n) Ayf(m, n) f(m, n) — f(m — 1, n) f(m, n) — f(m, n — 1) Axf(m,n) Ayf(m, n) f(m + 1, n) - f(m - 1, n) n + 1) - n - 1) Notice: A ... difference operator David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 First Derivative Based Roberts Operator Diagonally oriented operator • One of the oldest edge detectors with the following convolution masks: +1 0 0 -1 (a) Rx 0 +1 -1 0 (b) Ry Figure: Roberts kernels |Vf(m,n)| = \f(m,n)-f(m + l,n + l)\ + \f{m,n+l)-f(m + l,n)\ David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 First Derivative Based Sobel Operator • Based on two convolution kernels and Sv: 1 0 -1 1 2 1 2 0 -2 0 0 0 1 0 -1 -1 -2 -1 (a)S X (b)S y Figure: Sobel kernels \Vf(m,n)\ = ^(Axfy_smooth(m, n))2 + (Ayfx_smooth(m, n)): David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 First Derivative Based Canny Edge Detector John Canny [Canny-86] specified three criteria that an edge detector must address: o Error rate - the edge detector should respond only to edge, and should find all of them; no edges should be missed • Localization - the distance between the edge pixels as found by the edge detector and the actual edge should be as small as possible • Response - the edge detector should not identify multiple edge pixels where only a single edge exists Canny assumed: • A step edge subject to white Gaussian noise. • The edge detector was a convolution filter p that would smooth the noise and locate the edges. • The problem was to identify the filter that optimizes the three edge detection criteria. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 15 / 65 First Derivative Based Canny Edge Detector In one dimension, the response of the filter p(x) of width 1/1/ to an edge is given by the convolution: w h(x)= J f(t)p(x-t)dt -w where f(t) denotes the input signal. The three criteria are expressed as: Error rate: Localization Response: x 2 0 oo A f p(x)dx SNR=^- a f p2(x)dx -w Loc = _ V(o) w Xzc = 7T a f [p'{x)Ydx -w -oo oo jf p/2(x)dx -oo David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 16 / 65 First Derivative Based Canny Edge Detector - Filter Design o Canny attempts to find the filter p that maximizes the product SNR x Loc subject to the multiple-response constraint. • The result is too complex to be solved analytically. • An efficient approximation turns out to be the first derivative of a Gaussian g(x) — e ^2: x x2 P(X) « g (X) =--?e 2a2 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 17 / 65 First Derivative Based 2D Canny Edge Detector - Filter Design First, the gradient direction r(x,y) is estimated at some point (x, If the image is noise free then r(x,y) = W(x,y). Unfortunately, the image is usually noisy therefore we smooth the image by Gaussian .2 i w2a /o~2 G{x,y) = e-(x+YV2a- Thus, we have V(G*f)(x,y) ||V(G*f)(x,y)||- • We know that ID Canny filter is equal to the derivative of the Gaussian. For that reason we compute dG Gr = dr David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 18 / 65 First Derivative Based 2D Canny Edge Detector - Filter Design • Edge points show up as local maxima in the gradient image, and so if there is an edge passing through (x,y) in the direction r(x,y) then there will be a local maximum in the image convolved with Gr, so that d_ dr (Gr*f) = 0. • The gradient magnitude at this point will be: Gr*f|| = ||(r- VG)*f VG* f Note that and _ ^ , OG r OG (VG * f) = [ — * f, — * f dx dy dG d = " -(*2+yW = _2xe-(x*+rW = ^(x)^(y) 2 i w2 <9x <9x David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 19 / 65 First Derivative Based 2D Canny - Algorithm O Read in the image f to be processed. O Create a ID Gaussian mask g to convolve with f. The standard deviation a of this Gaussian is a parameter to the edge detector. O Create a ID mask for the first derivative of the Gaussian in the x and y direction; call these gx and gy. The same a value is used as in step 2 above. O Convolve the image f with g along the rows to give the x component image fXt and down the columns to give the y component image fy. Q Convolve fx with gy (orthogonal directions) to give f£, the x component of f convolved with the derivative of the Gaussian, and convolve fy with gx to give fy. O The magnitude of the result is computed at each pixel (x,y) as: |VG * f(x,y)\ = ^(x,y)2 + f;(x,y)2 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 20 / 65 First Derivative Based Canny Edge Detector - post-processing Nonmaxima Suppression • Goal: thinning of edges to a width of 1 pixel o In every edge pixel, consider the grid direction (out of 4 directions) that is "most orthogonal" to the edge. • If one of the two neighbours in this direction has a larger gradient magnitude, remove the central pixel from the edge map. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 21 / 65 First Derivative Based Canny Edge Detector - post-processing Hysteresis Thresholding • Goal: extract only relevant edges. • Use points above the upper threshold as seed points of relevant edges. • Add all neighbours that are below the upper threshold, but above the lower threshold. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 22 / 65 First Derivative Based Canny Edge Detector — Summary Some Important Properties • One of the most popular edge detectors (benchmark) • Taken as "ground truth" among the others • Optimal under certain conditions (step edges & white Gaussian noise) • Canny does not produce continuous edges David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 23 / 65 First Derivative Based Rothwell Edge Detector Uses the idea of Canny but modifies the "nonmaxima suppression" step, since the edge direction is not correct near corners and junctions: • topological based approach 9 thinning (nonmaxima suppression) is modified to preserve topological properties of the objects in the image David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 24 / 65 First Derivative Based Rothwell Edge Detector An example Figure: (left) original image; (centre) Canny output; (right) Rothwell modified edge detector output David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 25 / 65 Q Second Derivative Based David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 Second Derivative Based Edge Detectors Idea: A maximum of the first derivative, i.e. an edge, will occur at a zero crossing of the second derivative. The most typical (ID) approximation: Standard (2D) approximation using Laplacian: V2f"(m, n) = fxx{m, n) + fyy(m, n) / 0 1 0 \ V2*^ 1-4 1 V 0 10/ ■ David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 27 / 65 Second Derivative Based Edge Detectors Disadvantages: • does not only detect maxima of the first derivative, but also the minima • very sensitive to noise o strong Gaussian smoothing is required —> derealization • does not detect edge direction —> first derivative evaluation is required Advantages: generate closed contours • rotationally symmetric o orientation-independent (if the local intensity change is nearly linear) • no input parameters but the width of Gaussian David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 28 / 65 Second Derivative Based Edge Detectors Laplacian of Gaussian (Marr-Hildreth) x2+y2 o Given smoothing kernel: G(x,y) = —e 2a2 • Laplacian of G(x,y): V2G(x,y) = - (x2+y2)-rr x2+y2 a is called "Laplacian of Gaussian (LoG)" e 2a2 Example: 5x5 LoG filter mask 0 0 -1 0 0 0 -1 -2 -1 0 -1 -2 16 -2 -1 0 -1 -2 -1 0 0 0 -1 0 0 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 29 / 65 Second Derivative Based Edge Detectors Laplacian of Gaussian Due to its shape, LoG is called the Mexican hat function 0.01 0.008 0.006 0.004 0.002 0 ■0.002 ■0.004 ■0.006 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 30 / 65 Second Derivative Based Edge Detectors Laplacian of Gaussian - an example David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 31 / 65 Second Derivative Based Edge Detectors Laplacian of Gaussian - an example David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 31 / 65 Second Derivative Based Edge Detectors Difference of Gaussians (DoG) • DoG is close approximation to the LoG filter • Convolution kernel is given by DoG = Gai - Ga2 where 0 • optimal filter function (ISEF for 2D): g{x,y) = a • e-rtW+M) • this produces better signal to noise ratios and better localization than Canny. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 33 / 65 Second Derivative Based Edge Detectors Shen-Castan Edge Detector David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 34 / 65 Second Derivative Based Edge Detectors Shen-Castan Edge Detector - Algorithm O Convolve the input image with the ISEF Q Localize edges by subtracting the original image from the smoothed one (similar to the Marr-Hildreth algorithm) O A binary Laplacian image is generated by setting all the positive valued pixels to 1 and all others to 0 O The candidate pixels are on the boundaries of the regions in the binary image Q Postprocessing: • false zero-crossing suppression (similar to Canny nonmaxima suppression) • hysteresis thresholding David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 35 / 65 Template Based David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 36 / 65 Template Based Edge Detectors The idea is to use a small discrete template as model of an edge. 2D specific: • several convolution kernels are created by rotating one "seed kernel" • kernel with maximum response (e.g. correlation) defines the result at given location clockwise rotation clockwise rotation clockwise rotation B B B A A A A A A B B B B B A B A A A A B A B B A B A B A B B A B A B A A A A B B B B B B A A A David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 37 / 65 Template Based Edge Detectors Common (Linear) Edge Detectors Kirsch operator: -3 -3 5 -3 0 5 -3 -3 5 Prewitt operator: 1 1 1 0 0 0 -1 -1 -1 Robinson operator: 1 1 1 1 -2 1 -1 -1 -1 Sobel operator: 1 0 -1 2 0 -2 1 0 -1 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 38 / 65 Template Based Edge Detectors (Nonlinear) Goodness-Of-Fit Test Based Edge Detection position 1 position 3 • position 1: mean a • position 2: mean a o position 3: \ mean a means means meanß\ is very high number David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 39 / 65 Template Based Edge Detectors (Nonlinear) Goodness-Of-Fit Test Based Edge Detection o position 1: no match with given template • position 2: bad match • position 3: edge found David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 39 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle For each point (x,y) of the image f\ O apply the mask: Q measure & rotate O measure & rotate | \^ f (-^^ 5 j | i s t h e ed ^^e ©cms the edge direction - collect A pixels A - collect B pixels B - compute "goodness-of-fit" test over A and B David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle For each point (x,y) of the image f\ O apply the mask: Q measure & rotate O measure & rotate O measure | \^ ^ y | is thg GcJsti^gnh ©cms the edge direction - collect A pixels A - collect B pixels B - compute "goodness-of-fit" test over A and B David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle For each point (x,y) of the image f: O apply the mask: © measure & rotate O measure & rotate O measure 0 find the highest measure | \^ / (j j | is the ed^^e st\ O a is the edge direction collect A pixels A collect B pixels B compute "goodness-of-fit" test over A and B David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle For each point (x,y) of the image f: O apply the mask: © measure & rotate O measure & rotate O measure 0 find the highest measure O |W(x,y)| is the edge strength O a is the edge direction \\7f(x,y)\ = max (measure (A. a David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle For each point (x,y) of the image f: O apply the mask: © measure & rotate O measure & rotate O measure 0 find the highest measure O |W(x,y)| is the edge strength O ol is the edge direction \\7f(x,y)\ = max (measure (A. a David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Basic principle For each point (x,y) of the image f\ O apply the mask: Q measure & rotate O measure & rotate O measure 0 find the highest measure 0 \\7f(x,y)\ is the edge strength O a is the edge direction \Vf(x,y)\ = max (measure {A, B)) a David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 40 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection The use of various statistics The measure is a tool for edge detection in the location between two different neighbouring areas. Two sample goodness-of-fit test deciding whether chosen datasets A a B differ may be: • Student's T test (mean and variance) a Fisher/Likelihood-test (variance) 9 %2-test (frequency) • Kolmogorov-Smirnov test (cumulative distribution) • Wilcoxon test (distribution) • simply mean difference • etc ... David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 41 / 65 Template Based Edge Detectors Goodness-Of-Fit Test Based Edge Detection Advantages • offer similar ability as traditional gradient based detectors • give better performance on noisy images and texture images 9 the statistical filter incorporates a process of edge tracking inherent within the algorithm Drawbacks • slower o due to predefined templates these cannot find corners correctly David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 42 / 65 Scale-Space Based David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 Scale-Space Based Interesting Observation • Structures that can be detected at a coarse scale a can be traced back to smaller scales in order to improve their localization • This has led to the notion of scale-space: Embed an image in a continuum of more and more smoother versions of it. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 44 / 65 Scale-Space Based David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 45 / 65 Edge Evaluation Methods David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 46 / 65 Edge Evaluation Methods Fundamentals How to solve the problem of evaluating the performance of edge detectors? Given ground truth (GT) image and the edge map (EM), we can report the following statistics: 9 true positive (TP) 9 false positive (FP) 9 true negative (TN) • false negative (FN) Monitoring of only one measure may lead to wrong conclusions. Tuning a detector to increase the TP score generally also results in a higher FP score. • sensitivity = TP/(TP+FN) • specificity = TN/(TN+FP) • accuracy = (TP+TN)/(TP+FN+TN+FP) David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 47 / 65 Edge Evaluation Method List of the most utilized evaluation methods: • Utilization of Canny's edge detector as a benchmark [Canny] • Pratt's Figure of Merit [Pratt] • Local Coherence [Kitchen] • ROC curves [Bowyer] • Pixel Correspondence Metric [Prieto] Notice: Keep in mind, that the majority of similarity metrics manage binary data (binary edges). David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 48 / 65 Pratt's Figure Of Merit (FOM) The similarity measure designed by Pratt is defined as follows: * Iem -t 1 = 1 where • Iqt ... number of pixels in GT 9 Iem ■ ■ ■ number of pixels in edge map • //v = max(/GT, Iem) (3 ... scaling (magic) constant (typically set to 1/9) • d . . .separation distance between an actual edge pixel in EM and its correct position in the GT • FOM = 1 is valid for perfect match David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 49 / 65 Local Edge Coherence The aim of this measure is to inspect the thinness and coherence of an edge in each pixel. Legend: • brown ... edge pink .. . inspected pixel • arrows ... gradient direction David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 50 / 65 Local Edge Coherence Given an edge direction d at some given x pixel we measure: how well an edge pixel x is continued on the left L(k) = if neighbour k is an edge pixel o, otherwise where d is the edge direction at the pixel being tested, do is the edge direction at its neighbor to the right, d\ is the direction of the upper-right neighbour, and so on counterclockwise about the pixel involved. The function dist is a measure of the angular difference between any two angles: dist (a, ß) = 7T — \ol — ß\ TT d3 d4 d2 d6 k = 3 •ííc David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 51 / 65 Local Edge Coherence Q A similar function measures directional continuity on the right of the pixel x: R(k) = if neighbour k is an edge pixel 0, otherwise David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 52 / 65 Local Edge Coherence O The overall continuity measure C is taken to be the average of the largest value of L(k) and the largest value of R(k). O An edge should be thin line, one pixel wide. The thinness measure 7 is the fraction of the six pixels in the 3x3 neighbourhood, excluding the center and the two pixels found by L(k) and R(k), that are the edge pixels. 0 The overall evaluation of the edge detector is E2 =7c +(1-7)7 where 7 is a constant. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 53 / 65 ROC curves Definition Let ground truth (GT) be a reference image in which: • black ... edge 9 gray ... no-edge • white .. . "don't care 7 1 ROC = Receiver Operating Characteristics David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 54 / 65 ROC curves Algorithm 0.15 Airplane Image - Iteration 1 (4x4x7) O Sample the parameter space of an edge detector. Q For each sample do • execute the edge detector, • evaluate FN and FP count, • put (FN, FP)-point into the graph. O Analyze the points and construct the ROC curve. 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.J % Unmatched GT Edges ROC curve construction A point P appears on the ROC curve only if no other point is included in the axis-oriented rectangle demarcated by origin (0,0) and P. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 55 / 65 ROC curves Aggregation • Average several ROC curves, each generated from different image. • The ideal point is (FN,FP)=(0,0) —>> the ROC curve with the lower "area under the curve" is the better one. gl_i_i_i_i_i_i_:_i_ 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 % Unmatched GT Edges David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 56 / 65 Pixel Correspondence Metrie (PCM) Motivation The common evaluation methods classify this situation GT = ( 1 0 0 Vo 0 0 1 0 0 0 0 0 0 0 o / EM = ( 0 0 0 1 0 0 V o o 0 0 \ 0 0 1 0 0 0/ as one correctly detected edge pixel, one misdetection, and one false alarm The only mistake is the small diagonal shift! J David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 Pixel Correspondence Metrie (PCM) David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 58 / 65 Pixel Correspondence Metrie (PCM) What are "Bipartite Graphs"? Let Q{yE) be an undirected graph with vertex set V and edge set E. The graph Q is bipartite if the vertex set V can be partitioned into two disjoint sets V+ and V~\ o match A4 is a subset of E such that no two edges share a vertex • vertex is matched if it is incident to an edge in Ai and unmatched otherwise • edge is matched if it contained in Ai and unmatched otherwise David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 59 / 65 Pixel Correspondence Metrie (PCM) Separation Let f and g be two images of the same dimensions. The separation S between the pixels in positions (ij) and (/c, /) is defined as: S((/,i),(/c,/)) = E(max(|/c-/|,|/-i|)), where E(d) e [0; 1] is a normalized function that represents a weighting dependent on the chessboard distance between pixels: E(d) = (1,0.9,0.65,0.5) |c/ = 0... 3 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 60 / 65 Pixel Correspondence Metrie (PCM) Cost of match Let M(f^g) be some match between two images f and g. The cost of match of two particular pixels f(ij) and g(kj) is: C(f(i,j),g(k,l)) = l-S((iJ),(k,l))(l- \f(i,j)-g(k,l)\ max value Example: The cost of match between two pixels f(3,35) = 140 and g"(5,36) = 130 from 8-bit images is: C(f(3,35),s(5,36)) = 1-S((3,35),(5,36))- 1 - 10 140 - 130 255 1 - E(2) [ 1 - V ' \ 255 1 - 0.69(0.961) 0.337 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 61 / 65 Pixel Correspondence Metrie (PCM) Getting optimal match • EM & GT .. .two disjoint parts (\/+ and V~) of bipartite graph. • The weight of edge connecting pixels f(ij') and g(/c, /): W={C{f{i,j),g{k,l))-{max value)] • The cost of match for the whole graph C(M) is the accumulated value of • all the weights of the edges in Ai plus o the accumulated value of all the unmatched vertices (the value of the pixel that the vertex represents) • Optimal match Aiopt(f\ g) is a match with minimal cost among all possible matches. David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 62 / 65 Pixel Correspondence Metrie (PCM) Definition Pixel Correspondence Metrie PCM,(f,g) = 100 (l-C(^g|'g)) Some properties: a PCMv{f,g) e [0;100] • If images f = g then PCM^f.g) = 100 • Search for optimal match in bipartite graphs is too hard common way is to solve the task locally. • This method is capable of working with grayscale data. The David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 63 / 65 Bibliography • Lim, D. H. Robust edge detection in noisy images. Comput. Statist. Data Anal. v50. 803-812, 2006 • deSouza, P. Edge detection using sliding statistical tests. Comput. Vision Graphics Image Process. v23 il. 1-14, 1983 • Bowyer K. W., Kranenburg Ch., Dougherty S. Edge detector evaluation using empirical ROC curves, Computer Vision and Image Understanding 84 (1), October 2001, 77-103 • Prieto M. S., Allen A. R. A similarity metric for edge images, IEEE TPAMI 25 (10): pp 1265-1273; 2003 • Kitchen, L. and Rosenfeld, A. Edge Evaluation Using Local Edge Coherence, IEEE TSMC, Vol 11. 9:597-605, 1981 • Canny, J. A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8, 6 (Nov. 1986), 679-698. • Rothwell, C, Mundy, J., Hoffman, W. and Nguyen, V.-D. Driving Vision by Topology, Technical Report No. 2444, INRIA, 1994 • Marr, D. and Hildreth, E. Theory of edge detection. In Proc. Royal Soc. Lond., volume B 207, pages 187-217, 1980 Q Shen, J. and Castan, S. An optimal linear operator for step edge detection. Computer Vision, Graphics and Image Processing, 54(2):112-133, March 1992 • Witkin, A. P. Scale-space filtering, Proc. 8th Int. Joint Conf. Art. Intell., Karlsruhe, Germany, 1019-1022, 1983 David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 64 / 65 You should know the answers ... o What are the pros and cons of the first derivative based edge detection? Explain the idividual items. • Compare Sobel and Canny's operator. • Propose a simple pseudocode for nonmaxima suppression algorithm. • In terms of edge detection, what does zero-crossing mean? o How do we get/compute an edge direction by template based edge detectors? • Explain the use of sensitivity, specificity, and accuracy. Show the examples. • How would you measure the edge coherence? Explain in detail. • When constructing the ROC curves, what is the size of parametric space for Roberts operator? • When measuring the quality of edge detection, how would you assign the corresponding pixels from EM and GT? David Svoboda (CBIAOFI) Filters in Image Processing autumn 2019 65 / 65