项目作者: umbertogriffo

项目描述 :
Fast Near-Duplicate Image Search and Delete using pHash, t-SNE and KDTree.
高级语言: Python
项目地址: git://github.com/umbertogriffo/fast-near-duplicate-image-search.git
创建时间: 2019-04-23T10:24:56Z
项目社区:https://github.com/umbertogriffo/fast-near-duplicate-image-search

开源协议:Apache License 2.0

下载


Fast Near-Duplicate Image Search and Delete

This Python script is a command line tool for visualizing, checking and deleting near-duplicate images from the target directory.
In order to find similar images this script hashes the images using pHash from
ImageHash library,
adding the hash into a KDTree and perform a nearest neighbours search.
In addition, near-duplicate images can be visualized generating a
t-SNE (t-distributed Stochastic Neighbor Embedding)
using a feature vector for each image derived from the pHash function.

I take no responsibility for bugs in this script or accidentally deleted pictures.
Use at your own risk. Make sure you back up your pictures before using.
This algorithm is intended to find nearly duplicate images. It is NOT intended to find images that are conceptually
similar.

Contents

pHash definition

Features in the image are used to generate a distinct (but not unique) fingerprint, and these fingerprints are comparable.
Perceptual hashes are a different concept
compared to cryptographic hash functions like MD5 and SHA1.

phash

With cryptographic hashes, the hash values are random. The data used to generate the hash acts like a random seed,
so the same data will generate the same result, but different data will create different results.
Comparing two SHA1 hash values really only tells you two things.
If the hashes are different, then the data is different.
And if the hashes are the same, then the data is likely the same.
(Since there is a possibility of a hash collision, having the same hash values does not guarantee the same data.)
In contrast, perceptual hashes can be compared giving you a sense of similarity between the two data sets.
Using pHash images can be scaled larger or smaller, have different aspect ratios, and even minor coloring differences
(contrast, brightness, etc.) and they will still match similar images.

KDTree definition

A KDTree(short for k-dimensional tree) is a space-partitioning data structure for organizing
points in a k-dimensional space.
In particular, KDTree helps organize and partition the data points based on specific conditions.
KDTree is a useful for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches).

Complexity (Average)

Scape Search Insert Delete
O(n) O(log n) O(log n) O(log n)

where n is the number of points.

phases

Deletion

delete

Installation

Check INSTALL.md for installation instructions.

How to use the Makefile

Prerequisites

Install Python3 and virtualenv see Option 2 in INSTALL.md

  • All-in-one: make all
    • Setup, test and package.
  • Setup: make setup-env
    • Installs all dependencies.
  • Export dependencies of the environment: make export_env
    • Export a requirements.txt file containing the detailed dependencies of the environment.
  • Test: make test
  • Clean: make clean
    • Removes the environment.
    • Removes all cached files.
  • Check: make check
    • Use It to check that which pip3 and which python3 points to the right path.
  • Lint: make lint
    • Checks PEP8 conformance and code smells using pylint.
  • Package: make package
    • Creates a bundle of software to be installed.

Note: Run Setup as your init command (or after Clean)

Usage

Arguments

  1. <command> delete or show or search.
  2. --images-path /path/to/images/
  3. The Directory containing images.
  4. --output-path /path/to/output/
  5. The Directory containing results.
  6. -q /path/to/image/, --query /path/to/image/
  7. Path to the query image
  8. --tree-type {KDTree,cKDTree}
  9. --leaf-size LEAF_SIZE
  10. Leaf size of the tree.
  11. --hash-algorithm {average_hash,dhash,phash,whash}
  12. Hash algorithm to use.
  13. --hash-size HASH_SIZE
  14. Hash size to use.
  15. -d {euclidean,l2,minkowski,p,manhattan,cityblock,l1,chebyshev,infinity}, --distance-metric {euclidean,l2,minkowski,p,manhattan,cityblock,l1,chebyshev,infinity}
  16. Distance metric to use
  17. --nearest-neighbors NEAREST_NEIGHBORS
  18. # of nearest neighbors.
  19. --threshold THRESHOLD
  20. Threshold.
  21. --parallel [parallel]
  22. Whether to parallelize the computation.
  23. --batch-size BATCH_SIZE
  24. The batch size is used when parallel is set to true.
  25. --backup-keep [BACKUP_KEEP]
  26. Whether to save the image to keep into a folder.
  27. --backup-duplicate [BACKUP_DUPLICATE]
  28. Whether to save the duplicates into a folder.
  29. --safe-deletion [SAFE_DELETION]
  30. Whether to execute the deletion without really
  31. deleting nothing.
  32. --image-w IMAGE_W The source image is resized down to or up to the
  33. specified size.
  34. --image-h IMAGE_H The source image is resized down to or up to the
  35. specified size.

Delete near-duplicate images from the target directory

  1. $ deduplication delete --images_path <target_dir> --output_path <output_dir> --tree_type KDTree

For example:

  1. delete \
  2. --images-path datasets/potatoes_multi_folder \
  3. --output-path outputs \
  4. --tree-type KDTree \
  5. --threshold 40 \
  6. --parallel y \
  7. --nearest-neighbors 5 \
  8. --hash-algorithm phash \
  9. --hash-size 8 \
  10. --distance-metric manhattan \
  11. --backup-keep y \
  12. --backup-duplicate y \
  13. --safe-deletion y \
  1. Building the dataset...
  2. Parallel mode has been enabled...
  3. CPU: 16
  4. delegate work...
  5. 100%|██████████| 1/1 [00:00<00:00, 2231.01it/s]
  6. get the results...
  7. 100%|██████████| 1/1 [00:00<00:00, 773.57it/s]
  8. Building the KDTree...
  9. Finding duplicates and/or near duplicates...
  10. Max distance: 33.0
  11. Min distance: 0.0
  12. number of files to remove: 28
  13. number of files to keep: 4
  14. 28 duplicates or near duplicates has been founded in 0.0027272701263427734 seconds
  15. We have found 28/32 duplicates in folder
  16. Backuping images...
  17. 100%|██████████| 28/28 [00:00<00:00, 4087.45it/s]

Find near-duplicated images from an image you specified

  1. $ deduplication search \
  2. --images_path <target_dir> \
  3. --output_path <output_dir> \
  4. --query <specify a query image file>

For example:

  1. $ deduplication search \
  2. --images-path datasets/potatoes \
  3. --output-path outputs \
  4. --tree-type KDTree \
  5. --threshold 40 \
  6. --parallel f \
  7. --nearest-neighbors 5 \
  8. --hash-algorithm phash \
  9. --hash-size 8 \
  10. --distance-metric manhattan \
  11. --query datasets/potatoes/2018-12-11-15-031193.png

phases

Show near-duplicate images from the target directory With t-SNE

  1. $ deduplication show --images_path <target_dir> --output_path <output_dir>

For example:

  1. $ show
  2. --images-path datasets/potatoes \
  3. --output-path outputs \
  4. --parallel y \
  5. --image-w 32 \
  6. --image-h 32

phases

Todo

References