Giter Site home page Giter Site logo

ghash's Introduction

ghash

ghash generates fuzzy hashes from images. That is, it generates similar hashes for perceptually similar images.

Usage

ghash makes use of features from sharp requiring libvips v7.42.0+.

Overview

Generate a 64-bit hash (Buffer) from a local file in the form of a Promise:

ghash('path/to/image.jpg')
  .calculate()
  .then(function (hash) {
      console.log(hash.toString('hex'));
  });

Generate a hash from an image stored in a Buffer, using a callback:

ghash(imageBuffer).calculate(function (err, hash) {
    if (!err) console.log(hash.toString('hex'));
});

Specify resolution and fuzziness:

ghash('path/to/image.jpg')
  .resolution(4)
  .fuzziness(10)
  .calculate();

Options

Resolution

Valid values are in the range [2-8], inclusive. ghash always generates a 64-bit Buffer, but depending on resolution, not all bits are utilized. The default resolution is 8, utilizing all 64 bits. Smaller resolutions increase fuzziness (see Supplemental).

Fuzziness

Valid values are in the range [0-255], inclusive. The default fuzziness value is 0. Increasing this value increases fuzziness (see Supplemental).

Supplemental

Why ghash?

  • ghash is simple (see Internals).
  • ghash works well for tiny images.
    • pHash, which is fantastic, doesn't work well for tiny images in my experience. Even for 4x4-pixel images that are nearly perceptually identical, pHash generates vastly different hashes. Theoretically, ghash could synergize nicely with pHash.
  • ghash's "fuzziness" can be tuned (see Hash Characteristics).
    • For instance, similar input images can be reduced to identical "archetypes" (potentially useful for similarity search space reduction). In its current form, ghash generates too few hash collisions to reliably "bucket" images into archetypal hashes. This makes it unsuitable for similarity search space reduction. See this study for details.
  • ghash is fairly resilient to various attacks (see Resilience).

Hash Characteristics

Following are the results of running ghash (via included hash_profile.js) against various attacks on an input image (see test/sample) at various resolution and fuzziness values.

Numbered columns indicate Hamming distance from the original image's hash value at respective resolutions (8, 4, 3).

fuzziness = 0

    Input                            8       4       3
    --------------------------------------------------
    orig                             0       0       0
    attacked-compressed              0       1       0
    attacked-color-curved            0       0       0
    attacked-grayscale               1       0       0
    attacked-contrast                1       1       0
    attacked-gamma                   1       1       0
    attacked-noise                   0       1       0
    attacked-gaussian-blur           1       1       0
    attacked-scaled                  1       1       0
    attacked-new-feature             2       2       0
    attacked-padded                  33      8       3
    attacked-sheared                 10      2       0
    attacked-crop-centered           17      10      2
    attacked-rotated                 27      7       2
    control                          38      13      6

fuzziness = 5

    Input                            8       4       3
    --------------------------------------------------
    orig                             0       0       0
    attacked-compressed              0       0       0
    attacked-color-curved            2       1       0
    attacked-grayscale               0       0       0
    attacked-contrast                2       2       0
    attacked-gamma                   3       0       1
    attacked-noise                   0       1       0
    attacked-gaussian-blur           0       0       0
    attacked-scaled                  0       0       0
    attacked-new-feature             2       1       0
    attacked-padded                  34      8       3
    attacked-sheared                 12      1       0
    attacked-crop-centered           17      11      3
    attacked-rotated                 21      4       3
    control                          35      9       5

fuzziness = 10

    Input                            8       4       3
    --------------------------------------------------
    orig                             0       0       0
    attacked-compressed              0       0       0
    attacked-color-curved            2       0       0
    attacked-grayscale               1       0       0
    attacked-contrast                0       0       0
    attacked-gamma                   2       0       0
    attacked-noise                   0       0       0
    attacked-gaussian-blur           0       0       0
    attacked-scaled                  0       0       0
    attacked-new-feature             1       0       0
    attacked-padded                  29      6       3
    attacked-sheared                 7       1       0
    attacked-crop-centered           14      9       2
    attacked-rotated                 13      4       4
    control                          27      8       5

As you can see, decreasing the resolution or increasing the fuzziness value tends to generate more hash collisions--that is, Hamming distances of 0 (though not monotonically). This is important for eliminating false negatives in a similarity search, for instance.

Resilience

Going by the above results...

  • ghash is resilient to the following attacks...
    • Compression
    • Color curving
    • Contrast/gamma adjustment
    • Noise
    • Gaussian blurring
    • Grayscale conversion
    • Scaling
  • ghash has some resilience to...
    • Small feature changes
    • Slight shearing
  • ghash has virtually no resilience to...
    • Padding
    • Cropping
    • Rotation

Internals

ghash works in two stages.

1. Image preprocessing

This involves two steps: conversion to grayscale, and down-scaling.

ghash converts to grayscale not only to simplify the algorithm, but because human sight relies almost entirely on luminance to recognize images.

Downscaling is necessary to compress the hash to 64 bits or less. The resolution value determines the final size of the downsized image.

2. Hash calculation via luminance gradient

Now that ghash has a preprocessed image, it can begin calculating the hash value. It does so by calculating the difference in luminance between every pixel in the image and its immediate neighbor. If the neighboring pixel is "brighter" by some threshold (the fuzziness value), the corresponding bit in the output buffer is set to 1, otherwise 0.

By examining these "deltas", the algorithm is essentially performing edge-detection, the basis of image recognition. A higher fuzziness value equates to a higher edge-detection threshold.

Caveats

  • The above results are not scientific. The sample size used to explore ghash is too small to form serious conclusions. See this study for more comprehensive coverage.

  • If ghash is used for search-space reduction, even a single false negative is bad. False positives are okay. This means you should tune aggressively for minimizing false negatives, even at the expense of increasing false positives. Elimination of all false negatives cannot be guaranteed. :(

  • Because ghash uses sharp/libvips to preprocess images, changes to either library may result in tiny changes to the hashes produced.

  • Because of ghash's simplicity, it has the potential to be lightning-fast. This implementation is slow. Ideally, ghash would be a native, multithreaded library.

ghash's People

Contributors

skedastik avatar dzcpy avatar

Watchers

James Cloos avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.