![](https://csdnimg.cn/release/download_crawler_static/12011620/bgb.jpg)
• Two hashes are identical if their hamming distance is 0; their maximum possible hamming distance is
256.
• Since each bit of the 16x16 output is a 1 if the corresponding DCT bin exceeds the median DCT value or
not, necessarily each hash has 128 1-bits and 128 0-bits. The only exception is in highly degenerate
images, e.g. solid-color images, where multiple DCT output bins have the exact same numerical value.
(Phrased differently, all non-trivial PDQ hashes have a hamming norm of 128.) In particular, a perfectly
solid-color image has all 256 bits 0, but essentially solid-color images won’t: hence the reason for having a
quality metric to surface these.
• Since hashes have half their bits 0s and half 1s, the maximum number of unique PDQ hashes is not 2
256
but rather 256 choose 128 (still an astronomical number).
• As well, hamming distance between pairs of PDQ hashes is (again, almost) always an even number.
• Statistical distribution of distances will be discussed below. For the moment, let us say that the hamming
distance between random pairs of PDQ hashes averages 128, supported on the range of 90 to 160 or so.
Confident-match distances are up to the system designer, of course, but 30, 20, or less has been found to
produce good results on evaluation data. (We will gain more context for matching-distance thresholds in
the Evaluation section below.)
PDQ ALGORITHM DETAILS
Each step of the above algorithm sketch is now discussed in detail.
LUMINANCE CALCULATION
Luminance is computed as in (https://en.wikipedia.org/wiki/Luminance): namely if R, G, and B are 0-255 unsigned-
byte values then
Y = 0.299 R + 0.587 G + 0.114 B
which is also in the range 0-255. (If floating-point arithmetic is done, 0-255 is fine; for fixed-point arithmetic, say
with 12 mantissa bits, then Y can be stored as integer with the 0.299 et al. coefficients replaced by 0.299 · 2
12
, etc.)
Note that this is distinct from greyscale (an unweighted average of R, G, and B); luminance is preferred since it is
designed to align with visual perception.
JAROSZ FILTERS AND DOWNSAMPLING
PDQ is intended to be robust with respect to light crops or shifts. For this reason, it is important that the
downsample to 64x64 not be a cherry-pick of pixels out of the full-resolution luminance image, but rather an
average over pixels within each image block. As is well-known in the image-processing field, a single ‘box’ filter (i.e.
sliding-window sum) in the X and Y directions done twice produces a tent filter, and done three times produces a
bell filter; eventually this approaches a Gaussian filter. So an implementation of smoothing/filtering decomposes
into box passes, and a count of how many box passes are to be done. Furthermore, as detailed in Jarosz (Jarosz,
2001) the naïve two-dimensional filter can be much more efficiently be done using a pair of one-dimensional
passes. Thus four 1-D passes – X direction, Y direction, X direction, Y direction – produces a 2-D tent filter.
Window sizes: The pHash algorithm, which inspired PDQ, uses 16x16 boxes and 64 output bits. Within those 256
boxes, single pixels are selected using convolution with a mean filter on 7x7-pixel patches. For example, if the input