php - sirve - propiedad alt imagen

Libpuzzle indexando millones de imágenes?

Question

se trata del libpuzzle libray para php ( http://libpuzzle.pureftpd.org/project/libpuzzle ) del Sr. Frank Denis. Estoy tratando de entender cómo indexar y almacenar los datos en mi base de datos mysql. La generación del vector es absolutamente ningún problema.

Ejemplo:

# Compute signatures for two images
$cvec1 = puzzle_fill_cvec_from_file(''img1.jpg'');
$cvec2 = puzzle_fill_cvec_from_file(''img2.jpg'');
# Compute the distance between both signatures
$d = puzzle_vector_normalized_distance($cvec1, $cvec2);
# Are pictures similar?
if ($d < PUZZLE_CVEC_SIMILARITY_LOWER_THRESHOLD) {
echo "Pictures are looking similar/n";
} else {
echo "Pictures are different, distance=$d/n";
}

Eso está claro para mí, pero ahora, ¿cómo trabajo cuando tengo una gran cantidad de imágenes> 1.000.000? ¿Calculo el vector y lo guardo con el nombre de archivo en la base de datos? ¿Cómo encontrar las imágenes similares ahora? Si almaceno cada vector en el mysql, tengo que abrir cada registro y calcular la distancia con la función puzzle_vector_normalized_distance. Esos procedimientos llevan mucho tiempo (abra cada entrada de la base de datos, póngala, lance la función, ...)

Leí el archivo Léame de Lib Puzzle Libaray y encontré lo siguiente:

¿Funcionará con una base de datos que tiene millones de imágenes?

Una firma de imagen típica solo requiere 182 bytes, utilizando las funciones integradas de compresión / descompresión.

Firmas similares comparten "palabras" idénticas, es decir. Secuencias idénticas de valores en las mismas posiciones. Al usar índices compuestos (palabra + posición), el conjunto de posibles vectores similares se reduce drásticamente, y en la mayoría de los casos, no es necesario calcular la distancia de vector para calcularla.

La indexación a través de palabras y posiciones también facilita la división de los datos en varias tablas y servidores.

Así que sí, la biblioteca de Puzzle no es incompatible con los proyectos que necesitan indexar millones de imágenes.

También encontré esta descripción sobre la indexación:

------------------------ INDEXING ------------------------

¿Cómo encontrar rápidamente imágenes similares, si son millones de registros?

El artículo original tiene una respuesta simple pero eficiente.

Cortar el vector en palabras de longitud fija. Por ejemplo, consideremos el siguiente vector:

[ ABCDEFGHIJKLMNOPQRSTU VWXYZ ]

Con una longitud de palabra (K) de 10, puede obtener las siguientes palabras:

[abcdefghij] encontrado en la posición 0 [bcdefghijk] encontrado en la posición 1 [cdefghijkl] encontrado en la posición 2 etc. hasta la posición N-1

Luego, indexa tu vector con un índice compuesto de (palabra + posición).

Incluso con millones de imágenes, K = 10 y N = 100 deberían ser suficientes para tener muy pocas entradas que compartan el mismo índice.

Aquí hay un esquema de base de datos de muestra muy básico:

+-----------------------------+
| signatures |
+-----------------------------+
| sig_id | signature | pic_id |
+--------+-----------+--------+
+--------------------------+
| words |
+--------------------------+
| pos_and_word | fk_sig_id |
+--------------+-----------+

Recomiendo dividir al menos la tabla de "palabras" en varias tablas y / o servidores.

Por defecto (lambas = 9) las firmas tienen una longitud de 544 bytes. Para ahorrar espacio de almacenamiento, se pueden comprimir hasta la tercera parte de su tamaño original a través de la función puzzle_compress_cvec (). Antes de usarlos, deben descomprimirse con puzzle_uncompress_cvec ().

Creo que comprimir es el camino equivocado porque tengo que descomprimir cada vector antes de compararlo.

Mi pregunta ahora es: ¿Cuál es la manera de manejar millones de fotos y cómo compararlas de una manera rápida y eficiente? No puedo entender cómo el "corte del vector" debería ayudarme con mi problema.

Muchas gracias, tal vez pueda encontrar a alguien aquí que esté trabajando con libpuzzle libaray.

Aclamaciones.

Answer 1

Entonces, veamos el ejemplo que dan y tratemos de expandir.

Supongamos que tiene una tabla que almacena información relacionada con cada imagen (ruta, nombre, descripción, etc.). En esa tabla, incluirá un campo para la firma comprimida, calculada y almacenada cuando inicialmente rellena la base de datos. Vamos a definir esa tabla así:

CREATE TABLE images (
image_id INTEGER NOT NULL PRIMARY KEY,
name TEXT,
description TEXT,
file_path TEXT NOT NULL,
url_path TEXT NOT NULL,
signature TEXT NOT NULL
);

Cuando inicialmente calcula la firma, también va a calcular una cantidad de palabras de la firma:

// this will be run once for each image:
$cvec = puzzle_fill_cvec_from_file(''img1.jpg'');
$words = array();
$wordlen = 10; // this is $k from the example
$wordcnt = 100; // this is $n from the example
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) {
$words[] = substr($cvec, $i, $wordlen);
}

Ahora puedes poner esas palabras en una tabla, definida así:

CREATE TABLE img_sig_words (
image_id INTEGER NOT NULL,
sig_word TEXT NOT NULL,
FOREIGN KEY (image_id) REFERENCES images (image_id),
INDEX (image_id, sig_word)
);

Ahora inserta en esa tabla, anteponiendo el índice de posición donde se encontró la palabra, para saber cuándo una palabra coincide con la que coincidió en el mismo lugar en la firma:

// the signature, along with all other data, has already been inserted into the images
// table, and $image_id has been populated with the resulting primary key
foreach ($words as $index => $word) {
$sig_word = $index.''__''.$word;
$dbobj->query("INSERT INTO img_sig_words (image_id, sig_word) VALUES ($image_id,
''$sig_word'')"); // figure a suitably defined db abstraction layer...
}

Sus datos así inicializados, puede tomar imágenes con palabras coincidentes con relativa facilidad:

// $image_id is set to the base image that you are trying to find matches to
$dbobj->query("SELECT i.*, COUNT(isw.sig_word) as strength FROM images i JOIN img_sig_words
isw ON i.image_id = isw.image_id JOIN img_sig_words isw_search ON isw.sig_word =
isw_search.sig_word AND isw.image_id != isw_search.image_id WHERE
isw_search.image_id = $image_id GROUP BY i.image_id, i.name, i.description,
i.file_path, i.url_path, i.signature ORDER BY strength DESC");

Podría mejorar la consulta agregando una cláusula HAVING que requiera una strength mínima, lo que reducirá aún más su conjunto coincidente.

No garantizo que esta sea la configuración más eficiente, pero debería ser más o menos funcional para lograr lo que está buscando.

Básicamente, dividir y almacenar las palabras de esta manera le permite hacer una verificación de distancia aproximada sin tener que ejecutar una función especializada en las firmas.

Answer 2

He experimentado con libpuzzle antes, he llegado tan lejos como tú. Realmente no comenzó con una implementación adecuada. Tampoco estaba claro cómo hacerlo exactamente. (y abandonó el proyecto por falta de tiempo, así que realmente no persistí en él)

De todos modos, mirando ahora, intentaré ofrecer mi comprensión, tal vez entre nosotros podamos resolverlo :)

Las consultas utilizan un proceso de 2 etapas -

1. Primero usas la tabla de palabras .
   1. tomar la imagen de ''referencia'' y elaborar su firma.
   2. resolver sus palabras componentes,
   3. Consulte la tabla de palabras para encontrar todas las coincidencias posibles . Esto puede usar los ''índices'' de los motores de base de datos para consultas eficientes.
   4. compilar una lista de todos los sig_ids. (Obtendré algunos duplicados en 3.)
2. Entonces consulte la tabla de firmas.
   1. recupere y descomprima todo lo posible de las firmas (debido a que tiene una lista prefiltrada, el número debe ser relativamente pequeño)
   2. use puzzle_vector_normalized_distance para calcular una distancia real.
   3. ordenar y clasificar los resultados según sea necesario

(Es decir, solo utiliza la compresión en la tabla de firmas . Las palabras permanecen sin comprimir, por lo que puede ejecutar consultas rápidas en ella)

La tabla de palabras es una forma de índice invertido. De hecho, tengo en mente utilizar https://.com/questions/tagged/sphinx lugar de la tabla de base de datos de palabras, porque está diseñado específicamente como un índice invertido muy rápido.

... en teoría de todos modos ...

Answer 3

Hice un proyecto DEMO de libpuzzle en GitHub: https://github.com/alsotang/libpuzzle_demo .

El proyecto utiliza la forma que Jason propuso anteriormente.

El esquema de la base de datos se muestra en: https://github.com/alsotang/libpuzzle_demo/blob/master/schema.sql

Y daré más información sobre la firma de libpuzzle.

Ahora tenemos las dos imágenes, y déjame calcular su firma.

Las líneas impares son para la imagen 1 (la izquierda), y las líneas pares son para la imagen 2.

Puede encontrar que en la mayoría de los casos, el número en la misma posición es el mismo.

....

Mi inglés es muy pobre, por lo que no puedo expresar mi mente continuar ... Creo que cualquiera que quiera indexar millones de imágenes debería inspeccionar mi repo de GitHub en la DEMO de libpuzzle.

Answer 4

También estoy trabajando en libpuzzle en PHP y tengo algunas dudas sobre cómo generar las palabras de las firmas de la imagen. La respuesta anterior de Jasons parece correcta, pero tengo un problema con esta parte:

// this will be run once for each image:
$cvec = puzzle_fill_cvec_from_file(''img1.jpg'');
$words = array();
$wordlen = 10; // this is $k from the example
$wordcnt = 100; // this is $n from the example
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) {
$words[] = substr($cvec, $i, $wordlen);
}

El vector de firma tiene una longitud de 544 letras y con la creación de palabras anterior, siempre estamos usando solo las primeras 110 letras. Lo que significa que estamos indexando en nombre del tercio superior del contenido de la imagen si lo comprendo correctamente.

Si lees el artículo original ( una firma de imagen para cualquier tipo de imagen ) en el que se basa libpuzzle, explican que las palabras deben generarse " ... posiblemente no contiguas y superpuestas ". No estoy seguro de si significan no contiguos y no superpuestos, o no contiguos y superpuestos ...

Pero si significan que no se superponen, supongo que las palabras deberían extenderse a lo largo de todo el vector de la firma. También tendría más sentido, ya que el vector se crea al evaluar las regiones de la imagen de izquierda a derecha, de arriba a abajo. Y al difundir las palabras en todo el vector, esto significa que está considerando la imagen completa en lugar de la parte superior de la misma (si genera todas las palabras desde el principio del vector).

Me encantaría saber cómo ustedes entienden esto.