Minimally invasive surgery (MIS) offers great benefits to patients compared with open surgery. Nevertheless during MIS surgeons often need to contend with a narrow field-of-view of the endoscope and obstruction from other surgical instruments. He/she may also need to relate the surgical scene to information derived from previously acquired 3D medical imaging. We thus present a new framework to reconstruct the 3D surface of an internal organ from endoscopic images which is robust to measurement noise, missing data and outliers. This can provide 3D surface with a wide field-of-view for surgeons, and it can also be used for 3D-3D registration of the anatomy to pre-operative CT/MRI data for use in image guided interventions. Our proposed method first removes most of the outliers using an outlier removal method that is based on the trilinear constraints over three images. Then data that are missing from one or more of the video images (missing data) and 3D structure are recovered using the structure from motion (SFM) technique. Evolutionary agents are applied to improve both the efficiency of data recovery and robustness to outliers. Furthermore, an incremental bundle adjustment strategy is used to refine the camera parameters and 3D structure and produce a more accurate 3D surface. Experimental results with synthetic data show that the method is able to reconstruct surfaces in the presence of feature tracking errors (up to 5 pixel standard deviation) and a large amount of missing data (up to 50%). Experiments on a realistic phantom model and in vivo data further demonstrate the good performance of the proposed approach in terms of accuracy (1.7 mm residual phantom surface error) and robustness (50% missing data rate, and 20% outliers in in vivo experiments). (C) 2010 Elsevier B.V. All rights reserved.