Как по 2-мерной матрице вычислить представляющую ее функцию f(x,y)?

Question

[AndreyMust19]

Математическая задача.
Есть black-white BMP-изображение, записанное двоичной матрицей (0,1) или матрицей байтов (0...255).
Как по этой матрице вычислить функцию f(x,y), которая возвращает все значения этой матрицы в том же диапазоне?
Что-то вроде f(x,y) = (15 + 3.4*sin(x) + 15.09f*y^2 + ...) > 0;, где убирая последние элементы формулы мы получаем менее точный результат, по сравнению с исходным изображением.

Смысл - вычислить в программе по этой функции исходное изображение, чтобы не хранить изображение целиком и уменьшить размер программы. Так сказать, заменить память на вычисления.
Ищу алгоритм вычисления такой функции на Си (можно Си# или Lua), а лучше онлайн-сервис, на который можно загрузить изображение и получить описывающую его формулу с заданной точностью.
Да, есть еще вариант хранить как PNG, а не массивом пикселей, но для одного изображения код декодера наверняка будет соизмерим с размером исходного изображения.

Answer 1

[AngReload]

Предлагаю к прочтению - Изобретаем JPEG.

Comments

[Александр Скуснов]

Да, самое лучшее - спектральный анализ (напр., дискретное косинусное преобразование).

Answer 2

[rPman]

В универсальном случае, как ни странно, на текущий момент такой функцией являются нейронные сети, на хабре была статья про исследователей, эксперементирующих с восстановлением видео с использованием мизерной функции (нейронной сети, причем там получались считанные килобайты на все видео).
https://habr.com/post/372337/

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

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

Answer 3

[Сергей Соколов]

Можно пытаться приближенно найти функцию, заранее предположив её порядок – методом градиентного спуска. Но это будет «размытое» приближение.

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

0 1
1 0

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

spoiler

Идеально опишет некая ломаная линия из прямых отрезков. Да и то, по пути из (1, 1) в (2, 4) заденет непричастные клетки.

Comments

[AndreyMust19]

То есть записать функцию, которая описывает траекторию рисования пикселей?

[Сергей Соколов]

функцию f(x,y), которая возвращает все значения этой матрицы в том же диапазоне

Функцию ожидаете непрерывную? Т.е. она добавит бесконечное множество дополнительных точек, к конечному множеству исходных. Да и к исходным будет лишь приближаться, скорее всего, с какой-то точностью.

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