問題タブ [baduk]

標準の素集合構造は非結合をサポートしていないため、結合、検索、および非結合をかなり効率的にサポートできるデータ構造を探しています (すべて少なくとも O(log n) 以上)。背景として、私は MCTS [ http://en.wikipedia.org/wiki/Monte_Carlo_tree_search]を使用して Go AI を作成しています。これは、バックトラック中に接続および切断される石のグループを追跡するために使用されます。デユニオンはセット内の任意のオブジェクトではなく、常に最新のユニオンの「元に戻す」ため、これにより簡単になると思います。

私は次の論文を読みましたが、提案されたデータ構造を実行することはできましたが、少しやり過ぎで、 http://docs.lib.purdue.edu/cgi/viewcontent.cgi ?article を実装するのに時間がかかるようです。 =1773&context=cstech

もちろん、O( a(n)) は素晴らしいものですが、パス圧縮は de-union では機能しないと確信しており、O(log n) に満足しています。私の腸は、解決策がヒープに関連している可能性があることを教えてくれますが、何も理解できませんでした.

GO ボードを認識し、そのSGF ファイルを作成するAndroid アプリに取り組んでいます。

ボードを検出し、パースペクティブをワープして正方形にすることができるバージョンを作成しました（下のコードとサンプル画像）残念ながら、石を追加すると少し難しくなります（下の画像）

平均的な碁盤に関する重要事項:

• 丸い黒と白の石
• ボード上の黒い線
• ボードの色は白から明るい茶色まであり、時には木目があります
• 石は2本の線の交点に置かれます

私が間違っている場合は修正してください。ただし、現在のアプローチは適切ではないと思います。石と線を写真の残りの部分からどのように分離できるかについて、誰かが一般的な考えを持っていますか?

私のコード:

いくつかの画像:

_{（出典：eightytwo.axc.nl）}

_{（出典：eightytwo.axc.nl）}

編集： 2016年5月3日

わーい！ラインストーンと色を正しく検出できました。前提として、写真はボード自体のみで、他の背景が見えないようにする必要があります。
私は houghLinesP (60lines) と houghCircles (17circles) を使用し、携帯電話 (第 1 世代の Moto G) で約 5 秒持続します。
ボードとワープを検出することは、さまざまな角度や雷の条件下で作業する必要がある場合、非常に困難であることが判明しました..まだそれに取り組んでいます

さまざまなアプローチの提案は大歓迎です!!

_{（出典：eightytwo.axc.nl）}

編集: 15-03-2016

私はクロスタイプの形態学的変換と交差する線を取得する良い方法を見つけました。写真がボードの真上で撮影された場合、残念ながら斜めではありません（以下を参照） _{（ソース：eightytwo.axc.nl）}

前回の更新で、真上から撮影した写真でラインとストーンの検出を示しました。それ以来、ラインとストーンの検出が役立つように、ボードの検出とワープに取り組んできました。

ハリス コーナーの検出
正しいパラメータ設定を得るのに苦労しましたが、それらが最適かどうかはまだわかりません。ハリス コーナーを使用する前に画像を最適化する方法について多くの情報を見つけることができません。現在、多くのコーナーを検出して便利です。それはうまくいくように感じますが。（例の写真付きの上の行）

クロスタイプの形態変換
は、写真が真上から撮影された場合、斜めから使用された場合、または回転したボードで使用された場合にうまく機能します（例の写真の中央の線）

外側のボードラインに石がなく、光条件が厳しくない場合、輪郭とハウライン
はかなりうまく機能します。輪郭はボードの一部にすぎないことがよくあります (下の線と例の写真)

適切な画像を提供すると、3 つの方法すべてが機能しますが、信頼できるほど十分ではありません。パラメータ、画像の前処理、さまざまなアプローチ、または検出を改善する可能性のあるものについての考えは大歓迎です =)

画像へのリンク

編集: 31-03-2016

線と石の検出はほとんど解決されたので、この質問を閉じます。検出とワープを正確に行うための新しいものを作成しました。

私の進歩に興味がある人:これは私の GOSU Snap Alpha チャンネルです。今はあまり期待しないでください!

編集: 16-10-2016

更新: 何人かの人々がまだこの質問に従っているのを見ました. 私はさらにいくつかのことをテストし、Tensorflow の使用を開始しました。私のニューラル ネットワークは有望に見えます。ここで見ることができます。 まだ多くの作業を行う必要があります。現在の画像データセットはひどく、現在、大きなデータセットの取得に取り組んでいます。

アプリは、太い線とまともな稲妻のある正方形のボードを使用すると最適に機能します.

GO ボードを認識し、そのSGF ファイルを作成するAndroid アプリに取り組んでいます。

ボード全体をワープして、以下のような正しいラインと石を見つけることができるようにする必要があります。

_{（出典：eightytwo.axc.nl）}

現在、Opencv RGB Mat を使用して、次のことを行っています。

• チャンネルを分ける

• 別々のチャンネルをキャニー

  /li>

• すべてのチャネルを結合 (ビットごとの OR) します。

  /li>
• ボードの輪郭を見つける

下の写真でわかるように、いくつかの線が消える傾向にあり、ボード上の黒い線と石がはっきりと見えますが、ボードの端がいくつかの場所で欠けているため、まだボードを一貫して検出することはできません.

_{（出典：eightytwo.axc.nl）}

この検出を改善するにはどうすればよいですか? または、それを検出し、失敗したときにそれらを切り替える複数の方法を実装する必要があります..

* 覚えておくべき重要なこと *

• 碁盤は色によって異なります
• 囲碁盤は空であるか、完全に石で満たされている可能性があります。
  これは、盤上の外側の黒い線の検出に頼ることができないことを意味します。
• 背景は必ずしも真っ白ではありません

これは、私が検出したい囲碁盤の写真の小さなコレクションです

* 更新 * 2016 年 5 月 23 日

これを解決するためにopencvを使用してインスピレーションを使い果たしたので、新しいインスピレーションは大歓迎です!!! その間、私は機械学習を使い始めました。最初の結果は素晴らしく、引き続き投稿しますが、opencv の実装を作成することには大きな期待を寄せています。

私はパイゲームとボードの場所と石の色（0、1、2）を格納するためのnumpy配列を使用して、PythonでGOのボードゲームを作成しようとしています。私の問題は、for ループを使用して一度に各インデックスを調べ、int を追加または削除して隣接するインデックスを調べていたことです。

この方法は、単一の石をキャプチャするのには問題ないように見えます (ボードの端にない限り、範囲外の問題も発生し始めるため) が、同じ色の複数の石がそれぞれ隣にあると非常に複雑になります。その他であり、キャプチャする必要がある場合とない場合があります。

範囲外を引き起こすことなくこれらのインデックスを検索するより良い方法が必要ですか? すべての石とそれに隣接するスペースを追跡できるものはありますか?