Correlation is more intuitive, so we use correlation to implement convolution k k C(m, n) k=1 h ∑hm(-m+j,-m+k)×(j,k) k=0 2153 j=01 Flip h k (m=0,n=0) 11 Discrete convolution I*h, flip h, shift h and correlate with I [1] Tutorial for CMSC5711: Edge vo. 1a
Correlation is more intuitive, so we use correlation to implement convolution. • = =− = =− − + − + = j j k k flip h m j n k I j k C m n ( , ) ( , ) ( , ) ( ) ( ) 1 4 1 1 1 , 2 5 3 1 1 1 1 ( 0, 0) , 1 1 flip I h h m n = = − − = = = j k j k k j Flip h Discrete convolution I*h, flip h ,shift h and correlate with I [1] j=0 1 2 j=0 1 k=1 k=0 j=0 1 Tutorial for CMSC5711 : Edge v0.1a 21
Discrete convolution /*h, flip h shift h and correlate with /1 ∑∑0m(-m+1-n+k)×1(,k) h Flip h: is like this after the多入0 C(m, n) m and no shift (m=o, n=0 h lip) The trick: I(j=o, k=0) needs to (m=0,n=0) Itiply to hip/f-mo, n+O) 1 1P since m=l, n=0, so we shift the pattern 1-bit to the right so Shift Flipped h to m=l, n=0 we just multiply overlapped elements of I and hElp/. Similarly k we do the same for all m,n h1n(m=1,n=0)= values Tutorial for CMSC571: Edge vo. 1a
Discrete convolution I*h, flip h ,shift h and correlate with I [1] • = =− = =− − + − + = j j k k flip h m j n k I j k C m n ( , ) ( , ) ( , ) ( ) ( ) 1 4 1 1 1 , 2 5 3 1 1 1 1 ( 0, 0) , 1 1 flip I h h m n = = − − = = = j k j k k j Flip h: is like this after the flip and no shift (m=0,n=0) ( ) 1 1 ( 1, 0) , 1 1 flip h m n − = = = j k Shift Flipped h to m=1,n=0 m n j=0 1 C(m,n) The trick: I(j=0,k=0) needs to multiply to h (flip)(-m+0,-n+0), since m=1, n=0, so we shift the h (flip) pattern 1-bit to the right so we just multiply overlapped elements of I and h (flip) . Similarly, we do the same for all m,n values Tutorial for CMSC5711 : Edge v0.1a 22
Find clm, n) C(m,n) J=∞ ∑∑h(-m+j,一n+k)×(,k) Shift Flipped h to m1, n=0 K K 253 h1/0(m=1,n=0) multiply overlapped elements and add(see next slide) hence,C(m=1,n=0)=-2+5=3, Tutorial for CMSC5711: Edge vo. 1a
Find C(m,n) • = =− = =− − + − + = j j k k flip h m j n k I j k C m n ( , ) ( , ) ( , ) ( ) Shift Flipped h to m=1,n=0 ( ) 1 1 ( 1, 0) , 1 1 flip h m n − = = = K J hence, ( 1, 0) 2 5 3, C m n = = = − + = 1 4 1 2 5 3 I = J K multiply overlapped elements and add (see next slide) Tutorial for CMSC5711 : Edge v0.1a 23
C(m, n) Find clm, n) ∑∑hm(-m+j-n+k)x/(,k) Shift Flipped h to m1, n=0 141 121513」 m(m=1,n=0)= C(m, n) multiply overlapped elements and add C(m=1,n=0)=(2×-1)+(5×1)=3 Tutorial for CMSC5711: Edge vo. 1a
Find C(m,n) • = =− = =− − + − + = j j k k flip h m j n k I j k C m n ( , ) ( , ) ( , ) ( ) Shift Flipped h to m=1,n=0 ( ) 1 1 ( 1, 0) , 1 1 flip h m n − = = = K J C m n ( 1, 0) (2 1) (5 1) 3, = = = − + = 1 4 1 2 5 3 I = J K multiply overlapped elements and add m n C(m,n) Tutorial for CMSC5711 : Edge v0.1a 24
Steps to find C(m, n) Step1: Step 3 141 C(0,0 C(2,0) =1x2=2 1*5+1*3 2 Step 2: C(10) 14 ●Step4 141 =-1*2+1*5=3 25 C(3,0) -1*3 11 3 c(00) c(1,0) c(2,0) c(30) C(m, n)= C(0,0 C(1,0) C(2,0) C(3,0) C(0,0)=2c(10)=3C(2,0)=2C(3,0)=3 Tutorial for CMSC5711: Edge vo. 1a
Steps to find C(m,n) • Step1: • C(0,0) • =1x2=2 • Step 2: • C(1,0) • = -1*2+1*5=3 • Step 3: • C(2,0) • = -1*5+1*3 • =-2 • Step 4: • C(3,0) • = -1*3 • =-3 1 4 1 2 5 3 -1 1 1 1 1 4 1 2 5 3 -1 1 1 1 1 4 1 2 5 3 -1 1 1 1 1 4 1 2 5 3 -1 1 1 1 C(m,n)= C(0,0) C(1,0) C(2,0) C(3,0) C(0,0) C(1,0) C(2,0) C(3,0) C(0,0)=2 C(1,0)=3 C(2,0)=-2 C(3,0)=-3 Tutorial for CMSC5711 : Edge v0.1a 25