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

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に導入されなかった可能性大

60 ：無名：2013/09/26(木) 20:54:40.97

よくわからないけど応援してます
dx, dy ってなんだろう

61 ：無名：2013/09/26(木) 21:44:56.60

>>60
delta x、delta yっす
現在位置からみた、下に見つかった同色ピクセルの相対位置

62 ：無名：2013/09/26(木) 21:58:05.52

とりあえず以前にも増して汚くなってきたソースコードをマシにする作業を続ける事にする

63 ：無名：2013/09/27(金) 18:51:20.85

リファクタリング作業もこれはこれで手間がかかる
ついでに気になるところを修正しつつ進める(これがいかんのだが)

動作テストしていたらOutOfMemoryで例外が
まさかと思いつつデバッグしたら、単に古い形式のファイルを間違って開こうとしただけだった
ああびっくりした

64 ：無名：2013/09/28(土) 01:03:19.91

ちょっと手を入れてはバグを追加→必死で修正の繰り返し
かなり疲れた

65 ：無名：2013/09/28(土) 01:34:42.79

謎のファイルサイズ増加が・・・
と思ったら、既存ファイルを開いた後、RandomAccessFile.setLength()していなかっただけだった

66 ：無名：2013/09/28(土) 19:17:44.79

今日もコードのリファクタリング
ちょっとずつ次の改良を考える
縦方向の連鎖だが、下方向に検索して、それ以上見つからなかったら終了としていた所を
折り返して上方向に検索することで連鎖度を高められないか
圧縮率の向上はたぶんわずかで、圧縮時間はかなり増加の予想
上方向に検索する時に、既に圧縮済みかどうか見たら、若干軽減できるかなあ

67 ：無名：2013/09/28(土) 19:25:41.07

圧縮対象の画像を何とかして単純化出来れば良いのだが
色を差分で扱ったら多少は単純化するのだろうか
差分化＋RGB各チャネル別で圧縮すれば、色情報は多分かなり圧縮されるとは思う
しかしそれをやると、方向データ＆距離データが約3倍になるので
どれだけ差分値が同じになるピクセルが固まるかによる

68 ：無名：2013/09/28(土) 19:49:08.38

わかるような
わからないような

69 ：無名：2013/09/28(土) 20:49:12.01

とりあえずは現在の色情報ストリームをRGB別に分けて
前の色との差分をエンコードするというのが手軽だな

現在
・LRUテーブル参照/12bit差分/24bit直接の3種類のデータを1本のストリームに格納

改良案
・24bit直接のデータを、RGB各チャネルに分け、3本のストリームに格納
・それぞれのストリーム内で、前のデータとの差分を取り、それを圧縮する

70 ：無名：2013/09/28(土) 21:01:06.02

>>68
説明ではなくただのつぶやきなので仕方がない
すまぬ

71 ：無名：2013/09/28(土) 23:43:40.41

うああ、バグ発見
ごくたまに正確にデコードされないピクセルが出る
とりあえず圧縮の方から調査・・・

72 ：無名：2013/09/29(日) 03:20:41.26

圧縮のバグだった
最初のバージョンから乗ってたバグだった
未処理のピクセルを探すメソッドで、画像の横幅が32で割り切れない時に、
検索開始位置がぴったり32の倍数で、かつ画像の右端までの距離が32未満の時に
距離の計算を誤るという現象だった
原因としては1箇所、<=とすべき部分が<になっていたため

バグは出尽くしただろうと思っていたところから出ると、かなり途方に暮れる
今日はこれで終わり

73 ：無名：2013/09/29(日) 17:46:50.88

ちまちまと小改良を施す
出現頻度テーブルを昇順にソートするようにして、値を差分で記録するようにする
差分は大体小さな値に収まるので、可変長のデータにして少しでもサイズを縮める

74 ：無名：2013/09/29(日) 19:06:29.76

きたああああああ
遂にPNGより縮むようになったぞ

しかしまだ複雑な画像では負ける
そして圧縮がクソ遅い

75 ：無名：2013/09/30(月) 02:52:34.41

描画開始点とその1つ前の色との差分を調査してみた
色数の多い画像ではRGB各チャネル毎の差分＋レンジコーダで効果が出そうな感じ
画像全体を色の差分で扱っても、チャネル毎に圧縮すればそれなりに縮むかも知れない

76 ：無名：2013/09/30(月) 18:56:03.22

差分＋レンジコーダを実装した
しかし、思ったほど縮まない(1MBが900KBになる程度)
どうしたものか

77 ：無名：2013/09/30(月) 21:06:12.08

さらに詳細に色の差分の出現傾向を調査中・・・

78 ：無名：2013/09/30(月) 22:30:50.67

うーん、だめだ
単に描画開始点の色コードを差分化しただけじゃ、大して縮まる見込みはない
画像全体を色の差分で扱う方向しか、可能性の有りそうな方法がない
しかしそれは結構な工事になる
しばらくはよくアルゴリズムを考えねばなるまい

79 ：無名：2013/09/30(月) 23:18:40.92

一応コテ付けたらどうだい？
別にどっちでもいいが

80 ：◆WxHhsot03c：2013/10/01(火) 04:41:15.19

じゃあ鳥だけでもつける事にする

いつも使用している数枚の画像以外の画像を試しにセーブ＆ロードしたらバグが・・・
これも最初のバージョンからあったローダ側の未発見のバグ
下方向へ連続するピクセルを描画し終わった後、次の描画開始位置を読み込んで
そこまでの移動の間、未描画のピクセルを塗って行く処理(y0 → y1)
・処理開始ラスタ (y0)
・途中のラスタ (y0 + 1 〜 y1 - 1)
・最後のラスタ (y1)
と処理する中で、途中のラスタ処理の開始ラスタが処理開始ラスタと同じ所から開始していた
(処理開始ラスタ+1から処理しなければならない所)
なんでこんなバグが今まで発覚しなかったのか謎

81 ：◆WxHhsot03c：2013/10/01(火) 19:42:43.47

画像の取り扱いを変える前に、圧縮を高速化する事にする
以下高速化案

1ピクセル毎に最大21110ピクセル(dx:-1055〜1055、dy:1〜10より2111×10)検索していたのを軽減する
具体的には、画像を左上から走査して行って
・見つけた色をキーにHashMapに放り込む
・その色の座標からごく近傍にある同色を検索して、座標のLinkedListを作る
・そのLinkedListを開始ラスタ・終了ラスタ毎に分けて、Listに放り込む(Listのインデックス==ラスタ)
・そのListを上記HashMapの値とする
格納するオブジェクトは、
・HashMap<Integer, ArrayList<LinkedList<LinkedList<Point>>>>　(開始ラスタ)
・HashMap<Integer, LinkedList<LinkedList<LinkedList<Point>>>> (終了ラスタ)
の2つとなる
終了側のLinkedList<LinkedList<LinkedList<Point>>は11要素(dy:+10ラスタまで探すので)あればよい

次々放り込む一方で、
・1ラスタスキャンし終わったら、10ラスタ前の情報を取り出す(終了ラスタの方のLinkedList)
・既に格納してあるArrayListの中から、連続するものを探し出す(開始ラスタの方のArrayList)
・見つかったら、そのLinkedList<Point>を連結し、開始ラスタ側の要素を削除する
・1ラスタ分処理したら、10ラスタ前のLinkedListを削除する

うーん複雑
まともに動くんかなあ

82 ：◆WxHhsot03c：2013/10/01(火) 20:23:30.26

最後にソートすることを考えると
ArrayList<HashMap<Integer, LinkedList<LinkedList<Point>>>>
LinkedList<HashMap<Integer, LinkedList<LinkedList<Point>>>>
の方がいいか
それにしてもメモリ食いそうな方式だ

83 ：◆WxHhsot03c：2013/10/01(火) 23:12:08.91

いかんな、下方向の連続ピクセルを探したら、その下端に当たるラスタに相当する格納領域が必要だ
終了ラスタの方も、ArrayList<HashMap<Integer, LinkedList<LinkedList<Point>>>>にするべきか
あと、格納する時は、後で左側のピクセルから順に取り出したいから
既に格納してある要素をチェックしなければならないな

ArrayList<HashMap<Integer, LinkedList<LinkedList<Point>>>> f_endPoint = new ...(省略)

として、挿入したいListを nowList 、そのの最終要素のx座標(連続ピクセルの最後)を xe 、y座標を ye とすると

LinkedList<LinkedList<Point>> pointList = f_endPoint.get(ye).get(color);
boolean inserted = false;
for (int i = 0; i < pointList.size(); ++i) {
　int endX = pointList.get(i).getLast().x;
　if (xe < endX) {
　　pointList.add(i, nowList);
　　inserted = true;
　}
}
if (!inserted) {
　pointList.add(nowList);
}

こんな所か

84 ：◆WxHhsot03c：2013/10/02(水) 21:38:52.89

高速化コードの続きを書く作業を続ける
前のコードと構造が結構変わるので新しいクラスを作る
名前は安直にCryopictSaver2

85 ：◆WxHhsot03c：2013/10/02(水) 23:50:34.09

LinkedList<Point>をソートする必要が出たので、配列を作ろうと
LinkedList<Point>[] conListArray = new LinkedList<Point>[arraySize];
と書いたらコンパイルエラー
どうも総称型の配列は作れないらしい
仕方ないのでググると、Collections.sort()なるものがある
という訳で、ArrrayList<LinkedList<Point>>に修正して解決

86 ：◆WxHhsot03c：2013/10/03(木) 20:50:26.17

ひとまずコードは書き終わった
これから地獄のデバッグが始まる

87 ：◆WxHhsot03c：2013/10/03(木) 22:59:36.59

予想通りバグの荒らしに苦しめられる
だが今のところアルゴリズムに根本的な誤りはない模様
1箇所を除いて大体バグは取れた
後は、ラスタ毎にバラバラに作成した連続ピクセル情報を、結合する部分のバグを取る作業にかかることにする

88 ：◆WxHhsot03c：2013/10/04(金) 05:00:52.33

やっと解決した・・・
連鎖データを連結する時に、開始ラスタ側だけ削除して、終了ラスタ側を削除し忘れてたのが原因だった
ゾンビ連鎖データが残ってて、そこにさらに連鎖データを連結するもんだからデータが失われていた

連結アルゴリズムのまずさから圧縮率が低下しているが、チューニングは明日以降にする
やっと寝られる

89 ：◆WxHhsot03c：2013/10/04(金) 14:37:55.73

効果を確認する
圧縮に92秒かかっていたファイルが25秒になった
まあまあか、でもメモリ使用量の増加から考えるとどうか・・・
さらにメモリを消費して高速化する道があるので、高速化してみることにする

圧縮率は幾分低下した
連続するピクセルを見つけるアルゴリズムが手抜きなせいだろう
こちらも手を入れることにする

90 ：◆WxHhsot03c：2013/10/04(金) 15:13:58.28

高速化できると思って手を加えたら、却って遅くなったので元に戻した
数百要素のソートを繰り返しても案外大丈夫なんだなあ(最初からある程度整列しているせいか)
そしてインスタンスの生成はコストが非常に高い
実感した

91 ：◆WxHhsot03c：2013/10/04(金) 20:48:34.80

しかし、これだけインスタンス生成のコストが高いという事は、
旧アルゴリズムが遅いのも調査用コードが予想以上に時間を食ってる可能性がある

92 ：◆WxHhsot03c：2013/10/04(金) 21:55:18.53

予想通り、調査用コードがかなりの負荷になっている模様
連続ピクセルを探すアルゴリズムにも改良を加えたが、いまいち旧アルゴリズムに追いつき切れていない
なるべく近いピクセルを探す、とかこだわらず、とにかく繋がるピクセルを探すほうが漏れが少ないようだ

93 ：◆WxHhsot03c：2013/10/04(金) 22:02:53.72

旧コードから調査用コードを外してみたが、やはり遅い
アルゴリズムを変更する意義はある程度はある模様

ちょっとはモチベーションを保てそうだ

94 ：◆WxHhsot03c：2013/10/05(土) 01:25:27.81

連続ピクセルを探すアルゴリズムにさらに改良を加えた
連続ピクセルの連結処理には二段階あって
1. 近くにあるものを探して連結する
2. 遠くにあるものを探して連結する
という処理を従来は1つのループの中で順に呼び出していたのだが、
これを独立した2つのループに分けたところ、圧縮率はさらに向上した
結果として、複雑な画像でもPNGよりわずかに有利となった
ようやくここまで辿り着いた
感慨深い

95 ：◆WxHhsot03c：2013/10/05(土) 18:46:16.47

うわ、何も弄った覚えがないのにまたバグが

96 ：◆WxHhsot03c：2013/10/05(土) 20:55:14.05

ただ単にバグを見落としてただけみたいだった
原因が良く分からないので、場当たり的な修正でとりあえず難を逃れる
圧縮率は再びPNGより不利に
ぬか喜びであった

97 ：無名：2013/10/05(土) 21:12:20.34

俺もこんなふうにプログラム作れるようになりたかったな…
応援してるぜ

98 ：◆WxHhsot03c：2013/10/05(土) 22:34:26.56

>>97
応援ありがとう

時間とデバッグに耐える精神力があればいつでも挑戦可能だが
時間確保が難しいか・・・

99 ：◆WxHhsot03c：2013/10/05(土) 22:39:28.55

バグの原因が分かった
2つの連続ピクセル情報を連結する時、
・吸収される側の、開始位置を格納したオブジェクトから情報を削除する
・吸収される側の、終了位置を格納したオブジェクトから情報を削除する
まではやっていたのだが、
・吸収する側の、終了位置が連結処理によって変更される
という点を見逃していた
よって、
・吸収する側の、吸収前の終了位置を格納したオブジェクトから情報を削除する
・吸収する側の、吸収後の終了位置をしかるべきオブジェクトに格納する
という処理を追加

100 ：◆WxHhsot03c：2013/10/05(土) 22:44:24.09

このバグ修正によって、さらに圧縮率が改善したが、
まだ手持ちの一番複雑な画像ではPNGに負ける
そろそろ限界だろうか

101 ：◆WxHhsot03c：2013/10/06(日) 03:29:46.25

とりあえず新バージョンをUPしてみた

http://yui.oopsup.com/download.php/blogban/1380997393_0.jar

ソースコード
http://yui.oopsup.com/download.php/blogban/1380997508_0.bz2

なお、前回のバージョンで圧縮したファイルとの互換性は無いので注意
前も書いたけど、決して実用しないでください！！！！

102 ：無名：2013/10/06(日) 12:49:28.22

ベンチとってみた　元画像：http://yui.oopsup.com/download.php/blogban/1381031209_0.xz
お糸地獄.bmp　　　 2,359,350
お糸地獄.cro　　　　1,553,640
お糸地獄.jls　　　　 1,063,358
お糸地獄.png　　　　991,342
お糸地獄.p2　　　　 778,565
お糸地獄.jp2　　 　 683,694
お糸地獄.webp　　　666,346

103 ：◆WxHhsot03c：2013/10/06(日) 21:26:28.00

>>102
検証ありがとう
やはり自然画は弱いか
webpは凄いな

やはりRGBチャネル別に分けて圧縮かけるしかないな
それしか思いつかない

104 ：◆WxHhsot03c：2013/10/06(日) 21:41:20.05

それにしてもPIC2とは懐かしい
ググってたら、自分の使っている符号化方式がWyle符号だと知った
後でソースのコメントを修正しなくては

105 ：◆WxHhsot03c：2013/10/07(月) 02:34:49.68

Irfanview4.36をインストールして手持ちのテスト画像をwebpで圧縮してみたが
圧縮率凄過ぎワロタ
何をしたらこんなに縮むんだよ

106 ：◆WxHhsot03c：2013/10/07(月) 03:24:55.74

アイデアらしきものはいくつか思いつきはするのだが、
実際に実装できるのかというと難しかったりする(又は、実装できても殆どor全く効果がない)
現状でさらに出来そうな事は
・さらにピクセルの連鎖を探す(方向コードの増加と引き換えに色コード/距離コードを減少させることが出来る。効果は不明)
・方向コードにブロックソートをかけてMTF-2→レンジコーダのコンボ

ブロックソートはソートアルゴリズムに特有の工夫があるとの事なので、その辺また勉強しなければならない
図書館からWin32 APIの本借りてきたけど読む暇が取れるのだろうか・・・

107 ：◆WxHhsot03c：2013/10/07(月) 18:27:41.21

さらなる改良のためにコードを改造中
方向コードからこれまでの-1056 <= dx <= 1056、1 <= dy <=10という制限を取り払って
それぞれ±32bit値の限界までに拡張することにする

108 ：◆WxHhsot03c：2013/10/08(火) 02:46:21.30

取っても取ってもバグが出る

109 ：◆WxHhsot03c：2013/10/08(火) 04:08:23.73

また初期バージョンから取り逃していたバグが見つかる
ビット単位でデータを書き込んだ後、バッファに取っておく分のデータのマスクが間違っていた
負数を書き込むと上位ビットが残ったままになりデータ化けが発生

とりあえず動く状態に復帰する
連鎖を総ざらえするクレイジーアルゴリズムにより実行速度が劇的に低下
そして圧縮率の低下
だがブロックソートを実装すればその分以上に取り返せるはず

110 ：◆WxHhsot03c：2013/10/08(火) 21:05:56.76

ふと思いついた
方向データはレンジコーダで圧縮するので、その値が出るのが1回だけとか少ない場合には
符号長が長くなって圧縮率が低下する
そこで、2回圧縮処理をするようにして、1回目の圧縮で方向データの統計を取り
2回目では、方向データの値が重複しないものについては連鎖として扱わない事にすれば
圧縮率が改善するかもしれない
処理時間が2倍＋αになるけど

後で検討するために書き記しておこう

111 ：◆WxHhsot03c：2013/10/08(火) 22:01:12.80

サンプルデータの1つから、連鎖総ざらえ方式への変更前と後で
方向データが20万個(dx、dy各10万個)増加して、色データが190KB減少した
総ファイルサイズは70KBの増加し、概算で
(190 + 70) * 1000 / 100000 = 2.6byte = 20.8bit
方向データ1つにつき20.8bit増加している

一方、連鎖1つに必ず付随するデータが、現状では
・色コードが14bit程度
・連鎖終了コードが3bit程度
・距離コードが2bit程度
の合計19bit

(dx, dy)で19bitを超えるようなデータは圧縮しないほうがマシという事になる

現状では、わざわざデータを総ざらえする手間と時間をかけた挙句、
ファイルサイズは増加するという結果になってしまっている

112 ：◆WxHhsot03c：2013/10/08(火) 22:04:01.51

ただ、ある程度複雑な画像では、総ざらえ以前では見つけられなかったような所でも
同じ値が固まって出てきているので、ブロックソート＋MTF法によってリカバーされる可能性は十分ある

113 ：◆WxHhsot03c：2013/10/09(水) 04:04:43.44

>>110のアイデアを試しに実装してみた
結論から言うと、効果があるのは色データのコストが小さいデータ
(＝色数の少ないデータ)に限られることが分かった
まあ、当たり前の結果が出ただけの話なのだが
この辺のバランスは結構タイトなようで、色データとしては圧縮が効くが、
方向データとしてはおいしくないというようなデータを上手く探し出してやらないと効果が出ない模様
あまり苦労に見合う結果は得られそうに無い

114 ：◆WxHhsot03c：2013/10/09(水) 19:04:15.85

今日はブロックソートの勉強を進める
ソートの効率化にsuffix arrayの効率的な作成アルゴリズムが使用できるとの事
suffix arrayの作成には分布数えソート、マルチキークイックソートとそれらを利用した
Larsson-Sadakane法が有効らしい
分布数えソートに関しては、レンジコーダの実装で出現頻度表を作成するコードがあるので
それを流用すれば良さそう(ただし、正規化を行う場合があるので場合分けが必要)

suffix arrayやブロックソートのような共有部分を持つデータのソートは
大まかな大小関係をまず確定して、再帰的に正確な大小関係を求めていく事ができる
この方法にクイックソートが相性が良いらしい

115 ：◆WxHhsot03c：2013/10/10(木) 21:15:43.99

ちょこちょことコードを書きつつ理解を進めていっているが
正直かなりわけわかめ

ブロックソートをかける時は、一度に処理するデータサイズを決めておかないと
えらいことになるので、とりあえず何も考えず512K個としておく
処理の流れとしては
1. 全データからユニークなものを抜き出してMTF法用テーブルを作成する
2. 総データ数を記録する
3. 512K個のデータにブロックソートをかける
4. ソート前と同じ並びのデータのインデックスを記録する
5. MTF法でデータを変換する
6. 全データを処理するまで3に戻って繰り返す
7. レンジコーダのために出現頻度テーブルを作成する
8. レンジコーダでデータを圧縮する

ファイルに記録すべきデータは
・MTF法用テーブル
・データのインデックス値の配列
・出現頻度テーブル
・レンジコーダで圧縮したデータ列
あと、後々のために、ブロックソートの処理単位(512K)も記録した方が良いのかな？

116 ：◆WxHhsot03c：2013/10/11(金) 21:16:11.46

殆どコピペでコードを書き進める
それだけだとあんまりなので、理解した限りの事をコメントに書き込む
コピペではあまりモチベーションが上がらないのと、
理解できない部分について考え込んだりするので極めて進行が遅くなる

117 ：◆WxHhsot03c：2013/10/11(金) 21:23:42.15

今やってる部分と関係ない事ばかり思いつく
色コードに関してだが、LRUテーブルを各色に持たせる現在方式に加えて
通常(？)仕様の単なるLRUテーブル(前の色コードに対して、という状態を持たせず、
単に何回前に出たか、という情報だけの奴)との選択制にする事を思いつく
どの方式にするかをある程度事前に選択する事も考えたほうが良いかもしれない
現在のLRUテーブルが256エントリなので、色数が数万色とかだと
メモリ使用量がバカにならない上効果も無いに等しいので

118 ：◆WxHhsot03c：2013/10/11(金) 21:26:38.33

まあ、いずれにせよ画像の特性をあらかじめ調べるのはやる事になるであろう
自然画とアニメ調画像とで処理を分けるべきだと思うので
ブロックソートとLRUテーブル辺りの事が片付いたら、いよいよ自然画用アルゴリズムをやる事になるだろう

119 ：◆WxHhsot03c：2013/10/11(金) 23:46:41.79

うーん、闇雲に同色ピクセルを連結していくのではなく、
圧縮が可能なのかどうかを判断しながら連結する方法がないものか

120 ：◆WxHhsot03c：2013/10/12(土) 00:39:00.48

連鎖ピクセルの終点を格納するコードの誤りを正したら、圧縮率が低下した・・・
すなわち、最も近い連鎖をちゃんと探せていない事が明らかになったという事・・・

121 ：◆WxHhsot03c：2013/10/12(土) 16:25:32.60

誤りだと思った事自体が誤りだった(わざわざ間違った方へ修正してた)
最も近い連鎖を探すようにコードに手を入れてみたが、
コードが醜くかつ遅くなった割に見返りは小さかった

122 ：◆WxHhsot03c：2013/10/12(土) 23:10:10.30

どうにかブロックソートのエンコード側が動くようになった
だがまだMTF法とか実装しなければならない

123 ：◆WxHhsot03c：2013/10/13(日) 01:09:45.41

出来たと思いきや、壮絶な勘違いにより後戻り
もう何がなんだか

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

乙乙！