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.