Documentation ¶
Overview ¶
Package duplo provides tools to efficiently query large sets of images for visual duplicates. The technique is based on the paper "Fast Multiresolution Image Querying" by Charles E. Jacobs, Adam Finkelstein, and David H. Salesin, with a few modifications and additions, such as the addition of a width to height ratio, the dHash metric by Dr. Neal Krawetz as well as some histogram-based metrics.
Quering the data structure will return a list of potential matches, sorted by the score described in the main paper. The user can make searching for duplicates stricter, however, by filtering based on the additional metrics.
Example ¶
Package example.
// Create some example JPEG images. addA, _ := jpeg.Decode(base64.NewDecoder(base64.StdEncoding, strings.NewReader(imgA))) addB, _ := jpeg.Decode(base64.NewDecoder(base64.StdEncoding, strings.NewReader(imgB))) query, _ := jpeg.Decode(base64.NewDecoder(base64.StdEncoding, strings.NewReader(imgC))) // Create the store. store := New() // Turn two images into hashes and add them to the store. hashA, _ := CreateHash(addA) hashB, _ := CreateHash(addB) store.Add("imgA", hashA) store.Add("imgB", hashB) // Query the store for our third image (which is most similar to "imgA"). queryHash, _ := CreateHash(query) matches := store.Query(queryHash) fmt.Println(matches[0].ID)
Output: imgA
Index ¶
- Constants
- Variables
- type Hash
- type Match
- type Matches
- type Store
- func (store *Store) Add(id interface{}, hash Hash)
- func (store *Store) Delete(id interface{})
- func (store *Store) Exchange(oldID, newID interface{}) error
- func (store *Store) GobDecode(from []byte) error
- func (store *Store) GobEncode() ([]byte, error)
- func (store *Store) Has(id interface{}) bool
- func (store *Store) IDs() (ids []interface{})
- func (store *Store) Modified() bool
- func (store *Store) Query(hash Hash) Matches
- func (store *Store) Size() int
Examples ¶
Constants ¶
const ( // ImageScale is the width and height to which images are resized before they // are being processed. ImageScale = 128 )
Variables ¶
var ( // TopCoefs is the number of top coefficients (per colour channel), ordered // by absolute value, that will be kept. Coefficients that rank lower will // be discarded. Change this only once when the package is initialized. TopCoefs = 40 )
Functions ¶
This section is empty.
Types ¶
type Hash ¶
type Hash struct { haar.Matrix // Thresholds contains the coefficient threholds. If you discard all // coefficients with abs(coef) < threshold, you end up with TopCoefs // coefficients. Thresholds haar.Coef // Ratio is image width / image height or 0 if height is 0. Ratio float64 // DHash is a 128 bit vector where each bit value depends on the monotonicity // of two adjacent pixels. The first 64 bits are based on a 8x8 version of // the Y colour channel. The other two 32 bits are each based on a 8x4 version // of the Cb, and Cr colour channel, respectively. DHash [2]uint64 // Histogram is histogram quantized into 64 bits (32 for Y and 16 each for // Cb and Cr). A bit is set to 1 if the intensity's occurence count is large // than the median (for that colour channel) and set to 0 otherwise. Histogram uint64 // HistoMax is the maximum value of the histogram (for each channel Y, Cb, // and Cr). HistoMax [3]float32 }
Hash represents the visual hash of an image.
type Match ¶
type Match struct { // The ID of the matched image, as specified in the pool.Add() function. ID interface{} // The score calculated during the similarity query. The lower, the better // the match. Score float64 // The absolute difference between the two image ratios' log values. RatioDiff float64 // The hamming distance between the two dHash bit vectors. DHashDistance int // The hamming distance between the two histogram bit vectors. HistogramDistance int }
Match represents an image matched by a similarity query.
type Store ¶
Store is a data structure that holds references to images. It holds visual hashes and references to the images but the images themselves are not held in the data structure.
A general limit to the store is that it can hold no more than 4,294,967,295 images. This is to save RAM space but may be easy to extend by modifying its data structures to hold uint64 indices instead of uint32 indices.
Store's methods are concurrency safe. Store implements the GobDecoder and GobEncoder interfaces.
func (*Store) Add ¶
Add adds an image (via its hash) to the store. The provided ID is the value that will be returned as the result of a similarity query. If an ID is already in the store, it is not added again.
func (*Store) Delete ¶
func (store *Store) Delete(id interface{})
Delete removes an image from the store so it will not be returned during a query anymore. Note that the candidate slot still remains occupied but its index will be removed from all index lists. This also means that Size() will not decrease. This is an expensive operation. If the provided ID could not be found, nothing happens.
func (*Store) Exchange ¶
Exchange exchanges the ID of an image for a new one. If the old ID could not be found, nothing happens. If the new ID already existed prior to the exchange, an error is returned.
func (*Store) GobDecode ¶
GobDecode reconstructs the store from a binary representation. You may need to register any types that you put into the store in order for them to be decoded successfully. Example:
gob.Register(YourType{})
func (*Store) IDs ¶
func (store *Store) IDs() (ids []interface{})
IDs returns a list of IDs of all images contained in the store. This list is created during the call so it may be modified without affecting the store.
func (*Store) Modified ¶
Modified indicates whether this store has been modified since it was loaded or created.