System and method for computer aided detection via asymmetric cascade of sparse linear classifiers

• US 20070110292A1
• Filed: 11/03/2006
• Published: 05/17/2007
• Est. Priority Date: 11/14/2005
• Status: Active Grant

• Current Assignee: Siemens Healthcare GMBH (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Salganicoff, Marcos, Periaswamy, Senthil, Okada, Kazunori, Bi, Jinbo, Fung, Glenn, Kubota, Toshiro, Rao, R.
• Granted Patent: US 7,756,313 B2
• Time in Patent Office: Days
• US Class Current: 382/128
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting

Abstract

A method for computer aided detection of anatomical abnormalities in medical images includes providing a plurality of abnormality candidates and features of said abnormality candidates, and classifying said abnormality candidates as true positives or false positives using a hierarchical cascade of linear classifiers of the form sign(w^Tx+b), wherein x is a feature vector, w is a weighting vector and b is a model parameter, wherein different weights are used to penalize false negatives and false positives, and wherein more complex features are used for each successive stage of said cascade of classifiers.

Claims

1. A method for computer aided detection of anatomical abnormalities in medical images comprising the steps of:

providing a plurality of abnormality candidates and features of said abnormality candidates; and

classifying said abnormality candidates as true positives or false positives using a hierarchical cascade of linear classifiers of the form sign(w^Tx+b), wherein x is a feature vector, w is a weighting vector and b is a model parameter, wherein different weights are used to penalize false negatives and false positives, and wherein more complex features are used for each successive stage of said cascade of classifiers.

2. The method of claim 1, wherein each stage of said cascade solves a linear program formulated using a training error rate ξ

equivalent to max{0,1-y(w^Tx+b)} and an l₁-norm equivalent to ∥

w∥

₁=Σ

|w_i| summed over all features.

3. The method of claim 2, wherein said l₁-norm is weighted by factors γ

_i related to the computational cost of the i^th feature.

4. The method of claim 1, wherein a false negative penalty is set to infinity for the early stages of said cascade of classifiers.

5. The method of claim 1, wherein said abnormality candidates and features include a location, intensity statistics, and geometric information of each candidate.

6. The method of claim 1, wherein each classifier of said cascade of classifiers uses a single set of features.

7. The method of claim 1, wherein each classifier of said cascade of classifiers uses an accumulative set of features that includes those features used by preceding classifiers in said cascade.

8. The method of claim 1, further comprising providing a digitized medical image comprising a plurality of intensities corresponding to a domain of points on a 3-dimensional grid;

segmenting a region-of-interest from said medical image;

generating said abnormality candidates and internal features of said abnormality candidates from said region-of-interest; and

for each abnormality candidate, computing additional more complex features that characterize the shape, size, intensity statistics, and template matches for each candidate.

9. The method of claim 2, wherein said linear program is equivalent to the system represented by

$\begin{array}{c}{\min }_{u,v,\xi }\end{array}$

⁢

λ

⁢

∑

j = 1 d ⁢

( u j + v j ) + μ

l + ⁢

∑

i ∈

C + ⁢

ξ

i + 1 - μ

l - ⁢

∑

i ∈

C - ⁢

ξ

i , ⁢

y ( ∑

j ⁢

X ij ⁡

( u j - v j ) + b ) + ξ

i ≥

1 , ⁢

such ⁢

 

⁢

that ⁢

⁢

ξ

i ≥

0 , i = 1 , …

⁢

 

, l , ⁢

u j , v j ≥

0 , j = 1 , …

⁢

 

, d , ( 1 )

wherein λ

>

0 is a regularization parameter, {x_i, y_i}, i=1, . . . , l denotes the abnormality candidates, y denotes a label indicating whether or not a candidate associated with a feature vector is a true positive, X denotes a feature matrix of d features wherein each row represents candidate feature vector x, and each column specifies a feature, l⁺ is the number of positive candidates and l⁻

the number of negative candidates, C⁺ and C⁻

contain, respectively, the sets of indices of positive candidates and negative candidates, 0≦

μ

≦

1 is a tuning parameter for combining the false negative rate and false positive rate, and w_j=u_j−

v_j.

10. The method of claim 4, wherein imposing an infinite penalty comprises imposing a constraint equivalent to

$\sum _{}$

j ⁢

X ⁡

( u j - v j ) + b ≥

0 , ∀

i ∈

C + ,

wherein said linear program is equivalent to the system represented by

${\min }_{u,v,\mathrm{\xi <br><br>}}<br><br>\mathrm{\lambda <br><br>}<br><br>\underset{j=1}{\overset{d}{\sum <br><br>}}<br><br>\left(u_j+v_j\right)+\frac{1}{l^{-}}<br><br>\underset{i\in <br><br>C^{-}}{\sum <br><br>}<br><br>{\mathrm{\xi <br><br>}}_i,<br><br>\underset{j}{\sum <br><br>}<br><br>X<br><br>\left(u_j-v_j\right)+b\ge <br><br>0,\forall <br><br>i\in <br><br>C^{+},<br><br>-\underset{j}{\sum <br><br>}<br><br>X<br><br>\left(u_j-v_j\right)-b+{\mathrm{\xi <br><br>}}_i\ge <br><br>0,\forall <br><br>i\in <br><br>C^{-}$ $\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}$ ${\mathrm{\xi <br><br>}}_i\ge <br><br>0,i\in <br><br>C^{-},<br><br>u_j,v_j\ge <br><br>0,j=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},d,$

wherein λ

>

0 is a regularization parameter, {x_i, y_i}, i=1, . . . , l denotes the abnormality candidates, y denotes a label indicating whether or not a candidate associated with a feature vector is a true positive, X denotes a feature matrix of d features wherein each row represents candidate feature vector x, and each column specifies a feature, l⁺ is the number of positive candidates and l⁻

the number of negative candidates, C⁺ and C⁻

contain, respectively, the sets of indices of positive candidates and negative candidates, 0≦

μ

≦

1 is a tuning parameter for combining the false negative rate and false positive rate, and w_j=u_j−

v_j.

11. The method of claim 2, wherein each said linear classifier is constructed using a boosting algorithm comprising the steps of:

partitioning said weights w_i into a working set W for constructing said classifier and a remaining set N of weights eliminated from said classifier;

initializing a first column vector of a feature matrix X_ij to a vector of ones;

solving said linear program using said first column;

finding a next column vector that maximizes a quantity τ

defined as

$\mathrm{\tau <br><br>}=\underset{j\in <br><br>N}{\max }<br><br><br><br>\underset{i^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>{\mathrm{\beta <br><br>}}_{\hat{i}}<br><br>y_i<br><br>X_{\mathrm{ij}}<br><br>,$

wherein y is a label indicating whether or not a candidate associated with a feature vector is a true positive, and β

is derived from a Lagrangian dual to said linear program; and

reinitializing said first column vector by including said next column vector, wherein if T is less than a predetermined value, the boosting algorithm terminates.

12. A method for computer aided detection of anatomical abnormalities in medical images comprising the steps of:

providing a plurality of abnormality candidates and internal features of said abnormality candidates; and

classifying said abnormality candidates as true positives or false positives using a plurality of linear programs arranged in a hierarchical cascade, said programs constructing classifiers of the form sign(w^Tx+b), wherein x is a feature vector, w is a weighting vector and b is a model parameter, wherein each stage of said cascade solves a linear program formulated using a training error rate ξ

equivalent to max{0,1-y(w^Tx+b)} and an l₁-norm equivalent to ∥

w∥

₁=Σ

|w_i| summed over all features.

13. The method of claim 12, wherein different weights are used to penalize false negatives and false positives, and wherein a first classifier uses said internal features and each successive classifier of said cascade uses more complex features to eliminate false positives from said abnormality candidates.

14. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for computer aided detection of anatomical abnormalities in medical images, said method comprising the steps of:

providing a plurality of abnormality candidates and features of said abnormality candidates; and

classifying said abnormality candidates as true positives or false positives using a hierarchical cascade of linear classifiers of the form sign(w^Tx+b), wherein x is a feature vector, w is a weighting vector and b is a model parameter, wherein different weights are used to penalize false negatives and false positives, and wherein more complex features are used for each successive stage of said cascade of classifiers.

15. The computer readable program storage device of claim 14, wherein each stage of said cascade solves a linear program formulated using a training error rate ξ

equivalent to max{0,1-y(w^Tx+b)} and an l₁-norm equivalent to ∥

w∥

₁=Σ

|w_i| summed over all features.

16. The computer readable program storage device of claim 15, wherein said l₁-norm is weighted by factors γ

_i related to the computational cost of the i^th feature.

17. The computer readable program storage device of claim 14, wherein a false negative penalty is set to infinity for the early stages of said cascade of classifiers.

18. The computer readable program storage device of claim 14, wherein said abnormality candidates and features include a location, intensity statistics, and geometric information of each candidate.

19. The computer readable program storage device of claim 14, wherein each classifier of said cascade of classifiers uses a single set of features.

20. The computer readable program storage device of claim 14, wherein each classifier of said cascade of classifiers uses an accumulative set of features that includes those features used by preceding classifiers in said cascade.

21. The computer readable program storage device of claim 14, the method further comprising providing a digitized medical image comprising a plurality of intensities corresponding to a domain of points on a 3-dimensional grid;

segmenting a region-of-interest from said medical image;

generating said abnormality candidates and internal features of said abnormality candidates from said region-of-interest; and

for each abnormality candidate, computing additional more complex features that characterize the shape, size, intensity statistics, and template matches for each candidate.

22. The computer readable program storage device of claim 15, wherein said linear program is equivalent to the system represented by

$\begin{array}{c}{\min }_{u,v,\xi }\end{array}$

⁢

λ

⁢

∑

j = 1 d ⁢

( u j + v j ) + μ

l + ⁢

∑

i ∈

C + ⁢

ξ

i + 1 - μ

l - ⁢

∑

i ∈

C - ⁢

ξ

i , ⁢

y ( ∑

j ⁢

X ij ⁡

( u j - v j ) + b ) + ξ

i ≥

1 , ⁢

such ⁢

 

⁢

that ⁢

⁢

ξ

i ≥

0 , i = 1 , …

⁢

 

, l , ⁢

u j , v j ≥

0 , j = 1 , …

⁢

 

, d , ( 1 )

wherein λ

>

0 is a regularization parameter, {x_i, y_i}, i=1, . . . , l denotes the abnormality candidates, y denotes a label indicating whether or not a candidate associated with a feature vector is a true positive, X denotes a feature matrix of d features wherein each row represents candidate feature vector x, and each column specifies a feature, l⁺ is the number of positive candidates and l⁻

the number of negative candidates, C⁺ and C⁻

contain, respectively, the sets of indices of positive candidates and negative candidates, 0≦

μ

≦

1 is a tuning parameter for combining the false negative rate and false positive rate, and w_j=u_j−

v_j.

23. The computer readable program storage device of claim 17, wherein imposing an infinite penalty comprises imposing a constraint equivalent to

$\sum _{}$

j ⁢

X ⁡

( u j - v j ) + b ≥

0 , ∀

i ∈

C + ,

wherein said linear program is equivalent to the system represented by

${\min }_{u,v,\mathrm{\xi <br><br>}}<br><br>\mathrm{\lambda <br><br>}<br><br>\underset{j=1}{\overset{d}{\sum <br><br>}}<br><br>\left(u_j+v_j\right)+\frac{1}{l^{-}}<br><br>\underset{i\in <br><br>C^{-}}{\sum <br><br>}<br><br>{\mathrm{\xi <br><br>}}_i,<br><br>\underset{j}{\sum <br><br>}<br><br>X<br><br>\left(u_j-v_j\right)+b\ge <br><br>0,\forall <br><br>i\in <br><br>C^{+},<br><br>-\underset{j}{\sum <br><br>}<br><br>X<br><br>\left(u_j-v_j\right)-b+{\mathrm{\xi <br><br>}}_i\ge <br><br>0,\forall <br><br>i\in <br><br>C^{-}$ $\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}$ ${\mathrm{\xi <br><br>}}_i\ge <br><br>0,i\in <br><br>C^{-},<br><br>u_j,v_j\ge <br><br>0,j=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},d,$

wherein λ

>

0 is a regularization parameter, {x_i, y_i}, i=1, . . . , l denotes the abnormality candidates, y denotes a label indicating whether or not a candidate associated with a feature vector is a true positive, X denotes a feature matrix of d features wherein each row represents candidate feature vector x, and each column specifies a feature, l⁺ is the number of positive candidates and l⁻

the number of negative candidates, C⁺ and C⁻

contain, respectively, the sets of indices of positive candidates and negative candidates, 0≦

μ

≦

1 is a tuning parameter for combining the false negative rate and false positive rate, and w_j=u_j−

v_j.

24. The computer readable program storage device of claim 15, wherein each said linear classifier is constructed using a boosting algorithm comprising the steps of:

partitioning said weights w_i into a working set W for constructing said classifier and a remaining set N of weights eliminated from said classifier;

initializing a first column vector of a feature matrix X_ij to a vector of ones;

solving said linear program using said first column;

finding a next column vector that maximizes a quantity τ

defined as

$\mathrm{\tau <br><br>}=\underset{j\in <br><br>N}{\max }<br><br><br><br>\underset{i^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>{\mathrm{\beta <br><br>}}_{\hat{i}}<br><br>y_i<br><br>X_{\mathrm{ij}}<br><br>,$

wherein y is a label indicating whether or not a candidate associated with a feature vector is a true positive, and β

is derived from a Lagrangian dual to said linear program; and

reinitializing said first column vector by including said next column vector, wherein if τ

is less than a predetermined value, the boosting algorithm terminates.