RoA Threshold Computation

(1)

Chapter 8

Conclusions

This thesis presents a novel approach for linear feature extraction from high-resolution SAR images. The main methods for automatic linear landmark recognition base their whole procedure on edge detection. For this reason, edge detectors constitute the first step of the proposed processing chain.

Depending on the applications, the possibility of computing an analytical threshold, which might be applied on the filtered image to yield a desired PFA in output, could be desirable. For this reason, we evaluated the main statistical filters to accomplish such scope: the RoA [8], the T-test [12] and the W-test [13]. Neverthe- less, they are sensitive of the hypothesis underlying their theory. However, respecting the hypothesis of statistical independence among pixels without raise the complexity of the model can be done by a simple image downsampling. Instead, the hypothesis of pixels belonging to the same distribution limits the maximum size of the filtering window. Among all, the RoA edge detector yielded the best results followed in ranking by the T-test and the W-test. Nevertheless, since the RoA and the T-test edge detector need a certain distribution of the data (respectively Gamma and Normal), the W-test can be applied in the cases such hypotheses do not hold. To improve the final performance and reduce the multiple border problems, a weighted version of the RoA can be exploited. However, to keep the possibility of computing an analytical threshold even in such case, a novel statistical model was developed. Even though the presented model approximates the real pdf, which does not have closed form, it fits well the data and its mathematical treatability enables us to exploit the model in different way. For example, throughout the proposed model we found an interesting property of the RoA applied to linear borders: increasing the filtering window length makes raise their detection rate, even on very thin edges. Moreover, analytical computation of the performance varying the number of win- dows was possible by the proposed model, which also enables a performance improving to be reached on the subsequent linking stage.

Nevertheless, when more complicated models of the backscattering behavior are considered, the proposed statistical filter could not fit such data. In this case, the appropriate filters could involve several parameters whose estimation could be both difficult and time-consuming. In this sense, the simplicity and mathematical treatability of the model is often preferred to formal correctness. For this reason, and to reach a performance improving by a non-linear combination of pixels, the general multiscale linear filtering is investigated. In particular, exploiting different linear filters (Canny [25], Shen-Castan [33], Deriche [35], Paillou [36], and Quadratic Box Spline [27]), we evaluated several methods of scale combinations and automatic thresholding.

Our results show how all these filters are good when the noise power is low, and how their performance gets worse on real one-look CSK data.

However, the edge map retrieved by edge detectors can be refined and improved by a subsequent linking stage. For this purpose, we propose to use a modified version of the SEL algorithm [41] that models the linking issue as a shortest path problem (SPP). Actually, the original model was completely modified to solve the loops problem and to allow SEL to be used on the multiplicative noise case. Further in deep, both a parametric (“LR”) and a non-parametric (“Phy”) metric has been proposed to make the method generally applicable.

In our experiments LR metrics obtain the best performance and a further improving on the results can be reached by exploiting the model developed as general extension of the RoA edge detector.

(2)

Chapter 8 - Conclusions 201

The novel algorithm devised to extract linear features (e.g. roads and runways) relies on a modified version of the Hough Transform. In fact, each time a line is vectorized, its contribution is deleted in the transformed domain to dim the corresponding noise. Moreover, most of information that arises from the edge detection step is exploited to drive a correct vectorization. Then, a new approach to find theoretical sound bounds in the Hough Transform discretization has been followed. Surprisingly, the formulas derived with such methods are very near to the signal theory ones and they are tighter than those suggested following the rounding error theory alone [55]. Then, iterating the vectorizing procedure until all pixels are vectorized (even as single point), the object boundaries becomes a composition of linear segments. Next, thanks to a “grow and merge”

procedure, even a smooth curve in the road could be recognized as part of “grown line”. Finally, the road is recognized as composition of regions that are limited by symmetric “grown lines” and characterized by a low radar cross section (RCS) and high homogeneous material (low coefficient of variation). The results reported in this thesis confirm the feasibility of this approach for road extraction.

Finally, to improve edge detection performance and approach a higher level of processing, a novel despeck- ling algorithm is presented. In particular, we have presented a novel anisotropic diffusion filter that manages to combine normally contrasting requirements: reducing noise on homogeneous regions, preserving weak edges, and keeping corners and targets intact (maintaining them as seen in the original image). Moreover, since such filter is a PDE-based filter, no noise model is presupposed so that, in principle, it can be applied to any noise type. We want to emphasize that this last property has a strong impact on its possible application.

In fact, no mathematical modeling effort is required (e.g. statistical modeling of both noise and radar reflec- tivity) to change sensor or data type (e.g. intensity or amplitude). In addition, since the filtered image is a solution of a PDE, many theorems and properties hold for such a solution. Ultimately, visual impressions and performance indexes confirm that our techniques outperforms state-of-the-art filters for SAR image despeck- ling.

(3)

Appendixes

Appendix A

RoA Threshold Computation

In general, the computation of the threshold 𝑇 needs the inversion of the following equation:

{ }

(

r

)

^dr

r L N

L dr N

r f H

T r P P

T

L N L N T

H

FA r ∫

Γ +

= Γ

=∫

<

= ⁻

0 2 ˆ

ˆ 1 0 0 2

0 ( ˆ) 1

ˆ) 2 2 ( )

( (A. 1)

with Lˆ the estimated number of looks. The Fisher-Snedecor pdf f_F_u_,_v(r)is the following:

( )

²¹⁽ ⁾

) 2 2( 1 2 2 ,

2 1 2 1

2 1 2 1 )

(

v u v u u

v Fu

v ur

r v u v u

v u r

f − +

−

 +



 

 Γ



 

 Γ



 



 +

Γ

= (A. 2)

so that, changing variables:





=

= 2

2 v b

u

a (A. 3)

we have:

( )

( ) ( ) ( )

( )

( ) ( )

( )

( ) ( )

⁽ ⁾

) 1 (

) ) (

(

) 1 (

) (

) 1 ( ,

) 2 (

) 2 ( ) 2 (

2 2

) 2 ( ) 2 ) (

(

b a b a

b b a

a

a b a

b a

a b a v

Fu

a r b

r a b b a

b a

a r b a

r b a b a

b a

b ar

r b a b a

b r a

f

+

− + +

− +

−



 

 +



 



 Γ Γ

+

= Γ



 

 + Γ

Γ +

= Γ Γ + Γ

+

= Γ

(A. 4)

Now, setting a=b=NLˆin Eq. (A. 4) we have:

( )

^N^L

L N v

Fu H

r r

r L N

L r N

f r

f _ˆ

2 ˆ 1 2 0 ,

) 1 ( ˆ

ˆ) 2 ) ( ( 2 )

( Γ +

=Γ

= ⁻ (A. 5)

that is:

(4)

Appendix A 203

{

^r ^T^H

}

^P

{

^F ^T

}

P

P_FA= < ₀ =2 _u_,_v< ^{(A. 6)}

Now, relating the Fisher-Snedecor cdf with the Incomplete Beta function ^I_y

( )

^b^,^a [10]:

{

F T

}

I

( )

a b

P _u_,_v< = _y , ^{(A. 7)}

where:

aT b y b

− +

=1 (A. 8)

we have all the variable we need for the inversion. In fact, fixed the desired P , the threshold T can be _FA computed throughout the following passages:

• given N and Lˆ we compute a=b=NLˆ;

• given the P we compute _FA

{ }

, 2

FA v

u

T P F

P < = (see Eq. (A. 6));

• given a, b and^P

{

^Fu_,v<^T

}

, we compute y from (A. 7) exploiting the fast inversion method of the In- complete Beta function;

• given y we retrieve the threshold T by manipulating Eq. (A. 8), i.e. exploiting the following equation:

) 1

( y

a T by

= − (A. 9)

(5)

204 Appendix B

Appendix B

T-test Threshold Computation

The computation of the threshold 𝑇 needs the inversion of the following equation:

{ }

^dt

B v v

v t dt

t f H T t P P

T

v

T tH

FA ∫



 







 



 +

∫ =

=

>

= ^∞



 



− +

∞

2 , ˆ 2 ˆ 1 1 ˆ 2 ) (

2 ˆ 1 2

0 0

(B. 1)

we can prove [12], the following relation with the Fisher-Snedecor cdf holds:

{

^t ^T^H

}

^P

{

^F ^T ^u ^v ^v

}

P

P_FA= > ₀ = _u_,_v> ² =1, =ˆ (B. 2)

Then, exploiting the following relation [10]:

{ }





 



= 

>

= 2

,1 2

ˆ

0

I v H T t P

P_FA _x (B. 3)

where 



 



 2 ,1 2

I_x ˆv is the Incomplete Beta Fuction, and the following holds:

ˆ 2

ˆ T v x v

= + (B. 4)

Therefore, we have all the variable we need for the inversion. In fact, fixed the desired P , the threshold T _FA can be computed throughout the following passages:

• given vˆ , P and resorting to Eq. (B. 3), we compute x exploiting the fast inversion method of the _FA Incomplete Beta function;

• given x we retrieve the threshold T by manipulating Eq. (B. 4), i.e. exploiting the following equation:

x x

T = vˆ(1− ) (B. 5)

(6)

Appendix C 205

Appendix C

WMW-test Threshold Computation

The computation of the threshold 𝑇 needs the inversion of the following equation:

dw e dw

w f P

T

w

T WH

FA=^∞∫ =^∞∫ ⁻ ²

2

0 2

2 1 )

( π ^{(C. 1)}

it can be proved [10] that, given a r.v.G~ N(0,1), the following relation holds:

{

W TH

}

P

{

G T

}

P

P_FA= > ₀ =2 > ^{(C. 2)}

Given the symmetry OF Normal pdf we have:

{ }

2

{ }

2 ( )

2PG>T = P G<−T = Θ −T (C. 3)

where Θ(T) is the Normal cdf. Relating the Normal cdf to the Complemetary Error function erfc(⋅): )

( ) (

2 T erfc x

P_FA= Θ − = (C. 4)

with:

2 T

x= ^{(C. 5)}

we can exploit the fast inversion algorithm for this last function. Therefore, we have all the variable we need for the inversion. In fact, fixed the desired P , the threshold T can be computed throughout the following _FA passages:

• given theP we compute x exploiting the fast inversion method of the Complemetary Error func-_FA tion;

• given x we retrieve the threshold T by manipulating Eq. (C. 5), i.e. exploiting the following equation:

2 x

T = (C. 6)

(7)

206 Appendix D

Appendix D

Sums of Generic Gamma r.v.s: A Very Accurate Approximation

Given the following r.v.:



 

 Γ

+



 

 Γ +

= _∑ _∑

L NL NL N

L N X

X

Y₁ ^' ^'' ~ ₁ ,σ¹ ₂ ,σ² _{(D. 1)}

remembering that mean and variance of a generic Gamma r.v. are:

( )

[ ]

²

var ,

~

αβ αβ µ

β α

=

= Γ

X X

X (D. 2)

and considering the approximation of the sums of generic Gamma r.v.s distributed as a Gamma with mean and variance of the real pdf, we have:

[ ] [ ] [ ] [ ]

L N

N N L N

L N L N

L X N

X X

X Y

N N N NL

L N NL

L X N

E X E X X E Y

Y E

2 2 2 2 2 1 1 2 2

2 2 2 2 2

2 1 '' 1

' ''

' 1

2 2 1 1 2 2 1 '' 1

' ''

' 1 1

var var

var

var σ σ σ σ

σ σ σ

µ σ

= + +

= +

=

= + +

= +

=

∑

(D. 3)

so that the parameters of the resulting Gamma r.v. Y1 ~ Γ

(

α1,β1

)

are:

[ ] ( )

[ ] (

1 1 2 2

)

2 2 2 2 1 1 1

1 1

2 2 2 2 1 1

2 2 2 1 1 1

2 1 1

var var

σ σ

β µ

σ σ

σ µ σ

α

N N NL

N N

Y

N N

N N L Y

Y Y

+

= +

=

+

= +

=

(D. 4)

(8)

Appendix E 207

Appendix E

Ratio of Generic Gamma r.v.s

The distribution 𝑓𝑟(𝑟𝑟) of the ratio between two independent r.v.s r=Y1 Y2 is given by [8]:

2 2 2 2

0 1( 2) ( )

)

(r f ry f y y y

f_r =∫^+∞ _Y _Y ∂ (E. 1)

when the r.v.s Y and ₁ Y follow a Gamma pdf: ₂

( )

∫ ∂

Γ

= Γ

∫ ∂

Γ

= Γ

∫ ∂

=

= Γ

∞ +

− +

−

− +

∞

+ − − − −

∞ +

− −

0 2

2 1

2 1 2 2 1 1 2 2 1 2 2 1 1

1 1

0 2 2

2 2

2 2 2

2 1 1 2

2

1 1 1

1 1 2 2

2 2 2

0 1 2

2 2

2 2 2

2 1 2 2 2

1 1

1 1 1

1 1 1 1 1

) ( ) (

) ( )

( ) ( ) ( )

(

) ( )

(

) ) (

(

y e

r y

y y y e

ry e y

y y f ry f r

f

y e y

f

y e y

f

y r

y ry

Y Y

r

y Y

β β

β β α α α

α α

β α

α β

α α β

α α

β α

α

α α β β

α β α

β α

β α β

(E. 2)

so that, changing variables:

( )

y

(

r

)

^t

r y t y

t r ∂

= +

∂ + ⇒

= + ⇒

=

1 2

2 1 2

1 2

2 1 2

2 1

2

β β

β β β

β β β β

β β

β (E. 3)

we have:

( )

^_^ ^∫ ^∂



 Γ +

= Γ ⁺^∞ ⁺ ⁻ ⁻

− +

0 2 1 1 2 1

1 2

2 1

2 1 2 2 1 1

1 1

) ( ) ) (

( t e t

r r r

f_r ^α ^α ^t

α α α

α α

β β

β β α

α β

β ^{(E. 4)}

Remembering the definition of the Gamma function:

(

+

)

=_∫ ∂

Γα₁ α₂ ₀^+∞t^α¹⁺^α²⁻¹e⁻^t t ^{(E. 5)} replacing it in Eq. (E. 4) and simplifying some terms we have:

( )

2 1

2 1 1 1 2

2 1

) ( ) ) (

( _α _α

α α

β β β

β α α

α α

+

−



 



 +



 



 Γ Γ

+

= Γ

r r r

f_r

(E. 6)

Now, considering that the r.v. rmin =min

(

Y1 Y2,Y2 Y1

)

is equivalent to the following r.v.:







>

≤

= 1 1

1

min r

r r r

r (E. 7)

which is linked to the r.v. r=Y₁ Y₂ throughout the graphic in Fig. E.1.

(9)

208 Appendix E

Fig. E.1 - Mathematical link between r and rmin. From Fig. E.1 results intuitive that:

( ) { } { }

{ } ( ) ( )

( ) [

min

( )

min

] ( )

min 1

( )

min min

min 1 min min

min

min min

min min min min

1

r f r f r r F

r f

r F r F r r

P r r P

r r P r r P r r P r F

r r

r

+

∂ =

= ∂

+

=





 ≤ +

≤

=







 ≥ +

≤

=

≤

=

(E. 8)

where we have indicated with F_x(x)the generic cdf. Finally, since the r.v. 1r=Y₂ Y₁is equal to the r.v.

2

1 Y

Y

r= but with reversed Y and ₁ Y , we have: ₂

( ) ( ) ( )

( )

( ) ( ) ( )

( ) ( )

( )

( ) ( )



















 



 +



 

 +



 



 +



 



 Γ Γ

+

= Γ



 



 +



 



 Γ Γ

+ + Γ



 



 +



 



 Γ Γ

+

= Γ

+

=

+

− +

−

+

− +

−

2 1

1 2 min

2 1 min 1

1 2 2 1

2 1 min

1 1 min 2

2 1

1 2 min

2 1 min 1

1 2

2 1

2 1 2

1

2 1 min

1 1 min 2

2 1

2 1 min min

min 1 min min min

) (

α α α α

β β β

β β

β β β α α

α α

β β β

β α α

α α β

β β β α α

α α

r r r

r

r r r

r r f

r f r f r f

r

r r

r

(E. 9)

(10)

Appendix F 209

Appendix F

Properties of the RoA pdf Varying Window and Edge Orientations

The properties of the RoA pdf varying window and edge orientations are:

Property 1 𝑓𝑟_{𝐴𝑖|𝐴𝑖} = 𝑓𝑟_{𝐵𝑖|𝐵𝑖} ∀𝑖

Property 2 𝑓_𝑟_{𝐴𝑖|𝐴𝑗} = 𝑓_𝑟_{𝐵𝑖|𝐵𝑗} ∀𝑖, 𝑗 with 𝑗 ≠ 𝑖 Property 3 𝑓_𝑟_{𝐴𝑖|𝐵𝑗} = 𝑓_𝑟_{𝐵𝑗|𝐴𝑖} ∀𝑖, 𝑗

Property 4 𝑓𝑟_{𝐴𝑖|𝐵𝑗} = 𝑓𝑟_{𝐴𝑘|𝐵𝑗} ∀𝑖, 𝑗, 𝑘 with 𝑘 ≠ 𝑖

The first property states that when a filtering window is applied with the same orientation of the edge, the r.v. 𝑟𝑟 = min {𝐼̅₁⁄ , 𝐼̅𝐼̅₂ ₂⁄ } has the same pdf independently for the edge orientation. From Fig. F.1 results 𝐼̅₁ clear that 𝑟𝑟 has the same pdf in every case shown in figure since the number of pixels with different scale parameter inside each part of the window is the same (equal to zero).

Fig. F.1 - Filtering window with the same orientation of the edge.

The second property states that the r.v. 𝑟𝑟 = min {𝐼̅₁⁄ , 𝐼̅𝐼̅₂ 2⁄ } has the same pdf if the window is orthogo-𝐼̅₁ nal to the edge. Even in this case (see Fig. F.2), since the number of pixels with different scale parameter inside each part of the window is the same (equal to 4 and 6).

Fig. F.2 - Filtering window orthogonal to the edge.

The third property states that filtering an edge with a window which is neither identical nor orthogonal to the edge orientation may generates the same pdf for some particular cases. For example, it highlights that filtering an edge with orientation 135° with a vertical window gives the same pdf of filtering a vertical edge with a 135° window (see Fig. F.3).

(11)

210 Appendix F

Fig. F.3 - Some examples highlighting the validity of the third property.

The fourth property states that filtering an edge with a window which is neither identical nor orthogonal to the edge orientation may generates the same pdf for some particular cases. For example, it highlights that filtering an edge with orientation 135° with a vertical window gives the same pdf of filtering it with a horizon- tal window, i.e. a window orthogonal to the former one (see Fig. F.4).

Fig. F.4 - Some examples highlighting the validity of the fourth property.

(12)

Appendix G 211

Appendix G

RoA pdf with a Window Overlapped to a Generic Width Border

Given the formulas reported in Eq. (3.52):

𝛼₁=𝐿 �𝑁₁⁽¹⁾𝜎1+ 𝑁₂⁽¹⁾𝜎2�²

𝑁₁⁽¹⁾𝜎₁²+ 𝑁₂⁽¹⁾𝜎₂² 𝛽₁= 𝑁₁⁽¹⁾𝜎₁²+ 𝑁₂⁽¹⁾𝜎₂² 𝑁𝐿 �𝑁₁⁽¹⁾𝜎₁+ 𝑁₂⁽¹⁾𝜎₂�

𝛼₂=𝐿 �𝑁₁⁽²⁾𝜎1+ 𝑁₂⁽²⁾𝜎2�²

𝑁₁⁽²⁾𝜎₁²+ 𝑁₂⁽²⁾𝜎₂² 𝛽₂= 𝑁₁⁽²⁾𝜎₁²+ 𝑁₂⁽²⁾𝜎₂² 𝑁𝐿 �𝑁₁⁽²⁾𝜎₁+ 𝑁₂⁽²⁾𝜎₂�

(G. 1)

Let us consider the configuration in Fig. G.1.

Fig. G.1 - Vertical window with side length D overlapped to a border of width W.

where 𝜎₁ and 𝜎₂ are the RCS of the background and border respectively, we have:

⎩⎪

⎨

⎪⎧𝑁¹⁽¹⁾= 𝑁 𝑁₂⁽¹⁾= 0 𝑁₁⁽²⁾= 𝐷𝑊 𝑁₂⁽²⁾= 𝑁 − 𝐷𝑊

(G. 2)

Therefore, the resultant parameters are:

𝛼₁= 𝐿𝑁 𝛽₁= 𝜎₁

𝑁𝐿 𝛼2=𝐿(𝐷𝑊𝜎₁+ (𝑁 − 𝐷𝑊)𝜎₂)²

𝐷𝑊𝜎₁²+ (𝑁 − 𝐷𝑊)𝜎₂² 𝛽2= 𝐷𝑊𝜎₁²+ (𝑁 − 𝐷𝑊)𝜎₂² 𝑁𝐿(𝐷𝑊𝜎₁+ (𝑁 − 𝐷𝑊)𝜎₂)

(G. 3)

where 𝛼₂ and 𝛽₂ can be rewritten as:

𝛼₂= 𝐿(𝐶1)²

𝐶₂ = 𝐿𝐶_𝛼= 𝐿_𝐸𝑞 𝛽1 = 𝜎₁

𝑁𝐿 𝐶₁

𝐶2 = 𝜎𝐸𝑞

𝑁𝐿𝐸𝑞

(G. 4)

with:

𝑅 = 𝜎₂⁄𝜎₁ 𝐶_𝛼= (𝐶₁)²⁄ ; 𝐶𝐶₂ ₁ = 𝑊𝐷𝑅 + (𝑁 − 𝑊𝐷);

𝐿_𝐸𝑞 = 𝐿𝐶_𝛼; 𝐶_𝛽 = 𝐶₂⁄(𝐶1)³; 𝐶₂= 𝑊𝐷𝑅²+ (𝑁 − 𝑊𝐷); (G. 5) so that, by Eq. (3.48) the final pdf becomes:

(13)

212 Appendix G

𝑓_𝑟(𝑟𝑟) = 1 𝐵�𝑁𝐿_𝐸𝑞, 𝑁𝐿�

⎣⎢

⎢⎢

⎡�𝐶𝛽�^𝑁𝐿^𝐸𝑞𝑟𝑟^𝑁𝐿^𝐸𝑞⁻¹

�𝑟𝑟 + 𝐶_𝛽�^𝑁𝐿^𝐸𝑞^+𝑁𝐿 +�1 𝐶⁄ �𝛽 ^𝑁𝐿^𝐸𝑞𝑟𝑟^𝑁𝐿−1

�𝑟𝑟 + 1𝐶_𝛽�^𝑁𝐿^𝐸𝑞^+𝑁𝐿⎦⎥⎥⎥⎤

(G. 6)

(14)

Appendix H 213

Appendix H

RoA pdf with Negative Exponential Weights

Indicating with I the sample mean of pixels X weighted with the coefficients _i c : _i

=∑

i ciXi

I (H. 1)

Presupposing X as i.i.d. Gamma r.v.s with mean RCS _i σ_iand number of looks L :



 



 L L Γ

X_i σⁱ

,

~ (H. 2)

The r.v.s Y_i =c_iX_i due to the multiplication of a Gamma r.v. X by the positive constant _i c is distributed as: _i



 



 L L c Γ

Y_i ⁱσⁱ ,

~ (H. 3)

Considering the approximation of the sums of generic Gamma r.v.s distributed as a Gamma with mean and variance of the real pdf, we have:

(

α,β

)

1 1

~Γ I

Y X c I

N

i i

N

i∑ i i=∑

=

= (H. 4)

with:

[ ] [ ]

[ ]

=∑

[ ]

=∑

( )



∑

=

∑

∑ =

=

 

∑

=

N

i i i

N

i i

N

i i

N i i i N

i i

N

i i

L c Y

Y I

c Y E Y

E I E

1 2 1

1 2

1 1

1

var var

var σ

αβ

σ αβ

(H. 5)

so that:

[ ] [ ] _{( )}

[ ] [ ]

( )

∑



 

 ∑

=



 

 ∑



 

 ∑

=

N

i i i

N

i i i

N

i i i

N i i i

c L c

I E

I

L c

c I

I E

1 1

2 1

2 2

1 2

var var

σ β σ

σ σ α

(H. 6)

Now, presupposing the window overlapped to two homogeneous areas with RCS σ₁,σ₂, the RoA operator

2 1 I I

r= has the following pdf f_r

( )

r :

( )

( ) ( ) ( )

( ) ( )

^α

α α α

α α

σ α σ

α σ σ β

α β α

β β

β α

β α σ

σ

2 2 1

1 2

1 2 2 1

1 2

1

2 1 2 2

2 2

1 2

2 2

2 1

, ) ,

(

, , ,

,

~

= +

Γ

= Γ









 Γ









 Γ

=

−

∑

r r r B

r r B

f

C C L C L C

I r I

r

(H. 7)

(15)

214 Appendix H

which is the one of the classical RoA where change the shape parameter α. In the classical RoA we have

=NL

α whereas in the weighted RoA α =N_eqL with:

∑



 

 ∑

=

∑

∑ N

i i

N

i i

eq

c c C

N C

1 2

2

1 2

2 (H. 8)

Now, presupposing a DxD filtering window with the smaller sub-window side length equal to M (in Section 3.3.1 we have referred to it with the letter W), the following relations hold:

( )

MD N M D

=

= − 2

1

(H. 9)

At this point, considering negative exponential weights going far from the central pixels but constant along the direction parallel to the orientation we have:

α α α

α

α α α

α

2 1 2

0 1 2

0 2 1

2 2

1 0 1

0 1

1 1 1 1

−

− −

=

− −

=

−

∑ =

−

− −

=

− −

=

−

∑ =

−

= −

= ∑

=∑

−

= −

= ∑

=∑

e D e e

D De

c C

e D e e D De c

C

M M

i M i

i N i

i i

M M

i M i

i N i

i i

(H. 10)

so that the equivalent number of pixels become:

α α α α

2 2

2

2 2

1 1

−

∑

−



 





−

=

e D e

C

N C _M

M

eq

(H. 11)

that is, studying the N_Eqasymptotic limits:

• N_Eq→ for D α→∞;

• N_Eq→ for N α→0.

The behavior of N_Eqvarying D is shown in Fig. H.1 for the exponential coefficientα=0.2.

Fig. H.1 - N_Eqvarying D with the weighted RoA with exponential coefficientα=0.2superimposed to the classic RoA.

(16)

Appendix I 215

Appendix I

Filter Implementation

Several methods exists to implement discrete convolution (i.e. LTI filtering). Given a discrete signals x

[ ]

n and a filterh

[ ]

n , respectively of length X and H, their convolutiony

[ ]

n is:

[ ]

n x h

[ ]

n x

[ ] [

phn p

]

y

p

∑ −

=

∗

= ^∞

−∞

= (I.1)

with y

[ ]

n of length X+ H−1. A direct computation of Eq. (I.1), when H ≤X , would require

(

H+1

)

H+

(

X −H

)

H multiplications and addictions. An efficient method to compute direct convolution is to exploit Fast Fourier Transform properties and the circular convolution theorem.

In fact, considering ^x

[ ]

ⁿ ^and^h

[ ]

ⁿ as periodic signal of equally length period N (i.e. padding with zero the smaller signal), the circular convolution theorem gives:

[ ]

n x h

[ ]

n x

[ ] [

phn p

]

Y

[ ]

k X

[ ] [ ]

k H k

y ^N

p

=



 →



∑ −

=

⊗

= ⁻

=

DFTN 1

0 (I.2)

where DFT indicates the N-points discrete FT (DFT): _N

[ ]

^N

[ ]

^j ^N^kⁿ

n

e n y k

Y ²^π

1 0

−

∑=

= (I.3)

Now, it is also well-known that given the aperiodic N-length version of signalsx

[ ]

n and h

[ ]

n , their linear convolution, which has length 2N-1, can be computed by circular convolution with the previous signals zero- padded to have 2N-1 samples. Hence, exploiting FFT algorithms, linear convolution can be computed by 2N- 1 points FFT of the signals, i.e. X

[ ]

k andH

[ ]

k , successively multiplying the two transforms

[ ]

^k ^X

[ ] [ ]

^k ^H ^k

Y = , and bringing ^Y

[ ]

^k in time with the 2N-1 points inverse FFT (IFFT):

[ ]

^N

[ ]

^j ^N^k ⁿ

n

e k N Y

n

y ² ¹ ² ² ¹

1 0

2

1 ⁻ ⁻ ₋

∑=

= − ^π (I.4)

Usually, the FFT of a signal of size M requires CMlog₂Moperations, with C that depends on the FFT algo- rithm (e.g. the split-radix FFT has C=4). Moreover, when the signal is real, exploiting hermitian symmetry (X

[ ]

−k =X^*

[ ]

k ), C is halved by 2. Hence, in order to implement linear convolution of length 2N-1 by FFT, at least

(

2 1

)

log

(

2 1

)

3C2 N− ₂ N−

operations are required (i.e. two 2N-1 points FFT and one 2N-1 points IFFT). Usually, when both x

[ ]

n and h

[ ]

n have small support, direct computation is faster, whereas the FFT method has less computational burden when signal supports raise.

Anyway, when the filter h

[ ]

n has infinite support (IIR filter), direct computation can only be approximated truncating or multiplying with an appropriate window ^w

[ ]

ⁿ the original filter ^h

[ ]

ⁿ ^.

Nevertheless, a very fast way to implement even this case exist when the Z-transform of ^h

[ ]

ⁿ can be expressed in a rational form. In fact, in this last case a recursive implementation of the convolution

[ ]

n x h

[ ]

n

y = ∗ is given by:

[ ]

∑

[

−

]

∑ − =

=

M

j j

N

i aixn i b yn j

0

0 (I.5)

whose Z-transform can be expressed as:

(17)

216 Appendix I

( ) ( ) ( )

_∑

∑

=

−

=

−

N i

i i M j

j j

z a

z b z

X z z Y H

0

0 (I.6)

If the denominator is not equal to 1 (i.e. a_i≠0for somei>0) the recursive implementation could be applied and it requires only N+Mmultiplications and addictions to obtain the final result.

In the following, a summary of edge detection filter coefficients, both in discrete-time and in Z-domain will be given. Filter functions and their Z-transformed version (when exists) will be summarized for discrete implementation purpose. Moreover, for recursive filtering, the Z-transform 𝐻(𝑍) of the filter ℎ[𝑛] will always be given as:

𝐻(𝑍) = 𝐻₊(𝑍) + 𝐻₋(𝑍) (I.7)

that is the sum of the causal component 𝐻₊(𝑍) and the anticausal component 𝐻−(𝑍).

Canny filter 1-D

Canny filter in discrete-time is:

Time-domain Constants

Filter

[ ]

² ²

2

σ σ n

n e c n h

− −

= = ∑^∞

−∞

=

−

n

n e

c ² ²

2

1 2 ^σ

σ

The Z-transform of this function cannot be given in rational form and, consequently, fast recursive filtering cannot be implemented.

Deriche Filter 1-D

Deriche filter in discrete-time is:

Filter

[ ]

^{[ [}

( )

( ) ( )







<

+

≥

= +









<

+

−

≥ +

−

=

−

=

−

− +

+

−

0 ,

0 2 ,

2

0 2 ,

2

sin

* 2

* 1 1 2

* 1

* 1 1 1

0 0

0

n p p

n je

e c j c

n je

e c j c

n ce

n h

n n n n

n j n

j

n j n

j n

α α

ω

α ω α

ω

α ω α

ω α

;

; 2 ;

0 2

0 1

1

ω α

α

j j

e p

j c

+ +

−

=

−

=

and in Z-domain:

Z-domain Constants

Filter

( )

bz b z

z a z

p z p z p

z z p

H

z b z b

z a z

p z

z p H

2 1

1 1

1

* 1

* 1 1

2 2 1 1

1 1 1

* 1

* 1 1

1 1

1

1 ; 1

1

+ +

= − + −

= −

+

= + + −

= −

−

− + −

α α

( )

;

; cos 2

; sin

2 2

0 1

α α α

ω ω

−

=

−

=

−

=

e b

ce a

To have unitary l1-norm:

[ ] ( ) ( )

[ ( )

0

]

2 0

1 2 sin

cos 2 1

2 1

1 ω

ω

α

α α

−

− + =

∞

−∞

=

+

= −

⇒

=

∑ = ⇒

e

e c e

z H n

h _z

n

(I.8)

(18)

Appendix I 217

Paillou Filter 1-D

Paillou filter in discrete-time is:

Filter

[ ]

^{[ [}

( )

( ) ( )







<

−

≥

= −









<

+

−

≥ +

−

=

−

=

−

− +

+

−

0 ,

0 2 ,

2

0 2 ,

2

sinh

1 2 1 1 1 1 1 2 1

2 1 1 1 2 1 1

0 0

0

n p

p p

p

n p p p

p

n ce

ce

n ce

ce

n ce

n h

n n

n

α α

ω

α ω α

ω

α ω α

ω α

;

; 2;

2 1 0 1

α ω

α

= −

=

−

=

e p

c

and in Z-domain:

Filter

( )

bz b z z z a

H

z b z b

z z a

H

2 1

1

2 2 1 1

1 1

1 1 ;

+ +

= −

+

= +

−

+

( )

α α α

ω ω

2 2

0 1

; cosh 2

; sinh

−

=

−

=

−

=

e b

ce a

[ ] ( ) ( )

[ ( )

0

]

2 0

1 2 sinh

cosh 2

1 2 1

1 ω

ω

α

α α

−

− + =

∞

−∞

=

+

= −

⇒

=

∑ = ⇒

e

e c e

z H n

h _z

n

(I.9)

Shen-Castan Filter 1-D

Shen-Castan filter in discrete-time is:

Filter

[ ]







<

=

>

−

=

−

0 ,

0 , 0

0 ,

n ce

n n ce n

h

n n

α α

-

and in Z-domain:

Filter

( )

bz z z a

H

z b

z z a H

1 1

1 1 ;

+

= −

= +

−

− +

α

− −

=

= e b

cb a

1 1 1 ;

[ ]

₊

( )

₌ ₋⁻_α^α

∞

−∞

=

= −

⇒

=

∑ = ⇒

e c e z

H n

h _z

n 2

1 2 1

1 ₁ (I.10)

Canny Filter 2-D

Canny filter in discrete-time is: