The goal of this research is to investigate and develop discrete optimization algorithms for problems of clustering, pattern recognition, data mining and image processing. The research will address the theory and practice of such discrete optimization techniques, and will compare them to traditional approaches including variational models, spectral analysis, support vector machines and Principal Component Analysis. Algorithms will be implemented and their practical performance will be evaluated in applications of medical imaging; security detection; and image segmentation. The theoretical analysis will address the performance of algorithms for several clustering problems, which cannot be solved efficiently and optimally. For such known hard problems the performance will be evaluated in terms of how close the solutions attained are to the optimum, or the worst case error ratio. Efficient implementations will be developed to solve quickly pattern recognition and clustering problems on a sequence of data-sets that differ slightly from each other (e.g. for dynamically changing images, as in video).

The results of this research are expected to improve automated or semi-automated methodologies for pattern recognition, image segmentation, clustering and co-segmentation. The anticipated benefits include the reduction in cost and the frequency of human error in image analysis. In particular, automatic identification of unusual or pathological features is expected to improve diagnosis and reduce the cost of evaluating medical images by introducing accurate and fast automated procedures. The high speed of the proposed methodologies will permit real time deployment and mayl contribute to speeding up the rate of research and development in health-care, biological sciences and homeland security applications.

Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
University of Southern California
Los Angeles
United States
Zip Code