パターンマッチング（正規化相関など） 画像処理ソリューション
このとき、テンプレートと画像データがどれだけ似ているか？という評価値（類似度または相違度）にはいくつかあり、次に示すような値を用います。 以下の式において、テンプレートの輝度値の値をT(i,j)、画像の輝度値の値をＩ(i,j)とします。 座標の（ｉ，ｊ）はテンプレートの幅をｍ画素、高さをｎ画素としたとき、 左上（もしくは左下）を（0,0）、右下（もしくは右上）を（m-1、n-1）とします。 SSD(Sum of Squared Difference)ＳＳＤはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の２乗の合計が用いられます。 ＳＳＤの値が小さいほど、似ている位置となります。 SAD(Sum of Absolute Difference)ＳＡＤはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の絶対値の合計が用いられます。 ＳＡＤの値が小さいほど、似ている位置とな
視覚の幾何学 1
1 視覚の幾何学１ 呉海元＠和歌山大学 参考書 佐藤 淳： 「コンピュータビジョン －視覚の幾何学－」 コロナ社 ? projections Single view geometry Camera model Single view geom. 画像内の一点と3次元空間中の光線の関係 投影（Projections）・射影関係によって決定 ⇒ この関係を記述するカメラモデルが複数ある カメラモデル（Camera model） ? 投影による3次元空間から2次元画像への変換 レンズによる写真投影（物理モデル） ピンホールカメラ投影 射影・透視変換（中心投影） 正射影（平行投影） 平行投影・正射影モデル (Orthographic) 投影面 理想・簡単 ) , ( ) , , ( y x Z Y X 3D point 2D image position 投影中心 投影面 物理モデルに一番近い
動的計画法入門（数え上げ） - ペケンペイのブログ
数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。 例題 次の問題を考えてみよう。 N 桁以下の 3 の倍数はいくつあるか。 N が小さければ全列挙できる。i 桁の数がすべて列挙できていれば、その後ろに 0～9 を付け足せば i+1 桁の数をすべて列挙できることを使う。 dp[i] := leading zero を含めて i 桁のすべての非負整数の集合 #include <iostream> #include <string> #include <vector> using namespace std; int modulo(string s, int mod) { int ret = 0; for (char c : s) ret = (ret * 10 + (c - '0'))
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
AlphaGo | DeepMind
The story of AlphaGo so farAlphaGo is the first computer program to defeat a professional human Go player, the first program to defeat a Go world champion, and arguably the strongest Go player in history. AlphaGo’s first formal match was against the reigning 3-times European Champion, Mr Fan Hui, in October 2015. Its 5-0 win was the first ever against a Go professional, and the results were publis
TopCoder の傾向と対策４（Ｃ＋＋編：数え上げ）
ホームに戻る TopCoder の傾向と対策４（Ｃ＋＋編：数え上げ） ０、はじめに Div2 の hard は数え上げの問題がでます。 単に数え上げという視点で考えてみます。 １、1000000007 で割った余りを答えよ問題対策 TopCoder では整数の６４ビット制限を考慮してくれる。 よって、long long より大きな数値を考えなくても良い。 この数値を超える答えが出る場合には、 答えを 1000000007 で割った余りを答えよ、とされる。 足し算においては足し算を行うごとに % 1000000007 する。 引き算のときは先に引かれる数に 1000000007 を足しておく。 そこから引く数を引いて % 1000000007 する。 こうすると結果がマイナスにならず結果がおかしくならない。 掛け算する場合は足し算と同様である。 A * B をするとき、 A、B それぞれを
Borůvka's algorithm - Wikipedia
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.[1][2][3] The algorithm was rediscovered by Choquet in 1938;[4] again by Florek, Łukasiewicz, Perkal, Steinhaus,
AlphaGo: マシンラーニングで囲碁を
中国を起源とする囲碁は 2,500 年以上の歴史を持ち、その昔、孔子が文人、士大夫が嗜むべきとした四芸のひとつです。世界中で 4,000 万人以上に親しまれている囲碁のルールはシンプルです。2 人のプレーヤーが、交互に白黒の碁石を碁盤上に置いていきます。余白や相手の石を取り囲みながら地（領域）を広げていき、地の面積で勝敗を競います。このゲームでは直感や感覚が重要とされ、囲碁が求める審美性、巧妙さ、および深い思考力は長い年月に渡り、人間の創造力を刺激してきました。 シンプルなルールに比べ、囲碁は非常に複雑なゲームです。囲碁において考えられる手の数は実に 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,00
数列の連続部分列の"区間和の2乗"の総和をO(N)で求めるテク - koyumeishiのブログ
なんだかよくわからないタイトルでごめんなさい。こういうのなんて言ったらいいんだろうか。 先日の Facebook Hacker Cup 2016 Round2 C でそんなテクが要求されて解けなかったので自分用メモ書き。 教えて下さった@kyuridenamidaさんに感謝。 @koyumeishi_ (X-x1)^2+(X-x2)^2+...+(X-x_n)を展開するとnX^2-2*X*(x1+x2+..xn)+(x1^2+x2^2+...+xn^2)になるので，一次の総和と二次の総和持っとくといいかんじです．— きゅうり (@kyuridenamida) 2016, 1月 23 長さ $n$ の 数列 $A_1, A_2, ... , A_n$ について、 区間 $[l,r]$ の和を $ S_{l,r} = A_l + A_{l+1} + ... + A_r$ とします。 全ての区間
Mo's algorithm - ペケンペイのブログ
Mo’s algorithm について説明します。 Mo’s algorithm の動作の様子をアニメーションにしてみました。アニメーションを見れば、計算量解析パートは自明でしょう。IE以外なら見れると思います。 https://pekempey.github.io/mo_algorithm/mo.html Mo’s algorithm とは 区間クエリ系の問題を解くためのアルゴリズム。次のようなクエリに対して有効。 要素が更新されない クエリの先読みが可能 区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる Mo’s algorithm の流れ まず区間を平方分割し、左端をキーにしてクエリをバケットに入れる。その後、各バケット内で右端をキーにしてソートする。 結局のところ上の操作は次の比較関数でソートすること
Codeforces Round #339 (Div. 1) A. Peter and Snow Blower - pekempey's blog
※問題をエスパーしたので問題を勘違いしています。 問題文 codeforces.com 問題概要 点P と 多角形 S が与えられる。 点 P を中心とした円を 2 つ描き、多角形 S がその円の間に挟まれるようにする。 この 2 つの円に囲まれる領域の面積の最小値を求めよ。 解法 点と多角形の距離の最小値・最大値を求めれば面積の最小値が求められる。 点と多角形の距離の最小値は、点と多角形のそれぞれの辺の距離の最小値になる。 そのため、点と線分の距離を求めたい。 点と線分の距離は、点が緑色の領域内部にあるかどうかで求め方が変わる。 以降、直線の単位方向ベクトルを $d=(q-p)/|q-p|$ とする。 緑色の領域の内部にある場合 図でいうと r1 がこのケースになる。これは点と直線の距離を求めればいい。 点と直線の距離は外積を用いて、 $$ | d \times (r-p) | $$ で
競技プログラミング頻出アルゴリズム攻略
【DL輪読会】Hyena Hierarchy: Towards Larger Convolutional Language Models
There’s Math.random(), and then there’s Math.random() · V8
Show navigation Math.random() returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo-randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments. — ES 2015, section 20.2.2.27 Math.random() is the most well-known and frequently-used source of rand
どせい on Twitter: "2^32-1 乗で単位行列になるか実際に計算してみた https://t.co/NmYvnzgHNY https://t.co/m3yY8zvCqm"
2^32-1 乗で単位行列になるか実際に計算してみた https://t.co/NmYvnzgHNY https://t.co/m3yY8zvCqm
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
An algorithm for efficient and exhaustive template matching
コンピュータビジョン特論
[AAAI-16] Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
モンテカルロ木探索およびコンピュータ囲碁の進歩について
n個の球をm個の箱に分ける方法
bitset.js