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

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

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

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

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

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

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

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

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

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

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

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

Фактически он состоит из двух частей. В первой части нам необходимо разбить наше множество входящих векторов на группы.
Этим занимается метод 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 - это второй параметр в этом алгоритме, который задаёт пользователь.

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

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

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


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

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

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

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

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

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

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

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

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

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

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