6 Генерация признаков Карунен-Лоэв (Лекции 2016 года)

Генерация признаков на основелинейных преобразований• Генерация признаков осуществляется черезпреобразования исходных измерений образов (вчастности, изображений).• Целью такой генерации признаков являетсясокращение информации до “значимой” путёмпреобразования исходного множества измерений вновое множество признаков.• Обычно задача состоит в выделении низкочастотныхкомпонент, содержащих основную информацию.1Место генерации признаков впостроении системы распознаванияобразовОбразыСенсор(измеритель)ГенерацияпризнаковСелекцияпризнаковПостроениеклассификатораОценкасистемыЦель – генерация признаков через линейные преобразования исходных векторовизмерений.Базовая идея – преобразовать данное множество измерений в новое множествопризнаков.2Идея1) Представить исходный образ в виделинейной комбинации базисных образов.Исходныйобраз=Σ Ci ×i-й базисныйобраз2) Составить вектор признаков изкоэффициентов разложения (C0,…,CN-1)3Вектор измеренийПустьx(0), x(1),..., x( N − 1) – множество исходных измерений,xT = [ x(0),..., x( N − 1)] – соответствующий вектор столбец.x=x(0)x(1)….x(N-1)Tx = [ x(0), x(1), …, x(N-1)]4Эрмитов операторМатрицей, эрмитово сопряжённой к данной, называютHHматрицу A =|| aij || получаемую из исходной матрицыA = ||aij||путем её транспонирования и перехода кHкомплексно сопряжённой, то есть aij*= a ji .Матрицу, равную своему эрмитовому сопряжению,HA=Aназывают эрмитовой, или самосопряжённой:5Унитарные матрицыПусть AN × N - унитарная матрица.Для действительной матрицы условие унитарностиобозначает, что матрица AN × N ортогональная, т.е.AN−1× N = ANT × N .Для комплексной матрицы AN × N условие унитарностиобозначает, что−1HAN × N = AN × N ,где матрица ANH× N - транспонированная и сопряженная.6Базисные вектораПусть A = [ a(0), a(1),..., a( N − 1)] - представление матрицы ввиде столбцов.Вектора-столбцы a (i ) называются базисными векторами. a0H  H  a1 Hy = A x=⋅xM H  a N −1 где a H (0), a H (1),..., a H ( N − 1)] – строки из транспонированныхстолбцов a (i ) .7Разложение по базисным векторамВектор измерений x можно представить в виде линейнойкомбинации базисных векторовN −1x = ( AA ) x = ( AA ) x = AA x = Ay = ∑ y (i ) ai−1HH.Поскольку ‫ܣ ∙ ܣ‬ு = ‫ ܧ‬или ܽ௜ு ∙ ܽ௝ = ൫ܽ௜ , ܽ௝ ൯ = ߜ௜௝ , получаемi =0൫‫ݔ‬, ܽ௝ ൯ = ‫ ݔ‬ு ∙ ܽ௝ = ෍ ‫ݕ‬ሺ݅ ሻ ∙ ൫ܽ௜ , ܽ௝ ൯ = ‫)݆(ݕ‬ேିଵ௜ୀ଴Таким образом, в силу ортогональности векторов a (i ) междусобой, y (i ) – это проекция вектора x на базисные вектора:N −1x = ∑ y (i ) ⋅ aii =08Цель разложения по базиснымвекторамМы хотим использовать подмножество компонент вектора y вкачестве признакового описания исходного образа x .9Разложение по базисным матрицамВ задачах анализа изображений множество образовпредставляется двумерными массивами‫ݔ‬ሺ݅, ݆ሻ, ݅, ݆ = 0,1, … , ܰ − 1,определёнными, как ܰ × ܰ матрицы, а не вектора.Обработка матриц как векторов размерности ܰ ଶ не эффективна.Альтернативная возможность – преобразовать матрицу ܺ черезмножество базисных матриц.10Базисные матрицыПусть ܷ, ܸ – унитарные ܰ ×-матрицы.‫ݑ‬௜ – вектора-столбцы матрицы ܷ,‫ݒ‬௝ – вектора-столбцы матрицы ܸ.Определим преобразование:ܻ = ܷு ∙ ܺ ∙ ܸи обратноеܺ = ܷ ∙ ܺ ∙ ܸு.ܺ = ෍ ෍ ܻ(݅, ݆) ∙ ‫ݑ‬௜ ‫ݒ‬௝ுேିଵ ேିଵ௜ୀ଴ ௝ୀ଴∗‫ݒ‬௝଴⋯‫ݑ‬௜଴ ∙⋮‫ݑ‬௜ ‫ݒ‬௝ு = ቎∗‫ݑ‬௜ ேିଵ ∙ ‫ݒ‬௝଴‫ݑ‬௜଴ ∙ ‫ݒ‬௝∗ேିଵ⋱⋮቏ = ‫ܣ‬௜௝⋯ ‫ݑ‬௜ ேିଵ ∙ ‫ݒ‬௝∗ேିଵ11Представление через базисныематрицыܺ = ෍ ෍ ܻ(݅, ݆) ∙ ‫ݑ‬௜ ‫ݒ‬௝ு = ෍ ෍ ܻ(݅, ݆) ∙ ‫ܣ‬௜௝ேିଵ ேିଵேିଵ ேିଵ௜ୀ଴ ௝ୀ଴௜ୀ଴ ௝ୀ଴Всего получается ܰ ଶ базисных матриц.Но если получится сделать такое разложение, чтобы матрица ܻбыла диагональной, то количество базисных матриц сокращаетсядо ܰ.12Преобразование Карунена-ЛоеваПусть x – вектор измерений образа.

Рассматриваем его каквектор случайных величин.Тогда полученный вектор признаков y = AT x такжеявляется случайным.Целью преобразования является такой выбор матрица A ,чтобы для вектора признаков y = AT x , имело место:E [ y (i ) ⋅ y ( j )] = 0 для всех i ≠ j ,т.е. чтобы признаки были взаимно не коррелированны.Такое свойство признаков характеризует их«минимальность», поскольку нет «избыточностиописания»: каждый признак не дублирует остальныепризнаки.13Корреляционная матрица векторапризнаковОбозначим R y = E[ y ⋅ y T ].×=Матрица (1×N)Матрица (N×1)Матрица (N×N)E[ y (0) 2 ]E[ y (0) y (1)]2E[y(1)y(0)]E[y(1)]Ry = MM E[ y ( N − 1) y (0)] E[ y ( N − 1) y (1)]L E[ y (0) y ( N − 1)] L E[ y (1) y ( N − 1)] OMLE[ y ( N − 1) 2 ] По главной диагонали стоят дисперсии, а остальные элементы –парные корреляции компонент вектора признаков.14Корреляционная матрица вектораизмеренийПоскольку y = AT x и, следовательно, yT = xT A получаем:TTTTTTR y = E[ y ⋅ y ] = E[ A x ⋅ x A] = A E[ x ⋅ x ] A = A Rx A,гдеRx = E[ x ⋅ xT ] - корреляционная матрица вектора измерений x .Теперь задача состоит в том, чтобы выбрать такую матрицу A ,при которой матрица Ry будет диагональной.15Матрица преобразованияВыберем в качестве базисных векторов ai собственные векторакорреляционной матрицы Rx .1) Матрица Rx положительно полуопределённая, её собственныезначения ߣ௜ ≥ 0.2) Матрица Rx симметрическая, её собственные вектораортогональны между собой.3) Матрица A = [ a(0), a(1),..., a( N − 1)], составленная изсобственных векторов матрицы Rx , приводит её к диагональной:0  λ0 0 M0  0 λ1 MT.A Rx A = Λ = L L O L 0 0 M λN −1 16Преобразование Карунена-ЛоеваОписанное преобразование называетсяпреобразованием Карунена-Лоева.

Оно имеетфундаментальное значение, т.к. оно приводитк построению некоррелированных признаков.Другое название:Метод главных компонент (Пирсон, 1901 г.)17Свойства преобразованияКарунена-ЛоеваРазложение по базисным векторам:N −1x = ∑ y ( i ) aii =0Определим новый m -мерный вектор ( m < N ):m −1xˆ = ∑ y (i ) aii =0где x̂ – проекция вектора x на подпространство, соответствующеепервым m компонентам этого вектора.Вектор x̂ можно рассматривать, как аппроксимацию вектора x спомощью x̂ .18Ошибка аппроксимации2E x − xˆ = E N −12N −1∑ y(i)aii = 0mN −1T = E  ∑∑ ( y (i )ai ) ( y (ij)ai )  = i jN −1N −1= ∑ E  y 2 (i )  = ∑ aiT E  xxT ai = ∑ aiT λi ai = ∑ λi.Из этого следует, что выбирать нужно m базисных векторов смаксимальными собственными значениями.i =mi=mi=mi=mВ преобразовании Карунера-Лоева в качестве критериявыступает наилучшее приближение исходных измерений.19Задача распознавания лицМетод «Собственных лиц» (Eigenfaces) –основан на преобразовании КаруненаЛоэва (методе главных компонент)20Преобразование обучающего наборалиц в одну общую матрицу21Вычисление «собственных лиц»Дано:Mизображений лиц размером h × w.1.

Каждое изображение преобразуется в вектор размера D = hwи помещается в множество векторов {Γ1 , Γ2 ,L, ΓM }. Лицаприводятся к одинаковому масштабу, фон (волосы, шея)должен быть одинаков или удалён.1 M2. Вычисляется «среднее лицо»: Ψ =Γi и отличия от∑M i =1среднего Φ i = Γi − Ψ .1 MTT3. Вычисляется матрица ковариации С =ΦΦ=AA, где∑i iM i =1D×MA = {Φ1 , Φ 2 ,L, Φ M }∈ R .4. Вычисляются собственные вектора матрицы С на основематрицы AT A размерности M × M .22Собственные лицаСреднее лицоДва первых собственных лицаТри последних собственных лица23Главной целью метода главных компонентявляется значительное уменьшениеразмерности пространства признаков такимобразом, чтобы оно как можно лучшеописывало «типичные» образы,принадлежащие множеству лиц.

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