Методы обработки краевых и угловых случаев трехмерного массива - PullRequest
Новая
       1

Методы обработки краевых и угловых случаев трехмерного массива

0 голосов
/ 05 марта 2019

У меня есть трехмерный массив с плавающей точкой фиксированного размера и алгоритм, который должен проверять значение каждой ячейки массива и 7 ближайших соседей этой ячейки в положительных направлениях x, y и z.Следующий фрагмент кода работает для случаев тела, но он не оценивает конечные ячейки в крайних случаях, когда x, y или z равен Size-1, потому что у них может не быть соседа в определенном направлении.

#include <stdint.h>
#include <iostream>

const size_t SIZE     = 10;
const float THRESHOLD = 0.0f;

float array[SIZE][SIZE][SIZE];

int main() {
    for (size_t x = 0; x < SIZE - 1; x++)
    for (size_t y = 0; y < SIZE - 1; y++)
    for (size_t z = 0; z < SIZE - 1; z++) {
        uint8_t mask = 0x00;

        if (array[x    ][y    ][z    ] > THRESHOLD) { mask |= 0x01; }
        if (array[x + 1][y    ][z    ] > THRESHOLD) { mask |= 0x02; }
        if (array[x    ][y + 1][z    ] > THRESHOLD) { mask |= 0x04; }
        if (array[x + 1][y + 1][z    ] > THRESHOLD) { mask |= 0x08; }
        if (array[x    ][y    ][z + 1] > THRESHOLD) { mask |= 0x10; }
        if (array[x + 1][y    ][z + 1] > THRESHOLD) { mask |= 0x20; }
        if (array[x    ][y + 1][z + 1] > THRESHOLD) { mask |= 0x40; }
        if (array[x + 1][y + 1][z + 1] > THRESHOLD) { mask |= 0x80; }

        std::cout << "x: " << x << " y: " << y << " z: " << z << " mask: " << (int)mask << std::endl;
    }

    return 0;
}

Мое быстрое решение заключалось в том, чтобы обернуть проверки, которые должны обращаться к соседу в определенном направлении, с помощью операторов if, чтобы увидеть, было ли это направление на краю.Если ячейка не имеет соседа, оценка должна быть эквивалентна тому, что она находится ниже порогового значения.

int main() {
    //no longer SIZE - 1, checks all cells now
    for (size_t x = 0; x < SIZE; x++)
    for (size_t y = 0; y < SIZE; y++)
    for (size_t z = 0; z < SIZE; z++) {
        uint8_t mask = 0x00;

        if (array[x][y][z] > THRESHOLD) {
            mask |= 0x01;
        }

        if (x != SIZE - 1) {
            if (array[x + 1][y][z] > THRESHOLD) {
                mask |= 0x02;
            }
        }

        if (y != SIZE - 1) {
            if (array[x][y + 1][z] > THRESHOLD) {
                mask |= 0x04;
            }
        }

        if (x != SIZE - 1 && y != SIZE - 1) {
            if (array[x + 1][y + 1][z] > THRESHOLD) {
                mask |= 0x08;
            }
        }

        if (z != SIZE - 1) {
            if (array[x][y][z + 1] > THRESHOLD) {
                mask |= 0x10;
            }
        }

        if (x != SIZE - 1 && z != SIZE - 1) {
            if (array[x + 1][y][z + 1] > THRESHOLD) {
                mask |= 0x20;
            }
        }

        if (y != SIZE - 1 && z != SIZE - 1) {
            if (array[x][y + 1][z + 1] > THRESHOLD) {
                mask |= 0x40;
            }
        }

        if (x != SIZE - 1 && y != SIZE - 1 && z != SIZE - 1) {
            if (array[x + 1][y + 1][z + 1] > THRESHOLD) {
                mask |= 0x80;
            }
        }

        std::cout << "x: " << x << " y: " << y << " z: " << z << " mask: " << (int)mask << std::endl;

    }
}

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

Ответы [ 2 ]

1 голос
/ 05 марта 2019

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

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

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

std::array<float, 7> getVoxelAndNeighbors(int x, int y, int z)

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

Другая возможность можетобрабатывать поверхности (и края (и углы)) отдельно от «общего» тела цикла: 

for (z = 1; z < SIZE-1; ++z)
  for (y = 1; y < SIZE-1; ++y)
    for (x = 1; x < SIZE-1; ++x)
      { /* Your original body */ }

for (y = 1; y < SIZE-1; ++y)
  for (x = 1; x < SIZE-1; ++x)
    { /* Handle positive and negative z surface */ }

// (Repeat for x, y)

for (x = 1; x < SIZE-1; ++x)
  { /* Handle edges in x direction */ }

// (Repeat for x, y)

// Handle all eight corners.

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

0 голосов
/ 05 марта 2019

Существует несколько возможных подходов:

  1. Просто добавьте тест и ветвь для каждой операции, как у вас есть.

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

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

  2. Добавьте значения часового в ваш массив.

    То есть, увеличьте ваш массивна [SIZE+1][SIZE+1][SIZE+1] и затем сохраните ваше безопасное ложное значение в записях дозорного array[SIZE][*][*], array[*][SIZE][*] и array[*][*][SIZE]

    Компромисс состоит в том, что вам больше не нужны тесты и ветки в вашем коде, но вашимассив увеличился и ухудшилось месторасположение ссылки.

  3. Напишите свои различные случаи явно.

    Вы уже написали случай [0..SIZE-2][0..SIZE-2][0..SIZE-2] - теперь напишите три оставшихся случая для[SIZE-1][0..SIZE-2][0..SIZE-2], [SIZE-1][SIZE-1][0..SIZE-2] aи изолированный дальний угол [SIZE-1][SIZE-1][SIZE-1].

    Эта версия предоставляет вам наименьшие данные, с наименьшим количеством ненужных ветвей, но с наибольшей сложностью.

...