We have developed a method for lumen centerline detection in individual coronary segments that is based on simultaneous detection of the approximate positions of the left and right coronary borders. This approach emulates that of a clinician who visually identifies the lumen centerline as the midline between the simultaneously-determined left and right borders of the vessel segment of interest. Our lumen centerline detection algorithm and two conventional centerline detection methods were compared to carefully-defined observer-identified centerlines in 89 complex coronary images. Computer-detected and observer-defined centerlines were objectively compared using five indices of centerline position and orientation. The quality of centerlines obtained with the new simultaneous border identification approach and the two conventional centerline detection methods was also subjectively assessed by an experienced cardiologist who was unaware of the analysis method. Our centerline detection method yielded accurate centerlines in the 89 complex images. Moreover, our method outperformed the two conventional methods as judged by all five objective parameters (p < 0.001 for each parameter) and by the subjective assessment of centerline quality (p < 0.001). Automated detection of lumen centerlines based on simultaneous detection of both coronary borders provides improved accuracy in complex coronary arteriograms.