Сообщество - Лига математиков
Добавить пост

Лига математиков

383 поста 1 864 подписчика
3162

Какой порядок правильный?

Какой порядок правильный? Мемы, Математика, Две женщины орут на кота, American Chopper, Дискуссия, Картинка с текстом
Показать полностью 1
1541

Как воссоздать изображение всего по нескольким пикселям

Эта статья дает возможность познакомиться с такой методикой получения и восстановления сигнала, как Compressive Sensing.
Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Множество всех возможных изображений 2 на 2 с цветами, закодированными одним битом

Пространство изображений огромно, невероятно огромно, но при этом очень мало. Задумайтесь об этом на минуту. Из сетки размером всего 8 на 8 пикселей можно создать 18 446 744 073 709 551 616 различных чёрно-белых изображений. Однако из этих 18 квинтиллионов изображений очень немногие покажутся осмысленными человеческому взгляду. Большинство изображений, по сути, выглядит как QR-коды. Те, которые покажутся человеку осмысленными, принадлежат к тому множеству, которое я называю естественными изображениями. Они представляют крошечную долю пространства изображений 8 на 8. Если мы рассмотрим мегапиксельные изображения, то доля естественных изображений становится ещё меньше, почти ничтожной, однако содержит любое изображение, которое можно придумать. Так чем же эти естественные изображения так уникальны? И можем ли мы использовать эту фундаментальную разницу в собственных интересах?


Спектральное пространство


Рассмотрим два представленных ниже изображения. Оба изображения имеют размер 512 на 512 пикселя. Если вычислить гистограмму значений пикселей, то можно понять, что эти распределения идентичны. И это на самом деле так. Левое изображение такое же, как правое, только пиксели перемешаны случайным образом. Тем не менее между ними есть фундаментальное отличие. Одно выглядит как «снег» на экране старого телевизора, а другое — это лицо человека.

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Слева: случайное изображение. Справа: классическое тестовое изображение женщины с тёмными волосами. Оба изображения принадлежат к пространству изображений 512 на 512

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


Описание этих двух изображений в пространстве Фурье представлено ниже. Для отображения величины коэффициента Фурье использована логарифмическая шкала. Разница между двумя изображениями теперь очевидна. Одно имеет гораздо больше ненулевых коэффициентов Фурье, чем другое. На языке математики говорится, что естественное изображение является разреженным по базису Фурье. Именно разреженность отличает естественные изображения от случайных. Давайте же используем эту разницу с пользой для себя!

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Амплитуда преобразований Фурье обоих изображений. Использована логарифмическая шкала

Воссоздание изображений по нескольким пикселям, задача с высокой степенью неопределённости

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Записано всего 10% пикселей

Рассмотрим следующую ситуацию: по какой-то неизвестной причине большинство фотодатчиков камеры оказалось неисправным. Скопировав на компьютер только что сделанную фотографию своей жены (или матери, или друга), вы обнаружили, что изображение получилось таким, как показано выше. Можно ли как-то восстановить изображение?


Допустим, что мы точно знаем, какие фотодатчики исправны. Обозначив как x ∊ ℝⁿ неизвестное изображение (где n — общее количество пикселей, и мы считаем, что оно представлено в виде вектора), а как y ∊ ℝᵐ ненулевые яркости пикселей, зафиксированные датчиками, мы можем записать

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Здесь C — это разреженная матрица измерений m × n. Все элементы, соответствующие неисправным фотодатчикам, равны нулю, и она содержит только m ненулевых элементов, соответствующих исправным датчикам. Следовательно, наша задача — выяснить, каким был x исходного изображения, учитывая, что мы наблюдаем только несколько его пикселей.


С точки зрения математики, это задача с высокой степенью неопределённости. У нас гораздо больше неизвестных, чем уравнений. Эта задача имеет бесконечное количество решений. Значит, вопрос сводится к тому, какое решение из бесконечного множества является тем, которое мы ищем. Естественным способом решения такой задачи было бы принятие того, что решение имеет наименьшую норму ℓ₂. Это можно формализовать как следующую задачу оптимизации:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

решение которой задаётся так:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Матрица C соответствует измерениям единичных пикселей, её строки получены из единичной матрицы n × n. В такой ситуации решение задачи оптимизации не особо нам поможет, поскольку оно вернёт только повреждённое изображение (произведение матриц справа сводится к Cᵀ). Очевидно, что это нам не подходит. Но можно ли найти решение получше?


Используем разреженность в спектральном пространстве


При обсуждении уникальных особенностей естественных изображений мы увидели, что они являются разреженными в пространстве Фурье, поэтому давайте этим воспользуемся. Обозначив как Ψ отображение матрицы n × n из пространства Фурье в пространство пикселей, мы получим следующий вид уравнения измерений:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

где s — преобразование Фурье x (т. е. x = Ψs). Это по-прежнему задача с высокой степенью неопределённости, но теперь у нас есть дополнительная информация о решении, которое мы ищем. Мы знаем, что оно должно быть разреженным. Введя псевдонорму ℓ₀ для s (т. е. его число ненулевых элементов), мы сможем сформулировать следующую задачу оптимизации:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

К сожалению, это задача комбинаторики, очень быстро становящаяся нерешаемой. Чтобы найти её решение, потребуется проверить все возможные сочетания. К счастью в своей революционной работе 2006 года Канде et al. [1, 2] показал, что при условии разумных допущений решение изложенной выше задачи можно получить (с высокой вероятностью) при помощи решения более простой задачи:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Здесь норма ℓ₁ — это сумма абсолютных значений вектора s. Сегодня хорошо известно, что использование нормы ℓ₁ кроме превращения задачи оптимизации в выпуклую, склонно отдавать предпочтение разреженным решениям. Несмотря на свою выпуклость, эту задачу всё равно может быть достаточно сложно решить на стандартном компьютере. В дальнейшем мы используем более ослабленную версию, задаваемую следующим образом:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

где λ — это задаваемый пользователем параметр, управляющий равновесием между соответствием ограничениям и необходимой разреженностью решения. Эту задачу оптимизации называют Basis Pursuit Denoising. При помощи проксимальных операторов она решается чрезвычайно быстро. Ниже представлена реализация на Julia с использованием StructuredOptimization.jl.

using StructuredOptimization
" " "
Simple implementation of basis pursuit denoising using StructuredOptimization.jl
INPUT
- - - - -
C : The measurement matrix.
Ψ : Basis in which x is assumed to be sparse.
y : Pixel measurements.
λ : (Optional) Sparsity knob.
OUTPUT
- - - - - -
x : Estimated image.
" " "
function bpdn(C, Ψ, y ; λ=0.1)
# - - > Initialize variable.
x = Variable(eltype(y), size(Ψ, 2))
# - - > Solve the compressed sensing problem.
@minimize ls(C * Ψ * x - y) + λ*norm(x, 1)
return ~x
end

Кроме того, мы можем воспользоваться тем фактом, что для спектральных преобразований произведение матрицы и вектора Ψs при помощи алгоритма быстрого преобразования Фурье можно вычислить за O(n log n) операций вместо O(n²).

using StructuredOptimization
" " "
Simple implementation of basis pursuit denoising using StructuredOptimization.jl
INPUT
- - - - -
m, n : Size of the image in both direction.
idx : Linear indices of the measured pixels.
y : Pixel measurements.
λ : (Optional) Sparsity knob.
OUTPUT
- - - - - -
x : Estimated image.
" " "
function bpdn(m, n, idx, y ; λ=0.1)
# - - > Initialize variable.
x = Variable(eltype(y), m, n)
# - - > Solve the compressed sensing problem.
@minimize ls(idct(x)[idx] - y) + λ*norm(x, 1)
return ~x
end

Хотя до сих пор мы предполагали, что Ψ является преобразованием Фурье, в этом фрагменте кода мы использовали косинусное преобразование, являющееся более эффективным преобразованием для изображений. Теперь у нас есть всё необходимое, поэтому давайте вернёмся к исходной задаче. На изображении ниже сравнивается истинное изображение с его реконструкцией при помощи ℓ₁.

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Слева: оригинал изображения. Справа: изображение, воссозданное при помощи compressive sensing на основании данных всего 10% пикселей

Даже несмотря на то, что исправно работало всего 10% фотодатчиков камеры, формулировка этой задачи восстановления изображения в рамках Compressed Sensing позволяет нам воссоздать достаточно точное приближение к тому, каким было исходное изображение! Очевидно, что оно всё равно неидеально, однако учитывая обширность пространства изображений и бесконечное количество решений нашей задачи, нужно признать, что результат довольно хорош!


Заключение


Методика Compressed Sensing совершила революцию в сфере обработки сигналов. Если мы заранее знаем, что сигнал, с которым работаем, разрежен по указанному базису, то compressed sensing позволяет восстановить его по гораздо меньшему количеству сэмплов, чем предполагается по теореме выборки Найквиста-Шеннона. Кроме того, она позволяет значительно сжимать данные непосредственно на этапе получения, уменьшая таким образом необходимый объём хранилища данных. Также Compressed Sensing привела к возникновению неожиданных новых технологий, например, однопиксельной камеры, разработанной Университетом Райса, или новых техник обработки для создания визуализаций МРТ в медицине. Я не сомневаюсь, что в ближайшие несколько лет мы станем свидетелями множества новых способов применения этой методики.


Compressed sensing — это гораздо более глубокая область математики, чем можно судить по этому ознакомительному посту. Существует ещё множество не рассмотренных нами вопросов, например:


- Каково наименьшее количество необходимых измерений?


- Могут ли некоторые измерения быть информативнее других?


- Как выбирать эти измерения, имея базис Ψ?


- Существуют ли другие нормы, лучше подходящие для изображений?


Для ответа на эти вопросы потребуется гораздо больше математики, чем можно представить в посте. Если вы хотите знать больше, то крайне рекомендую изучить оригиналы статей, ссылки на которые я указал в конце. Также стоит изучить потрясающий веб-сайт Numerical Tours Габриеля Пейре или последнюю книгу Брантона и Кутца [3], а также соответствующий канал на YouTube (здесь и здесь).


Ссылки на научные работы


[1] Candès E., Romberg J., Tao T. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied mathematics. 58(8): 1207–1223. 2006.


[2] Candès E. Compressed sensing. IEEE Transactions on Information Theory. 52(4): 1289–1306. 2006.


[3] Brunton S. L. and Kutz J. N. Data-driven science and engineering: machine learning, dynamical systems, and control. Cambridge University Press, 2019.

Автор оригинала: Jean-Christophe B. Loiseau

Перевод: https://habr.com/ru/company/timeweb/blog/549024/

Показать полностью 12
3739

Хруст на сузуки

Хруст на сузуки Мотоциклисты, Физика, Математика, Светофор, Динозавры, Комментарии на Пикабу, Скриншот

#comment_214337272

Показать полностью 1
9

Ищу - Курс высшей математики

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

4098

И почему никто не может понять красоту математики

И почему никто не может понять красоту математики Юмор, Математика, Фракталы, Бумага, Граф, Картинка с текстом

4х-мерный фрактал упаковки сфер и его соответствующая диаграма Коксетера

20

Рейтинг регионов России по количеству победителей на математической олимпиаде

Регионы по количеству победителей на Всероссийской олимпиаде школьников по математике с 1992 по 2021 год

328

Пифагорова комната... - Алексей Савватеев

В какой комнате хранятся ВСЕ доказательства математики и где она находится? 😉 Как формулируется задача об этой комнате, решена ли она и почему эта комната называется пифагоровой?

Рассказывает Алексей Савватеев, математик и матэкономист, доктор физико-математических наук, научный руководитель Кавказского Математического Центра АГУ, ректор Университета Дмитрия Пожарского, профессор МФТИ, научный руководитель ЦДПО РЭШ, ведущий научный сотрудник ЦЭМИ РАН, популяризатор математики среди детей и взрослых.

14

Задача

Придумал, нечаянно, задачу и, сходу, решил ее не правильно.

Задача Логическая задача, Задача, Круг, Колесо, Шар, Геометрия

Да, и вопрос - почему?

Показать полностью 1
6

Помогите решить задачу

Прислала подруга в Вайбер такую задачу. Помогите с разбором решения, сам честно не осилил( Сын у неё запнулся на ней.А теперь и самому интересно.

Помогите решить задачу Задача, Математика
7

Самое лучшее объяснение интеграла

Вопрос: какое на ваш взгляд существует самое удачное и простое объяснение смысла интеграла?

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