Алгоритм классификации изображений парковочных мест автостоянки на основе гистограмм ориентированных градиентов и метода опорных векторов

Системы видеонаблюдения приобретают все большую значимость в различных сферах деятельности человека [1-3]. Благодаря развитию технологий компьютерного зрения предложен ряд систем видеонаблюдения с интеллектуальной обработкой входных видеоданных, включая системы управления автомобильными парковками. Такие видеосистемы могут автоматически выполнять многие функции. Например, определение занятости парковочного места, подсчет количества автомобилей на стоянке, определение расположения или типа транспортного средства, анализ активности людей, предоставление справочной информации в виде маршрута к парковочному месту, удаленное наблюдение владельца за автомобилем с помощью смартфона и оповещение в случае возникновения нештатной ситуации и т.д. Очевидно, что для таких систем необходимо алгоритмическое обеспечение по обработке входных видеоданных, основным требованием к которому является высокая эффективность классификации парковочных мест, в том числе при наличии различных шумовых факторов: теней, световых пятен в солнечную погоду, изменений общей освещенности автомобильной парковки в течение суток, изменений погодных условий и т.д. Таким образом, сложность задачи предопределила разработку и развитие ряда методов и алгоритмов для её решения.

Общий подход для построения алгоритмов обнаружения свободных и, соответственно, занятых парковочных мест предполагает выполнение следующих шагов: предварительная сегментация и локализация парковочных мест (регионов интереса), вычисление их признаков, классификация и интерпретация результата. В настоящее время активно ведутся исследования в данной области и предлагается ряд методов для определения занятости парковочных мест по видеоизображениям [4]: методы, основанные на обнаружении автомобиля на парковочном месте [5, 6]; методы, основанные на сравнении обрабатываемого парковочного места с эталонным свободным местом [7, 8] и комбинированные методы [9, 10], построенные на основе первых двух подходов. Методы первой группы неустойчивы к ошибкам классификации, возникающим из-за взаимного перекрытия автомобилей на видеоизображениях. Методы второй группы предполагают использование модели эталонного свободного парковочного места, поэтому вероятность ложной классификации увеличивается при появлении естественных шумовых факторов, людей, при локальном изменении освещенности и т.д. Комбинированные методы, как правило, предполагают использование преимуществ обоих подходов, но требуют при этом значительных вычислительных затрат.

Для построения вектора признаков изображения парковочного места перспективным является использование гистограмм ориентированных градиентов (HOG), т.к. в данном случае обеспечивается инвариантность относительно поворота изображения и изменения масштаба, устойчивость к шуму и изменению освещения [11]. В последнее время предложен ряд методов и алгоритмов для классификации парковочных мест с использованием гистограмм ориентированных градиентов, к наиболее эффективным можно отнести [9, 14-16]. В работе [14] рассматривается метод, использующий указанный дескриптор и байесовский классификатор, для которого вероятность правильной классификации при нормальных условиях съемки достигает 0,9945. Метод предполагает построение структурной ЗВ-модели для каждого парковочного места и характеризуется большими временными затратами. Алгоритм, представленный в [9], направлен на повышение производительности подоб ного подхода и при наиболее оптимальных условиях съемки позволяет достичь вероятности правильной классификации 0,9936. В работе [15] показано дальнейшее развитие алгоритма путем применения на этапе классификации метода опорных векторов (SVM), за счет чего обеспечивается увеличение вероятности правильной классификации до 0,9955. В [16] исследованы алгоритм для классификации парковочных мест на основе гистограмм ориентированных градиентов и машин опорных векторов и алгоритм на основе признаков Хаара и метода AdaBoost. При этом вероятность правильной классификации достигается для первого и второго алгоритмов 0,691 и 0,95 соответственно. Таким образом, несмотря на хорошие качественные характеристики методов обнаружения свободных парковочных мест автостоянки в системах видеонаблюдения, данная задача не решена в полной мере в настоящее время, следовательно, исследования в данном направлении актуальны.

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

где 0w+ 1, bh^ch-Bh+X.

• 5)    Формирование вектора признаков:

  • 5.1)    Вычисление второй нормы ориентаций ячеек блока Ву₈:

5.2) Нормализация ориентаций ячеек блока:

./ +⁵» ^-1 g +5/, -1 6-1

-=/ j=g 1-0

5.3) Составление вектора признаков:

d                           = С‘ J’s b-B1,-Bl,y-,v.g+fyb

Размер вектора d зависит от размера изображения w^h, размера ячеек С,уСн и размера блока B,yBh, а также от количества ориентаций в ячейке Ь. Таким образом, количество элементов в признаковом векторе может быть определено как:

1. Вычисление вектора признаков

Алгоритм построения вектора признаков парковочного места на основе гистограммы ориентированных градиентов требует выполнения следующих шагов:

1) Вычисление градиентов для исходного изображения I с размерами wx/z:

2. Классификация признаков

Для классификации дескрипторов парковочного места, полученных на основе гистограмм ориентированных градиентов, применяется метод опорных векторов, который позволяет разделять парковочные места на два класса - свободные и занятые. Правило классификации парковочных мест может быть записано в следующем виде [12]:

a(tZ) = sign| ^X/y^d^-wA         (9)

G^I^-AT Gy,=IiyMy,

где 0Х,МУ) - дискретный дифференцирующий оператор (М^х и М^у для осей х и у соответственно).

• 2)    Вычисление модуля вектора градиента G_x, >- и ориентации 0^ для изображения /:

v                      v = ^arctan (G^y_x „ !G^X „)      (2)

у A,V x,y x,y              \ x,y x,y J         x / и формирование матрицы градиентов G и ориентаций 0 изображения I.

• 3)    Разбиение G на ячейки С_т,„ размером С«уСь и накопление мощностей градиентов в соответствии с ориентациями 0, для каждой из них:

где a(d) - решающее правило (принимающее одно из значений меток класса: +1 и -1 для свободных и занятых мест соответственно), Ц Хо, Х\,...,Х_п) - вектор двойственных переменных, y(yo,yt,.. ,,у_п) - вектор меток классов опорных векторов, {^} — - множество

С*

0п+1)си-1 ,

Z-(27t/6)<0,,<(/ + l).(2K/6)

[0, (2к/6) > 0,_; U 0,_; >(/ + !)• (2л/6) ’ ^} j=nch

где b - число ориентаций в ячейке, которое определяется поставленной задачей, 0 cw = (w/ С»), ch = (h/ Ch).

4) Объединение ячеек в блоки Ву₈ размером В-,уВу

(

С

с, Vye.-vg

В, =

.Лк

опорных векторов признаковых векторов, wo - пороговое значение, d - обрабатываемый вектор признаков.

Эффективность работы классификатора в значительной степени определяется применяемой функцией ядра. Для классификации парковочных мест могут быть использованы следующие функции: • линейная

K,MA^ = da-db,(10)

• •    радиальная

Ау (<Л) = exp(-Y- \\da -dh||2),

• •    полиномиальная

К^АьМ^^АУ^,(12)

• •    пересечения гистограмм

^U^A^Z^tHW)’      оз)

с

С

где d_a a db - признаковые вектора;у, 8, с - параметры соответствующих ядер.

3. Результаты экспериментов

Для проведения экспериментов и оценки результатов исследований рассмотренный подход реализован на языке Java с использованием среды разработки eclipse, библиотеки компьютерного зрения OpenCV 3.0.0 и библиотеки машинного обучения метода опорных векторов jlibsvm. Разработка, тестирование и анализ результатов работы алгоритма проводились на персональном компьютере с центральным процессором Intel(R) Core(TM)2 DuoCPU с тактовой частотой 2,6 ГГц и объемом ОЗУ 4,0 ГБ.

В качестве данных для экспериментов использовались изображения парковки Папского католического университета Параны (Pontifical Catholic University of Parana) из базы данных Pk-Lot[13], Pk-Lot содержит изображения парковки, полученные при различных погодных условиях, теневых эффектах и освещенности. Парковочные места находятся на различном удалении от камеры, которая установлена достаточно высоко над парковкой. Это позволяет перейти к виду сверху на изображение парковки путем преобразования перспективы, при этом отсутствуют перекрытия изображений парковочных мест транспортными средствами, расположенными рядом.

Для тестирования алгоритма использованы 2153 изображения парковки с общим количеством изображений парковочных мест 292808, которые были получены при различных погодных условиях (табл. 1).

Табл. 1. Основные характеристики используемых изображений парковки

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

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

На рис. 2 представлена визуализация ориентаций ячеек свободного и занятого парковочных мест, вы численных на основе гистограмм ориентированных

Рис. 2. Визуализация ориентаций ячеек для изображений парковочных мест: занятое парковочное место (а), свободное парковочное место (б)

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

Эффективность дескриптора оценивается вероятностью правильной классификации изображений парковочных мест RR(.w, h, C_w, Ch, b\ которая вычисляется по формуле:

TP+TN

RR^w,h,C ,C_h,b^ =----------------,      (14

v          / TP + FP + TN + FN где w, h - ширина и высота изображения парковочного места; C„., Ch - ширина и высота ячейки, b - количество ориентаций в ячейке; ТР - количество правильно классифицированных свободных парковочных мест; FP - количество свободных мест парковки, классифицированных как занятые; TN - количество правильно классифицированных занятых парковочных мест, FN - количество занятых мест парковки, классифицированных как свободные.

Вероятность ложной классификации изображений свободных парковочных мест определяется как:

FPR = FPKTP + FP).                     (15)

Вероятность ложной классификации изображений занятых парковочных мест определяется как:

FNR = FN/(TN + FN). (16)

На рис. 3 представлены результаты эксперимента по определению наиболее эффективного размера изображения парковочного места дескриптора для наиболее используемых размеров ячейки при решении других практических задач 8x8 и количестве ориентаций в ячейке равном 9 для признакового вектора, формируемого на основе гистограмм ориентированных градиентов.

Из рис. 3 следует, что наиболее эффективными могут быть размеры изображений парковочных мест: 64x56, 64x64, 64x72, 64x80, 48x104, для которых необходимо определение значений последу- ющих параметров алгоритма. На рис. 4 показаны результаты экспериментов по определению наиболее эффективных размеров ячеек, обеспечивающих максимальную вероятность правильного обнаружения для изображений с размерами, полученными на предыдущем этапе исследований. Анализ рис. 4 показывает, что максимальная вероятность пра вильной классификации при различных размерах ячеек обеспечивается для соответствующих размеров изображений парковочного места, при следующих параметрах дескриптора (w, h, С,,., С/,) парковочного места: (64, 56, 8, 8), (64, 64, 8, 8), (64, 72, 8, 6), (64, 72, 8, 8), (64, 72, 8, 9), (64, 72, 8, 12), (64, 80, 8, 5), (64, 80, 8, 8), (64, 80, 8, 16), (48, 104, 8, 8).

RR 0,9970

0,9965

0,9960

0,9955

0,9950

0,9945

0,9940

0,9935

Рис. 3. Вероятность правильной классификации для различных размеров изображений парковочных мест

RR

RR

1,000

0,995

0,990

0,985

' C_w IS 1 ' П76Щ2]

ГТЬ- ^{08 0/2}   0.997 -^---■----■---[176ПЛ

Illi Ин

0,980 а)

С/,

б)

Рис. 4. Вероятность правильной классификации при различных размерах ячеек для изображения с wxh: а) 48x104, б) 64 x56, в) 64x64, г) 64x80, д) 64x72

На следующем шаге проведены экспериментальные исследования по определению количества ориентаций в ячейке, обеспечивающих максимальную вероятность правильного обнаружения, в интервале от 4 до 18, т.е. в два раза меньше и больше от традиционно применяемого значения при решении других практических задач с использованием гистограмм ориентированных градиентов. На рис. 5 представлены результаты исследований для количества ориентаций в ячейке в диапазоне от 9 до 18, т.к. для меньшего количества ориентаций вероятность правильного обнаружения значительно ниже.

2 - (64, 64, 8, 8), 3 - (64, 72, 8, 6), 4 - (64, 72, 8, 8), 5 - (64, 72, 8, 9), 6 - (64, 72, 8, 12), 7 - (64, 80, 8, 5), 8 - (64, 80, 8, 8), 9 - (64, 80, 8, 16), 10- (48, 104, 8, 8)

Результаты, представленные на рис. 5, свидетельствуют о том, что вероятность правильной классификации тестовых изображений является максимальной для трех различных параметров дескриптора (w, h, C_w, C_h, by. (64, 72, 8, 6, 14), (64, 72, 8, 6, 16), (64, 72, 8, 8, 16). В этом случае необходимо найти признаковый вектор минимальной длины.

Исходя из размеров полученных дескрипторов:

D_s (64,72,8,16,14) = 4928, D_s (64,72,8,6,16) = 5638,

Ds^EA, 72, 8, 8, 16) = 3584, следует, что наиболее эффективными являются следующие параметры дескриптора: размер изображения парковочного места - 64x72, размер ячейки - 8x8, количество ориентаций в ячейке - 16.

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

Табл. 2. Сравнительная характеристика эффективности классификации при использовании различных функции ядра

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

На рис. 6 показан пример классификации парковочных мест разработанным алгоритмом с определенными параметрами на свободные и занятые.

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

Заключение

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

На основе экспериментальных исследований установлены наиболее эффективные значения параметров дескриптора: размер изображения парковочного места - 64x72, размер ячейки -8x8, количество ориентаций в ячейке -16. При этом вероятность правильной классификации 0,997.

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

в)

а)

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

Табл. 3. Сравнение характеристик алгоритмов классификации парковочных мест