Наиболее распространенные и вторые по распространенности значения в трехмерном массиве по последней оси

Question

Я хотел бы знать 2 верхних наиболее распространенных значения и их частоты вдоль последней оси моего массива. У меня уже есть эта работа, но я бы хотел, чтобы она работала быстрее.

Пример case

Реальные данные - это (720, 1280, 64) -образный массив numpy типа uint16, но для простоты, давайте представим, что это массив (2, 2, 4).

Таким образом, данные будут выглядеть так:

               0          1  
          ------------------------
        0 | [1,1,1,2] [1,1,2,2]
        1 | [2,2,2,1] [1,1,1,3]

Для каждой позиции x, y, Iхотел бы знать, что является наиболее распространенным и вторым наиболее распространенным значением, и сколько раз появляются наиболее распространенное и второе наиболее распространенное значение (если два значения одинаково распространены, выбор любого из них - это нормально).

Итакдля приведенного выше примера наиболее распространенными значениями будут:

               0          1  
          ------------------------
        0 |    1          1
        1 |    2          1

И сколько раз они появляются:

               0          1  
          ------------------------
        0 |    3          2
        1 |    3          3

Вторые наиболее распространенные значения (в случае отсутствия второго наиболееобычное значение, с нуля в порядке) в примере:

               0          1  
          ------------------------
        0 |    2          2
        1 |    1          3

И как часто появляется второе наиболее распространенное значение. Если второго наиболее распространенного значения не существует, то все будет в порядке.

               0          1  
          ------------------------
        0 |    1          2
        1 |    1          1

Текущее решение

Если массив называется "a", я сначала делаю это, чтобы получить максимальнообщее значение и его число появлений:

import numpy as np
from scipy.stats import mode

a = np.array([
    [[1,1,1,2], [1,1,2,2]],
    [[2,2,2,1], [1,1,1,3]]
])

most_common_value, most_common_count = mode(a, axis=2)
print(most_common_value.squeeze())
print(most_common_count.squeeze())

Вывод:

[[1 1]
 [2 1]]

[[3 2]
 [3 3]]

Затем, чтобы получить второе наиболее распространенное значение, я просто удаляю наиболее распространенное значениеи затем снова запустите выше. Чтобы удалить, я сначала создаю маску, значения которой я хочу удалить.

mask = a == most_common_value
print(mask)

Вывод:

array([[[ True,  True,  True, False],
        [ True,  True, False, False]],

       [[ True,  True,  True, False],
        [ True,  True,  True, False]]])

Теперь то, что я действительно хотел быЗначение true - это удалить все, что является True, но поскольку измерение по оси должно оставаться неизменным, вместо того, чтобы что-либо удалять, я заменяю наиболее распространенное значение вместо NaN.

Поскольку это uint16, которые не знают о NaN, я должен сначала конвертировать в float.

a = a.astype('float')
np.putmask(a, mask, np.nan)
print(a)

Вывод:

[[[nan nan nan  2.]
  [nan nan  2.  2.]]

 [[nan nan nan  1.]
  [nan nan nan  3.]]]

Теперь mode можно снова запустить на этом, за исключением того, что необходимо указать игнорировать NaN, и результат необходимо снова преобразовать в uint16.

m = mode(a, axis=2, nan_policy='omit')
m = [x.astype('uint16') for x in m]
second_most_common_value, second_most_common_count = m
print(second_most_common_value.squeeze())
print(second_most_common_count.squeeze())

Вывод:

[[2 2]
 [1 3]]

[[1 2]
 [1 1]]

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

Производительность

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

Автономный пример:

import time
import numpy as np
from scipy.stats import mode

a = np.random.randint(30000, size=(720, 1280, 64))

start_time = time.time()

most_common_value, most_common_count = mode(a, axis=2)

mask = a == most_common_value
a = a.astype('float')
np.putmask(a, mask, np.nan)

m = mode(a, axis=2, nan_policy='omit')
m = [x.astype('uint16') for x in m]
second_most_common_value, second_most_common_count = m

end_time = time.time()
print(f'Took {end_time-start_time:.2f} seconds to run')

Вывод:

Took 123.29 seconds to run

В идеале это должно выполняться менее чем за 30 секунд, но любое улучшение приветствуется.

Почему вы хотите это сделать?

Как вы могли заметить, первые два измерения (720, 1280, 64) - это разрешение изображения 1280x720. 64 значения для каждого пикселя являются цветами субпикселей под этим пикселем и относятся к известной палитре цветов по индексу.

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

Цель этого проекта - улучшить качество рендеринга на моего сайта, где пользователи могут создавать мгновенные пользовательские анимации;решение этой проблемы избавило бы от зазубренных краев в рендерингах.

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

Answer 1

Я закончил тем, что написал простой режим, который перебирает все значения конечной оси, пытаясь каждый из них увидеть, может ли это быть новый режим. Это наивное решение все равно оказалось вдвое быстрее, чем scipy.stats.mode для моих данных.

def silly_mode(a):
    """Returns mode and counts for final axis of a numpy array.

    Same as scipy.stats.mode(a, axis=-1).squeeze()
    """

    # Best mode candidate discovered so far
    most_common_value = np.zeros((a.shape[0], a.shape[1]),dtype=a.dtype)
    most_common_count = np.zeros((a.shape[0], a.shape[1]),dtype=a.dtype)

    # Silly solution based on just iterating all of final dimension,
    # but still beats scipy if final dimension is less than 100 in length.
    for i in range(0, a.shape[2]):

        # Find candidate value for each cell
        val = np.expand_dims(a[:,:,i], axis = -1)

        # Count how many times it appears
        counts = np.count_nonzero(a == val, axis = -1).astype(a.dtype)

        # Find out which ones should become the new mode values
        update_mask = counts > most_common_count[:,:]

        # Update mode value and its count where necessary
        np.putmask(most_common_value, update_mask, val)
        np.putmask(most_common_count, update_mask, counts)

    return most_common_value, most_common_count

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

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

Обновление:

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

def top_2_most_common_values(a, ignore_zeros = False):
    """Returns mode and counts for each mode of final axis of a numpy array,
    and also returns the second most common value and its counts.

    Similar to calling scipy.stats.mode(a, axis=-1).squeeze() to find the mode,
    except this also returns the second most common values.

    If ignore_zeros is true, then zero will not be considered as a mode candidate.
    In this case a zero instead signifies that there was no most common or second
    most common value, and so the count will also be zero.
    """

    # Silly solution based on just iterating all of final dimension
    most_common_value = np.zeros((a.shape[0], a.shape[1]),dtype=a.dtype)
    most_common_count = np.zeros((a.shape[0], a.shape[1]),dtype=a.dtype)
    second_most_common_value = np.zeros((a.shape[0], a.shape[1]),dtype=a.dtype)
    second_most_common_count = np.zeros((a.shape[0], a.shape[1]),dtype=a.dtype)

    for i in range(0, a.shape[2]):

        # Find candidate value for each cell
        val = np.expand_dims(a[:,:,i], axis = -1)

        # Count how many times it appears
        counts = np.count_nonzero(a == val, axis = -1).astype(a.dtype)

        # Find out which ones should become the new mode values
        update_mask = counts > most_common_count[:,:]
        if ignore_zeros:
            update_mask &= val.squeeze() != 0

        # If most common value changes, then what used to be most common is now second most common
        # Without the next two lines a like [1,2,2] would fail, as the second most common value
        # is never encountered again after being initially set to be the most common one.
        np.putmask(second_most_common_value, update_mask, most_common_value)
        np.putmask(second_most_common_count, update_mask, most_common_count)        

        # Update mode value and its count where necessary
        np.putmask(most_common_value, update_mask, val)
        np.putmask(most_common_count, update_mask, counts)

        # In a case like [2, 0, 0, 1] the last 1 isn't the new most common value, but it 
        # still should be updated as the second most common value. For these cases separately check 
        # if any encountered value might be the second most common one.
        update_mask = (counts >= second_most_common_count[:,:]) & (val.squeeze() != most_common_value[:,:])
        if ignore_zeros:
            update_mask &= val.squeeze() != 0

        # # Save previous best mode and its count before updating
        np.putmask(second_most_common_value, update_mask, val)
        np.putmask(second_most_common_count, update_mask, counts)

    return most_common_value, most_common_count, second_most_common_value, second_most_common_count