libsixelによるSixel Graphicsへの変換処理について #SIXEL

はじめに
　Sixel Graphicsは，DEC VT240にまで遡る太古の画像表示手段ですが，近年再び端末エミュレータ界隈の一部で注目を集めつつあるようです。
　しかし，同時に256色までしか表示できなかったり，フォーマットの仕様に癖があり効率的なシーケンスを生成するのに工夫が必要であったりと扱いにくい面もあります。
　libsixel (http://github.com/saitoha/libsixel) は，256色という制約の中で欠かすことのできない高機能な減色処理に対応するとともに，非常に効率のよいシーケンスを生成する変換エンジンを搭載していることから，Sixel Graphicsを利用する上で無くてはならないものとなっています。
　本稿では，libsixelに実装されているSixel Graphicsへの変換処理方法について概説したいと思います。
Sixel Graphicsのフォーマットについて
　仕様の詳細は，http://www.vt100.net/docs/vt3xx-gp/chapter14.html 辺りを参照してください。
　頭に入れておく必要のある事項は次の4点です。

(1)　縦6×横1ドットごとに，どのドットに色を塗るかを1バイトの文字で表現します。

(2)　最大256色のパレットから'#パレット番号'により指定した1色について，(1)の文字を使って色を塗ります(パレットの色は，パレット番号に続けて';2;R;G;B'のようにすることで定義できます。)。
(3)　縦6ドット×画像幅を1行として色を塗っていきますが，縦6×横1ドットに(1)の文字を使って1色分塗ると，まだ塗れていないドットがあっても次の縦6×横1ドットに移動します。'$'で行の最初に戻り，'-'で次の行に移ることができます。
(4)　同じパターン(文字)を繰り返す場合は，(1)の文字の前に，'!'に続けて繰り返し回数を数字で指定することができます。'?'と組み合わせると，色を塗りたい位置への移動に利用できます。
libsixelにおけるSixel Graphicsへの変換方法
(1) 基本的な変換方法
　Sixel Graphicsで画像を表示するには，最大256個のパレットを切り替えながら縦6ピクセル単位で1色ずつ塗っていく必要があります。
　例えば，次のような画像は，どのようにSixel Graphicsに変換すればよいでしょうか。

　最も単純な方法としては，画像の左上から1ドットずつ塗っていく方法があります。ppmtosixel(Netpbm)はこの方法でSixel Graphicsへの変換を行います。

　この方法ではたった6×6ドットの画像を表わすのに85バイトも必要となります。

　折角縦6ドット分まとめて色を塗ることができるのですから，画像の左側から新しい色を見つけるたびに，縦6ドット×その色が続く幅分を塗っていけば，サイズを減らすことができそうです。

　31バイトですから，最初の方法の約3分1のサイズに減らすことができました。

　しかし，色は4色しかないのに，パレットの切り替え('#パレット番号')を6回も行っており，もう少しどうにかできそうです。
　縦6ドット×画像幅の範囲内で，1色分のパターンを塗り，行頭に戻って別の1色分のパターンを塗るという方法で，パレットの切り替えを最小限にするとどうでしょうか。

　パレットの切り替え回数が4回に減り，サイズも29バイトまで減りました。

　この場合，3回行頭に戻って色を塗っていますが，上図をよく見ると2つ目のパターンと4つ目のパターンは重なっていないので，2つ目のパターンの色を塗った後行頭に戻らずに続けて4つ目のパターンの色を塗れば，行頭に戻る回数を1回減らせそうです。
　最終的に，libsixelでは，次のような方法でSixel Graphicsに変換しています。

　これにより，パレットの切り替えや，'$'や'!繰り返し回数?'を使った無駄な動きをできるだけ減らし，効率的なシーケンスを出力するようになっています。

　なお，上記の変換方法は，kmiya's sixel (http://nanno.dip.jp/softlib/man/rlogin/sixel.tar.gz) の実装に由来しています。

(2) 更なる最適化
　libsixelでは，Sixel Graphicsへの変換を行うに当たって，上述のとおり，元の画像を縦6ドット×画像幅の範囲内で，色ごとのパターンに分解します。
　下図のような画像の場合，左側の枠内のように分解することになります。

　ここで，黄色のパターンについて考えてみると，右側の枠内のように全てのドットを塗りつぶすようにした場合でも，茶色のパターンを重ね塗りすれば，最終的に得られる画像は同じになります。
　これを利用し，全てのドットを塗りつぶすパターンに'!繰り返し回数'を使うことにより，サイズを減らすことができます(色数が少ない画像ほど効果が大きくなります。)。
　なお，一旦全てのドットを塗りつぶすため，透過色が使えなくなるというデメリットもあります。

　この最適化方法については，libsixel-1.4.0に-E size オプションとして採用していただきました。

(3)　15ビットカラー対応
　Sixel Graphicsでは，パレットは256個しかありませんが，'#パレット番号;2;R;G;B'によりパレットを定義する際のR,G,Bはそれぞれ0～100まで指定できるため，24ビットフルカラーまではいかないものの，指定できる色数は100万色となります。
　VT340等の実機では，パレットの色を変更すると，既にそのパレットを使って塗られたドットの色も変わってしまいますが，近年Sixel Graphicsに対応した端末エミュレータ(RLoginやmlterm)では，パレットの色を変更しても，既にそのパレットを使って塗られたドットの色には影響しない実装になっていることを利用し，パレットの色を逐次変更することで最大100万色を同時に表示することができます。

　libsixelでは，次のA→B…を繰り返しながら変換を続けることにより，RLoginやmlterm上で256色超の色数を同時に表示することが可能となっています。

　ただし，色数を増やしすぎると，変換後のデータサイズが大きくなってしまうこと，変換速度も遅くなることから，今のところ色数を最大32,768色までに制限しています。
　また，透過色が使えなくなる(上図のとおり内部で特殊な用途に使用するため)というデメリットもあります。

　上記方法による15ビットカラー対応についても，libsixel-1.4.0に-Iオプションとして採用していただきました。
変換結果
　libsixelに同梱されているimages/snake.jpgについて，ppmtosixelとlibsixel(img2sixel)によるSixel Graphicsへの変換結果を比べてみると次のとおりとなります。

　(1)(2)(3)については，ImageMagick 6.7.7-10のconvertによりsnake.jpgを255色に減色した後に，それぞれ(1)ppmtosixel(Netpbm 10.0)，(2)img2sixel(2014/11/20現在のdevelopブランチ)，(3)img2sixel –E sizeしたときの出力サイズの比較です(img2sixelには，減色処理を行わないようにするため-d none –Iオプションもつけています。)。
　img2sixelの出力サイズは，ppmtosixelの約3分の1となっています。
　また，-E sizeした場合は，更に約1割出力サイズが減っています。

　(4)は，15ビットカラーで(Floyd-Steinberg methodによるdiffuseもかけて)出力したものであり，パレットを何度も定義し直すことにより大幅にサイズが増えていますが，それでも255色でのppmtosixelよりも小さいサイズに留まっています。

　なお，上記のとおり変換したsixelファイルは，それぞれ
http://mlterm.sf.net/snake-ppmtosixel.six
http://mlterm.sf.net/snake-img2sixel.six
http://mlterm.sf.net/snake-img2sixel-Esize.six
http://mlterm.sf.net/snake-img2sixel-highcolor.six
のとおりです。
おわりに
　本稿は，libsixelにおける実装方法を簡単に説明したものですが，更に新しい(ひょっとしたら再発見された)アイデアがlibsixelに実装されるきっかけになれば幸いです。