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

Привет, Хабр!

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

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

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

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

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

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

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

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

 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∈Aif(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.

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

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

P.s.

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