画像圧縮プログラム開発日記

1 ：無名：2013/09/15(日) 23:10:03.18

誰の得にもならなさそうなガラクタを開発中
現在の使用言語はJava

アルゴリズムとしては
・縦横に繋がっている同色のピクセルを圧縮する
　いにしえのPIC形式っぽいイメージ(PICのソース見たこと無いけど)
・色コードをキャッシュして24bit直書きを減らす
　直前の色からの変化をLRUテーブルで持っているので、同じ色変化パターンで圧縮がきく
　ただしLRUテーブルの更新に時間がかかる

現状
・クソ遅い
・PNG比125%〜200%位の低圧縮率
・エンコーダだけ書いてまだデコーダ書いていない(エンコーダのバグが取りきれていない)

TODO
・デコーダを書く
・レンジコーダの導入
　圧縮時に統計を取るのでその時間がどの程度になるかも要考慮
　LRUが要らなくなるのでその分早くなる・・・かも
・PNG同様に色の差分を圧縮する
・差分参照マップの導入
　色の差分をどのピクセル(左上/上/左/無参照)から取ったかの情報を保存
　有効性は未確認
・チャネル別に圧縮する(効率次第)
・Cのライブラリを書く
　malloc()とか面倒くさいのでC++で妥協する可能性大(というか書かない可能性の方が大)

とりあえず、PNGにないフィーチャーは効果が低いからPNGに導入されなかった可能性大

124 ：◆WxHhsot03c：2013/10/13(日) 04:37:44.96

・・・くっ、もしかしてブロックソートって
同じ値が長く連続するようなデータは上手く並べ替えできないのか？

125 ：◆WxHhsot03c：2013/10/13(日) 21:41:45.57

参考にしている(というかここからコードをパクっている)のサイト
http://www.geocities.jp/m_hiroi/light/pyalgo48.html
にあるプログラムを使用して、ブロックソートの性質を調べると
・同じデータが6個以上連続するとソート結果が壊れる(普遍性は不明)
・全く法則の無いデータはソートしても無駄
という事が分かってきた

というか、そもそも、ブロックソートが上手く動作する原理は
・ある文字と、その次に現れる文字には法則性がある事を利用してデータを整理する
という事らしい
まあデータ圧縮の基本は、統計的な偏りを利用するという事だから当然の話なのだが

126 ：◆WxHhsot03c：2013/10/14(月) 03:35:26.72

ブロックソート前と後でデータの連続度を取ってみた
結論
当プログラムの出力データに対し、ブロックソートの効果は殆ど無いか逆に悪化していた
・・・・・・・・
ショーーーック

(ブロックソート自体は非常に優秀な圧縮支援アルゴリズムです、念のため)

127 ：◆WxHhsot03c：2013/10/14(月) 21:07:00.52

現状の出力データにさらに圧縮を掛けようというのが無謀な考えに思われてきた
どちらかというと出力するデータ数を削減する方向に向かうのが正しいような気がする
しかし、どうやってそんな事を実現するのか、想像がつかない・・・

128 ：◆WxHhsot03c：2013/10/15(火) 22:20:04.11

画像を色の差分に変換して、どの位色数が減るか調べてみた
結果として、自然画など数万〜数十万色の画像では、1/3〜1/7くらいにはなる事が分かった
しかし、それだけでどれ位縮むものだろうか

129 ：◆WxHhsot03c：2013/10/16(水) 21:30:14.85

行き詰ってきた・・・

130 ：◆WxHhsot03c：2013/10/17(木) 23:02:49.99

LRUテーブル参照をWyle符号化してセコく縮める
モチベーションが上がらないながらも、色差分で扱うためのコードをちまちま書く

131 ：無名：2013/10/17(木) 23:47:30.61

ガンバレ

132 ：◆WxHhsot03c：2013/10/18(金) 21:16:01.10

>>131
ありがとう

133 ：◆WxHhsot03c：2013/10/18(金) 21:17:45.88

Cプログラミング診断室を読んで普段の悪行を反省する
http://www.pro.or.jp/~fuji/mybooks/cdiag/index.html#mokuji3
だが身に付いた悪癖は油汚れのように染み付いて取れないのだった

134 ：◆WxHhsot03c：2013/10/19(土) 21:52:56.39

画像バッファクラスを、差分対応版に書き換える
エンコーダクラスとデコーダクラスは、最早構造的に寿命が来ているような気がするが、
強引に書き換えることにする

135 ：◆WxHhsot03c：2013/10/20(日) 22:07:22.36

差分バージョンを実装した
例によってバグの嵐に会う

136 ：◆WxHhsot03c：2013/10/20(日) 22:48:51.41

あからさまなバグは除去し、どうにか動くようになった
画像によっては幾分縮むようになった
しかし、圧縮率が悪化する画像もある
調べてみた結果、色情報の削減効果以上に、方向情報の増加の影響、
特に遠距離の連鎖データの増加が圧縮率の悪化を招いていることが分かった

色を差分データで扱うことで、色コードの分布がバラバラになってしまっているのだろうか
まさかこんな事になるとは思わなかった

137 ：無名：2013/10/21(月) 22:06:09.86

ぎゃんばって

138 ：◆WxHhsot03c：2013/10/21(月) 23:36:47.39

>>137
ありがとう
だがそろそろ限界が見えてきた模様

139 ：◆WxHhsot03c：2013/10/22(火) 00:00:13.53

色情報を圧縮できないかどうかを調査する
差分変換後の色情報(RGBそれぞれの差分dR、dG、dB)に対し
・値の分布
・1つ前の値との関連性(LRUテーブルの効果)
を調べた

結果は芳しいものではなく、値の分布は大体均等、
LRUテーブルに関しては3bit圏内(0〜7番)に約5%の分布、
5bit圏内(0〜31番)に約13%の分布というものだった
判別bitに1bitは必要なので、収支的に見合わない

140 ：無名：2013/10/22(火) 12:01:40.62

公開しないの?

141 ：◆WxHhsot03c：2013/10/22(火) 22:39:11.16

>>140
正直、新バージョンで確実に圧縮率が向上するわけではないので・・・
ファイル形式としても特別な旨みがあるわけでもなく、あくまで個人の研究レベルに留まっているので
でもひとまずうｐ

実行ファイル
http://yui.oopsup.com/download.php/blogban/1382448921_0.jar

ソース
http://yui.oopsup.com/download.php/blogban/1382448995_0.bz2

142 ：◆WxHhsot03c：2013/10/22(火) 22:55:46.12

連鎖とみなす範囲を-127 <= dx <= 127に限定してみた
下手に連鎖を繋げるより、制限した方が縮むというというのが何とも・・・
画像によって、以前のバージョンより圧縮率が向上したり低下したり
簡易的な判定メソッドは実装してはいるものの、色コードそのままと差分形式と
どちらが縮むのかという判定は想像以上に難しいようだ

143 ：◆WxHhsot03c：2013/10/23(水) 23:43:44.89

やべえ、何も思いつかない
PNGとWebP loselessの資料を読み返すか

144 ：◆WxHhsot03c：2013/10/23(水) 23:46:53.02

loselessじゃねえ、losslessか

145 ：無名：2013/10/24(木) 22:47:11.20

負けなしか

146 ：◆WxHhsot03c：2013/10/25(金) 02:35:27.47

負けなしどころか、ほとんど勝ってねえ

147 ：◆WxHhsot03c：2013/10/25(金) 02:41:04.34

さて、ひとまず、今の方式の限界が見えたので、ここらで一旦開発終了としたいと思います

作者のヘボさ故にバグを作りこんでは修正する毎日、ここを見てくださる方々のレスには大変励まされました
短い間でしたが、本当にありがとうございました

148 ：無名：2013/10/25(金) 11:50:40.08

おつかれ
次回も期待

149 ：無名：2013/10/25(金) 23:20:29.27

内容はわけわかめだったが情熱は伝わったぞ
お疲れさま！

150 ：無名：2013/10/28(月) 15:46:37.46

おつかれ

151 ：無名：2013/10/28(月) 17:32:03.12

乙乙！