-
Notifications
You must be signed in to change notification settings - Fork 1
/
QB.tex
1876 lines (1642 loc) · 98.2 KB
/
QB.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[preprint,authoryear,a4paper,10pt,onecolumn]{elsarticle}
\usepackage[british,english]{babel}
\usepackage{mathpazo}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
%\usepackage[a4paper]{geometry}
%\geometry{verbose,tmargin=0.15\paperwidth,bmargin=0.15\paperwidth,lmargin=0.2\paperwidth,rmargin=0.15\paperwidth}
%\setlength{\parskip}{\bigskipamount}
%\setlength{\parindent}{0pt}
\usepackage{float}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{setspace}
\usepackage{amssymb}
\usepackage{natbib}
\usepackage[title]{appendix}
\usepackage{siunitx}
\makeatletter
\newfloat{algorithm}{tbp}{loa}
\floatname{algorithm}{Algorithm}
\journal{Neuroimage}
\def\argmin{\mathop{\operator@font arg\,min}}
\def\argmax{\mathop{\operator@font arg\,max}}
\makeatother
\begin{document}
\begin{frontmatter}
\title{Effective Real-Time Tractography Clustering with QuickBundles}%\tnoteref{Collab}}
%\tnotetext[Collab]{This work is a collaborative effort.}
\author[UC]{Eleftherios Garyfallidis}
\ead{[email protected]}
\address[UC]{University of Cambridge, UK}
\author[Berkeley]{Matthew Brett}
\ead{[email protected]}
\address[Berkeley]{University of California, Berkeley CA, USA}
\author[CBU]{Marta Correia}
\ead{[email protected]}
\address[CBU]{MRC Cognition and Brain Sciences Unit, 15 Chaucer Road, Cambridge CB2 7EF, UK}
\author[WBIC]{Guy Williams}
\ead{[email protected]}
\address[WBIC]{The Wolfson Brain Imaging Centre, University of Cambridge, UK}
\author[CBU]{Ian Nimmo-Smith\corref{Cor}}
\ead{[email protected]}
\cortext[Cor]{Corresponding author}
\begin{abstract}
Diffusion MR white matter tractography algorithms generate datasets
(tractographies) with a very large number of tracks. Their size makes
it difficult to interpret, visualize and interact with
tractographies. This is even more of an issue when several
tractographies are being considered together. To overcome this
drawback, we present a clustering algorithm, QuickBundles (QB), that
simplifies the complexity of these large datasets and provides
anatomically meaningful clusters in seconds with minimum memory
consumption. Each QB cluster can be represented by a single track,
which collectively can be visualised as a first sketch of the
tractography. Representative tracks from this QB sketch can be
selected and the associated tracks re-clustered in turn via QB. This
allows one to explore the neuroanatomy directly. Alternatively the QB
sketch can be used as a precursor tractography of reduced the
dimensionality for input to other algorithms of higher order
complexity, resulting in their greater efficiency. Beyond these
fundamental uses we show how QB can help identify hidden structures,
find landmarks, create atlases, and compare and register
tractographies.
\end{abstract}
\begin{keyword}
Diffusion MR Tractography;
Diffusion MRI;
White matter tractography;
Fiber clustering;
White matter atlas;
Direct tractography registration;
Clustering algorithms
\end{keyword}
\end{frontmatter}
\section{Introduction}
Diffusion weighted MR (dMR) imaging of white matter accumulates diffusion
weighted images of the whole brain or of a region of interest, with each
image derived for one of a prescribed set of complementary weighting
gradient directions. By comparison with one or more $T_{2}$-weighted
reference images, each dMR image attenuates the $T_{2}$ signal according
to the amount of diffusion along the corresponding gradient directions~\citep{DiffMRIBook}. Collectively the images provide voxel-wise
information about the presence and orientation of directionally
organised tissue.
Following the acquisition of dMR scans, processes of reconstruction and
integration (track propagation) are performed to create a tractography:
a dataset composed of sequences of points in 3-d space. These sequences
are called tracks. Irrespective of the types of reconstruction and
integration a tractography can contain a very large number of tracks (up
to $10^6$) depending principally on the number of seed points used to
generate the tractography but also on how the propagation algorithm
handles voxels with more than one strong diffusion direction.
The size of these tractographies makes them difficult to interpret and
visualize. This is even more the case when we consider combining
tractographies from more than one brain. A clustering of some kind seems
to be a solution to simplify the complexity of these datasets and
provide a useful segmentation; however most of the proposed tractography
clustering algorithms in the literatue are very slow and often need to
calculate a matrix of inter-track distances of size $N\times (N-1)/2$
where $N$ is the number of tracks. This $\mathcal{O}(N^2)$ number of
computations puts a heavy load on clustering algorithms, making them too
inefficient and therefore too impractical for everyday analysis as it is
difficult to compute all these distances or even store them in
memory. This not only adds a further overhead to the use of tractography
for clinical applications but also puts a barrier on understanding and
interpreting the quality of diffusion datasets.
We show in this document that a stable, generally linear time clustering
algorithm exists and that we can generate meaningful clusters of tracks
in seconds with minimum memory consumption. In our approach we do not
need to calculate all pairwise distances unlike most of the other
existing methods. Furthermore we can update our clustering online or in
parallel. We show that we can generate these clusters $~1000$ times
faster than any other available method before even applying possible
further acceleration through parallel processing, and that it can be
used to cluster from a few hundred to many millions of tracks.
Moreover our method is multi-purpose: its results can either stand on
their own to explore the neuroanatomy directly, or the clustering
technique can be used as a precursor tool which reduces the
dimensionality of the data, which can then be used as an input to other
algorithms of higher order complexity, resulting in their greater
efficiency. Beyond the use of this algorithm to simplify tractographies,
we show how it can help identify hidden structures, find landmarks,
create atlases, compare and register tractographies.
\section{Clustering Tractographies}
During the last 10 years there have been numerous efforts by many
researchers to address both unsupervised and supervised learning
problems of brain tractography. As far as we know all these methods
suffer ultimately from low efficiency, though they do provide many
useful ideas which we have recently
reviewed~\citep{Garyfallidis_thesis}. We list the names of these
techniques and the principal papers that apply them to tractography
clustering: \textit{Hierarchical clustering} \citep{Visser2010,
gerig2004analysis, Guevara2010, zhang2005dti, jianu2009exploring};
\textit{$k$-means} \citep{ElKouby2005, Tsai2007}; \textit{Adaptive mean
shift} \citep{zvitia2008adaptive, Zvitia2010}; \textit{Graph theoretic
segmentation} \citep{brun2004clustering}; \textit{$k$-nearest
neighbours} \citep{Ding2003a}; \textit{Generalized Procrustes Analysis
and Principal Components Analysis (PCA)} \citep{Corouge2004,
corouge2004towards, Corouge2006}; \textit{Spectral embedding}
\citep{ODonnell_IEEETMI07}; \textit{EM clustering}
\citep{Maddah_MICCA2005, maddah2006statistical, Maddah_IEEEBI2008,
ziyan2009consistency}; \textit{Spectral clustering}
\citep{jonasson2005fiber}; \textit{Affinity propagation}
\citep{leemans17new, malcolm2009filtered}; \textit{Hierarchical
Dirichlet process mixture model} \citep{wang2010tractography};
\textit{Current models} \citep{Durrleman2009,
durrleman2010registration}.
% \begin{description}
% \item[Hierarchical clustering:] \citep{Visser2010, gerig2004analysis,
% Guevara2010, zhang2005dti, jianu2009exploring}
% \item[$k$-means:] \citep{ElKouby2005, Tsai2007}
% \item[Adaptive mean shift:] \citep{zvitia2008adaptive, Zvitia2010}
% \item[Graph theoretic segmentation:] \citep{brun2004clustering}
% \item[$k$-nearest neighbours:] \citep{Ding2003a}
% \item[Generalized Procrustes Analysis and Principal Components Analysis (PCA):]
% \citep{Corouge2004, corouge2004towards, Corouge2006}
% \item[Spectral embedding:] \citep{ODonnell_IEEETMI07}
% \item[EM clustering:] \citep{Maddah_MICCA2005, maddah2006statistical,
% Maddah_IEEEBI2008, ziyan2009consistency}
% \item[Spectral clustering:] \citep{jonasson2005fiber}
% \item[Affinity propagation:] \citep{leemans17new, malcolm2009filtered}
% \item[Hierarchical Dirichlet process mixture model] \citep{wang2010tractography}
% \item[Current models:] \citep{Durrleman2009, durrleman2010registration}
% \end{description}
Tractography clustering algorithms are rarely compared in the
literature. An exception to this is \citep{moberts2005evaluation} which
evaluated a range of hierarchical clustering methods against a gold
standard segmentation by physicians. The authors concluded that
single-link clustering with mean average distance was the method which
performed best.
From this overview we observe that there are two main trends in the
literature. The first -- which is the most frequent -- uses inter-track
distances and the calculation of the associated distance matrix. In this
case deciphering the inter-track distance matrix with hierarchical
clustering or spectral embedding are two of the most prevailing
approaches. The second, less common, trend is to employ methods which
avoid calculating inter-track distances because it is so memory
intensive. In this case using hierarchical Dirichlet processes,
current modelss, or connectivity-based parcelation seem to be some viable
solutions.
However, if we want to apply clustering in clinical settings or to make
the analyses of clinicians and neuroscientists less time-consuming we need
algorithms that can provide useful clusters and cluster descriptors in
minimum time and with low memory usage. None of the papers mentioned in
this literature review achieve these criteria; indeed most of the
methods would need many hours or even many days to run on a standard
sized data set. The method we propose in this report can provide a
solution to this problem and it is an extended update on our
preliminary work~\citep{EGMB10}.
% One further matter to note is that a number of different approaches have
% been taken to how to code or represent the tracks in a tractography. We
% will look at this in the next section.
In summary, we can see that most authors agree that unsupervised
learning with tractographies is a difficult problem because the data
sets are very large, dense, cluttered with noisy tracks which might have
no anatomic relevance and bundles which are frequently tangled together
in many areas. Furthermore, we can observe that there is a strong
disagreement on the number of clusters (\numrange{10}{60}).
Because of the difficulty of this important problem an international contest was
organized by SchLab in Pittsburgh University in 2009 (PBC Brain
Connectivity Challenge - IEEE ICDM). However, the competition
did not conclude with any directly viable solutions. We think that in
order to find big clusters a lot of anatomical prior knowledge needs to
be introduced in a way that is not yet established. Instead, the
clustering that we propose concentrates on reducing the complexity of
the data rather than finding bundles with anatomical relevance at the
outset. We think that this step is more useful at this stage of
tractography analysis research.
\section{Methods}
% \subsection{\label{sub:track-coding}Track Coding}
% Beyond the simple representation of a track as a sequence of points in
% $\mathbb{R}^3$, a number of alternative codings have been employed.
% \begin{description}
% \item[B-spline representations:] \citep{Maddah_MICCA2005,
% maddah2006statistical, Maddah_IEEEBI2008}
% \item[Track shape parameters:] Using a feature space based on track mean
% and covariance \citep{brun2004clustering}
% \item[Phase space representation:] Tracks modeled as discrete
% distributions over a codebook of quantized orientations and voxel regions \citep{wang2010tractography}
% \end{description}
% \subsection{Alternative tractography similarity metrics}
% Co-occurrence matrix: \citep{jonasson2005fiber}
% ROI-based connectivity matrix: \citep{ElKouby2005}
\subsection{\label{sub:track-distances}Track distances and preprocessing}
Another observation from foregoing literature review is that a wide
range of approaches have been taken to how the raw track data in
tractographies is coded. The approach we have taken with track coding
has gone in parallel with the selection of appropriate metrics for
inter-track distances. Numerous inter-track distance metrics have been
proposed~\citep{Ding2003, MaddahIPMI2007, zhang2005dti}. The most common
is the Hausdorff distance~\citep[and many other
studies]{corouge2004towards}. There are two primary disadvantages of
this metric: (1) it ignores the sequential nature of the tracks and
treats each track simply as a cloud of points, and (2) its computation
requires every point on the first track to be compared with every point
on the second track, and vice versa. For these reasons we have opted to
use a very simple symmetric distance \citep{EGMB10, Visser2010} which we
call Minimum average Direct-Flip (MDF) distance
$d_{\textrm{MDF}}(s,s')$ between track $s$ and track $s'$,
see Eq.~(\ref{eq:direct_flip_distance}). This distance can be applied
only when both tracks have the same number of points. Therefore we
assume that an initial downsampling of tracks has been implemented,
where all segments on a track have approximately the same length, and
all tracks have the same number of segments, $K$ which is much less than
the number of segments in the typical raw track. Under this assumption
MDF is defined as:
\begin{eqnarray}
\textrm{MDF}(s,s') & = & \min(d_{\textrm{direct}}(s,s'),d_{\textrm{flipped}}(s,s')),\,\textrm{where}\nonumber\\
d_{\textrm{direct}}(s,s') & = & \frac{1}{K}\sum_{i=1}^{K}|x_{i}-x_{i}'|,\,\textrm{and}\label{eq:direct_flip_distance} \\
d_{\textrm{flipped}}(s,s') & = & \frac{1}{K}\sum_{i=1}^{K}|x_{i}-x_{K-i}'|,\nonumber
\end{eqnarray}
\noindent
where $K$ is the number of points $x_{i}$ and $x_{i}'$ on the two tracks $s$ and $s'$
and $|x-x'|$ denotes the euclidean distance between two points $x$ and
$x'$.
In some stages in the analysis of tractographies we find a use for metrics from the family of Hausdorff distances
which for simplicity we denote as MAM distances -- short for Minimum,
or Maximum, or Mean, Average Minimum distance (MAM). We mostly use
the Mean version of this family, see Eq.~(\ref{eq:mean_average_distance})
but the others are potentially useful as they can weight different
properties of the tracks. These distances are slower to compute but
they can work with different number of segments on tracks that is
useful for some applications. The equations below show the formulation
of these distances:
\begin{eqnarray}
d_{\textrm{mean}}(s,s') & = & \frac{1}{K_{A}}\sum_{i=1}^{K}d(x_{i},s'),\nonumber \\
d_{\textrm{min}}(s,s') & = & \min_{i=1,...,K}d(x_{i},s'),\,\textrm{and}\label{eq:minimum_distance}\\
d_{\textrm{max}}(s,s') & = & \max_{i=1,...,K }d(x_{i},s'),\,\textrm{where}\label{eq:maximum distance}\\
d(x,s') & = & \min_{j=1,...,K'}|x-x_{j}'|.\nonumber \\
\textrm{MAM}_{\textrm{min}} & = & \min(d_{\textrm{mean}}(s,s'),d_{\textrm{mean}}(s',s))\label{eq:min_average_distance}\\
\textrm{MAM}_{\textrm{max}} & = & \max(d_{\textrm{mean}}(s,s'),d_{\textrm{mean}}(s',s))\nonumber \\
\textrm{MAM}_{\textrm{mean}} & = & (d_{\textrm{mean}}(s,s')+d_{\textrm{mean}}(s',s))/2\label{eq:mean_average_distance}\end{eqnarray}
\noindent
where the number of points $K=\#s$ and $K'=\#s'$ on the two tracks
are not necessarily the same. For the same threshold value $\textrm{MAM}_{\textrm{min}}$,
$\textrm{MAM}_{\textrm{max}}$ and $\textrm{MAM}_{\textrm{mean}}$
will give different results. For example, $\textrm{MAM}_{\textrm{min}}$ will
bring together more short tracks with long tracks than $\textrm{MAM}_{\textrm{max}}$,
and
$\textrm{MAM}_{\textrm{mean}}$
will have an in-between effect. Finally, other distances than the average
minimum based on the minimum see Eq.~(\ref{eq:minimum_distance})
or maximum distance see Eq.~(\ref{eq:maximum distance}) can be used.
However, we have not investigated them in this work in relation to
clustering algorithms.
\begin{figure}
\includegraphics[scale=0.5]{distances2}
\centering{}\caption{The principal distance used in this work is minimum average
direct flip distance $\textrm{MDF}=\min(d_{\textrm{direct}},d_{\textrm{flipped}})$
which is a symmetric distance that can deal with the track bi-directionality
problem; it works on tracks which have the same number of points.
Another distance is the mean average distance which is again symmetric
but does require the tracks to have the same number of points
$\textrm{MAM}_{\textrm{mean}}=(d_{mean}(s,s')+d_{mean}(s',s))/2$.
In this figure the components of both distances are shown; the tracks are drawn with solid
lines, and then with dashed lines we connect the
pairs of points of the two tracks whose distances contribute to the
overall metric.\label{Flo:Distances_used}}
\end{figure}
Coming back to the MDF distance (see Eq.~(\ref{eq:direct_flip_distance})),
its main advantages are that it is fast to compute, it takes account of
track direction issues through consideration of both direct and flipped
tracks, and that it is easy to understand how it will behave, from the
simplest case of parallel equi-length tracks to the most complicated
with very divergent tracks. Another advantage is that it will separate
short tracks from long tracks and as we will see this will be a good way
to find broken or erroneous tracks. An advantage of having tracks with
the same number of points is that we can easily do pairwise calculations
on them; for example add two or more tracks together to create a new
average track. We will see in the next section that track addition is a
key property that we explout in of the QB clustering algorithm. Some
thought needs to be given to chosing the number of points
required in a track (track downsampling). We always keep the endpoints
intact and then downsample in equidistant segments. One consequence of short
tracks having the same number of points as long tracks is that more
of the curvature information from the long tracks is lost relative to the short
tracks i.e. the short tracks will have higher resolution. We found
empirically that this is not an important issue and that for clustering
purposes even downsampling to only $K=3$ points in total can be useful
\citep{EGMB10}. Depending on the application, more or fewer points can be
used. In the present demonstrations we use $K=12$.
\subsection{\label{sub:QB-Data-sets}Data sets}
We applied QuickBundles to a variety of data sets: simulations, $10$ human
tractographies collected and processed by ourselves, and one tractography
with segmented bundles which was available online.
\textbf{Simulated trajectories.} We generated $3$ different bundles of
parametric paths samples at $200$ points. The tracks were made from
different combinations of sinusoidal and helicoidal functions. In total
this data set contained $450$ tracks see Fig.~\ref{Flo:simulated_orbits}.
\textbf{Human subjects.} We collected data from $10$ healthy subjects at
the MRC-CBU 3T scanner (TIM Trio, Siemens), using Siemens advanced
diffusion work-in-progress sequence, and STEAM
\citep{merboldt1992diffusion,MAB04} as the diffusion preparation
method. The field of view was $240\times240\,\textrm{mm}^{2}$, matrix size
$96\times96$, and slice thickness $2.5\,\textrm{mm}$ (no gap). $55$ slices were
acquired to achieve full brain coverage, and the voxel resolution was
$2.5\times2.5\times2.5\,\textrm{mm}^{3}$. A $102$-point half grid
acquisition \citep{Yeh2010} with a maximum $b$-value of $4000\, \textrm{s/mm}^{2}$
was used. The total acquisition time was $14'\,21''$ with
TR=$8200\,\textrm{ms}$ and TE=$69\,\textrm{ms}$. The experiment was approved
by the local ethical committee CPREC.
For the reconstruction of the 10 human data sets we used Generalized
Q-samping \citep{Garyfallidis_thesis} with diffusion sampling length
$1.2$ and for the tractography propagation we used EuDX (Euler
integration with trilinear interpolation, \citet{Garyfallidis_thesis})
with $1$ million random seeds, angular threshold $60^{\circ}$, total
ef weighting $0.5$, propagation step size $0.5$ and anisotropy stopping
threshold $0.0239$ (see Fig.~\ref{Flo:CloseToSelected}
and Fig.~\ref{Flo:arcuate_close}).
\textbf{PBC human subjects}. We also used a few labeled data sets (see
Figs.~\ref{Flo:cst_pbc} and \ref{Flo:QB_fornix}), from the freely available
tractography database used in the Pittsburgh Brain Competition Fall
$2009$, ICDM pbc.lrdc.pitt.edu.
\section{QuickBundles (QB) Clustering}
\subsection{The QB Algorithm}
QuickBundles (QB) is a notably fast algorithm which can simplify
tractography representation in an accessible structure in a time that is
linear in the number of tracks $N$. QB is a linear time $O(N)$ (see
section~\ref{sub:Complexity}) distance based clustering algorithm that
we created in order to clarify huge trajectory data sets such as those
produced by current state-of-the-art tractography generation algorithms~\citep{Parker2003,WWS+08}.
In QB each item (track) is a fixed-length ordered sequence of points in
$\mathbb{R}^{3}$, and uses metrics and amalgamations which take account
of and preserve this structure. Moreover each item is either added to
an existing cluster on the basis of a distance between the cluster
descriptor of the item and the descriptors of the current set of
clusters. Clusters are held in a list which is extended according to
need.
QB creates an online list of cluster nodes. The cluster node is defined
as $c=\{I,\mathbf{h},n\}$ where $I$ is the list of the integer indices
of the tracks in that cluster, $\mathbf{h}$ is a $p\times3$ matrix,
which the most important descriptor of the cluster, and $n$ is the
number of tracks in the cluster. $\mathbf{h}$ is a matrix which can be
updated online when a track is added to a cluster and is equal to
\begin{equation}
\mathbf{h}=\sum_{i=1}^{n}\mathbf{s}_{i}
\end{equation}
where $\mathbf{s}_{i}$ is the $p\times3$ matrix representing track $i$,
$\Sigma$ here represents matrix addition, and $n$ is the number of
tracks in the cluster. QB assumes that all tracks have the same number
of points $p$, therefore a downsampling of tracks, typically
equidistant, is necessary before QB starts. A short summary of the
algorithm goes as follows.
Select the first track $s_{0}$ and place it in the first cluster
$c_{0}\leftarrow\{0,s_{0},1\}$. Then for all remaining tracks (i) goto
next track $s_{i}$; (ii) calculate MDF distance between this track and
virtual tracks of all existing clusters $c_{k}$, where a virtual track
is defined on the fly as $\mathbf{v}=\mathbf{h}/n$; (iii) if the minimum
MDF distance is smaller than a distance threshold
$\theta$ add the track to the cluster
$c_{j}=\{I,\mathbf{h},n\}$ with the minimum distance and update
$c_{j}\leftarrow\{I\cup\{i\},\mathbf{h}+s,n+1\}$; otherwise create a new
cluster $c_{|C|+1}\leftarrow\{\{i\},s_{i},1\}$, $|C|\leftarrow|C|+1$ where
$|C|$ denotes the current total number of clusters.
\begin{algorithm}
\textbf{Input} tracks $T=\{s_{0},...,s_{i},...,s_{|T|-1}\}$, threshold $\theta $\\
\textbf{Output} clustering $C=\{c_{0},...,c_{k},...,c_{|C|-1}\}$ where cluster $c=\{I,\mathbf{h},N\}$\\
\\
$c_{0}=\left\{0,s_{0},1\right\}$\\
$C=\left\{c_{0}\right\}$ \# the first track becomes the first cluster\\
$|C|=1$ \# the total number of clusters is 1 \\
$\textbf{For}$ $i$ $\textbf{From}$ $1$ $\textbf{To}$ $|T|-1$ $\textbf{Do}$ \# all tracks\\
\hspace*{2em} $\textbf{t}=T_{i}$\\
\hspace*{2em} $\texttt{alld}=\textbf{0}$ \# distance buffer\\
\hspace*{2em} $\texttt{flip}=\textbf{0}$ \# flipping check buffer\\
\hspace*{2em} $\textbf{For}$ $k$ $\textbf{From}$ $0$ $\textbf{To}$ $|C|-1$ \# all clusters\\
\hspace*{4em} $\mathbf{v}=C_{k}.\mathbf{h}/C_{k}.N$\\
\hspace*{4em} $d$=$d_{d}(\mathbf{t},\mathbf{v})$\\
\hspace*{4em} $f$=$d_{f}(\mathbf{t},\mathbf{v})$\\
\hspace*{4em} $\textbf{If}$ $f < d$ $\textbf{Then}$\\
\hspace*{6em} $d = f$\\
\hspace*{6em} $\texttt{flip}_{k} = 1$\\
\hspace*{4em} $\texttt{alld}_{k} = d$\\
$m=\min(\texttt{alld})$\\
$l=\mathrm{arg min}(\texttt{alld})$\\
$\textbf{If}$ $m < \theta$ \# append in current cluster \\
\hspace*{2em} $\textbf{If}$ $\texttt{flip}_{l}=1$ $\textbf{Then}$\\
\hspace*{4em} $C_{l}.\mathbf{h}+=t'$\\
\hspace*{2em} $\textbf{Else}$ \\
\hspace*{4em} $C_{l}.\mathbf{h}+=t$\\
\hspace*{2em} $C_{l}.N+=1$\\
\hspace*{2em} $C_{l}.I$.append($i$)\\
$\textbf{Else}$ \# create new cluster\\
\hspace*{2em} $|C|+=1$ \# total number of clusters increases\\
\hspace*{2em} $C_{|C|-1}.I_{0}=l$\\
\hspace*{2em} $C_{|C|-1}.\mathbf{h}=\mathbf{t}$\\
\hspace*{2em} $C_{|C|-1}.N=1$\\
\caption{QuickBundles\label{Alg:QuickBundles}}
\end{algorithm}
Flipping can become an issue when using the MDF distance and adding
tracks together, because tracks do not have a preferred direction. A
step in QB takes account of the possibility of needing to perform a flip
of a track before adding it to a representative track. The complete QB
algorithm is described in detail in Alg.\ref{Alg:QuickBundles} and a
simple step by step visual example is given in Fig. \ref{Fig:LSC_simple}.
One of the reasons why QB has on average linear time complexity derives
from the structure of the cluster node: we only save the sum of current
tracks in the cluster and this is achieved cumulatively. By contrast if
we were using k-means at every iteration we would have to re-assign
tracks to clusters and recalculate averages which is computationally
much more intensive. Other reasons are that QB passes through the tracks
only once and that a track is assigned to one cluster only.
QB is can be extended for specific applications to contain more information
about the clusters. For example we could redefine $c=\{I,\mathbf{h},n,\mathbf{h}^{(2)}\}$
where
$$\mathbf{h}^{(2)}\leftarrow\{\sum_{i,j}x_{ij}^{2},\sum_{i,j}y_{ij}^{2},\sum_{i,j}z_{ij}^{2},\sum_{i,j}x_{ij}y_{ij},\sum_{i,j}y_{ij}z_{ij},\sum_{i,j}x_{ij}z_{ij}\}.$$
Here $x_{ij},y_{ij},z_{ij}$ are the coordinates of the $j$th point of
the $i$th track in the cluster. In this way second order information can
be obtained offering a potentially more refined cluster distances which
take into account the additional information. However we leave this for
investigation at a later stage.
\begin{figure}
\includegraphics[scale=0.25]{last_figures/LSC_algorithm}
\caption{QB step-by-step: Initially in panel (i) 6
unclustered tracks (A-F) are presented; imagine that the distance
threshold used is the MDF distance (Eq. [reference needed]) between B
and E. The algorithm starts and in (ii) we see that track A was
selected, so no other clusters exist therefore track A becomes the
first cluster (labeled with purple color) and the virtual track of
that cluster is identical with A as seen in (iii), next in (iv) track
B is selected and we calculate the MDF distance between B and the
virtual track of the other clusters. For the moment there is only one
cluster to compare so QB calculates MDF (B,virtual-purple) and this is
obviously bigger than threshold (that being MDF(B,E)) therefore a new
cluster is assigned for B and B becomes the virtual track of that
cluster as shown in (v). In (vi) the next track is selected and this
is again far away from both purple and blue virtuals therefore another
cluster is created and B is the virtual of the blue cluster as shown
in (vii). In (viii) track D is current and after we have calculated
MDF(D,purple), MDF(D,Blue) and MDF(D,green) it is obvious that D
belongs to the purple cluster as MDF(D,purple) is smaller and lower
than threshold as shown in (ix). However we can now see in (x) that
things change for the purple cluster because the virtual track is not
anymore made by only one track but it is the average of D and A shown
with dashline. In (xi) E is the current track and will be assigned at
the green cluster as shown in (xii) because MDF(E,virtual green) =
MDF(E,B) = threshold, and in (xiii) we see the updated virtual track
for the green cluster which is equal to (B+E)/2 where + means track
addition. In (xiv) the last track is picked and compared with the
virtual tracks of the other 3 clusters; obviously MDF(F,purple) is the
only with smaller threshold, and so F is assigned to the purple
cluster in (xv). Finally, in (xvi) the virtual purple track is updated
as (D+A+F)/3. As there are no more tracks to select, the algorithm
stops. We can see all three clusters have been found and all tracks
have been assigned successfully.\label{Fig:LSC_simple}}
\end{figure}
One of the disadvantages of most clustering algorithms is that they give
different results with different initial conditions; for example this is
recognised with k-means, expectation-maximization
\citep{dempster1977maximum} and k-centers \citep{gonzalez1985clustering}
where it is common practice to try a number of different random initial
configurations. The same holds for QB so if there are not distinct
clusters such that the distance between any pair of clusters is
supra-threshold, then with different permutations of the same
tractography we will typically see similar number of clusters but
different underlying clusters. We will exaqmine the robustness of QB in
this respect in section \ref{sub:Comparisons}.
\subsection{Comparison of QB with BIRCH}
QuickBundles (QB) is a notably fast algorithm which can simplify
tractography representation in an accessible structure in a time that is
linear in the number of tracks $N$. QB is a linear time $O(N)$ (see
section \ref{sub:Complexity}) distance based clustering algorithm that
we created in order to clarify huge trajectory data sets such as those
produced by current state-of-the-art tractography generation algorithms
\citep{Parker2003,WWS+08}. In general, there are very few linear time
clustering algorithms. Just two are well known: CLARANS
\citep{ng2002clarans} and BIRCH \citep{zhang1997birch}. QB is different
from both of these methods; we will describing some
aspects of BIRCH to shed further light in the conceptual basis of QB.
BIRCH has two key components: the first is relatively simple and involves
the use and updating of clusters' descriptors; the second is the
construction of a tree structure in which the accumulated clusters are
held. This second component is aimed at maintaining efficient
searchability of the database while balancing what is kept in memory and
what is on disc for very large databases. BIRCH uses clustering
descriptors which are available for each item in the dataset; these are
specific vectors of a fixed dimension of numerical values. Each cluster
in turn has a descriptor which is an aggregate of the properties of the
items that belong to it (e.g. the sum or mean of the individual
clustering feature vectors). Proceeding by a single sweep through the
dataset, items are adjoined to clusters on the basis of their proximity
to the clusters, subject to a maximum cluster size, or they are added as
new leaves into the hierarchical tree structure in which the evolving
clusters are held. There then follow updating steps which can involve
the merging off previously created clusters in a k-means
fashion \citep{steinhaus1956division,macqueen1967some}.
It is the linear nature of BIRCH combined with the fixed dimensionality
of its cluster descriptors that makes it quite fast. However the further
steps involving reorganisation of the accumulated tree do add some major
overheads to BIRCH's performance. QB capitalises on these positive
features but does not try to create any kind of hierarchical structure
for the clusters. While items in BIRCH are fixed dimension vectors with
no additional structure, in QB each item (track) is a fixed-length
ordered sequence of points in $\mathbb{R}^{3}$, and uses metrics and
amalgamations which take account of and preserve this structure.
Moreover each item is either added to an existing cluster on the basis
of a distance between the cluster descriptor of the item and the
descriptors of the current set of clusters. Clusters are held in a list
which is extended according to need.
\subsection{Complexity and timings\label{sub:Complexity}}
To apply QB to a data set we need to specify three key parameters:
$p$, the fixed number of downsampled points per track; $\theta$
the distance threshold, which controls the heterogeneity of clusters;
and $N$ the size of the subset of the tractography on which the clustering
will be performed. When $\theta$ is higher, fewer more heterogeneous
clusters are assembled, and conversely when $\theta$ is low, more
clusters of greater homogeneity are created.
The complexity of QB is in the best case linear time $O(N)$ with
the number of tracks $N$ and worst case $O(N^{2})$ when every cluster
contains only one track. The average case is $O(MN)$ where $M$ is
the number of clusters however because $M$ is usually much smaller
than $N$ ($M\ll N$) we can neglect $M$ and denote it only as $O(N)$
as it is common in complexity theory. We created the following experiment
to investigate this claim and we found empirically that the average
case is actually $O(N)$ for tractographies (see Fig.\ref{Flo:Speed1}).
In this experiment we timed the duration of QB clustering of tractographies
containing from $100$ thousand to $1$ million tracks, with different
initial number of points per track ($3,6,12$ and $18$) and different
QB thresholds ($10.0,15.0,20.0,25.00$ mm). The results can be seen
in Fig.\ref{Flo:Speed1}. Even when the the threshold value becomes impressively
low ($10.0$ mm) the linearity is only slightly disturbed.
% \begin{figure}
% \begin{centering}
% \label{Flo:Speed1}\includegraphics[scale=0.8]{last_figures/speed_3_6}
% \par\end{centering}
% \caption{QB is a very efficient algorithm whose performance is controlled by
% just three parameters. The first is the number of tracks, a second
% is the distance threshold in millimeters - shown with different colours
% and another is the amount of initial downsampling of the initial trajectories.
% A last parameter not shown in these diagrams is the underlying structure
% of the data which is expressed by the number of final clusters. We
% used a full tractography to generate these figures without removing
% or preselecting any parts. This results run of a single thread Intel(R)
% Xeon(R) CPU E5420 at 2.50GHz on a standard PC. (NB This and the following
% figure use the same vertical scale to assist direct comparison.)}
% \end{figure}
% Furthermore, the memory usage of QB is $O(M)$ where $M$ is the number
% of clusters and because this is usually much smaller than $N$ we
% consider memory consumption to be negligible. Because in QB we store
% only the indices of the tracks even for very large tractographies
% $20$ or more clusterings can be stored simultaneously in the RAM
% of a simple notebook without any problems. Therefore, another feature
% of QB is memory efficiency.
\begin{figure}
\noindent \begin{centering}
%\label{Flo:Speed2}\includegraphics[scale=0.8]{last_figures/speed_12_18}
\includegraphics[scale=0.33]{2x2+leg-box}
\par\end{centering}
\caption{Time comparisons of QB using different number of points per
track, different distance thresholds and different number of
tracks. QB is a very efficient algorithm whose performance is
controlled by just three parameters. (1) the initial downsampling $K$
of the tracks exemplified in four subdiagrams: 3 points (A), 6 points
(B) 12 points (C), 18 points (D). (2) the distance threshold $\theta$
in millimeters shown in 4 colours: 10 mm (blue), 15 mm (green), 20 mm
(red), 25 mm (cyan). The final parameter, not shown explicitly in
these diagrams, is the underlying structure of the data which is
expressed by the resulting number of clusters. We used a full
tractography to generate these figures without removing or
preselecting any parts. This results run of a single thread Intel(R)
Xeon(R) CPU E5420 at 2.50GHz on a standard PC. (NB The subdiagrams use
different vertical scales.) Random subsets of the tractography were
chosen with size $N$ from \numrange{e5}{e6} (x-axis).We see how the
linearity of the QB algorithm with respect to $N$ only reduces
slightly even when we use a very low threshold such as $10$ mm which
can generate many thousand of clusters. This experiment concludes that
QB is suitable for fast clustering.\label{Flo:Speed1}}
\end{figure}
We compared QB with $12$ point tracks and distance threshold at
$\theta=10$ mm versus some timings reported from other state of the art
methods found in the literature (Table \ref{Flo:timings}). Unfortunately
timings were very rarely reported up till now as most algorithms were
very slow on full data sets. Nonetheless the speedup that QB offers is
obviously of great importance and holds out the prospect of real-time
clustering on data sets of fewer than $20,000$ tracks (see
Table \ref{Flo:timings}).
%
\begin{table}
\small\addtolength{\tabcolsep}{-5pt}
\begin{centering}
\begin{tabular}{|c|c|c|c|c|}
\hline
Number of tracks ($N$) & Algorithms & Timings (secs) & QB (secs) & Speedup\tabularnewline
\hline
\hline
$1000$ & Wang et al. \cite{wang2010tractography} & $30$ & $0.07$ & $429$\tabularnewline
\hline
$60,000$ & Wang et al. \cite{wang2010tractography} & $14400$ & $14.7$ & $980$\tabularnewline
\hline
$400,000$ & Visser et al. \cite{Visser2010} & $75000$ & $160.1$ & $468$\tabularnewline
\hline
\end{tabular}
\par\end{centering}
\caption{QB run on $p=12$ point tracks and distance threshold at $\theta=10$ mm
compared with some timings reported from other state of the art methods
found in the literature. Unfortunately timings were very rarely reported
until today as most algorithms were very slow on full data sets. Nonetheless,
we can observe in this table that the speedup that QB offers is substantial,
holding out the prospect of real-time clustering on data sets containing
fewer than $\sim 20,000$ tracks. This experiment was executed on a
standard PC using only a single CPU core.\label{Flo:timings}}
\end{table}
\section{The QB Sketch}
One of the major benefits of applying QB to tractographies is that it
can provide meaningful simplifications and find structures that were
previously invisible or difficult to locate because of the high density
of the tractography. For example we used QB to cluster the corticospinal
tract (CST). This bundle was part of the datasets provided by the
Pittsburgh Brain Competition (PBC2009-ICDM) and it was selected by an
expert. The QB Sketch is clearly shown in Fig.\ref{Flo:cst_pbc} where
every cluster is represented by a single virtual track. To generate this
clustering we used a tight threshold of $10$mm. We observe that only a
few virtual tracks travel the full distance from bottom to top and that
they are many tracks that are broken (i.e. shorter than what was
initially expected) or highly divergent.
%
\begin{figure}
\begin{centering}
\includegraphics[scale=0.3]{last_figures/cst_simplification}
\par\end{centering}
\caption{On the left the CST bundle is shown (red) consisting of $11041$ tracks
which were merged by an expert (PBC2009 data). At first glance it
looks as though all tracks have a similar shape, and possibly converge
towards the bottom, and fan oiut towards the top. However, this is a
misreading caused by the opaque density when all the tracks are
visualised. QB can help us see the fuller structure of the bundle and
identify its elements. On the right hand side we see the
14 QB virtual tracks of the CST generated by running QB
with distance threshold of $10$ mm after downsampling to $12$ points. We
can now clearly see that lots of parts which looked homogeneous are
actually broken bundles e.g. dark green (A), light blue (C) or bundles
with very different shape e.g. light green virtual track (B). To
cluster this bundle took $135$ ms $\simeq$$0.14$ seconds.\label{Flo:cst_pbc}}
\end{figure}
Another interesting feature of QB is that it can be used to merge
or split different structures by changing the distance threshold.
This is shown in Fig. \ref{Flo:simulated_orbits}; on the left we
see simulated paths made from simple sinusoidal and helicoidal functions
packed together. The colour coding is used to distinguish the three
different structures. With a lower threshold the three different structures
keep remain separated but when we use a higher threshold the red and
blue bundles are represented by only one cluster; represented by a
purple virtual track.
%
\begin{figure}
\begin{centering}
\includegraphics[scale=0.7]{last_figures/helix_phantom}
\par\end{centering}
\caption{On the left we see $3$ bundles of simulated trajectories; red,
blue and green consisting of $150$ tracks each. All $450$ tracks are
clustered together using QB and the virtual tracks are shown when
threshold $1$ was used shown in the middle and $8$ on the right. We
can see that when the threshold is low enough the underlying structure
is a more detailed representation of the underlying geometry. However
when the distance threshold is higher closer bundles could merge
together as seen in the result on the right panel where the red and
blue bundle have merged together in one cluster represented by the
purple virtual track.\label{Flo:simulated_orbits}}
\end{figure}
Similarly, with the simulations shown in Fig.\ref{Flo:simulated_orbits}
we can see the same effect on real tracks, e.g. those of the fornix
shown at the left panel of Fig. \ref{Flo:QB_fornix} where we can obtain
different number of clusters at different thresholds. In that way we can
stress thinner or larger sub-bundles inside other bigger bundles.
%
\begin{figure}
\begin{centering}
\includegraphics[scale=0.6]{last_figures/LSC_simple}
\par\end{centering}
\caption{Left - Here we see how QB clustered the fornix bundle with the
dataset from the PBC2009 competition. The original fornix is shown in
black consists of $1076$ tracks. All tracks were equidistantly
downsampled at $3$ points in this example. With a $5$mm threshold our
method generates $22$ clusters (top right). With $10$mm generates $7$
(bottom left) and with $20$mm the whole fornix is determined by one
cluster only (bottom right). Right - an example of a full tractography
($250,000$ tracks) being clustered using QB with a distance threshold
of $10$mm. Here we see just $763$ virtual tracks depicted which
produce a useful simplification of the initial tractography. Every
track shown here represents an entire cluster from $10$ to $5000$
tracks each. These can be thought as fast access points to explore the
entire data set. The colour here just encodes track orientation. With
an appropriate visualization tool you could click on a track and
obtain the entire cluster/bundle that it represents. Visualizing an
entire data set of that size is impossible on standard graphic cards
and most visualization tools e.g. Trackvis or DSI Studio can only show
a small random sample of the full tractography at real time.\label{Flo:QB_fornix}}
\centering{}
\end{figure}
A full tractography containing $250,000$ tracks was clustered using QB
with a distance threshold of $10$mm (Fig. \ref{Flo:QB_fornix}). We
produced a useful reduction of the initial tractography leaving only
$763$ virtual tracks. Bundles smaller than $10$ tracks were
removed. Every track shown here represents an entire cluster containing
from $10$ to $5000$ tracks each.
The virtual tracks can be thought as fast access points to explore the
entire data set (see Fig. \ref{Flo:QB_fornix}).
\subsection{Virtual tracks, exemplar tracks and other descriptors.}
The virtual tracks created by QB have very nice properties as they
represent an average track which can stand as the most important feature
of the cluster that they belong to. However, now that we have segmented
our tractography into small bundles we can calculate many more
potentially important descriptors for the cluster. For instance the
Cluster Spread (CS) can be computed for any cluster $c$ as a vector of
length $p$ whose $j$th component is $\sum_{x\in c}|x_{j}-v_{j}|^{2}/n.$
Here $x_{j}$ is the $j$-th point in the track $x$ in cluster $c$,
$v_{j}$ is the corresponding point of the virtual track, and $n$ is the
size of the cluster. CS provides a profile of the tightness or looseness
of the cluster along the length of the virtual track. Many other similar
or higher order statistics can be readily computed in an analogous
fashion. One of the most useful features is the calculation of
exemplars.
\textbf{Exemplars}. Another fruitful idea relating to the virtual track
is to try to identify a corresponding feature for the bundle which
actually belongs to the tractography. In other words to find an exemplar
or centroid track. Remember that the virtual tracks do not necessarily
coincide with real tracks as they are just the outcome of large
amalgamations. There are many strategies for how to select good
exemplars for the bundles. A very fast procedure that we use in this
work is to find which real track from the cluster is closest (by MDF
distance) to the virtual track. Let's call this exemplar track $e_{1}$
such that $e_{1}={\displaystyle \argmin_{x\in C}}\textrm{\,\ MDF}(v,x)$.
The computational complexity of finding $e_{1}$ is still linear in
cluster size, and that will be very useful if we have created
clusterings with clusters containing more than $\sim5000$ tracks
(depending on system memory).
A different exemplar can be defined as the most similar track among all
tracks in the bundle, which we denote by $e_{2}={\displaystyle
\argmin_{x\in C}}\,{\displaystyle \sum_{y\in C}}\mathrm{MDM(}y,x)$, or
if we want to work with tracks with possibly different numbers of points
we could instead use $e_{3}={\displaystyle \argmin_{x\in
C}}\,{\displaystyle \sum_{y\in C}}\mathrm{MAM(}y,x)$.
Identification of exemplar tracks of type $e_{2}$ and $e_{3}$ will be
efficient only for small bundles of less than $5000$ tracks because we
need to calculate all pairwise distances in the bundle. We will see next
many applications of the exemplars. For example in the section
\ref{sub:The-bi-directionality-problem} we will use them to simplify the
bi-directionality problem when merging clusters.
In summary, a virtual (centroid) track is the average of all tracks in
the cluster. We call it virtual because it doesn't really exist in the
real data set and to distinguish it from exemplar (medoid) tracks which
are again descriptors of the cluster but are represented by real tracks.
\subsection{The bi-directionality problem\label{sub:The-bi-directionality-problem}}
Because a track is a sequence of points without a preferred direction,
it has two possible orientations when comparing it with another track.
Most tractography methods will create tracks with arbitrary directions;
meaning that close and similar tracks can have opposite directions. Of
course the tracks do not really carry directional information. By
direction we mean the encoding of the sequence of points which define
the track. Thus a track may be ordered $p_{1},p_{2}\ldots
p_{N-1},p_{N}$, or $p_{N},p_{N-1}\ldots p_{2},p_{1}$. We call this the
bi-directionality problem. Using the MDF distance we found a way with QB
to eliminate this problem. However, if we want to merge clusters
together we need to have a way to minimize this problem.
For this purpose we devised the following technique. Choose a fixed
point or pole $P$ in the 3D space of the tractography, possibly away
from the mid-sagittal plane. Then re-direct all tracks so that the first
point of every track is the end closer to $P$. If the tractography is in
native space it suffices to have the origin $(0,0,0)$ as the pole point;
in MNI space we can use the point $(100,100,100)$. It is our empirical
experience that this method will redirect correctly most tracks in the
sense that similar tracks will have the same direction. However there
will still be a small percentage for which the bi-directionality problem
persists. We can correct for these by using exemplars rather than
virtual tracks as virtual tracks can misrepresent a bundle if the bundle
consists of tracks with ambiguous directionality. The exemplars are
preferable to the virtual tracks because of the way the latter can be
influenced more by outliers and thus can be less representative in terms
of the shape of real tracks in a bundle. The exemplars are similar to
the concept of the median and the virtuals more similar to the concept
of the mean. It is well known that the mean is usually influenced more
by outliers than the median.
\section{Comparisons within- and between-subjects\label{sub:Comparisons}}
\subsection{Robustness under reordering}
As mentioned above, QB shares the behaviour of most clustering
algorithms in that different orderings of the tracks give rise to
different clusterings. As a first step towards examining the robustness
of QB in this respect we recorded the numbers of QB clusters in $20$
different random orderings of the tractographies of $10$ human subjects
acquired as described in section \ref{sub:QB-Data-sets}. We removed
short tracks shorter than $40$mm and downsampled the tracks at $12$
points. Then we applied QB with threshold at $10$mm. The mean number of
clusters was $2645.9$ (min $1937.6$; max $3857.8$; s.d. $653.8$). There
is therefore a considerable between-subject variation in this metric. By
contrast the within-subject variability of the number of clusters across
random orderings is rather small, with mean standard deviation $12.7$
(min $7.3$; max $17.4$). This suggests an encouraging level of
robustness in terms of the numbers of clusters that QB creates. We now
consider ways of measuring and comparing the contents of the clusters in
a clustering.
\subsection{Tightness comparisons\label{sub:Tightness-comparisons-1}}
We have found rather few systematic ways to compare different clustering
results for tractographies in the literature
\citep{moberts2005evaluation}. Being able to compare results of
clusterings is crucial for creating stable brain imaging procedures, and
therefore it is necessary to develop a way to compare different
clusterings of the same subject or different subjects. Although we
recognise that this is a difficult problem, we propose the following
approach with a metric which we call tight comparison (TC). Tight
comparison works as follows. Let us assume that we have gathered the
exemplar tracks from clustering A in $E_{A}=\{e_{1},...,e_{|E_{A}|}\}$
and from clustering B in $E_{B}=\{e_{1}^{'},...,e_{|E_{B}|}^{'}\}$
where $|E|$ denotes the number of exemplar tracks of each clustering
$E$. The size of set $E_{A}$ does not need to be the same as that of
$E_{B}$. Next, we calculate all pairwise MDF distances
between the two sets and store them in rectangular matrix $D_{AB}$. The
mimima of the rows of $D_{AB}$ provide the distance to the nearest track
in B of each track in A ($E_{A\rightarrow B}$) and similarly
the minima of the columns of $D_{AB}$ the distance to the nearest track
in $A$ of each track in B ($E_{B\rightarrow A}$). From these
correspondences we only keep those distances that are smaller than a
tight (small) threshold $\theta$. Then we define TC (Tightness
Comparison) to be
\begin{equation}
TC=\frac{1}{2}\left(\frac{|E_{A\rightarrow B}\leq \theta |}{|E_{A}|}+\frac{|E_{B\rightarrow A}\leq \theta |}{|E_{B}|}\right)\end{equation}
where $|E_{A\rightarrow B}\leq \theta |$ denotes the number of
exemplars from A which had a neighbour in B that is closer than
$\theta$ and similarly for $|E_{B\rightarrow A}\leq
\theta |$ the number of exemplars from B to A which their
distance was smaller than $\theta$. When $TC=0$ that means
that every exemplar from the one set was further than $\theta$
to all exemplars in the other set. When $TC=1$ then all exemplars from
one set had a close neighbour in the other set. This metric is extremely
useful especially when comparing tractographies from different subjects
because it does not require $|E_{A}|=|E_{B}|$.
We ran an experiment were we compared TC between pairs of $10$ subjects
with their tractographies warped in MNI space. This generated
$\binom{10}{2}=45$ TC values with $\theta=$$10$ mm. We did this
experiment twice; first by keeping only the bundles with more than $10$
tracks (TC10) and secondly by keeping only the bundles with more than
$100$ tracks (TC100). The average value for TC10 was $47\%$ and standard
deviation $2.6\%$. As expected TC100 (bigger landmarks) did better with
average value of $53\%$ and standard deviation $4.9\%$. The difference
between TC10 and TC100 is highly significant: Student's t$=4.692$,
df=88, $p=1.97\times10^{-5}$, two-sided; and, as a precaution against
non-normality of the underlying distributions, Mann-Whitney U = 530.,