Tweet Counter
Home

GRID (類似画像検索ソフトウェア/ similar image search software)

for Windows2000, Windows XP
download (Japanese ver., Windows2000 では GDI+.dll が必要です)
download (English ver., GDI+.dll is required for Windows2000.)

Test versions are here.

主要な修正事項 / lasted main fix. check.

version 000u からキャッシュ形式が変わり, default の Grid サイズが 16x16 になりました.


・重複ファイル検索ソフトウェア DHFiND はこちら. / DHFiND is here.
・類似画像検索用 DLL GRIDExt.DLL はこちら. / DLL version is here.
・他の製作者の類似画像検索ソフトはこちら

Main 画面 (Windows7)


Result View (Windows7)


Result View (Windows7,
GRID16.ini ファイルに ResultImageCount=8, ResultImageSize=140 を追加)


Result View (Windows2000)

more sample, and more...




0) 概要 / Overview

「GRID」はローカルコンピュータ内に保存された画像から,類似画像を検索する Windows 用ソフトウェアです. 現在,3つの検索モードがあり,1) 指定フォルダの類似画像をグループ化して表示する,2) 指定フォルダ2の画像を検索ソースにして指定フォルダ1から類似画像を検索する, 3) 指定画像を検索ソースにして指定フォルダ1から類似画像を検索する,ことができます.

書庫("ZIP","LZH") 内のファイルを検索対象にすることが可能です (それぞれ unzip32.dll, unlha32.dll が必要です). 一度検索したフォルダに対して cache ファイルを作成するので,2 度目の検索は比較的高速になります. 検索された画像は「ResultViewer」に表示され,不要なファイルを削除することができます.また,2つの画像の「差分イメージ」を表示して異なる部分を確認することが可能です.

NOTE: ここでの「類似画像」は見た目が似たような画像を指し,「重複画像」はファイル内容が完全に一致する画像ファイルを意味します.



"GRID" is a similar image search software for Windows that retrieval similar images from your local computer.
At present, 3 search modes are available. 1) Glouping and display images similar to each others included in indicated folder(Path1). 2) Find out images similar to source images in Path2 from indicated Path1. 3) Retrieval images similar to an indicated image from Path1.

Image files stored in archive ("ZIP" and "LZH") will be search target (check on "Accept Archive").(require unzip32.dll and unlha32.dll respectively)
In 1st search step, cache files related in folder and archive file are generated, so following search will be fast.
After search step, detected images are displayed in "ResultView", and you can delete graphically dupulicated image files. In addition, you can confirm difference portion of 2 images by "Differential image".

NOTE: In this page, "similar images" indicate images looks like same (graphically duplicated), and "duplicated images" means image files had same bainarys (completely duplicated files).





1) 仕様 / Specification






2) インストール,アンインストール / Install, uninstall

・インストール:

zip ファイルを適当なフォルダに解凍して 「GRID.exe」 を起動してください.
 Windows2000 では "GDIplus.dll" が必要です.ダウンロードして解凍した後,実行ファイルと同じフォルダに置いてください.アーカイブファイル("ZIP" and "LZH")を扱うには "unzip32.dll" and "unlha32.dll" がそれぞれ必要です. ここ (統合アーカイバプロジェクト) から入手可能です.ダウンロード,解凍した後,実行ファイルと同じフォルダに置いてください.Susie plugin は "00IN" 系のみ対応しています.spi フォルダに plugin を入れて下さい.

・アンインストール:

レジストリは使用しません.フォルダごと削除してください.


Install:

Uncompress downloaded zip file to a suitable folder and start "GRID.exe".
Windows2000 will require "GDIplus.dll". Download & uncompress it, then put GDIplus.dll on same folder to execution file.
To accept archive ("ZIP" and "LZH") files, "unzip32.dll" and "unlha32.dll" are required respectively. you can get them from here (Common Archive Library Project), download & uncompress "UNZIP32.DLL" and "UNLHA.DLL", then put them on same folder to execution file.

Uninstall:

Delete installed folder. (Registry is not used.)




3) 使い方 / How to use

・"GRID search window"

Grouping: 「検索 Path1」 にフォルダを指定して「検索開始 >>」ボタンを押します.

Grouping: Set a folder path containing images to "Path1", then push "SEARCH >>" button.

"GRID search window" (default mode) jpn eng

検索パス1 のエディットボックスにフォルダをドロップするか,「フォルダ選択」ボタンから検索フォルダを指定できます.
Drop a folder to the edit box of "Path1", or press a "SelectFolder>>" button to indicate a folder for retrieval.



Whole window and detailed setting will appear when pushing "Expand >>" button several times. jpn eng



Search1: Grouping.

To quick start search, drop a folder or files on "SEARCH" button.

Search2: Find similar images.(mass compare)

To quick start search, drop a folder or files on "SEARCH" button.

Search3: Find similar images.(an image compare)





To quick start search, drop a file on "SEARCH" button.

Search preset (stringency setting).jpn eng

Select a stringency preset before search.
Upper side menu items of "Search preset" are high-stringency setting. In contrast, lower sides are low-stringency setting.

検索前にプリセットで設定を選択します.
検索プリセットは,基本的に上のほうが "厳密に検索",下に行くほど "あいまい検索" になります.



- Pre Check, and etc.




- PostGridCompare




- Cache control



"Analyzer view"

検索パス1の画像キャッシュを解析します.画像キャッシュが読み込まれていない場合,これらの機能は動作しません(cache empty エラーになる).解析をする前に,検索パス1に画像が含まれるフォルダをセットし,"キャッシュ更新 >>" ボタンを押して下さい.

Analyzing cached images in path1. If image caches are not loaded, these function did not work (should be "cache empty" error). Set a folder path containing images to path1, and press "Cache Update >>" button before analyze.


"Intensity": 画像輝度の分布 / image intensity distribution.

X軸は画像輝度 ( 0 〜 255), Y軸は各輝度の画像数.

X-axis is image intensity ( 0 to 255) and Y-axis is image count of each intensity.



"FileSize": ファイルサイズ分布 / file size distribution.

X軸はファイルサイズ (単位bytes, 0 〜 最大値), Y軸は各画像サイズの画像数.

X-axis is file size (bytes, 0 to Max) and Y-axis is image count of each file size.



"ImageSize": 画像サイズランキング / image size ranking.

各画像サイズの頻度をランキング形式でリストアップ.

List up earch image size frequency by ranking form.



"Unique": ユニークファイル数 / unique file count.

ユニーク(MD5非一致の)画像と重複(MD5一致)画像の数を表示, ファイルサイズの合計を計算します.

Count up uniqued (MD5 unmatched) and duplicated (MD5 matched) image number respectively, and calculate sum of file size.









・"Result View"

上段にグループのサムネイル画像が表示されます.下段に,選択されたグループに含まれるファイルのサムネイル画像が表示されます.
選択されたグループは赤い枠で,選択されたイメージは青い枠で示されます.


Thumbnail images of each groups are displayed in the upper row. Thumbnail images included in the selected group are displayed in the lower.
The selected group is shown by red frame, selected image shown by blue frame.



"ResultView" sample 1

Upper row: Thumbnail images of each groups. Under row: Grouped images of selected group.
Search source images are always arranged in left end of each group by "Search2" and "Search3".

"ResultView" sample 3

非選択イメージ上で右クリックすると,選択されたイメージとの「差分イメージ」を表示します (右クリックメニューから選択).
When right-clicking on non-selected image, "differential image" with the selected image is displayed (select a right-clicking memu item).

"ResultView" sample 4

選択された画像と MD5 が同じ画像には 「MD5 Match」が表示されます.
"MD5 Match" is displayed if image have same MD5 with the selected image.

"ResultView" sample 5

書庫内のファイルは赤いテキストで表示されます (このファイルは削除不可).
Files stored in archives are shown by red text (These files are not deletable).

right clicking menu







4) TIPS






5) 動作解説 / Explanation of similar image detection method

・類似画像検索の基本的なアルゴリズム(類似画像の検索方法)

画像ファイルを読み込み, 120x120 pixel に縮小した後,8x8 のグリッド(1 セル当たり 15x15 pixel)に分割して,各セルの平均色を算出し 16bit color (RGB565) で保存します.この情報は cache されます.
各画像について,この 8x8 グリッドの色彩差を比べて検索・グループ化します.
この検索方法では,画像がトリミングされている場合,見逃しが多くなります(似ているけど検索されない).

original image vs. 8x8 grid view
original image 8x8 gird view

検索の高速化のため,検索画像と同程度の輝度を持った画像のみを計算します(option で範囲指定可能).
比較は,平均輝度差 > MD5 > 画像サイズ > 画像アスペクト比 > 平均色彩差 > グリッド > 画像ピクセル(option) の順で行われます.各比較の段階での差が大きいと,そこで比較は中止され,次の比較は行われません.


・GRID compare function

基本的に,「各セル色彩差の総和を比較」,「グリッド色彩最遠距離を比較」,「色彩一致セル数を比較」の3つの関数が用意されています.またそれぞれに,「高輝度・低輝度切り捨て」version があります.


「各セル色彩差の総和を比較」

各セル色彩(RGB)差の絶対値を加算していき,理論的最大値で割ってその比率を求めます.理論的最大値は真黒グリッド( RGB(0,0,0)x 8x8セル )と真白グリッド( RGB(255,255,255)x 8x8セル )の比較で最大となり,一致率は 0% になります.
一致率以外のパラメータはありません.


「グリッド色彩最遠距離を比較」

実験用です.
グリッド色彩(RGB)差の絶対値の総和を計算するのは同じですが,比較元グリッドと最も距離が遠くなるグリッドを想定し,その差を理論的最大値にして比率を求めます.例えば RGB(100,0,200) の場合,最遠グリッドは RGB(255,255,0) になります.
基本的に非対称です.
一致率以外のパラメータはありません.
削除されました.000l


「色彩一致セル数を比較」

色彩の一致するセル数を全体のセル数で割ってその比率を求めます.2nd パラメータは各セルの一致許容範囲(%)です.



「高輝度・低輝度切り捨て」version

白い紙の真中に小さく絵が描かれた2つの画像を比較すると,周りの余白が一致するため全体の一致率が上昇します.余白が白いという意味では2つの画像は一致していますが,この余白を比較に含めたくない場合,この version の関数を使用します.
比較する2つのセルの輝度がある一定以上の場合(白っぽい場合),そのセルを Skip し,比較の計算に含めません.
比較する2つのセルの輝度がある一定以下の場合(黒っぽい場合)も同様にします.


・Post Grid compare

「Post Grid compare」 にチェックを入れた場合は,グリッドの比較で一致した後に,画像ファイルを実際に開いて比較します. 実際にファイルを読み込むため,動作はかなり遅くなります.


Post GRID compare: line draw compare function

画像を 128x128 pixel の線画に変換してから,各ピクセルの比較を行います.
変更可能なパラメータは,全体の一致率(%),各ピクセルの許容差(%),線として認識する明るさの閾値(%).


original vs line draw view sample1
original image line draw view

original vs line draw view sample2
original image line draw view



Post Grid compare: standard function

画像を 120x120 pixel に縮小,ピクセル毎の色彩差の総和を算出し,輝度別の閾値を設定して類似画像か判断します.一致率も含めて変更可能なパラメータは一切ありません.
古い default 関数です.通常は使用しないで下さい.



Post Grid compare: external dll

外部 DLL を使用して画像ファイルを比較します.詳しくは 「外部定義の画像比較関数」 の章を参照して下さい.



・「差分イメージ」 / "Differential image"

「差分イメージ」は2つの写真の異なる部分を抽出します(各ピクセル差の絶対値).色の変化の無い部分は黒くなります.色の変化があった部分に色がつきます.


"differential image" sample A. differential source images(top) and differential image(bottom)
differential source image1 differential source image2
differential image



"differential image" sample B. differential source images(top) and differential image(bottom)
differential source image1 differential source image2
differential image
写真の右側でナメクジが移動している./ a slug is moving at right side of picture.



"differential image" sample C. differential source images(top) and differential image(bottom)
differential source image1 differential source image2
differential image



・「chain search」

「chain search」にチェックを入れると,類似画像が見つかった場合にその発見画像を検索 source として次の類似画像を探します.結果として,通常はグループを大きくする方向に働きます.


類似度順に image A, image B, image C と類似画像があったとします.

「chain search」なしの場合,
まず image A と image B を比較してグループを作ります.
次に image A と image C を比較しますが,類似度差が大きすぎると image C はグループに追加されません.

「chain search」ありの場合,
まず image A と image B を比較してグループを作ります.
次に検索画像を image B に切り替え, image B と image C を比較します.
image C を image A, image B のグループに追加します.

結果としてとんでもない画像がグループに入ったりすることもあります.
また,image A と image C が良く似ていても,image B と image C が似ていない場合は,グループ化されません.


・キャッシュ更新 / Cache update

Cache 更新では,既存の cache ファイルを読み込んだ後,実際には存在しない画像の cache を削除します.次に,フォルダに新規に追加されたファイルを cache に追加します.また,ファイル名が同じで,ファイルサイズの異なる画像ファイルを再 cache 化します.このとき,ファイルサイズしか検査しないため,偶然同じフォルダに同じファイル名で存在する,ファイルサイズの一致する異なる画像があった場合は,古い cache のまま更新が行われません.この場合は,そのファイルを別の場所に移動してから cache 更新を行い,再び元の場所に戻して再度 cache 更新を行う必要があります.(000m からは更新時間もチェックします.)

通常,こういったことが起きる可能性はかなり低いハズですが,BMP ファイルに関してはピクセル色が変わってもサイズが変化しないため,起こりうる可能性があります.

ちなみに MD5 で比較しないのは,Cache 更新の度に MD5 を再取得すると速度が著しく低下するためです.

「Cache 更新」ボタンで cache の更新が行われるのは「検索Path1」に対してのみで,「検索Path2」に対しては行われません.「検索Path2」の cache は検索時に毎回 cache の更新が行われます.これには明確な理由があるわけではなく,試行錯誤の一つです.




6) 外部定義の画像比較関数 / External defined image compare function

外部定義の画像比較関数を用意することにより,PostGridCompare での比較関数を独自のものに置き換えられます. Post Grid Compare の関数に "external dll(match %, ...)" を選択してください. 実行ファイルと同じフォルダに GRIDExt.dll を作成します. GRIDExt.dll では IsAcceptableImage2() 関数をエクスポートして下さい.

extern "C" __declspec(dllexport)
int __cdecl IsAcceptableImage2(const char* szLeft,
                               const char* szRight, 
                               double dAcceptPer,
                               int   nParamSize,
                               const double* in_pParamArray,
                               double *out_pMatchPer)
パラメータ / Parameters

szLeft

比較する画像 (source image) のファイルパスが渡されます.


szRight

比較するもう一方の画像 (dest image) のファイルパスが渡されます.


dAcceptPer

GRID では GRID::MainWindow で入力した一致率が 100 分率で渡されます. 2 つの画像を比較し,この一致率以上の場合,関数は true を返して下さい.そうでないなら false を返して下さい.


nParamSize

in_pParamArray の要素数が渡されます.


in_pParamArray

GRID では GRID::MainWindow で入力したパラメータが渡されます.現在は 4 つのパラメータが指定可能です.関数特有のパラメータを独自に定義して使用して下さい.


out_pMatchPer

out_pMatchPer が NULL でない場合,2 つの画像の一致率 (100 分率) を設定して返します.


戻り値 / Return Values

関数は 2 つの画像ファイル szLeft, szRight を比較して dAcceptPer 以上であるなら true を,そうでない場合は false を返して下さい.また,out_pMatchPer が NULL でないときは,ここに 2 つの画像の一致率を 100 分率で設定して下さい.画像ファイルパスが不正な場合,もしくは未対応の画像ファイルである場合 -1 を返して下さい.


解説 / Remarks

関数は 2 つの画像ファイル szLeft, szRight を比較して dAcceptPer 以上であるなら true を,そうでない場合は false を返します.また,out_pMatchPer が NULL でないときは,ここに 2 つの画像の一致率が 100 分率で設定されます.
画像ファイルパス szLeft, szRight が不正な場合,もしくは未対応の画像ファイルである場合 -1 が返ります.






7) 画像情報 (Info text) の拡張 / Extended additional information of an image

外部定義の InfoText 関数を用意することにより,ResultView での InfoText を独自のものに置き換えられます. Info フォルダ以下に,下に示す関数郡をエクスポートした dll を置いて下さい.ResultView 上の余白で右クリックすることにより InfoText を切り替えます(トルグ). GetInfoText〜() 関数では,画像の MD5 値,もしくは画像のファイルパスから Text 情報を取得します.


黄色丸の部分を置き換えます. InfoText の切り替えは,空白部分 (ボタンの隣など) を右クリックすることによって行います. "available" では何らかのテキストを返した InfoText.dll の情報を表示します.無い場合は "default" の情報になります. "default" では 「ファイルのフルパス」「保存フォルダ+ファイル名」「ファイルサイズ」「MD5値」「画像サイズ」「作成時間」「更新時間」が表示されます.




extern "C" __declspec(dllexport) 
int __cdecl Initialize(const char* szFolder)

他の関数が呼ばれる前,アプリケーション起動時に一度だけ呼ばれます.szFolder に dll のフォルダパスが渡されます. 初期化に成功した場合は 1 を,失敗した場合は 0 を返して下さい. 0 を返した場合,dll は登録されません.


extern "C" __declspec(dllexport) 
int __cdecl Finalize()

アプリケーション終了時に一度だけ呼ばれます.成功した場合は 1 を,失敗した場合は 0 を返して下さい. Initalize() で 0 を返した場合,この関数は呼ばれません.


extern "C" __declspec(dllexport) 
int __cdecl GetInfoTitle(char* out_pBuffer, int nBufLen)

取得する情報のタイトルを out_pBuffer に設定し,設定した長さを byte 単位で返して下さい. nBufLen に out_pBuffer のサイズ (byte) が渡されます. out_pBuffer が NULL の場合は,タイトルを設定するのに必要な長さを byte 単位で返してください. エラーの場合は 0 を返して下さい.


extern "C" __declspec(dllexport) 
int __cdecl GetInfoTextFromMD5String(const char* szMD5String, 
                                    char* out_pBuffer,
                                    int nBufLen)

MD5値 szMD5String に関連する情報を out_pBuffer に設定し,設定した長さを byte 単位で返して下さい. nBufLen に out_pBuffer のサイズ (byte) が渡されます. out_pBuffer が NULL の場合は,情報を設定するのに必要な長さを byte 単位で返してください. MD5値から情報を取得できない場合,エラーの場合は 0 を返して下さい. この関数を実装しない場合は,GetInfoTextFromFilePath() を実装してください.


extern "C" __declspec(dllexport) 
int __cdecl GetInfoTextFromFilePath(const char* szFilePath, 
                                    char* out_pBuffer,
                                    int nBufLen)

指定ファイル szFilePath に関連する情報を out_pBuffer に設定し,設定した長さを byte 単位で返して下さい. nBufLen に out_pBuffer のサイズ (byte) が渡されます. out_pBuffer が NULL の場合は,情報を設定するのに必要な長さを byte 単位で返してください. 指定ファイルから情報を取得できない場合,エラーの場合は 0 を返して下さい. この関数を実装しない場合は,GetInfoTextFromMD5String() を実装してください.



解説 / Remarks

関数郡は,アプリケーション起動 → Initalize() → GetInfoTitle() → GetInfoTextFromMD5String() or GetInfoTextFromFilePath() → Finalize() → アプリケーション終了, の流れで呼ばれます. GetInfoTextFromMD5String() と GetInfoTextFromFilePath() の両方を実装する必要はありません.両方を実装した場合は GetInfoTextFromMD5String() が優先的に使われます. SetInfoText〜() 関数は今のところ用意されていません.


InfoText.dll サンプルソース


TSVInfo.dll TSVInfo.zip

TSVInfo.dll は,ResultView の InfoText 欄を,画像の MD5 値と関連付けられたテキスト情報に置き変える InfoText.dll です. ダウンロードの後解凍して,GRID の Info フォルダ以下に入れてください.MD5 値に関連付けられた情報は TSV 形式のファイルで用意します. 先頭に MD5 値が書かれたタブ区切りのテキストファイル TSVInfo.TSV を用意し,TSVInfo.dll と同じフォルダに置いて下さい.

例: TSVInfo.TSV
30a50afc5d74028e23d3ab2f680d9837[TAB]情報1[TAB]情報2………
d801adf924e164c0647d3cdedb5f518d[TAB]情報1[TAB]情報2………
cf9886bfcdd7eb291f1dbc8523bf0438[TAB]情報
………
……

[EOF]

上記の [TAB] はタブ文字に置き換えてください. タイトルを変更したい場合は,TSVInfo.dll と同じフォルダに TSVInfo.ini ファイルを作り,「Title=$Title」 の行を追加してください.$Title がタイトルになります. TSV ファイルを明示的に指定する場合は,「TSVFile=$TSVFile」 の行を追加してください. この .ini ファイルには,先頭から空改行を含めないで下さい(空改行を終端と判定するため).

例: TSVInfo.ini
Title=メニューのタイトル
TSVFile=C:\TSV\FileMD5andAttribute.TSV
[EOF]

IHDBInfo.dll (InfoText.dll for IHDB) IHDBInfo.zip Details from here.





8) 設定ファイル / config file

実行ファイル GRID.exe と同じフォルダに GRID.ini という名のテキストファイルを作成して下さい(Grid16.exe の場合は Grid16.ini). parameter=$parameter_content の形式で各パラメータを設定します. ini ファイルには空改行を含めないで下さい.


設定ファイルパラメータ一覧

FoundSoundFile=$FoundSoundFile
NotFoundSoundFile=$NotFoundSoundFile
ErrorSoundFile=$ErrorSoundFile
GoForegroundOnFind=$GoForegroundOnFind
UseTaskTray=$UseTaskTray
ImageSizeLimitMin=$ImageSizeLimitMin
ImageSizeLimitMax=$ImageSizeLimitMax
FileSizeLimitMin=$FileSizeLimitMin
FileSizeLimitMax=$FileSizeLimitMax
ResultGroupMax=$ResultGroupMax
ThreadDivide=$ThreadDivide
ImageViewer=$ImageViewer
GroupViewer=$GroupViewer
ResultViewer=$ResultViewer
ResultImageSize=$ResultImageSize
ResultImageCount=$ResultImageCount




$FoundSoundFile, $NotFoundSoundFile, $ErrorSoundFile
それぞれ,発見した時,未発見の時,エラーの時の wav サウンドを指定します.
これらを指定した場合,一部のダイアログ(未発見ダイアログなど)は表示されなくなります.


$GoForegroundOnFind
1 の場合,発見後に GRID をフォアグランドウインドウにします.
0 の場合はフォアグランドウインドウにしません.
default は 0 です.


$UseTaskTray
1 の場合,タスクトレイを使用します.
0 の場合はタスクトレイを使用しません.
default は 0 です.
タスクトレイのアイコンをダブルクリックするとメインウインドウは隠れます.もう一度ダブルクリックすると表示します.
メインウインドウが非表示状態では,未発見のメッセージはバルーンで表示されます.


$ImageSizeLimitMin, $ImageSizeLimitMax
それぞれ,取り込む画像の最小,最大サイズをピクセル単位で指定します.縦サイズ,横サイズは共通です.指定ピクセル数未満,超過の画像は読み込みません.


$FileSizeLimitMin, $FileSizeLimitMax
それぞれ,取り込む画像ファイルの最小,最大サイズをバイト単位で指定します.指定サイズ未満,超過のファイルは読み込みません.


$ResultGroupMax
ResultGroup の最大数を設定します.指定数以上の Group が作製された場合検索を中止します.0 を指定した場合無制限になりますが,メモリが確保できなくなった場合死亡します.default は 30000 です.


$ThreadDivide
検索時のスレッド分割数を指定します.default は 0 で,検出された論理コア数です.


$ImageViewer
ResultView でダブルクリック時に使用する Viewer を指定します.


$GroupViewer
ResultView で右クリックメニューから指定グループを表示する Viewer を指定します.グループ内のファイルはパスリスト形式のファイルで指定のプログラムに渡されます.


$ResultViewer
結果を表示する ResultViewer をフルパスで指定します.このパラメータを指定した場合,結果を GRID の ResultViewer で開かず,指定のビューアで開きます.default は無為指定です.結果はパスリスト形式のファイルで指定のプログラムに渡されます.

$ResultViewer "$FulllPath_of_PathListFile"

パスリストファイルの内容はテキスト形式で,画像ファイルのフルパスが改行(\r\n)区切りで書かれています.グループ間の区切りは空改行で示されます.


$ResultImageSize
ResultView でのサムネイルの画像サイズをピクセル単位で指定します.最低値は 140 です (140x140 pixels).


$ResultImageCount
ResultView でのサムネイルの画像数を指定します.最低値は 4 ,最大値は 10 です.


サンプル: 空改行の次の行から [EOF] 直前まで.

FoundSoundFile=found.wav
NotFoundSoundFile=notfound.wav
ErrorSoundFile=error.wav
GoForegroundOnFind=1
UseTaskTray=1
[EOF]



9) memo

・ GRID (Graphically Redundant Image Detector) ソースコード(一部)

・ cache ファイルの構造

LocalCache( フォルダのフルパスの MD5 ).txt


ファイルフルパス[改行]
ファイルサイズ(byte)[改行]
create FILETILE(hex)[改行]
access FILETILE(hex)[改行] あまり意味が無いので, 000m で削除.
write FILETILE(hex)[改行]
File MD5(hex)[改行]
Grid(8x8) Color(RGB565) 左上から右下へ (hex)[改行]
イメージサイズ SIZE(hex)[改行]
[改行](空改行)


・GRID cache から画像を特定できるか?

8x8 GRID では線画の識別が不十分.16x16でもさほど十分とはいえないか.
ディスク上に複数の grid cache を保存しておき,場合によって読み替えるか.


・ grid size 再検討
original image vs. grid view (6x6, 8x8, 16x16, 24x24, 32x32)
original
original image
6x6
6x6 gird view
8x8
8x8 gird view
16x16
16x16 gird view
24x24
24x24 gird view
32x32
32x32 gird view

original は右端が白飛びしているが, 6x6, 8x8 grid では右端のグリッドは白飛びしていない.16x16 grid 以上だとこの情報が保存されている.


参考: MD5(16 byte = 128 bit), SHA-1(20 byte = 160 bit), SHA256(32 byte = 256 bit), SHA512(64 byte = 512 bit)


theoretical memory consumption
file size8x8 grid16x16 grid24x24 grid32x32 grid64x64 grid
1万ファイル: 10,000 filesabt. 1.2 MBabt. 4.9 MBabt. 11.0 MBabt. 19.5 MBabt. 78.1 MB
10万ファイル: 100,000 filesabt. 12.2 MBabt. 48.8 MBabt. 109.9 MBabt. 195.3 MBabt. 781.3 MB
100万ファイル: 1,000,000 filesabt. 122.1 MBabt. 488.3 MBabt. 1098.6 MBabt. 1953.1 MBabt. 7812.5 MB
#Grid のみの理論値.実際にはパス情報等で 256 byte/file ほど増加する.

grid size が増えるに従って画像ファイルの分解能は向上するが,cell の比較回数も増加するので速度はかなり低下する.

grid size & compare frequency
gridcell num.(compare frequency)timeselapsed time
8x8 grid64 compare/image pair x1 170 sec.(x1)
16x16 grid256 compare/image pair x4 603 sec.(x3.5)
24x24 grid576 compare/image pair x9 1326 sec.(x7.8)
32x32 grid1024 compare/image pair x16 2342 sec.(x13.8)
64x64 grid4096 compare/image pair x64 N.D.
a) elapsed time は 6,000 files(cached) で測定した参考値(設定や条件を統一. debug build).
(8x8 grid release build: 49 sec.)
b) N.D. = No data
比較関数を調整したため,通常,総比較は行わないことに.000l



・ファイル同士の総比較回数

画像ファイルの単純な比較回数は,file 数 n の時,単純ループで n x n 回. n(n+1)/2 回.n(n-1)/2-1 回.

n(n-1)/2-1 回 の時,
10,000 files = 49,994,999 times.
100,000 files = 4,999,949,999 times.
1,000,000 files = 499,999,499,999 times.

比較済みかどうかを調べる情報を 1 byte で保存すると,
10,000 files = 49,994,999 byte (47.7MB)
100,000 files = 4,999,949,999 byte (4.65 GB)
1,000,000 files = 499,999,499,999 byte (465 GB)



・"Find same files (same binary)" vs GetSameBinary, tested by GRID16x16

Path1 をキャッシュ更新の後,それぞれの処理を行った.よってファイル探索と読み込みの時間は含まれない.

107546 total images.

"Find same files (same binary)"
1st: 24943 images classified into 10610 groups. elapsed 1 min 1 sec.
2nd: 24943 images classified into 10610 groups. elapsed 1 min 3 sec.

GetSameBinary
1st: Found 10610 duplicated image groups. elapsed 7 sec. 20 msec.
2nd: Found 10610 duplicated image groups. elapsed 19 sec.



52223 total images.

"Find same files (same binary)"
1st: 7772 images classified into 3482 groups. elapsed 11 sec.
2nd: 7772 images classified into 3482 groups. elapsed 12 sec.

GetSameBinary(ver.2)
1st: Found: 3482 duplicated image groups. elapsed 1 sec. 643 msec.
2nd: Found 3482 duplicated image groups. elapsed 5 sec. 718 msec.



107619 total images.

"Find same files (same binary)"
1st: 24956 images classified into 10616 groups. elapsed 53 sec.
2nd: 24956 images classified into 10616 groups. elapsed 1 min 12 sec.
3rd: 24956 images classified into 10616 groups. elapsed 1 min 29 sec.

GetSameBinary(ver.3)
1st: Found 10616 duplicated image groups. elapsed 5 sec. 518 msec.
2nd: Found 10616 duplicated image groups. elapsed 9 sec. 274 msec.
3rd: Found 10616 duplicated image groups. elapsed 8 sec. 582 msec.




・マルチコア実験

Processing time is controled by number of worker threads and CPU cores.
CPU/Number of worker threads12346
AthlonXP2000+ (1.66GHz) 19min 36sec 19min 35sec N.D. N.D. N.D.
Celeron DualCore E1200 (1.6GHz) 11min 31sec 8min 21sec 7min 14sec 6min 5 sec 6min 0 sec
N.D. : No Data
GRID16 000v(08.08.15), Grouping, default setting
Data: G16Rand20000.dat

1コアの AthlonXP ではスレッド分割数を増やしても,処理時間は変わらなかった.マルチコア CPU では,スレッド分割数をコア数と同じにすれば,理論上比較処理時間は半分になるはずである.しかし,2 コアの Celeron DualCore では,実際そうはならなかった.GRID では,比較処理の分割スケジュールを実行前に決める仕様のため,あるスレッドが先に終了してしまうと,全てのコアが動いていない状況が発生すると考えられる.そしてスレッド分割数を増やすと,このようなスレッドが先に終了して片方のコアがアイドル状態になる時間が短くなるため,処理時間がほぼ理論値(2コアで半分)になったと考えられる.




・画像に関連付けられた情報の検索

必要なもの:MD5 データベース

1) 検索画像の MD5 算出.
2) MD5 データベースより検索,found >> 発見したら表示.
3) not found >> 検索画像から GRID を作成.
4) GRID データから類似画像を検索.
 4-1) found >> 発見したら,その画像から MD5 を算出し,MD5 データベースより検索.
 4-2) not found >> not found で終了.
5) 4-1で発見したらそれを表示.


MD5 データベースファイルの仕様

#案1

画像ファイル 1 のMD5 [TAB] 情報1 [TAB] 情報2 [TAB] 情報3 … [改行]
画像ファイル 2 のMD5 [TAB] 情報1 [TAB] 情報2 [TAB] 情報3 … [改行]
画像ファイル 3 のMD5 [TAB] 情報1 [TAB] 情報2 [TAB] 情報3 … [改行]
……

改行までを 1 レコード,[TAB] 区切り.情報内の TAB と改行をエスケープする必要あり.


#案2

画像ファイル 1 のMD5 [改行]
情報1 [改行]
情報2 [改行]
情報3 [改行]
… [改行]
[改行](空改行)
画像ファイル 2 のMD5 [改行]
情報1 [改行]
情報2 [改行]
情報3 [改行]
… [改行]
[改行](空改行)
……

空改行までを 1 レコード,[改行] 区切り.情報内の改行をエスケープする必要あり.


#速度と手間を考えなければ xml が汎用性があってよい.
#どうせなら MySQL を…




・他の類似画像検索ソフト (外部リンク:リンク先はこのサイトとは無関係です)



・現状の問題点

線画の分解能の不足(8x8, 16x16 で不足)
32x32 で十分か?,64x64 が必要?
32x32, 64x64 では全体の速度が著しく低下する.
カラー情報を捨てて,輝度で判定する.ビット深度は 4 bit/cell, 8 bit/cell を検討.

32x32x4 bit = 512 byte
32x32x8 bit = 1024 byte

画像サイズ(複雑性)により作成グリッドサイズを切り替える.異サイズグリッド同士の比較.
複雑性は,セルを構成するピクセルの分散を見る.


GIF で明らかに同じような画像なのに,一致率が異常に低くなる場合がある. GDI+.dll での背景色関連の処理の関係かもしれない.


セルを構成するピクセル輝度の分散が無く,2つのセルのピクセルの平均色が同じなら,2つは同じセル.背景色とみなして,スキップ.



主要な修正事項 / lasted main fix.

・既知のバグと修正 / known bugs & fix

Delete ボタンで削除しようとすると,特定のファイルでエラーになる(GRID がファイルをロックしている) (count 2) .fixed since 000r7
Search2, Search3 において, "重複画像を検索 (同じバイナリ)" で常に未発見になる.fixed since 000s2
Search2 において,初回の検索で常に未発見になる.fixed since 000s2
ResultView で高輝度の画像グループを表示しようとすると落ちる (count 3).fixed since 000s3
ResultView を開いた瞬間に落ちる (count 2).fixed since 000s4
Search2 において,Path2 画像ロード時の表示がおかしかったのを修正.fixed since 000s5
ResultView: 「Delete this Group」を修正.fixed since 000s8
「キャッシュ更新>>」で空フォルダに古いキャッシュが残ったままになる.(count 2) fixed since 000s9
SendTo メニューの最上段を選択すると,ソートになる問題を修正.fixed since 000s10
SendTo メニューに空白のあるファイルパスを送れない不具合の修正.fixed since 000s10
ResultView: ウインドウに隠れていたサムネイル画像が更新されない. (count -1).fixed since 000s10
ResultView: Exif InfoText.dll で delete 等でファイルが存在しない場合,落ちる.fixed since 000t1
Intensity Dif% 0.0 で検索すると落ちる.fixed since 000v
ResultView で左クリックしたファイルがロックされ,削除できなくなるバグの修正.fixed since 000w2 (10.03.07)
ResultView の grouped images で,画像の無い場所で左クリックした場合マウスがキャプチャされたままになる.fixed since 000w3 (10.03.13)
キャッシュ形式を変更して以来 "Delete Unlinked Cache >>" が動作しない不具合の修正.fixed since 000w4 (10.03.30)
Grouping をマルチスレッドで行うと,検索元画像が取り除かれた場合にグループが取り除かれないバグの修正.fixed since 000w4 (10.03.30)

コメント検索中に他のスレッドを起動するとたぶん落ちる (count 0).waiting for fix...
特定のファイルを GDIplus で扱えない, (count -1).waiting for fix...


・更新メモ / update memo

InfoText.dll etc since 000s4
ResultView: サムネール上ホイールでスクロール etc since 000s6
Cache Control: LoadFromResult, LoadFolderCache since 000s6
ResultView: SendTo メニュー since 000s7
外部からの操作コマンド,タスクトレイ since 000s7, temporary implemented, details in here.
temp フォルダを追加 etc. since 000s11
ResultView: Exif InfoText.dll を追加. since 000t
Search1, Search2: マルチスレッド分割処理 since 000t
Search3: マルチスレッド分割処理 since 000t2

テスト実装,マルチコアでは比較処理速度が理論値で倍になるハズ.


論理 Processer 数を入力.Auto detect = 0, Single core = 1, Dual core = 2, Quad core = 4, Quad core x Dual socket = 8. (Detected numder is set as default.)
Default では検出された論理 Processer 数を設定. since 000t2
Default では,マルチコアの場合は検出された論理 Processer 数 ×2を設定. since 000v
Default では検出された論理 Processer 数を設定,に戻した. since 000w
+++ マルチスレッド動作時はスレッド分割数を増やす毎に Grouping で結果が若干変わる場合があります.+++

ResultView: SortByFileName を追加.全グループソートを追加.since 000t3
キャッシュをバイナリ形式に変更 (高速化).since 000u
複数フォルダ対応.since 000u
ResultView の結果の保存/復帰 (Save/Load ボタン).since 000u
ビューアを指定.since 000v
ResultView から画像を他のアプリケーションなどに Drag&Drop (not OLE) since 000v
ResultViewer を指定.since 000v
アイコン追加 since 000w (10.03.07)
設定ファイルで ResultView で表示されるサムネイル画像サイズ,画像数を起動時に指定できるようにした. since 000w3 (10.03.13)
Preset.txt で独自のプリセットを作製できるようにした.since 000w3 (10.03.13)
サムネイル画像サイズの最低値を 140 にした.since 000w4 (10.03.30)



・用語(整理中)
類似画像 (similar image): 見た目が同じような画像(部分的に違う画像も含む).
重複画像 (duplicated image): 同じバイナリファイル.(FileMD5)
同じ画像 (same image): バイナリが違っても同じピクセルの画像(コメント付き jpeg, BMP と PNG などのファイル形式違い).(PixcelMD5?)

similar image: images looks like same (include graphically duplicated images).
duplicated image: images had same binary (completely duplicated file). (FileMD5)
same image: images had same pixcels (completely graphically duplicated images). (PixcelMD5?)




・検討課題

現在の作業: プログラム内部構造の整理 (随時). (progress..)

当面の目標0: 完全なマルチランゲージ仕様.Perfect Multi language.(High priority) (complete)
当面の目標1: GRID cache のエクスポート,インポート(DVD disk 等に保存した,参照できない画像をキャッシュから検索).(重要度高) (complete)
当面の目標2: GRID cache と画像情報の関連付け.(重要度中)
当面の目標3a: より高速な比較アルゴリズムの実装1.(重要度高)(complete)
当面の目標3b: より高速な比較アルゴリズムの実装2.(予定なし)
当面の目標3c: より高速な比較アルゴリズムの実装3 (PostGridCompare).(重要度中)
当面の目標4: より汎用的なデータ構造(特に ResultData).(重要度高)(complete)
当面の目標5: ゴミキャッシュの削除.(重要度中)(complete)
当面の目標6: "Delete" を全て元に戻す.(重要度低)(complete)
当面の目標7: ビューアを指定.(重要度低)(complete)
当面の目標8a: cache file の load 高速化1.(重要度低)
当面の目標8b: cache file の load 高速化2, binary data.(重要度低)(complete)
当面の目標9: 複数フォルダの読み込みにデフォで対応 (complete)
当面の目標10: HashFileDB の導入.(pending)
当面の目標11: GridCompare() 比較関数に Score 方式を導入.(progress..)


検討課題1: 元画像のサイズ(複雑性)に対して最適なグリッド作成と異サイズグリッド同士の比較.(pending)
検討課題2: grouping 後に,グループ同士の類似度によってグループをマージする.(pending)
検討課題3: 書庫(zip, lzh)ファイル内からの検索. (complete)
検討課題4a: Susie plugin 00IN の対応. (complete)
検討課題4b: Susie plugin 00AM の対応. (pending)
検討課題5: GridCompare の外部 dll 化.(progress..)
検討課題6: 検索 preset の外部 text 化 (編集可).(complete)
検討課題7: 比較ウィンド.(pending)
検討課題8: 比較マルチスレッド化(マルチコア等に対応).(complete)
検討課題9: 比較対象をファイルサイズ,作成・更新日時,イメージサイズ等で制限する.(progress..)
検討課題10: database を SQLite にして,DHFiND と一部共用にする.(progress..)

実験予定1: 画像を 128*128 程度に縮小後,平面微分により線画を抽出.対角線を引いて交差する点の位置と数を保存.これを情報として保持.類似検索に用いる.検討課題は,線の数と保存する点の最大数.
実験予定2: グレイスケール Grid での比較( 4 bit,or 8 bit/cell).色情報を捨て,セル数を稼ぐ.
実験予定3: 平面微分により線画を抽出した後に 32x32 で分割し,分割セル毎の平均輝度情報を保存する.

注意点: GRID size の再考.

#重要度は私見です.重要度と実装される順番に関連はありません.



・正式版 (version 1.0) までに必要なこと.
アイコン.(complete)



・テスト公開
GRID000w4


・開発環境

CPU: AthlonXP2000+
Memory: DDR-SDRAM 1024 MB (1 GB)
HDD: Seagate ST3120022A (Total 120 GB, System + 20 GB of image datas + alpha )

Development tool: Microsoft Visual C++ 2005 Express edition
OS: Microsoft Windows 2000





10) Benchmark

ベンチマーク用データ GRID16, 000u 以降, ランダム 16x16 Grid 2万データ.
G16Rand20000.dat (16x16 grid random data) download
  1. ダウンロード後、解凍して ExtraCache フォルダに入れます.
  2. GRID16 を起動して,「Expand>>」ボタンを 5 回ほど押します.
  3. 「CacheControl」の「AddCache...」ボタンを押して G16Rand20000.dat を選択して読みます.
  4. 一番上の「類似画像をグループ化」にある「検索開始>>」ボタンをクリックします.
sample01
CPU: AthlonXP2000+ (1.66GHz)
Memory: 1GB
OS: Windows2000
version: 000v, Grid16, default setting
Data: G16Rand20000.dat
Result: Similar image not found. elapsed 21 min 40 sec.

sample02
CPU: AthlonXP2000+ (1.66GHz)
Memory: 1GB
OS: Windows2000
version: 000v, Grid8, default setting
Data: G8Rand20000.dat
Result: Similar image not found. elapsed 2 min 41 sec. 
・ランダムデータは Grid16.exe /MakeRandomCache=20000 の様にして作製できます.データは ExtraCache フォルダに出力されます.



11) その他 / Others

ゲストブックへ