The watermarking of digital images has an important role in the protection of digital content with respect to many aspects. In this paper we present a reversible watermarking algorithm for hiding information into medical images having luminance histograms with particular characteristics. Some radiographic images have the property that not all the gray levels are present; this leads to sequences of 0 values (0-runs) in the corresponding histograms. It is possible to use these 0-runs to encode information by modifying pixels having gray levels contiguous to these runs; by encoding also the run information it is possible to restore the original image after extracting the stored data. In this work we present a novel reversible watermarking technique capable of exploiting all the 0-runs in the image histogram to achieve high capacity. We show that an optimization problem arises for those cases in which two or more non-zero frequency gray levels are contiguous to 0-runs. Part of the watermark information may be devoted to a digital signature of the original image, whose authenticity may also be verified by a user. © 2015 Elsevier B.V. All rights reserved.