テーマ
ポケコンでもE500シリーズのＯＰＡＳやG800シリーズのＳＡＳ（by Toshiさん）などの登場によりBASICでもグラフィックを多用したゲーム等が作れるようになりました。しかし、データは無圧縮のGPRINT形式（縦８ドットで２バイト消費）が基本となっておりメモリの無駄や入力の手間がかかるなどの問題があり、ポケコン用の画像圧縮規格が欲しいと思っている人も多いことでしょう。
《参考》
圧縮法入門 http://www.ingnet.or.jp/~kojif/mu/comp/index.htm
ということで今回考えていくのは次の２点です。
|
（１）ポケコンに最適な画像データ圧縮・解凍ルーチンを考える （２）ポケコン用標準圧縮規格を作る
|
御茶目菜子式 画像圧縮
|
（１）GPRINT形式のデータを上位・下位の４ビットを分離する （２）文字の組み合わせで最も多いものを調べそれを別のコードに置き換える 置き換える前の文字は辞書に入れておく （３）置き換えができなくなるまで（２）を繰り返す。 （４）連続する部分がある場合それを連続を表すコードに置き換える 以上で圧縮が終了 |
《解説》
このアルゴリズムでは「簡易辞書＋ランレングス法」を使用しており、一定の文字の組み合わせが多く出現したり、同じ文字（または同じ文字の組み合わせ）が連続する場合にはかなりの圧縮率が期待できます。
しかし、パターンにばらつきが多い場合は圧縮率が低くなる、サイズが小さい画像では辞書の効果が生かせない、辞書のデータだけでも相当の量になるなどの多くの問題をかかえており、まだ改良を加えないといけないでしょう。
ちなみに辞書は２バイト固定式で数は４５までです。（解凍プログラムの肥大化を防ぐための措置）
|
２４×２４ドット サンプル画像（そもそもさん提供）
F8FEFFFF3F1721070800100F8B88889023FF03FFFFFF7FFF 010709FFFE015D1EA0800003600E6B0F67F0FEFFE7EFF07F 000000033FFFA254BC58F030B858281410FF3F101729C000 |
以下の記事はおちゃめくらぶの掲示板に投稿されたのを引用したものです。掲載に関して不都合なことがありましたら、ご遠慮なく申し出てください。
また、引き続きポケコン用の画像圧縮・解凍についてのアルゴリズム、プログラム募集中です！何かあれば掲示板にお願いします！
|
投稿者 ＮＯ１さん（2001年1月25日）
lz77はなにかと組み合わせると有効かも まぁ、、御茶目菜子陛下方式に辞書データが無い感じ＋可変長辞書シュ”詳しくはＹＡＨＯＯで検索して調べるにょ！”では逃げなので分かりづらい説明にょ、、（間違ってるかも） ”３４５９３４ＡＦ９３”というＧＰＲＩＮＴデータなら”３４５９！＜４、２＞ＡＦ！＜５、２＞”という感じで圧縮かもじゃて（実際には！＜４、２＞を”Ｋ”とかにあらかじめ割り当て） この場合、４や５が何文字前に戻るかを表現し２がコピーする文字数にょ、、でも６４文字程度を辞書に使えるとして！＜８、８＞程度しか、戻れないからのー解凍は比較的単純＆早いはずシュ このさい、、ＲＬＥとかと組み合わせるか、、 |
|
投稿者 そもそもさん（2001年1月25日）
この方法は縦８ドット 横７ドットに適しています まずデータを・・
例FF00FF00FF00FF
これの各列のドットの一番上を取っていきます |
|
投稿者 ＮＯ１さん（2001年1月26日）
そこで実際には１３２文字、辞書に使うことにしたにょ、、 これで標準で＜２２，６＞にょ、、 さらに１６文字を使って拡張タグすることにより最大で（つまり、２バイトで表現）＜１７６，１２＞まで可能シュ Ｇ８５０のかなりの文字コードを使用じゃのー（１３２＋１６＋１６＝１６４文字使用） しかしlz77は特に高圧縮だと圧縮に何十分かかりそうな気がする、、(爆)特に拡張すると、、、 |
|
投稿者 ＮＯ１さん（2001年1月26日）
確実に６６％に圧縮できる方式がいちよう決定にょ、、（６ドット＝１バイト） 使用アスキーコード４８〜１１１
欠点＆長所
まず、ＧＰＲＩＮＴデータの長さは３の倍数じゃなきゃ駄目にょ（ならない場合は終わりに０を追加）
ＩＦ ２ ＡＮＤ ８ で１の場合は１文字目に３２を足す |
|
投稿者 ＮＯ１さん（2001年1月27日）
圧縮する前にＧＰＲＩＮＴデータを変化させることにより（一種の画像処理）格段に圧縮できる可能性があるにょ、、 まぁ、フィルタ無しの方が圧縮できる場合もあるので判定する必要があるけど
●フィルタの長所と欠点
例、前のデータとの比較フィルタ
例 偶数奇数交換フィルタ |
|
投稿者 ＮＯ１さん（2001年1月28日）
新たな圧縮法にょ 今度は高速性重視かつまずまず高圧縮？ とはいえ、８ビット＝１ビットは無理だったのでは？という説もあるのじゃが、、、、 Ｇ８５０はアスキーコードの２５６うち、２１２は割り当てられているので、、、、 つまり文字コードが割り当てられている部分は２文字を圧縮し（例外として”０”〜”Ｆ”の部分は圧縮しない） それ以外は、生のＧＰＲＩＮＴデータのままにょ！
●長所短所
REM Ｇ８５０の文字コードに最適化しています REM まだバグがあるかも、、、 CLS DIM S$(0)*255 REM S$(0)はGPRINTデータ用の文字変数です DIM E$(0)*255 REM E$(0)は圧縮されたデータ用の文字変数です DIM K$(0)*255 REM K$(0)は解凍されたGPRINTデータ用の文字変数です INPUT S$(0) REM S$(0)にGPRINTデータが入ります FOR I=1 TO LEN(S$(0)) B=ASC(MID$(S$(0),I,1))-48 C=ASC(MID$(S$(0),I+1,1))-48 D=(B+(B>9)*7)*16+(C+(C>9)*7) REM 変数Dに文字コードが入ります IF ((D>32 AND D<48) OR (D>57 AND D<65) OR (D>70 AND D<127) OR (D>128 AND D<160) OR (D>160 AND D<248)) AND(I<>LEN(S$(0))) THEN REM このＩＦ文が圧縮メインです REM 文字コードで機種依存しているでしょう？ REM 他の文字コードにわりあてる場合はここを変更 E$(0)=E$(0)+CHR$(D) I=I+1 ELSE E$(0)=E$(0)+MID$(S$(0),I,1) REM 無圧縮になるけどコピー ENDIF NEXT PRINT E$(0) REM ここまでが圧縮プログラム REM ここからが解凍プログラム FOR I=1 TO LEN(E$(0)) B=ASC(MID$(E$(0),I,1)) IF (B>47 AND B<58) OR (B>64 AND B<71) THEN REM 無圧縮データなのか圧縮データなのかを判定 K$(0)=K$(0)+CHR$(B) ELSE K$(0)=K$(0)+HEX$(B) ENDIF PRINT K$(0) END |
《注》「全桁に同じ値を足すフィルタ」とは・・・
このプログラムではキー入力入力ができない0xh、1xhのコード（大半が圧縮できない3xh、4xh、Fxhも同様）できないが多発すると圧縮率が下がるという短所があります。従って、全部の桁に一定の値を足しそういう値（０、１、３、４、Ｆ）が出にくくすることで平均圧縮率を高めることが可能になります。
（例） ６を足す場合： Ｆh＋６h＝１５h → ５h
圧縮を１６通りやれば最も良いものが分かるのですが、頻度を調べそれを元に判断すれば、１６回も圧縮しなくてもおよその目安を立てることができます。
|
投稿者 Toshiさん（2001年1月29日）
とりあえず簡単に説明します。 文字コードの中でキー入力できる文字の部分のみをキャラクタに置き換えて圧縮するのですが、使える文字は連続していません。 途中にスペースや入力できない文字もあります。 俺が考えたアルゴリズムではその空いた部分を無理矢理詰めて使います。＃はCHR$35ですが、０として扱います。 圧縮するときは値が１２８未満と１２８以上にわけた場合で、多い方を圧縮します。多い方を圧縮する場合は＃は０ではなくて１２８となります。それを区別するためにデータのはじめに[!]を入れます。 その後は１２８未満か１２８以上で多い方を圧縮していき、連続した同じデータがある場合は[!]を入れてその直後に個数をあらわすア〜ンを使いその後に圧縮するデータを入れます。アを２個とし、ンまでを使い４６個分を圧縮できるようにしています。 |
ポケコン用の圧縮・解凍プログラムやそのアルゴリズムを掲載しているＨＰをお持ちの人はぜひご連絡下さい！
ここからリンクを貼ります！！
ということで、グラフィックを多用したゲームや画像処理プログラムを作る人があればこれらの圧縮・解凍規格をぜひ利用してみてください！！より多くの人が使用すれば、それが事実上の標準規格となるでしょう（笑）
現在、準備中・・・（笑）