Восстановление изображения

[Igors]

Файлы (включая исходник) здесь

Алгоритм: берем строку имеджа и интерполируем пиксели лежащие между 2 базовыми. Веса считаем как 1 / расстояние. Получаем Pass_1. Затем делаем то же самое по столбцу имеджа Pass_2 и по диагоналям Pass_3 и Pass_4. Ну и для приличия немного подблюрим (аттач)

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

[m_ax]

Спасибо за пример. Идея в общем понятна) И по скорости и по качеству весьма недурно.
Правда, всё это хорошо, когда у вас все данные упорядоченны и отображены в виде матрицы с random access доступом за O(1) 

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

[Igors]

Правда, всё это хорошо, когда у вас все данные упорядоченны и отображены в виде матрицы с random access доступом за O(1) 

Совершенно верно, все это лишь "игры с картинкой".
[off]
Какой идиотский это навязанный термин "random access" - ну чем было плохо "прямой доступ"
[/off]

Но с другой стороны можно рассматривать большие размерности как входных, так и выходных векторов.   

Алгоритм который бы работал в 2D/3D/4D и.т.д. вероятно будет "слишком общим" и поэтому мало ценным/интересным. Меня никогда не останавливало соображение типа "да это, мол, не распространяется на N измерений", тем более что 3 измерения (реальное геометрическое пр-во) - более чем достаточно чтобы нажить грыжу.

Подход приведённый мной не подразумевает такой упорядоченности: есть набор входных и выходных векторов и всё)

А можно как-то ознакомиться с этим подходом? (если это не секрет). Вы упоминаете о некой vanda, но что это - я без понятия. Может ушами прохлопал, please "ткните носиком"

Интерполяция (конкретно интерполяция в 3D) - одна из "вечных" задач, она всегда актуальна. Однако постановка существенно отличается от простого "запрашиваем цвет по (x. y)". Это типа "сейчас отсюда вылетит птичка" , на деле все гораздо хуже. Основные моменты

1) Представительность/достоверность. Напр в 3D запросная точка может оказаться там "куда Макар телят не гонял", такую надо считать (а не интерполировать)

2) Не все может интерполироваться со всем, напр освещенность одной грани куба не имеет ничего общего с другой (хотя точки на разных гранях могут быть сколь угодно близко)

3) "Покрытие" (добрая половина работы). Это тут хорошо, мол, "извне" даны 5% достоверных. А по жизни базовые точки выбираются самостоятельно, и необходимо обеспечить максимальное попадание множества запросных точек туда где интерполяция разумна. Первый шаг (splattering) похож на Ваш - да, делаем N базовых, равновероятных. Но это лишь "начало большого пути" 

Не, ну старый ретроград не совсем уж чужд новых идей/веяний, но как/куда приткнуть эти нейросети (или что еще)? Если по-прежнему делать все что выше - то где "выйгрышь"? А не делать и уповать на чудо - не наш метод. Да и 76 минут обучения как-то пугает.. за что боремся?
 

[m_ax]

А можно как-то ознакомиться с этим подходом? (если это не секрет). Вы упоминаете о некой vanda, но что это - я без понятия. Может ушами прохлопал, please "ткните носиком"

Нет, не секрет) Сегодня-завтра напишу детали алгоритма..

[m_ax]

Итак, суть алгоритма.

Фактически он состоит из двух частей. В первой части нам необходимо разбить наше множество входящих векторов на группы.
Этим занимается метод train.

Код

C++ (Qt)
void train(const training_dataset & dataset, const real_t & radius = 0.0)
    {
        if (dataset.empty())
            return;
 
        for (size_t i = 0; i < dataset.size(); ++i)
        {
            auto it = m_groups.begin();
            bool is_added = false;
 
            while (it != m_groups.end())
            {
                it = std::find_if(it, m_groups.end(), [&](const group_t & g)
                {
                    return g.is_contain(dataset[i].first, sqr(radius));
                });
 
                if (it != m_groups.end()) {
                    it->add( dataset[i].first, dataset[i].second );
                    is_added = true;
                    ++it;
                }
            }
 
            if (!is_added) {
                m_groups.emplace_front(dataset[i].first, dataset[i].second);
            }
        }
    }
 

Каждая группа содержит "базисный" вектор - просто центр масс всех точек, что попали в неё (об этом ниже) и среднее значение
выходного вектора, соответствующего базисной точки. В данном случае, критерий принадлежности какой-либо точки группе определяется
просто как попадание её внутрь гиперсферы радиуса R (radius - это параметр, который пользователь устанавливает сам. Чем больше R, тем меньше групп в итоге будет).
Сам центр сферы находится отсчитывается от базиса. Если точка попала в группу, то базис пересчитывается (центр масс смещается) и пересчитывается среднее значение выходного вектора.
Разумеется одна и та же входная точка может принадлежать нескольким группам.

Код

C++ (Qt)
Т.е. если точка принадлежит групе, то происходит следующее:
void add(const vec_t & input, const vec_t & output)
        {
            ++m_count;
 
            for (size_t i = 0; i < m_stat.size(); ++i)
            {
                m_stat[i] += (output[i] - m_stat[i])/m_count;
            }
 
            for (size_t i = 0; i < m_basis.size(); ++i)
            {
                m_basis[i] += (input[i] - m_basis[i])/m_count;
            }
        }
 

Понятно, что разбиение на группы не единственно и имеет комбинаторно большое число вариантов.
После того, как все исходные данные разбиты на группы можно переходить ко второй части алгоритма: Предсказание (метод predict)

Код

C++ (Qt)
vec_t predict(const vec_t & data, const real_t & q = 0.5) const
    {
        if (m_groups.empty())
            return vec_t();
 
        if (m_groups.size() == 1)
            return m_groups.begin()->statistics();
 
        m_groups.sort( [&](const group_t & a, const group_t & b)
        {
            return a.sqr_distance_from(data) < b.sqr_distance_from(data);
        });
 
        vec_t stat(m_groups.begin()->statistics_size(), 0.0);
 
        real_t w = (1.0 - q)/(1.0 - std::pow(q, m_groups.size()));
 
        for (const auto & group : m_groups)
        {
            for (size_t j = 0; j < stat.size(); ++j)
            {
                stat[j] += w*group.statistics(j);
            }
            if (w < err)
                break;
            w *= q;
        }
 
        return stat;
    }
 

Суть этого метода заключается в следующем: Мы подаём на вход произвольный входной вектор data.
И далее сортируем наш список групп в порядке возрастания расстояния от входного вектора data до базисных векторов
групп. Т.е. в отсортированном списке первыая группа будет всех ближе к data, вторая группа чуть дальше и т.д..
Теперь осталось найти результирующий выходной вектор.
Его компоненты stat_i определяются по формуле:
stat_i = sum_n^groups.size ( c_n * (group_n).statistics_i ),
где коэффициенты c_n = w * q^n и  удовлетворяют условию нормировки:
sum_n c_n = 1,
так, что w = (1 - q)/(1 - q^N), где N - число групп, причём 0 < q < 1, и характеризует число ближайших соседей
дающих вклад в итоговое значение выходного вектора. Чем ближе q к единице, тем большее число ближайших соседей будет учтено
и тем более "разблюреней", будет результат, и напротив. q - это второй параметр в этом алгоритме, который задаёт пользователь.

Вот, собственно и всё.    

Исходники с примером в аттаче.

[Igors]

Позвольте "попридираться" к деталям

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

Типовая подлянка: после того как центр пересчитан, следующая точка может уже не попасть в группу. Или попасть. В любом случае получается зависимость от порядка добавления точек, так нельзя

Мы подаём на вход произвольный входной вектор data.
И далее сортируем наш список групп в порядке возрастания расстояния от входного вектора data до базисных векторов
групп. Т.е. в отсортированном списке первыая группа будет всех ближе к data, вторая группа чуть дальше и т.д..

Любая сортировка на этапе использования не годится. Ну хотя бы потому что multi-threaded = обязон. И, судя по времени, очень может быть что где-то насвистели и месите данные (а не указатели)

А вот саму идею/суть я, наверное, не понял. Пока я вижу только "найти ближайших", да, есть такая подзадача, и она не так уж проста. Но есть типовые способы, напр ocTree или kd-tree (оба кстати распространяются на N измерений). С ними время должно быть до секунды, ну ладно, пару секунд. Или разбиение на группы/кластеры несет еще какой-то смысл (не уловил какой) ?

Еще деталь: такие, казалось бы, совершенно "элементарные" вещи как "радиус R" в 3D далеко не очевидны Напр рендерится нечто "далекое" (у линии горизонта) - здесь разумный R порядка километров. Но на той же картинке у ближнего (к камере) объекта радиус R может быть миллиметр и меньше.

[m_ax]

Типовая подлянка: после того как центр пересчитан, следующая точка может уже не попасть в группу. Или попасть. В любом случае получается зависимость от порядка добавления точек, так нельзя

Это нормально (если "точка выйдет из группы"), поскольку вместе с этим и вклад от её значения (выходного вектора) также будет давать всё более малый и малый вклад в итоговое среднее значение.

Любая сортировка на этапе использования не годится. Ну хотя бы потому что multi-threaded = обязон.

Как то уж слишком радикально.. Без сортировки не обойтись, поскольку данные неупорядочены и вы не можете знать заранее, какая точка попадёт в метод predict.
Потом, что мешает мне распараллелить  процесс? Заряжу thread_pool и буду ему скармливать очередной входящий вектор..Не вижу проблемы..

Но есть типовые способы, напр ocTree или kd-tree (оба кстати распространяются на N измерений).

Да, соглашусь, здесь напрашивается kd-tree.. Надо попробовать.
    

Еще деталь: такие, казалось бы, совершенно "элементарные" вещи как "радиус R" в 3D далеко не очевидны  

Для меня очевидна) Т.е. я всегда могу оценить порядок этой величины, который будет для меня приемлем в контексте моей задачи.

[m_ax]

Да, соглашусь, здесь напрашивается kd-tree.. Надо попробовать.

Правда, здесь возникает такой неприятный момент.. Если я фиксирую точность в определении компонент выходного вектора (x_i +- err) и фиксирую параметр q,
то я, в принципе, могу однозначно сказать (читай подсчитать) сколько мне нужно ближайших соседей (n) упорядоченных по расстоянию от запрашиваемой точки.
Чем меньше q, тем, соответственно, меньше таких соседей нужно:

Код

C++ (Qt)
n = 1 + log(err/(1-q))/log(q) + O(q^N)  // 0 < q < 1
 

Если n << N (N - training size) то сейчас, в лучшем случае, я получу такой отсортированный список за O(N). А с kd-tree за один запрос,  смогу ли я получить такой отсортированный список за меньшее время? Мне вот это совсем не очевидно..  

Т.е. для наглядности, у нас есть training_data (2D)

Код

C++ (Qt)
input_data = { {1, 2}, {12, -34}, {5, 7}, ..., {x_N, y_N} }
 

На вход метода predict подаётся вектор { x, y }.
Мне нужно за минимальное время получить отсортированное по расстоянию от точки {x, y} до каждой из точек input_data подмножество input_data, размером n.

Не выйлется ли это за то же самое O(N)?

[Igors]

Мне нужно за минимальное время получить отсортированное по расстоянию от точки {x, y} до каждой из точек input_data подмножество input_data, размером n.

Обычная техника работы с kd_tree:

- на каждом делении дерева добавляем "медиану" с расстоянием < R в (статический) массив и подсчитываем суммарный вес. Если он превысил некоторую величину, это понимается как сигнал "ближайших слишком много, берем только самых ближних". Тогда сортируем массив по весу и последующие точки вставляем в сортированный массив (если вес > последнего то вытесняем его) или игнорируем (если <). Это соответствует автоматьчному уменьшению R. Часто также используется не вес а "макс число ближайших"

Недостаток кв-tree: требуется фиксированный R, если это не так, то приходится использовать макс R, но тогда скорость поиска падает

[Igors]

Для меня очевидна) Т.е. я всегда могу оценить порядок этой величины, который будет для меня приемлем в контексте моей задачи.

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

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

Ваша постановка (если не так понял - поправьте):

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

Профессиональная постановка:

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

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

[Old]

Ваша постановка...

Профессиональная постановка...

Это вы поскромничали.
Нужно было так:

Неправильная постановка...

Истинная постановка...

[m_ax]

Нужно было так:

Неправильная постановка...

[Истинная постановка...

За что я обожаю этот форум)

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

Да, хорошо..
Только дайте мне время разобраться с kd-tree)
(У меня сейчас университетская деятельность львиную долю времени сжирает..)

[m_ax]

Обычная техника работы с kd_tree:

- на каждом делении дерева добавляем "медиану" с расстоянием < R в (статический) массив и подсчитываем суммарный вес. Если он превысил некоторую величину, это понимается как сигнал "ближайших слишком много, берем только самых ближних". Тогда сортируем массив по весу и последующие точки вставляем в сортированный массив (если вес > последнего то вытесняем его) или игнорируем (если <). Это соответствует автоматьчному уменьшению R. Часто также используется не вес а "макс число ближайших"

Недостаток кв-tree: требуется фиксированный R, если это не так, то приходится использовать макс R, но тогда скорость поиска падает

Вот! А если я не знаю заранее этот самый R? Как тогда мне обозначить/построить это дерево?
Я понимаю, конечно, что я его, в принципе, могу организовать,
 но когда на вход predict поступают совершенно случайные точки, мне это дерево каждый раз придётся перестраиваить?

[Igors]

Вот! А если я не знаю заранее этот самый R? Как тогда мне обозначить/построить это дерево?
Я понимаю, конечно, что я его, в принципе, могу организовать,

 но когда на вход predict поступают совершенно случайные точки, мне это дерево каждый раз придётся перестраиваить?

Можно найти "просто ближайших" не имея начального R, конечно это обойдется дороже. Как работает дерево при наличии R

- Взяли средний эл-т массива, у него есть "ось деления" (это единственнык доп данные нужные дереву). Допустим это ось X. Сравниваем расстояние по X от этого среднего эл-та до запросной точки с R. Если оно больше то одну из  половинок массива (в зависимости от знака расстояеия) можно не смотреть, там точно никто не дотянется. Повторяем для оставшейся половинки. Ну а если dist_x меньше R, то придется (рекурсивно) парить обе половинки.

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

[m_ax]

Разобрался с k-d tree. Действительно, мощная вещь) Время обработки изображения сразу на два порядка сократилось!
Спасибо igors за наводку.
Более того, качество восстановленного изображения стало даже лучше, и это при том, что использовался алгоритм "на коленке"..

Исходники приаттачиваю..