Depth information of tissue surfaces and laparoscope poses are crucial for accurate surgical guidance and navigation in Computer Assisted Surgeries (CAS). Intra-operative Three Dimensional (3D) reconstruction and laparoscope localization are therefore two fundamental tasks in CAS. This dissertation focuses on the abdominal Minimally Invasive Surgeries (MIS) and presents laparoscopic-video-based methods for these two tasks. Different kinds of methods have been presented to recover 3D surface structures of surgical scenes in MIS. Those methods are mainly based on laser, structured light, time-of-flight cameras, and video cameras. Among them, laparoscopic-video-based surface reconstruction techniques have many significant advantages. Specifically, they are non-invasive, provide intra-operative information, and do not introduce extra-hardware to the current surgical platform. On the other side, laparoscopic-video-based 3D reconstruction and laparoscope localization are challenging tasks due to the specialties of the abdominal imaging environment. The well-known difficulties include: low texture, homogeneous areas, tissue deformations, and so on. The goal of this dissertation is to design novel 3D reconstruction and laparoscope localization methods and overcome those challenges from the abdominal imaging environment. Two novel methods are proposed to achieve accurate 3D reconstruction for MIS. The first method is based on the detection of distinctive image features, which is difficult in MIS images due to the low-texture and homogeneous tissue surfaces. To overcome this problem, this dissertation first introduces new types of image features for MIS images based on blood vessels on tissue surfaces and designs novel methods to efficiently detect them. After vessel features have been detected, novel methods are presented to match them in stereo images and 3D vessels can be recovered for each frame. Those 3D vessels from different views are integrated together to obtain a global 3D vessel network and Poisson reconstruction is applied to achieve large-area dense surface reconstruction. The second method is texture-independent and does not rely on the detection of image features. Instead, it proposes to mount a single-point light source on the abdominal wall. Shadows are cast on tissue surfaces when surgical instruments are waving in front of the light. Shadow boundaries are detected and matched in stereo images to recover the depth information. The recovered 3D shadow curves are interpolated to achieve dense reconstruction of tissue surfaces. One novel stereoscope localization method is designed specifically for the abdominal environment. The method relies on RANdom SAmple Consensus (RANSAC) to differentiate rigid points and deforming points. Since no assumption is made on the tissue deformations, the proposed methods is able to handle general tissue deformations and achieve accurate laparoscope localization results in the abdominal MIS environment. With the stereoscope localization results and the large-area dense surface reconstruction, a new scene visualization system, periphery augmented system, is designed to augment the peripheral areas of the original video so that surgeons can have a larger field of view. A user-evaluation system is designed to compare the periphery augmented system with the original MIS video. 30 subjects including 4 surgeons specialized in abdominal MIS participate the evaluation and a numerical measure is defined to represent their understanding of surgical scenes. T-test is performed on the numerical errors and the null hypothesis that the periphery augmented system and the original video have the same mean of errors is rejected. In other words, the results validate that the periphery augmented system improves users' understanding and awareness of surgical scenes.