% Тут используется класс, установленный на сервере Papeeria. На случай, если
% текст понадобится редактировать где-то в другом месте, рядом лежит файл matmex-diploma-custom.cls
% который в момент своего создания был идентичен классу, установленному на сервере.
% Для того, чтобы им воспользоваться, замените matmex-diploma на matmex-diploma-custom
% Если вы работаете исключительно в Papeeria то мы настоятельно рекомендуем пользоваться
% классом matmex-diploma, поскольку он будет автоматически обновляться по мере внесения корректив
%

% По умолчанию используется шрифт 14 размера. Если нужен 12-й шрифт, уберите опцию [14pt]
\documentclass[14pt]{matmex-diploma}
%\documentclass[14pt]{matmex-diploma-custom}
\usepackage{amsmath}


\begin{document}
% Год, город, название университета и факультета предопределены,
% но можно и поменять.
% Если англоязычная титульная страница не нужна, то ее можно просто удалить.
\filltitle{ru}{
    chair              = {Кафедра информационно-аналитических систем},
    title              = {Разработка и улучшение алгоритма построения тепловых карт},
    % Здесь указывается тип работы. Возможные значения:
    %   coursework - Курсовая работа
    %   diploma - Диплом специалиста
    %   master - Диплом магистра
    %   bachelor - Диплом бакалавра
    type               = {bachelor},
    position           = {студента},
    group              = 441,
    author             = {Машарский Станислав Сергеевич},
    supervisorPosition = {к. ф.-м. н., доцент},
    supervisor         = {Михайлова Е. Г.},
    reviewerPosition   = {Старший специалист по тестированию},
    reviewer           = {Бухмастов Д. С.},
    university         = {Санкт-Петербургский Государственный Университет},
    faculty            = {Математико-механический факультет},
    city               = {Санкт-Петербург},
    year               = {2019}
}
\filltitle{en}{
    type               = {bachelor},
    chair              = {Dept. of Analytical Information Systems},
    title              = {Development and improvement of the heat mapping algorithm},
    faculty            = {Mathematics and Mechanics Faculty},
    author             = {Stanislav Masharskii},
    supervisorPosition = {Associate professor},
    supervisor         = {Elena Mikhailova},
    reviewerPosition   = {Senior QA \& Testing Analyst},
    reviewer           = {Dmitry Bukhmastov},
    year               = {2019}
}
\maketitle
\tableofcontents



% У введения нет номера главы
\section*{Введение}
В настоящее время собирается очень большое количество данных,
которые можно как-то анализировать и использовать.
Делать это вручную долго и утомительно, поэтому учёные разрабатывают
различные алгоритмы, агрегирующие каким-то образом эти данные в
данные меньшего объёма, которые анализировать проще.
Например, предприятия хотят знать о наиболее популярных местах
передвижений людей по своей территории, в таких местах обычно
устанавливаются видеокамеры.

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

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



\section{План работы}
Целью работы является разработка алгоритма, агрегирующего данные с видеозаписей
таким образом, чтобы можно было легко узнать и увидеть,
в какой области происходило больше движений людей.

Для достижения цели были поставлены задачи:
\begin{enumerate}
    \item Разработка алгоритма
    \begin{enumerate}
        \item Разработка алгоритма обнаружения движений
        \item Разработка алгоритма нейтрализации помех
    \end{enumerate}
    \item Ускорение алгоритма
\end{enumerate}



\section{Разработка алгоритма}
Был разработан алгоритм, агрегирующий в каждом пикселе исходной
видеозаписи количество движений, происходивших в нём.

Для работы с видео и обработки кадров из него была выбрана популярная
библиотека OpenCV, написанная на C++ и предоставляющая функции для работы
с изображениями и видео на этом языке. На данный момент она предоставляет
наибольший функционал.



\newpage
\subsection{Обнаружение движений}
Вся информация о видеофайле и кадры из него считываются программой спомощью
соответствующих методов из библиотеки OpenCV.
В начале алгоритма заводится двумерный массив $\mathtt{Counters}$ такого же размера,
как разрешение видеозаписи, и заполняется нулями.

Для определения наличия движения на видеозаписи рассматривается
симметрическая разность двух последовательно идущих кадров.
Далее применяется фильтр binary thresholding \cite{opencv:tutorial_threshold},
который делает следующее:


\[ \mathtt{dst} (x, y) = \left\{
\begin{array}{ll}
\mathtt{maxVal} & \textrm{если } \mathtt{src} (x, y) > \mathtt{thresh} \textrm{,}\\
0 & \textrm{иначе.}
\end{array}
\right. \]

где $x$ -- номер пикселя по горизонтали,
$y$ -- номер пикселя по вертикали,
$\mathtt{thresh}$ -- планка, которую должна превосходить интенсивность каждого канала в пикселе,
$\mathtt{maxVal}$ -- значение, которое присваивается пиклесям, преодолевшим планку,
в данном алгоритме это $255$,
$\mathtt{src}$ -- исходное изображение,
$\mathtt{dst}$ -- результирующее изображение.

Здесь важно отметить, что если $src$ был многоканальным изображением,
то $\mathtt{dst}$ -- это уже однокональное изображение, в котором пиксели бывают
только интенсивности $0$ либо $255$, т.е. изображение даже бинарное
и к нему можно будет применять соответствующие алгоритмы.

Для выделения областей активности, то есть тех областей, в которых теперь
интенсивность пикселя $255$, применяется алгоритм поиска контуров \cite{find_contours}.
Каждый контур -- это набор точек, задающих полигон при последовательном соединении.
Затем для каждого контура применяем алгоритм поиска выпуклой оболочки \cite{convex_hull},
возвращающий набор точек, при последовательном соединении которых получается
выпуклый многоугольник, ограничивающий контур.
Данная выпуклая оболочка считается местом, в котором происходило движение.

Осталось только инкрементировать значение счётчиков в матрице $\mathtt{Counters}$
на соответствующих позициях.

Чтобы это сделать, нужно будет пройтись по каждому
пикселю $(x, y)$ и если точка лежит в выпуклой оболочке
(проверяется за $O(k)$, где $k$ -- количество точек в оболочке,
проходом по направлению "по часовой стрелке" по каждому ребру и проверкой,
что точка "правее" ребра). Такой подход потребует $\mathcal{O} \left(w \cdot h \cdot \sum\limits_{c \in C} \lVert c \rVert \right)$
операций, где $w$ -- количество пикселей по вертикали,
$h$ -- количество пикселей по горизонтали,
$C$ -- множество найденных выпуклых оболочек.
$h$ и $w$ могут быть довольно велики, например при разрешении видеозаписи
1920x1080 px произведение $w \cdot h$ из асимптотики будет примерно $2$ миллиона,
что непозволительно много.

Ввиду вышесказанного перед записью результатов для каждой выпуклой оболочки
ищется обрамляющий её прямоугольник, с которым сильно проще работать.
Прямоугольники ищутся за $\mathcal{O} \left(\sum\limits_{c \in C}{\lVert c \rVert} \right)$.
Затем проходимся по каждому прямоугольнику (по каждой строке в нём)
и инкрементируем значения счётчиков $\mathtt{Counters}$ в соответствующих точках.
Данный подход потребует $\mathcal{O} \left(\sum\limits_{c \in C}{\lVert c \rVert} + \sum\limits_{p \in P} S(p) \right)$,
где $C$ -- множество найденных выпуклых оболочек,
$P$ -- множество ограничивающих выпуклые оболочки прямоугольников,
$S(p)$ -- площадь прямоугольника $p$, то есть количество пикселеё в нём.
Такой подход сильно более эффективен, особенно если выпуклых оболочек было
найдено не много и их площадь сильно меньше площади всего кадра.



\newpage
\subsection{Нейтрализация помех}
Для нейтрализации шума на изображении, к каждому кадру применяется размытие,
то есть усреднение определённым образом значения интенсивности в пикселе
с учётом значений в соседних пикселях.

Как компромиссное решение для быстрого и плавного сглаживания было выбрано
размытие gaussian blur \cite{gaussian_blur_1} \cite{gaussian_blur_2}
c ядром $5$ на $5$ пикселей, то есть усредняться значение
интенсивностей каналов в пиклелях будет с учётом
соседних $24$-х пикселей, стоящих вокруг текущего.

Значения интенсивностей пикселей в обработанном изображении вычисляется
по следующей формуле:

$G(x, y) = \frac{1}{2\pi\sigma^2} e^{(-\frac{x^2+y^2}{2\sigma^2})}$,

где $x$ -- координата текущего пикселя по горизонтали,
$y$ -- координата текущего пикселя по вертикали,
$\sigma$ -- параметр сглаживания и автоматически вычисляется при заданном размере ядра.


\vspace{\baselineskip}
На видеозаписях также есть более сильные помехи, иногда на изображении
размера 1920x1080 px появляются на один кадр совершенно другие блоки
случайно расположенные и размера примерно 40x40 px, похожие на такое:
% Здесь вставить снимок с кучей крупных шумов

Чтобы они не учитывались,
после рассмотрения абсолютной разности между кадрами и binary thresholding
к полученному изображению применяются последовательно несколько раз
две фундаментальные операции в морфологической обработке изображений:
erosion и dilation \cite{opencv:tutorial_erosion_and_dilation}. % нужно больше ссылок

Erosion -- это морфология "разъедание", будем использовать её с заданным ядром
размера $n$ на $n$, в центре которого стоит текущий пиксель.
Значения в результирующем изображении получаются с помощью следующей формулы:

$$\mathtt{dst} (x, y) = \min\limits_
    {\substack{\lvert x' \rvert \leq \lfloor n/2 \rfloor \\
               \lvert y' \rvert \leq \lfloor n/2 \rfloor}}
    \mathtt{src} (x + x', y + y')$$

где где $x$ -- номер пикселя по горизонтали,
$y$ -- номер пикселя по вертикали,
$\mathtt{src}$ -- исходное изображение,
$\mathtt{dst}$ -- результирующее изображение.

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

Dilation -- это морфология "раздутие", будем использовать её с заданным ядром
размера $n$ на $n$, в центре которого стоит текущий пиксель.
Значения в результирующем изображении получаются с помощью следующей формулы:


\vspace{\baselineskip}
Сначала применяется dilation (раздутие), потом erosion (сжатие) с одинаковым ядром,
шумовые пятна расширятся и сожмутся обратно.
Если в областях, где были движения людей, в некоторых пикселях или маленьких
подобластях были пропуски (внутри облака движения есть точки нераспознанного движения),
то они тоже примут значение $255$, то есть облако движения будет содержать
внутри только пиксели со значением $255$, без $0$.

% Здесь нужны картинки

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

% Здесь нужны картинки



\newpage
\subsection{Результаты алгоритма}
В итоге получается двумерный массив такого же размера,
как и расширение видеозаписи с камеры,
в котором каждый элемент хранит в себе то, сколько раз было зафиксировано
движение в этом пикселе.
По данной матрице можно производить анализ движения людей,
накладывая её на изображение с камеры.
Можно генерировать картинку, которая будет показывать где происходит больше
движений, можно сравнивать количество движений в том или ином
месте за промежуток времени по сравнению с данными со всех остальных камер.



\section{Ускорение алгоритма}
Так как на обнаружение движения людей не влияет цвет видео, а чёрно-белые
изображения содержат в $3$ раза меньший объём информации и, следовательно,
могут обрабатываться в $3$ раза быстрее, сначала каждый получаемый из видео
кадр проходит через фильтр и становится чёрно-белым. Для этого используеся
специальный фильтр из библиотеки OpenCV.

Значения интенсивности цвета в пикселе в результирующем чёрно-белом изображении
вычисляется по формуле:

$newValue = 0.299 \cdot R + 0.587 \cdot G + 0.114 \cdot B$

где $newValue$ -- интенсивность цвета в новом, обработанном изображении,
$R, G, B$ -- интенсивности красного, зелёного и синего каналов,
которые были в изображении соответственно.

Для уменьшения влияния помех на результат и лучшего выявления движения людей,
а также для ускорения алгоритма, рассматривается
разность не двух соседних кадров, а стоящих через каждые
$10$ кадров. Таким образом, обрабатываются кадры, по времени отстоящие не на
$\frac{1}{24}$ секунды, а на $\frac{5}{12}$ секунды,
что примерно равняется половине секунды и приемлемо для выявления движения людей.

Б\'oльшая часть обработки изображений производится на видеокарте с помощью
технологии CUDA, но на данный момент считывание кадров из видезаписи с диска,
поиск контура и выпуклой оболочки осуществляются процессором
в связи с отсутствием их реализации в OpenCV с помощью CUDA.

% У заключения нет номера главы
\section{Заключение}

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

Алгоритм реализован в виде проекта на языке C++, принимает на вход имя файла
(видеозаписи), анализирует данные и записывает результаты в новый файл
в том же каталоге, что и запущенная программа.

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

Первые две проблемы планируется решать с помощью нейронных сетей,
последнюю с помощью префиксного массива сумм
% не могу найти ни одной статьи с описанием использования
% префиксных сумм для вычисления сумм подмассивов
, состоящий из агрегированных с
интервалом в час данных.

\setmonofont[Mapping=tex-text]{CMU Typewriter Text}
\bibliographystyle{ugost2008ls}
\bibliography{diploma.bib}
\end{document}


@book{saturday_is_monday,
  author    = "Стругацкий, А.Н. and Стругацкий, Б.Н.",
  title     = "Понедельник начинается в субботу",
  address   = "М.",
  editor    = "Иванов",
  publisher = "Детская литература",
  year      = 1965,
  language  = "russian"
}
@book{book:fourier,
  title      = {Ряды и интеграл Фурье: Теория поля. Аналитические и специальные функции. Преобразование Лапласа},
  author     = {Кожевников, Н.И. and Краснощекова, Т.И. and Шишкин, Н.Е.},
  lccn       = {66051327},
  series     = {Избранные главы высшей математики для инженеров и студентов втузов. Задачи и упражнения},
  url        = {http://books.google.ru/books?id=xvXuAAAAMAAJ},
  year       = {1964},
  publisher  = {Наука},
  eprint     = {http://books.google.ru/books?id=xvXuAAAAMAAJ},
  eprinttype = {Google Books}
}

@online{opencv:tutorial_erosion_and_dilation,
  author       = "OpenCV",
  title        = "Eroding and Dilating",
  url          = {https://docs.opencv.org/3.4/db/df6/tutorial_erosion_dilatation.html},
  urldate      = "16.12.2018",
  language     = "english"
}
@online{opencv:tutorial_threshold,
  author       = "OpenCV",
  title        = "Basic Thresholding Operations",
  url          = {https://docs.opencv.org/3.4/db/d8e/tutorial_threshold.html},
  urldate      = "16.12.2018",
  language     = "english"
}

@article{find_contours,
  author    = "Satoshi Suzuki and others",
  title     = "Topological structural analysis of digitized binary images by border following",
  journal   = "Computer Vision, Graphics, and Image Processing",
  pages     = "30(1):32–46",
  year      = 1985,
  language  = "english"
}
@article{convex_hull,
  author    = "Jack Sklansky",
  title     = "Finding the convex hull of a simple polygon",
  journal   = "Pattern Recognition Letters",
  pages     = "1(2):79–83",
  year      = 1982,
  language  = "english"
}
@article{gaussian_blur_1,
  author    = "Shapiro, L. G. \& Stockman",
  title     = "G. C: "Computer Vision"",
  journal   = "Prentice Hall",
  pages     = "137, 150",
  year      = 2001,
  language  = "english"
}
@article{gaussian_blur_2,
  author    = "Mark S. Nixon and Alberto S. Aguado",
  title     = "Feature Extraction and Image Processing",
  journal   = "Academic Press",
  pages     = "88",
  year      = 2008,
  language  = "english"
}