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

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

2 ：無名：2013/09/15(日) 23:58:24.20

使用言語は

まで読んだ

3 ：無名：2013/09/16(月) 10:19:09.88

頑張れ
Macで使えるかな？

4 ：無名：2013/09/16(月) 16:39:58.88

>>3
Macでも動くとは思うが、他の画像ビューア等にプラグインするとかでは無いので
利用範囲は自作画像ビューア限定
そしてこの自作画像ビューアがまた貧弱と言う・・・

5 ：無名：2013/09/16(月) 17:19:38.46

方向コード(同じ色が下方向にどれだけ繋がっているか)の有効範囲を調査中
最初に組んだ状態では
x方向のズレ：-63〜+63まで許容(7bit)
y方向のズレ：+1〜+2まで許容(1bit)
の8bitでコーディングしていたのだが、とりあえずどの位繋がる色があるのかを調べるため
制限だけ取っ払って調査

6 ：無名：2013/09/16(月) 17:26:49.46

うーん、同色ピクセルの探索に時間が掛かっているみたいだ
この部分を何とか高速化出来れば・・・

7 ：無名：2013/09/16(月) 18:28:25.50

x方向の繋がりは、大体-32<= dx <= 31が9割位を占めているようだ
y方向は大体dy <= 2が8割超
方向コードの前に2bit付けて
1bit目：x size(0:6bit/1:11bit)
2bit目：y size(0:1bit/1:3bit)
位が適正か

9割の部分に+1bitする事になるが、新規ピクセルには最低20bit必要になるから
全体としてはサイズ減になるはず
しかし処理時間が増加すると言うジレンマ

8 ：無名：2013/09/16(月) 18:34:41.27

色コードのサイズを何とか縮小できれば・・・
現在は識別コード：1bitで
0：LRUテーブル(8bit)
1：色コード(RGB24bit)
としているが、これを最大2bitにして
0：LRUテーブル(8bit)
1：next(さらに1bit続く)
0：16bit色差分(-16 <= dR <= 31, -32 <= dG <= 31, -16 <= dB <= 31)
1：色コード(RGB24bit)
とでもするかなあ

9 ：無名：2013/09/16(月) 18:39:48.71

待てよ、それだと1bit増えて精々8bitずつ削減、良くて7bitの削減にしかならんか
12bit色差分にすれば、各色-8 <= d <= 7に出来て11bitの削減になる
この辺が落とし所か
あくまで隣接ピクセルは似た色であるという場合に限るが
(写真やイラストには有利、画面キャプチャには不利)

10 ：無名：2013/09/16(月) 22:34:44.63

425KBだったのが363KBまで縮むようになった(PNGでは257KB、BMPでは1.52MB)
1.03MBのは880KBまで縮んだ(PNGでは775KB、BMPでは1.37MB)
逆にごく小さく縮む画像はサイズが増えるようになってしまった(でもそういう時はBMPよりは圧倒的に小さくなるのでまあいいか)

そろそろ現在の方式では限界が見えてきたので、一旦デコーダを書く方向に行くか

11 ：無名：2013/09/16(月) 23:20:16.96

何となくBufferedImage.getRGB()が遅いんじゃないかと思ったが大正解だった
画像を一度int[]に全部コピーしてから圧縮するようにしたら
381秒→14秒
ありえん位高速化した

12 ：無名：2013/09/16(月) 23:51:29.02

こんなスレあったのか！
wktkwktk

13 ：無名：2013/09/17(火) 19:10:27.64

デコーダを書き始めたが、Save時とLoad時でヘッダ部の記述に統一性が無いというグダグダっぷり
Cなら構造体に詰めてsizeofで一発なのだが(パッキングには要注意だが)、Javaだといちいち数えてやらなくてはならない
ヘッダ用のクラス作るか・・・急がば回れだよなあ

14 ：無名：2013/09/17(火) 21:52:18.35

グダグダしつつなんとかヘッダ用クラスを書いてエンコーダ・デコーダのヘッダアクセス部分も書き換えた
さあデコーダ書くぞ

15 ：無名：2013/09/18(水) 17:30:19.03

ああEclipseのくそったれ！！！
指図して無いコード補完とかするんじゃねえよ！！！

16 ：無名：2013/09/18(水) 17:40:09.97

デコーダ書き終わった
さあ地獄のデバッグの始まりである

17 ：無名：2013/09/18(水) 20:13:39.25

うおおおお
デバッグ中に改良可能な部分が見つかった
せっかくだから改良してさらに泥沼へ突っ込むぜ！！！

18 ：無名：2013/09/19(木) 00:15:08.66

エンコーダとデコーダの状態のログを吐くようにして、両方を比較検討してみたら
細かいバグが出るわ出るわ

19 ：無名：2013/09/19(木) 03:25:09.06

>>15
捕完されたくないところはメモ帳を使うんや！

20 ：無名：2013/09/19(木) 20:46:38.08

いやっほおおおおおお
動いたぜええええ

21 ：無名：2013/09/19(木) 20:55:29.99

>>19
余計面倒くさいいいいいいい

22 ：無名：2013/09/19(木) 21:07:05.72

という訳で、無責任にファイルを公開

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

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

※間違っても実用しないように！！！

23 ：無名：2013/09/19(木) 21:14:28.05

とりあえず何枚かの画像はセーブしてロードできることを確認しただけなので
バグが潜んでいる可能性は大(というか確実に潜んでいると思われ)

あと、デバッグ用・調査用のコードをifでON/OFFしているだけなので
無駄なコードが多く動作がクソ遅い
CやC++のマクロが非常に恋しい

ウィンドウの位置やサイズを覚えるために、ユーザのホームディレクトリに設定ファイルを作るので
遊んだ後はその辺も削除してやると吉

ソースは実にイカれたキチガイコードで満ちているので、あまり真面目に見ない方がいいかも

あと、何に関してもすべて無保証なのでそこんとこ注意しておくれやす

24 ：無名：2013/09/19(木) 23:10:32.89

もうできたのすごいね

25 ：無名：2013/09/19(木) 23:13:47.56

うおお、謎のバグ発見
デバッグ用のコードをON/OFFする変数を変更すると画像が正常にロードされなくなる
コード部分をコメントアウトしても異常にはならないのに

26 ：無名：2013/09/19(木) 23:16:00.27

>>24
そんなに大きなプログラムじゃないしね
これがゲームとかだったら話は違ってたと思う

27 ：無名：2013/09/19(木) 23:32:39.89

あっちなみに>>25の謎のバグはうｐした実行ファイルでは出ない模様

28 ：無名：2013/09/19(木) 23:43:52.35

実質コードの内容は変更していないのにバグが出なくなった
謎過ぎる

29 ：無名：2013/09/19(木) 23:45:08.74

もしかしてメモリにエラーが有るとかじゃないよな
もしそうだったら嫌すぎる

30 ：無名：2013/09/20(金) 16:39:17.64

さて、次の段階に進もう
LRUテーブルでは思うほど圧縮できなかったので他の方法を考える
色コードを直接扱うと、どの色も1回はそのままファイルに書く必要が出てくる
それなりの画像だと、1枚に20万色くらい使ってたりするから
3Byte(24bit) * 200000 = 600000 Byte(586KB)
が色コードの記述だけで必要になる
これをPNGみたいに色の差分を扱うようにしたい

画像全体を差分色で扱うのではなく、描画色を参照する部分でだけ扱えば良さそう
RGBの各成分に分けてそれぞれ差分を取り、圧縮する
差分情報は最大9bitになるので、deflateやlzmaのような8bit単位の圧縮アルゴリズムは
相性が良くないので、ハフマン符号や算術符号の方が良さそう
というわけで算術符号系のレンジコーダを勉強することにする

31 ：無名：2013/09/20(金) 16:45:21.56

色の連鎖方向の格納データや、次の描画開始点へのオフセットも圧縮可能と思われる
これらも符号長が可変の方が向いていると思われるので、レンジコーダの使用を予定

以上の変更を行うにあたって、ファイル内のデータ配置を見直す必要が出てくる
現在は

(色コード情報1) (方向情報1) , [(方向情報1), ・・・] (次の描画開始点へのオフセット1) (色コード情報2) ・・・

という並びで配置しているが、それぞれを別のストリームに分けて

(色コード情報1) (色コード情報2) ・・・
(方向情報1) (方向情報2) ・・・
(オフセット1) (オフセット2) ・・・

という3本のストリームにした方が良いだろう

32 ：無名：2013/09/20(金) 21:42:07.66

memtest86を掛けたらエラーが・・・
すわ、初期不良か？と思いきや、刺すスロットを変えたら収まった
何かアレだがまあ良しとしよう

33 ：無名：2013/09/21(土) 17:40:38.02

ストリームを3本に分ける変更が出来た
副作用としてロード時間が早くなった
ディスクからの読み取りサイズを大きくしたのでその辺が効いてるっぽい

34 ：無名：2013/09/21(土) 17:48:26.81

↓を参考にレンジコーダの勉強中
http://www.geocities.jp/m_hiroi/light/pyalgo36.html
ただし、出現頻度が1〜数万まで分布するので、
このサイトにあるように出現確率を16bitに丸める方式では確率0になる符号語が出てしまう
出現確率を24bitにするとして、レンジが24bitではギリギリになるだろうから
レンジも31bitにするか(unsignedが扱えないのが恨めしい)
とりあえずやってみるしかない

35 ：無名：2013/09/21(土) 21:44:18.52

ああ良くわかんねええええ
自分の頭の悪さが嫌になる・・・

36 ：無名：2013/09/22(日) 21:13:05.24

ちょっとずつ分かった所をコーディングして行く
例とは仕様が違うので、その辺大丈夫かどうか検討しつつ進める
現段階で分かっている、問題になりそうな部分は出現確率のオーバフロー
一度総和を取ってから(必要であれば)正規化し、確率と総和を修正する
元々入れていた、使用色数などを調べるコードに間違いがあったのでその辺も修正する

37 ：無名：2013/09/23(月) 01:13:44.18

Javaでも数値演算はquietにラップアラウンドするのか
System.out.println(0x7FFFFFFF + 1);

-2147483648

38 ：無名：2013/09/23(月) 21:25:06.65

ちょっとずつ分かってきた
・lowはデコード時にコード列からフルに読み込むので、lowの最大値はコード長の整数倍でないといけない
・rangeの最小値は出現頻度の総和より大きくないといけない
・rangeの最小値のbit数と最大値のbit数の差は、コード長のbit数に等しくしないといけない

というわけで、
・コード長=4bit
・rangeの最小値(=許容される出現頻度の総和)=24bitの最大値+1=0x01000000
・rangeの最大値=0x10000000
でやってみることにする

参考にしたサイトではrangeを64bitにしているが、そうすると64bitの除算を使うのが気になる

39 ：無名：2013/09/23(月) 21:48:37.41

コードが増えれば増えるほど、追加/修正が重くなっていく・・・

40 ：無名：2013/09/24(火) 00:41:45.30

HashMap<Integer, Integer[]>をentryset()からtoArray()しようとしたが
引数なしのtoArray()だと、Object[]になってそこからMap.Entry<Integer, Integer[]>[]へはキャストできないし
引数ありのtoArray()はMap.Entryがインタフェースだから実体作れないしでつっかえる
素直にInteger[][]をnewしてforループでコピーするか・・・

41 ：無名：2013/09/24(火) 04:26:48.85

結局新しくクラスを作って入れることにした
配列を要素にするのもクラスインスタンスを要素にするのも同じ事だし
それなら名前を付けられる方が良い

42 ：無名：2013/09/24(火) 04:33:59.38

どうにかレンジコーダのエンコーダ側が動くようになってきた
素で圧縮が効く画像にはあまり効果が無さそうだと言う事も分かってきた
とにかく圧倒的な出現頻度の差が必要な模様
(あまり差が出ない場合は、ビット長情報＋ビット長を調整したデータ、というパターンの方が効率が良い、
特に絶対値が小さい値が出る傾向が強いデータ列の場合)
圧縮率で採用/非採用を判断してファイルに識別子を入れた方が良さそうだ

43 ：無名：2013/09/24(火) 17:40:00.16

でかい画像だとそれなりに効果がありそうなことは分かってきた
ただ、今のところファイルサイズへの影響の低い、次の描画開始点へのオフセット値で実験しているため
大した効果は出ていない(2MBのデータが1.9MBになる程度)
でかいのは色データと方向データ、特に色データが重要
(2MBのサンプル画像の内、200KBがオフセットデータ、800KBが方向データ、1MBが色データ)
だが浅く広く分布するのでレンジコーダでは全く手が出ない
どうしたもんかなあ

44 ：無名：2013/09/24(火) 18:32:22.76

方向データは画像サイズが小さい方が圧縮率が良いような感じだ
小さい画像だと30%くらい、大きい画像だと70%くらい
大きい画像になるとまたクソ重くて泣ける
やっぱり色だ、色を圧縮しない限り希望は無い

45 ：無名：2013/09/24(火) 19:00:51.32

画像によってはPNGと同等以上の圧縮率も見えてきた
(得手不得手があるのでまっとうなアルゴリズム同士であれば当然の話ではあるが)
ただクソ遅いのがなあ
やっぱりPNGは偉大だ

46 ：無名：2013/09/24(火) 23:18:36.19

メソッド引数の中でダブルクォート内にカンマ書くと、
強制的に次の引数へジャンプするeclipseのクソ動作を直す方法が見つかった

メニューの「ウィンドウ」→「設定」
「Java」→「エディター」→「コンテンツ・アシスト」の中の
チェックボックス「メソッド引数を入力し、推測された引数を表示」をOFF

47 ：無名：2013/09/25(水) 03:15:32.87

レンジコーダのデコーダの実装とローダ側の対応コードを書き終わった
テスト＆デバッグはまた明日

48 ：無名：2013/09/25(水) 19:17:35.05

デバッグを開始
予想通りバグが出る
とりあえず、セーブ側とロード側で出現頻度表の総和の値が合わない
ファイルへのデータ読み書きの順序や内容に不整合があるのかと思ったが、
一見それは無いような感じがする
重症の予感

49 ：無名：2013/09/25(水) 20:54:51.57

セーブ側とロード側でログが合わないのは、
エンコーダだけ複数回動かしててログが上書きされただけだった
バグ探しは続く

50 ：無名：2013/09/25(水) 21:03:40.72

おれはここにレスすることしかできないけども
応援してるよ

51 ：無名：2013/09/25(水) 22:22:19.26

何とかバグが取れた
レンジコーダのエンコーダ部分、lowがオーバフローした時に余計なデータを出力していたのが原因だった
距離データのレンジコーダ対応が済んだので、次は方向データと行きたい所だが
かなりソースコードが汚くなってきたのでリファクタリングしたい

52 ：無名：2013/09/25(水) 22:24:13.12

>>50
ありがとう
断片的な話ばかりで意味不明ですまん

53 ：無名：2013/09/25(水) 23:39:34.88

ここに書いてあることはワケワカメだけど
いつも見てます

54 ：無名：2013/09/25(水) 23:51:05.04

儂も

55 ：無名：2013/09/26(木) 02:22:07.40

ありがとう
励みになります

56 ：無名：2013/09/26(木) 03:03:41.65

ではちょっとアルゴリズムの解説をば

基本的な考え方として、
・同じ色は固まって存在している
・近所にあるピクセルは似た色をしている
・ある色が出た後、その次に出る色は大体決まっている
という仮定に基づいて圧縮を行う

あるピクセルに対し
・右に繋がる同色ピクセルは、一括して扱う
　(次に違う色が出てくるまでの距離を記録する)
・下にも同じ色が続く場合、同色ピクセルの内左端への相対位置を記録する
　(例えば、左に1ピクセル、下に2ピクセル、とか)
・下に続いた同色ピクセルの内、これも左端だけを記録する

違う色が出た場合
・1つ左のピクセルの色と、そのピクセルの色の組を覚えておく
・同じパターンが出た場合、色コード(24bit)そのままではなく、
　どの位前に出たかという数値(8bit)(LRUT:Least Recenly Used Table)を記録する
・上記パターンが通用しなかった場合、
　1つ左のピクセルの色と近い色(RGB各成分±31)だったら
　色の相対値(12bit)を記録する

57 ：無名：2013/09/26(木) 03:04:11.29

次の違う色までの距離は
・左から右へ1ピクセル単位での距離
・右端を超える場合は1ライン下の左端からの距離
・以下同様
極端な場合、画像が1色だけの場合は、次のピクセルへの距離は
画像の横幅×高さ
となる
これを利用して、
・距離データの累積を覚えておき、これが幅×高さに等しくなったらデータ終了
とする

以上によって、画像は以下のデータ組
・ピクセルの色
・下方向への同色の連鎖情報
・次の違う色のピクセルへの距離
の連続に変換される

色コードは上記方法によって、(8bit/12bit/24bit)に圧縮される
(ただし、どの方式かを判別するために1〜2bitの判別bitを付加)

58 ：無名：2013/09/26(木) 03:10:02.63

連鎖方向に関しては
X方向
-31 <= dx <= +31 の場合、6bit値として記録する
-1055 (-1024 - 31) <= dx <= -32 or +32 <= dx <= +1055 (1023 + 32) の場合、11bit値として記録する
連鎖終了はコード値-32(6bit)を充てる
Y方向
1 <= dy <= 2 の場合、1bit値として記録する
3 <= dy <= 10の場合、3bit値として記録する
(ただしXYそれぞれbit数判別のために各1bitずつ判別bitを付加)
という方式でデータ量を削減する

ピクセル距離に関しては
offset <= 4 の場合、2bit値として記録する(距離0は存在しないため、
2bit値:0〜3を1〜4と読み替える)
5 <= offset <= 20 (15 + 5) の場合、4bit
21 <= offset <= 276 (255 + 21) の場合、8bit
277 <= offset <= 4372 (4095 + 277) の場合、12bit
offset <= 65535の場合、16bit
offset <= 4294967295 の場合、32bit
それ以上の場合、64bit
(ただしbit数判別のために、2〜4bitの判別bitを付加)
という方式でデータ量を削減する

59 ：無名：2013/09/26(木) 03:10:37.10

同じ色は近くに存在する(dx、dyの絶対値が小さくなる傾向が高い)、
そうでない場合は、次のピクセルへの距離は小さくなる場合が多い、
という事実によりデータ量を削減する

ただし、上記の方式では、小さい値が圧倒的に多い場合
判別bitによるデータ増加の影響が大きくなり、圧縮率が低下するという問題が有り
これを改善するために上記方式に替えてレンジコーダを導入しようと思った次第
ただ、レンジコーダは計算がやや重く、ただでさえ同色ピクセルの探査回数がかさんで
処理が重めなのに加えて、さらなる負荷の増加を招いてしまっているという状態

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

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