SVD-сжатие, модификации

Министерство образования и науки российской федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Кубанский государственный университет

Факультет математики и компьютерных наук

Кафедра математических и компьютерных методов

Направление 02.03.01 Математика и компьютерные науки

Выпускная квалификационная работа бакалавра

Тема:

SVD-сжатие, модификации

Выполнила К.Г. Твердова

курс, группа 43.1

Руководитель, д.ф.-м.н.,

профессор В.Г. Лежнев

Краснодар, 2015

СОДЕРЖАНИЕ

Введение

. Сингулярное разложение

1.1 Определение SVD

.2 Методы нахождения сингулярного разложения

.3 Алгоритм SVD

.4 Сингулярное разложение и собственные значения матрицы

2. Пространства матрицы и SVD

2.1 Сингулярное разложение и нормирование матриц

3. SVD-сжатие

. Метод максимизации столбцов

. Практическая часть

Заключение

Список использованных источников

ВВЕДЕНИЕ

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

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

Эта проблема и была поставлена для решения в данной работе. Здесь предполагается реализация возможности сжатия изображения с помощью SVD-сжатия.

Для решения поставленной цели необходимо рассмотреть ряд сопутствующих задач:

1.   Рассмотреть особенности сингулярного разложения

2.      Разработать алгоритм, реализующий сжатие изображения

.        Применить теорию о сингулярном разложении для сжатия изображения при помощи MathCAD, разработав программу для сжатия изображения

.        Произвести анализ динамики сингулярных чисел

.        Сделать выводы

1. СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ

.1 Определение SVD

Теорема. Для любой вещественной (п х п)-матрицы A существуют две вещественные ортогональные (п х п)-матрицы U и V такие, что

Более того, можно выбрать U и V так, чтобы диагональные элементы  имели вид

где r - ранг матрицы A. В частности, если A невырождена, то

Индекс r элемента  есть фактическая размерность собственного пространства матрицы A.

Столбцы матриц U и V называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы  называются сингулярными значениями [1].

Пусть A - (m х n)-матрица и ей в соответствие поставлен линейный оператор, также обозначаемый A. Формулу сингулярного разложения ^T можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства R^m в элементы пространства Rⁿ представим в виде последовательно выполняемых линейных операций вращения, растяжения и вращения. Число ненулевых элементов на диагонали матрицы  есть фактическая размерность матрицы A.

Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором A множества векторов из одного векторного пространства в другое.

.2 Методы нахождения сингулярного разложения

Для нахождения сингулярного разложения существует 4 основных метода - QR-итераций, Якоби, метод «разделяй-и-влавствуй», бисекции [2].

В настоящее время «разделяй-и-влавствуй» один из самых быстрых алгоритмов отыскания сингулярных чисел и сингулярных векторов матриц порядка больше 25. Однако алгоритм «разделяй-и-властвуй» не гарантирует высокой относительной точности для малых сингулярных чисел.

Метод бисекции способен вычислять сингулярные числа на заданном интервале. Таким образом, для реализации сингулярного разложения были выбраны метод Якоби и QR-итераций, т.к. метод Якоби является наиболее точным, а QR-итераций наиболее быстрым и надежным.

В отличие от QR-алгоритма, метод Якоби не предполагает первоначального приведения к трехдиагональной форме, а работает с исходной плотной матрицей. Он работает медленнее, однако способен вычислять сингулярные числа и сингулярные векторы намного точнее, чем другие алгоритмы.

.3 Алгоритм SVD

Рассмотрим приближенное линейное описание матрицы  вида

, (1)

где  и .

Значения  для данного значения k найдены из условия минимума выражения

, (2)

при ограничениях нормировки

, (3)

и упорядоченности

Выражения (1), (2), (3) запишем в матричных обозначениях:

где матрицы , , . Если значение r достаточно велико, то .

Так будет заведомо при . Минимальное значение r, при котором выполнимо равенство ^T, равно рангу матрицы A.

Один из возможных алгоритмов нахождения сингулярного разложения заключается в следующем. Найдем последовательно векторы u_k, v_k и сингулярные числа для . В качестве этих векторов берутся нормированные значения векторов a_k и b_k соответственно:

Процедура нахождения векторов u_k, v_k начинается с выбора наибольшей по норме строки b₁₁ матрицы A. Для k = 1 формулы нахождения векторов a_1i, b_1i имеют вид:

Для вычисления векторов u_k, v_k при  используется вышеприведенная формула, c той разницей, что матрица A заменяется на скорректированную на k-м шаге матрицу

.4 Сингулярное разложение и собственные значения матрицы

Сингулярное разложение обладает свойством, которое связывает задачу отыскания сингулярного разложения и задачу отыскания собственных векторов. (Собственный вектор x матрицы A - такой вектор, при котором выполняется условие ), число  называется собственным числом. Так как матрицы U и V ортогональные, то есть

, (4)

где I - единичная матрица размерности , то из (4) следует, что

,

 (5)

Умножая оба выражения справа соответственно на U и V получаем

,

 (6)

Из выражения (6) следует, что столбцы матрицы U являются собственными векторами матрицы, а квадраты сингулярных чисел  ее собственными значениями. Также столбцы матрицы V являются собственными векторами матрицы , а квадраты сингулярных чисел являются ее собственными значениями.

2. ПРОСТРАНСТВА МАТРИЦЫ И SVD

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

Существует так называемое экономное представление сингулярного разложения матрицы.

Согласно этому представлению при , диагональная матрица  имеет пустые строки, а при  - пустые столбцы. Поэтому существует еще одно экономное представление [1]:

,

в котором

Нуль-пространство матрицы A - набор векторов х, для которого справедливо высказывание . Собственное пространство матрицы A - набор векторов b, при котором уравнение  имеет ненулевое решение для х. Обозначим  и  - столбцы матриц U и V.

Тогда разложение может быть записано в виде:

,

где .

Если сингулярное значение , то  и  находится в нуль-пространстве матрицы A, а если сингулярное значение , то вектор  находятся в собственном пространстве матрицы A.

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

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

Пусть V₀ будет набором тех столбцов , для которых , а V₁ - все остальные столбцы .

Также, пусть U₀ будет набором столбцов , для которых , а U₁ - все остальные столбцы , включая и те, для которых .

Тогда, если r - количество ненулевых сингулярных значений, то имеется r столбцов в наборе V₀ и столбцов в наборе V₁ и U₁, а также столбцов в наборе U₀.

Каждый из этих наборов формирует базис векторного пространства матрицы A:

V₀ - ортонормальный базис для ортогонального комплементарного нуль-пространства A,

V₁ - ортонормальный базис для нуль-пространства A,

U₀ - ортонормальный базис для собственного пространства A,

U₁ - ортонормальный базис для ортогонального комплементарного нуль-пространства A.

2.1 Сингулярное разложение и нормирование матриц

Рассмотрим изменение длины вектора х до и после его умножения справа матрицу A. Евклидова норма вектора определена как:

При умножении вектора x на матрицу A справа, длина результирующего вектора Ax изменяется.

Если матрица A ортогональна, длина вектора Ax остается неизменной. В противном случае, с помощью выражения, можно вычислить, насколько матрица A растянула вектор x.

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

Евклидова норма матрицы определяется так. Пусть x является n-мерным вектором, и A - матрица размерности . Тогда Евклидова норма матрицы

Альтернативной Евклидовой норме является норма Фробениуса:

Если известно сингулярное разложение, то обе эти нормы легко узнать. Пусть -сингулярное разложение ()-матрицы A.

Тогда

 и

Сингулярные значения матрицы A - это длины осей эллипсоида, заданного множеством .

3. SVD-СЖАТИЕ

Матрица изображения А = (a_ij), размерности n x n, представима в виде A = USV^T, где U, V - ортогональный матрицы, а S-диагональная, на главной диагонали которой расположены (в порядке убывания) неотрицательные значения s_k - сингулярные числа матрицы.

Величина

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

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

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

Рассмотрим алгоритм SVD сжатия изображений. Так как сингулярные значения быстро убывают, то, начиная с некоторого номера p, их вклад в общую сумму  достаточно мал, и эти оставшиеся значения можно не учитывать при восстановлении исходного изображения. В формуле A = USV^T нет необходимости целиком сохранять матрицы U, S, V, что позволяет производить сжатие изображения.

Справедливо приближенное неравенство

где S_p = diag (s₁,…, s_p, 0,…, 0), в матрицах  первые p столбцов и первые p строк соответственно совпадают со столбцами и строками матриц U, V, а остальные элементы равны нулю.

Следовательно, вместо матрицы A размерности n x n требуется сохранять матрицы размерности n x p, p x n и строку из p чисел s_k. Т.е. получим сжатие с коэффициентом

Анализ влияния сохраняемого количества сингулярных значений на качество сжатого черно-белого изображения. Выбор числа p можно характеризовать значениями параметра :

4. МЕТОД МАКСИМИЗАЦИИ СТОЛБЦОВ

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

Максимизация столбца. Пусть А = (a_ij) - вещественная квадратная матрица порядка n. Будем обозначать a_k = (a_1k, …, a_nk)^T ее k-ый столбец, а через |a_k|, (a_k, a_p) - евклидову норму и скалярное произведение вектор-столбцов.

Обозначим через  ортогональную матрицу с элементами , а остальные диагональные элементы равны единице, внедиагональные - нулю.

Рассмотрим матрицу . Для столбцов матрицы В имеем

Угол  будем выбирать так, что норма первого столбца  была бы максимальной. Максимизирующий угол , определяется следующим правилом:

а) если , то

, (7)

б) иначе  определяется равенство

 (8)

Свойство 1. Если , то , т.е. норма первого столбца не убывает при рассматриваемом преобразовании матрица А.

Свойство 2. Если , то , т.е. новые столбцы  ортогональны.

Итерационная последовательность матриц. Пусть , где  - ортогональная матрица перестановки первого столбца с максимальным по норме столбцом матрицы А. Рассмотрим последовательность

(9)

где  целочисленный индекс p = p(k) изменяется циклически от 2 до n при возрастании k. Номер матрицы  обозначает номер столбца, который преобразуется вместе с первым. Матрицы  с углом  определяются, кроме , правилами пункта 1. Так как первый столбец  является наибольшим в матрице , то выполняются свойства 1 и 2 для столбцов всех матриц .

Лемма. Последовательность  сходится поэлементно при  [3].

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

Следствие. Первый столбец  предельной матрицы  уже не может быть увеличен нашей итерационной процедурой.

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

Сингулярное разложение. Процедурой (7) - (9) будем называть построение последовательности (9), максимизирующей указанный столбец. Эта процедура для первого столбца приводит к матрице , первый столбец которой ортогонален остальным, обозначим эту матрицу через , то есть  и .

Для второго столбца матрицы  может быть осуществлена процедура (7) - (9) (предварительно поставив на его место максимальный по норме среди старших по номеру), индекс p = p(k) изменяется циклически от 3 до n при возрастании k. Полученную в пределе матрицу обозначим ; ее первые два столбца ортогональны остальным. Предельную ортогональную матрицу в этой процедуре будем обозначать , т.е. .

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

Пусть , где s_k - норма k-го столбца матрицы . Мы имеем , W - ортогональная, и для матрицы А получаем SVD-разложение A.

скорость связь сжатие изображение

5. ПРАКТИЧЕСКАЯ ЧАСТЬ

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

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

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

Результаты исследования динамики сингулярных чисел p (табл. 1) и коэффициентов сжатия  (табл. 2) различных размерностей:

Таблица 1

Таблица 2

На результаты исследования влияли качество и композиции изображений, а при p = 768 влиял размер, так как использовались матрицы изображения размерности m x n.

Также было выполнено сжатие цветного изображения.

Таблица 3

Изображение размера 256х256

Таблица 4

Изображение 512х512

Таблица 5

Изображение 1024х768

Таблица 6

Изображение цветное 1280х1024

ЗАКЛЮЧЕНИЕ

Для поставленной в работе задачи было выполнено:

.     изучено сингулярное разложение и SVD-сжатие изображений,

2.      разработан алгоритм сжатия изображения в MathCAD,

.        изучена особенность динамики сингулярных чисел,

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

.        произведено сжатие цветного изображения.

В практической части были использованы BMP-изображения различных размеров: 256х256, 512х512, 1024х768. По p сингулярным числам найдены F- норма Фробениуса сжатых изображений, числа  - отношения сжатой F-нормы к F-норме исходного изображения и коэффициенты сжатия .

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.   Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений: Пер. с англ. - М.: Мир, 1980. - 279 с.

2.      Деммель Дж. Вычислительная линейная алгебра - М.: Мир, 2001. - 429 с.

.        Прэтт У. Цифровая обработка изображений: Пер. с англ. - М.: Мир, 1982. - Кн. 1 - 312 с.

.        Сингулярная разложение [Электронный ресурс]

.        Стрижов В.В. Информационное моделирование [Электронный ресурс]

.        Логинов Н.В. Сингулярное разложение матриц. - М.: МГАПИ, 1996. - 80 с.

.        Смирнов С.И., Михайлов В.В., Остриков В.Н. Применение рандомизированного метода главных компонент для сжатия данных гиперспектральной съемки // Современные проблемы дистанционного зондирования Земли из космоса. - М.: Издательство КИРАН, 2014. - С. 9-17.

9.   Харебов К.С. Компьютерные методы решения задачи наименьших квадратов и проблемы собственных значений. - Владикавказ: Издательство СОГУ, 1995. - 76 с.

10.    Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. - М.: Физматгиз, 1963. - 536 с.

.        Марчук Г.И. Методы вычислительной математики. - М.: Наука, 1980. - 456 с.

.        Кабанихин С.И., Кривотько О.И. Сингулярное разложение в задаче об источнике // Сибирский журнал вычислительной математики. - Новосибирск: Издательство СО РАН, 2012. - Т. 15, №2. - С. 101-107.

.        Загребнюк В.И., Насиров Ф.В. Разложение цветных изображений на сингулярные компоненты // Восточно-европейский журнал передовых технологий. - Харьков: Технологический центр, 2013. - Т. 4, №2 (64). - С. 15 - 19.

.        Савостьянов Д.В. Быстрая полинейная аппроксимация матриц и интегральные уравнения. - М. ИВМ РАН, 2006. - 144 с.

.        Голуб Дж., Ван Лоун Ч. Матричные вычисления: Пер. с англ. - М.: Мир, 1999. - 548 с.

.        Ибрагимов И.В. Новый подход к решению задачи обобщённого сингулярного разложения // Матричные методы и вычисления. - М.: ИВМ РАН, 1999. - С. 193-201.

.        Сильвестров И.Ю. Анализ сингулярного разложения линеаризованного оператора динамической теории упругости для случая вертикального сейсмического профилирования // Вычислительные технологии. - Новосибирск: Издательство СО РАН, 2007. - Т. 12, №6. - С. 90-100.