スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ビットフラグで画像を比較する

恋愛SLG: プログラミングで彼女をつくる|paizaオンラインハッカソン7
https://paiza.jp/poh/ando

ちょっとやってみて全解禁してきた。初心者向けの問題が多かったんで余裕でした^q^
https://paiza.jp/poh/ando/share/0b8eed07

ひとつ面白い問題があったのでそれで記事を。レアアイテムのメガネの解禁問題で中級らしいんだけど、これが上級で水着が中級かなってぐらいすこし面倒な問題でした。まあ正攻法でやらなかったからなんだけどね。こんな問題↓

問題
20151209_1.png
20151209_2.png

部分一致ではなく、パターンの完全一致なんで、何のひねりもなく普通に考えると、

(1) N×Nの画像を、M×Mにトリミング(N≧M)
(2)トリミングした(1)の画像がパターンに一致するかを、ループか何かでぶん回して探索
(3)一致してればトリミングした座標を返す

というプロセスになるはず。ただ、ループで回して探索するのは芸がない!ということで、0と1の白黒画像であることを利用して2進数変換してビットフラグから一致検索する方法を考えてみます。ビットフラグにしちゃえば数字同士の計算だから場合によっては計算速くなるし、完全一致じゃなくて類似度の検索とか拡張も簡単なんで、より実戦的かもしれない(?)

注意:多倍長整数(BigInteger)を使うので、このまま問題に入力してもSystem.Numericsが足りませんとか出て正解にはなりません。オフラインで楽しむぶんがしかできないのでオナニーしましょう。

流れ
(1)画像、パターンを行単位のビットフラグに変換
例:
1 0 1
0 1 0
0 0 0
という画像なら、
[5, 2, 0]
という値になればOK

(2)画像からM×Mにトリミングする際は全てビット演算で行う。
例えば、N=3で、0行目~1行目&1列目~2列目の値を取り出したいときは、
画像:
1 0 1
0 1 0
0 0 0
マスク:
* 0 1
* 1 0
* * *
とすればいいので、マスクに使う値は
0 1 1
0 1 1
0 0 0
マスク値と画像の論理積を行単位で取ればいい(ここがミソ)。マスクした後、末尾に余計な0がくっついてる場合は逆方向に右方向にビットシフトしてM×Mのスケールに落とすことをお忘れなく。(先頭の0は無視してOK)

(3)トリミングした画像とパターンとの一致は、数値==数値ですればよい


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace Megane
{
class Program
{
static void Main(string[] args)
{
InputValue val = new InputValue();
int input_progress = 0;
int input_line = 0;
StringBuilder sb_buffer = new StringBuilder();

int inputstatus = 0;

//読み込み
while (inputstatus == 0)
{
switch (input_progress)
{
//Nの値
case 0:
int n;
if (int.TryParse(Console.ReadLine().Trim(), out n))
{
val.N = n;
input_progress++;
continue;
}
else
{
input_progress = -1;
break;
}
//画像の値
case 1:
if (input_line == val.N - 1)
{
//最終行の場合
sb_buffer.AppendLine(Console.ReadLine().Trim());

if (val.SetPicture(sb_buffer.ToString()))
{
sb_buffer = new StringBuilder();
input_progress++;
input_line = 0;
continue;
}
else
{
input_progress = -1;
break;
}
}
else if (input_line < val.N)
{
//途中行の場合
sb_buffer.AppendLine(Console.ReadLine().Trim());
input_line++;
continue;
}
else
{
//なんかおかしい場合
input_progress = -1;
break;
}
//Mの値
case 2:
int m;
if (int.TryParse(Console.ReadLine().Trim(), out m))
{
val.M = m;
input_progress++;
continue;
}
else
{
input_progress = -1;
break;
}
//パターンの値
case 3:
if (input_line == val.M - 1)
{
//最終行の場合
sb_buffer.AppendLine(Console.ReadLine().Trim());

if (val.SetPattern(sb_buffer.ToString()))
{
sb_buffer = new StringBuilder();
input_progress++;
input_line = 0;
continue;
}
else
{
input_progress = -1;
break;
}
}
else if (input_line < val.M)
{
//途中行の場合
sb_buffer.AppendLine(Console.ReadLine().Trim());
input_line++;
continue;
}
else
{
//なんかおかしい場合
input_line = -1;
break;
}
//正常に終了した場合
case 4:
inputstatus = 1;

input_line = 0;
input_progress = 0;
sb_buffer = new StringBuilder();
break;
//異常な値が入った場合
case -1:
inputstatus = -1;

input_line = 0;
input_progress = 0;
sb_buffer = new StringBuilder();
break;
}
}

//処理
if (inputstatus == 1)
{
var result = val.Compare();
if (result != null) result.Display();
}
}
}

public class InputValue
{
public int N { get; set; }
public string Picture { get; set; }
public List PictureBitFlags { get; private set; }

public int M { get; set; }
public string Pattern { get; set; }
public List PatternBitFlags { get; private set; }

public class MatchResult
{
public int X { get; set; }
public int Y { get; set; }

public void Display()
{
Console.WriteLine(Y + " " + X);
}
}

//ビットフラグにコンバート
private IEnumerable ConvertToBitFlags(string lines)
{
string[] separator = new string[] { Environment.NewLine };

foreach (var row in lines.Split(separator, StringSplitOptions.RemoveEmptyEntries))
{
BigInteger rowBitFlag = new BigInteger();

foreach (var cell in row.Split(' '))
{
if (cell == "1") rowBitFlag = (rowBitFlag << 1) | 1;
else rowBitFlag = rowBitFlag << 1;//1以外は0とみなす
}

yield return rowBitFlag;
}
}

//画像のセット
public bool SetPicture(string lines)
{
var picbit = ConvertToBitFlags(lines).ToList();

if (picbit.Count == N)
{
this.Picture = lines;
this.PictureBitFlags = picbit;
return true;
}
else
{
return false;
}
}

//パターンのセット
public bool SetPattern(string lines)
{
var patbit = ConvertToBitFlags(lines).ToList();

if(patbit.Count == M)
{
this.Pattern = lines;
this.PatternBitFlags = patbit;
return true;
}
else
{
return false;
}
}

//写真のトリミング
private IEnumerable TrimPicture(int startX, int startY, int length)
{
foreach(int row in Enumerable.Range(startY, length))
{
if (row >= N) yield return 0;

//行をマスクする値を求める
//N=5で2~3個目を抽出する場合は、0 1 1 0 0のようなマスクを作る
BigInteger rowmask = new BigInteger();
for (int i = 0; i < length; i++) rowmask = (rowmask << 1) | 1;//トリミングする部分
int nottrim = Math.Max(0, N - startX - length);//トリミングしないセルの個数
rowmask = rowmask << nottrim;

//AND演算でマスキング(気持ちいい)
BigInteger trim = PictureBitFlags[row] & rowmask;

//右側の0をビットシフトしてM×Mにスケーリングする
yield return trim >> nottrim;
}
}

//比較する
public MatchResult Compare()
{
if (this.PatternBitFlags == null || this.PictureBitFlags == null) return null;

//パターンのサイズにトリミングする
foreach (int startX in Enumerable.Range(0, N - M + 1))
{
foreach (int startY in Enumerable.Range(0, N - M + 1))
{
//トリミングされた画像
var trimmedpic = TrimPicture(startX, startY, M);

//行比較
int cnt = 0;
bool ismatch = true;
foreach (var row in trimmedpic)
{
//画像の完全一致は数値比較で良い
ismatch = ismatch && (row == PatternBitFlags[cnt]);
cnt++;
}
if (cnt == 0) ismatch = false;//トリミングデータがない場合

//完全一致した場所を発見した場合
if (ismatch)
{
var result = new MatchResult()
{
X = startX,
Y = startY,
};
return result;
}
}
}

return null;
}
}

}


ね、気持ちいいでしょ(簡単だとは言っていない)?

ちなみにこれ、数値の一致ではなく、一致した桁数を比較すれば擬似的な類似度が定義できます。抽出するピクセル数を限定すれば、とても速い画像検索アルゴリズムができそうですね。
スポンサーサイト
プロフィール

こしあん

Author:こしあん
(:3[____]
【TwitterID : koshian2】
【ほしい物リスト】http://goo.gl/bDtvG2

Twitter
カウンター
天気予報

-天気予報コム- -FC2-
カテゴリ
月別アーカイブ
最新記事
最新トラックバック
検索フォーム
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。