Хотя это не объясняет ваши проблемы с памятью, ваша реализация, мягко говоря, неоптимальна. Вы не только не используете numpy в полной мере, но и поток вашего алгоритма также не очень хорош для избежания повторных вычислений. Я думаю, что у вашей системы просто не хватает ресурсов не потому, что что-то не так в python или numpy, а потому, что вы создаете слишком много ненужных списков списков списков...
Изучив статью Википедии об алгоритме Лукаса-Канаде, я переписал вашу основную функцию следующим образом:
def lucas_kanade_np(im1, im2, win=2):
assert im1.shape == im2.shape
I_x = np.zeros(im1.shape)
I_y = np.zeros(im1.shape)
I_t = np.zeros(im1.shape)
I_x[1:-1, 1:-1] = (im1[1:-1, 2:] - im1[1:-1, :-2]) / 2
I_y[1:-1, 1:-1] = (im1[2:, 1:-1] - im1[:-2, 1:-1]) / 2
I_t[1:-1, 1:-1] = im1[1:-1, 1:-1] - im2[1:-1, 1:-1]
params = np.zeros(im1.shape + (5,)) #Ix2, Iy2, Ixy, Ixt, Iyt
params[..., 0] = I_x * I_x # I_x2
params[..., 1] = I_y * I_y # I_y2
params[..., 2] = I_x * I_y # I_xy
params[..., 3] = I_x * I_t # I_xt
params[..., 4] = I_y * I_t # I_yt
del I_x, I_y, I_t
cum_params = np.cumsum(np.cumsum(params, axis=0), axis=1)
del params
win_params = (cum_params[2 * win + 1:, 2 * win + 1:] -
cum_params[2 * win + 1:, :-1 - 2 * win] -
cum_params[:-1 - 2 * win, 2 * win + 1:] +
cum_params[:-1 - 2 * win, :-1 - 2 * win])
del cum_params
op_flow = np.zeros(im1.shape + (2,))
det = win_params[...,0] * win_params[..., 1] - win_params[..., 2] **2
op_flow_x = np.where(det != 0,
(win_params[..., 1] * win_params[..., 3] -
win_params[..., 2] * win_params[..., 4]) / det,
0)
op_flow_y = np.where(det != 0,
(win_params[..., 0] * win_params[..., 4] -
win_params[..., 2] * win_params[..., 3]) / det,
0)
op_flow[win + 1: -1 - win, win + 1: -1 - win, 0] = op_flow_x[:-1, :-1]
op_flow[win + 1: -1 - win, win + 1: -1 - win, 1] = op_flow_y[:-1, :-1]
return op_flow
Он использует два вложенных вызова np.cumsum и принцип исключения-включения для вычисления оконных параметров. Поскольку система уравнений, которую нужно решить в каждой точке, имеет размер всего 2x2, для векторизации решения используется правило Крамера.
Для сравнения, я переименовал вашу функцию lucas_kanade в lucas_kanade_op с одним изменением последнего оператора, чтобы она возвращала пустой массив:
def lucas_kanade_op(im1, im2, win=2) :
...
return np.array(opfl)
Я рассчитал оба подхода (и проверил, что они оба выводят одинаково) и никаких сюрпризов, использование numpy дает огромный импульс:
rows, cols = 100, 100
im1 = np.random.rand(rows, cols)
im2 = np.random.rand(rows, cols)
ans1 = lucas_kanade_op(im1, im2)
ans2 = lucas_kanade_np(im1, im2)
np.testing.assert_almost_equal(ans1,ans2)
import timeit
print 'op\'s time:', timeit.timeit('lucas_kanade_op(im1, im2)',
'from __main__ import lucas_kanade_op, im1, im2',
number=1)
print 'np\'s time:', timeit.timeit('lucas_kanade_np(im1, im2)',
'from __main__ import lucas_kanade_np, im1, im2',
number=1)
Это распечатывает:
op's time: 5.7419579567
np's time: 0.00256002154425
Так что это увеличение скорости в 2000 раз для небольшого изображения размером 100x100. Я не осмелился протестировать ваш подход для полноразмерного изображения 480p, но приведенная выше функция может обрабатывать около 5 вычислений в случайном массиве 854x480 в секунду без каких-либо проблем.
Я бы рекомендовал вам переписать свой код так, как это было предложено выше, максимально используя преимущества numpy. Публикация полного кода в Code Review будет хорошей отправной точкой. Но на самом деле нет никакого смысла искать случайные ссылки на объекты, когда ваш код изначально настолько неэффективен!
person
Jaime
schedule
14.01.2013
