Ищем отличия в изображениях

Привет!

По мотивам статьи Пишем бота для игры «Найди отличие» ^[1] появилась идея реализовать алгоритм поиска сторонних объекта на заданном изображении, используя алгоритмы компьютерного зрения.

Подробности — под катом.

Описание задачи.

Проблема выделения стороннего объекта возникает во многих ситуациях — например в задачах видеорегистрации, когда нужно, допустим, включить сигнализацию при появленнии постороннего лица ночью на охраняемой территории.

При этом главная сложность обработки сигнала состоит в том, что условия регистрации могут меняться — это зависит от времени суток, задымлённости помещения, состояния самого регистратора (например, запылился объектив). Следовательно, необходимо использовать алгоритм, который позволит выделить сторонний объект вне зависимости от условий, в которых производится съёмка.

Сведения из морфологического анализа

Без математического вступления, конечно, не обойтись!

Назовём функцию

 f(x):X → R

изображением. В нашей задаче значение
f(x) будет соответствовать яркости пикселя (в пределах от 0 до 255).

Пусть L — линейное пространство всех изображений, F — класс всех борелевских функций, принимающих числовые значения, F_f — подкласс F: F_f ={F ∈ F: F⊗f(⋅) ∈ L}.

И, наконец, введём важное понятие формы изображения: V_f = {F⊗f:F ∈ F_f} ⊂ L. Итак, под формой изображения понимается максимальный инвариант преобразований изображения, которым оно подвергается при изменении условий наблюдения, изменении параметров съёмки. Понятие формы мы и будем использовать при обработке изображений.

Алгоритм

Основная идея алгоритма — выделить некий максимальный инвариант изображения, с которым потом мы и будем сравнивать поступающие образы. Реализация алгоритма приведена на Python.

from PIL import Image#для работы с изображениями

• 1. Преобразуем входное (цветное) изображение в серое — присвоим каждому пикселю вместо цвета значение яркости в диапазоне [0,255]

  im1 = Image.open('./img/test1.jpg')#открываем файл
  p1 = im1.convert('L')#вычисляем значение яркости для каждого пикселя
  

• 2. Получим кусочно-постоянную аппроксимацию изображения. Необходимо разбить входное (гладкое) изображение на ряд областей постоянной яркости.

  g = ∑^N_i=1 A _i c_i(x),

  где c_i(x) — значение яркости, постоянное для области A _i.

      for i in xrange(p1.size[1]):#цикл по строкам
          for j in xrange(p1.size[0]):#цикл по элементам строки
              for l in xrange(len(split_map[1])):
                  if pix[j,i] in split_map[1][l]:
                      pix[j,i]=split_map[0][l]#присваиваем среднее группе значение яркости,
                      measure[l]+=1# считаем мощность мн-ва
                      break
  

  Мы заранее разбиваем интервал значений яркости на равные промежутки [0,...,a_1],...,[a_m,...,255]. Затем считаем среднее значение яркости по каждой группе. После этого остаётся только пройтись по изображению и присвоить каждому пикселю среднее значение яркости по группе, в которую он попадает. В итоге получаем разбиение входного изображения на ряд областей постоянной яркости A₁,...,A_N. Параллельно мы считаем мощность каждого множества постоянной яркости (т.к. множество дискретное — мощность равна количеству пикселей). Как работает алгоритм на примере:

  Входное изображение

  

  Кусочно-постоянная аппроксимация

  
  Полученная кусочно-постоянная аппроксимация — это и есть форма избражения.

• 3. Теперь поработаем со входным изображением (на котором нам нужно выделить сторонний элемент). Для этого найдём проекцию входного изображения на нашу форму:
  P_Vgf = ∑^N_i=1 = (∑_xsk∈A_if(x_sk)) / (|A|_i) ⋅ c_i(x).

  Другими словами — мы вычисляем для входного изображения нормированное значение яркости на каждом кусочно-постоянном элементе формы.

  def projector(img,split_form):
      p1 = img.convert('L');pix = p1.load();summ = [0]*len(split_form[2][1]);
      for l in xrange(len(split_form[2][1])):#выбираем очередное множество постоянной яркости
          for i in xrange(p1.size[1]):
              for j in xrange(p1.size[0]):    
                  if split_form[3][j,i]==l:
                      summ[l]+=pix[j,i]
          summ[l] = summ[l] / split_form[1][l]#получили "нормированное" значение яркости
      #теперь снова проходимся по всему изображению и приписываем пикселям "нормированную" яркость
      for i in xrange(p1.size[1]):
          for j in xrange(p1.size[0]):    
              if split_form[3][j,i]==l:
                  pix[j,i] = summ[l]
      return p1
  

• 4. Вот и всё! После того, как мы вычислили проекцию на нашу форму — останется только вычесть из нашей формы (исходного изображения кусочно-постоянного изображения, без стороннего объекта) проекцию нового изображения на форму попиксельно.

  Δ = g — P_Vgf

  Разница изображений — как раз и будет искомым объектом.

  def differ(i1,i2):
      map1 = i1.load(); map2 = i2.load()
      for i in xrange(i1.size[1]):#цикл по строкам
          for j in xrange(i1.size[0]):#цикл по элементам строки
              map1[j,i] = map1[j,i] - map2[j,i]
      return i1
  

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

  

  Итог работы скрипта:

  

  Ура! Мы получили сторонний объект на однородном фоне — его не составит труда выделить и распознать. Задача детектирования постороннего объекта решена.

Вывод

Вывод: был реализован алгоритм морфологического анализа изображений — выделение постороннего объекта на изображении при изменённых условиях регистрации, так же получена реализация на Python ^[2].

Использованная литература

• 1. Битюков Ю.И. Лекции по компьютерной геометрии; МАИ, 2012
• 2. Пытьев Ю.П. Методы морфологического анализа изображений; Москва, Физматлит 2010

P.s.

П
Подскажите, как набирать формулы? Хочется видеть в статьях красоту Latex!

Автор: Dju

Источник ^[3]