three.js勉強日誌 【No.6】
ディジタル画像とアルゴリズム1

ディジタル画像とアルゴリズム

2015年3月31日 NO.6

再開

こんばんは。 去年の9,10月ごろ掲載していたブログを、自身の勉強のために再開させて頂きます。 内容としましては、コンピュータ・グラフィックスや数値計算、数学や物理の話になると思います。もちろん勉強する目的もですが、ブログを通して特に客観的な文章を書く練習として使わせて頂きます。 では、またよろしくお願いいたします。

コンピュータ・グラフィックスと画像

コンピュータ・グラフィックスを改めて記事にするにあたり、原理からおさえてコンピュータ・グラフィックスを深く勉強していこうとおもいます。 openGLのWeb版であるWebGLをラッピングしたthree.jsを用いてコンピュータ・グラフィックスを作成していきます。

コンピュータ・グラフィックスは、形を作るモデリングや出来上がったデータを２次元画像に落としこむレンダリングばかり注目されがちですが、できあがった２次元データを画像として出力する部分はおろそかにされがちです。 コンピュータ・グラフィックスを学ぶにあたりまずは、２次元データを画像として出力するにはどのような手順を踏んでいるかなどおさえるとより理解が深まるかもしれません。

ラスタ表現とベクタ表現

コンピュータで画像を扱うには、画像そのものを格子状の区間にわけて、それぞれの区間での濃淡や色を記録するという方法があります。このように表現される画像をディジタル画像とよばれます。また、この区間のこそがピクセルなのです。 一方、図形を線分でつないで表す方法をベクタ表現といいます。 しかし、ディジタル画像ではベクタ表現で表された図形を表現できません。

図形を画素の集合に置き換える表現方法をラスタ表現というのですが、このラスタ表現するにもアルゴリズム(手順)が存在するので、今回はそのラスタ表現をするアルゴリズムをいくつか見ていくとしましょう。

直線をラスタ表現で表す

ディジタル画像において、一点から他の点へ直接直線を書くことはできません。 何故ならば、ピクセルは有限な大きさをもつため、無限小の点の集合である直線を描画することができないからです。 では、直線を直線として表現するために、直線の必要条件を考える。 始点と終点が正確である。表示される直線の明るさが一定であることである。 この二つの条件が挙げられます。 始点と終点を正確にすることは難しいですが、ある程度はピクセルの区間の細くすることによって(解像度を上げる)近似できます。

Bresenhamのアルゴリズム

直線をラスタ化する方法として、直線を示す微分方程式の解をとくディジタル.ディファレンシャルアナライザ(DDA)という手法があります。しかし、この方法では、方向依存性が強く、端点の精度が悪いです。

そこで、もう一つのブレゼンハム(Bresenham)のアルゴリズムをご紹介しましょう。 じつは、こちらのアルゴリズムのほうがDDAと比べ概念的は簡単なものです。(どちらも難しいものではありませんが...) 直線の傾きに応じてx,yの値を1単位ずつ増加させます。そこで、プロットされた点とy軸方向の上下に存在する格子点との距離を比較します。近い方を採用して通る点として採用します。このアルゴリズムのいいところは、プロットされた点と採用された格子点の距離がそののまま誤差になりますが、実際の座標であるプロットされた点が上下に存在する格子点の中点に達するまで誤差と中点から格子点に達するまではおおよそおなじくらいかかります。誤差の和が最小となるように打ち消しあってくれます。ラスタ表現のデータを用いているため、端点が大きくズレることもないです。