9 Генерация признаков Вейвлеты Хаара (Лекции 2016 года)

Генерация признаковна основе вейвлетпреобразования1ВейвлетыСинусоидальная волна – основа Фурье-преобразованияWavelet - короткая волна, волнишка, всплеск2Преобразование Хаара наоснове попарного усредненияПример изображения из одной строки в 4 пиксела16-цветная палитра9753841-1621-13Последовательное уменьшениеразрешенияРазрешениеСредниезначенияУточняющиекоэффициенты497352841 -11624Аппроксимация кусочно-постояннымифункциямиАппроксимацияРазрешение 16УточняющиекоэффициентыV 4 аппроксимацияРазрешение 8V 3 аппроксимацияW 3 коэффициентыV 2 аппроксимацияW 2 коэффициентыРазрешение 4Разрешение 2V 1 аппроксимацияW 1 коэффициентыРазрешение 1V 0 аппроксимацияW 0 коэффициенты5Функции одномерного базиса Хаара0≤‫<ݔ‬1в противном случае1߶ ሺ‫ ݔ‬ሻ = ൜0௝߶௜ ሺ‫ݔ‬ሻ݅= ߶൫2 ‫ ݔ‬− ݅൯ = ߶ ቆ2 ∙ ൬‫ ݔ‬− ௝ ൰ቇ , ݅ = 0, 1, … , 2௝ − 120௝1߶ሺ‫ ݔ‬ሻ௝012௝1߶൫2 ‫ݔ‬൯௝0݅2௝ሺ݅ + 1ሻ 12௝݅߶ ቆ2 ∙ ൬‫ ݔ‬− ௝ ൰ቇ2௝6Пространство функцийܸ௝ - пространство всех кусочно-постоянных функцийна [0,1) с интервалом постоянства௝߶௜ ሺ‫ݔ‬ሻ߶଴଴ ሺ‫ݔ‬ሻ = ߶ሺ‫ݔ‬ሻ ∈ ܸ ଴ ,ଵଶೕ∈ ܸ௝ , ݅ = 0, 1, … , 2௝ − 1߶଴ଵ ሺ‫ݔ‬ሻ = ߶ሺ2‫ݔ‬ሻଵቋ∈ܸ߶ଵଵ ሺ‫ݔ‬ሻ = ߶ሺ2‫ ݔ‬− 1ሻ߶଴ଶ ሺ‫ݔ‬ሻ = ߶ሺ4‫ݔ‬ሻۗ߶ଵଶ ሺ‫ݔ‬ሻ = ߶ሺ4‫ ݔ‬− 1ሻۖଶ∈ܸ߶ଶଶ ሺ‫ݔ‬ሻ = ߶ሺ4‫ ݔ‬− 2ሻۘۖ߶ଷଶ ሺ‫ݔ‬ሻ = ߶ሺ4‫ ݔ‬− 3ሻۙ12001410121101412101 32 4103417Скалярное произведениев пространстве функций݂ሺ‫ ݔ‬ሻ, ݃(‫ܸ ∈ )ݔ‬௝ ,ଵሺ݂, ݃ሻ = න ݂ሺ‫ ݔ‬ሻ݃(‫ݔ݀)ݔ‬଴8Ортодополнение в пространствефункцийܸ௝ - пространство всех кусочно-постоянных функцийна [0,1) с интервалом постоянстваଵଶೕܸ௝ାଵ - пространство всех кусочно-постоянных функцийна [0,1) с интервалом постоянстваଵଶೕశభܸ௝ ⊂ ܸ௝ାଵܹ௝ – ортодополнение для ܸ௝ в ܸ௝ାଵ – это множество всехфункций в ܸ௝ାଵ , ортогональных всем функциям из ܸ௝ .9Множество вейвлетовФункции߶ ሺ‫ ݔ‬ሻобразуют базис в пространстве ܸ .Определение.

Совокупность всех линейно независимыхфункций ߰ ሺ‫ ݔ‬ሻ, на которые натянуто ܹ (базис), называетсямножеством вейвлетов.Свойства.1. Базисные функции ߰ из ܹ вместе с базиснымифункциями ߶ из ܸ образуют базис ܸ2. Любая базисная функция ߰ из ܹ ортогональна любойбазисной функции ߶ из ܸ .10Вейвлеты Хаара1‫ ۓ‬10≤‫<ݔ‬2ۖ1߰ሺ‫ݔ‬ሻ =≤‫<ݔ‬1‫۔‬−12ۖ‫ ە‬0 в противном случае߰ ሺ‫ ݔ‬ሻ݅= ߰൫2 ‫ ݔ‬− ݅൯ = ߰ ቆ2 ∙ ൬‫ ݔ‬− ൰ቇ , ݅ = 0, 1, … , 2 − 12ሺ݅ + 1ሻ2௝12௝10߰ሺ‫ ݔ‬ሻ10߰൫2 ‫ݔ‬൯௝݅2௝01݅߰ ቆ2 ∙ ൬‫ ݔ‬− ௝ ൰ቇ2௝11Пример разложения Хаара߬ሺ‫ݔ‬ሻ = ሾૢ ૠ ૜ ૞ሿ,߬ሺ‫ ݔ‬ሻ ∈ ܸ , ݆ = 2.߬ሺ‫ݔ‬ሻ – кусочно-постоянная функция на [0,1) с интерваломଵସпостоянства .ܸ = ܸ ⊕ ܹ = (ܸ ⊕ ܹ ) ⊕ ܹ ߬ሺ‫ ݔ‬ሻ = ܿ ∙ ߶20 ሺ‫ݔ‬ሻ + ܿ ∙ ߶21 ሺ‫ݔ‬ሻ + ܿ ∙ ߶22 ሺ‫ݔ‬ሻ + ܿ ∙ ߶23 ሺ‫ݔ‬ሻ == ܿ ∙ ߶10 ሺ‫ݔ‬ሻ + ܿ ∙ ߶11 ሺ‫ݔ‬ሻ + ݀ ∙ ߰01 ሺ‫ݔ‬ሻ + ݀ ∙ ߰11 ሺ‫ݔ‬ሻ == ܿ ∙ ߶00 ሺ‫ݔ‬ሻ + ݀ ∙ ߰00 ሺ‫ݔ‬ሻ + ݀ ∙ ߰01 ሺ‫ݔ‬ሻ + ݀ ∙ ߰11 ሺ‫ݔ‬ሻ߶଴଴ ሺ‫ݔ‬ሻ, ߰଴ ሺ‫ݔ‬ሻ, ߰଴ ሺ‫ݔ‬ሻ, ߰ଵ ሺ‫ݔ‬ሻ – базис Хаара для ܸ ଴ଵଵ12Пример разложения Хаара߬ሺ‫ ݔ‬ሻ ൌ 9 ൈ+7ൈ+3ൈ+5ൈ߬ሺ‫ ݔ‬ሻ ൌ 8 ൈ+4ൈ+1ൈ+ (െ1) ൈ߬ሺ‫ ݔ‬ሻ ൌ 6 ൈ+2ൈ+1ൈ+ (െ1) ൈ13Ортогональность базиса Хаараቀ߰ ሺ‫ ݔ‬ሻ, ߰ ሺ‫ݔ‬ሻቁСлучай ݈ ≠ ݆1010௝߰௜ ሺ‫ݔ‬ሻСлучай ݈ = ݆ и ݅ ≠ ݇=0߰௞௟ ሺ‫ݔ‬ሻ12௝10߰௞௟ ሺ‫ݔ‬ሻ10௝߰௞௟ ሺ‫ݔ‬ሻ ߰௜ ሺ‫ݔ‬ሻ14Нормирование базиса Хаара߶௜ ሺ‫ݔ‬ሻ = ඥ2௝ ⋅ ߶൫2௝ ‫ ݔ‬− ݅൯௝߰௜ ሺ‫ ݔ‬ሻ = ඥ2௝ ⋅ ߰൫2௝ ‫ ݔ‬− ݅൯௝Тогдаቀ߶ ሺ‫ ݔ‬ሻ, ߶ ሺ‫ݔ‬ሻቁ = 1ቀ߰ ሺ‫ ݔ‬ሻ, ߰ ሺ‫ ݔ‬ሻቁ = 1Разложениепревращается вሾ6 2 1 − 1 ሿቂ6 2ቃ√√15Двумерный базис ХаараСтандартное разложение:Начинается вычислениемвейвлетных преобразований всехстрок изображения.1.2.

После этого стандартныйалгоритм производит вейвлетноепреобразование каждого столбца.16Двумерный базис ХаараНестандартное (пирамидальное) разложение:Пирамидальное разложениевычисляет вейвлетноепреобразование, применяя итерациипоочередно к строкам и столбцам.17Сжатие изображения вейвлетами Хаара(а) Исходное изображение(б) 19% вейвлет-коэффициентов, относительная погрешность 5% в ‫ܮ‬ଶ - норме(в) 3% вейвлет-коэффициентов, относительная погрешность 10% в ‫ܮ‬ଶ - норме(г) 1% вейвлет-коэффициентов, относительная погрешность 15% в ‫ܮ‬ଶ - норме18Формирование запросовизображений(а) Исходное изображение «Ирисы» Ва-Гога(б) Разложение на вейвлет-коэффициенты. Размер круга соответствуетвеличине, цвет – знаку коэффициента.(в) Усечение коэффициентов, остаются только самые большие19(г) Квантование оставшихся коэффициентов20Сравнение изображений21Вейвлет Габора22Биометрическая идентификацияпо радужной оболочке глаза23Выделение радужки , max ,బ ,బ 2, ଴ , ଴ – окружность с центром ଴ , ଴ и радиусом .24Вейвлет-разложение , ∙ ∙బ ∙ బమ / మ∙ బ1, если 0 0,иначе1, если 0 0,иначеమ / మ ∙ ∙ ∙ 25Измерение сходства и различияଵଶ଴ସ଼ – векторIrisCode"#$ , $ – расстояние Хэмминга26Классификатор27.