随笔-20  评论-12  文章-0  trackbacks-0
使用方法:先执行dir *.jpg *.bmp /b /s > imgcmp.lst,然后替换掉原来的imgcmp.lst双击执行imgcmp.exe.
哈哈windows目录下面相同或者相似的文件还是蛮多的嘛.
阈值是相关度判断是否是相似图片的阈值,块大小是图片的分块像素大小.
可执行文件下载:
下面是截图欣赏:





  1 RBT<Pair<String,String> > img_map;
  2 Int g_limit = 2;
  3 Int g_block = 32;
  4 
  5 RGBQUAD pixel_comp(CxImage* pImageSrc, CxImage* pImageDst,Int& nResult,Byte limit = 20)
  6 {
  7     Int src_row = pImageSrc->GetHeight();
  8     Int src_col = pImageSrc->GetWidth();
  9     Byte* src_buffer = pImageSrc->GetBits();
 10     Int dst_row = pImageDst->GetHeight();
 11     Int dst_col = pImageDst->GetWidth();
 12     Byte* dst_buffer = pImageDst->GetBits();
 13     RGBQUAD ret = {-1,-1,-1,-1}, max_ret = {0};
 14     if(src_row!=dst_row || src_col!=dst_col) 
 15     {
 16         nResult = (dst_row+2)*(dst_col+1)-(src_row+2)*(src_col+1);
 17         return ret;
 18     }
 19 
 20     Double r = 0,g = 0,b = 0,s = 0;
 21     Double abs_r = 0,abs_g = 0,abs_b = 0,abs_s = 0;
 22     Char delta_r = 0, delta_g = 0, delta_b = 0;
 23     Int Block_Row = g_block;
 24     Int Block_Col = g_block;
 25 #define Abs(x) ((x)>=0?(x):-(x))
 26     for(Int i=0; i<(src_row+Block_Row-1)/Block_Row; i++)
 27     {
 28         for(Int j=0; j<(src_col+Block_Col-1)/Block_Col; j++)
 29         {
 30             Double l_r = 0,l_g = 0,l_b = 0,l_s = 0;
 31             Double l_abs_r = 0,l_abs_g = 0,l_abs_b = 0,l_abs_s = 0;
 32             for(Int k=0; k<Block_Row; k++)
 33             {
 34                 for(Int l=0; l<Block_Col; l++)
 35                 {
 36                     register Int row = i*Block_Row+k;
 37                     register Int idx = j*Block_Col+l;
 38                     if(row>=src_row || idx>=src_col) continue;
 39                     idx += row*src_col;
 40                     delta_b = dst_buffer[idx*3  ]-src_buffer[idx*3  ];
 41                     delta_g = dst_buffer[idx*3+1]-src_buffer[idx*3+1];
 42                     delta_r = dst_buffer[idx*3+2]-src_buffer[idx*3+2];
 43 
 44                     l_b += (delta_b);
 45                     l_g += (delta_g);
 46                     l_r += (delta_r);
 47 
 48                     l_abs_b += Abs(delta_b);
 49                     l_abs_g += Abs(delta_g);
 50                     l_abs_r += Abs(delta_r);
 51                 }
 52             }
 53             if(    (max_ret.rgbBlue =(Byte)l_abs_b/Block_Row/Block_Col)>limit ||
 54                 (max_ret.rgbGreen=(Byte)l_abs_g/Block_Row/Block_Col)>limit ||
 55                 (max_ret.rgbRed  =(Byte)l_abs_r/Block_Row/Block_Col)>limit )
 56             {
 57                 return max_ret;
 58             }
 59 
 60             b += l_b;
 61             g += l_g;
 62             r += l_r;
 63 
 64             abs_b += l_abs_b;
 65             abs_g += l_abs_g;
 66             abs_r += l_abs_r;
 67         }
 68     }
 69 #undef Abs
 70     max_ret.rgbRed = (Byte)(abs_r/src_row/src_col);
 71     max_ret.rgbGreen = (Byte)(abs_g/src_row/src_col);
 72     max_ret.rgbBlue = (Byte)(abs_b/src_row/src_col);
 73     nResult = (Int)((r+g+b)/src_row/src_col);
 74     return max_ret;
 75 }
 76 
 77 template <typename T>
 78 T jabs(T t)
 79 {
 80     if((t | ((T)(-1)>>1)) == (T)(-1))
 81         return 0-t;
 82     else
 83         return t;
 84 }
 85 
 86 Int symbol(Int p)
 87 {
 88     return p>=0?p:-p;
 89 }
 90 
 91 CStr next_sub(CStr pchSrc, Char match = '\\')
 92 {
 93     int len = strlen(pchSrc);
 94     for(int i=len-1; i>=0; i--)
 95     {
 96         if(pchSrc[i]==match)
 97             return pchSrc+i+1;
 98     }
 99     return 0;
100 }
101 
102 Int img_comp(CStr pchFileSrc,CxImage* img_src,CStr pchFileDst,CxImage* img_dst,Byte limit = 2)
103 {
104     CStr tmp_str = Nul;
105     if(strcmp(pchFileSrc,pchFileDst)==0return 0;
106     if(!img_src->IsValid())
107     {
108         printf("parse image (%s) failure!\n",pchFileSrc);
109         throw "parse image failure!";
110     }
111     if(!img_dst->IsValid())
112     {
113         printf("parse image (%s) failure!\n",pchFileDst);
114         throw "parse image failure!";
115     }
116     Int nResult;
117     RGBQUAD t = pixel_comp(img_src,img_dst,nResult);
118 
119     if(*(Int*)&== -1// 长宽不同,则按名字排序
120         return (Int)nResult;
121     else if(jabs(t.rgbBlue)<limit && jabs(t.rgbGreen)<limit && jabs(t.rgbRed)<limit && jabs(t.rgbReserved)<limit)
122     {
123         if(strcmp(pchFileDst,pchFileSrc)!=0)
124         {
125             img_map.Insert(Pair<String,String>(String(pchFileSrc),String(pchFileDst)));
126             img_map.Insert(Pair<String,String>(String(pchFileDst),String(pchFileSrc)));
127         }
128         return 0;
129     }
130     else 
131         return (Int)nResult;
132 }
133 
134 class ImageCmp
135 {
136 public:
137     Bool operator<(ImageCmp& img)
138     {
139         try{
140             return img_comp(_img_src.ConvertToCStr(),_img,img._img_src.ConvertToCStr(),img._img,g_limit)<0;
141         }catch(){return False;}
142     }
143     CStr GetSrc()                                                                        { return _img_src.ConvertToCStr(); }
144     ImageCmp(CStr pchImgSrc) : _img_src(pchImgSrc)
145     {
146         _img = New CxImage(pchImgSrc,CxImage::GetTypeIdFromName(next_sub(pchImgSrc,'.')));
147     }
148     ImageCmp(const String& sImgSrc) : _img_src(sImgSrc)
149     {
150         CStr tmp_str = Nul;
151         _img = New CxImage(sImgSrc.ConvertToCStr(),CxImage::GetTypeIdFromName(next_sub(sImgSrc.ConvertToCStr(),'.')));
152     }
153     ImageCmp()                                                                            {_img = New CxImage();}
154     AutoPtr<CxImage> _img;
155 protected:
156     String _img_src;
157 };
158 
159 int main()
160 {
161     printf("阈值:");
162     scanf("%d",&g_limit);
163     printf("块大小:");
164     scanf("%d",&g_block);
165     CStr name_cfg = "imgcmp.lst";
166     Char buffer[MAX_PATH+1= {0};
167     Vector<ImageCmp> vec_file;
168     FILE* file_cfg = fopen(name_cfg,"r");
169     printf("loading.");
170     if(file_cfg)
171     {
172         String last;
173         while(!feof(file_cfg))
174         {
175             String tmp;
176             fgets(buffer,MAX_PATH,file_cfg);
177             tmp = buffer;
178             tmp.Trim();
179             if(!tmp.IsEmpty() && tmp!=last)
180             {
181                 vec_file.PushBack(tmp);
182                 printf(".");
183             }
184             last = tmp;
185         }
186         fclose(file_cfg);
187         file_cfg = Nul;
188     }
189     printf("\nParsing\n");
190 
191     fast_sort<ImageCmp,Vector<ImageCmp> >(vec_file,0,vec_file.GetSize()-1);
192     printf("results:\n");
193     
194     FILE* html = fopen("output.html","w");
195     fprintf(html,"<HTML><HEAD><TITLE>图片相似度搜索</TITLE></HEAD><BODY>\n");
196     Bool has_line_draw = False;
197     String last_name;
198     for(UInt i=0; i<vec_file.GetSize(); i++)
199     {
200         RBT<Pair<String,String> >::Iterator iter = img_map.Search(vec_file[i].GetSrc());
201         if(iter)
202         {
203             if(!last_name.IsEmpty())
204             {
205                 Bool found = False;
206                 RBT<String> src_map,dst_map;
207                 typedef RBT<String>::Iterator map_iter;
208                 for(RBT<Pair<String,String> >::Iterator iter=img_map.Search(last_name);iter;iter=img_map.Search((*iter).GetVal()))
209                 {
210                     map_iter it = src_map.Search((*iter).GetKey());
211                     if(it)
212                     {
213                         break;
214                     }
215                     src_map.Insert((*iter).GetKey());
216                 }
217                 for(RBT<Pair<String,String> >::Iterator iter=img_map.Search(vec_file[i].GetSrc());iter;iter=img_map.Search((*iter).GetVal()))
218                 {
219                     if(src_map.Search((*iter).GetKey()))
220                     {
221                         found = True;
222                         break;
223                     }
224                     map_iter it = dst_map.Search((*iter).GetKey());
225                     if(it)
226                     {
227                         break;
228                     }
229                     dst_map.Insert((*iter).GetKey());
230                 }
231                 if(!found)
232                 {
233                     fprintf(html,"<hr>\n");
234                 }
235             }
236             printf("%s Same with %s \n",vec_file[i].GetSrc(),(*iter).GetVal());
237             fprintf(html,"<a href='file:///%s'>%s</a><br>\n",vec_file[i].GetSrc(),vec_file[i].GetSrc());
238             has_line_draw = False;
239             last_name = vec_file[i].GetSrc();
240         }
241     }
242     fprintf(html,"</body></html>");
243     fclose(html);
244     ShellExecute(Nul,"open","output.html",Nul,Nul,SW_SHOW);
245     return 0;
246 }
247 

posted on 2009-02-04 12:06 宋振华 阅读(2937) 评论(3)  编辑 收藏 引用

评论:
# re: 相似图像搜索(算法) [原创] 2009-02-04 19:19 | Dancefire
算法上很奇怪,求每一个块的颜色数的差。首先是无法处理经过缩放的图片,其次是无法处理整体调暗或调亮或者转色的图片,而且求的是平均值而不是常用的SSE?

为什么不考虑用离散余弦求出最显著的特征,缩小至特定大小后,使用HSV(而不是RGB)来分通道比较并且综合其结果呢?这样起码转色、缩放、JPG按照不同质量保存或者换图像格式、调明暗之类的问题基本上都可以处理的。

可以看一些关于模式识别、数据挖掘和图像处理的书,应该对上述问题都有介绍。  回复  更多评论
  
# re: 相似图像搜索(算法) [原创] 2009-02-04 20:57 | 宋震华
@Dancefire
很不错的建议,这个版本的原始需求的仅仅是提供相似图像的快速搜索匹配.
另外一个目的是检验基本类库稳定性,后续的版本可以考虑采用一些更加优秀并且高效的算法,毕竟需要匹配的图片数量可能随时超过10的3次方.
分块的目的就是为了快速筛选不相似的图片.

缩放后的图片可以考虑缩放M:N匹配规则,没有考虑图像转换的主要原因是效率.
谢谢指点.  回复  更多评论
  
# re: 相似图像搜索(算法) [原创] 2009-02-05 22:19 | Bill Hsu
很强  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理