風邪引いたnodamushiです。急に気温が下がり、雨も降りでみなさま体調は大丈夫でしょうか？
さて、風邪を引いてグースカ寝てたけど、もう全然寝られなくなったのでフラフラインターネットを見ていました。すると、Capyという次世代（？）CAPTCHAがあることを知りました。CAPTCHAってのは、機械による自動登録とかを防止する、超読みにくくてイライラさせられるあれです。Capyの画面は以下のような感じで、楽しく入力できます。
ん〜、解きやすい。解き…やすい………。これ、簡単に自動化できるよね？と、思ったらやっぱりやられてた。参考記事：Capy CAPTCHAは一瞬で突破できる
でも、上の参考記事にはフリースタイルパズルの話は書いてないんだよね。フリースタイルパズルはピースの色の情報とかは使えない。デモでは使っている画像が少ないから、完全な背景画像を作って、後は差分で一瞬で解くことは出来る。しかし、これはデモの話で毎日新しい画像を使うとかなるだろうし、現実的な方法ではないと思う。そして、ピースを回転させるというのもそのうち出てくると思われる。
と、いうわけで、完全な背景画像を用意せずに解いてみました。
手順は簡単
- 背景画像とピース画像を読み込む（完全な背景画像ではない）
- それぞれからエッジ画像を得る
- 各エッジ点に対してShapeContextを求める
- ピース画像の各エッジ点と最も類似する背景画像のエッジ点を求める
現状、ピース画像のエッジとの差分が最も小さくなるところで出来る（テンプレートマッチング）と思いますが、ピースの回転が来ることを考慮して、ShapeContextを使ってみました。将来ピースの回転を実装したとしても無駄ですよと先手を打っておく意味もあります。ん〜、私てば親切だってばよ。
背景画像とピース画像はドラッグアンドドロップで簡単に取得できます。背景の画像幅は400固定みたいです。さらに、ピース画像の方は、ピース以外の所は全部透明色。つまり、α値だけ見れば単なる二値画像。エッジ検出超簡単。
背景画像のエッジ検出にはCanny法を使………いたかったんですが、フォルダのどこを探しても、私が昔実装したCanny法のプログラムが見つからない(´Д⊂ヽ SIFTといい、あいつらどこ消えたんだ………。もう、面倒くさかったのでソーベルフィルタのマグニチュードを閾値処理することにしました。
利用した画像はこちら（著作権はCapyにあり。）
エッジの結果はこちら。
ソーベルフィルタだけど、割と問題なさそうです。
で、これらのエッジからShapeContextを求め、類似度が最も近いエッジ点を独立に計算して、結んだのがこちらの結果
うわ〜、超適当に組んだのにおおよその場所特定しちゃってるよ。ただし、こららの結果は回転を考慮していません。
ピース画像の部分をフォトショで回転させた物もテストしてみました。
十分でしょう。なお、回転を考慮するとパターンが増える為、回転させていない場合についてのみよりは精度が当然ながら落ちます。落ちると言っても下ぐらいの程度だったけど。
今回はnodamushiが面倒くさいということもあって、各点の類似度は完全独立に計算しました。このローカルレベルの特徴をもちっとミドルレベルの特徴にすればもっと精度が上がると思います。が、我々が欲しいのは各エッジ点の完全な対応ではなく、おおよそどこら辺に答えがあるのか分かれば良いのです。しかも、完璧にマッチしなくてもある程度の誤差はCapyが許容するみたいなので、結構適当で構いません。もっと精度良くというなら、ここまで絞った後に、周辺でテンプレートマッチングさせても良いでしょう。というわけで、こんな簡単な方法ですが、Capyを破ったと言うに十分な結果でしょう。
Capyはどうすればいいの？
ここから先は会社の人が考えるべき事なので、あまり突っ込むのもどうかと思いますが、いくつかの指針を書いておきたいと思います。
ダミー情報を入れる
文字のCAPTCHAと違って、この方式は嘘の答えの位置を入れ込むことが出来ます。嘘の文字が入っていたら人間もその嘘の文字を答えてしまうので、嘘の文字を入れることは出来ません。しかし、この方法の場合はパーツと同じエッジ線を入れておくなど計算機をだましつつ、人間には明らかに違うという情報を持たせることが可能です。それだけで、今回私が実装したような簡易手法はダメになります。
エッジ情報を消す
画像認識はエッジと共にあり。いくら何でもエッジ情報が多すぎます。とにかく、エッジ情報を消してください。でも、人間には識別できるようにしてください。
テクスチャ情報を減らす
画像認識はテクスチャ情報と共にあり。いくら何でもテクスチャ情報が取得できすぎです。ピースとして切り抜いた部分のテクスチャ情報が周囲と極端に変わらないようにした方が良いです。今回、私は特に利用をしませんでしたが、テクスチャパターンで分類すれば精度の高いエッジ画像を生成できてしまいそうです。
これら課題を何とかしない限り、どんな小細工しても、私レベルの人間でも簡単に自動化する手法を作れるでしょう。
今後どうなっていくか分かりませんが、私はこの方向性はありだと思います。特に、広告媒体としてかなり優秀だと思われる。
一つの方向性として、一般ユーザーには「これはセキュリティ上必要なんだよ」と騙くらかし、単なる広告媒体以上の意味はないという方向性でも良いと思います。そのために次世代CAPTCHAという看板を掲げるのは大いにありだと思います。広告というユーザーにとってのストレスに、必要性の理由付けを与えることが出来ればかなりWinWinの関係になるでしょう。ただ、ある程度CAPTCHAを名乗る以上、一般ユーザーに「これって簡単に機械化できるんじゃないの？」と思われない程度の偽装は必要でしょう。
（今のレベルでも既に一般ユーザーには、機械化は難しいと思われるレベルなのかどうかの判断はちょっと私にはつかない。ただ、コンテストで優勝していたり、賞を取っていたりする辺り、結構筋は良いんだと思います。）
今はまだまだ、私が適当に実装したような内容であっさり破られましたが、私は応援しています。
ところで、風邪が悪化した気がするんですが気のせいでしょうか。
今回作成したJavaコード
package nodamushi.capy; import static java.awt.image.BufferedImage.*; import static java.lang.Math.*; import static java.lang.String.*; import java.awt.Color; import java.awt.Graphics2D; import java.awt.Image; import java.awt.image.BufferedImage; import java.io.IOException; import java.nio.file.Path; import java.nio.file.Paths; import java.util.ArrayList; import java.util.List; import javax.imageio.ImageIO; import javax.swing.ImageIcon; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.SwingUtilities; /** * Capyのフリースタイルパズルを単純な方法で解いてみた。 * @author nodamushi */ public class CapyHack{ public static void main(String[] args) throws IOException{ Path input = Paths.get("img","5.png"); Path output = Paths.get("img","result5.png"); BufferedImage[] imgs = loadImage(input); //背景のエッジ画像 BufferedImage bg=simpleEdge(imgs[0],50); //ピースのエッジ画像 BufferedImage pc=imgs[1]; //元画像 BufferedImage original = imgs[2]; int[][] map = ShapeContextData.createBinMap(6, 9, 13); //背景のエッジ画像上の全てのエッジ点のShapeContextを求めます List<ShapeContextData> bgShapeContexts = new ArrayList<>(); int bgw = bg.getWidth(),bgh=bg.getHeight(); for(int y=0;y<bgh;y++)for(int x=0;x<bgw;x++){ int v = bg.getRGB(x, y)&0xff; if(v!=0){ bgShapeContexts.add(new ShapeContextData(bg, x, y, map)); } } //ピースのエッジ画像の全てのエッジ点に対してShapeContextを求め、 //最も類似する背景のエッジを独立に求めます //結果は元画像の上に対応点を結ぶ形で出力します Graphics2D g = original.createGraphics(); int pcw = pc.getWidth(),pch=pc.getHeight(); for(int y=0;y<pch;y++)for(int x=0;x<pcw;x++){ int v = pc.getRGB(x, y)&0xff; if(v!=0){ ShapeContextData sd=new ShapeContextData(pc, x, y, map); //似ているのを全検索 //効率は面倒くさいから無視で double maxsim = -10000000000000000000d; ShapeContextData n = null; for(ShapeContextData s:bgShapeContexts){ double sim = s.similarity(sd); if(maxsim < sim){ maxsim = sim; n = s; } } //対応点を線で結ぶ int red = (int)(random()*255); int green = (int)(random()*255); int blue = (int)(random()*255); int rgb = 0x33000000 | red<<16 | green <<8 | blue; Color c = new Color(rgb,true); g.setColor(c); int x1 = n.x; int y1 = n.y; int x2 = x+400; int y2 = y; g.drawLine(x1, y1, x2, y2); } } g.dispose(); showImage(original); ImageIO.write(original, "png", output.toFile()); } /** * ソーベルフィルタでエッジを検出 * @param img * @param threshold 閾値（0〜255） * @return */ public static BufferedImage simpleEdge(BufferedImage img,int threshold){ int w=img.getWidth(),h = img.getHeight(); BufferedImage ret = new BufferedImage(w, h, TYPE_BYTE_BINARY); int[] map = new int[w*h]; int max=0; int[] sx=new int[3],sy=new int[3]; for(int y=1;y<h-1;y++)for(int x=1;x<w-1;x++){ /* * 1 2 3 * 4 6 * 7 8 9 */ int rgb1 = img.getRGB(x-1, y-1); int rgb2 = img.getRGB(x , y-1); int rgb3 = img.getRGB(x+1, y-1); int rgb4 = img.getRGB(x-1, y); int rgb6 = img.getRGB(x+1, y); int rgb7 = img.getRGB(x-1, y+1); int rgb8 = img.getRGB(x , y+1); int rgb9 = img.getRGB(x+1, y+1); //ソーベルフィルタx方向 sx[0]=0;sx[1]=0;sx[2]=0; _addSobelResult(rgb1, sx, 1); _addSobelResult(rgb4, sx, 2); _addSobelResult(rgb7, sx, 1); _addSobelResult(rgb3, sx, -1); _addSobelResult(rgb6, sx, -2); _addSobelResult(rgb9, sx, -1); //ソーベルフィルタy方向 sy[0]=0;sy[1]=0;sy[2]=0; _addSobelResult(rgb1, sy, 1); _addSobelResult(rgb2, sy, 2); _addSobelResult(rgb3, sy, 1); _addSobelResult(rgb7, sy, -1); _addSobelResult(rgb8, sy, -2); _addSobelResult(rgb9, sy, -1); int r = sx[0]*sx[0]+sy[0]*sy[0]; int g = sx[1]*sx[1]+sy[1]*sy[1]; int b = sx[2]*sx[2]+sy[2]*sy[2]; int v = (int)(sqrt(r+g+b)); map[x+y*w] = v; max = Math.max(max, v); } //閾値で二値化します threshold = threshold*max/255; for(int y=1;y<h-1;y++)for(int x=1;x<w-1;x++){ map[x+y*w]= map[x+y*w] > threshold? 1:0; } //※ここで細線化とかしようかと思ったけど、面倒くさくなった for(int y=1;y<h-1;y++)for(int x=1;x<w-1;x++){ int v = map[x+y*w]; if(v==1){ ret.setRGB(x, y, -1); } } return ret; } private static void _addSobelResult(int rgb,int[] ret,int mult){ ret[0] += r(rgb)*mult; ret[1] += g(rgb)*mult; ret[2] += b(rgb)*mult; } /** * 画像を読み込んで、背景画像とピース画像に分割し、配列にして返す。<br> * ピース画像は二値化してある。 * @param path * @return 背景画像、ピース画像、オリジナル画像を順に入れた配列 * @throws IOException */ public static BufferedImage[] loadImage(Path path) throws IOException{ //Pathに対応しろよなー BufferedImage img = ImageIO.read(path.toFile()); int w = img.getWidth(); int h = img.getHeight(); //この画像、画像部分は幅400で固定みたいよ BufferedImage bgImg=new BufferedImage(400, h, TYPE_INT_RGB); Graphics2D g = bgImg.createGraphics(); g.drawImage(img,0,0,null); g.dispose(); //ピースの取り出し //なんとピース部分以外は透明という"超"親切設計 //α値でエッジを抽出してしまいましょう BufferedImage pcImg=new BufferedImage(w-400,h,TYPE_BYTE_BINARY); //別に閾値はalpha>0でも良いけど、何となく127で final int threshold = 127; for(int y=0;y<h;y++)for(int x=400;x<w;x++){ int color = img.getRGB(x, y); int alpha = (color>>>24); if(alpha > threshold)BLOCK:{ //上下左右を見て、一つでも透明なところがあれば //エッジと見なす if(y >1){ int c = img.getRGB(x, y-1); int a = (c >>> 24); if(a < threshold){ pcImg.setRGB(x-400, y, -1); break BLOCK; } } if(y<h-1){ int c = img.getRGB(x, y+1); int a = (c >>> 24); if(a < threshold){ pcImg.setRGB(x-400, y, -1); break BLOCK; } } if(x>1){ int c = img.getRGB(x-1, y); int a = (c >>> 24); if(a < threshold){ pcImg.setRGB(x-400, y, -1); break BLOCK; } } if(x<w-1){ int c = img.getRGB(x+1, y); int a = (c >>> 24); if(a < threshold){ pcImg.setRGB(x-400, y, -1); break BLOCK; } } } } return new BufferedImage[]{bgImg,pcImg,img}; } public static final int r(int rgb){ return rgb >>> 16 &0xff; } public static final int g(int rgb){ return rgb >>> 8 &0xff; } public static final int b(int rgb){ return rgb &0xff; } /** * 画像をウィンドウに表示します。 * @param img */ public static void showImage(final Image img){ SwingUtilities.invokeLater(new Runnable(){ public void run(){ JFrame f = new JFrame(); JLabel l = new JLabel(new ImageIcon(img)); f.add(l); f.pack(); f.setDefaultCloseOperation(3); f.setVisible(true); } }); } //Shape Contextを表すクラス public static class ShapeContextData{ /** * 座標がどのビンに格納されるかを示すマップを作成する<br> * 今回利用するShapeContextは3つの半径の円からなる。 * 最も内側（1層目）は0番のビン一つ、それ以外は45度刻みで領域を分割し、 * 連続するビン番号を与える。<br> * （2層目は1〜8のビン、3層目は9〜16のビン） * @param r1 最も小さい内円の半径 * @param r2 真ん中の内円の半径 * @param r3 外円の半径 * @return */ public static int[][] createBinMap(int r1,int r2,int r3){ if(r1<=0 || r1>=r2 || r2 >=r3) throw new IllegalArgumentException("0<r1<r2<r3でありません"); int [][] ret = new int[r3*2+1][r3*2+1]; int rr1 = r1*r1; int rr2 = r2*r2; int rr3 = r3*r3; for(int Y=-r3;Y<=r3;Y++){ int[] arr = ret[Y+r3]; for(int X=-r3;X<=r3;X++){ int x=X,y=Y; int p = x+r3; int l = x*x+y*y; if(l <= rr1){ arr[p] = 0; }else if( l > rr3){ arr[p] = -1;//対応ビンなし }else{//2,3層目 int i = l<=rr2? 1:9; int b; if(x>0&&y>=0){ b=0; }else if(x<=0&&y>0){ b=2; int t = x; x = y; y = -t; }else if(x<0 && y<=0){ b=4; x = -x; y = -y; }else{ b=6; int t = x; x = -y; y = t; } if(y >= x)b++; arr[p]=i+b; } }//end for X }//end for Y return ret; } int x,y;//ピクセルの位置情報 int[] points=new int[1+8+8];//エッジ点の数 double[] normal=new double[1+8+8];//正規化した点の数 /** * 類似度を単にnormalベクターのL2の負数で表現。 * @param d * @return */ public double similarity(ShapeContextData d){ double[] normal = this.normal; double[] normal2 = d.normal; double min=Double.MAX_VALUE; double n0 = normal[0]-normal2[0]; n0 = n0*n0; for(int r=0;r<8;r++){ double sim = n0; for(int i=0;i<8;i++){ int ii = i+r &7;//(i+r)%8 double n1 = normal[i+1]; double n2 = normal2[ii+1]; double n = n1-n2; sim += n*n; n1 = normal[i+9]; n2 = normal2[ii+9]; n = n1-n2; sim+=n*n; } if(min>sim){ min = sim; } } return -sqrt(min); } /** * * @param img 二値化画像 * @param x 調べるx座標 * @param y 調べるy座標 * @param bmap createBinMapで作成した配列 */ public ShapeContextData( BufferedImage img,final int x,final int y, int[][] bmap){ if((img.getRGB(x, y)&0xff )== 0) throw new IllegalArgumentException( format("(%d,%d)はエッジ上の点ではありません", x,y )); this.x = x; this.y = y; int rmw = bmap.length; int cen = (rmw>>1); int w = img.getWidth(),h=img.getHeight(); //ループの範囲の計算 int tmp = x-cen; int sx = tmp<0? -tmp:0; tmp = y-cen; int sy = tmp<0? -tmp:0; tmp = rmw -cen + x; int ex = tmp>w? rmw- (tmp-w):rmw; tmp = rmw -cen + y; int ey = tmp>h? rmw- (tmp-h):rmw; //エッジ点の数をカウント for(int yy=sy;yy<ey;yy++){ int[] arr = bmap[yy]; int Y = yy-cen+y; for(int xx=sx;xx<ex;xx++){ int X=xx-cen+x; int p = arr[xx]; if(p==-1) continue; int v = img.getRGB(X, Y)&0xff; if(v!=0){ points[p]++; } } } //正規化 なお、sumは0にはなりえません。 double sum=0; for(int i:points)sum+=i; for(int i=0;i<points.length;i++){ normal[i] = points[i]/sum; } } } }
