CodeIQ 小飼弾さんからの出題 「百聞は一見に如かず~文字列処理+画像処理=?」の解答

だいぶ前の話ですが去年の年末にブログ404 Blog Not Foundで有名な小飼弾さんからgihyo.jp経由でCodeIQ百聞は一見に如かず~文字列処理+画像処理=?という題名で出題されていた問題に挑戦した際の解答をブログにメモしておこうと思います。

既に締め切りが過ぎていますが、問題の内容は以下を参照してください。

第1回 百聞は一見に如かず~文字列処理+画像処理=? ─小飼弾からの挑戦:エンジニアのスキルを試すコードパズル ─この問題,あなたは解けますか?|gihyo.jp … 技術評論社
挑戦者求む!【言語不問】百聞は一見にしかず by 404 Blog Not Found 小飼 弾│CodeIQ

小飼さん公式の解説はこちらにあります。

解説については小飼さんのエントリに書かれていますので、今回は自分の解答と、それをどうやって解いたのかを書こうと思います。

どうやって解いたか

まずこの問題を簡単に説明すると、人の見た目では気付かないようにテキストが埋め込まれたpng画像が公開されており、それと同じ方法で画像にテキストを埋め込むプログラムと、画像から埋め込まれたテキストを読みだすプログラムを作成するというものです。

公開されている画像は埋め込み前が下の画像で
(追記:あとで気づいたのですが、はてなフォトライフはPNG画像を変換するみたいなので元の画像と差異がある可能性が高いです)

f:id:nukesaq88:20130418185453p:plain

下の埋め込み画像にUTF-8

漢字,カタカナ,ひらがなの入ったPNG。¥n

という文字列が埋め込まれています。

f:id:nukesaq88:20130418185507p:plain

埋め込み前と後の差分を見てみる

まず自分は埋め込み前と後の画像でどのように変化しているのかを見るために、2つの画像を差分を見てみることにしました。

以下が2つの画像のピクセル毎に差分の絶対値をとったものです。
画像はGimpを用いてレイヤーモードを"差の絶対値"にして重ねあわせて作成しました。

f:id:nukesaq88:20130418185556p:plain

このように見た目にはほぼ真っ黒で差はほとんどないように見えますが、この画像中の輝度の最大値を調べ、その値が255になるようにに正規化(ノーマライズ)してあげると以下のようになります。

f:id:nukesaq88:20130418185606p:plain

差がはっきり見えるようになりましたね。
そして、ここで画像の上部に注目すると。

f:id:nukesaq88:20130418185612p:plain


画像の最上段だけ、他の場所と違っていることに気がつきます。
ということはおそらく、この部分にテキストが埋め込まれており、埋め込むテキストは画像の上段のピクセルに順番に埋め込んでいっている可能性が高いことが推測できます。

どうやってテキストがピクセルに埋め込まれているのか

ここで埋め込み後画像上部のテキストが埋め込まれていそうな領域にあるピクセルをいくつか抜き出してみました。(16進 #rrggbb形式)
#fffcfb
#fdffff
#f3fc42
#040089
そして反対に埋め込まれてなさそうな部分
#888c88
#f8fcf8
#707070
#f0b488

これだけでは違いはよく分からないので、これを2進数で表現してみます。
埋め込み有り
r:11111111 g:11111100 b:11111011
r:11111101 g:11111111 b:11111111
r:11110011 g:11111100 b:01000010
r:00000100 g:00000000 b:10001001

埋め込み無し
r:10001000 g:10001100 b:10001000
r:11111000 g:11111100 b:11111000
r:01110000 g:01110000 b:01110000
r:11110000 g:10110100 b:10001000

これを埋め込み無しの方の下位ビットに注目すると、下位ビット部分が共通して0であることがわかります。
rでは3桁 gでは2桁 bでは3桁の下位ビット部分がこの4つピクセルに共通して0になっていますね。
埋め込み有りの方はこのような特徴はありません。

ということはこの部分に文字が埋め込まれているのだとすれば、1ピクセルごとに8ビットの領域を埋め込んでおり、領域が余った部分は0で埋めているのだろうということが推測できました。

そこで埋め込んだ画像の上段から8ビットずつNULL終端(0)が見つかるまで読み込むソフトを作成したところ、問題中にある

漢字,カタカナ,ひらがなの入ったPNG。¥n

という文字列が読み出せました。

ということで今回の問題のテキスト埋め込みアルゴリズムはこのように解析していきました。
この時点で、すでにデコードには成功したため、あとは逆の方法でエンコードソフトを作るだけとなりました。

解答

以上のようにして解いていった解答となるデコーダとエンコーダのソースを以下に公開しておきます。
言語はC++で、コンパイルにはQt環境が必要です。

一応公式の解説ページでC++を使用した解答者、正答者ともに1人となっているので正解をもらえたのだと思います。

デコーダ

#include <QImage>
#include <QByteArray>
#include <QFile>
#include <QDebug>


// decode steganographically hidden byte from pixel
char decode_from_pixel( const QRgb rgb )
{
    const unsigned char r = qRed( rgb );
    const unsigned char g = qGreen( rgb );
    const unsigned char b = qBlue( rgb );
    // 3 bits from r channel, 2 bits from g channel, 3 bits from b channel
    const char hidden_byte =
            ((r & 0x7) << 5) |
            ((g & 0x3) << 3) |
            (b & 0x7);
    return hidden_byte;
}


// decode steganographically hidden text from image
QByteArray decode_from_image( const QImage &image )
{
    const int w = image.width();
    const int h = image.height();
    QByteArray decoded_string;
    for( int y = 0; y < h; ++y )
    {
        for( int x = 0; x < w; ++x )
        {
            // decode a byte from a pixel
            const QRgb rgb = image.pixel( x, y );
            const char hidden_byte = decode_from_pixel( rgb );

            if( ! hidden_byte ) // return if charcter is null
                return decoded_string;

            decoded_string.push_back( hidden_byte );
        }
    }

    return decoded_string;
}


int main(int argc, char *argv[])
{
    if( argc != 3 )
    {
        qDebug() << "usage: decoder [embedded image path] [result text file path]";
        return -1;
    }

    // load image
    const char * const image_file_path = argv[1];
    QImage image;
    if( ! image.load( image_file_path ) )
        return -1;

    // decode
    const QByteArray &decoded_string = decode_from_image( image );

    // write result text
    const char * const result_file_path = argv[2];
    QFile result_file( result_file_path );
    if( ! result_file.open( QFile::WriteOnly ) )
        return -1;
    result_file.write( decoded_string );

    return 0;
}

エンコーダ

#include <QImage>
#include <QByteArray>
#include <QFile>
#include <QDebug>

// embed a byte to a rgb
QRgb make_embedded_pixel( const QRgb source_rgb, const char embed_byte )
{
    const unsigned char r = qRed( source_rgb );
    const unsigned char g = qGreen( source_rgb );
    const unsigned char b = qBlue( source_rgb );
    const unsigned char a = qAlpha( source_rgb );

    const unsigned char embed_r =
            ( r & 0xf8 ) | ( ( embed_byte >> 5 ) & 0x7 );
    const unsigned char embed_g =
            ( g & 0xfc ) | ( ( embed_byte >> 3 ) & 0x3 );
    const unsigned char embed_b =
            ( b & 0xf8 ) | ( ( embed_byte ) & 0x7 );

    return qRgba( embed_r, embed_g, embed_b, a );;
}


// decode steganographically hidden byte from pixel
QImage make_embedded_image( const QImage &source_image, const QByteArray &text )
{
    const int text_len = text.size();
    QImage embedded_image = source_image;
    const int w = embedded_image.width();
    const int h = embedded_image.height();
    for( int y = 0; y < h; ++y )
    {
        for( int x = 0; x < w; ++x )
        {
            const QRgb source_rgb = embedded_image.pixel( x, y );
            const int text_index = y * w + x;
            const char embed_byte = ( text_index < text_len ) ? text[text_index] : '\0';

            const QRgb embed_rgb = make_embedded_pixel( source_rgb, embed_byte );
            embedded_image.setPixel( x, y, embed_rgb );
        }
    }

    return embedded_image;
}

int main(int argc, char *argv[])
{
    if( argc != 4 )
    {
        qDebug() << "usage: encoder [source image path] [text file path] [embedded image path]";
        return -1;
    }

    // load source image
    const char * const source_image_file_path = argv[1];
    QImage source_image;
    if( ! source_image.load( source_image_file_path ) )
        return -1;

    // load text
    const char * const text_file_path = argv[2];
    QFile text_file( text_file_path );
    if( ! text_file.open( QFile::ReadOnly ) )
        return -1;
    const QByteArray &text = text_file.readAll();

    // encode and make embedded image
    const QImage &embedded_image = make_embedded_image( source_image, text );

    // save embedded image
    const char * const embedded_image_file_path = argv[3];
    if( ! embedded_image.save( embedded_image_file_path ) )
        return -1;

    return 0;
}

感想

CodeIQは今回はじめて挑戦してみましたが、なかなか楽しめたと思います。
特にテキスト埋め込みの方法が正解だとわかったときは、素直に嬉しかったです。

今回は小飼さんの出題ということもあり、人数制限で締め切られないよう出題を知ってからは早めに挑戦したのですが、最終的に人数制限まで達さなかったのは少し残念だったと思います。
もし最大の100人が挑戦していた場合の正答数や使用言語の割合も見てみたかったです。