Как найти изображения по сходству внутри SQL-запроса? - PullRequest
Новая
       0

Как найти изображения по сходству внутри SQL-запроса?

1 голос
/ 08 апреля 2011

Я хочу обработать изображения, чтобы установить, скажем, 9 областей внутри каждой, затем найти средний цвет каждой области, а затем сохранить его в поле символа, например: 

255,255,255,255,255,255,107,195,305

Затем найтиДля всех изображений, похожих на данное изображение, я должен рассчитать расстояние между каждой парой цветов (сравнение с теми же областями), например:

Разница между этими изображениями составляет 1: 

255,255,255,255,255,255,107,195,305
255,255,255,255,255,255,107,195,304

Разница между этими изображениями составляет 3: 

255,255,255,255,255,255,105,195,305
255,255,255,255,255,255,107,195,304

Моя проблема в том, как выполнить такой запрос и упорядочить его по сходству?Поле представляет собой просто строку со значениями, разделенными запятыми.

Возможно ли, что такой запрос может быть быстрым?Или я должен искать другой подход?Мы говорим о тысячах изображений

Редактировать: как @therealsix, одним из вариантов может быть помещение каждого среднего значения цвета в отдельный столбец.

Ответы [ 6 ]

3 голосов
/ 08 апреля 2011

Более «SQLey» способ сделать это, возможно, использовать более нормализованный подход к базе данных с двумя таблицами: 

Image(ImageID int, ... other columns as required ...)
ImageZone(ImageID int, ZoneIndex int, ColourValue int, ...)

так что для вашего примера, вы можете иметь 

ImageID   ZoneIndex   ColourValue
-------   ---------   -----------
  1          1          255
  1          2          255
  ...
  1          9          304
  2          1          255
  ...
  2          9          305

Затем, чтобы получить расстояние, что-то вроде (я парень SQL Server, но это должно быть легко переводится на MySQL): 

 SELECT
    Candidate.ImageID,
    Candidate.ImageFile, /* or whatever... */
    Scores.Difference
 FROM
 (
   SELECT
      Original.ImageID AS OriginalID,
      Candidate.ImageID AS CandidateID,
      SUM(ABS(Original.ColourValue - Candidate.ColourValue)) AS Difference
   FROM ImageZone AS Original
   INNER JOIN ImageZone AS Candidate
     ON (Original.ImageID <> Candidate.ImageID)
     ON (Original.ZoneIndex = Candidate.ZoneIndex)
 ) AS Scores
 INNER JOIN Image AS Candidate ON (Scores.CandidateID = Candidate.ImageID)
 WHERE Scores.OriginalID = 1 /* or the image ID you want to look up */
 ORDER BY Difference

Таким образом, внутренний запрос создает строку для каждой зоны-кандидата, например (O = оригинал, C = кандидат): 

 O.ImageID  O.ZoneIndex  O.ColourValue  C.ImageID  C.ZoneIndex  C.ColourValue
 ---------  -----------  -------------  ---------  -----------  -------------
    1           1           255            2            1           255
    ... then ...
    1           9           305            2            9           304
    1           1           255            3            1            99
    ... then ...
    99          9           100           98            9            99

, которые затем агрегируются в общую разницу: 

 OriginalID  CandidateID  Difference
 ----------  -----------  ----------
    1            2            1
    1            3           10
    ...
    99          98          500

Затем вы выбираете из этой виртуальной таблицы только то, где OriginalID равен 1, и присоединяете ее к исходной таблице изображений, чтобы получить любые детали, которые вам нужны для наименьшей оценки «разница» (в данном случае 2).

Это ИМХО гораздо более чистый дизайн БД (и идеально подходит, если вы позже будете использовать больше зон и т. Д.).

0 голосов
/ 08 апреля 2011

Мне кажется, что проблема это не сравнение последовательностей проблема, а география одна.

Я думаю, вы хотите найти ближайшие точки в 9-е измерение набор точек.

Ознакомьтесь с этой статьей о том, как пространственные базы данных используют R-деревья для эффективного поиска кластеров (например, точек поблизости, что является именно тем, что вам нужно.): Алгоритмы инкрементального соединения на расстоянии для пространственных баз данных (щелкните ссылку "Кэширование")

Реальная проблема заключается в том, что я не знаю ни одной пространственной базы данных, которая бы поддерживала 9 измерений.Единственный хак, о котором я мог подумать, - это тройка (A, B, C) тройных точек географии.

Чтобы прояснить мою точку зрения.Давайте посмотрим на ваши данные:

Разница между этими изображениями составляет 3: 

255,255,255,255,255,255,105,195,305
255,255,255,255,255,255,107,195,304

Мы можем рассматривать вышеупомянутые 2 строки как 2 точки (давайтеназовите их a и b) в 9-мерном мире.

9 чисел - их координаты (a1,a2,...,a9 и b1,b2,...,b9).

А "разница" - их расстояние: Sum(|ai-bi|).Существует много способов определения расстояния, и это один из распространенных способов.Это не евклидово расстояние, но оно похоже.И вычислить его немного быстрее.

Теперь, если у вас действительно будут тысячи или миллионы изображений, это будет очень медленная процедура для вычисления всех этих миллионов (или триллионов) расстояний.Если вам просто нужно сравнить по одному, с несколькими тысячами, я думаю, у вас уже есть два ответа, которые будут в порядке.

Но если вы действительно хотите найти похожие изображения и хранить их (например, сотни тысяч), R-деревья или какой-либо другой индекс, используемый в пространственных базах данных, будет лучше.R-дерево - это не что-то волшебное, это просто индекс, специализированный для такого рода многомерных данных.

Если вы не можете найти пространственную базу данных, которая поддерживает такое количество измерений, я не уверен, как найти решениеваш собственный будет создан.

Одной из мыслей было бы разделить 9 чисел на 3 триплета.Каждый триплет был бы трехмерной точкой.Таким образом, каждое из ваших изображений будет храниться в виде трех трехмерных географических точек.Тогда разница между двумя изображениями будет суммой трех (географических) расстояний.

0 голосов
/ 08 апреля 2011

Хорошо, поэтому ваши изображения в таблице имеют идентификатор и 9 отдельных цветовых полей - от цвета 1 до цвета 9 

SELECT a.id, b.id, ( ABS( a.color1 - b.color ) + ABS( a.color2 + b.color2 ) + ABS( a.color3 + b.color3 ) + ... ) AS difference
FROM images AS a
JOIN images AS b
WHERE a.id > b.id
ORDER BY difference

Это может быть достаточно эффективным, вам придется попробовать его.

0 голосов
/ 08 апреля 2011

Я бы предложил использовать функции mysql для сравнения с вашим случайно заданным изображением. Сначала давайте создадим простой пример таблицы 

DROP TABLE IF EXISTS images;

CREATE TABLE images (
  id         INTEGER AUTO_INCREMENT PRIMARY KEY,
  rgb_values VARCHAR(255)
);

Теперь давайте определим функции, которые мы будем использовать в нашем запросе. Первый позволяет использовать для разделения строки на любой разделитель и получить желаемый элемент обратно по индексу: 

DROP FUNCTION SPLIT_STR;

CREATE FUNCTION SPLIT_STR(
  x VARCHAR(255),
  delim VARCHAR(12),
  pos INT
)
RETURNS VARCHAR(255)
RETURN
  REPLACE(SUBSTRING(SUBSTRING_INDEX(x, delim, pos),
  LENGTH(SUBSTRING_INDEX(x, delim, pos -1)) + 1),
  delim, '')
;

Далее мы определяем функцию для вычисления разности изображений по вашему алгоритму (или любому алгоритму, который вы хотите использовать): 

DROP FUNCTION IMAGE_DIFF;

CREATE FUNCTION IMAGE_DIFF(
  from_val VARCHAR(255),
  to_val VARCHAR(255)
)
RETURNS INTEGER(4)
RETURN
  ABS((SPLIT_STR(to_val, ',', 1) - SPLIT_STR(from_val, ',',1))) +
  ABS((SPLIT_STR(to_val, ',', 2) - SPLIT_STR(from_val, ',',2))) +
  ABS((SPLIT_STR(to_val, ',', 3) - SPLIT_STR(from_val, ',',3))) +
  ABS((SPLIT_STR(to_val, ',', 4) - SPLIT_STR(from_val, ',',4))) +
  ABS((SPLIT_STR(to_val, ',', 5) - SPLIT_STR(from_val, ',',5))) +
  ABS((SPLIT_STR(to_val, ',', 6) - SPLIT_STR(from_val, ',',6))) +
  ABS((SPLIT_STR(to_val, ',', 7) - SPLIT_STR(from_val, ',',7))) +
  ABS((SPLIT_STR(to_val, ',', 8) - SPLIT_STR(from_val, ',',8))) +
  ABS((SPLIT_STR(to_val, ',', 9) - SPLIT_STR(from_val, ',',9)))
;

Давайте создадим несколько примеров данных: 

INSERT INTO images(rgb_values) VALUES ("237,128,73,69,35,249,199,183,178");
INSERT INTO images(rgb_values) VALUES ("39,212,164,170,202,49,93,77,145");
INSERT INTO images(rgb_values) VALUES ("28,242,83,167,92,161,115,38,108");
INSERT INTO images(rgb_values) VALUES ("72,81,73,2,77,109,177,204,120");
INSERT INTO images(rgb_values) VALUES ("165,149,106,248,39,26,167,237,139");
INSERT INTO images(rgb_values) VALUES ("183,40,156,131,120,19,71,88,69");
INSERT INTO images(rgb_values) VALUES ("138,136,112,36,69,245,130,196,24");
INSERT INTO images(rgb_values) VALUES ("1,194,153,107,16,102,164,154,74");
INSERT INTO images(rgb_values) VALUES ("172,161,17,179,140,244,23,219,115");
INSERT INTO images(rgb_values) VALUES ("166,151,48,62,154,227,44,21,201");
INSERT INTO images(rgb_values) VALUES ("118,73,212,180,150,64,254,177,68");
INSERT INTO images(rgb_values) VALUES ("119,220,226,254,14,175,123,11,134");
INSERT INTO images(rgb_values) VALUES ("118,93,238,31,77,36,105,151,216");
INSERT INTO images(rgb_values) VALUES ("123,108,177,136,9,24,119,175,88");
INSERT INTO images(rgb_values) VALUES ("11,207,12,215,215,80,101,213,143");
INSERT INTO images(rgb_values) VALUES ("132,158,46,188,7,245,241,126,214");
INSERT INTO images(rgb_values) VALUES ("167,238,186,86,109,164,219,199,238");
INSERT INTO images(rgb_values) VALUES ("216,93,139,246,153,39,226,152,143");
INSERT INTO images(rgb_values) VALUES ("98,229,7,203,230,224,57,154,252");
INSERT INTO images(rgb_values) VALUES ("7,95,145,120,35,6,116,240,64");
INSERT INTO images(rgb_values) VALUES ("45,194,172,223,96,168,18,4,215");
INSERT INTO images(rgb_values) VALUES ("243,161,214,235,134,190,207,63,127");
INSERT INTO images(rgb_values) VALUES ("74,189,249,85,148,169,65,3,81");
INSERT INTO images(rgb_values) VALUES ("46,113,191,20,108,139,60,249,6");
INSERT INTO images(rgb_values) VALUES ("153,246,189,175,5,125,9,197,160");
INSERT INTO images(rgb_values) VALUES ("202,248,23,59,81,175,197,180,114");
INSERT INTO images(rgb_values) VALUES ("73,136,252,137,222,197,118,64,69");
INSERT INTO images(rgb_values) VALUES ("172,224,251,32,154,175,201,33,14");
INSERT INTO images(rgb_values) VALUES ("141,126,112,12,45,214,243,127,49");
INSERT INTO images(rgb_values) VALUES ("116,155,23,205,62,235,111,136,205");

, а затем выполните запрос, используя нашу недавно определенную функцию, для изображения, с которым вы хотите сравнить: 

mysql> SELECT id
    ->      , image_diff(rgb_values, '255,191,234,123,85,23,255,255,255') rgb_diff
    ->   FROM images
    ->  ORDER BY 2 DESC;
+----+----------+
| id | rgb_diff |
+----+----------+
| 19 |     1150 |
| 10 |     1148 |
|  3 |     1122 |
| 27 |     1094 |
|  9 |     1070 |
| 15 |     1069 |
| 23 |     1061 |
| 21 |     1059 |
|  7 |     1034 |
| 12 |     1024 |
| 24 |     1022 |
| 30 |     1016 |
| 29 |      989 |
| 28 |      962 |
|  2 |      947 |
|  4 |      933 |
| 16 |      893 |
|  6 |      885 |
|  8 |      875 |
| 20 |      848 |
| 25 |      835 |
| 26 |      815 |
|  1 |      777 |
| 22 |      758 |
| 14 |      745 |
| 11 |      706 |
| 18 |      683 |
|  5 |      656 |
| 13 |      645 |
| 17 |      494 |
+----+----------+
30 rows in set (0.01 sec)
0 голосов
/ 08 апреля 2011

Я думаю, вы ищете что-то вроде этого ...

http://kodisha.net/color-names/?color=FD464A

Обратите внимание на разницу в цвете справа ... 

Color Difference: 1.84568861095

http://en.wikipedia.org/wiki/Color_difference

Выполнение этого запроса на 1000+ строк наверняка убьет ваш сервер, если одновременно будет большое количество пользователей.

0 голосов
/ 08 апреля 2011

На самом деле, исходя из его звуков, вы пытаетесь выполнить форму выравнивания Последовательности.Для этого есть ряд алгоритмов, которые были использованы для сравнения последовательностей генов:

Выравнивание последовательностей

...