Many industries rely heavily on safe and reliable water traffic. Obstacles below the water line are a significant problem for Marine safety, and therefore need to be continuously monitored, especially in the shallow water, sea ports and harbours. Biologists, on the other hand, are interested in tracking of sea-bed changes, especially as related to flora and fauna, over the course of months, years, and even decades. This illustrates the need for mapping and reconstruction of underwater terrain both in seawater and freshwater environments. This thesis presents one of the possible solutions for the above problems. It consists of an underwater camera, attached to an autonomous boat, which is equipped with position and orientation sensors. From the video captured by a camera pointing downwards, frames are extracted, with criteria based on travelled GPS distance between the two successive frames. Distinctive key points are detected and matched between the successive frames, and using on-board sensors, 3-D points are triangulated to form a point cloud. Extracted point clouds are registered to global positioning grid, using sensor data. Depth accuracy depends heavily on video quality, which, in turn, is proportional to water depth and clarity. Picture quality is assessed with the help of entropy estimation before the frame is sent to processing. If the picture does not contain enough information for a reliable point cloud reconstruction, depth from an on-board single-beam sonar is taken and points for that patch are synthesized based on the measured depth to provide second-best possible estimate of the terrain surface.