Краевые/граничные условия многомерного массива

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

//For each value on the image    
for (i=0;i<3*width*height;i++){
    //For each filter value
    for (j=0;j<9;j++){
        if (notOutsideEdgesCondition){
            *(**(outArray)+i)+= *(**(pixelArray)+i-1+(j%3)) * (*(filter+j));
        } 
    }
}

Я использую арифметику указателя, потому что, если бы я использовал нотацию массива, у меня было бы 4 цикла, и я пытаюсь иметь как можно меньше циклов. Моя проблема в том, что мой notOutsideEdgesCondition выходит из-под контроля, потому что мне нужно рассмотреть 8 пограничных случаев. У меня есть следующие обработанные условия

  • Левая колонка: ((i%width)==0) && (j%3==0)
  • Правая колонка: ((i-1)%width ==0) && (i>1) && (j%3==2)
  • Верхний ряд: (i<width) && (j<2)
  • Нижний ряд: (i>(width*height-width)) && (j>5)

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


person kirbuchi    schedule 31.05.2010    source источник


Ответы (2)


Да, есть гораздо лучший способ. Напишите быстрый цикл для обработки случаев, когда гарантированно не будет граничных проблем. Он будет состоять из области от второго до предпоследнего столбца и от второго до предпоследнего ряда. Затем вы можете написать четыре подпрограммы для обработки каждой из сторон (строка 0, столбец 0, строка N и столбец N) и вручную закодировать последние четыре точки.

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

person swestrup    schedule 31.05.2010
comment
Я попробую это, потребуется больше кода, но, надеюсь, я смогу сделать это проще. Кроме того, не могли бы вы указать мне правильное направление, чтобы ускорить расчеты адресации? - person kirbuchi; 31.05.2010
comment
Я сделал быстрый поиск в Google, чтобы попытаться найти для вас руководство по развертыванию вычислений адресации массива, но не нашел его. Короче говоря, избегайте как можно большего количества вычислений попиксельной адресации. Используйте указатель, который увеличивается от пикселя к пикселю по мере работы, и удалите все операции по модулю и умножения. Чтобы реализовать адресацию ядра 3x3, вы должны либо поддерживать 3 указателя (по одному на ваше текущее место в каждой строке), либо один указатель и постоянный «шаг» (смещение между строками), который добавляется. Используйте несколько циклов, чтобы знать, когда добавлять /вычесть шаг. Данг. Нет больше персонажей - person swestrup; 31.05.2010
comment
Итак, теперь я обработал 4 боковых случая и буду вручную кодировать угловые случаи. Подход с тремя указателями для ядра кажется лучшим, потому что я могу индивидуально отключить каждую строку ядра при решении пограничных случаев. Имея это в виду, я могу действовать аналогичным образом с массивом изображений и легче разделить их для последующей реализации CUDA, что является моей конечной целью. Большое спасибо. PS: я поищу книгу или учебник по оптимизации развертывания и адресации массивов. - person kirbuchi; 01.06.2010

Хороший совет — добавить дополнительную строку в начало массива и еще одну в конец (сделайте то же самое для столбцов).

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

Просто идея :)

person ereOn    schedule 31.05.2010
comment
Я думаю, что это не займет так много памяти. я могу попробовать - person kirbuchi; 31.05.2010
comment
Добавление строки границы вокруг всего массива будет работать, но включает копирование массива, что может быть не самым эффективным методом (опять же, это может быть, в зависимости от стратегий кэширования ваших процессоров). - person swestrup; 31.05.2010