Computer aided detection via asymmetric cascade of sparse hyperplane classifiers

ABSTRACT

This paper describes a novel classification method for computer aided detection (CAD) that identifies structures of interest from medical images. CAD problems are challenging largely due to the following three characteristics. Typical CAD training data sets are large and extremely unbalanced between positive and negative classes. When searching for descriptive features, researchers often deploy a large set of experimental features, which consequently introduces irrelevant and redundant features. Finally, a CAD system has to satisfy stringent real-time requirements.This work is distinguished by three key contributions. The first is a cascade classification approach which is able to tackle all the above difficulties in a unified framework by employing an asymmetric cascade of sparse classifiers each trained to achieve high detection sensitivity and satisfactory false positive rates. The second is the incorporation of feature computational costs in a linear program formulation that allows the feature selection process to take into account different evaluation costs of various features. The third is a boosting algorithm derived from column generation optimization to effectively solve the proposed cascade linear programs.We apply the proposed approach to the problem of detecting lung nodules from helical multi-slice CT images. Our approach demonstrates superior performance in comparison against support vector machines, linear discriminant analysis and cascade AdaBoost. Especially, the resulting detection system is significantly sped up with our approach.

REFERENCES

• 1: S. G. Armato-III, M. L. Giger, and H. MacMahon. Automated detection of lung nodules in CT scans: preliminary results. Medical Physics, 28 (8):1552--1561, 2001.
• 2: S. G. Armato-III, M. B. Altman, J. Wilkie, S. Sone, F. Li, K. Doi and A. S. Roy. Automated lung nodule classification following automated nodule detection on CT: a serial approach. Medical Physics, 30(6):1188--1197, 2003.
• 3: M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. John Wiley & Sons, Inc., New York, NY, 1993.
• 4: Kristin P. Bennett, Combining support vector and mathematical programming methods for classification, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 5: Kristin P. Bennet , Ayhan Demiriz , John Shawe-Taylor, A Column Generation Algorithm For Boosting, Proceedings of the Seventeenth International Conference on Machine Learning, p.65-72, June 29-July 02, 2000
• 6: Jinbo Bi , Tong Zhang , Kristin P. Bennett, Column-generation boosting methods for mixture of kernels, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014113]
• 7: S. Buchbinder, I. Leichter, R. Lederman, B. Novak, P. Bamberger, M. Sklair-Levy, G. Yarmish, and S. Fields. Computer-aided classification of BI-RADS category 3 breast lesions. Radiology, 230:820--823, 2004.
• 8: M. Dundar, G. Fung, L. Bogoni, M. Macari, A. Megibow, and B. Rao. A methodology for training and validating a CAD system and potential pitfalls. In Proceedings of CARS 2004 Computer Assisted Radiology and Surgery, 2004.
• 9: Andras Ferencz , Erik G. Learned-Miller , Jitendra Malik, Building a Classification Cascade for Visual Identification from One Example, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.286-293, October 17-20, 2005 [doi>10.1109/ICCV.2005.52]
• 10: Yoav Freund , Robert E. Schapire, Game theory, on-line prediction and boosting, Proceedings of the ninth annual conference on Computational learning theory, p.325-332, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238163]
• 11: J. Friedman, T. Hastie and R. Tibshirani. Additive logistic regression: A statistical view of boosting. The Annals of Statistics, 38(2):337--374, 2000.
• 12: Xiangsheng Huang , Stan Z. Li , Yangsheng Wang, Learning with Cascade for Classification of Non-Convex Manifolds, Proceedings of the 2004 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW'04) Volume 5, p.66, June 27-July 02, 2004
• 13: J. S. Lin, S. C. Lo, A. Hasegawa, M. T. Freedman, and S. K. Mun. Reduction of false positives in lung nodule detection using a two-level neural classification. IEEE Trans. Med.Imag., 15(2):216--227, 1996.
• 14: J. Lin. Divergence measures based on the Shannon entropy. IEEE Trans. Info. Theory, 37(1):145--151, 1991.
• 15: X. Lu, G. Wei, J. Qian and A. K. Jain. Learning-based pulmonary nodule detection from multislice CT data. In Proceedings of CARS 2004 Computer Assisted Radiology and Surgery, 2004.
• 16: D. P. Naidich, J. P. Ko, and J. Stoechek. Computer aided diagnosis: Impact on nodule detection amongst community level radiologist. A multi-reader study. In Proceedings of CARS 2004 Computer Assisted Radiology and Surgery, pages 902--907, 2004.
• 17: S. G. Nash and A. Sofer. Linear and Nonlinear Programming. McGraw-Hill, New York, NY, 1996.
• 18: K. Okada, D. Comaniciu and A. Krishnan. Robust anisotropic Gaussian fitting for volumetric characterization of pulmonary nodules in multislice CT. IEEE Trans. Med. Imag, 24(3):409--423, 2005.
• 19: J. Roehrig. The promise of CAD in digital mamography. European Journal of Radiology, 31:35--39, 1999.
• 20: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 21: G. Shakhnarovich, P. Viola, and B. Moghaddam. A unified learning framework for real time face detection and classification, 2002.
• 22: X. Tang, Z. Ou, T. Su and P. Zhao. Cascade AdaBoost classifiers with stage features optimization for cellular phone embedded face detection. In Lecture Notes in Computer Science (Advances in Natural Computation), volume 3612, pages 688--695, 2005.
• 23: R. Verschae and J. R. del Solar. A hybrid face detector based on an asymmetrical adaboost cascade detector and a wavelet-bayesian-detector. In Lecture Notes in Computer Science IWANN (1), volume 2686, pages 742--749, 2003.
• 24: Paul Viola , Michael J. Jones, Robust Real-Time Face Detection, International Journal of Computer Vision, v.57 n.2, p.137-154, May 2004 [doi>10.1023/B:VISI.0000013087.49260.fb]
• 25: P. A. Viola and M. J. Jones. Fast and robust classification using asymmetric AdaBoost and a detector cascade. In Advances in Neural Information Processing Systems, volume 14, Cambridge, MA, 2002. MIT Press.
• 26: M. Wolf, A. Krishnan, M. Salganicoff, J. Bi, M. Dundar, G. Fung, J. Stoeckel, S. Periaswamy, H. Shen, P. Herzog, and D. P. Baidich. CAD performance analysis for pulmonary nodule detection on thin-slice MDCT scans. In H. Lemke, K. Inamura, K. Doi, M. Vannier, and A. Farman, editors, Proceedings of CARS 2005 Computer Assisted Radiology and Surgery, pages 1104--1108, 2005.
• 27: H. Zhao and S. Ram. Constrained cascade generalization of decision trees. IEEE Transactions on Knowledge and Data Engineering, 16(6):727--738, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.m Miscellaneous

General Terms:
Algorithms

Keywords:
cascading classification, computer aided detection, mathematical programming, sparse solutions, support vector machines