System and Method for Multiple Instance Learning for Computer Aided Detection

• US 20070189602A1
• Filed: 02/06/2007
• Published: 08/16/2007
• Est. Priority Date: 02/07/2006
• Status: Active Grant

• Current Assignee: Siemens Healthcare GMBH (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Krishnapuram, Balaji, Fung, Glenn, Dundar, Murat, Rao, R.
• Granted Patent: US 7,986,827 B2
• Time in Patent Office: Days
• US Class Current: 382/159
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 7/0012 Biomedical image inspection
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

A method of training a classifier for computer aided detection of digitized medical images, includes providing a plurality of bags, each bag containing a plurality of feature samples of a single region-of-interest in a medical image, wherein said features include texture, shape, intensity, and contrast of said region-of-interest, wherein each region-of-interest has been labeled as either malignant or healthy, and training a classifier on said plurality of bags of feature samples, subject to the constraint that at least one point in a convex hull of each bag, corresponding to a feature sample, is correctly classified according to the labeled of the associated region-of-interest.

Claims

1. A method of training a classifier for computer aided detection of digitized medical images, comprising the steps of:

providing a plurality of bags, each bag containing a plurality of feature samples of a single region-of-interest in a medical image, wherein said features include texture, shape, intensity, and contrast of said region-of-interest, wherein each region-of-interest has been labeled as either malignant or healthy; and

training a classifier on said plurality of bags of feature samples, subject to the constraint that at least one point in a convex hull of each bag, corresponding to a feature sample, is correctly classified according to the labeled of the associated region-of-interest.

2. The method of claim 1, wherein said classifier is trained by solving a program equivalent to

$\underset{(\xi }{\min }$

, ω

, η

, λ

) ∈

R r + n + 1 + γ

⁢

vE ⁡

( ξ

) + Φ

⁡

( ω

, η

) + Ψ

⁡

( λ

) $\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\xi <br><br>}}^i=d^i-\left({\mathrm{\lambda <br><br>}}_j^i<br><br>B_j^i<br><br>\mathrm{\omega <br><br>}-e<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\eta <br><br>}\right)$ $\text{\hspace{1em}<br><br>}<br><br>\mathrm{\xi <br><br>}\in <br><br>\mathrm{\Omega <br><br>}$ $\text{\hspace{1em}<br><br>}<br><br>e^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j^i=1$ $\text{\hspace{1em}<br><br>}<br><br>0\le <br><br>{\mathrm{\lambda <br><br>}}_j^i$

wherein ξ

={ξ

₁, . . . , ξ

_r} are slack terms (errors), E;

R^rR represents a loss function, or is a hyperplane coefficient, η

is the bias (offset from origin) term, λ

is a vector containing the coefficients of the convex combination that defines the representative point of bag i in class j wherein 0≦

λ

_jⁱ, e′

λ

_jⁱ=1, γ

is the total number of convex hull coefficients corresponding to the representative points in class j, Φ

;

R⁽ⁿ⁺¹⁾R is a regularization function on the hyperplane coefficients, Ψ

is a regularization function on the convex combination coefficients λ

_jⁱ, matrix B_jⁱ∈

R<sup>mji×

n</sup>, i=1, . . . , r_j, j∈

{±

1} is the i^th bag of class label j, r is the total number of representative points, n is the number of features, m_jⁱ is the number of rows in B, vector d∈

{±

1}^rj represents binary bag-labels for the malignant and healthy sets, respectively, and the vector e represent a vector with all its elements one.

3. The method of claim 2, wherein E(ξ

)=∥

(ξ

)₊∥

₂², Φ

(ω

,η

)=∥

(ω

,η

)∥

₂² and Ω

=R^r+, wherein ξ

₊ and r₊ are respectively slack variables and points labeled by +1.

4. The method of claim 2, wherein E(ξ

)=∥

(ξ

)∥

₂², Φ

(ω

,η

)=∥

(ω

,η

)∥

₂² and Ω

=R^r.

5. The method of claim 2, wherein v=1, E(ξ

)=∥

ξ

∥

₂² and Ω

={ξ

;

e′

ξ

_j=0, j∈

{±

1}}.

6. The method of claim 5, further comprising replacing ξ

ⁱ by dⁱ−

(λ

_jⁱB_jⁱω

−

eη

) in the objective function, replacing equality constraints e′

ξ

_j=0 by ω

′

(μ

₊−

μ

₋

)=2, wherein classifier is trained by solving a program equivalent to

$\underset{\left(\mathrm{\omega <br><br>},\mathrm{\lambda <br><br>}\right)\in <br><br>R^{n+\mathrm{\gamma <br><br>}}}{\min }<br><br>{\mathrm{\omega <br><br>}}^T<br><br>S_W<br><br>\mathrm{\omega <br><br>}+\mathrm{\Phi <br><br>}<br><br>\left(\mathrm{\omega <br><br>}\right)+\mathrm{\Psi <br><br>}<br><br>\left(\mathrm{\lambda <br><br>}\right)$ $\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\omega <br><br>}}^T<br><br>\left({\mathrm{\mu <br><br>}}_{+}-{\mathrm{\mu <br><br>}}_{-}\right)=b$ $\text{\hspace{1em}<br><br>}<br><br>e^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j^i=1<br><br><br><br>\text{\hspace{1em}<br><br>}<br><br>0\le <br><br>{\mathrm{\lambda <br><br>}}_j^i$

wherein

$S_W={\sum <br><br>}_{j\in <br><br>\left\{\pm <br><br>1\right\}}<br><br>\frac{1}{r_j}<br><br>\left(X_j-{\mathrm{\mu <br><br>}}_j<br><br>e^{\mathrm{\prime <br><br>}}\right)<br><br>{\left(X_j-{\mathrm{\mu <br><br>}}_j<br><br>e^{\mathrm{\prime <br><br>}}\right)}^T$

is the within-class scatter matrix,

${\mathrm{\mu <br><br>}}_j=\frac{1}{r_j}<br><br>X_j<br><br>e$

is the mean for class j, X_j∈

R<sup>rj×

n</sup> is a matrix containing the r_j representative points on an n-dimensional space such that the row of X_j denoted by b_jⁱ=B_jⁱλ

_jⁱ is the representative point of bag i in class j where i={1, . . . , r_j}, j∈

{±

1}, and μ

₊ and μ

₋

are the mean values for the positive and negative labeled classes, respectively.

7. The method of claim 6, further comprising:

initializing

${\mathrm{\lambda <br><br>}}^{i<br><br>\text{\hspace{1em}<br><br>}<br><br>0}=\frac{e}{m^i},\forall <br><br>i=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},r$

and a counter c=0,

$\underset{\left(\mathrm{\omega <br><br>},\mathrm{\lambda <br><br>}\right)\in <br><br>R^{n+\mathrm{\gamma <br><br>}}}{\min }<br><br>{\mathrm{\omega <br><br>}}^T<br><br>S_W<br><br>\mathrm{\omega <br><br>}+\mathrm{\Phi <br><br>}<br><br>\left(\mathrm{\omega <br><br>}\right)$$\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}$${\mathrm{\omega <br><br>}}^T<br><br>\left({\mathrm{\mu <br><br>}}_{+}-{\mathrm{\mu <br><br>}}_{-}\right)=b;<br><br>$

for a fixed ω

=ω

^c, solving for λ

^ic, ∀

i=1, . . . , r, in a system equivalent to

$\underset{\left(\mathrm{\omega <br><br>},\mathrm{\lambda <br><br>}\right)\in <br><br>R^{n+\mathrm{\gamma <br><br>}}}{\min }<br><br>{\mathrm{\lambda <br><br>}}^T<br><br>{\stackrel{\_}{S}}_W<br><br>\mathrm{\lambda <br><br>}+\mathrm{\Psi <br><br>}<br><br>\left(\mathrm{\lambda <br><br>}\right)$$\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}$${\mathrm{\lambda <br><br>}}^T<br><br>\left({\stackrel{\_}{\mathrm{\mu <br><br>}}}_{+}-{\stackrel{\_}{\mathrm{\mu <br><br>}}}_{-}\right)=b$$e^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j^i=1$$0\le <br><br>{\mathrm{\lambda <br><br>}}_j^i$

wherein S_W and μ

are defined with X_j replaced by X_j wherein X_j∈

R<sup>rj×

γ</sup>

is a matrix containing r_j new points on a γ

-dimensional space wherein the row of X_j denoted by b_jⁱ is a vector with its nonzero elements set to B_jⁱω

^c; and

if ∥

λ

^1(c+1)−

λ

^1c, . . . , λ

^r(c+1)−

λ

^rc∥

₂ is greater than a predefined tolerance, replacing λ

^ic by λ

^i(c+1) and c by c+1 and repeating the two previous steps.

8. The method of claim 7, further comprising setting convex-hull coefficients of negative bags to be 1.

9. The method of claim 6, wherein Φ

(ω

)=ε

∥

ω

∥

₂² and Ψ

(λ

)=ε

∥

λ

∥

₂², wherein ε

is a positive regularization parameter.

10. The method of claim 7, further comprising transforming said feature samples into a higher dimensional space using a kernel transformation (X{+}, X) for the positive class and K(X{−

}, X) for the negative class, wherein X{+}, X{−

}, and X are data matrices for positive, negative and all samples respectively, wherein each row is a sample vector in these matrices, wherein if the size of X is too large, subsampling a random subset from said original feature samples.

11. A method of training a classifier for computer aided detection of digitized medical images, comprising the steps of:

providing a plurality of bags, each bag containing a plurality of feature samples of a single region-of-interest in a medical image, wherein each region-of-interest has been labeled as either malignant or healthy, wherein each bag is represented by a matrix B_jⁱ∈

R<sup>mji×

n</sup>, i=1, . . . , r_j, j∈

{±

1} is the i^th bag of class label j, r is the total number of representative points, n is the number of features, m_jⁱ is the number of rows in B; and

solving a program equivalent to

$\underset{\left(\mathrm{\xi <br><br>},\mathrm{\omega <br><br>},\mathrm{\eta <br><br>},\mathrm{\lambda <br><br>}\right)\in <br><br>R^{r+n+1+y}}{\min }<br><br>{<br><br>\mathrm{\xi <br><br>}<br><br>}_2^2+\mathrm{\Phi <br><br>}<br><br>\left(\mathrm{\omega <br><br>},\mathrm{\eta <br><br>}\right)+\mathrm{\Psi <br><br>}<br><br>\left(\mathrm{\lambda <br><br>}\right)$$\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}$${\mathrm{\xi <br><br>}}^i=d^i-\left({\mathrm{\lambda <br><br>}}_j^i<br><br>B_j^i<br><br>\mathrm{\omega <br><br>}-\mathrm{e<br><br>\eta <br><br>}\right)$$e^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{\xi <br><br>}}_j=0$$e^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j^i=1$$0\le <br><br>{\mathrm{\lambda <br><br>}}_j^i$

wherein ξ

={ξ

₁, . . . , ξ

_r} are slack terms, ω

is a hyperplane coefficient, η

is the bias (offset from origin) term, λ

is a vector containing the coefficients of the convex combination that defines the representative point of bag i in class j wherein 0≦

λ

_jⁱ, e′

λ

_jⁱ=1, γ

is the total number of convex hull coefficients corresponding to the representative points in class j, Φ

;

R⁽ⁿ⁺¹⁾R is a regularization function on the hyperplane coefficients, Ψ

is a regularization function on the convex combination coefficients λ

_jⁱ, matrix B_jⁱ∈

R<sup>mji×

n</sup>, i=1, . . . , r_j, j∈

{±

1} is the i^th bag of class label j, r is the total number of representative points, n is the number of features, m_jⁱ is the number of rows in B, vector d∈

{±

1}^rj represents binary bag-labels for the malignant and healthy sets, respectively, and the vector e represent a vector with all its elements one.

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 a classifier for computer aided detection of digitized medical images, said method comprising the steps of:

providing a plurality of bags, each bag containing a plurality of feature samples of a single region-of-interest in a medical image, wherein said features include texture, shape, intensity, and contrast of said region-of-interest, wherein each region-of-interest has been labeled as either malignant or healthy; and

training a classifier on said plurality of bags of feature samples, subject to the constraint that at least one point in a convex hull of each bag, corresponding to a feature sample, is correctly classified according to the labeled of the associated region-of-interest.

13. The computer readable program storage device of claim 12, wherein said classifier is trained by solving a program equivalent to

$\underset{(\xi }{\min }$

,  

⁢

ω

,  

⁢

η

,  

⁢

λ

) ⁢

 

∈

 

⁢

R r + n + 1 + y ⁢

vE ⁡

( ξ

) + Φ

⁡

( ω

, η

) + Ψ

⁡

( λ

) $\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}$ ${\mathrm{\xi <br><br>}}^i=d^i-\left({\mathrm{\lambda <br><br>}}_j^i<br><br>\text{\hspace{1em}<br><br>}<br><br>B_j^i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\omega <br><br>}-e<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\eta <br><br>}\right)$ $\mathrm{\xi <br><br>}=\mathrm{\Omega <br><br>}$ $e^{\mathrm{\prime <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\lambda <br><br>}}_j^i=1$ $0\le <br><br>{\mathrm{\lambda <br><br>}}_j^i$

wherein ξ

={ξ

₁, . . . , ξ

_r} are slack terms (errors), E;

R^rR represents a loss function, ω

is a hyperplane coefficient, η

is the bias (offset from origin) term, λ

is a vector containing the coefficients of the convex combination that defines the representative point of bag i in class j wherein 0≦

λ

_jⁱ, e′

λ

_jⁱ=1, γ

is the total number of convex hull coefficients corresponding to the representative points in class j, Φ

;

R⁽ⁿ⁺¹⁾R is a regularization function on the hyperplane coefficients, Ψ

is a regularization function on the convex combination coefficients λ

_jⁱ, matrix B_jⁱ∈

R<sup>mji×

n</sup>, i=1, . . . , r_j, j∈

{±

1} is the i^th bag of class label j, r is the total number of representative points, n is the number of features, m_jⁱ is the number of rows in B, vector d∈

{±

1}^rj represents binary bag-labels for the malignant and healthy sets, respectively, and the vector e represent a vector with all its elements one.

14. The computer readable program storage device of claim 13, wherein E(ξ

)=∥

(ξ

)₊∥

₂², Φ

(ω

,η

)=∥

(ω

,η

)∥

₂² and Ω

=R^r+, wherein ξ

⁺ and r⁺ are respectively slack variables and points labeled by +1.

15. The computer readable program storage device of claim 13, wherein E(ξ

)=∥

(ξ

)∥

₂², Φ

(ω

,η

)=∥

(ω

,η

)∥

₂² and Ω

=R^r.

16. The computer readable program storage device of claim 13, wherein v=1, E(ξ

)=∥

ξ

∥

₂² and Ω

={ξ

;

e′

ξ

_j=0, j∈

{±

1}}.

17. The computer readable program storage device of claim 16, the method further comprising replacing ξ

ⁱ by dⁱ−

(λ

_jⁱB_jⁱω

−

eη

) in the objective function, replacing equality constraints e′

ξ

_j=0 by ω

′

(μ

₊−

μ

₋

)=2, wherein classifier is trained by solving a program equivalent to

$\underset{\left(\mathrm{\omega <br><br>},\mathrm{\lambda <br><br>}\right)\in <br><br>R^{n+\mathrm{\gamma <br><br>}}}{\min }<br><br>{\mathrm{\omega <br><br>}}^T<br><br>S_W<br><br>\mathrm{\omega <br><br>}+\mathrm{\Phi <br><br>}<br><br>\left(\mathrm{\omega <br><br>}\right)+\mathrm{\Psi <br><br>}<br><br>\left(\mathrm{\lambda <br><br>}\right)$ $\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}$ ${\mathrm{\omega <br><br>}}^T<br><br>\left({\mathrm{\mu <br><br>}}_{+}-{\mathrm{\mu <br><br>}}_{-}\right)=b$ $e^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j^i=1$ $0\le <br><br>{\mathrm{\lambda <br><br>}}_j^i$

wherein

$S_W={\sum <br><br>}_{j\in <br><br>\left\{\pm <br><br>1\right\}}<br><br>\frac{1}{r_j}<br><br>\left(X_j-{\mathrm{\mu <br><br>}}_j<br><br>e^{\mathrm{\prime <br><br>}}\right)<br><br>{\left(X_j-{\mathrm{\mu <br><br>}}_j<br><br>e^{\mathrm{\prime <br><br>}}\right)}^T$

is the within-class scatter matrix,

${\mathrm{\mu <br><br>}}_j=\frac{1}{r_j}<br><br>X_j<br><br>e$

is the mean for class j, X_j∈

R<sup>rj×

n</sup> is a matrix containing the r_j representative points on an n-dimensional space such that the row of X_j denoted by b_jⁱ=B_jⁱλ

_jⁱ is the representative point of bag i in class j where i={1, . . . , r_j}, j∈

{±

1}, and μ

₊ and μ

₋

are the mean values for the positive and negative labeled classes, respectively.

18. The computer readable program storage device of claim 17, the method further comprising:

initializing

${\mathrm{\lambda <br><br>}}^{i<br><br>\text{\hspace{1em}<br><br>}<br><br>0}=\frac{e}{m^i},\forall <br><br>i=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},r$

and a counter c=0,

for a fixed λ

^ic, ∀

i=1, . . . , r, solving for w^c in a system equivalent to

$\underset{\left(\mathrm{\omega <br><br>},\mathrm{\lambda <br><br>}\right)\in <br><br>R^{n+\mathrm{\gamma <br><br>}}}{\min }<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\omega <br><br>}}^T<br><br>S_W<br><br>\mathrm{\omega <br><br>}+\mathrm{\Phi <br><br>}<br><br>\left(\mathrm{\omega <br><br>}\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\omega <br><br>}}^T<br><br>\left({\mathrm{\mu <br><br>}}_{+}-{\mathrm{\mu <br><br>}}_{-}\right)=b;<br><br>$

for a fixed ω

=ω

^c, solving for λ

^ic, ∀

i=1, . . . , r, in a system equivalent to

$\underset{\left(\mathrm{\omega <br><br>},\text{\hspace{1em}<br><br>}<br><br>\mathrm{\lambda <br><br>}\right)<br><br>\text{\hspace{1em}<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>R^{n<br><br>\text{\hspace{1em}<br><br>}+\text{\hspace{1em}<br><br>}<br><br>\mathrm{\gamma <br><br>}}}{\min }<br><br>{\mathrm{\lambda <br><br>}}^T<br><br>\text{\hspace{1em}<br><br>}<br><br>{\stackrel{\_}{S}}_W<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\lambda <br><br>}+\mathrm{\Psi <br><br>}<br><br>\left(\mathrm{\lambda <br><br>}\right)<br><br>\text{\hspace{1em}<br><br>}$$\mathrm{such}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{that}<br><br>\text{\hspace{1em}<br><br>}$${\mathrm{\lambda <br><br>}}^T<br><br>\left({\mathrm{\mu <br><br>}}_{+}-{\mathrm{\mu <br><br>}}_{-}\right)=b<br><br><br><br>e^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j^i=1<br><br><br><br>0\le <br><br>{\mathrm{\lambda <br><br>}}_j^i$

wherein S_w and μ

are defined with X_j replaced by X_j wherein X<sub>j∈

R</sub><sup>rj×

γ</sup>

is a matrix containing r_j new points on a γ

-dimensional space wherein the row of X_j denoted by b_jⁱ is a vector with its nonzero elements set to B_jⁱω

^c; and

if ∥

λ

^1(C+1)−

λ

^1c, . . . , λ

^r(C+1)−

λ

^rc∥

₂ is greater than a predefined tolerance, replacing λ

^ic by λ

^i(c+1) and c by c+1 and repeating the two previous steps.

19. The computer readable program storage device of claim 18, the method further comprising setting convex-hull coefficients of negative bags to be 1.

20. The computer readable program storage device of claim 17, wherein Φ

(ω

)=ε

∥

ω

∥

₂² and Ψ

(λ

)=ε

∥

λ

∥

₂², wherein ε

is a positive regularization parameter.

21. The computer readable program storage device of claim 18, the method further comprising transforming said feature samples into a higher dimensional space using a kernel transformation (X{+}, X) for the positive class and K(X{−

}, X) for the negative class, wherein X{+}, X{−

}, and X are data matrices for positive, negative and all samples respectively, wherein each row is a sample vector in these matrices, wherein if the size of X is too large, subsampling a random subset from said original feature samples.