Barnes-Hut Approximation for Point SetGeodesic Shooting

  • 2019-07-10 17:32:07
  • Jiancong Wang, Long Xie, Paul Yushkevich, James Gee
  • 2

Abstract

Geodesic shooting has been successfully applied to diffeo-morphicregistration of point sets. Exact computation of the geodesicshooting betweenpoint sets, however, requiresO(N2) calculations each time step on the number ofpoints in the point set. We proposean approximation approach based on theBarnes-Hut algorithm to speedup point set geodesic shooting. This approximationcan reduce the al-gorithm complexity toO(N b+N logN). The evaluation of theproposedmethod in both simulated images and the medial temporal lobe thick-nessanalysis demonstrates a comparable accuracy to the exact point set geodesicshooting while offering up to 3-fold speed up. This improvementopens up a rangeof clinical research studies and practical problems towhich the method can beeffectively applied.

 

Quick Read (beta)

Table 1: Characteristics of the ADNI dataset. All statistics are in comparison to Aβ- CN. Independent two-sample t-tests (age, education, MMSE) and contingency χ2 test (gender) were used. Standard deviation in parentheses. MMSE = mini-mental state examination. :*p<0.05;**:p<0.01;***:p<0.001.
Aβ- CN Aβ+ CN Aβ+ EMCI Aβ+ LMCI Aβ+ AD
N 190 95 142 110 128
Age (yrs.) 72.3 (6.0) 74.8 (5.9)*** 73.6 (6.9) 72.4 (6.8) 74.3 (8.2)*
Sex (M/F) 100/90 31/64** 81/61 58/52 69/59
Edu (yrs.) 16.9 (2.4) 16.1 (2.7)* 15.6 (2.8)*** 16.6 (2.6) 15.6 (2.7)***
MMSE 29.0 (1.3) 29.0 (1.1) 28.0 (1.7)*** 27.2 (1.9)*** 23.0 (2.1)***
Table 2: Statistical analysis results using thickness measurements extracted by the none-approximation (Non-approx), Barnes-Hut approximation (BH-approx) implementations, adjusted for age, in discriminating patient groups from normal controls in ADNI. Each patient group is compared to Aβ- CN separately. Measurements that survived Bonferroni correction (p<0.05/12) are highlighted in bold.
Aβ- CN Aβ+ CN Aβ+ EMCI Aβ+ LMCI Aβ+ AD
N 190 95 142 110 128
ERC thickness (mm), age as covariate
Median (SD) 2.00 (0.16) 2.00 (0.16) 1.98 (0.17) 1.92 (0.18) 1.78 (0.22)
F stats <2.5 <2.5 15.8 116.1
Non-approx (1275 pts) p value >0.1 >0.1 8.90e-05 3.00e-23
Median (SD) 2.00 (0.15) 2.00 (0.16) 1.98 (0.17) 1.92 (0.18) 1.78 (0.21)
F stats <2.5 <2.5 16.3 116.5
BH-approx (1275 pts) p value >0.1 >0.1 6.90e-05 2.50e-23
Median (SD) 2.01 (0.18) 2.02 (0.16) 1.99 (0.17) 1.93 (0.18) 1.79 (0.22)
F stats <2.5 <2.5 17.9 120.3
BH-approx (2540 pts) p value >0.1 >0.1 3.00e-05 6.30e-24
BA35 thickness (mm), age as covariate
Median (SD) 2.35 (0.16) 2.32 (0.18) 2.30 (0.19) 2.19 (0.23) 2.06 (0.22)
F stats 2.8 8.0 49.2 182.3
Non-approx (1275 pts) p value 0.097 5.10e-03 1.50e-11 4.30e-33
Median (SD) 2.36 (0.16) 2.33 (0.17) 2.31 (0.18) 2.20 (0.22) 2.07 (0.22)
F stats 3.0 7.4 52.1 189.4
BH-approx (1275 pts) p value 0.083 6.60e-03 4.40e-12 4.60e-34
Median (SD) 2.37 (0.16) 2.34 (0.17) 2.31 (0.18) 2.21 (0.22) 2.07 (0.22)
F stats 3.2 10.5 50.8 190.0-
BH-approx (2540 pts) p value 0.075 1.30e-03 7.80e-12 3.80e-34
BA36 thickness (mm), age as covariate
Median (SD) 2.40 (0.23) 2.38 (0.23) 2.38 (0.21) 2.28 (0.22) 2.20 (0.24)
F stats <2.5 <2.5 20.4 56.8
Non-approx (1275 pts) p value >0.1 >0.1 9.00e-06 5.30e-13
Median (SD) 2.42 (0.23) 2.39 (0.23) 2.40 (0.21) 2.29 (0.22) 2.21 (0.23)
F stats <2.5 <2.5 20.9 57.2
huijiale BH-approx (1275 pts) p value >0.1 >0.1 7.00e-06 4.40e-12
Median (SD) 2.42 (0.23) 2.41 (0.23) 2.40 (0.21) 2.30 (0.22) 2.22 (0.23)
F stats <2.5 <2.5 21.3 57.9
BH-approx (2540 pts) p value >0.1 >0.1 6.00e-06 3.20e-13
PHC thickness (mm), age as covariate
Median (SD) 2.14 (0.13) 2.16 (0.16) 2.14 (0.13) 2.09 (0.15) 1.99 (0.15)
F stats <2.5 <2.5 9.9 92.2
Non-approx (1275 pts) p value >0.1 >0.1 1.80e-03 2.60e-19
Median (SD) 2.14 (0.12) 2.16 (0.16) 2.14 (0.13) 2.09 (0.14) 1.99 (0.15)
F stats <2.5 <2.5 10.8 94.9
BH-approx (1275 pts) p value >0.1 >0.1 1.10e-03 8.90e-20
Median (SD) 2.15 (0.13) 2.17 (0.16) 2.15 (0.13) 2.10 (0.14) 2.00 (0.15)
F stats <2.5 <2.5 13.9 97.6
BH-approx (2540 pts) p value >0.1 >0.1 2.20e-04 3.10e-20