LOCO-I予測+LZMAで画像を可逆圧縮してみた

　画像を可逆圧縮する方法にはいくつかありますが、多くの場合は(1)ある画素の輝度値を周りの画素から予測する→(2)予測誤差を符号化する という2ステップから成り立っています。今回は、(1)にLOCO-I予測を使い、(2)にLZMAを使って実際に可逆圧縮を行ってみました。

原理

　まず、LOCO-I予測に関してはwikipediaの以下の記事を参考にしました。
Lossless JPEG - Wikipedia
　LOCO-I予測は上・左・左上の3つの画素の値を元に当画素の値を予測するものです。具体的な式はwikipediaの記事にあります。なぜ上・左・左上の三箇所なのかというと、復号するときに左上から順番に復号していくので、当画素を復号しようとする時点では右や下の画素値は未知だからです。
　LZMAのアルゴリズムに関しては英語版のwikipediaに細かい解説があります。
Lempel–Ziv–Markov chain algorithm - Wikipedia, the free encyclopedia
　LZMAはzipと同じ辞書式圧縮ですが、エントロピー符号化にハフマン符号化でなくRange Coderを使っているなどの理由から、zipより高い圧縮率を期待できます。ちなみにPNGはzipと同じハフマン符号化を使っています。(というか、zipそのものを使っています)

方法

　下記のプログラムを使ってテスト画像をLOCO-I予測し、得たビットマップ画像を7zというフリーソフトでLZMA圧縮しました。テスト画像には　ご注文はうさぎですか？　ホワイトデー特製PC用壁紙(1920x1200)の5人分を試してみました。
スペシャル -TVアニメ「ご注文はうさぎですか？」公式サイト-

結果

名前	PNG (MB)	JP2 (MB)	提案手法 (MB)
ココア	3.82	2.29	2.50
チノ	3.92	2.38	2.57
リゼ	4.00	2.38	2.61
シャロ	3.93	2.38	2.58
千夜	3.78	2.25	2.42

　2列目の"PNG"は、元画像をMSペイントで開きPNGで保存した場合の大きさです。PNGはソフトによって圧縮率が変わります。3列目の"JP2"は、GIMPを使って元画像をJPEG2000 losslessに変換したときの大きさです。
　変換後の画像はこんな感じになります。(縮小してあります)

考察

　全ての画像の圧縮率でJPEG2000のほうが優れています。LOCO-I予測はJPEG-LSというJPEG2000より古い規格で使われていた方法ですし、エントロピー符号化に関してもJPEG2000はより洗練された方法を使っています。

ソースコード

　C++とOpenCVで書きました。

#include <opencv2/core/core.hpp>
#include <opencv2/opencv.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <stdlib.h>
#include <iostream>

using namespace cv;

int encode()
{
	//画像を読み込み、このプログラムに対応している形式の画像かどうか確認する。
	IplImage* img = cvLoadImage("test.png", CV_LOAD_IMAGE_ANYCOLOR | CV_LOAD_IMAGE_ANYDEPTH);
	if (img == NULL)return 0;
	if (img->depth != IPL_DEPTH_8S && img->nChannels != 3)
	{
		cvReleaseImage(&img);
		return 0;
	}

	//LOCO-I予測を行い、残差画像をdestに格納する。
	unsigned char* dest = (unsigned char*)calloc(img->widthStep * img->height * 3, sizeof(unsigned char));
	for (int y = 0; y < img->height; y++)for (int x = 0; x < img->width * 3; x++)//各ピクセルの各色について
	{
		//左、上、左上の画素について、それがあるならその輝度値、ないならゼロを得る。
		const int left = (x < 3) ? 0 : (unsigned char)img->imageData[y * img->widthStep + (x - 3)];
		const int upper = (y == 0) ? 0 : (unsigned char)img->imageData[(y - 1) * img->widthStep + x];
		const int upperleft = (x < 3 || y == 0) ? 0 : (unsigned char)img->imageData[(y - 1) * img->widthStep + (x - 3)];

		//LOCO-I予測を行い、predictに格納する。
		int predict;
		if (max(left, upper) <= upperleft)predict = min(left, upper);
		else if (upperleft <= min(left, upper))predict = max(left, upper);
		else predict = left + upper - upperleft;

		//実際の画素値との差を求めてdestに格納する。
		predict -= (unsigned char)img->imageData[y * img->widthStep + x];
		dest[y * img->widthStep + x] = (unsigned char)((predict + 256) % 256);
	}

	//destの中身をimgに全部コピーする。見やすいように、全単射の写像をかませる。
	for (int y = 0; y < img->height; y++)for (int x = 0; x < img->width * 3; x++)
	{
		const unsigned char a = dest[y * img->widthStep + x];
		img->imageData[y * img->widthStep + x] = a < 128 ? 255 - 2 * a : 2 * a - 256;
	}

	//ウィンドウを生成して画像を表示する。
	cvNamedWindow("test_loco_i", CV_WINDOW_AUTOSIZE);
	cvShowImage("test_loco_i", img);

	//何かのキーが押されたら保存して終了。
	cvWaitKey(0);
	int param[] = { CV_IMWRITE_PNG_COMPRESSION, 9 };
	cvSaveImage("test_loco_i.png", img, param);
	cvSaveImage("test_loco_i.bmp", img);
	cvDestroyWindow("test_loco_i");
	cvReleaseImage(&img);
	free(dest);

	return 0;
}
int decode()
{
	//画像を読み込み、このプログラムに対応している形式の画像かどうか確認する。
	IplImage* img = cvLoadImage("test_loco_i.png", CV_LOAD_IMAGE_ANYCOLOR | CV_LOAD_IMAGE_ANYDEPTH);
	if (img == NULL)return 0;
	if (img->depth != IPL_DEPTH_8S && img->nChannels != 3)
	{
		cvReleaseImage(&img);
		return 0;
	}

	//LOCO-I予測を行い、元画像を復元する。
	for (int y = 0; y < img->height; y++)for (int x = 0; x < img->width * 3; x++)//各ピクセルの各色について
	{
		//左、上、左上の画素について、それがあるならその輝度値、ないならゼロを得る。
		const int left = (x < 3) ? 0 : (unsigned char)img->imageData[y * img->widthStep + (x - 3)];
		const int upper = (y == 0) ? 0 : (unsigned char)img->imageData[(y - 1) * img->widthStep + x];
		const int upperleft = (x < 3 || y == 0) ? 0 : (unsigned char)img->imageData[(y - 1) * img->widthStep + (x - 3)];

		//LOCO-I予測を行い、predictに格納する。
		int predict;
		if (max(left, upper) <= upperleft)predict = min(left, upper);
		else if (upperleft <= min(left, upper))predict = max(left, upper);
		else predict = left + upper - upperleft;

		//かませてあった写像の逆変換を行い、予測誤差を求める。
		int e = (unsigned char)img->imageData[y * img->widthStep + x];
		e = e % 2 ? (255 - e) / 2 : (256 + e) / 2;

		//実際の画素値を求めてimgを更新する。
		predict -= e;
		img->imageData[y * img->widthStep + x] = (unsigned char)((predict + 256) % 256);
	}

	//ウィンドウを生成して画像を表示する。
	cvNamedWindow("test_decode", CV_WINDOW_AUTOSIZE);
	cvShowImage("test_decode", img);

	//何かのキーが押されたら終了。
	cvWaitKey(0);
	cvDestroyWindow("test_decode");
	cvReleaseImage(&img);

	return 0;
}
int main()
{
	////予測誤差を濃淡に変換する写像が全単射であることを確認する。
	//int f[256] = { 0 };
	//for (int a = 0; a < 256; a++)
	//{
	//	int e = a < 128 ? 255 - 2 * a : 2 * a - 256;
	//	int r = e % 2 ? (255 - e) / 2 : (256 + e) / 2;
	//	assert(a == r);
	//	assert(f[e]++ == 0);
	//}

	encode();
	decode();

	return 0;
}