задачка
 

с яндексового контеста, матрицей *.npy дана картинка
три канала rgb, целые циферки от 0 до 255
85% пикселей рандомно похерено во тьму

восстановить качество до psnr > 20
(желающие сами можуть взять картинку побить на ргб матрицы и рандомно дропнуть 85% пикселей)


как бы стал решать? лимит времени 1-2 часа (в контесте 6 задач на 6 часов)

Я на работе вообще-то... Поэтому крайне схематично:

0. Насколько я понял чёрные точки (0,0,0) подлежат восстановлению по данным цветных точек.

1. Для каждой восстанавливаемой точки строим "функцию распределения" в малой окрестности точки: цвет -> количество точек с таким цветом

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


3. Если функция распределения имеет 2 пика вокруг двух конкретных значений цвета - предполагаем, что через окрестность точки проходит линейный контур с разными цветами по разные стороны. Определяем наклон контура и по какую сторону контура находится восстанавливаемая точка и восстанавливаем цветом той части, в которой оказалась точка.

4. Три и более пиков - игнорируем, такие зоны скорее всего малы по площади, а за два часа все варианты перебрать всё равно не успеем.

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

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

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

так это не кспеху, я то уже отмахался, другие мысли интересно послушать

Расскажи хоть как сам делал.
И как там со сборщиком мусора?
Я когда пробовал с Яндекс-контестом играться обнаружил, что для java он не учитывает память, освобождённую сборщиком мусора, поэтому для прохождения лимита по памяти все алгоритмы приходится переписывать для работы на однократно выделенном массиве байтов.

Попожже. Может Afa, Zab тоже выскажутся.

Afa, Zab
как бы решали задачку?

мне в лом
скорей - матрицу усреднения наложил б. эдак 7х7 для начала. с учетом двух третей - ну вон вова сказал за треугольники. я б билинейку предпочел. но этому методу мало доверия. большой процент выбитых точек
а вообще - разодрать на каналы ycbcr и сначала гонять по яркости усредняя выпавшие точки. матрицей прям. будет уже достаточно. дальше по разностным каналам, можно тупо уменьшить вдвое разрешение по ним, при интерполяции точек учитывать только не ч0рные

А контура объектов при этом не расплывутся?

а наплевать
пять шестых картинки похерены. я ж не зря с матрицы 7х7 начал. и то мало будет наверн
и эт. если ты про уменьшение вдвое - так стандартно жипеги так и пакуют. и яркостный канал даёт контура и резкость

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