質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • Python 3.x

    6367questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

numpyの連続した数値列のカウント

解決済

回答 8

投稿 編集

  • 評価
  • クリップ 3
  • VIEW 924

p_pp

score 6

python初心者です
二値化した画像(.jpg)を配列に入れました
配列が

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

のようになっているとき,連続した1の数をカウントするソースコードを教えていただきたいです
1の数を数えるソースコードは調べれば出てくるのですが、連続した数字を数えるソースコードは出てきません

よろしくお願いいたします

実際には画像ファイルが多く,ピクセル数も多いため時間がかかってしまいます
1,0の境界の位置を探してそのピクセル数を得るのに時間短縮できる方法があれば,教えていただけると有難いです
最終的には写真から輪郭形状のグラフを作りたいと思っています

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • umyu

    2018/04/12 22:19

    最終的に行いたいことはなにですか?輪郭抽出とかでしょうか?

    キャンセル

  • p_pp

    2018/04/12 22:28

    そうです!写真から最終的にはグラフの作成を考えています

    キャンセル

  • umyu

    2018/04/12 22:33

    >itakovichさんへ 質問文にその旨を追加してくださいな。

    キャンセル

  • p_pp

    2018/04/12 23:33

    分かりにくくて、すみません… 追加しておきます

    キャンセル

回答 8

+5

https://www.geeksforgeeks.org/maximum-consecutive-ones-or-zeros-in-a-binary-array/

普通に考えて全部のピクセルを見ないといけないのでO(N)になります。(worstケース)

最も簡単な方法は並列化です。
今回の場合、単純並列なので、立てることのできるスレッドの数分の1に計算時間を減らすことができます。


あとはアルゴリズムの話になりますが、例えばk番目まで見て、今のマスは0でこれまでの最長の1たちは100個でした。

そうすれば、とりあえず次は、k+100を見てみることにします。
こいつが1であればk+50を見てみることにします。
そして…

なんとなくお察しいただけるかと思いますが、このように探索することで枝切りの可能性が増えます。
例えばk+50の時点で0に出逢えば、k+1~k+49k+51~k+99はもう探索する必要はありません。

このようにすることで常に1536*2048*1000個のピクセルを見なければいけなかったところを、より少ないピクセルを探索すれば良いことになります。

後はデータの性質に依存します。
01010101010101010101010101010のように並んでいるのであれば判定が必要な分遅くなります。
11111111110000011100000000011のようであれば、大幅に探索を減らすことができます。


ブロック分けしてdivide-and-conquerでもよいですが。

↓    ↓↓  ↓
0000001 0111011 ...
0000010 1111011 ...
1000010 0000000 ...
1100001 1000001 ...
1000010 0111110 ...
...

比較。(更新:groupby, numpy.where, backward, forward)

from itertools import groupby
import numpy as np
import random

from contextlib import contextmanager
import time
@contextmanager
def timer(name):
    t0 = time.time()
    yield
    print(f'[{name}] done in {time.time() - t0:.5f} s')

slen = 1300
tslen = 1500
N = 10000

ss = []
for _i in range(N):
    random.seed(_i)
    s_ = np.array([1]*(tslen-slen) + [random.randint(0, 1) for _ in range(slen)])
    ss.append(s_)

with timer('groupby'):
    mm0 = []
    for _i in range(N):
        s = ss[_i]
        ans = [len(list(g)) for k, g in groupby(s)]
        m = max(ans[::2])
        mm0.append(m)

with timer('numpy.where'):
    mm1 = []
    for _i in range(N):
        a = ss[_i]
        offset = 1
        diff_a = a[offset:] - a[:-offset]

        pos1to0 = np.where(diff_a ==-1)[0] + offset
        pos0to1 = np.where(diff_a ==+1)[0] + offset

        pos0to1 = np.append([0], pos0to1)
        m = (pos1to0 - pos0to1[:len(pos1to0)]).max()
        mm1.append(m)

with timer('backward-search'):
    def forward_search(s):
        j = 0
        while j < len(s) and s[j] == 1:
            j += 1
        return j

    def backward_search(s, m):
        if m >= len(s):
            return False, len(s), 0
        t = s[m::-1]
        c = forward_search(t)
        return True, m, c

    mm2 = []
    for _i in range(N):
        s = ss[_i]
        m = 0
        i = forward_search(s)
        m = i
        while i < len(s):
            fforward, j, c = backward_search(s[i:], m)
            i += j
            if fforward:
                j = forward_search(s[i:])
                c += j
                i += j
                if c > m:
                    m = c
        mm2.append(m)

with timer('forward-search'):
    mm3 = []
    for _i in range(N):
        s = ss[_i]
        m = 0
        c = 0
        for v in s:
            if v == 1:
                c += 1
            else:
                if c > m:
                    m = c
                c = 0
        if c > m:
            m = c
        mm3.append(m)

assert np.all(mm0 == mm1)
assert np.all(mm0 == mm2)
assert np.all(mm0 == mm3)

雑談

高速化を行う際には、

  1. アルゴリズムの改良
  2. コーディングの改良

に分けて考えるとスッキリします。

今回の場合、最低でもO(N)で各ピクセルを見ないと答えが出ないような問題です。
すると、探索の打ち切りの可能性を検討した後、コーディングの改良を検討します。

(目的とあっていない可能性がありますが、
最長の1の塊を探索するのであれば、最長になりえない領域をできるだけスキップする作戦を考えます。)

次に書き方を工夫します。
(ブロック化してSIMD命令を利用するのが、C++などのコンパイル言語を使う際に検討する必要があります。)
Pythonの場合、numpy、opencvのライブラリを出来る限り利用できるようにするのが近道です。
すると、numpyのメソッド、opencvのメソッド、pythonのbuilt-inメソッドを使用することを検討すべきです。

一個ずつピクセルを見ていくより、ベクトルとみなしてsumが速いことは予想できます。
ならば、sumだけで済むように前処理を検討するのが良さそうです。

opencvのオープニングを使うことで先にノイズを消してから、sumを行うのが一番速そうです。

他にもバイナリとして扱ってビット演算を用いることで高速化することも考えられます。
Pythonでそれをやるのは少しちぐはぐ感が残ってしまいます。
C++などで書き換えるだけで、もとのアルゴリズムで高速に処理できることが見込まれるためです。

(重複するようなケースが出現する場合、キャッシュをうまく使うことも重要です。
https://pypi.python.org/pypi/fastcache/0.4.3
メモリと演算のバランスをチューニングするがよいコード書くために大切です。)

高速化することも大事ですが、楽して高速化することも大事です。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/12 23:43

    分かりやすい説明ありがとうございます!
    さっそく実装してみます

    キャンセル

  • 2018/04/13 04:21

    やってみました!
    意外と難しくて、なかなかうまくいきません

    データの性質では
    111111111111111111111110000000000000000000
    111111111111111111111111100000100000000000
    111111111111111000000000001000000000000000
    のように一列目はすべて1から始まっています
    ノイズをカウントしたくないので連続しているという1の数を求めたいという標記にしました
    よろしければ探索を減らすソースコードを乗せていただけないでしょうか

    キャンセル

  • 2018/04/15 14:27

    今気づいたのですが、
    連続したブロックのうち最長のものがほしいのか、
    1個以上連続で出現している1の総数がほしいのか、
    どちらでしょう?

    キャンセル

  • 2018/04/15 14:43

    前者ならデータの性質の応じて最後に追記したコードで処理できます。
    連続する1が少ない場合、素直に順番に探索するのが最速です。
    連続する1が多い場合、枝切りをすることで速めることができます。

    ノイズをカウントせずに、1個以上連続で出現している1の総数がほしいのであれば、
    http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/html/py_tutorials/py_imgproc/py_morphological_ops/py_morphological_ops.html
    オープニングを行うことでノイズを消せます。
    後に、和を取ることによって1の数を得ることができます。

    キャンセル

  • 2018/04/16 16:11

    ありがとうございます!!
    こっちもやってみます!!

    キャンセル

checkベストアンサー

+3

0と1の境界線が欲しいなら、変化点を探して距離を測ればいいんじゃないかなぁ。変化点なんで、まず微分します。

a = np.array([1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0])
offset = 1
diff_a = a[offset:] - a[:-offset]

1->0は-1の変化、0->1は+1の変化なので、それぞれの場所をnp.argwhereを使って抽出します。

pos1to0 = np.where(diff_a ==-1)[0] + offset # -> [8, 10]
pos0to1 = np.where(diff_a ==+1)[0] + offset # -> [9]


右端が必ず0で終わると仮定すれば、pos0to1を微調整してインデックスの差分を取れば1が連続する長さを測れます。

pos0to1 = np.append([0], pos0to1)
len11 = pos1to0 - pos0to1 

pythonのfor-loopが遅いので行列のインデックスを駆使した方法です。理解してコーディングしないと収拾がつかなくなるので、適度な用法用量を守ってご参考にしてください。


追記

mkgreyさんのコードそのまま回したケース
[groupby] done in 0.39933 s
[forward-search] done in 0.12787 s
[backward-search] done in 0.05486 s

最大の長さを返すよう若干修正したバージョン

In [51]: slen = 1000         
    ...: tslen = 1200           
    ...: N = 1000      
    ...:                            
    ...: random.seed(0)                                  
    ...: s_org = [1]*(tslen-slen) + [random.randint(0, 1) for _ in range(1000)]
    ...:                                      
In [52]: with timer("numpy"):
    ...:     a = np.array(s_org)
    ...:     offset = 1
    ...:     diff_a = a[1:] - a[:-1]
    ...:     pos1to0 = np.where(diff_a ==-1)[0] + offset 
    ...:     pos0to1 = np.where(diff_a ==+1)[0] + offset
    ...:     pos0to1 = np.append([0], pos0to1)
    ...:     len11 = (pos1to0 - pos0to1).max()
    ...:         
[numpy] done in 0.00026 s
In [53]: assert len11 == 202

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/15 18:21

    文句をつけるようで申し訳ないのですが、手元の環境でやってみたところfor文を回したほうが速かったです。
    私の実装に自信がないので、ご確認していただいてよろしいでしょうか。

    キャンセル

  • 2018/04/15 18:58

    なるへそ。コメントありがとうございます。しばしお待ちを。

    キャンセル

  • 2018/04/15 21:18

    mkgreiさん、比較してみました。同じものを比べてますかね??np.arrayを前もって変換しておけば実際の計算時間はこれの半分程度で済みました。

    キャンセル

  • 2018/04/15 21:32

    ご確認していただいてありがとうございます。

    a = np.array([1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0])
    で比較していました。

    numpyの方が長さが増えても計算時間がほとんど変わらず、速いですね。

    キャンセル

  • 2018/04/15 21:57

    numpyのテクニックですね(ちなみにMATLABも同様)。アルゴリズムを工夫しても実装であしを引っ張られてしまうのは辛いところ。

    キャンセル

  • 2018/04/15 22:15

    whereを使えば、最長だけでなくすべての区間も取り出せるのがいいですね。

    lookupなら素直に組んでもワンチャンあるかとも思いましたが、ダメですね。

    キャンセル

  • 2018/04/16 15:09

    返信遅れてすいません
    分かりやすい解説ありがとうございます!!

    キャンセル

  • 2018/04/19 18:23

    np.whereで-1を探しても出てこないのですが、なぜでしょうか

    キャンセル

  • 2018/04/19 18:35

    値が変化してない・・・ということは無いですか?

    キャンセル

  • 2018/04/20 11:58

    確認してみましたが値は変化していました…

    キャンセル

  • 2018/04/20 16:01

    from PIL import Image
    import numpy as np
    import matplotlib.pyplot as plt

    np.set_printoptions(threshold=np.inf)


    #閾値
    t=100

    for i in range(0,1):
    filename='C://toisi//f_%05d.jpg'%(i)
    im = np.array(Image.open(filename).convert('L'))

    #二値化
    im[im<t]=0
    im[im>=t]=1

    #print(im.shape, im.dtype)
    #print(im[1,1250])


    #0の数をカウント
    for i in range(1535):
    a = im[i]
    offset = 1
    diff_a = a[offset:] - a[:-offset]
    pos0to1 = np.where(diff_a ==+1)[0] + offset
    pos1to0 = np.where(diff_a ==-1)[0] + offset
    #print(pos0to1)
    #print(pos1to0)
    print(diff_a)

    キャンセル

  • 2018/04/20 16:06

    diff_aをプリントしてみてみると
    [0,0,0,0,0,0,0,0,0,0,0,0,255,1,1,0,0,0,0,0,0,0]
    のような感じになってしまい、出るはずのない255という値がでてきてしまいました

    キャンセル

  • 2018/04/20 16:22

    dtypeがnp.uint8なのでしょう。アンダーフローが発生しています。
    この場合気にせず diff_a == 255 の箇所を利用すれば良いかと思います。

    キャンセル

  • 2018/04/20 16:31

    フォローありがとうございます。画像を読み込んだ結果がuint8になっているためで、その型uint8同士の演算もuint8になって、結果アンダーフローして255に飛んだわけですか。im=im.astype(np.int)でint型にするか、LouiS0616さんのコメントにあるとおり255を利用するかですね。迂闊でした。

    キャンセル

  • 2018/04/20 18:03

    ありがとうございます!!
    できました!

    少し聞きたいのですがpos0to1のときは[9]でpos1to0の中身が[]のように何もないときpos1to0-pos0to1でエラーが表示されてしまうのですがif文で無理やり入れてしまうなどの対処法でよかったでしょうか

    度々すいません。よろしくお願いいたします

    キャンセル

  • 2018/04/20 18:40

    m = (pos1to0 - pos0to1[:len(pos1to0)]).max()
    どっちが短いか見極めて、スライスしてください。

    キャンセル

  • 2018/04/25 20:46

    ありがとうございます!!

    キャンセル

+2

初めて1が来たところから0が来るまでfor文やwhile文でカウントし、カウントした数を別のリストに格納する。if文で評価し、0だったらbreak文で切る

これでどうでしょうか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/12 22:17

    早速の回答ありがとうございます!
    一度それでやったのですが時間がかかってしまいました
    1536×2048の画像で,1000個のファイル処理をする予定です

    キャンセル

  • 2018/04/12 22:24

    なるほど... もっと効率的な方法を考えておきます。

    キャンセル

  • 2018/04/12 22:29

    すみません
    ありがとうございます!!

    キャンセル

  • 2018/04/12 22:46 編集

    今思いついたアルゴリズムを書きたいと思います。
    同じ数字が続くということはその二つの整数の差は"0"です。0~1または1~0が変わるということは
    差の絶対値は1です。この差の絶対値が1というところが変わる境目なのでこれを数えるのはどうでしょうか? 差が1のところと-1のところを別々にカウントするという意味です。
    (データが多いのでこれも時間がかかるかもしれません)

    キャンセル

  • 2018/04/12 23:37

    ありがとうございます!!
    やってみます!

    キャンセル

  • 2018/04/13 04:16

    やってみましたがあまり変わらなかったです…
    ありがとうございます!

    キャンセル

  • 2018/04/13 09:52

    すみません、もう少し考えたらカウントではなく差が-1や1になるところの"リストの番号"をとりだす
    だけでいいと思いました。

    キャンセル

  • 2018/04/13 10:04

    あと、具体的な方法はまだですが別方法で"0と1"のみなので「2進数を使う」も検討中です。

    キャンセル

+2

一列目はすべて1から始まっています

本来の目的から考えると、私なら左端を塗りつぶした画像を新たに作成します。
OpenCVを使えば内部はネイティブ処理してくれると思うので速度も期待できます。
以下例では左端の黒を白ですが、逆も同様の考えでできます。

import cv2
img = cv2.imread( 'bin.bmp', cv2.IMREAD_GRAYSCALE) # 簡単のため2値ビットマップを読込
print(img.shape)
# y方向に左端が黒を白に塗りつぶし
for r in range(img.shape[0]):
    if img[r,0] == 0:
        print('fill',r)
        cv2.floodFill(img,None,(0,r),255)
cv2.imwrite('out.jpg',img)


bin.bmp
イメージ説明
out.jpg
イメージ説明

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

もしかしてnumpy配列を直接pythonから処理していますか?
それなら、cythonの力で高速化しちゃえば同じアルゴリズムで100倍くらいは期待できるはずです。

参考ページ:
NumPyとCythonを組み合わせると爆速! - Kesinの知見置き場 

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

RLE (Run Length Encoding)を高速にできれば、境界をグラフ化するのも簡単になりそうですね。

Pure PythonでRLEを書くにはitertools.groupbyを使うのが正攻法らしいです。Pure Pythonに限らなければもっと速く書くことはできると思います。

from itertools import groupby
[(k, len(list(g))) for k, g in groupby("111100010101011111000")]
"""
[('1', 4),
 ('0', 3),
 ('1', 1),
 ('0', 1),
 ('1', 1),
 ('0', 1),
 ('1', 1),
 ('0', 1),
 ('1', 5),
 ('0', 3)]
"""

長さ1(非連続)の1を取り除くのはRLE後でも可能ですが、手間がかかるのでできるだけRLE前に別途画像処理系のアルゴリズムで取り除いておくほうが良いと思います。良くは知りませんがノイズ除去処理あたりだと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

元の配列からひとつずらした配列を作成して、ベクトル同士の引き算をします。結果のベクトルの要素がゼロならひとつ前の値と連続状態にあることになります。
処理はnumpyのarrayにすれば簡単かと思います。2次元ベクトルと見なしてしまえばこの差の計算は1回で終わります。
arrayのsliceを使ったほうが簡単かもしれません

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

シンプルに書けば速くなる‥なんて甘くはないだろうけど。

import numpy as np

pixels = np.array([[1,1,1,0,0,0],[1,0,0,0,0,0],[1,1,1,1,1,0],[1,1,1,1,1,1]])

def search0(line):
    try:
        return line.index(0)
    except:
        return 0

print([search0(list(line)) for line in pixels])
# [3, 1, 5, 0]

絶対に0が含まれているなら、

pixels = np.array([[1,1,1,0,0,0],[1,0,0,0,0,0],[1,1,1,1,1,0]])
print([list(line).index(0) for line in pixels])
# [3, 1, 50]

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.52%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Python 3.x

    6367questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。