Алгоритм поиска похожих изображений

83

Мне нужен алгоритм, который может определить, являются ли два изображения «похожими» и распознает похожие образцы цвета, яркости, формы и т. Д. Мне могут понадобиться некоторые указатели относительно того, какие параметры человеческий мозг использует для «категоризации» изображений. ..

Я рассмотрел сопоставление на основе Хаусдорфа, но, похоже, оно в основном предназначено для сопоставления преобразованных объектов и шаблонов формы.

кицунэ
источник
На этот похожий вопрос есть несколько хороших ответов: stackoverflow.com/questions/25977/…
blak
2
много «мог» и «противников». Кто-нибудь попробует все эти предложения и знает, что лучше?
john ktejik

Ответы:

60

Я сделал нечто подобное, разложив изображения на сигнатуры с помощью вейвлет-преобразования .

Мой подход заключался в том, чтобы выбрать n наиболее значимых коэффициентов из каждого преобразованного канала и записать их местоположение. Это было сделано путем сортировки списка кортежей (мощность, расположение) по abs (мощность). Похожие изображения будут иметь сходство в том, что они будут иметь значимые коэффициенты в одних и тех же местах.

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

Вы можете найти мою реализацию вышеупомянутого в mactorii , над которой, к сожалению, я не работал так много, как должен :-)

Другой метод, который некоторые мои друзья использовали с удивительно хорошими результатами, - это просто уменьшить размер вашего изображения, скажем, до 4x4 пикселей и сохранить ваши подписи. Насколько похожи два изображения, можно оценить, скажем, вычислив манхэттенское расстояние между двумя изображениями с использованием соответствующих пикселей. У меня нет подробностей о том, как они выполняли изменение размера, поэтому вам, возможно, придется поиграть с различными алгоритмами, доступными для этой задачи, чтобы найти тот, который подходит.

свободное место
источник
7
Метод изменения размера до 4x4 - отличная идея (не то чтобы ваш метод тоже не очень хорош), но первый проще.
Аликс Аксель,
@freespace, не могли бы вы объяснить это «вычисление манхэттенского расстояния между двумя изображениями с использованием соответствующих пикселей»
Амбика,
1
@Ambika: обрабатывать цвет каждого пикселя как вектор длиной 3 и вычислять манхэттенское расстояние между соответствующими пикселями в сравниваемых изображениях. Это дает вам 4 манхэттенских расстояния. Как вы получите из этого единую меру, зависит от вас. Самый очевидный - сложить их вместе.
freespace
45

pHash может вас заинтересовать.

перцептивный хеш n. отпечаток аудио-, видео- или графического файла, который математически основан на аудио- или визуальном контенте, содержащемся в нем. В отличие от криптографических хеш-функций, которые полагаются на лавинообразный эффект небольших изменений входных данных, приводящих к резким изменениям в выходных данных, перцептивные хеш-коды «близки» друг к другу, если входные данные визуально или слухово похожи.

Алвис
источник
8
Только что заглянул на сайт pHash. В настоящее время у них есть эта функция на своем сайте, которая позволяет вам загружать два изображения и сообщает вам, похожи они или нет. Я пробовал около 10 похожих изображений и 10 - нет. К сожалению, процент успеха не был таким впечатляющим.
Родриго-Сильвейра
2
pHash на самом деле довольно строгий, вы можете использовать ahash или средний хеш, который, как правило, менее строг. Вы можете найти реализацию python здесь github.com/JohannesBuchner/imagehash/blob/master/…
Rohit
13

Я использовал SIFT, чтобы повторно обнаружить один и тот же объект на разных изображениях. Это действительно мощно, но довольно сложно и может оказаться излишним. Если изображения должны быть очень похожими, некоторые простые параметры, основанные на разнице между двумя изображениями, могут многое вам сказать. Некоторые указатели:

  • Нормализовать изображения, т.е. сделать среднюю яркость обоих изображений одинаковой, вычислив среднюю яркость обоих и уменьшив самую яркую в соответствии с соотношением (чтобы избежать обрезки на самом высоком уровне)), особенно если вас больше интересует форма, чем цвет.
  • Сумма разницы в цвете нормализованного изображения на канал.
  • Найдите края изображений и измерьте расстояние между пикселями краев обоих изображений. (для формы)
  • Разделите изображения на набор дискретных областей и сравните средний цвет каждой области.
  • Установите пороговое значение для изображений на одном (или на нескольких) уровнях и подсчитайте количество пикселей, в которых получаемые черно-белые изображения различаются.
Jilles de Wit
источник
Можете ли вы указать на код, который использует просеивающие выборки для вычисления сходства изображений?
mrgloom
Извините, я уверен, что есть общедоступный код, но мне ничего неизвестно. На этом сайте есть несколько примеров. Например, здесь: stackoverflow.com/questions/5461148/…
jilles de wit
В Accord Framework для .Net ( accord-framework.net ) есть несколько отличных классов для выполнения SURF, BagOfVisualWords, Harris Corner Detection и т.д. с множеством различных ядер и алгоритмов кластеризации.
dynamichael 05
6

Моя лаборатория тоже нуждалась в решении этой проблемы, и мы использовали Tensorflow. Вот полная реализация приложения для визуализации сходства изображений.

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

from __future__ import absolute_import, division, print_function

"""

This is a modification of the classify_images.py
script in Tensorflow. The original script produces
string labels for input images (e.g. you input a picture
of a cat and the script returns the string "cat"); this
modification reads in a directory of images and 
generates a vector representation of the image using
the penultimate layer of neural network weights.

Usage: python classify_images.py "../image_dir/*.jpg"

"""

# Copyright 2015 The TensorFlow Authors. All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
# ==============================================================================

"""Simple image classification with Inception.

Run image classification with Inception trained on ImageNet 2012 Challenge data
set.

This program creates a graph from a saved GraphDef protocol buffer,
and runs inference on an input JPEG image. It outputs human readable
strings of the top 5 predictions along with their probabilities.

Change the --image_file argument to any jpg image to compute a
classification of that image.

Please see the tutorial and website for a detailed description of how
to use this script to perform image recognition.

https://tensorflow.org/tutorials/image_recognition/
"""

import os.path
import re
import sys
import tarfile
import glob
import json
import psutil
from collections import defaultdict
import numpy as np
from six.moves import urllib
import tensorflow as tf

FLAGS = tf.app.flags.FLAGS

# classify_image_graph_def.pb:
#   Binary representation of the GraphDef protocol buffer.
# imagenet_synset_to_human_label_map.txt:
#   Map from synset ID to a human readable string.
# imagenet_2012_challenge_label_map_proto.pbtxt:
#   Text representation of a protocol buffer mapping a label to synset ID.
tf.app.flags.DEFINE_string(
    'model_dir', '/tmp/imagenet',
    """Path to classify_image_graph_def.pb, """
    """imagenet_synset_to_human_label_map.txt, and """
    """imagenet_2012_challenge_label_map_proto.pbtxt.""")
tf.app.flags.DEFINE_string('image_file', '',
                           """Absolute path to image file.""")
tf.app.flags.DEFINE_integer('num_top_predictions', 5,
                            """Display this many predictions.""")

# pylint: disable=line-too-long
DATA_URL = 'http://download.tensorflow.org/models/image/imagenet/inception-2015-12-05.tgz'
# pylint: enable=line-too-long


class NodeLookup(object):
  """Converts integer node ID's to human readable labels."""

  def __init__(self,
               label_lookup_path=None,
               uid_lookup_path=None):
    if not label_lookup_path:
      label_lookup_path = os.path.join(
          FLAGS.model_dir, 'imagenet_2012_challenge_label_map_proto.pbtxt')
    if not uid_lookup_path:
      uid_lookup_path = os.path.join(
          FLAGS.model_dir, 'imagenet_synset_to_human_label_map.txt')
    self.node_lookup = self.load(label_lookup_path, uid_lookup_path)

  def load(self, label_lookup_path, uid_lookup_path):
    """Loads a human readable English name for each softmax node.

    Args:
      label_lookup_path: string UID to integer node ID.
      uid_lookup_path: string UID to human-readable string.

    Returns:
      dict from integer node ID to human-readable string.
    """
    if not tf.gfile.Exists(uid_lookup_path):
      tf.logging.fatal('File does not exist %s', uid_lookup_path)
    if not tf.gfile.Exists(label_lookup_path):
      tf.logging.fatal('File does not exist %s', label_lookup_path)

    # Loads mapping from string UID to human-readable string
    proto_as_ascii_lines = tf.gfile.GFile(uid_lookup_path).readlines()
    uid_to_human = {}
    p = re.compile(r'[n\d]*[ \S,]*')
    for line in proto_as_ascii_lines:
      parsed_items = p.findall(line)
      uid = parsed_items[0]
      human_string = parsed_items[2]
      uid_to_human[uid] = human_string

    # Loads mapping from string UID to integer node ID.
    node_id_to_uid = {}
    proto_as_ascii = tf.gfile.GFile(label_lookup_path).readlines()
    for line in proto_as_ascii:
      if line.startswith('  target_class:'):
        target_class = int(line.split(': ')[1])
      if line.startswith('  target_class_string:'):
        target_class_string = line.split(': ')[1]
        node_id_to_uid[target_class] = target_class_string[1:-2]

    # Loads the final mapping of integer node ID to human-readable string
    node_id_to_name = {}
    for key, val in node_id_to_uid.items():
      if val not in uid_to_human:
        tf.logging.fatal('Failed to locate: %s', val)
      name = uid_to_human[val]
      node_id_to_name[key] = name

    return node_id_to_name

  def id_to_string(self, node_id):
    if node_id not in self.node_lookup:
      return ''
    return self.node_lookup[node_id]


def create_graph():
  """Creates a graph from saved GraphDef file and returns a saver."""
  # Creates graph from saved graph_def.pb.
  with tf.gfile.FastGFile(os.path.join(
      FLAGS.model_dir, 'classify_image_graph_def.pb'), 'rb') as f:
    graph_def = tf.GraphDef()
    graph_def.ParseFromString(f.read())
    _ = tf.import_graph_def(graph_def, name='')


def run_inference_on_images(image_list, output_dir):
  """Runs inference on an image list.

  Args:
    image_list: a list of images.
    output_dir: the directory in which image vectors will be saved

  Returns:
    image_to_labels: a dictionary with image file keys and predicted
      text label values
  """
  image_to_labels = defaultdict(list)

  create_graph()

  with tf.Session() as sess:
    # Some useful tensors:
    # 'softmax:0': A tensor containing the normalized prediction across
    #   1000 labels.
    # 'pool_3:0': A tensor containing the next-to-last layer containing 2048
    #   float description of the image.
    # 'DecodeJpeg/contents:0': A tensor containing a string providing JPEG
    #   encoding of the image.
    # Runs the softmax tensor by feeding the image_data as input to the graph.
    softmax_tensor = sess.graph.get_tensor_by_name('softmax:0')

    for image_index, image in enumerate(image_list):
      try:
        print("parsing", image_index, image, "\n")
        if not tf.gfile.Exists(image):
          tf.logging.fatal('File does not exist %s', image)

        with tf.gfile.FastGFile(image, 'rb') as f:
          image_data =  f.read()

          predictions = sess.run(softmax_tensor,
                          {'DecodeJpeg/contents:0': image_data})

          predictions = np.squeeze(predictions)

          ###
          # Get penultimate layer weights
          ###

          feature_tensor = sess.graph.get_tensor_by_name('pool_3:0')
          feature_set = sess.run(feature_tensor,
                          {'DecodeJpeg/contents:0': image_data})
          feature_vector = np.squeeze(feature_set)        
          outfile_name = os.path.basename(image) + ".npz"
          out_path = os.path.join(output_dir, outfile_name)
          np.savetxt(out_path, feature_vector, delimiter=',')

          # Creates node ID --> English string lookup.
          node_lookup = NodeLookup()

          top_k = predictions.argsort()[-FLAGS.num_top_predictions:][::-1]
          for node_id in top_k:
            human_string = node_lookup.id_to_string(node_id)
            score = predictions[node_id]
            print("results for", image)
            print('%s (score = %.5f)' % (human_string, score))
            print("\n")

            image_to_labels[image].append(
              {
                "labels": human_string,
                "score": str(score)
              }
            )

        # close the open file handlers
        proc = psutil.Process()
        open_files = proc.open_files()

        for open_file in open_files:
          file_handler = getattr(open_file, "fd")
          os.close(file_handler)
      except:
        print('could not process image index',image_index,'image', image)

  return image_to_labels


def maybe_download_and_extract():
  """Download and extract model tar file."""
  dest_directory = FLAGS.model_dir
  if not os.path.exists(dest_directory):
    os.makedirs(dest_directory)
  filename = DATA_URL.split('/')[-1]
  filepath = os.path.join(dest_directory, filename)
  if not os.path.exists(filepath):
    def _progress(count, block_size, total_size):
      sys.stdout.write('\r>> Downloading %s %.1f%%' % (
          filename, float(count * block_size) / float(total_size) * 100.0))
      sys.stdout.flush()
    filepath, _ = urllib.request.urlretrieve(DATA_URL, filepath, _progress)
    print()
    statinfo = os.stat(filepath)
    print('Succesfully downloaded', filename, statinfo.st_size, 'bytes.')
  tarfile.open(filepath, 'r:gz').extractall(dest_directory)


def main(_):
  maybe_download_and_extract()
  if len(sys.argv) < 2:
    print("please provide a glob path to one or more images, e.g.")
    print("python classify_image_modified.py '../cats/*.jpg'")
    sys.exit()

  else:
    output_dir = "image_vectors"
    if not os.path.exists(output_dir):
      os.makedirs(output_dir)

    images = glob.glob(sys.argv[1])
    image_to_labels = run_inference_on_images(images, output_dir)

    with open("image_to_labels.json", "w") as img_to_labels_out:
      json.dump(image_to_labels, img_to_labels_out)

    print("all done")
if __name__ == '__main__':
  tf.app.run()
Duhaime
источник
5

Вы можете использовать Perceptual Image Diff

Это утилита командной строки, которая сравнивает два изображения с помощью метрики восприятия. То есть он использует вычислительную модель зрительной системы человека, чтобы определить, отличаются ли два изображения визуально, поэтому незначительные изменения в пикселях игнорируются. Кроме того, это резко снижает количество ложных срабатываний, вызванных различиями в генерации случайных чисел, различиями ОС или архитектуры машин.

Алехандро Болонья
источник
4

Это сложная проблема! Это зависит от того, насколько точным вам нужно быть, и от того, с какими изображениями вы работаете. Вы можете использовать гистограммы для сравнения цветов, но это, очевидно, не принимает во внимание пространственное распределение этих цветов в изображениях (то есть формы). Обнаружение краев с последующей некоторой сегментацией (например, выделение форм) может обеспечить шаблон для сопоставления с другим изображением. Вы можете использовать матрицы согласованности для сравнения текстур, рассматривая изображения как матрицы значений пикселей и сравнивая эти матрицы. Есть несколько хороших книг по сопоставлению изображений и машинному зрению - поиск на Amazon найдет их.

Надеюсь это поможет!

Бен
источник
3

Некоторые программные решения для распознавания изображений на самом деле не основаны исключительно на алгоритмах, а вместо этого используют концепцию нейронной сети . Посетите http://en.wikipedia.org/wiki/Artificial_neural_network, а именно NeuronDotNet, который также включает интересные образцы: http://neurondotnet.freehostia.com/index.html

петр к.
источник
1
Ссылка на nerondotnet.freehostia.com мертва
Моника Хедднек
3

Есть похожие исследования с использованием нейронных сетей Кохонена / самоорганизующихся карт.

Существуют как более академические системы (Google для PicSOM), так и менее академические
( http://www.generation5.org/content/2004/aiSomPic.asp , (возможно, не подходящие для всех рабочих сред)) презентации.

EPa
источник
3

Вычисление суммы квадратов разностей значений цвета пикселей в резко уменьшенной версии (например, 6x6 пикселей) работает хорошо. Одинаковые изображения дают 0, похожие изображения дают маленькие числа, разные изображения дают большие.

Идея других ребят, упомянутых выше, проникнуть в YUV, сначала звучит интригующе - хотя моя идея отлично работает, я хочу, чтобы мои изображения вычислялись как «разные», чтобы получить правильный результат - даже с точки зрения дальтоника.

Крис
источник
2

Это похоже на проблему со зрением. Возможно, вы захотите изучить Adaptive Boosting, а также алгоритм извлечения строк Burns. Концепции этих двух должны помочь в решении этой проблемы. Обнаружение краев - еще более простое место для начала, если вы новичок в алгоритмах зрения, поскольку оно объясняет основы.

Что касается параметров категоризации:

  • Цветовая палитра и расположение (расчет градиента, гистограмма цветов)
  • Содержащиеся формы (Ada. Boosting / Обучение обнаружению форм)
скажи что
источник
2

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

Например, для анализа квадратов можно получить сумму значений цвета.


источник
1

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

Темный Шикари
источник
1

В качестве первого прохода вы можете попробовать использовать цветовые гистограммы. Однако вам действительно нужно сузить область своей проблемы. Общее сопоставление изображений - очень сложная проблема.

Дима
источник
1

Приносим извинения за то, что присоединились к позднему обсуждению

Мы даже можем использовать методологию ORB для обнаружения точек схожих характеристик между двумя изображениями. Следующая ссылка дает прямую реализацию ORB в python

http://scikit-image.org/docs/dev/auto_examples/plot_orb.html

Даже openCV имеет прямую реализацию ORB. Если вы больше информации, следуйте исследовательской статье, приведенной ниже.

https://www.researchgate.net/publication/292157133_Image_Matching_Using_SIFT_SURF_BRIEF_and_ORB_Performance_Comparison_for_Distorted_Images

Вивек Сринивасан
источник
0

В другой ветке есть несколько хороших ответов по этому поводу, но мне интересно, сработает ли что-нибудь, связанное со спектральным анализом? То есть, разбейте изображение на информацию о фазе и амплитуде и сравните их. Это поможет избежать некоторых проблем с кадрированием, трансформацией и различиями в интенсивности. Во всяком случае, это всего лишь мои предположения, поскольку это кажется интересной проблемой. Если вы искали http://scholar.google.com, я уверен, что вы могли бы найти несколько статей по этому поводу.

нейрогай123
источник
Спектральный анализ выполняется с помощью преобразования Фурье, цветовой гистограммы отсутствует, поскольку вы можете восстановить изображение из двух частей - воображаемой и реальной. (не знаю, сработает ли это, просто сообщаю, что это не из этой категории).
nlucaroni
Да, я имел в виду преобразование Фурье.
Neuroguy123,