In vivo studies of the relationships that exist among vascular geometry, plaque morphology, and hemodynamics have recently been made possible through the development of a system that accurately reconstructs coronary arteries imaged by x-ray angiography and intravascular ultrasound (IVUS) in three dimensions. Currently, the bottleneck of the system is the segmentation of the IVUS images. It is well known that IVUS images contain numerous artifacts from various sources. Previous attempts to create automated IVUS segmentation systems have suffered from either a cost function that does not include enough information, or from a non-optimal segmentation algorithm. The approach presented in this paper seeks to strengthen both of those weaknesses -- first by building a robust, knowledge-based cost function, and then by using a fully optimal, three-dimensional segmentation algorithm. The cost function contains three categories of information: a compendium of learned border patterns, information theoretic and statistical properties related to the imaging physics, and local image features. By combining these criteria in an optimal way, weaknesses associated with cost functions that only try to optimize a single criterion are minimized. This cost function is then used as the input to a fully optimal, three-dimensional, graph search-based segmentation algorithm. The resulting system has been validated against a set of manually traced IVUS image sets. Results did not show any bias, with a mean unsigned luminal border positioning error of 0.180 ± 0.027 mm and an adventitial border positioning error of 0.200 ± 0.069 mm.