image - tineye - Búsqueda de imágenes similares por distancia de pHash en Elasticsearch

subir imagen a google

Question

Problema de búsqueda de imagen similar

• Millones de imágenes fueron procesadas y almacenadas en Elasticsearch.
• El formato es "11001101 ... 11" (longitud 64), pero se puede cambiar (mejor no).

Dado el hash de la imagen del sujeto "100111..10", queremos encontrar todos los hashes de imágenes similares en el índice Elasticsearch dentro de una distancia de 8 .

Por supuesto, la consulta puede devolver imágenes con una distancia mayor que 8 y la secuencia de comandos en Elasticsearch o afuera puede filtrar el conjunto de resultados. Pero el tiempo total de búsqueda debe ser dentro de 1 segundo más o menos.

Nuestro mapeo actual

Cada documento tiene un campo de images anidado que contiene hashes de imágenes:

{
"images": {
"type": "nested",
"properties": {
"pHashFingerprint": {"index": "not_analysed", "type": "string"}
}
}
}

Nuestra pobre solución

Hecho: la consulta difusa de Elasticsearch admite la distancia de Levenshtein de máximo 2 solamente.

Usamos tokenizer personalizado para dividir una cadena de 64 bits en 4 grupos de 16 bits y hacer una búsqueda de 4 grupos con cuatro consultas difusas.

Analizador:

{
"analysis": {
"analyzer": {
"split4_fingerprint_analyzer": {
"type": "custom",
"tokenizer": "split4_fingerprint_tokenizer"
}
},
"tokenizer": {
"split4_fingerprint_tokenizer": {
"type": "pattern",
"group": 0,
"pattern": "([01]{16})"
}
}
}
}

Entonces nuevo mapeo de campo:

"index_analyzer": "split4_fingerprint_analyzer",

Luego consulta:

{
"query": {
"filtered": {
"query": {
"nested": {
"path": "images",
"query": {
"bool": {
"minimum_should_match": 2,
"should": [
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "0010100100111001",
"fuzziness": 2
}
}
},
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "1010100100111001",
"fuzziness": 2
}
}
},
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "0110100100111001",
"fuzziness": 2
}
}
},
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "1110100100111001",
"fuzziness": 2
}
}
}
]
}
}
}
},
"filter": {}
}
}
}

Tenga en cuenta que devolvemos documentos que tienen imágenes coincidentes, no las imágenes en sí, pero eso no debería cambiar mucho las cosas.

El problema es que esta consulta devuelve cientos de miles de resultados incluso después de agregar otros filtros específicos del dominio para reducir el conjunto inicial. El script tiene demasiado trabajo para calcular la distancia de nuevo, por lo tanto, la consulta puede llevar minutos.

Como era de esperar, si se aumenta el minimum_should_match a 3 y 4, solo se devuelve un subconjunto de imágenes que deben encontrarse, pero el conjunto resultante es pequeño y rápido. Debajo del 95% de las imágenes necesarias se devuelven con minimum_should_match == 3, pero necesitamos 100% (o 99.9%) como con minimum_should_match == 2.

Intentamos enfoques similares con n-grams, pero aún así no tuvimos mucho éxito de la misma manera que con demasiados resultados.

¿Alguna solución de otras estructuras de datos y consultas?

Editar :

Notamos que había un error en nuestro proceso de evaluación, y minimum_should_match == 2 devuelve el 100% de los resultados. Sin embargo, el tiempo de procesamiento luego toma un promedio de 5 segundos. Veremos si el script vale la pena optimizarlo.

Answer 1

Aquí hay una solución de 64 bits a @NikoNyrh''s respuesta de @NikoNyrh''s . La distancia de Hamming se puede calcular simplemente usando el operador XOR con la función __popcll incorporada de CUDA.

struct HammingDistanceFilter
{
const uint64_t _target, _maxDistance;
HammingDistanceFilter(const uint64_t target, const uint64_t maxDistance) :
_target(target), _maxDistance(maxDistance) {
}
__device__ bool operator()(const uint64_t hash) {
return __popcll(_target ^ hash) <= _maxDistance;
}
};

Answer 2

Aquí hay una solución poco elegante pero exacta (fuerza bruta) que requiere deconstruir el hash de características en campos booleanos individuales para que pueda ejecutar una consulta como esta:

"query": {
"bool": {
"minimum_should_match": -8,
"should": [
{ "term": { "phash.0": true } },
{ "term": { "phash.1": false } },
...
{ "term": { "phash.63": true } }
]
}
}

No estoy seguro de cómo funcionará esto frente a fuzzy_like_this, pero la razón por la que la implementación de FLT está en desuso es que tiene que visitar cada término en el índice para calcular la distancia de edición.

(Mientras que aquí / arriba, está aprovechando la estructura de datos subyacente de índice invertido de Lucene y las operaciones de conjunto optimizadas que deberían funcionar a su favor, dado que probablemente tenga características bastante dispersas)

Answer 3

He empezado una solución para esto yo mismo. Solo he probado hasta ahora en comparación con un conjunto de datos de alrededor de 3,8 millones de documentos, y tengo la intención de aumentar eso ahora hasta decenas de millones.

Mi solución hasta ahora es esta:

Escriba una función de puntuación nativa y regístrela como un complemento. Luego, llame al hacer una consulta para ajustar el valor _score de los documentos a medida que vuelven.

Como una secuencia de comandos groovy, el tiempo necesario para ejecutar la función de puntuación personalizada fue muy poco impresionante, pero escribirlo como una función de puntuación nativa (como se demuestra en esta publicación de blog algo envejecido: http://www.spacevatican.org/2012/5/12/elasticsearch-native-scripts-for-dummies/ ) eran órdenes de magnitud más rápidas.

My HammingDistanceScript se parecía a esto:

public class HammingDistanceScript extends AbstractFloatSearchScript {
private String field;
private String hash;
private int length;
public HammingDistanceScript(Map<String, Object> params) {
super();
field = (String) params.get("param_field");
hash = (String) params.get("param_hash");
if(hash != null){
length = hash.length() * 8;
}
}
private int hammingDistance(CharSequence lhs, CharSequence rhs){
return length - new BigInteger(lhs, 16).xor(new BigInteger(rhs, 16)).bitCount();
}
@Override
public float runAsFloat() {
String fieldValue = ((ScriptDocValues.Strings) doc().get(field)).getValue();
//Serious arse covering:
if(hash == null || fieldValue == null || fieldValue.length() != hash.length()){
return 0.0f;
}
return hammingDistance(fieldValue, hash);
}
}

Vale la pena mencionar en este punto que mis hashes son cadenas binarias codificadas en hexadecimal. Por lo tanto, lo mismo que el suyo, pero con codificación hexadecimal para reducir el tamaño de almacenamiento.

Además, estoy esperando un parámetro param_field, que identifica con qué valor de campo quiero hacer la distancia de Hamming. No necesita hacer esto, pero estoy usando la misma secuencia de comandos contra múltiples campos, por lo que hago :)

Lo uso en consultas como esta:

curl -XPOST ''http://localhost:9200/scf/_search?pretty'' -d ''{
"query": {
"function_score": {
"min_score": MY IDEAL MIN SCORE HERE,
"query":{
"match_all":{}
},
"functions": [
{
"script_score": {
"script": "hamming_distance",
"lang" : "native",
"params": {
"param_hash": "HASH TO COMPARE WITH",
"param_field":"phash"
}
}
}
]
}
}
}''

¡Espero que esto ayude de alguna manera!

Otra información que puede serle útil si realiza esta ruta:

1. Recuerde el archivo es-plugin.properties
Esto tiene que compilarse en la raíz de su archivo jar (si lo coloca en / src / main / resources y luego construye su jar irá en el lugar correcto).

El mío se veía así:

plugin=com.example.elasticsearch.plugins.HammingDistancePlugin
name=hamming_distance
version=0.1.0
jvm=true
classname=com.example.elasticsearch.plugins.HammingDistancePlugin
java.version=1.7
elasticsearch.version=1.7.3

2. Referencia su impl NativeScriptFactory personalizada en elasticsearch.yml
Al igual que en una publicación de blog envejecida.

El mío se veía así:

script.native:
hamming_distance.type: com.example.elasticsearch.plugins.HammingDistanceScriptFactory

Si no lo haces, seguirá apareciendo en la lista de complementos (ver más adelante) pero obtendrás errores cuando intentes usarlo diciendo que elasticsearch no puede encontrarlo.

3. No se moleste en usar el script del complemento elasticsearch para instalarlo
Es solo un dolor en el culo y todo lo que parece hacer es deshacer tus cosas, un poco sin sentido. En cambio, simplemente %ELASTICSEARCH_HOME%/plugins/hamming_distance en %ELASTICSEARCH_HOME%/plugins/hamming_distance y reinicie %ELASTICSEARCH_HOME%/plugins/hamming_distance .

Si todo ha ido bien, verás que se está cargando en el inicio de elasticsearch:

[2016-02-09 12:02:43,765][INFO ][plugins ] [Junta] loaded [mapper-attachments, marvel, knapsack-1.7.2.0-954d066, hamming_distance, euclidean_distance, cloud-aws], sites [marvel, bigdesk]

Y cuando llame a la lista de complementos, estará allí:

curl http://localhost:9200/_cat/plugins?v

produce algo como:

name component version type url
Junta hamming_distance 0.1.0 j

Espero poder probar contra más de decenas de millones de documentos dentro de la próxima semana más o menos. Trataré de recordar volver a abrir y actualizar esto con los resultados, si me sirve.

Answer 4

He simulado e implementado una posible solución, que evita todas las costosas consultas "difusas". En cambio, en el tiempo de índice, toma N muestras aleatorias de M bits de esos 64 bits. Supongo que este es un ejemplo de hashing sensible a Locality . Por lo tanto, para cada documento (y cuando se realiza una consulta), el número de muestra x siempre se toma de las mismas posiciones de bit para tener un hash consistente en todos los documentos.

Las consultas utilizan filtros de term en bool query ''s cláusula with low threshold minimum_should_match threshold. El umbral inferior corresponde a una mayor "borrosidad". Desafortunadamente necesita volver a indexar todas sus imágenes para probar este enfoque.

Creo que las consultas { "term": { "phash.0": true } } no funcionaron bien porque, en promedio, cada filtro coincide con el 50% de los documentos. Con 16 bits / muestra, cada muestra coincide con 2^-16 = 0.0015% de los documentos.

Ejecuto mis pruebas con la siguiente configuración:

• 1024 muestras / hash (almacenado en los campos de doc "0" - "ff" )
• 16 bits / muestra (almacenado en tipo short , doc_values = true )
• 4 fragmentos y 1 millón de hash / índice, aproximadamente 17,6 GB de almacenamiento (se pueden minimizar al no almacenar _source ni muestras, solo el hash binario original)
• minimum_should_match = 150 (de 1024)
• Benchmarked con 4 millones de documentos (4 índices)

Obtiene una velocidad más rápida y un menor uso de disco con menos muestras, pero los documentos entre las distancias de 8 y 9 no están tan bien separados (de acuerdo con mis simulaciones). 1024 parece ser el número máximo de cláusulas should .

Las pruebas se realizaron en un solo Core i5 3570K, 24 GB de RAM, 8 GB para ES, versión 1.7.1. Resultados de 500 consultas (ver notas a continuación, los resultados son demasiado optimistas) :

Mean time: 221.330 ms
Mean docs: 197
Percentiles:
1st = 140.51ms
5th = 150.17ms
25th = 172.29ms
50th = 207.92ms
75th = 233.25ms
95th = 296.27ms
99th = 533.88ms

Voy a probar cómo se escala a 15 millones de documentos, pero lleva 3 horas generar y almacenar 1 millón de documentos en cada índice.

Debe probar o calcular qué tan bajo debe establecer minimum_should_match para obtener la compensación deseada entre las coincidencias perdidas y las incorrectas, esto depende de la distribución de sus valores hash.

Consulta de ejemplo (se muestran 3 de 1024 campos):

{
"bool": {
"should": [
{
"filtered": {
"filter": {
"term": {
"0": -12094,
"_cache": false
}
}
}
},
{
"filtered": {
"filter": {
"term": {
"_cache": false,
"1": -20275
}
}
}
},
{
"filtered": {
"filter": {
"term": {
"ff": 15724,
"_cache": false
}
}
}
}
],
"minimum_should_match": 150
}
}

Editar: Cuando comencé a hacer más pruebas de referencia noté que había generado hashes demasiado diferentes para diferentes índices, por lo que la búsqueda de aquellos resultó en cero coincidencias. Los documentos generados recientemente generan entre 150 y 250 coincidencias / índice / consulta y deben ser más realistas.

Nuevos resultados se muestran en el gráfico anterior, tenía 4 GB de memoria para ES y 20 GB restantes para OS. La búsqueda de 1 - 3 índices tuvo un buen rendimiento (tiempo medio de 0.1 - 0.2 segundos) pero la búsqueda de más de esto dio como resultado un montón de IO de disco y las consultas comenzaron a tomar entre 9 y 11 segundos. Esto podría evitarse tomando menos muestras del hash pero luego las tasas de recuperación y precisión no serían tan buenas, o bien podrías tener una máquina con 64 GB de RAM y ver qué tan lejos llegarás.

Edición 2: he vuelto a generar datos con _source: false y no he almacenado muestras de hash (solo el hash en bruto), esto reduce el espacio de almacenamiento en un 60% a alrededor de 6,7 GB / índice (de 1 millón de documentos). Esto no afectó la velocidad de consulta en conjuntos de datos más pequeños, pero cuando la RAM no era suficiente y el disco tenía que ser utilizado, las consultas eran aproximadamente un 40% más rápidas.

Edición 3: Probé fuzzy búsqueda fuzzy con una distancia de edición de 2 en un conjunto de 30 millones de documentos, y la comparé con 256 muestras aleatorias del hash para obtener resultados aproximados. Bajo estas condiciones, los métodos tienen aproximadamente la misma velocidad, pero fuzzy dan resultados exactos y no necesitan ese espacio extra en el disco. Creo que este enfoque solo es útil para consultas "muy borrosas" como una distancia mayor de 3.

Answer 5

He usado @ndtreviv''s respuesta @ndtreviv''s como punto de partida. Aquí están mis notas para ElasticSearch 2.3.3:

1. es-plugin.properties archivo es-plugin.properties ahora se llama plugin-descriptor.properties

2. No hace referencia a NativeScriptFactory en NativeScriptFactory , sino que crea una clase adicional junto a su HammingDistanceScript .

import org.elasticsearch.common.Nullable;
import org.elasticsearch.plugins.Plugin;
import org.elasticsearch.script.ExecutableScript;
import org.elasticsearch.script.NativeScriptFactory;
import org.elasticsearch.script.ScriptModule;
import java.util.Map;
public class StringMetricsPlugin extends Plugin {
@Override
public String name() {
return "string-metrics";
}
@Override
public String description() {
return "";
}
public void onModule(ScriptModule module) {
module.registerScript("hamming-distance", HammingDistanceScriptFactory.class);
}
public static class HammingDistanceScriptFactory implements NativeScriptFactory {
@Override
public ExecutableScript newScript(@Nullable Map<String, Object> params) {
return new HammingDistanceScript(params);
}
@Override
public boolean needsScores() {
return false;
}
}
}

3. Luego haga referencia a esta clase en su archivo plugin-descriptor.properties :

plugin=com.example.elasticsearch.plugins. StringMetricsPlugin
name=string-metrics
version=0.1.0
jvm=true
classname=com.example.elasticsearch.plugins.StringMetricsPlugin
java.version=1.8
elasticsearch.version=2.3.3

4. module.registerScript("hamming-distance", HammingDistanceScriptFactory.class); consulta suministrando el nombre que utilizó en esta línea: module.registerScript("hamming-distance", HammingDistanceScriptFactory.class); en 2.

Espero que esto ayude a la próxima pobre alma que tiene que lidiar con los estúpidos documentos ES.

Answer 6

También implementé el enfoque CUDA con algunos buenos resultados incluso en una tarjeta gráfica GeForce 650M para computadora portátil. La implementación fue fácil con la biblioteca Thrust . Espero que el código no tenga errores (no lo probé a fondo) pero no debería afectar los resultados del benchmark. Al menos llamé a thrust::system::cuda::detail::synchronize() antes de detener el temporizador de alta precisión .

typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;
// Maybe there is a simple 64-bit solution out there?
__host__ __device__ inline int hammingWeight(uint32_t v)
{
v = v - ((v>>1) & 0x55555555);
v = (v & 0x33333333) + ((v>>2) & 0x33333333);
return ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
__host__ __device__ inline int hammingDistance(const uint64_t a, const uint64_t b)
{
const uint64_t delta = a ^ b;
return hammingWeight(delta & 0xffffffffULL) + hammingWeight(delta >> 32);
}
struct HammingDistanceFilter
{
const uint64_t _target, _maxDistance;
HammingDistanceFilter(const uint64_t target, const uint64_t maxDistance) :
_target(target), _maxDistance(maxDistance) {
}
__host__ __device__ bool operator()(const uint64_t hash) {
return hammingDistance(_target, hash) <= _maxDistance;
}
};

La búsqueda lineal fue tan fácil como

thrust::copy_if(
hashesGpu.cbegin(), hashesGpu.cend(), matchesGpu.begin(),
HammingDistanceFilter(target_hash, maxDistance)
)

La búsqueda fue 100% precisa y mucho más rápida que mi respuesta ElasticSearch, ¡en 50 milisegundos, CUDA podría transmitir hasta 35 millones de hashes! Estoy seguro de que las tarjetas de escritorio más nuevas son mucho más rápidas que esto. También obtenemos una varianza muy baja y un crecimiento lineal constante del tiempo de búsqueda a medida que atravesamos más y más datos. ElasticSearch golpeó problemas de mala memoria en consultas más grandes debido a datos de muestreo inflados.

Así que aquí estoy informando los resultados de "A partir de estos N hash, encuentre los que están dentro de una distancia de 8 Hamming desde un solo hash H". Corro estas 500 veces e informo percentiles.

Hay algo de sobrecarga de inicio del kernel, pero después de que el espacio de búsqueda es de más de 5 millones de hashes, la velocidad de búsqueda es bastante constante en 700 millones de hashes / segundo. Naturalmente, el límite superior en el número de hashes que se buscará se establece por la RAM de la GPU.