Оптимизация билинейной выборки с произвольным доступом

Question

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

FOR EACH PIXEL (x,y)      
  vec = vectors[x,y]                    // Get vector
  val = get(img, x + vec.x, y + vec.y)  // Get input at <x,y> + vec
  output[x,y] = val                     // Write to output

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

FUNCTION get(in,x,y)
  ix = floor(x); iy = floor(y)      // Integer upper-left coordinates
  xf = x - ix;   yf = y - iy        // Fractional parts

  a = in[ix,iy];   b = in[iy+1,iy]   // Four bordering pixel values
  b = in[ix,iy+1]; d = in[ix+1,iy+1]

  ab = lerp(a,b,xf)                  // Interpolate
  cd = lerp(c,d,xf)
  RETURN lerp(ab,cd,yf)

и lerp() это просто

FUNCTION lerp(a,b,x) 
  RETURN (1-x)*a + x*b

Предполагая, что ни входное изображение, ни векторный массив не известны заранее, какие виды оптимизации высокого уровня возможны? (Примечание: «Использовать GPU» - это мошенничество.) Я могу подумать о том, чтобы переставить интерполяционную математику в get(), чтобы мы могли кэшировать считывание пикселей и промежуточные вычисления для заданного (ix, iy). Таким образом, если последовательный доступ к одному и тому же подпиксельному квадру, мы можем избежать некоторой работы. Если векторный массив известен заранее, то мы можем изменить его так, чтобы координаты, переданные в get(), были более локальными. Это также может помочь с локальностью кэша, но за счет того, что записи в output будут повсюду. Но тогда мы не можем делать такие причудливые вещи, как масштабирование векторов на лету или даже перемещать эффект деформации из первоначального предварительно рассчитанного местоположения.

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

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

Answer 1

Интересная проблема.

Ваше определение проблемы в основном обеспечило непредсказуемый доступ в [x, y] - поскольку может быть предоставлен любой вектор. Предполагая, что векторное изображение имеет тенденцию ссылаться на локальные пиксели, самая первая оптимизация будет состоять в том, чтобы обеспечить прохождение памяти в подходящем порядке, чтобы максимально использовать локальность кэша. Это может означать сканирование 32 * 32 блоков в цикле "для каждого пикселя", чтобы в [x, y] попадать в одни и те же пиксели как можно чаще за короткое время.

Скорее всего, производительность вашего алгоритма будет ограничена двумя вещами

1. Как быстро вы можете загрузить vectors[x,y] и in[x,y] из основной памяти
2. Сколько времени занимает умножение и сумма

Существуют инструкции SSE, которые могут умножать несколько элементов одновременно, а затем складывать их вместе (умножать и накапливать). Что вы должны сделать, это вычислить

af = (1 - xf) * ( 1 - yf )
bf = (    xf) * ( 1 - yf )
cf = (1 - xf) * (     yf )
df = (    xf) * (     yf )

, а затем вычислить

a *= af
b *= bf 
c *= cf
d *= cf
return (a + b + c + d)

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

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

Если вы используете инструкции предварительной выборки на вашем процессоре для предварительной выборки in[vectors[x+1, y]] во время обработки vectors[x,y], вы можете улучшить производительность памяти, иначе процессор не сможет предсказать ваш случайный обход памяти в противном случае.

Последний способ улучшить производительность вашего алгоритма - это обрабатывать куски входных пикселей сразу, т.е. x[0..4], x[5..8] - это позволяет вам развернуть внутренние математические циклы. Однако вы, скорее всего, ограничены памятью, что это не поможет.