README
¶
Find similar images with Go ➔ LATEST version
Near duplicates and resized images can be found with the package.
Demo: similar image clustering (deployed from).
Semantic versions:
All versions will be kept available indefinitely.
Release note (v3): (1) Hashes get proper "hashy" meaning. If you work with millions of images, do preliminary image comparison with hash tables. (2) Renamed functions. What used to be Hash now becomes Icon to reflect (1).
Key functions
Func Similar gives a verdict whether 2 images are similar with well-tested default thresholds.
Func EucMetric can be used instead, when you need different precision or want to sort by similarity. Func PropMetric can be used for customization of image proportion threshold.
Func Open supports JPEG, PNG and GIF. But other image types are possible through third-party libraries, because func Icon input is image.Image.
For search in billions of images, use a hash table for preliminary filtering (see the 2nd example below).
Go doc for code reference.
The only dependency is my hyper package, which in turn does not have any dependencies. If you are not using hashes, you can remove this dependency by deleting files [hashes.go, hashes_test.go] from your fork.
Example of comparing 2 photos with func Similar
package main
import (
"fmt"
"github.com/vitali-fedulov/images3"
)
func main() {
// Photos to compare.
path1 := "1.jpg"
path2 := "2.jpg"
// Open photos (ignoring errors here).
img1, _ := images3.Open(path1)
img2, _ := images3.Open(path2)
// Icons are compact image representations.
icon1 := images3.Icon(img1, path1)
icon2 := images3.Icon(img2, path2)
// Comparison.
if images3.Similar(icon1, icon2) {
fmt.Println("Images are similar.")
} else {
fmt.Println("Images are distinct.")
}
}
Algorithm
Detailed explanation, also as a PDF.
Summary: Images are resized in a special way to squares of fixed size called "icons". Euclidean distance between the icons is used to give the similarity verdict. Also image proportions are used to avoid matching images of distinct shape.
Customization suggestions
To increase precision you can either use your own thresholds in func EucMetric (and PropMetric) OR generate icons for image sub-regions and compare those icons.
To speedup file processing you may want to generate icons for available image thumbnails. Specifically, many JPEG images contain EXIF thumbnails, you could considerably speedup the reads by using decoded thumbnails to feed into func Icon. External packages to read thumbnails: 1 and 2. A note of caution: in rare cases there could be issues with thumbnails not matching image content. EXIF standard specification: 1 and 2.
Example of comparing 2 photos using hashes
Hash-based comparison provides fast and RAM-friendly rough approximation of image similarity, when you need to process millions of images. After matching hashes use func Similar to get the final verdict. The demo shows only the hash-based similarity testing in its simplified form (without using actual hash table).
package main
import (
"fmt"
"github.com/vitali-fedulov/images3"
)
func main() {
// Paths to photos.
path1 := "1.jpg"
path2 := "2.jpg"
// Hyper space parameters.
epsPct := 0.25
numBuckets := 4
// Open photos (skipping error handling for clarity).
img1, _ := images3.Open(path1)
img2, _ := images3.Open(path2)
// Make icons. They are image representations for comparison.
icon1 := images3.Icon(img1, path1)
icon2 := images3.Icon(img2, path2)
// Hash table values.
// Value to save to the hash table as a key with corresponding
// image ids. Table structure: map[centralHash][]imageId.
// imageId is simply an image number in a directory tree.
centralHash := images3.CentralHash(
icon1, images3.HyperPoints10, epsPct, numBuckets)
// Hash set to be used as a query to the hash table. Each hash from
// the hashSet has to be checked against the hash table.
// See more info in the package "hyper" README.
hashSet := images3.HashSet(
icon2, images3.HyperPoints10, epsPct, numBuckets)
// Checking hash matches. In full implementation this will
// be done on the hash table map[centralHash][]imageId.
foundSimilarImage := false
for _, hash := range hashSet {
if centralHash == hash {
foundSimilarImage = true
break
}
}
// Image comparison result.
if foundSimilarImage {
fmt.Println("Images are similar.")
} else {
fmt.Println("Images are distinct.")
}
}
Documentation
¶
Index ¶
- Variables
- func CentralHash(icon IconT, hyperPoints []Point, epsPercent float64, numBuckets int) uint64
- func CustomPoints(n int) map[Point]bool
- func EucMetric(iconA, iconB IconT) (m1, m2, m3 float32)
- func HashSet(icon IconT, hyperPoints []Point, epsPercent float64, numBuckets int) []uint64
- func Open(path string) (img image.Image, err error)
- func PropMetric(iconA, iconB IconT) (m float64)
- func ResizeByNearest(src image.Image, dstX, dstY int) (dst image.RGBA, srcX, srcY int)
- func SaveToJPG(img *image.RGBA, path string, quality int)
- func SaveToPNG(img *image.RGBA, path string)
- func Similar(iconA, iconB IconT) bool
- type IconT
- type Point
Constants ¶
This section is empty.
Variables ¶
var HyperPoints10 = []Point{
{2, 5}, {3, 3}, {3, 8}, {4, 6}, {5, 2},
{6, 4}, {6, 7}, {8, 2}, {8, 5}, {8, 8}}
HyperPoints10 is a convenience 10-point predefined set with coordinates of icon values to become 10 dimensions needed for hash generation with package "hyper". The 10 points are the only pixels from an icon to be used for hash generation (unless you define your own set of hyper points with CustomPoints function, or manually. The 10 points have been modified manually a little to avoid texture-like symmetries.
Functions ¶
func CentralHash ¶
CentralHash generates a central hash for a given icon by sampling luma values at well-distributed icon points (hyperPoints, HyperPoints10) and later using package "hyper". This hash can then be used for a record or a query. When used for a record, you will need a hash set made with func HashSet for a query. And vice versa. To better understand CentralHash, read the following doc: https://vitali-fedulov.github.io/algorithm-for-hashing-high-dimensional-float-vectors.html
func CustomPoints ¶
CustomPoints is a utility function to create hyper points similar to HyperPoints10. It is needed if you are planning to use the package with billions of images, and might need higher number of sample points (more dimensions). You may also decide to reduce number of dimensions in order to reduce number of hashes per image. In both cases CustomPoints will help generate point sets similar to HyperPoints10. The function chooses a set of points (pixels from Icon) placed apart as far as possible from each other to increase variable independence. Number of chosen points corresponds to the number of dimensions n. Brightness values at those points represent one coordinate each in n-dimensional space for hash generation with package "hyper". Final point patterns are somewhat irregular, which is good to avoid occasional mutual pixel dependence of textures in images. For cases of low n, to avoid texture-like symmetries and visible patterns, it is recommended to slightly modify point positions manually, and with that distribute points irregularly across the Icon.
func EucMetric ¶
EucMetric returns Euclidean distances between 2 icons. These are 3 metrics corresponding to each color channel. The distances are squared to avoid square root calculations. Note that the channels are not RGB, but YCbCr, thus their importance for similarity might be not the same.
func HashSet ¶
HashSet generates a hash set for a given icon by sampling luma values of well-distributed icon points (hyperPoints, HyperPoints10) and later using package "hyper". This hash set can then be used for records or a query. When used for a query, you will need a hash made with func CentralHash as a record. And vice versa. To better understand HashSet, read the following doc: https://vitali-fedulov.github.io/algorithm-for-hashing-high-dimensional-float-vectors.html
func PropMetric ¶
PropMetric gives image proportion similarity metric for image A and B. The smaller the metric the more similar are images by their x-y size.
func ResizeByNearest ¶ added in v1.0.7
ResizeByNearest resizes an image by the nearest neighbour method to the output size outX, outY. It also returns the size inX, inY of the input image.
Types ¶
type IconT ¶
type IconT struct {
Pixels []float32
ImgSize Point // Original image size.
Path string // Original image path.
}
Icon has square shape. Its pixels are float32 values for 3 channels. Float32 is intentional to preserve color relationships from the full-size image.
func EmptyIcon ¶
func EmptyIcon() (icon IconT)
EmptyIcon is an icon constructor in case you need an icon with nil values, for example for convenient error handling. Then you can use icon.Pixels == nil condition.
Source Files