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

[Igors]

А я уж думал "бобик спекся" Иногда приятно ошибиться
По kd-tree

1) Сачкует

Код

C++ (Qt)
index = (index + 1) % m_dimensions;
 

Никто не обещал равномерного распределения по осям, ось деления надо вычислять при построении и хранить в элементе/ноде.

2) Multi-threading

Код

C++ (Qt)
    node* m_best = nullptr;
    real_t m_best_dist = 0.0;
 

Это сразу делает поиск "not thread-safe" (отрезали самое дорогое)  

3)

Код

C++ (Qt)
    vec_t predict(const vec_t & data, size_t tests = 10) const
    {
        size_t N = std::min(m_kdtree.num_nodes(), (tests) ? tests : size_t(1));
 
        vec_t output = m_kdtree.nearest(data).second;
 
        const real_t r = sqrt(3.0/m_kdtree.dimensions()) * m_kdtree.radius();
 
        std::uniform_real_distribution<real_t> dist(-r, r);
 
        for (size_t i = 1; i < N; ++i)
        {
            vec_t p = data;
            for (auto & x : p)
                x += dist(m_gen);
 
            auto stat = m_kdtree.nearest(p).second;
 
            for (size_t j = 0; j < output.size(); ++j)
            {
                output[j] += (stat[j] - output[j])/(i+1);
            }
        }
 
        return output;
    }
 

Как я понял: находим ближайшую к запросной точке. Затем N раз "jitter' (сдвигаем запросную на случайное смещение) и находим ближайшую к сдвинутой. Если я понял верно, то это плохо "зато" медленно. Дерево способно находить N ближайших, с радиусом или без, если хотите - еще пожуем. Предлагаю оформить public поиск так

Код

C++ (Qt)
void kd_tree::nearest( 
    const vec_t & ip,   // запросная точка
    double & ioRadius,   // напр -1 если начального R нет
    int iMaxNear;          // макс число ближайших (-1 если всех)
    std::vector<vec_t *> & outPt );   // вектор найденных ближайших
 

Ну ладно, занялся делом вместо сахара - уже хорошо  

Edit: пожалуй лучше макс число ближайших передавать явно (а не шифровать в outPt)

[m_ax]

1) Сачкует

Код

C++ (Qt)
index = (index + 1) % m_dimensions;
 

Никто не обещал равномерного распределения по осям, ось деления надо вычислять при построении и хранить в элементе/ноде.

Не понял.. Причём здесь равномерное/неравномерное распределение точек? Индекс (index) циклически бегает по компонентам вектора.
Т.е. при построении дерева мы сравниваем i-тые компоненты, затем на следующем шаге сравниваются следующие (i+1) компоненты и так далее..

Код

C++ (Qt)
index = (index + 1) % m_dimensions;
 
middle->m_left = make_tree(begin, middle, index); // Здесь индекс уже для следующей компоненты вектора
 
middle->m_right = make_tree(std::next(middle, 1), end, index);
 

2) Multi-threading

Ну да, это можно подправить, например, передавая их (m_best и m_best_dist) в сам метод..

Как я понял: находим ближайшую к запросной точке. Затем N раз "jitter' (сдвигаем запросную на случайное смещение) и находим ближайшую к сдвинутой. Если я понял верно, то это плохо "зато" медленно. Дерево способно находить N ближайших, с радиусом или без, если хотите - еще пожуем. Предлагаю оформить public поиск так

Да, такой вот наивный подход пока.. Я не совсем понял с радиусом. Я не могу заранее делать предположения о его величине.. Более того, для различных входных точек он (радиус) также будет (в общем случае) меняться.
Или мы о разных вещах говорим?

[Igors]

Не понял.. Причём здесь равномерное/неравномерное распределение точек? Индекс (index) циклически бегает по компонентам вектора.

"Отнюдь". Напр все 2D точки имеют одинаковую координату Y, отличаются лишь координатой X. Тогда деление по Y бесполезно, все деления должны быть по X

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

Примерно так (писал здесь)

Код

C++ (Qt)
   struct CFindData {
     vec_t mPt;
     double mRad;
     int mMaxNear;
     std::vector<node *> mOut;
   };
 
    void nearest(node ** beg, node ** end, size_t index, CFindData & data )
    {
        auto num = end - beg;   // std::distance?
        if (num < 1)  return;
        node *& mid = *(beg + dist / 2);
 
        bool scanLeft = true, scanRight = true;
 
// пытаемся добавить точку
       data.AddPoint(mid);
        if (num < 2)  return;
 
// если радиус есть (был или появился после AddPoint),
// то отсекаем точки что заведомо далеко 
       if (data.mRad >= 0.0) {
         real_t dx = mid->get(index) - data.mPt[index];
 
         scanRight = (dx < data.mRad);
         scanLeft  = (dx > -data.mRad);
     }
 
     index = (index + 1) % m_dimensions;   // халтура
 
// продолжаем рекурсивно
     if (scanLeft)
        nearest(beg, &mid, index, data);
 
     if (scanLeft)
        nearest(&mid + 1, end, index, data);
   }
 

Теперь добавление точки

Код

C++ (Qt)
bool CFindData::AddPoint( node * pt )
{
// гонорируем точку за границами радиуса
   double dist = pt->distance(mPt);
   if ((mRad >= 0.0) && (dist >= mRad)) return false;
 
// вставляем точку в сортированный вектор
   auto it = std::lower_bound(mOutPt.begin(), mOutPt.end(),  pt, CompDistFunc);
   mOutPt.insert(it, pt);
 
// вычисляем новый радиус
  if (mMaxNear > 0) {
     if (mOutPt.size() > mMaxNear)     
       mOutPt.resize(mMaxNear);
 
     if (mOutPt.size() >= mMaxNear)     
       mRad = mPt.distance(*mOutPt.back());
   }
   else
      assert(mRad >= 0.0);   // хотя бы 1 (mRad и mMaxNear) должен быть задан
 
   return true;
}
 

Edit: подправил num (условие выхода)

[m_ax]

Хорошо, спасибо! Я согласен с тем, что если мы задаём при запросе конкретный радиус, то за один проход дерева мы в принципе сможем собрать все точки лежайшие внутри гиперсферы радиуса R. В худшем случае, если радиус будет превышать размер "облака точек" то это выйлется асимптотически за O(N*log(N)), что тождественно quick_sort.. А в лучшем случае это будет за O(log(N)).
Я так и не понял по поводу радиуса.. Но буду ещё экспериментировать.. В выходные буду раскуривать эту тему)

[Igors]

Я согласен с тем, что если мы задаём при запросе конкретный радиус, то за один проход дерева мы в принципе сможем собрать все точки лежайшие внутри гиперсферы радиуса R. В худшем случае, если радиус будет превышать размер "облака точек" то это выйлется асимптотически за O(N*log(N)), что тождественно quick_sort.. А в лучшем случае это будет за O(log(N)).
Я так и не понял по поводу радиуса.. Но буду ещё экспериментировать.. В выходные буду раскуривать эту тему)

Если радиус "слишком велик", то дело сведется к прямому перебору, все ноды будут найдены, дерево ничего не отсечет. Однако если задано mMaxNear, то по достижении макс числа точек радиус появится автоматычно и будет неуклонно уменьшаться. Т.е. если R изначально не задан, то сначала будет прямой перебор, а потом начнутся отсечки

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