サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
災害への備え
www2.starcat.ne.jp/~fussy
で示すことができるので、上式に適当な値を代入して座標を計算することによって円弧を描くことが可能となります。 しかし、この方法では実数演算が必要で処理が重くなるので、整数演算のみを使って円を描くアルゴリズムを検討していきます。 まず、円の8分の1(45度分)を描画することに限定して考えます。下図のように原点(0,0)を中心とする半径Rの8分円を点(R,0)から時計回りに描いていく場合円弧は必ず45°よりも急な傾きの曲線となるため、描画途中ある点P(X,Y)を描いた後次に描くべき点は
前回、コンピュータ上での数値計算処理方法について紹介しました。二進数を使った計算を考えた場合、全ての計算を論理演算から構築することが可能です。今回はこの考え方を応用して、多倍長整数の演算について紹介したいと思います。 1) 多倍長整数の表現 「位取り記数法」を使って、任意の数を基数として数を表現することができることを前回説明しました。通常利用されている「10進法」で25という数が記述されているとき、これを16進法で表すと19、2進法で表すと11001になります。 基数として利用できる数に制限はないので、もっと大きな数を基数に使うこともできます。例えば10進法で表された12345678という数を1000進法で表せば(12)(345)(678)と記述することができます。ここで()内の数は"一桁の数"を表していることになりますが、1000個もの記号を用意するわけにもいかないので、中身は10進法
本章から、データ暗号作成方法とその解読方法について紹介したいと思います 紀元前から人々は、重要な機密文書を他人に知られることなく正当な受信者だけに渡すため、様々な手段を用いてきました。当然そのような重要な秘密を暴こうと、暗号を解読する手段も開発されてきたため、暗号の作成方法とその解読手段は常にお互い進化しつづけてきたわけです。新しく強力な暗号が作られたと思ったら、それを解読するための手段が発見され、一度解読法が見つかってしまえばその暗号はもはや役に立たなくなってしまいます。現在用いられている暗号についても、いつ破られてしまうかは分かりません。そしていったん破られてしまえば、それはもはや使うことができなくなるわけです。 この章では、まず紀元前の頃から第一次大戦前までに活躍した暗号作成方法と、その解読方法について紹介したいと思います。 1) 秘密通信の方法 情報を他人に知られることなく正当な
前章で、多重解像度解析の内容についてHaarの関数を使って説明しましたが、今回はこれを一般化したDaubechiesによるウェーブレット関数を紹介したいと思います。Haarの関数は不連続となることから、自然画の圧縮には適さないと言われています。Daubechiesの関数ではこの不連続が解消されており、Haarの関数よりも自然画の処理に適しているそうです。 前にも述べたように、ウェーブレット変換を行ってもデータ量は変化しません。JPEGの場合と同じく、変換後には量子化と符号化を行う必要があります。この章では、量子化の方法についても説明をしたいと思います。 1) ツースケール関係(two-scale relation) Haarのスケーリング関数を使った多重解像度解析処理では、二つの矩形を平均化して一つの矩形にすることで、解像度を一つ落とす(レベルを一つあげる)処理を行っていました。この時の
#define PALET_MAX 256 /* パレットコードの最大数 */ #define HUFFMAN_TREE_MAX ( PALET_MAX * 2 - 1 ) /* ハフマン木の節の最大数 */ #define RED( color ) ( ( ( color ) >> 16 ) & 0xFF ) #define GREEN( color ) ( ( ( color ) >> 8 ) & 0xFF ) #define BLUE( color ) ( ( color ) & 0xFF ) /* ハフマン木構造体 */ typedef struct Huffman_Tree { unsigned char rgb; unsigned int count; struct Huffman_Tree *left; struct Huffman_Tree *right; } Huffma
テキストとパターンの中で、両側に下線が引かれた文字は一致したもの、パターンのみに下線が引かれた文字は不一致を検出した個所を示します。 それでは早速サンプルを示したいと思います。 int strlen( s ) char *s; { int i; for ( i = 0 ; s[i] != '\0' ; i++ ); return( i ); } int strncmp( s1, s2, len ) char *s1,*s2; int len; { int i; int cmpret = 0; for ( i = 0 ; i < len ; i++ ) if ( ( cmpret = s1[i] - s2[i] ) != 0 ) break; return( cmpret ); } char *strstr( Text, Pattern ) char *Text, *Pattern; { i
検索アルゴリズム (2)2分検索/木検索 検索アルゴリズムの2回目は2分検索と木検索です。 1)2分検索 前回紹介した線形検索は、n個のデータ列に対して平均n/2回の比較操作が必要となるため、処理速度はnに比例していると言えます。これに対して、2分検索(Binary Search)ではn個のデータ列に対して最悪でもlog2n回の比較回数で済むので、線形検索に対してかなりの性能向上が期待できます。 ただし、2分検索を行うためにはデータ列がソートされている必要があり、その分線形検索に比べて前処理のための時間が必要となります。また、1回の比較処理にかかる時間も線形検索より長くなるため、データ数が少ない場合は2分検索の方がかえって遅くなることも考えられます。 2分検索では、まずデータ列の中央にある要素(以下mとします)と検索対象データ(以下xとします)を比較し、一致しなければxとmの大小関係より
Range Coder復号化処理による数直線の変化は、以下のようになります。 復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。 処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログ
この章から新たに、画像圧縮アルゴリズムの紹介を開始します。まずは、もっとも古典的でシンプルなランレングス(連長)法について説明します。 1) ランレングス法(連長法) FAXで送られる画像のように、白色と黒色のみで構成された画像(2値画像)や、色の変化が少ないアニメなどの画像は、隣り合ったピクセルの色の変化が少なく、値が連続して出現していることがわかります。この冗長性を利用して、「同じ色が連続する長さ」を符号化する方法がランレングス(連長)法です。 例えば、次のような 10 x 10 ピクセルの2値画像の場合 □■□□■□□■□□ □■■□□■□■□□ □■■■□□■■□□ □■■■■□□■□□ □■■■■■□■□□ □■■■■■■■□□ □■■■■□□■□□ □■■■□□■■□□ □■■□□■■■□□ □■□□■■■■□□ 2値画像は必ず白と黒が交互に現れるため、はじめの色がどちらなのか
検索アルゴリズム (5)正規表現 -1- 前回までは、固定文字列の照合アルゴリズムを紹介しましたが、この章では特定の「パターン」に合致する文字列を検索する処理、いわゆる「正規表現」(regular expression)を取り上げたいと思います。正規表現は、grep,sed,awk,perlなど、様々なツール、言語上でサポートされているので、たいていの方はその恩恵(?)に預かっているでしょう。 1)正規表現の定義 正規表現は、1つ以上の空白でない「枝」(branch)からなり、各「枝」は'|'で区切られます。正規表現は、「枝」の中のいずれかに一致した場合に「一致した」ことになるので、'|'は"論理和"の役割を持つといえます。
画像圧縮アルゴリズム (2)減色・パレット化 この章では、色に着目した画像変換を利用した圧縮方法について説明したいと思います。 前の章でも少し説明をしましたが、ディスプレイ上でカラー画像を表す時の色成分としては、現在RGBが一般的に使用されています。RGBでは、光の三原色であるR(赤)G(緑)B(青)で構成される表色系で、それぞれの色成分が持つ値(強さ)の組合わせによって、様々なカラーを作り出すことが可能になります。他にも、表色系の例としてYMCやYOQ、YUVなどが挙げられます。これらについては、以前ペイントルーチンの章で説明をしましたので、こちらをご覧下さい。 各色成分の強さは値の強弱で表されます。例えば赤色を表したい場合は、赤成分のみを最大値にして他の成分を0にすればいいわけです。HTMLドキュメントでは背景やフォントの色をRGB表色系で定義することができるので、参考までに色コード
検索アルゴリズム (1)線形探索/ハッシュ法 今回からはまた、画像処理関係のアルゴリズムから離れて、探索・検索アルゴリズムの紹介を行いたいと思います。もう1つ候補として画像圧縮法があったのですが、こちらはかなりの分量になりそう&まだ文献などのチェックが終わってないので、先に軽めのやつから片付けてしまいます。 1)線形探索 あるデータ配列から特定の要素を検索する場合、まず誰でも思いつくのはデータの先頭から1つずつ要素を比較していくやり方だと思います(書類の山から目的のものを探すとき、一番上から順に見ていくのと同じですね)。この方法は線形探索(linear search)と呼ばれています。 アルゴリズムとしては非常に単純なものなので、早速サンプルを示したいと思います。 int *LinearSearch( DataStart, DataEnd, Data ) int *DataStart, *
この章では、JPEG2000フォーマットで圧縮アルゴリズムとして採用されたことで、一躍有名になったウェーブレット変換(Wavelet Transform)について取り上げたいと思います。 JPEG2000では画像圧縮アルゴリズムとして採用されましたが、元々はフーリエ変換の応用形として、データ解析の利用を目的に考案された手法であり、その内容も多岐に渡っています。全てを説明するのは量的にも、自分の理解度から見ても不可能なため、ここでは離散ウェーブレット変換と、それを用いた解析手法である多重解像度解析を中心に紹介をしたいと思います。 1) フーリエ変換とウェーブレット変換 あるデータや関数の特性を分析する手法としてよく知られたものに、フーリエ変換(Foueier Transform)があります。フーリエ変換は、周期を持った任意の時間関数を正弦波と余弦波の和で表すことができることを利用して、時系
多角形の塗りつぶし (1)ソリッド・スキャン・コンバージョン この章からはまた図形描画に関するアルゴリズムへ戻り、多角形の塗りつぶしについて紹介します。「塗りつぶし」といっても以前紹介したペイント・ルーチンではなくて、「中身の詰まった多角形を描く」アルゴリズムであるソリッド・スキャン・コンバージョンを使います。 1)ソリッド・スキャン・コンバージョンのアルゴリズム ソリッド・スキャン・コンバージョン(Solid Scan Conversion)のアルゴリズムは、図形の輪郭とスキャン・ライン(走査線 ; 画面の横1ライン)の交点を求め、求めた各点の間を水平線分で結んでいく処理を各スキャン・ラインについて繰り返すことで実現できます(図1)。あるスキャンラインに対して交点がいくつも存在する場合は、x座標の小さいものから順に2点ずつペアを作り、その2点間を結んでいきます。このため、図形の内側にでき
検索アルゴリズム (4)文字列の検索 -2- 前章に引き続き文字列照合(string matching)のアルゴリズムから、この章ではBoyer-Moore(BM)法を紹介したいと思います。このアルゴリズムは、実用上最速な文字列照合アルゴリズムとして文字列検索ツールやエディタで使用されているようです。 1)BM法 BoyerとMoore、また両者とは別にGosperが考案したBoyer-Moore(BM)法の最大の特徴は、パターンを末尾側から逆方向に比較するということです。 テキストとパターンの先頭をそろえた後、今までのアルゴリズムではパターン先頭とテキスト先頭を比較するのですが、BM法ではパターン末尾(先頭からm文字目)の文字と、テキストのm文字目の文字を比較します。もし一致していたら注目文字を1つ前にずらし、末尾側から逆方向に比較していきます。もし不一致が検出されたら、不一致を引き起
この章では、現在のデータ圧縮・画像圧縮などで広く用いられているLZ法について説明します。 前章までで説明したハフマン圧縮では、個々のデータをハフマン符号に変換して圧縮を試みるというものでしたが、LZ法では、あるデータ列に着目して、それが以前に出現したことがあるかをチェックし、すでに出現したことがあるのならば、そのデータ列を示す何らかの符号(当然、データ列より短くなければなりません)に置き換える処理を行うことにより、圧縮を行っています。 LZ法には、いくつかの種類があり、その種類によってさらに名称が変わります。しかし、その違いは符号化の方法だけで、処理の内容については全て同じです。 LZ法は、Abraham LempelとJacob Zivの二人による共同開発によって、1977年に誕生しました。正式名称はZiv-Lempel codingですが、間違ってLZ法として紹介したことから、現在の
ペイントルーチン (1)シードフィルアルゴリズム ここでは、シード・フィル(seed fill)による閉領域の塗り潰し、いわゆるペイントルーチンについて取り上げたいと思います。 シードフィルアルゴリズムは、以下のような流れになります。
画像圧縮アルゴリズム (6) JPEG法(1) この章では、現在最も使用率の高い画像圧縮技術である(と思われる)JPEG(Joint Photographic Expert Group)法について説明したいと思います。 自然画のように、階調数が多くて色コードのパターンもより複雑になってしまうと、エントロピーが大きくなり、今まで説明したような符号化圧縮にも限界があります。そこで、今までのような可逆的な圧縮(復号した結果が元の画像と完全に一致するような圧縮法)をやめて、非可逆圧縮法を利用するアプローチが取られるようになりました。その中で誕生したのがJPEG圧縮法になります。 JPEGとはこの画像圧縮法の標準化を行うために、CCIC(Common Component for Image Communication)とISO IEC/JTC1/SC/WG1の二つのグループがジョイントして1986
になるので、x = 0, 1, ... 5 を代入して y = 0, 0.6, ... 3 を求め、その結果を順にプロットしていけばよいことになります(当然、各点の座標値は整数でなければならないため、実際には計算値の小数部を四捨五入して (0,0),(1,1),...(5,3) をプロットします)。 しかし、傾きが急な線分 (m > 1) の場合、Y座標の増分が1より大きくなって、とびとびにプロットされる事になるため、「X座標を変化させつつY座標を求める」のではなく「Y座標を変化させつつX座標を求める」ことになります。 ここで 0≦m<1の場合のみを考えます。この時、直線の傾きは右上がりで 45°より小さくなります。 上の例では各座標毎にxを代入してyを求めていましたが、xが1増えるとyはmずつ増加する事に着目すると、
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか? ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
このページを最初にブックマークしてみませんか?
『Fussy's HOMEPAGE』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く