Как транслировать или векторизовать линейную интерполяцию 2D-массива, который использует scipy.ndimage map_coordinates? - PullRequest
0 голосов
/ 22 декабря 2018

Я недавно столкнулся с препятствиями, когда дело доходит до производительности.Я знаю, как вручную выполнить цикл и выполнить интерполяцию от исходной ячейки ко всем остальным ячейкам путем грубого форсирования / циклической обработки каждой строки и столбца в массиве 2d.

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

Я ищу способ оптимизировать этот цикл, я знаю о векторизации и вещании, просто не знаю, какЯ могу применить его в этой ситуации.

Я объясню это с помощью кода и цифр

import numpy as np
from scipy.ndimage import map_coordinates
m = np.array([
    [10,10,10,10,10,10],
    [9,9,9,10,9,9],
    [9,8,9,10,8,9],
    [9,7,8,0,8,9],
    [8,7,7,8,8,9],
    [5,6,7,7,6,7]])

origin_row = 3
origin_col = 3
m_max = np.zeros(m.shape)
m_dist = np.zeros(m.shape)

rows, cols = m.shape
for col in range(cols):
    for row in range(rows):
        # Get spacing linear interpolation
        x_plot = np.linspace(col, origin_col, 5)
        y_plot = np.linspace(row, origin_row, 5)

        # grab the interpolated line
        interpolated_line = map_coordinates(m,
                                      np.vstack((y_plot,
                                                 x_plot)),
                                      order=1, mode='nearest')
        m_max[row][col] = max(interpolated_line)
        m_dist[row][col] = np.argmax(interpolated_line)

print(m)
print(m_max)
print(m_dist)

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

1.) входной массив

input array

2.) Первый цикл от 0,0 до начала координат (3,3)

first cell to origin

3.) Это вернет [10 9 98 0] и максимум будет 10, а индекс будет 0

5.) Вот вывод для использованного мной образца массива

sample output of m

Вот обновление производительности на основе принятого ответа.

times

Ответы [ 2 ]

0 голосов
/ 23 декабря 2018

Чтобы ускорить код, вы можете сначала создать x_plot и y_plot вне циклов, а не создавать их несколько раз каждый:

#this would be outside of the loops
num = 5
lin_col = np.array([np.linspace(i, origin_col, num) for i in range(cols)])
lin_row = np.array([np.linspace(i, origin_row, num) for i in range(rows)])

, затем вы можете получить к ним доступ в каждомцикл по x_plot = lin_col[col] и y_plot = lin_row[row]

Во-вторых, вы можете избежать обоих циклов, используя map_coordinates для более чем одного v_stack для каждой пары (row, col).Для этого вы можете создать все комбинации x_plot и y_plot, используя np.tile и np.ravel, например:

arr_vs = np.vstack(( np.tile( lin_row, cols).ravel(),
                     np.tile( lin_col.ravel(), rows)))

Обратите внимание, что ravel не используется в одном и том же месте каждый раз, чтобы получить все комбинации.Теперь вы можете использовать map_coordinates с этими arr_vs и reshape результатом с числом rows, cols и num, чтобы получить каждый interpolated_line в последней оси 3D-массива:

arr_map = map_coordinates(m, arr_vs, order=1, mode='nearest').reshape(rows,cols,num)

Наконец, вы можете использовать np.max и np.argmax на последней оси arr_map, чтобы получить результаты m_max и m_dist.Таким образом, весь код будет:

import numpy as np
from scipy.ndimage import map_coordinates
m = np.array([
    [10,10,10,10,10,10],
    [9,9,9,10,9,9],
    [9,8,9,10,8,9],
    [9,7,8,0,8,9],
    [8,7,7,8,8,9],
    [5,6,7,7,6,7]])

origin_row = 3
origin_col = 3
rows, cols = m.shape

num = 5
lin_col = np.array([np.linspace(i, origin_col, num) for i in range(cols)])
lin_row = np.array([np.linspace(i, origin_row, num) for i in range(rows)])

arr_vs = np.vstack(( np.tile( lin_row, cols).ravel(),
                     np.tile( lin_col.ravel(), rows)))

arr_map = map_coordinates(m, arr_vs, order=1, mode='nearest').reshape(rows,cols,num)
m_max = np.max( arr_map, axis=-1)
m_dist = np.argmax( arr_map, axis=-1)

print (m_max)
print (m_dist)

, и вы получите, как и ожидалось:

#m_max
array([[10, 10, 10, 10, 10, 10],
       [ 9,  9, 10, 10,  9,  9],
       [ 9,  9,  9, 10,  8,  9],
       [ 9,  8,  8,  0,  8,  9],
       [ 8,  8,  7,  8,  8,  9],
       [ 7,  7,  8,  8,  8,  8]])
#m_dist
array([[0, 0, 0, 0, 0, 0],
       [0, 0, 2, 0, 0, 0],
       [0, 2, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0],
       [0, 2, 0, 0, 0, 0],
       [1, 1, 2, 1, 2, 1]])

РЕДАКТИРОВАТЬ: lin_col и lin_row связаны, так что вы можете сделать быстрее:

if cols >= rows:
    arr = np.arange(cols)[:,None]
    lin_col = arr + (origin_col-arr)/(num-1.)*np.arange(num)
    lin_row = lin_col[:rows] + np.linspace(0, origin_row - origin_col, num)[None,:]
else:
    arr = np.arange(rows)[:,None]
    lin_row = arr + (origin_row-arr)/(num-1.)*np.arange(num)
    lin_col = lin_row[:cols] + np.linspace(0, origin_col - origin_row, num)[None,:]
0 голосов
/ 23 декабря 2018

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

Два примера: монохромный тестовый шаблон 384x512 и «настоящий» 3-канальный 768x1024образ.Оба являются uint8.На моем компьютере это займет полминуты.

Для больших изображений потребуется больше оперативной памяти, чем у меня (8 ГБ).Или нужно разбить его на более мелкие куски.

enter image description here enter image description here enter image description here enter image description here

и код

import numpy as np

def rays(img, ctr):
    M, N, *d = img.shape
    aidx = 2*(slice(None),) + (img.ndim-2)*(None,)
    m, n = ctr
    out = np.empty_like(img)
    offsI = np.empty(img.shape, np.uint16)
    offsJ = np.empty(img.shape, np.uint16)
    img4, out4, I4, J4 = ((x[m:, n:], x[m:, n::-1], x[m::-1, n:], x[m::-1, n::-1]) for x in (img, out, offsI, offsJ))
    for i, o, y, x in zip(img4, out4, I4, J4):
        for _ in range(2):
            M, N, *d = i.shape
            widths = np.arange(1, M+1, dtype=np.uint16).clip(None, N)
            I = np.arange(M, dtype=np.uint16).repeat(widths)
            J = np.ones_like(I)
            J[0] = 0
            J[widths[:-1].cumsum()] -= widths[:-1]
            J = J.cumsum(dtype=np.uint16)
            ii = np.arange(1, 2*M-1, dtype=np.uint16) // 2
            II = ii.clip(None, I[:, None])
            jj = np.arange(2*M-2, dtype=np.uint32) // 2 * 2 + 1
            jj[0] = 0
            JJ = ((1 + jj) * J[:, None] // (2*(I+1))[:, None]).astype(np.uint16).clip(None, J[:, None])
            idx = i[II, JJ].argmax(axis=1)
            II, JJ = (np.take_along_axis(ZZ[aidx] , idx[:, None], 1)[:, 0] for ZZ in (II, JJ))
            y[I, J], x[I, J] = II, JJ
            SH = II, JJ, *np.ogrid[tuple(map(slice, img.shape))][2:]
            o[I, J] = i[SH]
            i, o = i.swapaxes(0, 1), o.swapaxes(0, 1)
            y, x = x.swapaxes(0, 1), y.swapaxes(0, 1)
    return out, offsI, offsJ

from scipy.misc import face

f = face()
fr, *fidx = rays(f, (200, 400))
s = np.uint8((np.arange(384)[:, None] % 41 < 2)&(np.arange(512) % 41 < 2))
s = 255*s + 128*s[::-1, ::-1] + 64*s[::-1] + 32*s[:, ::-1]
sr, *sidx = rays(s, (200, 400))

import Image
Image.fromarray(f).show()
Image.fromarray(fr).show()
Image.fromarray(s).show()
Image.fromarray(sr).show()
...