リアルな映像を作るグラフィックス・アルゴリズム
3次元コンピュータ・グラフィックス（3DCG）の世界で，リアリティは非常に重要なテーマです。リアルな3DCGを作るため，これまで様々な研究/開発がなされ，その成果は映画やビデオ・ゲームなどで誰でも目にすることができるようになっています。そして，現在でもさらなるリアリティの追求のため，日々研究や開発が続けられています。このパートでは，そうしたリアルな3DCGの裏側にある技術の一端をお見せします。 3DCGのリアリティは「形状」「色/質感」「動作」という三つの要素に分けて考えることができます。これらが技術的にどのような難しい点を含んでおり，どのように解決されてきたかは，最後のカコミ記事「3DCGのリアリティを実現する三つの要素」を参照していただくとして，これらの三要素が一定の水準に達したところで浮かび上がってきた，ある問題に焦点を合わせてみましょう。それは自然な動作の大量生成が難しい，という問
Sliding Window - カメヲラボ
なかなか良さげな問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=2823 巨大な配列(最大10^6)の中で長さkの区間内の最大値と最小値を求める問題。 配列のサイズn=10、区間の長さk=3とすれば、 Window position Minimum value Maximum value [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 このように区切ることになり、最小値・最大値は順に -1 -3 -3 -3 3 3 3 3 5 5 6 7のようになる。配列サイズが大きいので、当然単純なソートでは終わ
第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム：ITpro
「倉庫番」＊1というゲームをご存じでしょうか。図1のように盤面にはいくつかの「荷物」とそれを運ぶ「人」がいます。人は1個の荷物を押して運ぶことができます。荷物を引っ張ったり，二つ並んだ荷物を同時に押して運ぶことはできません。人と荷物は縦横4方向に動けますが，壁のある位置には進めません。人を使って盤面上の荷物を動かし，すべての荷物を目的地（ゴール）に収めることができればゲーム・クリアとなります。図1の問題を解くための手順を示すアルゴリズムを作ってください。 友人たちと車でスキーに行くとき，いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキー靴やかさばるスキーウエアを詰め込んでいるうえ，人によってはゲーム機や本を持ってきたりするので，各自の荷物の量がまったく違うのです。狭い車のトランクには，これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰
最小完全ハッシュ関数の作り方
■順列型の最小完全ハッシュ関数 ０から４までの５個の数字が下のように並んでいる場合を例にして説明します。 ５個の数字の並べ方は５！通りありますので５！(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 ３４１０２ ここでは左側から順に数字を見ていくことにします。最初の数字は３で残りの数字の個数は４個ですね。 この残れさた数字の個数分の総順列数は４！ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基本となる重みのことです。 従って先ず最初の数字３に基数である４！を掛け算してはじき出します。 [３]４１０２ → ３＊４！ 次に左から２番目の数字ですが、ここから先はとても注意が必要です。 ２番目の数字は４で残りの数字の個数は３個です。残りの数字の個数が３個なので基数は３！になります。つまり基数が変化
A Plan for Spam - スパムへの対策
スパムへの対策 ---A Plan for Spam Paul Graham, August 2002 これは、Paul Graham：A Plan for Spam を、原著者の許可を得て翻訳・公開するものです。 <版権表示> 本和訳テキストの複製、変更、再配布は、この版権表示を残す限り、自由に行って結構です。 (「この版権表示」には上の文も含まれます。すなわち、再配布を禁止してはいけません)。 Copyright 2002 by Paul Graham 原文: http://www.paulgraham.com/spam.html 日本語訳：Shiro Kawai (shiro ＠ acm.org) <版権表示終り> Paul Graham氏のエッセイをまとめた『ハッカーと画家』の 邦訳版が出版されました。 出版社の案内ページ Amazon.co.jp サポートページ
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
脆弱性関連情報取扱い：APOP方式におけるセキュリティ上の弱点（脆弱性）の注意喚起について：IPA 独立行政法人 情報処理推進機構
独立行政法人 情報処理推進機構（略称：IPA、理事長：藤原武平太）は、メールの受信に利用される認証方式の一つであるAPOP（エーポップ）方式におけるセキュリティ上の弱点（脆弱性）に関する注意喚起を2007年4月19日に公表しました。 具体的には、APOP方式にはパスワードが漏えいする脆弱性があるというものです。悪用されると、メールの受信に利用しているパスワードが、SSHやウェブサイトへのログインに利用しているパスワードと同一の場合、不正なログインに利用される可能性があります。 プロトコル(通信手順)上の問題であり、現時点で根本的な対策方法はありません。 回避方法は「『POP over SSL』や『ウェブメール』など、SSLによる暗号化通信を利用する」ことです。回避方法が取れない場合「メールのパスワードを他のシステムのパスワードと同一にしない」ことで悪用された際の被害を軽減できます。 電子メ
衝突判定のアルゴリズム
2 つの図形の衝突判定 (コリジョン判定) のアルゴリズムをまとめます。 図が用意できておらず見難いですが、ご勘弁を。 太字はベクトルを表します。 線分と三角形 線分を p+tl、 三角形を (1-u-v)q0+uq1+vq2 で表します (t, u, v は媒介変数)。 Tomas Moller のアルゴリズム を Cramer の公式で解きます。 0.0≦t≦1.0, 0.0≦u, 0.0≦v, u+v≦1.0 なら交差と判定します。 半直線と三角形 線分と三角形の場合と同様の計算を行います。 0.0≦t, 0.0≦u, 0.0≦v, u+v≦1.0 なら交差と判定します。 点と球 点と球の中心の距離の 2 乗を求めて、 その長さが球の半径の 2 乗以下なら交差と判定します。 線分と球 線分の始点から終点へのベクトルを v、 線分の始点から球の中心へのベクトルを c とします。 v・c
交差判定_3DCG - FreeStyleWiki
レイトレース処理での一番大事な部分、交差判定について記述します。ここではレイ（視点位置と視線ベクトルを持つ）とポリゴン（三角形）との交差判定になりますね。 単純な交差判定 三次元空間上のポリゴンをX/Y/Z軸を圧縮する形で２次元に投影してしまいます。これは、X-Y平面への投影・X-Z平面への投影・Z-Y平面への投影の３つの投影があります。一番確実なのは（誤差を少なくするのは）それぞれの面に投影した場合の面積を計算して、一番面積の大きい面に投影するとするといいです。 上図の場合は、X-Z平面に投影しています（三角形の頂点座標のうち、X/Z成分のみを取り出します）。 また、レイの方向ベクトルと面の法線ベクトルにより「直線と面の交点位置」を求めます（これは３次元空間での処理）。このときに交点が求まります。が、三角形内に内包されているかは分かりません。これを、X-Z平面に三角形を投影している場合は
第6回 上手なアルゴリズムの見つけ方
図1に示すHTML形式のテキスト・データ（以下，HTMLデータ）があります。このHTMLデータをブラウザに表示させたときに「表示される文字列」と「その文字列に対して有効なタグ名」を対応付けるアルゴリズムを考えてください。結果は配列に格納して，画面に表示させるものとします（図2）。 見わたせば，世の中はアルゴリズムだらけです。私のようなプログラマは，日常生活でも「締め切り順に仕事をソートしてごらん」「仕事のスタックがたまっているからてんてこまい」など，いま置かれている状態をアルゴリズムやデータ構造になぞらえて会話することがよくあります。前回紹介した再帰処理と言えば，落語の演目の一つ，「頭山」です。自分の頭に生えた桜の木を引っこ抜いて，その跡にできた池に自分自身が身を投げる，という不思議な話ですが，これこそ再帰処理をよく言い表していると思います。 このように世の中には，ハッシュだってスタックだ
GeckoのReflowをアニメーションにする - 最速チュパカブラ研究会
MDCの記事用にGeckoのReflow（レイアウトを組み立てる処理）の過程をアニメーションGIF↑にしましたが、これが思ったより良い画になったので、トゥイーニングをつけてムービーを作ってみました。 まず、みんなの好きなGoogle。あんまり面白くないです 続いてWikipedia。スクロールバーが出て表示域が狭まったために、サイズを再調整している様子が見えます。 最後に、Mozilla.orgのトップ。floatの扱いがよくわかります。ここでもスクロールバーの出現に伴う再配置が発生しています。 作り方は大体以下のような感じです 各frameのrectが変化したところで位置、大きさ、this pointer値および親のthis pointer値をログに書き出すコードをMozillaに仕込む Rubyスクリプトでログを舐めて、frame treeを再構成する もう一度最初からログを舐めて、各
k-nearest neighbors algorithm - Wikipedia
In statistics, the k-nearest neighbors algorithm (k-NN) is a non-parametric supervised learning method. It was first developed by Evelyn Fix and Joseph Hodges in 1951,[1] and later expanded by Thomas Cover.[2] Most often, it is used for classification, as a k-NN classifier, the output of which is a class membership. An object is classified by a plurality vote of its neighbors, with the object bein
Better Bayesian Filtering - ベイジアンフィルタの改善
ベイジアンフィルタの改善 --- Better Bayesian Filtering Paul Graham, January 2003 これは、Paul Graham： Better Bayesian Filtering を、原著者の許可を得て翻訳・公開するものです。 <版権表示> 本和訳テキストの複製、変更、再配布は、この版権表示を残す限り、自由に行って結構です。 (「この版権表示」には上の文も含まれます。すなわち、再配布を禁止してはいけません)。 Copyright 2002 by Paul Graham 原文: http://www.paulgraham.com/better.html 日本語訳：Shiro Kawai (shiro ＠ acm.org) <版権表示終り> Paul Graham氏のエッセイをまとめた『ハッカーと画家』の 邦訳版が出版されました。 出
ベイジアンフィルタについて
最近話題のベイズ理論を用いたフィルタについて整理してみました．まず，ベ イズ理論が注目され始めたというニュースを最初にみたのが，ＭＳも注目する “ベイズ”って何だ(oricom.co.jp)でした． このときは対して気にもとめていませんでしたが，再度興味をそそられ出した のが，グーグル、インテル、MSが注目するベイズ理論(CNET)のニュース． MSだけならまだしも，Googleが，というのが自分的には大きかったです．しか し，このニュースだけでは，この技術が具体的にどのように採用されるのか， 特に検索エンジンのような大規模なものに適用可能かどうかは大きな疑問でし た． そもそも，このベイズ理論がどこに聞いてくるのかということを考えるとその 疑問は自然だと思います．ベイズ理論（ベイズ推定）は，過去に起きた事象の 確率を利用して未来を予測する手法です．そのため，直感的にはユーザごとの 最適化
画像圧縮アルゴリズム (8) ウェーブレット変換 -1-
この章では、JPEG2000フォーマットで圧縮アルゴリズムとして採用されたことで、一躍有名になったウェーブレット変換(Wavelet Transform)について取り上げたいと思います。 JPEG2000では画像圧縮アルゴリズムとして採用されましたが、元々はフーリエ変換の応用形として、データ解析の利用を目的に考案された手法であり、その内容も多岐に渡っています。全てを説明するのは量的にも、自分の理解度から見ても不可能なため、ここでは離散ウェーブレット変換と、それを用いた解析手法である多重解像度解析を中心に紹介をしたいと思います。 1) フーリエ変換とウェーブレット変換 あるデータや関数の特性を分析する手法としてよく知られたものに、フーリエ変換(Foueier Transform)があります。フーリエ変換は、周期を持った任意の時間関数を正弦波と余弦波の和で表すことができることを利用して、時系
超簡単なウェーブレット
多重解像度解析 データ―→低周波成分→低周波成分→低周波成分 ↓ ↓ ↓ ↓ …… 高周波成分 高周波成分 高周波成分 高周波成分 Lifting 両側からの予測誤差符号化（ハイパスフィルタ） 奇数番目のデータを偶数番目のデータで予測し，予測誤差を奇数番目に上書きする x'2i+1 = x2i+1 - (x2i + x2i+2) / 2 これは次のハイパスフィルタと同値 x'i = -0.5 xi-1 + xi - 0.5 xi+1 平滑化（ローパスフィルタ） 偶数番号のデータの平均値が元の全データの平均値と等しくなるようにするために，上で求めた予測誤差÷4を偶数番目のデータに加える x'2i = x2i + (x'2i-1 + x'2i+1) / 4 これは次のローパスフィルタと同値 x'2i = -(1/8) x2i-2 + (1/4) x2i-1 + (3/
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
染め手読み精度検証 - マッタリプログラミング日誌
Gauche:SpamFilter:予備実験
Gauche:SpamFilter
サービス終了のお知らせ