Первый алгоритм для определения лиц на изображении, который работает в реальном времени, был разработан Paul Viola и Michael Jones в 2001 году. Частью алгоритма является процедура, вычисляющая признаки Хаара. В рамках данной задачи мы рассмотрим упрощённую модель данного понятия.
Рассмотрим прямоугольное изображение, представляющее собой таблицу размера n × m. Элементы таблицы являются целыми числами, задающими яркость каждого пикселя в изображении.
Признак также представляет из себя прямоугольную таблицу размера n × m. Каждая ячейка признака покрашена в черный или белый цвет.
Чтобы вычислить значение данного признака на данном изображении, необходимо произвести следующие шаги. Сначала таблица признака совмещается с таблицей изображения (без переворотов или отражений), таким образом, каждый пиксель оказывается целиком покрыт либо черным, либо белым цветом. Значением признака на изображении называется величина W - B, где W — суммарная яркость пикселей изображения, покрытых белыми ячейками признака, а B — суммарная яркость пикселей, покрытых черными ячейками признака.
Ниже изображены примеры наиболее популярных признаков Хаара.
Ваша задача будет заключаться в определении числа операций, которые необходимы для подсчёта признака с помощью так называемых префиксных прямоугольников.
Префиксным прямоугольником называется любой прямоугольник на изображении, левый верхний угол которого совпадает с левым верхним углом изображения.
У вас есть переменная value, значение которой исходно равняется нулю. За одну операцию вы можете посчитать сумму значений пикселей на любом префиксном прямоугольнике, умножить её на любое целое число и прибавить к переменной value.
Вам задан признак. Необходимо посчитать минимальное число операций, которое требуется для вычисления значения этого признака на произвольном изображении. Для лучшего понимания условия, прочтите объяснение первого примера.
Примечание
Первый пример соответствует признаку B, изображенному на картинке. Значение этого признака на изображении размера 6 × 8 равняется разности суммарной яркости пикселей в нижней и верхней половине изображения. Для вычисления его значения необходимо выполнить следующие две операции:
- Прибавить сумму пикселей на префиксном прямоугольнике с нижним правым углом в 6 строке и 8 столбце с коэффициентом 1 к переменной value (красной рамкой обозначен прямоугольник);
- Прибавить сумму пикселей на префиксном прямоугольнике с нижним правым углом в 3 строке и 8 столбце с коэффициентом - 2 и переменной value.
Таким образом, все пиксели в нижних трёх строках изображения войдут с коэффициентом 1, а все пиксели в верхних трёх строках изображения войдут с коэффициентом 1 - 2 = - 1, что и требуется.