Perceptual Image Similarity with DCT and SIMD

A file digest and a perceptual digest of an image are not the same concept. A cryptographic digest is designed so that even a one-bit change produces a completely different result. A perceptual digest aims to produce close results for two images that have been resized, encoded at different quality levels, or subjected to limited color transformations.

I developed the library I shared for image similarity and fast candidate matching in large datasets within an institutional system. I did not leave the algorithm at an experimental stage. I used it in live systems, tested it on large image collections, and obtained successful results on real data distributions. During this work, I evaluated the mathematical properties of DCT, perceptual hashing methods, and SIMD capabilities on .NET together.

The theoretical line of the library is directly related to the chapter titled "Image and Audio Processing," which I wrote for the book Artificial Intelligence from Theory to Practice, published by Nobel Academic Publishing. In that chapter, I discussed the numerical representation of images, feature extraction, transform spaces, and processing of image data in artificial-intelligence systems. This library turns that theoretical approach into an image-matching component operating at institutional scale. The official publication record lists Muhammet Ali Köker among the authors and confirms ISBN 978-625-427-802-0.

The emergence of DCT

The discrete cosine transform was defined by Nasir Ahmed, T. Raj Natarajan, and K. R. Rao in a study published in 1974. One of its important findings was that DCT could approach the energy-compaction and rate-distortion performance of the Karhunen-Loeve transform, which is theoretically powerful but data-dependent, in image and signal processing. The original paper also pointed directly to applications such as pattern recognition and Wiener filtering.

The lasting success of DCT in image processing does not result only from ease of computation. Neighboring pixels in natural images are usually highly correlated. Pixel values change slowly across broad smooth surfaces, while sharp changes are concentrated more strongly around edges and textured regions. DCT decomposes this spatial regularity into cosine components at different frequencies.

Low frequencies carry overall brightness, broad color transitions, and coarse geometry. High frequencies represent fine edges, small textures, sensor noise, and encoding artifacts more strongly. When a natural image is transformed into DCT space, a substantial part of its energy is concentrated in a limited number of low-frequency coefficients. This energy-compaction property underlies the success of DCT in both compression and similarity analysis.

The one-dimensional orthonormal DCT-II is:

[ X_k=\alpha(k)\sum_{n=0}^{N-1} x_n\cos\left[\frac{\pi}{N}\left(n+\frac{1}{2}\right)k\right] ]

Where:

[ \alpha(0)=\sqrt{\frac{1}{N}} ]

and for other coefficients:

[ \alpha(k)=\sqrt{\frac{2}{N}} ]

The same normalization is visible directly in the implementation I examined. General coefficients are scaled by sqrt(2/N). An additional factor of 1/sqrt(2) is applied to the zero-frequency coefficient. This detail shows that the transform is an orthonormal DCT-II rather than an arbitrary cosine sum.

Historical connection with JPEG

The most widespread use of DCT is JPEG encoding. The JPEG working group was formed in 1986. The foundational JPEG standard was adopted by ITU-T in 1992 and later by ISO/IEC. Defined as T.81 and ISO/IEC 10918-1, the standard established a DCT- and quantization-based pipeline for coding continuous-tone images.

Lossy JPEG encoding generally consists of:

1. Separating the image into color components
2. Reducing color-sampling resolution where necessary
3. Dividing the image into small blocks
4. Applying two-dimensional DCT to each block
5. Quantizing DCT coefficients
6. Encoding the coefficients in a suitable order
7. Entropy coding

DCT itself is not lossy. With sufficient numerical precision, the original samples can be reconstructed through the inverse transform. The primary loss in JPEG occurs during quantization of DCT coefficients. Because the human visual system is less sensitive to fine high-frequency changes than to broad low-frequency structures, high-frequency coefficients are usually quantized more coarsely.

This also explains why DCT-based perceptual hashes are relatively robust against JPEG encoding. JPEG modifies high-frequency details more strongly while preserving low-frequency coefficients carrying overall image structure. Research on JPEG-compatible image hashing has reported that low-frequency DCT coefficients can exhibit strong correlation across similar images.

My implementation likewise uses the low-frequency matrix of the complete image. Unlike JPEG, however, it does not divide the image into 8 x 8 blocks. The image is first reduced to a standard size, and a global DCT is then calculated. The resulting digest therefore represents the general frequency layout of the image rather than local blocks.

Standardizing the image

Perceptual comparison requires two images to be brought into the same spatial representation. If source resolution, aspect ratio, and file format are carried directly into the digest, different copies of the same content may diverge.

The library converts the image into a fixed 64 x 64 working area. Aspect ratio is preserved. Excess width is cropped from the center, or empty space remains at the sides for narrow images. This has two important consequences.

First, computational cost becomes independent of original image resolution. A twelve-megapixel photograph and a small preview are represented by the same number of samples during the DCT stage. Second, a substantial portion of small high-frequency detail is removed during resampling. The algorithm focuses on coarse visual structure rather than file-level differences.

Color pixels are not sent to three separate DCT channels. Channel values are passed through a defined dynamic-range correction and combined into one intensity value. Rather than standard photometric luminance coefficients, the implementation uses a projection close to an equally weighted average of red, green, and blue.

This is not a scientific color-appearance model. It is a practical feature transformation developed for an institutional matching problem. The objective is not to preserve every detail of the color distribution, but to transfer general intensity geometry into DCT space consistently.

Handling channel ranges separately provides additional robustness to brightness and contrast differences. Copies that are lighter, darker, or have a limited color-balance change can produce similar frequency orderings even when their absolute pixel values differ.

Separating the two-dimensional DCT

When calculated directly, every output coefficient of the two-dimensional DCT depends on all input pixels:

[ F(u,v)=\alpha(u)\alpha(v) \sum_{x=0}^{N-1}\sum_{y=0}^{N-1} f(x,y) \cos\left[\frac{(2x+1)u\pi}{2N}\right] \cos\left[\frac{(2y+1)v\pi}{2N}\right] ]

A direct implementation processes N x N input samples for each of N x N output coefficients. General cost is O(N^4).

DCT is separable. A one-dimensional DCT can first be applied to each row, followed by a one-dimensional DCT to the columns of the resulting matrix. The cost of the complete two-dimensional transform is thereby reduced to O(N^3).

The library uses this separability explicitly. Each of the 64 rows is transformed first, followed by the column-direction transform. Because only the upper-left 8 x 8 low-frequency region is required for the perceptual digest, the second stage calculates only the first eight horizontal-frequency columns and the first eight vertical frequencies.

This is an important optimization. A full second pass would produce 64 x 64 output coefficients, while this path produces only 8 x 8. A complete column pass requires 262,144 scalar multiply-add operations, whereas the selected low-frequency pass requires 4,096.

In the examined version, the first row pass calculates all 64 frequencies. The next stage uses only the first eight. This may be related to retaining a general-purpose DCT core or to other paths used during development. If perceptual hashing is the only target, the first pass can also be limited to eight coefficients. Such a change can further reduce total transform cost without altering the result space.

A well-optimized algorithm is not necessarily one that cannot be improved further. The principal engineering achievement here is decomposing the expensive two-dimensional transform, precomputing cosine values, generating only the required coefficients in the second dimension, and executing the hot loop with SIMD.

Precomputing cosine coefficients

Calculating the cosine function inside the DCT inner loop is expensive. For N=64, the coefficients corresponding to every frequency and sample position remain constant throughout execution.

The library calculates these coefficients once when the class is first initialized:

[ C_{k,n}= \cos\left[\frac{(2n+1)k\pi}{2N}\right] ]

All subsequent images use the same coefficient table. The live processing path therefore contains no trigonometric-function call, only multiplication and addition.

The 64 x 64 coefficient table contains 4,096 floating-point values. They are stored in groups of four. For each frequency, there are 16 vectors with four components. The input array is likewise divided into 16 vectors.

One DCT coefficient becomes:

[ X_k=\sum_{i=0}^{15} \operatorname{dot}(P_i,C_{k,i}) ]

Each P_i contains four input samples and each C_{k,i} the corresponding four cosine coefficients.

The SIMD approach

SIMD allows the same operation to be applied to multiple data elements with one instruction. Image processing, matrix calculations, signal processing, and scientific computing naturally benefit from SIMD because they repeat the same arithmetic across large arrays.

Types in .NET System.Numerics can be translated into SIMD instructions on supported processors and JIT environments. Vector4 carries four 32-bit floating-point values in one logical vector. Vector4.Dot produces the dot product of two vectors. Microsoft documentation states that these types can benefit from hardware-accelerated SIMD execution and that acceleration depends on the runtime environment.

A scalar implementation requires 64 separate multiplications and additions for one 64-element DCT coefficient. With groups of four, the hot loop is reduced to 16 vector dot products.

Analysis of the transform counts in the library shows:

• 65,536 Vector4 dot products in the row pass
• 1,024 Vector4 dot products in the selected column pass
• 66,560 vector dot products in total

Because each vector carries four scalar components, this corresponds to approximately 266,240 scalar multiply-add equivalents. SIMD does not only reduce theoretical operation count. Retaining four values in one register aligns loads and arithmetic with the processor's vector execution units.

I did not treat SIMD as a micro-optimization added after implementation. The DCT coefficient layout was designed from the beginning around Vector4 groups. Data structures and processor execution model are part of the same design.

The fixed length of 64 samples also simplifies this approach. There are no tail elements, variable vector lengths, or remainder-processing conditions. Every array divides exactly into 16 vectors. Loop bounds are predictable, and all images follow the same execution path.

Why DCT captures similarity

The success of DCT in similarity analysis does not come merely from moving the image into another coordinate system. It depends on which coefficients are selected and how they are quantized.

The library uses the upper-left 8 x 8 region of the 64 x 64 DCT matrix. This region carries:

• Mean image intensity
• Broad horizontal and vertical transitions
• Large object boundaries
• Overall light-dark distribution
• Coarse composition
• Low-frequency texture

Fine text, dense textures, compression noise, and single-pixel changes remain at higher frequencies. Excluding these coefficients from the digest makes the result more stable against small file-level changes.

Studies of similar DCT perceptual-hash approaches use standard-size reduction, selection of an 8 x 8 low-frequency coefficient region, and construction of a 64-bit value from these coefficients. Experimental work has shown that Hamming distance between perceptually similar images can be lower than between unrelated images.

The library does not store the absolute values of the 64 coefficients. It calculates their median and converts each coefficient into one bit according to whether it is greater than the median:

[ h_i= \begin{cases} 1, & F_i > \operatorname{median}(F)\\ 0, & F_i \leq \operatorname{median}(F) \end{cases} ]

The result is a 64-bit integer.

Using the median is important. The mean can be strongly influenced by outlying coefficients, particularly the DC component. The median represents the relative ordering of frequency coefficients. When overall gain changes, absolute coefficient values can change while their relative greater-than and less-than structure remains largely stable.

The perceptual digest therefore answers the following question:

"Do similar coefficients in the low-frequency structure of these two images remain on the same side of the median?"

This differs from pixel-by-pixel equality. Two coefficients can be numerically different and remain in the same class. A small change alters the bit only when it crosses the median threshold.

Hamming distance and institutional scale

Similarity between two 64-bit digests can be measured with XOR and population count:

[ d_H(a,b)=\operatorname{popcount}(a\oplus b) ]

The result ranges from 0 to 64. Zero indicates identical digests. As the value increases, differences in low-frequency structure increase.

This representation provides an important advantage for institutional systems. Each image is represented by only an eight-byte digest. Excluding database and index overhead, raw digests for one million images occupy approximately eight megabytes. Preliminary comparison of two images requires neither a high-dimensional feature vector nor image decoding.

This compact representation was important in the successful results I obtained in live use. Instead of reopening every image and comparing pixels or deep features across large datasets, DCT hashes could produce a fast candidate set.

The threshold is not universal, however. Acceptable Hamming distance must be determined for the data domain. Document images, face photographs, screenshots, and natural scenes do not have the same distance distribution. The correct threshold should be selected on a validation set containing positive and negative examples.

A linear scan costs O(M) for M records, but each comparison has extremely low fixed cost. At larger scale, the digest can be partitioned by selected bit regions, or multi-index search and approximate-neighborhood structures suitable for Hamming space can be used.

Success domain and limitations

A global DCT-based digest is generally robust against:

• Resolution change
• JPEG quality change
• Limited blurring
• Small amounts of noise
• Brightness and contrast changes
• File-format conversion
• Limited color transformation

It is not naturally invariant to geometric transformations. Large crops, rotation, horizontal flipping, perspective transformation, or substantial movement of an object within the image also change the low-frequency matrix. Comparative studies likewise report this limitation of DCT-based perceptual hashes under broad transformations.

A global digest also does not explain the location of a local change. If a small region is altered, only an increase in digest distance is observed. The location of the change cannot be determined. Local forgery analysis requires an additional layer dividing the image into blocks or using local features.

A perceptual digest must not be used as a cryptographic digest. Producing collisions is part of its design. Different images with the same coarse frequency structure can produce close digests. It provides no security guarantee against an attacker deliberately constructing a misleading image.

Engineering limitations of the examined version

The mathematical hot path of the library is strong in its use of SIMD and precomputation. The examined source, however, accesses images through high-level pixel calls. Because the processed area is fixed at 64 x 64, the number of calls per image is bounded. A modern adaptation could still reduce data-access cost by operating directly on bitmap memory.

The dynamic-range calculation preparing DCT input is performed on a specified region of the original image, while the transform operates on the resized image. This may be consistent with the size and content preconditions of the dataset used in the live system. In a general-purpose library, defining the calibration region explicitly or calculating it from the same sample space as the resized image would be safer.

The expression used is also not a complete min-max normalization. After subtracting the minimum, division uses the maximum value rather than the channel range. This approach may have produced successful results on the target distribution, but it requires protection for channels with zero or very low maxima.

These points do not invalidate the successful institutional use of the algorithm. In real systems, outcomes depend on data distribution, preconditions, and edge-case policies as well as theoretical purity. An academic analysis of the source code should nevertheless distinguish implemented behavior from an ideal generalized model.

From theory to a live system

Image processing, signal processing, and low-level software optimization are combined in one pipeline in this library.

The image is first moved into a standard sample space. Color components are reduced to one intensity array. DCT transfers the image from the spatial domain into the frequency domain. The 64 low-frequency coefficients form coarse structural features. Median quantization converts these features into a 64-bit binary signature. SIMD moves the dense dot-product section of the transform onto the processor's vector units.

This approach matches the central principle I argued in the "Image and Audio Processing" chapter of Artificial Intelligence from Theory to Practice. Artificial intelligence and image analysis are not limited to model training. Representing data in the correct space, eliminating unnecessary detail, and extracting sufficient features at low cost are often decisive parts of the system.

DCT is not merely an old compression component borrowed from JPEG. It is a well-understood and mathematically explainable feature extractor that separates visual structure into frequency components. Preservation of low-frequency organization across similar images makes the transform effective for perceptual comparison.

The SIMD approach is also more than a detail that shortens a few processing loops. Data layout, coefficient precomputation, and the dot-product core are designed together around the processor's execution model. The feature enabling success at institutional scale is the combination of the mathematical model and hardware awareness in the same implementation.

The results I obtained on large datasets showed that a DCT-based perceptual digest is a strong preliminary matching method when used within its proper boundaries. It does not solve every visual problem. In large collections containing resizing, encoding differences, and limited photometric changes, however, it provides extremely fast and effective candidate comparison through an explainable eight-byte digest.