2020年7月28日火曜日

サイゼリヤの間違い探しを独立成分分析

家の近所にある唯一のファミレスがサイゼリヤなので,特に好きでもないのにたまに行くんですが,子供向けメニューに「間違い探し」が載っています.普段特に見ていないのですが,結構難しいと度々話題になるようです.

キッズメニュー間違い探し - サイゼリヤ

凄く「違い」が小さいエリアに存在していたり,間違い探しの問題文となる文字の部分に違いがあったりして,確かに非常に難しいです.

これを画像処理的に違いを見つけようという試みがいくつかweb上で行われています.私が最初に見つけたのはこちらです.

サイゼリヤの間違い探しがむず過ぎるので、独立成分分析をお見舞いしてやった

他にもっと「賢い」方法がいくつも公開されていますが,この方法は具体的にどうやるのか方法が公開されていないので,私の方でもやってみて纏めました.

まず,キッズメニュー間違い探し - サイゼリヤに掲載されている間違い探しから適当に選んで画像をダウンロードします.ダウンロード画像には,左右に白い余白があるので,それをまずカットしておきます.


これをMATLABで独立成分分析します.
独立成分分析とは,非常にざっくり言うとこんな感じの分析です.

こんな感じに,「なんか2つ(以上)の特徴に分割できそうだな〜」という2次元データの集合を,

こういう風に変形(無相関化)して,更に

こういう風に変形します.
こうすると,直交座標の横軸(第1成分)と縦軸(第2成分)それぞれに,見たかった特徴量が現れるという手法です.独立成分分析の応用でよく知られた分野に音源分離があります.2つのマイクロホンで録音した同一空間上に2人の話者が同時に発話している音声データ(2つのマイクロホンからの音声は,どちらも2人の声が混ざって拾っている),独立成分分析することで,2人それぞれの声に分離することができます.

独立成分分析で間違い探しを行う大まかなアイデアは以下です.

まず,2枚の画像データを比較したい訳ですが,「間違い探し」である以上,両画像データのほとんどは全く同じデータであり,「間違い」となる両画像で差異のあるデータは,全体の中の一部しかないということが予想されます.

2枚の画像データ(画像1,画像2)の,それぞれ対応する場所の画素データを並べた画像の総画素数x2の行列

{(画像1(0,0)のR, 画像2(0,0)のR), (画像1(0,0)のG, 画像2(0,0)のG),(画像1(0,0)のB, 画像2(0,0)のB), (画像1(1,0)のR, 画像2(1,0)のR), (画像1(1,0)のG, 画像2(1,0)のG),(画像1(1,0)のB, 画像2(1,0)のB), ・・・(画像の最後まで)}

の各行をプロットするとこのようになります.(画素データを-0.5~0.5にスケールしています)


この時,上記予想を踏まえると,以下のことが言えそうです.

・両画像で違いがない画素は,y=x の直線上(実用的にはその付近)に存在する.
・y=x の直線上(実用的にはその付近)にない画素は,「間違い」の画素である.


このデータを独立成分分析して,「間違い」の成分だけを可視化します.最終的にはこうなれば,両画像で同じである成分と「間違い」の成分を直交座標から別々に読み取ることができます.



まずデータの準備.

clear;
close all;
%元画像読み込み
src=imread('body.png');
srcsize=size(src);
width=srcsize(2)/2;%画像の横幅は元画像の半分(両画像が横に並べられているから)
height=srcsize(1);
img1=zeros(width,height,3);%画像1
img2=zeros(width,height,3);%画像2
dst1=zeros(width,height,3);%分析後の画像1
dst2=zeros(width,height,3);%分析後の画像2
ivec=zeros(2,width*height*3);%画像データのベクトル(実際の分析はこのベク鳥に対して行う)
%画像を分割,ベクトルに代入
for y=1:height
    for x=1:width
        for c=1:3
            img1(y,x,c)=src(y,x,c);
            img2(y,x,c)=src(y,x+width,c);
            ivec(1,3*x+(y-1)*width*3+c)=(img1(y,x,c)/255)-0.5;
            ivec(2,3*x+(y-1)*width*3+c)=(img2(y,x,c)/255)-0.5;
        end
    end
end
%画像を表示
figure(1);
imshow(uint8(img1));
figure(2);
imshow(uint8(img2));
%ベクトルの散布図を表示
figure(3);
plot(ivec(1,:),ivec(2,:),'.','MarkerSize',1);




先ほどの図が得られました.このデータの自己相関行列を求めて,データを無相関化します.

%独立成分分析
R=[ivec(1,:)*ivec(1,:)' ivec(1,:)*ivec(2,:)';ivec(2,:)*ivec(1,:)' ivec(2,:)*ivec(2,:)']/length(ivec(1,:));%自己相関行列
[Q,L]=eig(R);%自己相関行列の固有値・固有ベクトル
V=sqrt(inv(L))*Q';%信号無相関化行列
xd=V*ivec;%無双感化されたデータxdを得る
figure(4);
plot(xd(1,:),xd(2,:),'.','MarkerSize',1);
xdをプロットするとこうなります.




なんか,もうこれでいいような気もしますが,一応,無相関化されたデータが与えられた時に,それの各成分が直行座標の各軸に重なるような回転行列を求めます.
これはFastICAという手法によって行います.
%FastICA
B=eye(2,2);
% 1列目の基底探索 %
sh=xd;
for i=1:50
    b1_past=B(:,1);                           %b1の記録
    sh(1,:)=B(:,1)'*xd;                           
    B(1,1) = mean( sh(1,:).^3 .* xd(1,:)) - 3*B(1,1);%Bの第1基底の1番目の要素更新
    B(2,1) = mean( sh(1,:).^3 .* xd(2,:)) - 3*B(2,1);%Bの第1基底の2番目の要素更新
    B(:,1)=B(:,1)/norm(B(:,1));                       %Bの第1基底を正規化
    if abs( B(:,1)'*b1_past -1 ) < 0.001      %収束判定
        break;
    end
end

% 2列目の基底探索 %
B(:,2)=B(:,2)-B(:,1)*(B(:,1)'*B(:,2));                    %b2の初期値をb1と直交化する

for i=1:50
    b2_past=B(:,2);                           %b2の記録
    sh(2,:)=B(:,2)'*xd;                           
    B(1,2) = mean( sh(2,:).^3 .* xd(1,:)) - 3*B(1,2);%Bの第2基底の1番目の要素更新
    B(2,2) = mean( sh(2,:).^3 .* xd(2,:)) - 3*B(2,2);%Bの第2基底の2番目の要素更新
    B(:,2)=B(:,2)-B(:,1)*(B(:,1)'*B(:,2));                    %b2をb1と直交化する
    B(:,2)=B(:,2)/norm(B(:,2));                       %Bの第2基底を正規化
    if abs( B(:,2)'*b2_past -1 ) < 0.001      %収束判定
        break;
    end
end
figure(5);
plot(sh(1,:),sh(2,:),'.','MarkerSize',1);

このデータを画像として可視化すれば,「間違い」の部分が浮かび上がります.
%データを0-255にスケール
sh(1,:)=255*sh(1,:)/max(abs(sh(1,:)));
sh(2,:)=255*sh(2,:)/max(abs(sh(2,:)));
%分離した各成分を画像化
for y=1:height
    for x=1:width
        for c=1:3
            dst1(y,x,c)=sh(1,3*x+(y-1)*width*3+c);
            dst2(y,x,c)=sh(2,3*x+(y-1)*width*3+c);
        end
    end
end
%表示
figure(6);
imshow(uint8(dst1));
figure(7);
imshow(uint8(dst2));

ある程度「間違い」の部分を見つけられるようになりましたが,凄く小さい間違いはほとんど分かりません.
また,右下のゴーグルはこの分析では違いがほとんど目立ちませんでした(一応色は付いています).

参考
キッズメニュー間違い探し - サイゼリヤ
https://www.saizeriya.co.jp/entertainment/

ディジタル音声&画像の圧縮/伸張/加工技術 - CQ出版
https://www.cqpub.co.jp/hanbai/books/31/31451.htm