Precise segmentation of the vertebrae is often required for automaticdetection of vertebral abnormalities. This especially enables incidentaldetection of abnormalities such as compression fractures in images that wereacquired for other diagnostic purposes. While many CT and MR scans of the chestand abdomen cover a section of the spine, they often do not cover the entirespine. Additionally, the first and last visible vertebrae are likely onlypartially included in such scans. In this paper, we therefore approach vertebrasegmentation as an instance segmentation problem. A fully convolutional neuralnetwork is combined with an instance memory that retains information aboutalready segmented vertebrae. This network iteratively analyzes image patches,using the instance memory to search for and segment the first not yet segmentedvertebra. At the same time, each vertebra is classified as completely orpartially visible, so that partially visible vertebrae can be excluded fromfurther analyses. We evaluated this method on spine CT scans from a vertebrasegmentation challenge and on low-dose chest CT scans. The method achieved anaverage Dice score of 95.8% and 92.1%, respectively, and a mean absolutesurface distance of 0.194 mm and 0.344 mm.