Ищем самый быстрый способ уменьшить массив 3d на основе вхождений, используя numpy

Question

Учитывая большой массив 3d numpy (не слишком большой, чтобы поместиться в памяти) с типом 'uint8', я хотел бы уменьшить этот массив с заданным коэффициентом масштабирования в каждом измерении. Вы можете предположить, что форма массива делится на коэффициент масштабирования.

Значения массива находятся в [0, 1, ... max], где max всегда меньше 6. Я хотел бы уменьшите его так, чтобы каждый 3d-блок с формой «scale_factor» возвращал число, которое больше всего встречается в этом блоке. При равенстве возвращаем первое (мне все равно).

Я пробовал следующее, которое работает

import numpy as np

array = np.random.randint(0, 4, ((128, 128, 128)), dtype='uint8')
scale_factor = (4, 4, 4)
bincount = 3

# Reshape to free dimension of size scale_factor to apply scaledown method to
m, n, r = np.array(array.shape) // scale_factor
array = array.reshape((m, scale_factor[0], n, scale_factor[1], r, scale_factor[2]))


# Making histogram, first over last axis, then sum over other two
array = np.apply_along_axis(lambda x: np.bincount(x, minlength=bincount),
                            axis=5, arr=array)
array = np.apply_along_axis(lambda x: np.sum(x), axis=3, arr=array)
array = np.apply_along_axis(lambda x: np.sum(x), axis=1, arr=array).astype('uint8')

array = np.argmax(array , axis=3)

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

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

Answer 1

@F.Wessels думает в правильном направлении, но ответа пока нет. Скорость может быть увеличена более чем в сто раз, если вы возьмете дело в свои руки, вместо того, чтобы использовать применение вдоль оси.

Прежде всего, когда вы делите пространство трехмерного массива на блоки, ваши размеры изменяются от От 128х128х128 до 32х4х32х4х32х4. Попробуйте интуитивно понять это: у вас есть блоки размером 32x32x32 размером 4x4x4. Вместо того, чтобы сохранять блоки размером 4х4х4, вы можете просто сжать их размером 64, откуда вы сможете найти наиболее частый предмет. Вот хитрость: также не имеет значения, если ваши блоки расположены не как 32x32x32x64, а как 32768x64. По сути, мы вернулись к двумерным измерениям, где все проще.

Теперь с вашим двумерным массивом размером 32768x64 вы можете выполнять подсчет бинов самостоятельно с использованием списка и numpy ops; это будет в 10 раз быстрее.

import time
import numpy as np

array = np.random.randint(0, 4, ((128, 128, 128)), dtype='uint8')
scale_factor = (4, 4, 4)
bincount = 4

def prev_func(array):
    # Reshape to free dimension of size scale_factor to apply scaledown method to
    m, n, r = np.array(array.shape) // scale_factor
    arr = array.reshape((m, scale_factor[0], n, scale_factor[1], r, scale_factor[2]))
    arr = np.swapaxes(arr, 1, 2).swapaxes(2, 4)
    arr = arr.reshape((m, n, r, np.prod(scale_factor)))
    # Obtain the element that occurred the most
    arr = np.apply_along_axis(lambda x: max(set(x), key=lambda y: list(x).count(y)),
                              axis=3, arr=arr)
    return arr

def new_func(array):
    # Reshape to free dimension of size scale_factor to apply scaledown method to
    m, n, r = np.array(array.shape) // scale_factor
    arr = array.reshape((m, scale_factor[0], n, scale_factor[1], r, scale_factor[2]))
    arr = np.swapaxes(arr, 1, 2).swapaxes(2, 4)
    arr = arr.reshape((m, n, r, np.prod(scale_factor)))
    # Collapse dimensions
    arr = arr.reshape(-1,np.prod(scale_factor))
    # Get blockwise frequencies -> Get most frequent items
    arr = np.array([(arr==b).sum(axis=1) for b in range(bincount)]).argmax(axis=0)
    arr = arr.reshape((m,n,r))
    return arr

N = 10

start1 = time.time()
for i in range(N):
    out1 = prev_func(array)
end1 = time.time()
print('Prev:',(end1-start1)/N)

start2 = time.time()
for i in range(N):
    out2 = new_func(array)
end2 = time.time()
print('New:',(end2-start2)/N)

print('Difference:',(out1-out2).sum())

Out:

Prev: 1.4244404077529906
New: 0.01667332649230957
Difference: 0

Как вы можете видеть, нет никаких различий в результатах, даже если я манипулировал измерениями вокруг. Функция изменения формы Numpy поддерживала порядок значений, когда я перешел в 2D, так как последнее измерение 64 было сохранено. Этот порядок восстанавливается, когда я перехожу на m, n, r. Исходный метод, который вы дали, занял около 5 секунд для запуска на моей машине, так что эмпирически это улучшение скорости в пятьсот раз.

Answer 2

Ну, вот аналогичный метод, но быстрее. Он только заменяет функцию bincount на более простую реализацию, основанную на вашем сценарии использования: lambda x: max(set(x), key=lambda y: list(x).count(y)), где сначала изменяется массив, так что метод можно напрямую использовать в 1 измерении.

На моем ноутбуке с разрешением 128x128x128 это окружает В 4 раза быстрее:

import time
import numpy as np

array = np.random.randint(0, 4, ((128, 128, 128)), dtype='uint8')
scale_factor = (4, 4, 4)
bincount = 4

start_time = time.time()
N = 10
for i in range(N):

    # Reshape to free dimension of size scale_factor to apply scaledown method to
    m, n, r = np.array(array.shape) // scale_factor
    arr = array.reshape((m, scale_factor[0], n, scale_factor[1], r, scale_factor[2]))
    arr = np.swapaxes(arr, 1, 2).swapaxes(2, 4)
    arr = arr.reshape((m, n, r, np.prod(scale_factor)))

    # Obtain the element that occurred the most
    arr = np.apply_along_axis(lambda x: max(set(x), key=lambda y: list(x).count(y)),
                              axis=3, arr=arr)

print((time.time() - start_time) / N)

По-прежнему существует большой разрыв, например, с такими встроенными методами, как np.mean ()