Размещено на http://www.allbest.ru/

видеонаблюдение фрактальное кодирование изображение распознавание

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

Вуль В.В., СПбГУ, кафедра Информатики

Основное содержание исследования

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

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

Большинство традиционных систем наблюдения характеризуются следующими особенностями:

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

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

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

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

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

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

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

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

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

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

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

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

Компания Hitachi совместно с компанией Glory (производителем банкоматов), объявили о создании технологии идентификации личности по чертам лица с 99-процентной точностью. Для начала планируется начать использование новых биометрических систем в аэропортах или для контроля за доступом на различных объектах первостепенной важности.

Российская компания "Интеллектуальные системы безопасности" (ISS) разработала интеллектуальный детектор движений, систему автоматического распознавания автомобильных номеров, видеодетектор лиц в которых используется Wavelet-алгоритм компрессии видеоданных. Так видеодетектор лиц осуществляет:

Ё поиск и выделение лица человека, движущегося в контролируемой зоне;

Ё автоматический выбор видео кадров с оптимальным (фронтальным) расположением лица;

Ё автоматическое сопровождение движущегося человека с помощью поворотной камеры;

Ё в режиме реального времени выделение лица при высокоскоростных перемещениях, изменениях положения в пространстве тела человека.

Здесь недостает только идентификации лица на основе сравнения с данными людей, хранимыми в банке изображений такой системы.

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

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

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

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

Рис.1. Базовый алгоритм фрактального кодирования изображений

В частности, известны цифровые методы моделирования человеческого лица в программах трехмерной графики, таких как 3D Studio Max, Maya и пр. Основные параметры таких моделей могут быть положены в основу классификации и распознавания соответствующих образов в системах с использованием рентгеновского излучения. Именно в решении подобных задач фрактальное кодирование может сыграть существенно положительную роль, определяя компактное задание основных характеристик цифровых моделей и позволяя в реальном масштабе времени производить классификацию и идентификацию подозрительных лиц.

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

Хэш-метод поиска подходящего домена для рангового блока должен состоять из следующих основных блоков:

Ё вычисление хэш - ключей для всех доменов,

Ё распределение доменов по хэш-таблице,

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

Ё сравнение рангового блока только с теми доменами, хэш-ключи которых находятся в поднаборе, вычисленном на предыдущем шаге,

Ё выбор первого подходящего или наиболее подходящего домена,

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

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

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

Чтобы близость ключей рангового блока и домена соответствовала относительной близости собственно рангового блока и домена, рассмотрим подробно, что означает, что ранговый блок R близок к sD + o, где s - контрастность, а o - яркость, т.е.

R ~ sD + o.

Так как r_ij ~ sd_ij + o, то

<r> ~ s<d> + o,

где <r> - среднее значение пикселов рангового блока, а <d> - среднее значение пикселов домена. С другой стороны, R ~ sD + o дает

у (r) ~ |s|у (d) ( (1)

где у (r) - девиация рангового блока, у (d) - девиация доменного блока. Поэтому

( (2)

что задает соответствие оценки параметров аппроксимации и сравнения блоков.

Эти соображения приводят к определению следующей хэш-функции от блока h (B):

( (3)

где B - "центрирующий" параметр, а C - искомый "разброс" значений дроби в (2). Суммирование проводится по тем точкам блока (b_ij¹, b_ij², …, b_ij^H), которые выбраны для вычисления значений хэш-функции, в нашем случае их 5 и это - вершины блока и точка пересечения его диагоналей; H - количество этих точек. Параметр л используется для контроля разброса функции округления снизу, так чтобы ее значения были распределены приблизительно равномерно. Другими словами, (2) должна давать такое разложение h (B) в ряд по степеням C, что его коэффициенты распределены приблизительно равномерно. Выбор конкретных значений параметров B, C и л будет более подробно рассмотрен ниже.

Предположим теперь, что набор доменов D зафиксирован. Для распределения элементов D по хэш-таблице T используется хэш-функция (2). T [h] указывает на список, содержащий такие D из D, что h (D) = h.

Значения параметров B и C установить достаточно легко. C - искомый "разброс" значений дроби (2), в то время как B выбирается так, чтобы результат операции нахождения остатка был в пределах от 0 до C-1. Например, если ожидаемый разброс - 16, мы берем C = 16 и B = 8.

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

В результате исследований было установлено, что параметр л для блоков данного размера должен быть близок к усредненному значению у (b), деленному на B/3. Отметим, что точное совпадение h (D) и h (R) маловероятно. Подходящий домен для R будет выбран среди таких D, что h (D) принадлежит H_R. Значения в множестве H_R задаются как

( (4)

где отклонение д = (д₁, д₂,., д_H) соответствует |д| ? ?.

Диапазон значений ? также влияет на производительность алгоритма. В частности, из представленного на рис.2 алгоритма следует, что значение ?, близкое к 0, приведет к большому количеству возвратов, т.е. ситуаций, когда для заданного рангового блока не удалось найти подходящий домен в множестве H_R. В этом случае придется разбивать ранговый блок на несколько блоков меньшей величины. С другой стороны, увеличение значения ? неизбежно приведет к возрастанию требуемых вычислительных ресурсов и времени вычислений, в то же время улучшение качества окажется несущественным. Экспериментально нам удалось установить определенную связь (взаимную корреляцию) значений ? и л. Так, при выборе значения л, близкого к оптимальному, целесообразно задавать значение ? близкое к 1. Значение ключей в H_R упорядочены "по спирали". Под этим подразумевается, что, если взять для примера H = 2 в (3) и (4), д будет принимать значения (0; 0); (1; 0); (0; 1); (-1; 0); (0; - 1); и т.д.

Теперь уже можно дать точную формулировку предлагаемой версии алгоритма фрактального кодирования для распознавания образов в системах реального времени. Пусть набор доменов D зафиксирован, и для него построена хэш-таблица T. Предположим, что два других параметра d_M и d_C также установлены. Пусть R - сжимаемый ранговый блок, а H_R = (h₁;., h_M) - упорядоченный набор ключей, вычисленный в соответствии с (4). Определим расстояние между R и доменом D как

, ( (5)

где sup берется по всем пикселам домена и рангового блока.

Так как нам требуется положительный фактор контрастности , необходимо добавить в множество доменов негативы исходных доменов. Для обеспечения высокого качества декомпрессии, рассматриваются только домены, для которых s ? 1,5. Псевдокод для компрессии выглядит следующим образом:

d = ?; D_R = NULL; // инициализация

start:

for i = 1,., M:

for D in T [h_i]:

d' = dist (R, D);

if d' < d: D_R = D; d = d';

if d < d_M: переместить D_R в начало T [h_i];

goto end;

end:

if d < d_C: сжать R с использованием D_R;

else: разбить R на подблоки;

вычислить характеристики подблоков;

goto start;

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

Разбиение на ранговые блоки производится следующим образом. Сначала изображение разбивается на блоки 16х16 пикселей, затем разбиение осуществляется в соответствии со стандартным алгоритмом квадродерева для глубины 3. Т.е. разбиение производится лишь до тех пор, пока не достигнут размер блока 4х4: дальнейшее разбиение бесполезно, так как код сжатого изображения для области 2х2 пиксела требует около 4 байт.

Рассмотрим теперь параметры d_M и d_C. Как следует из описания алгоритма, ранг R сжимается с помощью домена D_R только в том случае, если расстояние между ними d меньше d_C.

Хорошие результаты дает выбор d_C, равного 70% от значения стандартной девиации всего изображения. Приемлемым выбором можно считать значение d_C в пределах от 40% до 70%.

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

Рис.2. Алгоритм фрактального кодирования с использованием хэш - ключей

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

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

Под похожестью изображений будем понимать следующее:

Определение. Два изображения одного размера будем называть д-похожими, если для любой точки одного изображения существует такая окрестность S этой точки (охватывающая достаточно большое число точек, в нашем случае - не менее 16) и такое значение o>0, что

,

где N (S) - количество точек, попавших в S.

Фактически, параметр o выравнивает яркость изображений в S, а д - средняя пиксельная разница изображений с выровненной яркостью.

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

Отметим, что если у двух кодов изображений совпадают квадродеревья, для соответствующих пары доменов D и D' выполняется следующее условие:

,

а значения контрастности попарно совпадают, то декомпрессированные изображения будут похожи с д=0. Данное утверждение очевидным образом следует из определения.

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

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

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

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

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

Размещено на Allbest.ru