モノクロ画像の類似検索
Posted feedbacks - R
kkobayashi
#2049()
[
R
]
Pentium M 1.5GHzで実行しました。
> df <- profiling(bitmap.match.01, 1024, 768, 100)
souce image : file012.bmp
most similar : file072.bmp
> df[["by.total"]][c("bitmap.match","sample.images","sapply.bitmap.match"),]
total.time total.pct self.time self.pct
bitmap.match 12.56 100.0 0 0
sample.images 9.54 76.0 0 0
sapply.bitmap.match 1.54 12.3 0 0
> df <- profiling(bitmap.match.02, 1024, 768, 100)
souce image : file030.bmp
most similar : file024.bmp
> df[["by.total"]][c("bitmap.match","sample.images","sapply.bitmap.match","lapply.to.vector"),]
total.time total.pct self.time self.pct
bitmap.match 70.88 100.0 0 0
sample.images 7.98 11.3 0 0
sapply.bitmap.match 3.98 5.6 0 0
lapply.to.vector 58.90 83.1 0 0
サンプル画像として、1024x768のmatrixにモノクロ2値情報を読み込んだ状態を想定しています。
普通に書いた場合（bitmap.match.01）とビット演算を使用した場合（bitmap.match.02）の
プロファイルを取ってみたところ、普通に書いた場合のほうが早く終わりました。
ビット演算を使用した場合は32bit変数に変換するオーバーヘッドが相当大きかったのと、
普通に書いた場合は100個のmatrixに対するループ演算であったのに対して
ビット演算を使用した場合は(1024*768/32)*100個のループ演算が実行されるため、
計算自体が高速でもループのオーバーヘッドによって遅くなってしまったのだと思います。
実際にこういう処理が必要になれば迷わずCで書きますが、普段気にしないRの実行速度について
色々分かったのは面白かったです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | require(bitops)
lapply.to.vector <- lapply
apply.to.vector <- apply
lapply.sample.images <- lapply
sapply.bitmap.match <- sapply
sapply.sample.images <- sapply
sample.images <- function(WIDTH=1024, HEIGHT=768, SAMPLES=100){
images <- lapply.sample.images(1:SAMPLES, function(x)
(matrix(sample(0:1, WIDTH*HEIGHT, replace=T), HEIGHT, WIDTH)))
names(images) <- sapply.sample.images(1:SAMPLES, function(x) sprintf("file%03d.bmp",x))
return(images)
}
to.vector <- function(x){
bits.32 <- c(as.vector(x), numeric((32-length(x))%%32))
return(apply.to.vector(matrix(bits.32, 32), 2, function(b)(b %*% (2 ** (0:31)))))
}
pop.count <- function(x){
x <- bitAnd(x, 0x55555555) + bitAnd(bitShiftR(x, 1), 0x55555555)
x <- bitAnd(x, 0x33333333) + bitAnd(bitShiftR(x, 2), 0x33333333)
x <- bitAnd(x, 0x0f0f0f0f) + bitAnd(bitShiftR(x, 4), 0x0f0f0f0f)
x <- bitAnd(x, 0x00ff00ff) + bitAnd(bitShiftR(x, 8), 0x00ff00ff)
x <- bitAnd(x, 0x0000ffff) + bitAnd(bitShiftR(x, 16), 0x0000ffff)
return(x)
}
bitmap.match.01 <- function(WIDTH=1024, HEIGHT=768, SAMPLES=100){
images <- sample.images(WIDTH, HEIGHT, SAMPLES)
s_index <- sample(1:SAMPLES, 1)
s_image <- unname(unlist(images[s_index]))
score <- sapply.bitmap.match(images[-s_index], function(x)(sum(s_image==x)))
cat("souce image :", names(images[s_index]), "\n")
cat("most similar :", names(which.max(score)), "\n")
}
bitmap.match.02 <- function(WIDTH=1024, HEIGHT=768, SAMPLES=100){
images <- sample.images(WIDTH, HEIGHT, SAMPLES)
images <- lapply.to.vector(images, to.vector)
s_index <- sample(1:SAMPLES, 1)
s_image <- unname(unlist(images[s_index]))
score <- sapply.bitmap.match(images[-s_index], function(x)(sum(pop.count(bitXor(s_image, x)))))
cat("souce image :", names(images[s_index]), "\n")
cat("most similar :", names(which.min(score)), "\n")
}
profiling <- function(bitmap.match, ...){
Rprof("profile.out")
bitmap.match(...)
Rprof()
summaryRprof("profile.out")
}
|
にしお
#3393()
Rating0/0=0.00
説明のために2*3のサイズで説明します。
この場合、画像1とは4つのピクセルが同じ値なので類似度は4、 画像2との類似度は2、画像3とは上半分の3つと下半分の白2つが一致するので類似度は5、よって一番類似しているのは画像3となります。このお題の趣旨は検索処理の実行速度にあるので、 実行してみて実用的な速度で動くことを確認することを強く推奨します。 可能であればマシンのスペックと実行にかかった時間を書いてもらえると参考になっておもしろいと思います。
なおこのお題はC言語からスクリプト言語への挑戦状です。 スクリプト言語に有利な問題が多すぎるので、この手の問題も大募集します。
[ reply ]