@@ -1,35 +1,306 @@
-- Каскад Хаара
+= Каскад Хаара
+
+
+- Гильза
+
+	* Допустим, у нас есть один миллион изображений: полмиллиона изборажений мотоциклов и полмиллиона изображений не-мотоциклов (это называется ''обучающая выборка''). В реальности, кстати, такая чудная ситуация (доля мотоциклов равно доле не-мотоциклов) бывает чрезвычайно редко.
+	* Мы хотим научить компьютер отличать изображения мотоциклов от изображений не-мотоциклов. Для этого мы проводим обучение. Сначала мы «рассказываем» компьютеру, что является мотоциклом, а что не является. Это называется ''обучение с учителем'', если компьютер неким образом сам смог бы научиться распознавать мотоциклы от не-мотоциклов без внешней помощи, то это было бы ''обучение без учителя'': подробнее смотри статью: ...
+	* После обучения бы даём компьютеру миллионпервое изображение, а компьютер выдаёт 1 («ДА», «ИСТИНА», «это мотоцикл»), если это изображение мотоцикла, и -1 («НЕТ», «ЛОЖЬ», «это не-мотоцикл»), если это изображение не-мотоцикла. В реальной практике мы даём не одно изображение, а, допустим, сто тысяч (эти сто тысяч называются ''тестовой выборкой''). По тому, как компьютер научился разделять мотоциклы от не-мотоциклов, мы судим о качестве нашего обучения. Для этого чаще всего используются следующие показатели: 
+		* доля верно определённых мотоциклов (на изображении мотоцикл, компьютер определил его как мотоцикл: TP — True Positive), 
+		* доля верно определённых не-мотциклов (на изображении не-мотоцикл, компьютер определел его не-мотоцикл: TN — True Negative), 
+		* доля неверно определённых не-мотоциклов (на изображении не-мотоцикл, но компьютер ошибся и определил его  как мотоцикл: FP — False Positive): например, мы не научили различать мотоциклы и велосипеды,
+		* доля неверно определённых мотоциклов (на изображении мотоцикл, компьютер его определил как не-мотоцикл: FN — False Negative): например, мы не научили различать мотоциклы с человеком на нём, обучали только по мотоциклам без водителя.
+	* Таким образом, компьютер проводит разделение поступающего множество на два класса, или, говоря иначе, выполняет задачу ''классификации''.
+	* В данной статье рассматривается метод обучения с учителем, называемый «каскады Хаара».
+	* Потом, в режиме понимания слушателем, проводится описание алгоритма.
+----
 
 Формально говоря, каскад Хаара выполняет задачу
-''классификации'' - разделения множества объектов на классы. В нашем случае
-объекты - это входные изображения. А класса всего два: искомый объект и все
+''классификации'' ‒ разделения множества объектов на классы. В нашем случае
+объекты — это входные изображения. А класса всего два: искомый объект и все
 остальное. Говоря проще, каскад Хаара принимает на вход изображение и выдает
 один из двух ответов: "да" и "нет".
 
 Что бы каскад Хаара определял, есть ли искомый объект на входном изображении,
-его нужно ''обучить''. Тоесть, задать ему такую структуру, что бы он выдавал
+его нужно ''обучить''. То есть, задать ему такую структуру, что бы он выдавал
 положительный результат для изображений с искомым объектом, и отрицательный в
 другом случае. В данном случае используется обучение с учителем, т.е. имеется
 обучающая выборка (набор разных изображений) и данные, указывающие, какие из
 этих изображений содержат искомый объект. Обучение может занимать очень много
 времени: иногда даже по несколько дней.
 
+----
+	* «В данном случае используется обучение с учителем»: читатель вообще может не понимать, что такое обучение с учителем (и не знать, чем оно отличается от обучения без учителя). В  одном научном журнале по точных наукам на фразу «Это алгоритм обучения без учителя» мне ответили: «Мы не публикуем статьи по педагогике». -- АтрашкевичАндрей
+----
+
 Правильно обученный каскад Хаара может достаточно быстро классифицировать
 изображения и имеет неплохую устойчивость к шумам и другим отклонениям.
-Несмотря на то, что оригинальная статья в основном описывает обнаружение лиц,
-данный метод можно использовать и для обнаружения других объектов. Далее
-описываются методы которые используются при классификации изображений с помощью
-каскадов Хаара.
+
+----
+	* «имеет неплохую устойчивость к шумам и другим отклонениям»: неплохую по отношению к чему? что есть шум? что за отклонения? -- АтрашкевичАндрей
+----
 
 -- Признаки Хаара.
 Признак Хаара является набором прямоугольных областей изображения, примыкающих
 друг к другу и разделенных на две группы. Возможных признаков Хаара огромное
 множество (разнообразные комбинации областей разной ширины и высоты с разными
 позициями на изображении). Первоначальный набор признаков зависит от реализации
-и конкретной задачи (в разделе, посвященном алгоритму ''AdaBoost'', описано,
-как из этого набора выбираются признаки, лучше всего классифицирующие
-изображения).
+и конкретной задачи: обычно используют такие комбинации прямоугольных областей:
 
 ----
-[[https://pp.vk.me/c630526/v630526863/b9f8/Bd7Yscrae6s.jpg|100px]]
+[[https://pp.vk.me/c630526/v630526863/b9f8/Bd7Yscrae6s.jpg]]
+----
+
+Чтобы вычислить значение конкретного признака Хаара для какого-либо
+изображения, надо сложить яркости пикселей изображения в первой и второй группах
+прямоугольных областей по отдельности, а затем вычесть из первой полученной
+суммы вторую. Полученная разность и есть значение конкретного признака Хаара
+для данного изображения.
+
 ----
+[[https://pp.vk.me/c630526/v630526863/b9ff/4FEa4ukhB_s.jpg]]
+----
+
+К примеру, на изображении белые прямоугольники ‒ это первая группа
+группа областей, а черные ‒ вторая. Значение признака Хаара ‒ это разность
+сумм яркостей пикселей первой и второй группы. В математической форме это будет выглядеть так:
+
+%EQ
+a sub i = sum from {i={y sub a sub i}} to {{y sub a sub i}+{h sub a sub i}-1}
+~~
+sum from {j^=^{x sub a sub i}} to {{x sub a sub i}+{w sub a sub i}-1} x sub {i j}
+%EN
+
+%EQ
+b sub i = sum from {i={y sub b sub i}} to {{y sub b sub i}+{h sub b sub i}-1}
+~~
+sum from {j^=^{x sub b sub i}} to {{x sub b sub i}+{w sub b sub i}-1} x sub {i j}
+~~~~~~~~
+%EN
+
+%EQ
+h = sum from {i ^ = ^ 1} to {{N sub a}} {a sub i}
+- sum from {i ^ = ^ 1} to {{N sub b}} {b sub i}
+~,
+%EN
+
+где $$x sub ij$$ ‒ яркость пискеля изображения с координатами $$[i, j]$$,
+$$a sub i$$ ‒ сумма яркостей пикселей в $$i$$-й области первой группы,
+$$b sub i$$ ‒ сумма яркостей пикселей в $$i$$-й области второй группы, $$h$$ ‒
+значение признака Хаара для этого изображения, $$h sub a sub i$$ ‒ высота $$i$$-й
+области первой группы, $$w sub a sub i$$ ‒ ширина $$i$$-й области первой группы,
+$$h sub b sub i$$ ‒ высота $$i$$-й области второй группы, $$w sub b sub i$$ ‒ ширина $$i$$-й области
+второй группы, $$N sub a$$ ‒ количество областей первой группы, $$N sub b$$ ‒
+количество областей второй группы, а $$h$$ ‒ значение признака Хаара для этого
+изображения.
+
+-- Интегральная форма представления изображения.
+Вычисление значения каждого признака Хаара для изображения требует много
+операций сложения. Однако, если использовать интегральную форму изображения,
+количество вычислений можно сильно уменьшить.
+
+В интегральной форме изображения значение каждого пикселя является суммой
+яркостей этого пикселя и всех пикселей, что находятся выше и левее
+него (если пиксель с координатами $$[1; 1]$$ находится в верхнем левом углу
+изображения):
+
+%EQ
+S sub {yx} = sum from {i^=^1} to {y} sum from {j^=^1} to {x} {x sub ij}
+~,
+%EN
+
+где $$S sub yx$$ ‒ значение пикселя интегральной формы изображения с
+координатами $$[y; x]$$, а $$x sub ij$$ ‒ значение пикселя исходного изображения
+с координатами $$[i; j]$$.
+
+Переведя изображение в интегральную форму, можно вычислять значения признаков
+Хаара для него, не выполняя суммирование всех требуемых значений яркостей
+каждый раз по новой. Достаточно посчитать сумму яркостей для каждой
+прямоугольной области, используя свойства интегральной формы изображения:
+
+%EQ
+left { lpile {
+a sub i
+= S[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}]
+above
+a sub i
+= S[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}]
+- S[{{y sub a sub i} + h sub a sub i};{x sub a sub i}]
+above a sub i
+= S[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}]
+- S[{y sub a sub i};{{x sub a sub i} + w sub a sub i}]
+above a sub i
+= S[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}]
+- S[{y sub a sub i};{{x sub a sub i} + w sub a sub i}]
+- S[{{y sub a sub i} + h sub a sub i};{x sub a sub i}]
++ S[{y sub a sub i};{x sub a sub i}]
+}
+lpile {
+, y = 1, x = 1
+above
+, y > 1, x = 1
+above
+, y = 1, x > 1
+above
+, y > 1, x > 1
+} right ""
+%EN
+
+%EQ
+left { lpile {
+b sub i
+= S[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}]
+above
+b sub i
+= S[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}]
+- S[{{y sub b sub i} + h sub b sub i};{x sub b sub i}]
+above b sub i
+= S[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}]
+- S[{y sub b sub i};{{x sub b sub i} + w sub b sub i}]
+above b sub i
+= S[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}]
+- S[{y sub b sub i};{{x sub b sub i} + w sub b sub i}]
+- S[{{y sub b sub i} + h sub b sub i};{x sub b sub i}]
++ S[{y sub b sub i};{x sub b sub i}]
+}
+lpile {
+, y = 1, x = 1
+above
+, y > 1, x = 1
+above
+, y = 1, x > 1
+above
+, y > 1, x > 1
+} right ""
+%EN
+
+где $$S[y;x]$$ ‒ значение пикселя интегральной формы изображения. Далее можно
+вычислить значение признака Хаара как обычно:
+
+%EQ
+h = sum from {i^=^1} to {{N sub a}} {a sub i}
+- sum from {i^=^1} to {{N sub b}} {b sub i}
+~,
+%EN
+
+----
+[[https://pp.vk.me/c630526/v630526863/ba1d/R2zQus3h-cM.jpg]]
+----
+
+Пример: для того, что бы вычислить сумму значений пикселей в прямоугольнике $$D$$,
+изображенном на рисунке можно использовать интегральную форму изображения: в ней
+точка $$a$$ будет являться суммой значений пикселей в прямоугольнике $$A$$, точка $$b$$ ‒
+суммой значений пикселей в прямоугольниках $$A$$ и $$B$$, точка $$c$$ ‒ суммой
+значений пикселей в прямоугольниках $$A$$ и $$C$$, а точка $$d$$ ‒ суммой значений
+пикселей в прямоугольниках $$A$$, $$B$$, $$C$$ и $$D$$. Тогда сумма значений пикселей
+в прямоугольнике $$D$$ будет равна $$d - c - b + a$$.
+
+- ''''''Алгоритм AdaBoost''''''.
+
+Для выбора признаков, лучше всего классифицирующих изображения используется
+алгоритм ''''''''AdaBoost'''''''' (adaptive boosting). Этот алгоритм построен на идее,
+что из большого числа простых способов классификации (называемых ''слабыми
+классификаторами'') можно составить, новый способ, выполняющий эту задачу
+намного эффективнее.
+
+----
+	* Основная идея данного алгоритма состоит в следующем: из большого числа простых способов классификации (т. н. ''слабых классификаторов'') можно составить новый способ, более эффективный чем каждая из его составляющих по отдельности.
+----
+
+В данном случае слабый классификатор ‒ это функция, которая принимает на вход
+изображение, вычисляет значение соответствующего ей признака Хаара для этого
+изображения и сравнивет это значение с порогом, возвращая либо $$0$$, либо $$1$$.
+
+%EQ
+{h sub i}(x) = left {
+lpile {
+1, {p sub i}{f sub i}(x) < {p sub i}{theta sub i}
+above 0, ~ roman "otherwise"
+}
+right ""
+~,
+%EN
+
+где $$theta sub i$$ ‒ порог, $$x$$ ‒ входное изображение, $${f sub i}(x)$$ ‒ 
+результат вычисления значения соотвествующего признака Хаара для изображения
+$$x$$, $$p sub i$$ ‒ направление знака неравенства, а $${h sub i}(x)$$ ‒ слабый
+классификатор.
+
+----
+$$p sub i$$ принимает одно из двух значений: $$1$$ или $$-1$$. Если оно равно $$1$$,
+ничего не меняется, если же оно равно $$-1$$, знак неравенства начинает работать в
+обратную сторону. Такая запись используется, из-за своей краткости, а так же потому,
+что при реализации на некоторых архитектурах, операция умножения работает
+намного быстрее, чем условные операторы.
+----
+
+Данный алгоритм перебирает все возможные слабые классификаторы (как уже
+говорилось, возможных признаков Хаара огромное количество, что не лучшим
+образом влияет на скорость обучения) и выбирает те, которые допускают меньше
+всего ошибок. Важная особенность алгоритма в том, что каждому изображению из
+обучающей выборки соответсвует определенный вес, и после выбора очередного
+слабого классификатора веса перераспределяется так, что неверно
+классифицированные изображения начинают сильнее влиять на значение ошибки.
+Ниже приведен полный алгоритм:
+
+-- Входные данные:
+	* $$h sub i$$ ‒ $$i$$-й слабый классификатор
+	* $$E sub i$$ ‒ $$i$$-й обучающий пример.
+	* $$y sub i$$ ‒ $$0$$, если $$i$$-й обучающий пример отрицательный, и $$1$$, если $$i$$-й обучающий пример положительный.
+	* $$n$$ ‒ количество обучающих примеров.
+
+-- Переменные:
+	* $$w sub i$$ ‒ вес, соответствующий $$i$$-му обучающему примеру.
+	* $$m$$ ‒ число отрицательных примеров.
+	* $$l$$ ‒ число положительных примеров.
+	* $$epsilon sub i$$ ‒ ошибка $$i$$-го слабого классификатора.
+	* $${h dot} sub i$$ ‒ слабый классификатор, выбранный на $$i$$-й итерации.
+	* $$epsilon dot$$ ‒ минимальное значение ошибки слабого классификатора на текущей итерации.
+	* $$beta sub i$$ ‒ минимальное значение ошибки слабого классификатора на $$i$$-й итерации, представленное в другой форме (для оптимизации вычислений и экономии места).
+
+-- Алгоритм:
+	* Инициализировать веса обучающих примеров: 
+%EQ
+left {
+lpile {
+w sub i = size -2 {1 over 2m}, if~y sub i = 0
+above w sub i = size -2 {1 over 2l}, if~y sub i = 1
+}
+right ""
+~,
+%EN
+	* Для $$t = 1, .., T$$:
+		1 Нормализовать веса обучающих примеров:
+%EQ
+w sub i = size -2 {{w sub i} over {sum from {j^=^1} to n {w sub j}}}
+%EN
+		1 Вычислить значение ошибки для каждого слабого классификатора:
+%EQ
+epsilon sub j = sum from k to n {{w sub k}|{h sub j}({E sub k}) - {y sub k}}|
+%EN
+		1 Hайти классификатор с минимальной ошибкой:
+%EQ
+{epsilon dot} = min {epsilon sub j}
+~,~~~
+{{h dot} sub t} = h sub j
+%EN
+		1 Обновить веса обучающих примеров:
+%EQ
+beta sub t = size -2 {{{epsilon dot}} over {(1 - {epsilon dot})}}
+~,~~~
+w sub i = {w sub i} {beta sub t} sup {1^-^{|{{h dot} sub t}({E sub i})^-^{y sub i}}|}
+%EN
+	* Итоговый конечный классификатор: 
+%EQ
+H(x) = left { lpile {
+1, ~ sum from {t = 1} to T {log({size -2 {1 over {beta sub t}}}) {h dot} sub t}({E sub i})
+>= sum from {t = 1} to T {log({size -2 {1 over {beta sub t}}})}
+above
+0, ~ roman "otherwise"
+}
+right ""
+%EN
+
+- Каскад классификаторов.
+
+# КатегорияМашинноеОбучение