System and method for joint optimization of cascaded classifiers for computer aided detection
View Patent ↗A method for training classifiers for Computer-Aided Detection in medical images includes providing an image feature training set {(x i , y i )} i=1 l , wherein x i εR d are input feature variables and y i ε{−1,1} are class labels, and a cascade of K classifiers to be trained, minimizing, for each classifier k, a first cost function to initialize an α k 0 associated with each classifier k, fixing all classifiers except classifier k and minimizing a second cost function to solve for α k c for a counter value c using the training dataset {(x i k , y i )} i=1 l , calculating a third cost function J c (α l c , . . . , α K c ) for each classifier k, and comparing J c with a previous iteration J c−1 , wherein if J c −J c−1 is less than a predetermined tolerance, said classifier training is completed.
1. A computer-implemented method for training classifiers for Computer-Aided Detection in medical images, said method performed by a computer comprising the steps of:
providing an image feature training set {(x i , y i )} i=1 l , wherein x i εR d are input feature variables and y i ε{−1,1} are class labels for labeling each variable and a cascade of K classifiers to be trained;
minimizing, for each classifier k, a first cost function
Φ
(
α
k
)
+
∑
i
=
1
I
w
i
×
max
(
0
,
1
-
α
T
y
i
x
i
k
)
,
to initialize an α k 0 associated with each classifier k, wherein the function Φ: R (d) = R is a regularization function and {w i : w i ≧0, ∀i} is a pre-determined weight associated with x i ;
for each classifier k, fixing all classifiers except classifier k and minimizing a second cost function
Φ
k
(
α
k
)
+
v
1
∑
i
∈
C
-
w
i
×
max
(
0
,
e
ik
)
+
v
2
∑
i
∈
C
+
max
(
0
,
e
i
1
,
…
,
e
ik
,
…
,
e
iK
)
to solve for α k c for a counter value c using the training dataset {(x i k , y i )} i=1 l , wherein
w
i
=
∏
m
=
1
,
m
≠
k
K
max
(
0
,
e
im
)
,
e ik =1−α k T y i x ik ′ defines a hinge loss of the i th training example {(x ik ′, y i )} induced by classifier k, v 1 and v 2 are weighting factors, C + and C − are corresponding sets of indices for positive and negative classes respectively, and wherein x ik ′ denotes the subset of features in x i used by classifier k;
calculating
J
c
(
α
1
c
,
…
,
α
K
c
)
=
∑
k
=
1
K
Φ
k
(
α
k
c
)
+
v
1
∑
i
∈
C
-
∏
k
=
1
K
max
(
0
,
e
ik
)
+
v
2
∑
i
∈
C
+
max
(
0
,
e
i
1
,
…
,
e
iK
)
for each classifier k; and
comparing J c with a previous iteration J c−1 , wherein if J c −J c−1 is less than a predetermined tolerance, said classifier training is completed.
2. The method of claim 1 , wherein providing an image feature training set comprises:
providing a set of image features, said features generated from one or more digitized medical images, each said image comprising a plurality of intensities associated with an n-dimensional grid of points;
partitioning said image feature set into a plurality of subsets according to a computational cost of classifying a candidate feature as one of said image features;
developing a feature classifier wherein each image feature subset is associated with a feature classifier; and
forming of cascade of said classifiers of increasing complexity.
3. The method of claim 2 , further comprising tuning values of said weighting factors v 1 and v 2 to maximize an area under a receiver operator characteristic (ROC) curve corresponding to a domain of 0 to 5 false positives per image,
ξ
i
≥
1
-
α
T
y
i
x
i
,
ξ
i
≥
0
,
∀
i
.
4. The method of claim 1 , wherein said second cost function is solved as a mathematical programming system
min
(
α
k
,
ξ
k
)
∈
R
d
k
+
i
Φ
k
(
α
k
)
+
v
1
∑
i
∈
C
-
w
i
ξ
i
+
v
2
∑
i
∈
C
+
ξ
i
,
such that
ξ
i
≥
e
ik
,
∀
i
,
ξ
i
≥
0
,
∀
i
∈
C
-
,
ξ
i
≥
γ
i
,
∀
i
∈
C
+
,
wherein y i =max(0, e il , . . . , e i(m−1) , e i(m+1) , . . . , e iK ).
5. The method of claim 1 , wherein said first cost function is solved as a mathematical programming system
min
(
α
,
ξ
)
∈
R
d
+
1
Φ
(
α
)
+
∑
i
=
1
I
w
i
ξ
i
such that
ξ
i
≥
1
-
α
T
y
i
x
i
,
ξ
i
≥
0
,
∀
i
.
6. The method of claim 1 , wherein said trained classifiers are adapted to being used in a cascade of classifiers of increasing complexity that detect and classify regions of interest in incoming medical images.
7. The method of claim 1 , wherein Φ(α)=∥α∥ 2 2 .
8. The method of claim 1 , wherein Φ(α)=|α|.
9. The method of claim 1 , further comprising incrementing a counter c, and terminating said training if said counter becomes greater than a pre-determined maximum.
10. A computer-implemented method for training classifiers for Computer-Aided Detection in medical images, said method performed by a computer comprising the steps of:
providing an image feature training set {(x i , y i )} i=1 l , wherein x i εR d are input feature variables and y i ε{−1,1} are class labels for labeling each variable and a cascade of K hyperplane classifiers to be trained;
training said cascade of hyperplane classifiers using said training set wherein a negative candidate is correctly classified by said cascade when it is rejected by at least one of said classifiers, and a positive candidate is correctly classified if it is detected by all of the classifiers in the cascade;
wherein training said cascade of hyperplane classifiers comprises providing an initial set α k 0 associated with each classifier k by minimizing, for each classifier k, a first cost function
Φ
(
α
k
)
+
∑
i
=
1
I
w
i
×
max
(
0
,
1
-
α
T
y
i
x
i
k
)
wherein the function Φ: R (d) R is a regularization function and {w i : w i ≧0, ∀i} is a pre-determined weight associated with x i ;
and, at each iteration of the classifier training, given a set α k c from a previous iteration, solving for α k c+1 for each classifier k by fixing all classifiers except classifier k and minimizing a second cost function
Φ
k
(
α
k
)
+
v
1
∑
i
∈
C
-
w
i
×
max
(
0
,
e
ik
)
+
v
2
∑
i
∈
C
+
max
(
0
,
e
i
1
,
…
,
e
ik
,
…
,
e
iK
)
using the training dataset {(x i k , y i )} i=1 l , wherein
w
i
=
∏
m
=
1
,
m
≠
k
K
max
(
0
,
e
im
)
,
e ik =1−α k T y i x′ ik defines a hinge loss of the i th training example {(x ik ′, y i )} induced by classifier k, v 1 and v 2 are weighting factors, C + and C − are corresponding sets of indices for positive and negative classes respectively, and x ik ′ denotes the subset of features in x i used by classifier k.
11. The method of claim 10 , further comprising calculating a third cost function
J
c
+
(
α
1
c
+
1
,
…
,
α
K
c
+
1
)
=
∑
k
=
1
K
Φ
k
(
α
k
c
+
1
)
+
v
1
∑
i
∈
C
-
∏
k
=
1
K
max
(
0
,
e
ik
)
+
v
2
∑
i
∈
C
+
max
(
0
,
e
i
1
,
…
,
e
iK
)
from the set of α k c+1 for each classifier k; and
comparing J c+1 with a previous iteration J c to determine if said training is complete.
12. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for training classifiers for Computer-Aided Detection in medical images, said method comprising the steps of:
providing an image feature training set {(x i , y i )} i=1 l , wherein x i εR d are input feature variables and y i ε{−1,1} are class labels for labeling each variable and a cascade of K classifiers to be trained;
minimizing, for each classifier k, a first cost function
Φ
k
(
α
k
)
+
∑
i
=
1
l
w
i
×
max
(
0
,
1
-
α
T
y
i
x
i
k
)
to initialize an α k 0 associated with each classifier k, wherein the function Φ: R (d) R is a regularization function and {w i : w i ≧0, ∀i} is a pre-determined weight associated with x i ;
for each classifier k, fixing all classifiers except classifier k and minimizing a second cost function
Φ
k
(
α
k
)
+
v
1
∑
i
∈
C
-
w
i
×
max
(
0
,
e
ik
)
+
v
2
∑
i
∈
C
+
max
(
0
,
e
i
1
,
…
,
e
ik
,
…
,
e
iK
)
to solve for α k c for a counter value c using the training dataset {(x i k , y i )} i=1 l , wherein
w
i
=
∏
m
=
1
,
m
≠
k
K
max
(
0
,
e
im
)
,
e
ik
=
1
-
α
k
T
y
i
x
ik
′
defines a hinge loss of the i th training example {(x ik ′, y i )} induced by classifier k, v 1 and v 2 are weighting factors, C + and C − are corresponding sets of indices for positive and negative classes respectively, and wherein x ik ′ denotes the subset of features in x i used by classifier k;
calculating
J
c
(
α
i
c
,
…
,
α
K
c
)
=
∑
k
=
1
K
Φ
k
(
α
k
c
)
+
v
1
∑
i
∈
C
-
∏
k
=
1
K
max
(
0
,
e
ik
)
+
v
2
∑
i
∈
C
+
max
(
0
,
e
i
1
,
…
,
e
iK
)
for each classifier k; and
comparing J c with a previous iteration J c−1 , wherein if J c −J c−1 is less than a predetermined tolerance, said classifier training is completed.
13. The computer readable program storage device of claim 12 , wherein providing an image feature training set comprises:
providing a set of image features, said features generated from one or more digitized medical images, each said image comprising a plurality of intensities associated with an n-dimensional grid of points;
partitioning said image feature set into a plurality of subsets according to a computational cost of classifying a candidate feature as one of said image features;
developing a feature classifier wherein each image feature subset is associated with a feature classifier; and
forming of cascade of said classifiers of increasing complexity.
14. The computer readable program storage device of claim 13 , the method further comprising tuning values of said weighting factors v 1 and v 2 to maximize an area under a receiver operator characteristic (ROC) curve corresponding to a domain of 0 to 5 false positives per image.
15. The computer readable program storage device of claim 12 , wherein said second cost function is solved as a mathematical programming system
min
(
α
k
,
ξ
k
)
∈
R
d
k
+
I
Φ
k
(
α
k
)
+
v
1
∑
i
∈
C
-
w
i
ξ
i
+
v
2
∑
i
∈
C
+
ξ
i
,
such that
ξ
i
≥
e
ik
,
∀
i
,
ξ
i
≥
0
,
∀
i
∈
C
-
,
ξ
i
≥
γ
i
,
∀
i
∈
C
+
,
wherein y i =max(0, e il , . . . , e i(m−1) , e i(m+1) , . . . , e iK ).
16. The computer readable program storage device of claim 12 , wherein said first cost function is solved as a mathematical programming system
min
(
α
,
ξ
)
∈
R
d
+
1
Φ
(
α
)
+
∑
i
=
1
I
w
i
ξ
i
such that
ξ
i
≥
1
-
α
T
y
i
x
i
,
ξ
i
≥
0
,
∀
i
.
17. The computer readable program storage device of claim 12 , wherein said trained classifiers are adapted to being used in a cascade of classifiers of increasing complexity that detect and classify regions of interest in incoming medical images.
18. The computer readable program storage device of claim 12 , wherein Φ(α)=∥α∥ 2 2 .
19. The computer readable program storage device of claim 12 , wherein Φ(α)=|α|.
20. The computer readable program storage device of claim 12 , the method further comprising incrementing a counter c, and terminating said training if said counter becomes greater than a pre-determined maximum.