Python: Как заполнить массив построчно? - PullRequest
Новая
       2

Python: Как заполнить массив построчно?

7 голосов
/ 08 июля 2011

У меня есть проблема с numpy, которую я не могу решить. У меня есть 3D-массивы (x, y, z), заполненные 0 и 1. Например, один срез по оси Z: 

array([[1, 0, 1, 0, 1, 1, 0, 0],
       [0, 0, 1, 1, 0, 1, 1, 0],
       [1, 0, 1, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 0, 1, 0, 0, 1],
       [1, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 1, 1, 0, 1]])

И я хочу этот результат: 

array([[1, 1, 1, 1, 1, 1, 0, 0],
       [0, 0, 1, 1, 1, 1, 1, 0],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 1, 1, 1, 1, 1]])

То есть, что я хочу сделать для каждого среза z, это сканировать построчно справа налево и слева направо (ось x), и в первый раз, когда у меня есть 1, я хочу заполнить оставшуюся часть строка с единицами.

Есть ли эффективный способ вычислить это?

Большое спасибо.

Нико!

Ответы [ 4 ]

4 голосов
/ 10 июля 2011

На самом деле, это базовая морфология двоичного изображения операция.

Вы можете сделать это за один шаг для всего трехмерного массива, используя scipy.ndimage.morphology.binary_fill_holes

Вам просто нужен немного другой элемент структуры. В двух словах, вы хотите структурирующий элемент, который выглядит следующим образом для 2D-случая: 

[[0, 0, 0],
 [1, 1, 1],
 [0, 0, 0]]

Вот краткий пример: 

import numpy as np
import scipy.ndimage as ndimage

a = np.array( [[1, 0, 1, 0, 1, 1, 0, 0],
               [0, 0, 1, 1, 0, 1, 1, 0],
               [1, 0, 1, 1, 0, 0, 0, 1],
               [0, 1, 0, 0, 1, 0, 1, 0],
               [1, 1, 1, 0, 1, 0, 0, 1],
               [1, 0, 0, 0, 0, 1, 0, 1],
               [0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 1, 0, 0, 0],
               [0, 0, 1, 0, 1, 1, 0, 1]])
structure = np.zeros((3,3), dtype=np.int)
structure[1,:] = 1

filled = ndimage.morphology.binary_fill_holes(a, structure)
print filled.astype(np.int)

Это дает: 

[[1 1 1 1 1 1 0 0]
 [0 0 1 1 1 1 1 0]
 [1 1 1 1 1 1 1 1]
 [0 1 1 1 1 1 1 0]
 [1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [0 0 0 0 0 0 0 0]
 [0 0 0 0 1 0 0 0]
 [0 0 1 1 1 1 1 1]]

Реальным преимуществом этого (кроме скорости ... Это будет намного быстрее и более эффективно использовать память, чем при использовании списков!) Является то, что он будет работать так же хорошо для массивов 3D, 4D, 5D и т. Д.

Нам просто нужно настроить структурирующий элемент в соответствии с количеством измерений. 

import numpy as np
import scipy.ndimage as ndimage

# Generate some random 3D data to match what we want...
x = (np.random.random((10,10,20)) + 0.5).astype(np.int)

# Make the structure (I'm assuming that "z" is the _last_ dimension!)
structure = np.zeros((3,3,3))
structure[1,:,1] = 1

filled = ndimage.morphology.binary_fill_holes(x, structure)

print x[:,:,5]
print filled[:,:,5].astype(np.int)

Вот фрагмент случайного ввода 3D массив: 

[[1 0 1 0 1 1 0 1 0 0]
 [1 0 1 1 0 1 0 1 0 0]
 [1 0 0 1 0 1 1 1 1 0]
 [0 0 0 1 1 0 1 0 0 0]
 [1 0 1 0 1 0 0 1 1 0]
 [1 0 1 1 0 1 0 0 0 1]
 [0 1 0 1 0 0 1 0 1 0]
 [0 1 1 0 1 0 0 0 0 1]
 [0 0 0 1 1 1 1 1 0 1]
 [1 0 1 1 1 1 0 0 0 1]]

А вот заполненная версия: 

[[1 1 1 1 1 1 1 1 0 0]
 [1 1 1 1 1 1 1 1 0 0]
 [1 1 1 1 1 1 1 1 1 0]
 [0 0 0 1 1 1 1 0 0 0]
 [1 1 1 1 1 1 1 1 1 0]
 [1 1 1 1 1 1 1 1 1 1]
 [0 1 1 1 1 1 1 1 1 0]
 [0 1 1 1 1 1 1 1 1 1]
 [0 0 0 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]]

Ключевым отличием здесь является то, что мы сделали это для каждого среза всего трехмерного массива за один шаг.

4 голосов
/ 08 июля 2011

Доступ к элементам массива NumPy один за другим не очень эффективен.Вы можете сделать лучше с простыми списками Python.У них также есть метод index, который может искать первую запись значения в списке. 

from numpy import *

a = array([[1, 0, 1, 0, 1, 1, 0, 0],
       [0, 0, 1, 1, 0, 1, 1, 0],
       [1, 0, 1, 1, 0, 0, 0, 1],
       [0, 1, 0, 0, 1, 0, 1, 0],
       [1, 1, 1, 0, 1, 0, 0, 1],
       [1, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 1, 1, 0, 1]])

def idx_front(ln):
    try:
        return list(ln).index(1)
    except ValueError:
        return len(ln) # an index beyond line end

def idx_back(ln):
    try:
        return len(ln) - list(reversed(ln)).index(1) - 1
    except ValueError:
        return len(ln) # an index beyond line end

ranges = [ (idx_front(ln), idx_back(ln)) for ln in a ]
for ln, (lo,hi) in zip(a, ranges):
    ln[lo:hi] = 1  # attention: destructive update in-place

print "ranges =", ranges
print a

Вывод: 

ranges = [(0, 5), (2, 6), (0, 7), (1, 6), (0, 7), (0, 7), (4, 4), (8, 8), (2, 7)]
[[1 1 1 1 1 1 0 0]
 [0 0 1 1 1 1 1 0]
 [1 1 1 1 1 1 1 1]
 [0 1 1 1 1 1 1 0]
 [1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [0 0 0 0 1 0 0 0]
 [0 0 0 0 0 0 0 0]
 [0 0 1 1 1 1 1 1]]
2 голосов
/ 08 июля 2011

После некоторого размышления, после вашего описания и углового случая со всеми нулевыми строками, это будет все еще довольно просто с numpy как: 

In []: A
Out[]: 
array([[1, 0, 1, 0, 1, 1, 0, 0],
       [0, 0, 1, 1, 0, 1, 1, 0],
       [1, 0, 1, 1, 0, 0, 0, 1],
       [0, 1, 0, 0, 1, 0, 1, 0],
       [1, 1, 1, 0, 1, 0, 0, 1],
       [1, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 1, 1, 0, 1]])

In []: v= 0< A.sum(1) # work only with rows at least one 1
In []: A_v= A[v, :]
In []: (r, s), a= A_v.nonzero(), arange(v.sum())
In []: se= c_[searchsorted(r, a), searchsorted(r, a, side= 'right')- 1]
In []: for k in a: A_v[k, s[se[k, 0]]: s[se[k, 1]]]= 1
   ..: 
In []: A[v, :]= A_v

In []: A
Out[]: 
array([[1, 1, 1, 1, 1, 1, 0, 0],
       [0, 0, 1, 1, 1, 1, 1, 0],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [0, 1, 1, 1, 1, 1, 1, 0],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 1, 1, 1, 1, 1]])

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

for k in xrange(A.shape[0]):
    m= A[k].nonzero()[0]
    try: A[k, m[0]: m[-1]]= 1
    except IndexError: continue

довольно простые.И они действительно очень хорошо выступят.

0 голосов
/ 08 июля 2011

Я не могу придумать более эффективного способа, чем вы описываете:

Для каждой строки

  1. Сканирование строки слева, пока не найдете 1.

  2. Если нет 1, найдите и продолжите со следующей строки.

  3. В противном случае отсканируйте справа, чтобы найти последний 1 в строке.

  4. Заполните все в текущей строке между позициями от 1. и 3. с 1 с.

...