# ЗАДАЧА СОПОСТАВЛЕНИЯ АВТОМОБИЛЕЙ И ЛЮДЕЙ ПО ДАННЫМ ВИДЕОНАБЛЮДЕНИЯ
_Комментарий к исходным данным задачи и построению алгоритма (метода) решения_

[TOC]

## Основные источники информации
Основным источником информации, по которой строятся и данные профайлов машин и персон и должна строится таблица соответствия между машинами и персонами, являются события, регистрируемые в пунктах наблюдения и предварительно распознаваемые с использованием обученных нейросетей. Эта информация в виде последовательности событий записывается в Mongo.db, сейчас имеющей название okko. Эта последовательность за определенный интервал времени сбрасывается в виде файлов okko_export_records.bson
Вот фрагменты из этого потока (разделенные нами на два отдельных потока - событий для машин и событий для персон):
### а) Пример данных событий машин

{car:
   { car_id: '70ef2d80-57cb-412d-a6b0-d14f23a0827d',
     registrationId: 'AB0164BT',
     mark: 'ISUZU  NLR 85AL',
     model: 'NLR 85AL',
     color: 'БІЛИЙ',
     fuel: 'ДИЗЕЛЬНЕ ПАЛИВО',
     url_foto:      '/okko/vehicle/recognize/2021/03/09/11/27-15.150989-9b15c4cd-3044-4d3a-9ce4-a8b1b042e73d.jpg' },
  event_id: '9b15c4cd-3044-4d3a-9ce4-a8b1b042e73d',
  place_code: '33f0b671-a756-411b-be5a-7036ffd17c61',
  event_type_code: 'Enter',
  event_begin: '2021-03-09T11:27:17.896Z',
  event_end: '2021-03-09T11:27:17.896Z',
  url_foto:   '/okko/vehicle/recognize/2021/03/09/11/27-15.150989-9b15c4cd-3044-4d3a-9ce4-a8b1b042e73d.jpg' }
,
{ car:
   { car_id: '9e60436c-caef-44b8-98c0-da0cb4928fa8',
     registrationId: '0342',
     mark: '',
     model: '',
     color: '',
     fuel: '',
     url_foto:      '/okko/vehicle/recognize/2021/03/09/11/27-27.781143-fa723ea6-9849-41ea-9919-22a92497fbef.jpg' },
  event_id: 'fa723ea6-9849-41ea-9919-22a92497fbef',
  place_code: 'bb523908-f718-45c8-8aa7-bc2d2946b213',
  event_type_code: 'Exit',
  event_begin: '2021-03-09T11:27:34.527Z',
  event_end: '2021-03-09T11:27:34.527Z',
  url_foto:   '/okko/vehicle/recognize/2021/03/09/11/27-27.781143-fa723ea6-9849-41ea-9919-22a92497fbef.jpg' }, …….

### б) Пример данных событий персон

{ customer_event:
   { customer:
      { customer_id: 'c7ba561e-6e74-4e19-b85c-c9d5e6032081',
        gender: 'Male',
        age: 'Child',
        url_foto: '/okko/faces/recognize/2021/03/09/11/25-38.750000-c406a59b-5ded-4454-a30b-50c7723d5572.jpg' },
     event_id: 'c406a59b-5ded-4454-a30b-50c7723d5572',
     place_code: '2dad4312-ac7d-41f7-83c8-2e537ceb5548',
     event_type_code: 'faceEnter',
     event_begin: '2021-03-09T11:25:37.250Z',
     event_end: '2021-03-09T11:25:38.951Z',
     url_foto: '/okko/faces/recognize/2021/03/09/11/25-38.750000-c406a59b-5ded-4454-a30b-50c7723d5572.jpg' } }
,
{ customer_event:
   { customer:
      { customer_id: '887fecea-a384-44d8-9932-47828eeb95c5',
        gender: 'Male',
        age: 'Adult',
        url_foto:         '/okko/faces/recognize/2021/03/09/11/26-04.250000-019bc324-b39d-423c-9cb9-8fdc724c7262.jpg' },
     event_id: '019bc324-b39d-423c-9cb9-8fdc724c7262',
     place_code: '2dad4312-ac7d-41f7-83c8-2e537ceb5548',
     event_type_code: 'faceEnter',
     event_begin: '2021-03-09T11:26:03.249Z',
     event_end: '2021-03-09T11:26:04.818Z',
     url_foto:      '/okko/faces/recognize/2021/03/09/11/26-04.250000-019bc324-b39d-423c-9cb9-8fdc724c7262.jpg' } }
, ……

Исходя из условий задачи, распознавание-идентификация автомобилей происходит с малой долей ошибок и работает, как базовый источник информации по событиям машин. Распознавание персон выполняется пока без однозначной идентификации (по, например, "паспортным данным").

## Оценка параметров пребывания автомобилей на заправке

Вот оценка некоторых параметров пребывания автомобилей на заправке по выборке из 1000 событий (по отфильтрованным нами данным -- брались в расчет вначале полностью идентифицированные события въезда и выезда распознанного автомобиля)
:::info
Минимальное время пребывания на заправке $dt_{min} = 11$ sec (сценарий: *въезд - просмотр цены или занятости - выезд*)
Медианное время пребывания на заправке $dt_{med} = 349$ sec $\approx$ 6 min
Среднее время пребывания на заправке $dt_{avg} = 489$ sec $\approx$ 8 min
Максимальное время пребывания на заправке $dt_{max} = 2706$ sec $\approx$ 45 min (варианты: *отдых, очередь или...*)

Квантильные оценки:

| ¼ quantile | mediana | ¾ quantile |
| -------- | -------- | -------- |
| 218 sec $\approx$ 3.6 min| 349 sec $\approx$ 6 min|574 sec$\approx$ 9.5 min|
:::

Для 55% событий, распознанных, как “Prk”, нет предварительного события "въезда на заправку"...

Кроме того, наблюдается и дублирование событий “Enter”,
::: spoiler например:

  1f6354bd-ab1e-4606-b0c2-4267c5574f68 BT6849BK KIA  MAGENTIS ЧОРНИЙ Enter 2021-03-09T12:47:54.147Z
  for BT6849BK memorized  on enter event time=2021-03-09T12:47:54.147Z

    1f6354bd-ab1e-4606-b0c2-4267c5574f68 BT6849BK KIA  MAGENTIS ЧОРНИЙ Enter 2021-03-09T12:48:20.628Z
    doubled car BT6849BK  on enter .......................................time delta =26.481sec

    1f6354bd-ab1e-4606-b0c2-4267c5574f68 BT6849BK KIA  MAGENTIS ЧОРНИЙ Enter 2021-03-09T12:48:47.862Z
    doubled car BT6849BK  on enter .......................................time delta =53.715sec

:::

---

И очень большое число событий “Exit” без предварительных событий “Enter” и “Prk”,
::: spoiler например:

756_______________________________________________________________________________
                           e9ce05cf-d9f1-4510-a0c1-ee7027e22f6e BH2358IM BMW БІЛИЙ Exit 2021-03-09T12:48:35.111Z 2021-03-09T12:48:35.111Z
                           ?????????????????????????? car BH2358IM  exited without enter event??????????
757_______________________________________________________________________________
758_______________________________________________________________________________
759_______________________________________________________________________________
    1f6354bd-ab1e-4606-b0c2-4267c5574f68 BT6849BK KIA  MAGENTIS ЧОРНИЙ Enter 2021-03-09T12:48:47.862Z
    doubled car BT6849BK  on enter .......................................time delta =53.715sec
760_______________________________________________________________________________
761_______________________________________________________________________________
                           36569fc4-c350-41fb-8678-e20d915dafc3 BH9739AT   Exit 2021-03-09T12:49:28.545Z 2021-03-09T12:49:28.545Z
                           ?????????????????????????? car BH9739AT  exited without enter event??????????
762_______________________________________________________________________________
763_______________________________________________________________________________
764_______________________________________________________________________________
                           754e8b87-112c-4800-97df-c1a919a7c4bc BH0793KO AUDI БЕЖЕВИЙ Exit 2021-03-09T12:49:35.059Z 2021-03-09T12:49:35.059Z
                           ?????????????????????????? car BH0793KO  exited without enter event??????????
765_______________________________________________________________________________
766_______________________________________________________________________________

:::

---

## [Диаграмма пересечения интервалов автомобилей и событий персон](#)

Горизонтально идущие сегменты - интервалы машин по исходным данным. Засечка вверх - старт, засечка вниз - выезд. Изгибы и изломы - распознанные события машин на заправке - prk.
Вертикальные линии (узкие прямоугольники) - события персон (вход в магазин, кассы). Одинаковые цвета вертикальных событий означают распознанного одного и того же человека.
Каждое событие имеет справа подпись (для автомобилей размер шрифта чуть больше)
Время идет слева направо (1 пиксел - 6 секунд, периодически повторяющиеся вертикальные зеленые события - интервалы примерно в 30 минут)

<iframe src="https://cars-persons-vis.glitch.me" width=1250 height=1250></iframe>

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

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

# Модель

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

## Базовые матрицы и функции модели
Исходя из этого, необходимо итеративно строить и уточнять:
1) Адаптивную функцию (матрицу) соответствия событий $H$ для персон $h$ с событиями $V$ для машин $v$ (индексированными интервалами -- определенными и недоопределенными)
$$ P : V\times H \to [ 0; 1 ] $$

2) Оценку близости идентифицированных персон $h_i$ и $h_j$ (возможного соответствия между дублями и/или близко связанных персон)
$$ D : h\times h \to [ 0; 1 ]. $$
>Функция (матрица) $P_{v,h}$ является принципиально асимметричной и, наоборот, функция (матрица) $D_{i,j}$ является симметричной.

3) Функцию соответствия $f:h \to v$ используя информацию матрицы $P$ с учетом ограничений на домены и дополнительных внешних ограничений.

## Ограничения на домены
При этом надо учитывать естественные ограничения на домены этих функций,
а именно:

a) один человек вряд ли приедет на двух машинах, а вот на одной машине могут приехать несколько (в зависимости от класса машины) человек;

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

в) среднее количество зафиксированных лиц, приходящихся на один зафиксированный автомобиль, находится между 1 и 2.

## Итерации и обновления матриц модели
Ограничение а) позволяет ставить задачу построения функции правдоподобия владения и использовать на первом этапе, например, варианты различных жадных алгоритмов и/или динамики.
На каждой итерации мы должны обновлять функции (матрицы) $D: [0;1]^{h\times h}$ и $P: [0;1]^{V\times H}$
После каждого обновления матрицы $D$ может происходить отождествление индексов лиц $i$ и $j$ (ликвидация дублей) и соответствующее обновление (объединение столбцов) матрицы $P$.
Выбирая элементы с максимальными долями в строках матрицы $P$, с учетом ограничения (в), мы получаем очередной вариант функции $f:h \to v$.
Полученную функцию $f$ мы можем использовать для последующей минимизации дублей с учетом ограничения (б)
Работа цепочки итераций должна останавливаться при отсутствии значимых изменений в матрицах $D$, $P$ и функции $f$

# Компоненты алгоритма

## Обнаружение интервала присутствия машины
>Метод обнаружения интервала присутствия машины из последовательности отдельных событий кажется интутивно понятным и простым. Но лучше поставить эту задачу достаточно формально, чтобы можно было обсуждать возможные тонкие моменты этой процедуры

Поскольку некоторые события могут отсутствовать в потоке данных, необходимо это учесть при обнаружении интервала и определения его параметров.
Рассмотрим определение интервала $I$ в виде контекстно свободной грамматики с $\epsilon$ правилами и дополнительным символом $\tau$, обозначающим время недопустимой задержки:

$$
I \to B P E \\
B \to b \tau | bB | \epsilon \\
P \to p \tau | pP | \epsilon \\
E \to e \tau | eE | \epsilon
$$

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

$I$ - нетерминал, означающий полностью построенный интервал из отдельных событий. Интервал в идеале должен состоять из начала ( B ), событий prk ( P ) и окончания ( E ). Однако в реальности из всех этих трех частей может присутствовать, например, только одна.
$B$ - нетерминал, означающий начало интервала $I$. Это начало может состоять из одного или нескольких подряд идущих событий $b$ (begin_event), расстояние между которыми во времени не должно превышать $\tau$.
$P$ - нетерминал, означающий последовательность событий prk внутри интервала $I$.
$E$ - нетерминал, означающий выезд машины с заправки и завершение интервала $I$.
Выезд также может состоять из одного или нескольких подряд идущих событий $e$ (exit_event), расстояние между которыми во времени не должно превышать $\tau$.

$\epsilon$ правила в этой грамматике нужны для учета выпадания какой-то части событий из определения интервала. Для написания кода распознавания интервала надо избавиться от $\epsilon$ правил. После процедуры избавления от $\epsilon$ правил и добавления атрибутивных действий грамматика принимает вид:

$$
I \to B \quad \{ \text{ I.recoveryFromB() } \}\\
I \to P \quad \{ \text{I.recoveryFromP() } \} \\
I \to E \quad \{ \text{I.recoveryFromE() } \} \\
I \to BP \quad \{ \text{I.recoveryFromBP() } \} \\
I \to BE \quad \{ \text{I.recoveryFromBE() } \} \\
I \to PE \quad \{ \text{I.recoveryFromPE() } \} \\
I \to B P E \quad \{ \text{ I.contsructFromBPE() } \} \\
B \to b\tau \quad \{ \text{I.close()} \} \\
P \to p\tau \quad \{ \text{I.close()} \} \\
E \to e\tau \quad \{ \text{I.close()} \} \\
B \to bB \quad \{ \text{I.push} \, (b, t_b ) \} \\
P \to pP \quad \{ \text{I.push} \, (p, t_p ) \} \\
E \to eE \quad \{ \text{I.push} \, (e, t_e ) \}
$$

Время $\tau$ недопустимой задержки может задаваться одним значением для всех событий интервала, либо для каждого типа события своим значением.
В процессе распознавания необходимо формировать список событий интервала $I$ со штампами времени. Эта работа обозначается действиями в фигурных скобках, сопоставленных соответствующим правилам вывода.
По окончании распознавания интервала, необходимо обработать сформированный список элементарных событий интервала и сформировать границы и важные внутренние точки как полностью (*I.contsructFrom(B,P,E)*), так и частично определенного интервала (*I.recoveryFrom( B ), I.recoveryFrom( P ), ...*). Также необходимо принять решение, что делать с событиями, нарушающими естественную (и поэтому жестко закрепленную в грамматике) последовательность событий интервала.

## Группировка событий
Желательно обрабатывать события, сгруппировав их относительно идентификаторов машин.

:::spoiler Примеры предварительной обработки событий

Выполнив следующий запрос, мы получим таблицу, удобную для обработки процедурными языками (например c++ или процедурами и функциями SQL)

/****** Script for Select N Rows of car events for subsequent  interval interval detection******/
DECLARE @startDate           as DateTime
     SET @startDate = CAST('2021-03-09' as date)
SELECT TOP (1000000)
       [car_id],
       [place_id],
       [event_type_id],
             DATEDIFF(MILLISECOND,@startDate,event_begin)/1000.0 
       [t],
             DATEDIFF(MILLISECOND,event_begin,event_end)/1000.0  
       [dt]
  FROM cars_events
  group by car_id,event_begin,event_end,place_id,event_type_id
  order by car_id,event_begin

car_id p_id e_type	t	          dt
16289	7	2	41237.896000	0.000000
16289	13	6	41444.473000	283.640000
16289	5	4	41709.313000	0.000000
16290	5	4	41254.526000	0.000000
16291	7	2	41259.686000	0.000000
16291	7	2	138807.900000	0.000000
16291	7	2	138871.210000	0.000000
16291	7	2	138919.190000	0.000000
16291	7	2	299098.353000	0.000000
16291	7	2	299136.466000	0.000000
16291	7	2	299172.373000	0.000000
16291	7	2	299203.056000	0.000000
16291	7	2	299231.240000	0.000000
16291	7	2	299255.866000	0.000000
16291	7	2	299283.246000	0.000000
16292	7	2	41264.860000	0.000000
16292	5	4	42957.183000	0.000000
16293	5	4	41272.776000	0.000000
16294	16	6	41281.440000	414.140000
16294	5	4	41715.470000	0.000000
16294	23	6	1327696.476000	727.987000
16294	5	4	1328491.446000	0.000000
16295	18	6	41284.326000	38.854000
16295	5	4	41351.570000	0.000000

Аналогично, выполнив следующий запрос, мы получим таблицу, удобную для обработки процедурными языками (например c++ или процедурами и функциями SQL)

/****** Script for Select N Rows of customer events for subsequent  interval interval detection******/
DECLARE @startDate           as DateTime
     SET @startDate = CAST('2021-03-09' as date)

SELECT TOP (1000000) 
      [customer_id]
      ,[place_id]
      ,[event_type_id]
     -- ,[event_begin]
     -- ,[event_end]
	  ,       DATEDIFF(MILLISECOND,@startDate,event_begin)/1000.0 
       [t],
             DATEDIFF(MILLISECOND,event_begin,event_end)/1000.0  
       [dt]
  FROM customer_events
  group by customer_id,event_begin,event_end,place_id,event_type_id
  order by customer_id,event_begin

cust_id p_id e_type	t	          dt
28316	3	3	41137.250000	1.700000
28317	3	3	41163.250000	1.566000
28318	3	3	41197.250000	6.700000
28318	3	3	42766.583000	1.933000
28318	3	3	44335.353000	0.633000
28318	3	3	46255.150000	0.500000
28318	3	3	1075574.626000	1.300000
28318	3	3	1077769.726000	1.200000
28318	3	3	1244268.510000	0.366000
28318	3	3	1249386.156000	5.100000
28318	3	3	1702511.180000	1.300000
28319	4	5	41173.426000	49.790000
28319	4	5	41238.210000	20.516000
28319	4	5	41274.200000	4.680000
28319	4	5	41283.796000	23.634000

:::

## Функции начальной оценки принадлежности лица интервалу машины

>Функции оценки принадлежности человека интервалу машины служат для начальной оценки связи персоны и машины на ее интервале присутствия на заправке.
Поскольку для одного профиля человека могут присутствовать несколько его событий на одном и том же интервале, то необходимо уточнить процедуру использования этих функций.
А именно, если на данном интервале все события одного человека попадают в "зеленую зону" (ненулевые значения), то из оценок выбирается максимальное значение. Если хотя бы одно из событий находится вне "зеленой" зоны, то оценка всего множества событий персоны равна 0 (профиль человека просто не учитывается для данного интервала).

В порядке неубывания количества параметров можно рассматривать следующие варианты функции оценки принадлежности к интервалу:
1) Треугольная симметричная: $\mu_0$ - вершина над центром допустимой части интервала (два параметра - $d_s$ и $d_e$)
<iframe src="https://www.desmos.com/calculator/hjzvwdaqxi?embed" width="500px" height="150px" style="border: 1px solid #ccc" frameborder=0></iframe>

2) Треугольная, зависящая от времени события prk: $\mu_1$ - вершина над первым событием prk (также два параметра - $d_s$ и $d_e$)
<iframe src="https://www.desmos.com/calculator/ugzd4yy6hw?embed" width="500px" height="150px" style="border: 1px solid #ccc" frameborder=0></iframe>

3) Трапециевидная $\mu_2$, обобщающая простые функции $\mu_0$ и $\mu_1$ (четыре параметра - $d_s$ и $d_e$, $d_0$ и $d_3$)
<iframe src="https://www.desmos.com/calculator/e85f3cyokm?embed" width="500px" height="150px" style="border: 1px solid #ccc" frameborder=0></iframe>

Более сложные варианты можно проверять после сравнительной проверки $\mu_0$,$\mu_1$ и $\mu_2$ по эффективности первоначальных фильтрации и взвешивания событий персон.

## Матрица *P* соответствия машин и персон

Функции принадлежности интервалу позволяют строить начальную матрицу соответствия.
$$ P : V\times H \to [ 0; 1 ] $$

Эта матрица должна индексироваться:
по оси $V$ - парой (идентификатор авто, номер в порядке повторного посещения заправки),
по оси $H$ - парой (код персоны, номер в порядке повторного распознавания вне одного интервала)

Для адаптивной каузальной коррекции элементов матрицы необходимо выполнять нормировки строк и столбцов и поддерживать следующие ограничения:
$$
S_v = \sum_h P_{v,h} = 1 \\
S_h = \sum_v P_{v,h} = 1
$$

Элементы строки $v$ матрицы $P$ могут быть проинтерпретированы как **оценки правдоподобия владения персонами $h$ машины $v$** или как оценка использования персонами машины $v$.
Элементы столбца $h$ матрицы $P$ могут интерпретироваться как **оценки правдоподобия принадлежности машин $v$ персоне $h$** (для машин из множества, присутствующих одновременно с этой персоной на заправке).

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

> Такая форма матрицы позволяет применять оптимизированные методы обновления и поддержки ограничений субквадратичной сложности.

## Матрица *D* близости идентификаторов персон

1) Диагональ $D_{i,i}$ заполняется единицами

2) Заполнение недиагональных элементов $D_{i,j}$ выполняется для лиц, попавших на один интервал $I$, и зависит от данных распознавания (мужчина/женщина, взрослый/ребенок) и расстояния по времени между ними, например, по формуле:

$$ D_{i,j} = \max_{\text{all}\, I} c_{i,j}\left(1-\min_{I}\frac{|t_i-t_j|}{|I|} \right),$$

где $t_i$ и $t_j$ - моменты времени распознавания лиц $i$ и $j$ во время пребывания в одном интервале $I$, $\; \; 0\le c_{i,j} \le 1$ - коррелятор распознанных признаков лиц $i$ и $j$.

## Корректоры весов при повторных посещениях автомобилем заправки

### Корректор весов матрицы *D*

Пусть $a$ - номер интервала одного посещения машиной заправки, $b$ - номер любого другого и, соответственно, $i_a$ - индекс лица $i$ при посещении $a$, а $j_b$ - индекс лица $j$ при посещении $b$.

Тогда
$$ D'_{i,j} = \max_{a,b} \left(1 -(1-D_{i_a,j_b})^n \right),$$
где $1\lt n$ - параметр алгоритма.
Этот корректор не изменяет диагональ матрицы $D$, но изменяет (быстро увеличивает) ненулевые веса, если на множестве повторных интервалов встречается хотя бы одна пара близких персон. При достижении определенного порога может происходить отождествление индексов лиц $i$ и $j$ (при соответвующем корреляторе распознанных признаков) или внесение лиц $i$ и $j$ в список близких людей.

### Корректоры элементов матрицы *P*

1) Для всех пар $I_a$, $I_b$ - номеров интервалов повторного посещения машиной заправки, для которых встречается событие персоны $j=j_a=j_b$ :

$$ P'_{I_a,j_a}= P'_{I_b,j_b} = \max \left(
1 -(1-P_{I_a,j_a})^m, 1 -(1-P_{I_b,j_b})^m
\right),$$
где $1\lt m$ -- параметр алгоритма.

2) Если для всех пар $I_a$, $I_b$ - номеров интервалов повторного посещения машиной заправки - нет повторного события персоны $j=j_a=j_b$, то

$$ P'_{I_a,j_a} = P_{I_a,j_a}/l \\ P'_{I_b,j_b} = P_{I_b,j_b}/l$$

где $1\lt l$ -- параметр алгоритма.

3) После шагов (1) и (2) выполняется нормировка измененных строк матрицы $P$.

# Алгоритм

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

## Базовые этапы алгоритма

### 1. Инициализация
::: spoiler
На этом этапе происходит импорт (использование) данных таблиц событий для машин (car_events) и для людей (customer_events).
Задаются начальные значения параметров алгоритма и выбирается функция начальной оценки принадлежности интервалу присутствия машины.
С использованием выбранных параметров и функции оценки принадлежности, инициализируются матрицы $P$ и $D$.
:::

### 2. Начальная коррекция
::: spoiler
На этом этапе происходит начальная коррекция матриц $P$ и $D$. Эта работа выполняется на отдельном шаге в связи с тем, что она должна будет выполняться повторно при очередном получении нового блока событий car_events и customer_events, дополняющего уже имеющиеся события.
Список откорректированных строк и столбцов запоминается для дальнейшей работы.
:::

### 3. Определение близости и удаление дубликатов персон
::: spoiler
На этом этапе происходит оценка матрицы $D$ и производится попытка обнаружить дубликаты (с некоторой вероятностью) и при условии их обнаружения удалить дубликаты в матрицах $P$ и $D$.
Строки матрицы $P$ после удаления элементов перенормируются.
:::
### 4. Определение терминалов лент событий
::: spoiler
На этом этапе происходит поиск терминалов (левых и правых краев) в лентах событий посещений автомобилями заправки. Для этих терминалов выполняется коррекция матриц $D$ и $P$ и происходит отметка строк матрицы $P$ с терминальными событиями
:::

### 5. Глобальная корректировка матрицы *P*
::: spoiler
На этом этапе происходит корректировка матрицы *P* для удовлетворения глобальных нормировочных ограничений при фиксации маркированных строк. Ленточная структура матрицы *P* позволяет выполнить этот шаг за разумное время.
:::

### 6. Корректировка матрицы *D* и выдача варианта функции *f*
::: spoiler
По полученным данным нормализованной матрицы *P* корректируется матрица *D* (по максимальным весам строк матрицы *P*). По этим же данным и формируется вариант функции соответствия *f*
:::

### 7. Адаптация и реинициализация
::: spoiler
На этом этапе должен выполняться процесс адаптации начальных параметров, возможный выбор альтернативных вариантов функции $\mu$ и параметров алгоритма. После этого должна проводиться реинициализация алгоритма.
:::

**При поступлении нового блока событий шаги, начиная с шага 2, повторяются.**

## Псевдокод

//step 1. Initialization
 import (car_events, customer_events)
 Initialize (function mu)
  Initialize(matrix P)
  Initialize(matrix D) 

repeat on new eventsBlocks (car_events, customer_events)
{
//step 2. Initial  сorrection
  getAddtionalEvents(car_events, customer_events)
   initialCorrection(D)
   initialCorrection(P)
    markCorrectedLinesOf(P)
    
//step 3. Reveal and Delete dublicates
    Hdup = revealDuplicate(D)
     deleteDuplicatesInH(Hdup)
      deleteDuplicatesInP(Hdup)
       markCorrectedLinesOf(P)
        normalizeCorrectedLinesOf(P)
        
 //step 4. Reveal and Mark CarEventsRibbon Terminals
      RevealTerminalsIn(P)
       correctByTerminals(P)
       correctByTerminals(D)
        markCorrectedLinesOf(P)
        
 //step 5. Global Correction of matrix P
      fixMarkedLines(P)
       GlobalCorectionOf(P)
 
 //step 6. Final correction D and yielding function f and  matrix D
      finalCorrectionOf(D)
       yield function f, matrix D
          
//step 7. Adaptation and reinitialization 
        adaptInitialParameters()
          reInitialize (function mu)          
 }