быть в сигнале [32]. Вместо представления некоторой функции в виде суммы взвешенных дельта-функций (пространственно-временное представление) или суммы взвешенных синусоид (частотная область) в вейвлетном представлении функция представлена суммой некоторой базовой функции при различных сдвигах и масштабах. Эта базовая функция у/^называется вейвлетом [52]. Вейвлеты должны быть пространственно локализованы, иметь равные площади над и под осью графика, и не равны нулю только на Г + со конечном интервале у-«. — 0 Также желательно, чтобы вейвлетный базис был ортонормальным, т.е. произведение любых различных векторов (базисных функций) равно нулю, и длина каждого вектора (норма функции) равна единице. Таким образом, вейвлетиые коэффициенты будут нести максимум независимой информации. Первыми были вейвлеты Хаара [9], они представляли собой комбинацию плоских функций. Из-за их очевидной простоты они плохо подходили для представления сложных функций. Следующими были вейвлеты Добеши [14]. Они были локализованы по времени и по частоте и обладают фрактальными свойствами, т.с. на каждом масштабе вейвлет Добеши (как и все остальные вейвлеты) является уменьшенной копией самого себя. Ниже приведен общий вид вейвлетного преобразования, вычисление вейвлетных коэффициентов функции/(I) /-+оо /(О грЦСОсИ.Уя.ц У-со где-масштабу сдвиг базисной функции (вейвлета) I — V На практике обычно используется дискретное вейвлетное преобразование, масштаб и сдвиг базисного вейвлета изменяется дискретными шахами. Мас; штаб, как правило, на каждом шаге уменьшается в геометрической 44 |
2.3. Алгоритм эластичного графа 58 В качестве основного алгоритма распознавания изображений лица был выбран, исследован и дополнен (раздел 2.4) алгоритм эластичного графа (Е1а$бс СгарЬ Ма1сЫп§ А1&огКНт). В основе алгоритма лежит вейвлет-преобразование Габора. В этом подразделе будет дано краткое описание алгоритма эластичного графа, введено понятие джста, определены различные функции подобия для джетов, описаны алгоритм автоматической разметки графа и процедура распознавания. 2.3.1. Вейвлеты Главная идея вейвлетного преобразования частотно-локальное (частотновременное) представление сигнала, в отличие от таких частотных преобразований, как преобразование Фурье или косинусное преобразование, дающих информацию только о частотных характеристиках сигнала, безотносительно тому, когда и какие частотные компоненты имели место быть в сигнале [60]. Вместо представления некоторой функции в виде суммы взвешенных дельта-функций (пространственно-временное представление) или суммы взвешенных синусоид (частотная область) в вейвлетном представлении функция представлена суммой некоторой базовой функции при различных сдвигах и масштабах. Эта базовая функция у/(/) называется вейвлетом [60]. Вейвлеты должны быть пространственно локализованы, иметь равные площади над и под Также желательно, чтобы вейвлетный базис был ортонормальным, т.с. произведение любых различных векторов (базисных функций) равно нулю, и длина каждого вектора (норма функции) равна единице. Таким образом, вейвлетные коэффициенты будут нести максимум независимой информации. осью графика, и не равны нулю только на конечном интервале: Первыми были вейвлеты Хаара, они представляли собой комбинацию плоских функций. Из-за их очевидной простоты они плохо подходили для представления сложных функций. Следующими были вейвлеты Добеши. Они были локализованы по времени и по частоте и обладают фрактальными свойствами, т.с. на каждом масштабе вейвлет Добеши (как и все остальные вейвлеты) является уменьшенной копией самого себя. Ниже приведен общий вид вейвлетного преобразования, вычисление вейвлетных коэффициентов функции /(/) На практике обычно используется дискретное вейвлетное преобразование, масштаб и сдвиг базисного вейвлета изменяется дискретными шагами. Масштаб, как правило, на каждом шаге уменьшается в геометрической прогрессии 2шт12(т шаг), а шаг смешения выбирается пропорционально масштабу. Обратное преобразование (реконструкция) имеет вид Основным прикладным назначением вэйвлетных преобразований является сжатие изображений. Кроме того, вэйвлетное преобразование используется для извлечения ключевых характеристик изображений и поиска участков с одинаковыми свойствами на разных изображениях. 2.3.2. Эластичный граф где //-масштаб; V сдвигбазисной функции (вейвлета) Для алгоритма эластичного графа базовым объектом представления является размеченный граф. Ребра графа помечены информацией о расстоянии ме |