Fast Near-Duplicate Image Search and Delete using pHash, t-SNE and KDTree.
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.
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.
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.
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).
| Scape | Search | Insert | Delete |
|---|---|---|---|
| O(n) | O(log n) | O(log n) | O(log n) |
where n is the number of points.
Check INSTALL.md for installation instructions.
Install Python3 and virtualenv see Option 2 in INSTALL.md
make allmake setup-envmake export_envmake testmake cleanmake checkwhich pip3 and which python3 points to the right path.make lintmake packageNote: Run Setup as your init command (or after Clean)
<command> delete or show or search.--images-path /path/to/images/The Directory containing images.--output-path /path/to/output/The Directory containing results.-q /path/to/image/, --query /path/to/image/Path to the query image--tree-type {KDTree,cKDTree}--leaf-size LEAF_SIZELeaf size of the tree.--hash-algorithm {average_hash,dhash,phash,whash}Hash algorithm to use.--hash-size HASH_SIZEHash size to use.-d {euclidean,l2,minkowski,p,manhattan,cityblock,l1,chebyshev,infinity}, --distance-metric {euclidean,l2,minkowski,p,manhattan,cityblock,l1,chebyshev,infinity}Distance metric to use--nearest-neighbors NEAREST_NEIGHBORS# of nearest neighbors.--threshold THRESHOLDThreshold.--parallel [parallel]Whether to parallelize the computation.--batch-size BATCH_SIZEThe batch size is used when parallel is set to true.--backup-keep [BACKUP_KEEP]Whether to save the image to keep into a folder.--backup-duplicate [BACKUP_DUPLICATE]Whether to save the duplicates into a folder.--safe-deletion [SAFE_DELETION]Whether to execute the deletion without reallydeleting nothing.--image-w IMAGE_W The source image is resized down to or up to thespecified size.--image-h IMAGE_H The source image is resized down to or up to thespecified size.
$ deduplication delete --images_path <target_dir> --output_path <output_dir> --tree_type KDTree
For example:
delete \--images-path datasets/potatoes_multi_folder \--output-path outputs \--tree-type KDTree \--threshold 40 \--parallel y \--nearest-neighbors 5 \--hash-algorithm phash \--hash-size 8 \--distance-metric manhattan \--backup-keep y \--backup-duplicate y \--safe-deletion y \
Building the dataset...Parallel mode has been enabled...CPU: 16delegate work...100%|██████████| 1/1 [00:00<00:00, 2231.01it/s]get the results...100%|██████████| 1/1 [00:00<00:00, 773.57it/s]Building the KDTree...Finding duplicates and/or near duplicates...Max distance: 33.0Min distance: 0.0number of files to remove: 28number of files to keep: 428 duplicates or near duplicates has been founded in 0.0027272701263427734 secondsWe have found 28/32 duplicates in folderBackuping images...100%|██████████| 28/28 [00:00<00:00, 4087.45it/s]
$ deduplication search \--images_path <target_dir> \--output_path <output_dir> \--query <specify a query image file>
For example:
$ deduplication search \--images-path datasets/potatoes \--output-path outputs \--tree-type KDTree \--threshold 40 \--parallel f \--nearest-neighbors 5 \--hash-algorithm phash \--hash-size 8 \--distance-metric manhattan \--query datasets/potatoes/2018-12-11-15-031193.png
$ deduplication show --images_path <target_dir> --output_path <output_dir>
For example:
$ show--images-path datasets/potatoes \--output-path outputs \--parallel y \--image-w 32 \--image-h 32
