We present a system detecting the presence of man-made objects in unconstrained subsea videos. This represents a significant challenge because nothing is assumed about the possible orientation or location of the objects and because of the generally poor underwater image quality. Classification is based on contours, which are reasonably stable features in underwater imagery. First, the system determines automatically an optimal scale for contour extraction by optimising a quality metric. Second, a classifier determines whether the image contains man-made objects or not. The features used capture general properties of man-made structures using measures inspired by perceptual organisation. Using a Support Vector Machines (SVM) classifier the system classified correctly approximately 77% of the image-frames containing man-made objects belonging to five different underwater videos, in spite of the varying image contents, poor quality and generality of the classification task.