こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは、MeCab互換の形態素解析器Vibrato（ヴィブラ〰ト）を開発しています。プログラミング言語Rustで実装しており、高速に動作することが主な利点です。Vibratoはオープンソースソフトウェアとして以下のレポジトリで公開しています。 github.com 本記事では、Vibratoの技術仕様を解説します。以下のような方を読者として想定します。 自然言語処理の要素技術に興味のある方 データ構造・アルゴリズムに興味のある方 Rustでの自然言語処理に興味がある方 Vibratoについて 最小コスト法による形態素解析 単語ラティスの構築 最小コスト経路の計算 高速化の取り組み 辞書引きのキャッシュ効率化 実装での注意点 連接コスト参照のキャ

x-meansとは，k-meansの繰り返しとBICによるクラスターの分割（or処理停止）基準によって，最適なクラスター数を決定するアルゴリズムです． この記事ではpyclusteringというライブラリでx-meansを使う方法を紹介します． k-means系まとめ k-means：クラスターの重心からの二乗誤差を最小化． k-medoids：クラスターのmedoid（クラスターに属する点で，非類似度の総和が最小となる点）からの非類似度の総和が最小となるようにEMの手続きを行う． x-means：BICに基づいてクラスタの分割を制御． g-menas：データが正規分布に基づくと仮定して，アンダーソン・ダリング検定によってクラスタの分割を制御． gx-means：上二つの拡張． etc（pyclusteringのreadme参照．色々ある） クラスター数の判定 データを人間が目で見てすぐに

はじめに 昨年１２月にこんなツイートを見かけました。 かわいいですね。幸いにして論文と実装が公開されていたので、自分でもやってみようと思って、その結果を書いたのが前回の記事です。 読んでいただければわかるとおり、前回の記事の中ではGPUを使わずにアルゴリズムやデータ構造を工夫して近似的に計算しています。結果の画像についてはそんなに悪くないと思っていますが、限界もありました。パーティクルの数も少ないし、一部の画像ではうまく行きませんでした。 やっぱり、もっとちゃんとネコチャンを点描してみたいですよね。 なので、今回の記事ではGPUを使ってアルゴリズムを再現し、よりヴィヴィッドなネコチャンの点描を作成しようと思います。GPUを使って計算するために、WebGPUのRust実装であるwgpuを使用します。ネコチャンの画像を点描にしたい人と、WebGPUに入門してcompute shaderで何か計

投稿日：2021/09/18 はじめに 小田垣先生著作の『つながりの物理学ーパーコレーション理論と複雑ネットワーク』の付録ページのクラスター形成のアルゴリズムを読んで実際に作ってみました。Numpyで基本的に組むため、本とは少し定義が異なります。Pythonで組んだコードを探してみた所、Numpyなどの基本ライブラリで構成された文献が見当たらなかったので参考になれば幸いです。 クラスターとは $N\times N$の正方格子を考えます。この正方格子上の格子点を$(i,j)\quad (i,j=0,\dots,N-1)$で表し、占有確率$p$のとき、$p\times N^2$個の格子点がランダムに占有されているとします。このとき、ある占有されている格子点$(k,l)$があり、$(k\pm 1,l)$、$(k,l\pm 1)$のいずれかが占有されているとき、その占有されている格子と$(k,l)

ヒルベルト曲線の最初の8ステップ 1次のヒルベルト曲線 1次、2次のヒルベルト曲線 1次、2次、3次のヒルベルト曲線 3次元のヒルベルト曲線。 ヒルベルト曲線（ヒルベルトきょくせん、Hilbert curve）は、フラクタル図形の一つで、空間を覆い尽くす空間充填曲線の一つ。ドイツの数学者ダフィット・ヒルベルトが1891年に考案した[1]。 平面を充填するため、ヒルベルト曲線のハウスドルフ次元は、 の極限で2である。 次のヒルベルト曲線 のユークリッド距離は となる。すなわち、 に対して指数的に増加する。

概要 OpenCVのcv2.Canny()関数に画像を投げると上図中央のようなエッジ検出結果が返されるが，このままだとエッジはただの白点の集合であり扱いづらい．そこで，エッジ検出結果のエッジを表す白点を繋いでいき，『いい感じ』の曲線(折れ線)を生成することを目指す．折れ線に変換することで，例えばBスプライン曲線補完することでエッジの連続化とスムージングを行ったり，閉じたエッジの場合は囲まれた部分の面積を求めたりできるようになる．最も素朴な方法は一番近い点同士をを繋いでいくというもので，この方法でも割といい感じの折れ線にはなるが，ここではもう少し工夫を凝らす． 表記に関する注釈 $\left(a_1, \dots, a_N \right)$ のように丸括弧で表記されたものは順列を表す． $\left\{a_1, \dots, a_N \right\}$ のように波括弧で表記されたものは集合を

赤で表される集合の凸包は、青で表された凸集合である。 数学における凸包（とつほう、英: convex hull）または凸包絡（とつほうらく、英: convex envelope）は、与えられた集合を含む最小の凸集合である。例えば X がユークリッド平面内の有界な点集合のとき、その凸包は直観的には X を輪ゴムで囲んだときに輪ゴムが作る図形として視認することができる[1]。 精確に言えば、X の凸包は X を含む全ての凸集合の交わり、あるいは同じことだが X に属する点の凸結合全体の成す集合として定義される。後者の定式化であれば、凸包をユークリッド空間だけでなく任意の実線型空間や、より一般に有向マトロイド（英語版）に対して考えることができる[2]。 平面上あるいは低次元ユークリッド空間内の有限点集合に対してその凸包を計算するアルゴリズム問題は、計算幾何学の基本的問題の一つである。 与えられた

はじめに 前回、NetworkXでグラフの作成と、A*アルゴリズムによる経路探索をしました。 今回は、グラフにコストを追加して、経路探索してみます。 また、ノードとエッジに色をつけて、経路を可視化してみます 日常生活で、目的地への経路を考えるとき、近道 or 遠回り、混む道 or 空いている道などを考慮することもあります。 これらを、コストとして表現していきます。 通常、隣接するノード間の"距離"を、コストにすることが多いです。 今回のアウトプットは、下図です。 導出した経路を青色で塗りました。エッジ中央の数字がコストです。 コストのラベルに加え、各ノードの座標も描画しています。 見づらい気がしますが、ボスg...　重要な情報ですね。 コードを書いていく Step0. 準備 Python 3.8.6、NetworkX 2.6.2を使います。まず、import。 import numpy a

Watershedアルゴリズムとは、くっついているものを分離したりなど、 古典的領域分割アルゴリズムです。分水嶺アルゴリズムとも言われています。 OpenCVのWatershedアルゴリズムをちょっと試してみようと 思ったら、参考文献やWebページ見ても良くわからなった。 サンプルや資料をひたすら読む。 距離変換関数 distanceTransform サンプルプログラム中に必ず、distanceTransform()があった。 これって何？「近似距離または正確な距離を求めます」と解説にはあった。 distanceTransform() 良く分からないので、白真円の二値画像を距離変換してみます。 二値画像を距離変換した結果の画像です。 黒い部分からの距離が値となっているものを画像としました。 結局、中央部を二値化で求めるだけ、分離の初期とりつき 位置を求めようとして使っていたので、補助的な

注意：結構この記事読んでくれる方が多いんですが、こちらの記事に書いてあるコードだと激烈に遅いので、アルゴリズムの説明を読み終わったらこっちのコード使ってください。 細線化は、(主には2値化した)画像を幅1ピクセルの線画像に変換する操作です。 用途は色々あるのですが、画像処理ライブラリのOpenCVになぜか細線化のメソッドが無かったので、 勉強も兼ねて自分で実装しました。 速さが欲しい場合こちらへどうぞ。 #細線化のアルゴリズム 細線化にはいくつかのアルゴリズムが提案されています。 田村のアルゴリズム Zhang-Suenのアルゴリズム Nagendraprasad-Wang-Guptaのアルゴリズム それぞれ癖があるのですが、 今回は2番のZhang-Suenのアルゴリズムを使いました。 (ロジックが簡単で書きやすそうだったので) #Zhang-Suenのアルゴリズム 細線化に用いる画像は

ダイクストラ法の動作のアニメーション ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。 ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 ほかのアルゴリズムとして、 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間での計算が可能