ポケコン用画像圧縮・解凍ソフト　（E500/G800シリーズ用）

ＯＧＥ（Ochame's Graphic Encoder） BASIC edition


　このプログラムは「第１回ＰＡＣ（ポケコンアルゴリズム協議会）」のテーマ「ポケコン用画像圧縮規格の考案」を元に考案されました。

　シャープのポケコンで通常使用されているGPRINT形式の画像データですが、縦８ドットを２桁の16進数（２バイト）で表記しているので、メモリ効率が良いとは言えません。
　そこで、このデータを圧縮する試みをしてみました。
《このソフト（ＯＧＥ　BASIC edition）の特長》
  • データ圧縮・解凍アルゴリズムが単純であるためにリストが短くてすむ。
  • リストが短い割りには高圧縮（一般的な画像で圧縮率60〜70％程度）
  • データに使用される文字がアルファベット大文字、数字、カナのみなのでデータの視認性にすぐれ入力の負担を軽減。
  • １バイト単位のデータが圧縮が可能なので画像だけでなくマシン語データ（ダンプリストではなく16進数表記のBASICのリスト）なども圧縮可能
  • 拡張性にすぐれいろいろな付加機能を追加可能。
《補足》「データの視認性」について
　これは、データを作る側ではなく、入力する側の立場になればすぐに分かることです。例えば、少しくらい入力する量が減ってもアルファベット大文字、小文字に加え、各種記号類が乱立するデータを入力したいでしょうか？しかし、これは主観的な面も含みますので、別に使用されている文字種が多くても気にならず、少しでもデータが短い方がいいという人もいるかもしれないでしょう。

《注意》


ポケコン用画像圧縮・解凍ソフト　ＯＧＥ


《圧縮アルゴリズムについて》

圧縮アルゴリズム

  1. 画像データの中から０〜Ｆの頻度を調べ上位４つを順に辞書に格納する。
  2. データから１文字ずつ取り出し、辞書に使われているのと同じ文字ならば次の文字と合わせて１文字に置き換える（２バイトを１バイトに圧縮）
    そうでない場合はそのまま（無圧縮）にする
  3. データの最後まで 2.を繰り返す

《補足》
2.の「１文字に置き換える」という方法について

　「Ｇ」〜「Ｚ」を変換文字コード　０〜１９
　「ア」〜「ワ」を変換文字コード２０〜６３と仮定する
　　辞書データ（４バイト）を先頭から辞書データ０〜３とする

圧縮されるデータが辞書データのどれかと一致する場合「辞書データのコード×１６＋次の文字（10進数に直したもの）」となる変換文字コードの文字（０〜６３）に置き換える

（例）
辞書データが「Ｆ２３５」の場合に画像データ「２４」を圧縮する。「２」が辞書データ１に一致するので、「１×１６＋４＝２０」となり、変換文字コード２０に相当する「ア」と置き換える。

《圧縮率》
理論上：50.0％〜87.5％（辞書４バイトを除いた場合）

圧縮率が最低になるのは0〜Fが１回ずつ出現し、かつ、「0123」が連続して出現（順番は問わない）した場合です。

（例）
「012345678ABCDEF」を圧縮した場合、「Hタ456789ABCDEF」となる（16バイトが14バイトに圧縮）

しかし、これは特殊なケースであり一般的な画像では圧縮率が80％以上になることはほとんどないでしょう。

《プログラムリスト》

圧縮プログラム

【E500シリーズ用】
10 DIM P(15),Q(15)
20 L=LEN D$:FOR I=0TO 15:P(I)=0,Q(I)=I:NEXT :FOR I=1TO L:H=I:GOSUB *MID:P(M)=P(M)+1:NEXT
30 FOR J=14TO 0STEP -1:FOR I=J TO 0STEP -1:IF P(I)<P(I+1)LET P=P(I),P(I)=P(I+1),P(I+1)=P,Q=Q(I),Q(I)=Q(I+1),Q(I+1)=Q
40 NEXT :NEXT :J$="":FOR I=0TO 3:J$=J$+HEX$ Q(I):NEXT :CLS :PRINT J$:E$=J$
50 FOR I=1TO L:H=I+1:GOSUB *MID:Y=M,H=I:GOSUB *MID:X=M
60 FOR J=0TO 3:IF I<L AND A$=MID$ (J$,J+1,1)LET Z=J*16+Y,A$=CHR$ (Z+71-(Z>19)*86),I=I+1ELSE NEXT
70 E$=E$+A$:PRINT A$;:NEXT I :END
80 *MID A$=MID$ (D$,H,1),M=VAL ("&"+A$):RETURN
【G800シリーズ用】
10 DIM P(15),Q(15),D$(1)*254
20 L=LEN D$(0):FOR I=0TO 15:P(I)=0,Q(I)=I:NEXT :FOR I=1TO L:H=I:GOSUB *MID:P(M)=P(M)+1:NEXT
30 FOR J=14TO 0STEP -1:FOR I=J TO 0STEP -1:IF P(I)<P(I+1)LET P=P(I),P(I)=P(I+1),P(I+1)=P,Q=Q(I),Q(I)=Q(I+1),Q(I+1)=Q
40 NEXT :NEXT :J$="":FOR I=0TO 3:J$=J$+CHR$ (Q(I)+48-(Q(I)>9)*7):NEXT :CLS :PRINT J$:D$(1)=J$
50 FOR I=1TO L:H=I+1:GOSUB *MID:Y=M,H=I:GOSUB *MID:X=M
60 FOR J=0TO 3:IF I<L AND A$=MID$ (J$,J+1,1)LET Z=J*16+Y,A$=CHR$ (Z+71-(Z>19)*86),I=I+1:GOTO 80
70 NEXT
80 D$(1)=D$(1)+A$:PRINT A$;:NEXT I :END
90 *MID A$=MID$ (D$(0),H,1),M=ASC A$,M=M+(M>9)*8-48:RETURN
【使用方法】
（G800シリーズ用を使用の場合は以下の説明中、Ｄ＄をD$(0)、Ｅ＄をD$(1)としてお読み下さい）

変数Ｄ＄に画像データを入れるとＥ＄に圧縮されたデータが入ります。
なお、２ヵ所使用しているPRINT文は圧縮過程が分かるように表示しているだけなので不要なら入力の必要はありません。
G800シリーズでの動作確認はしておりませんので、よろしかったら報告お願いします！

解凍プログラム

【E500シリーズ用】
10 E$="",J$=LEFT$ (D$,4):FOR I=5TO LEN D$:A$=MID$ (D$,I,1),B=ASC A$:IF B>70LET C=B-55+(B>176)*86,A$=MID$ (J$,C/16,1)+HEX$ (C AND 15)
20 E$=E$+A$:NEXT
【G800シリーズ用】
10 DIM D$(1)*254
20 D$(1)="":J$=LEFT$ (D$(0),4):FOR I=5TO LEN D$(0),A$=MID$ (D$(0),I,1),B=ASC A$:IF B>70LET C=B-55+(B>176)*86,H=C AND 15,A$=MID$ (J$,C/16,1)+CHR$ (H+48-(H>9)*7)
30 D$(1)=D$(1)+A$:NEXT

【使用方法】
（G800シリーズ用を使用の場合は以下の説明中、Ｄ＄をD$(0)、Ｅ＄をD$(1)としてお読み下さい）

変数Ｄ＄に圧縮されたデータを入れるとＥ＄に元のデータが入ります。
G800シリーズでの動作確認はしておりませんので、よろしかったら報告お願いします！

《ＦＡＱ》

このアルゴリズムが高圧縮の理由

　このプログラムではGPRINTのデータを辞書にヒットするデータのみ２桁の文字を１桁の別の文字に置き換えることで圧縮していますが、00〜FFまで256種類ある並びを４文字分の辞書で賄う（４バイト辞書で前作の64バイト分の性能！）ということをしています。
　しかし、調べているのが１桁ごとなので実際は0〜Fの１６通りの中の４文字分となり、辞書にヒットする確率の単純計算（以下「推定ヒット率」と略）は25％となりそうです。
　では、０〜Ｆの並びが完全にランダムで一様の確率で発生しているという仮定のものに推定ヒット率を考えていきます。
　次のデータはこれから圧縮されるデータの一部分です。

　　１Ｆ３

　ここで多くの皆さんが「Ｆ」がヒットする確率は25％であると考えるかもしれません。しかし、手前の「１」がヒットした場合は「Ｆ」と１まとめにされるので実質「Ｆ」がヒットしたのと同じことになります。
　そうなると「Ｆ」はヒットするのは、25+25で50％となると考える人もいるかもしれませんが、それも違います。
　というのも「１」がヒットしてしまったら「Ｆ」も無くなってしまうので、単純に加算が出来ないのです。
　つまり、「『１』がヒットする確率＋『１』がヒットしない、かつ、『Ｆ』がヒットする確率」が実質的に「Ｆ」がヒットする確率に等しいのです。
ということで「0.25＋0.75*0.25=0.4375」となり「Ｆ」の推定ヒット率は約44％（厳密に言えばデータの最初と最後の文字にはこの計算は当てはまらないのですが、おおざっぱな「推定」ということなので細かい計算は省略します）となります。
　この場合の推定圧縮率を計算してみると、約44％の確率で２バイトが１バイトになるので、約22％のデータ削減ができ圧縮率は約78％（辞書の４バイトを除いた場合）と推定されます。
　ここまで書くとたいしたことはないと思いがちですが、あくまでこれは完全にランダムでデータの割合が完全に一様な場合です。
　RND命令を使ってランダムなデータを作成した場合でも、全データに含まれる文字のうちの辞書に含まれる文字が入っている割合は30％程度（推定ヒット率51％→推定圧縮率74％）であり、人の手によって描かれた画像では50〜70％（推定ヒット率75％〜91％→推定圧縮率62％〜54％）となります。
　ただし、人の手によって描かれた画像の場合は、データに偏りが見られることが多く、辞書に含まれる文字が一部に集中する可能性もあり、実際の圧縮率は推定圧縮率と比べ数％（概ね3〜5％）落ちてしまうことがあります。しかし、そういう場合は可変式辞書やランレングス法が有効なので、デラックス版（「拡張性について」参照）では逆に高圧縮できる可能性があります。
　でも、一般的な画像ならば、このベーシック版でも60〜70％に圧縮可能なので大きな画像（32*32ドットを越えるもの）でなければ、圧縮率の心配はあまりないでしょう。

辞書が４バイトの理由

　一般的に考えると圧縮率を高めるためには辞書の量を増やした方が効果的なのですが、なぜ４バイトなのかを書いておきます。
　このプログラムでは２つの文字を１つの別の文字に置き換えることでデータ圧縮を実現していますが、元のデータに使われているのが０〜Ｆの１６種類のため辞書を１バイト増やすごとに１６文字分の文字コードが必要になります。キーボードから入力できる文字種には限りがあり（E500シリーズでは158文字程度）、さらに圧縮データに使用する文字種を増やせばデータの視認性の低下（このプログラムでは辞書のデータの中で頻度が高いものをアルファベットに充てることで、より視認性を高めている）や拡張性の低下（複数のアルゴリズムの組み合わせが困難）などを引き起こしてしまいます。
　さらに、たとえほんの数バイトの辞書とはいえ小さい画像（概ね16*16ドット以下）では実質的な圧縮率の低下につながってしまいます。16＊16ドットの画像では元のデータが64バイトのため辞書を１バイト増やすごとに実質圧縮率が約1.7％低下してしまいます。
　逆に４バイトよりも少なくした場合を考えてみると、頻度が高いものを辞書データから外すことになるので、小さい画像を除き圧縮率の大きな低下（辞書データが減る量よりも圧縮できる量の低下の方が大きい）につながってしまいます。
　これらのことを総合的に判断し、一般に良く使われるであろうサイズ（12*8〜24*24ドット）を想定して辞書のサイズを４バイトに固定としました。これ以上のサイズでもデラックス版を使えば４バイトの辞書でも十分に高圧縮が可能です。

拡張性について

　このプログラムでは文字コードに空きがありそれを有効に使うことでさまざまな圧縮アルゴリズムを追加することができます。それらの追加機能をつけたものをここでは「デラックス版」と呼びます。
　デラックス版では、ランレングス法や可変式辞書の追加を予定しています。
　ベーシック版では幾ら同じデータが連続していても、理論上50％までしか圧縮できませんが、ランレングス法を用いることにより数倍〜数１０倍に圧縮が可能となります。なお、ランレングス法についてここでは詳しくは述べません。
　また、可変式辞書を使用によりデータ全体としては文字の頻度に偏りがなくても部分的に偏っている場合にかなりの圧縮が可能です。それは、一時的に辞書の内容を変えることによりヒット率の大幅な向上が期待できるからです。
　ちなみにランレングス法と可変式辞書は併用が可能なのでさらなる圧縮が可能となります。
　これらのことを追加したデラックス版の圧縮データはベーシック版のものと比べ視認性の低下が予想されますが、圧縮データはベーシック版のものをベースとしているので、全体的な視認性の低下が起こることはありません。また、使用された部分は確実にベーシック版よりもデータ圧縮がされているのでそれとトレードオフになっていると思えば問題ないでしょう（笑）。したがって、常にデラックス版を使うのではなくベーシック版と使い分ける（圧縮率を取るか、解凍プログラムの短さや圧縮データの分かりやすさを取るか）ということも考えた方がよいかもしれません。
　なお、デラックス版で圧縮したデータはベーシック版で解凍することは出来ませんが、デラックス版では両方解凍が可能になります。
　それから、今後期待される動画圧縮の基本圧縮アルゴリズムとしてもベーシック版は活用可能となるために将来性（？）も有望です。

RETURN inserted by FC2 system