Медиана нескольких массивов в Julia

Question

Это связано с этим вопросом

Я хочу знать, как вычислить медианное значение по указанному c измерению на огромном массиве, например, с размером (20, 1920, 1080, 3 ). Я не уверен, есть ли в этом какая-то практическая цель, но я просто хотел проверить, насколько хорошо работает медиана в Julia.

Для вычисления медианы на (3,1920,1080) требуется ~ 0,5 секунды с. , 3) с numpy. Он работает очень быстро с массивом нулей (менее 2 секунд на (120, 1920, 1080,3)) и работает не так быстро, но отлично на реальных изображениях (20 секунд на (120, 1920, 1080,3)).

Python код:

import cv2
import sys
import numpy as np
import time

ZEROES=True
N_IMGS=20

print("n_imgs:", N_IMGS)
print("use dummy data:", ZEROES)

imgs_paths = sys.argv[1:]
imgs_paths.sort()
imgs_paths_sparse = imgs_paths[::30]

imgs_paths = imgs_paths_sparse[N_IMGS]

if ZEROES:
    imgs_arr = np.zeros((N_IMGS,1080,1920,3), dtype=np.float32)
else:
    imgs = map(cv2.imread, imgs_paths)
    imgs_arr = np.array(list(imgs), dtype=np.float32)

start = time.time()
imgs_median = np.median(imgs_arr, 0)
end = time.time()
print("time:", end - start)
cv2.imwrite('/tmp/median.png', imgs_median)

В julia я могу вычислить только медианное значение (3, 1920, 1080,3). После этого мой процесс earlyoom убивает процесс julia из-за огромного количества используемой памяти.

Я пробовал подход, аналогичный тому, который я пробовал сначала на max:

function median1(imgs_arr)
    a = imgs_arr
    b = reshape(cat(a..., dims=1), tuple(length(a), size(a[1])...))
    imgs_max = Statistics.median(b, dims=1)
    return imgs_max
end

Или даже больше простой случай:

import Statistics
a = zeros(3,1080,1920,3)
@time Statistics.median(a, dims=1)
 10.609627 seconds (102.64 M allocations: 2.511 GiB, 3.37% gc time)
...

Итак, это занимает 10 секунд против 0,5 секунды на numpy. У меня всего 4 ядра процессора и это не просто распараллеливание.

Есть более-менее простой способ как-то оптимизировать?

Или, по крайней мере, взять срезы и вычислить их один за другим без чрезмерного использования памяти?

Answer 1

Трудно понять, является ли тот факт, что изображения загружаются отдельно, ключевой частью проблемы здесь или нет, поскольку настройка для проблемы в Julia отсутствует, а программистам Julia немного сложно следовать Python настроить или знать, сколько нам нужно для этого. Вам либо нужно:

1. Загрузить или переместить данные изображения так, чтобы они фактически были частью одного и того же массива, а затем взять его медианное значение;

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

Ответ Фредрика неявно предполагает, что вы уже загрузили данные изображения, так что все они являются частью одного непрерывного массива. Однако в этом случае вам даже не нужен JuliennedArrays, вы можете просто использовать функцию median из Statistics stdlib:

julia> a = rand(3, 1080, 1920, 3);

julia> using Statistics

julia> median(a, dims=1)
1×1080×1920×3 Array{Float64,4}:
[:, :, 1, 1] =
 0.63432  0.205958  0.216221  0.571541  …  0.238637  0.285947  0.901014

[:, :, 2, 1] =
 0.821851  0.486859  0.622313  …  0.917329  0.417657  0.724073

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

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

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

Из-за локализации памяти может быть более эффективным скопировать один фрагмент данных во временный массив и вычислить его медианное значение. . Это можно сделать довольно легко с пониманием массива:

julia> v_of_a = [rand(1080, 1920, 3) for _ = 1:3]
3-element Array{Array{Float64,3},1}:
 [0.7206652600431633 0.7675119703509619 … 0.7117084561740263 0.8736518021960584; 0.8038479801395197 0.3159392943734012 … 0.976319025405266 0.3278606124069767; … ; 0.7424260315304789 0.4748658164109498 … 0.9942311708400311 0.37048961459068086; 0.7832577306186075 0.13184454935145773 … 0.5895094390350453 0.5470111170897787]

[0.26401298651503025 0.9113932653115289 … 0.5828647778524962 0.752444909740893; 0.5673144007678044 0.8154276504227804 … 0.2667436824684424 0.4895443896447764; … ; 0.2641913584303701 0.16639100493266934 … 0.1860616855126005 0.04922131616483538; 0.4968214514330498 0.994935452055218 … 0.28097239922248685 0.4980189891952156]

julia> [median(a[i,j,k] for a in v_of_a) for i=1:1080, j=1:1920, k=1:3]
1080×1920×3 Array{Float64,3}:
[:, :, 1] =
 0.446895  0.643648  0.694714   …  0.221553   0.711708   0.225268
 0.659251  0.457686  0.672072      0.731218   0.449915   0.129987
 0.573196  0.328747  0.668702      0.355231   0.656686   0.303168
 0.243656  0.702642  0.45708       0.23415    0.400252   0.482792

Answer 2

Попробуйте JuliennedArrays.jl

julia> a = zeros(3,1080,1920,3);

julia> using JuliennedArrays

julia> @time map(median, Slices(a,1));
  0.822429 seconds (6.22 M allocations: 711.915 MiB, 20.15% gc time)

Как Стефан прокомментировал ниже, встроенный median делает то же самое, но намного медленнее

julia> @time median(a, dims=1);
  7.450394 seconds (99.80 M allocations: 2.368 GiB, 4.47% gc time)

не менее julia> VERSION v"1.5.0-DEV.876"