As one of the crucial problems in watermarking, robustness against geometric distortion and JPEG compression becomes more than challenging and problematic. In this paper, a robust watermarking scheme based on block histogram and gray-level histogram is proposed for gray images. For embedding, the scheme orders the pixel gray-levels and groups the pixels into blocks of dynamic size, each of which has the same number of gray-levels, thus generates the block histogram. According to the block histogram, the Number-KEY and Value-KEY generate. Then the gray-level histogram is modified to form a specially distributed, indicating the embedding bits. For extraction, the watermarked image, the Number-KEY, and the Value-KEY are adopted together to get the watermark bits. Experimental results show that the scheme is highly robust against not only JPEG compression, but also geometric attacks and common signal processing such as median filtering. The comparison results between the proposed scheme and the existing methods indicate its advantages. © 2009 Springer-Verlag Berlin Heidelberg.