This paper describes an automatic segmentation algorithm for fish sampled by a trawl-based underwater camera system. To overcome the problem caused by very low brightness contrast between fish and their underwater background with dynamically changing luminance, our proposed algorithm adopts an innovative histogram backprojection procedure on double local-thresholded images to ensure a reliable segmentation on the fish shape boundaries. The thresholded results are further validated by area and variance criteria to remove unwanted objects. Finally, a post-processing step is applied to refine the segmentation. Promising results, as validated by expert-generated ground truth data, were obtained via our proposed algorithm.