3日で作る高速特定物体認識システム (1) 物体認識とは - 人工知能に関する断創録
情報処理学会の学会誌『情報処理』の2008年9月号（Vol.49, No.9）に「3日で作る高速特定物体認識システム」という特集記事があります。OpenCVを用いた面白そうなプロジェクトなのでレポートにまとめてみようと思います。3日でできるかはわからないけど。 残念ながらこの記事はPDFを無料でダウンロードすることができません（CiNiiでオープンアクセス可能になったみたいです）。なので会員以外で元記事が読みたい人は図書館でコピーする必要があるかも・・・また、2009年9月号の人工知能学会誌にも物体認識の解説「セマンティックギャップを超えて―画像・映像の内容理解に向けてー」があります。こちらも非常に参考になりますが同様にPDFが手に入りません・・・。他にもいくつかわかりやすい総説論文へのリンクを参考文献にあげておきます。 物体認識とは 物体認識（object recognition）は、画
Haskell 99問 (1-10) | tnomuraのブログ
Haskell 99問より、1ー10問。Haskell のプログラミングがアルゴリズムそのものを記述するという雰囲気がわかる。したがって、プログラミングがどこかパズル風になるのが面白い。 http://www.haskell.org/haskellwiki/99_questions/1_to_10 から引用。 第1問 リストの最後の要素を取得する関数を作れ。 解答 mylast :: [a] -> a mylast [x] = x mylast (x:xs) = mylast xs 第2問 リストの最後から2番目の要素を取得する関数を作れ。 解答 last1 :: [a] -> a last1 [x,_] = x last1 (x:xs) = last1 xs 第3問 リストの n 番目の要素を取得する関数を作れ。 解答 elementAt :: [a] -> Int -> a eleme
定兼 邦彦 (Kunihiko Sadakane) - 研究ブログ - researchmap
部分文字列の頻度を求めるプログラムを作成しました． サンプルプログラムのところからダウンロードできます． 文字列 T (長さ n) と文字列 P (長さ m) が与えられたとき，P の各部分文字列の T の中での 出現頻度を求めます． 実行は次のように行います． ./a.out -f1 pattern index.idx index.wxdpatternは P に対応するファイルで，index.idx と index.wxd は T の索引です． -f1 は出力するパタンを指定するフラグで， -f0 から -f2 まであります．省略すると -f0 と同じです． -f0 のとき，P の各位置 i に対し，そこから始まる部分文字列 P[i..j] (i <= j < n) に対し， その出現頻度を表示します．ある i に対し，j を順に増やしていき頻度を求め，出現頻度が 0 になったら i を
定兼 邦彦 (Kunihiko Sadakane) - 圧縮接尾辞配列ライブラリ - researchmap
文字列を圧縮したまま検索するライブラリです． 文字列の一部を高速に復元することもできます． 圧縮接尾辞配列ライブラリ (2010-08-10版) Direct BWT construction External Memory BWT construction http://code.google.com/p/csalib/ にもあります． 注意: dbwt100717.zipにはバグがありました．Ubuntuでは動かない可能性が高いです． dbwt100730.zipを使ってください． 索引とは，本の索引と同じ意味で，検索を高速に行うためのデータのことです． ただし，本の索引では代表的な言葉のみが登録されていますが，このライブラリの索引は 任意の語が検索できるようになっています． このライブラリの索引は自己索引 (self-index) と呼ばれるもので，索引自体に 元のファイルの情報を全
橋本詳解
JSでRSA暗号が使えるやつ使ってみた http://cryptico.wwwtyro.net/ 鍵作る var pass = 'kazusuke'; var rsa_key = cryptico.generateRSAKey(pass, 1024); var pub_key = cryptico.publicKeyString(rsa_key); 'hello'を暗号化 var enc = cryptico.encrypt('hello', pub_key); console.log(enc.cipher); 復号するとhelloが出てくる var dec = cryptico.decrypt(enc.cipher, rsa_key); console.log(dec.plaintext); Macはファイルが作成された時にフォルダアクションが実行できる フォルダアクションはAutoma
SACHICA(類似文字列列挙アルゴリズム) - Yasuo Tabeiの日記
SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。 http://sites.google.com/site/yasuotabei/sachica sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。 アルゴリズムは、マルチソーティングという手法に基づきます。 詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。 今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソ
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
転置インデックスを実装しよう - mixi engineer blog
相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
算術符号化法における復号プログラムの動作試験及び 適応的アルゴリズムの性能評価実験と動作特性の測定
Project ITADACI 算術符号化法における復号プログラムの動作試験及び 適応的アルゴリズムの性能評価実験と動作特性の測定 Project ITADACI （長野大学産業社会学部産業情報学科） 概要： 著名な圧縮アルゴリズムである算術符号化法における静的方法と適応的方法の概念及び動作原理を紹介する。また、これまでの研究を引き継ぎ、復号プログラムの動作試験を行った。そして、双方の圧縮効果の差違を確認する為に行った比較実験及び適応的方法における出現確率の遷移を確認する為に行った動作実験について、それらの結果を報告し考察する。 INDEX 0. 始めに 1. 情報の圧縮 1.1 圧縮手段の概要 1.1.1 可逆圧縮と非可逆圧縮 1.1.2 符号化の手順 1.1.2.1 モデル化 1.1.2.2 符号化 1.1.3 静的方法と動的方法 1.1.4 適応的方法（adapt
Modern Information Retrieval
Information retrieval (IR) has changed considerably in the last years with the expansion of the Web (World Wide Web) and the advent of modern and inexpensive graphical user interfaces and mass storage devices. As a result, traditional IR textbooks have become quite out-of-date which has led to the introduction of new IR books recently. Nevertheless, we believe that there is still great need of
ベンフォードの法則を確かめてみる - みずぴー日記
30分プログラム、その584。素数の分布はベンフォードの法則に従っているらしいので試してみる。 「ベンフォードの法則」とは、ある数値群をみたとき、最高桁が「1」である数値は（15や189や1088など）は全体の約30%、「2」であるものは約18%、「3」であるもの約12%･･･「9」であるものは約5%という割合になっているという法則である。この法則は物理学者フランク・ベンフォードが1938年に発見した分布法則であり、市場分析や不正検出アルゴリズムなどにも応用されているものである。 スペインの数学者がBartolo LuqueとLucas Lacasaは素数にもこの法則が当てはまることをこの度解明したそうだ（論文要旨）。 というわけで、これを最高桁の分布を調べるプログラムを書いてみた。 とりあえず5000までの素数で確認したけど、特にベンフォードの法則には従っていなかった。まあ、そんなに簡単
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
レコメンデーションとエディットグラフ
レコメンデーションとエディットグラフ：コーディングに役立つ！ アルゴリズムの基本（10）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 実際のアプリケーションで使われるアルゴリズム これまで見てきたアルゴリズムは、実際のアプリケーション開発の際にそのまま使われることはあまりなく、プログラム言語やライブラリなどですでに機能が用意されているものが大半でした。 今回は最終回ということで、実際のアプリケーション開発でそのまま使えるものを紹介したいと思います。 レコメンデーション ECサイトで、「あなたにお勧めの商品」を表示していることがあります。いろいろなデータベースや行動履歴のデータから、その人ごとにお勧めの商品をはじき出して推薦する機能をレコメンデー
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
FrontPage - BayesWiki
お知らせ † ベイズウィキの置き場をNAIST（http://hawaii.aist-nara.ac.jp/~shige-o/pukiwiki/index.php） から京都大学のサーバー上 （http://hawaii.sys.i.kyoto-u.ac.jp/~oba/bayeswiki/index.php）に移動しました. 2008/08/01 スパム対策に設置した併設会議場のほうのスパムがひどくなってきたので、 スパム対策を強化した本家pukiwiki のほうをメインとするべく整備中です。 2007/05/18 コメントスパム対策のために、合言葉を設定しました。 コメントを書き込むときには お名前欄に自分のハンドル名とともに bayes と半角英字で書き込む ようにして下さい。 2007/05/09 投稿や編集にパスワードを要求するようにしました。 ユーザー名、パスワードともに英小文
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズム入門 : 第 4 章 画像処理入門 2
サービス終了のお知らせ
http://www.bi.a.u-tokyo.ac.jp/~tak/index.html