问题是: 对于两个足够大的图片,判定他们是否完全相同。 如何选用最少的像素点来判断他们完全相同。 对于不完全相同的,又如何通过最少的迭代次数找出所有相同的点? 因为像素是数据,排列是图像,那么就无法搞出个公式出来,也就没法儿证明是否二阶可导,也就没法证明到底是npc,还是nphard。 就是这个问题,恳请指教!
我很好奇,你为啥要弄这些计算复杂性的东西啊? 这东西没啥用,只是告诉你算法是属于P还是NP的。然后属于NP的就是无解的... 所以研究计算机理论的人很没劲,一天到晚在研究什么东西是无法解决的... 其实许多算法,都是NP的,但并不能因为NP就不想办法去计算它。
一般是用贪心法来解。例如邮递员问题,是个典型的NP问题。(http://zh.wikipedia.org/zh-sg/旅行推销员问题)。 对于这种问题,很显然贪心法是能解的,但是肯定不是最有解。 一般NP问题的近似解只要是较优解,就能接受了~ 要获得比贪心更好的解,通常需要改进贪心法的局部最优问题, 因此需要用各种迭代算法。比如遗传算法、蚁群算法之类的。 其实说穿了,这类算法的本质都是穷举。
我的意思是,所有的基于搜索的算法的本质,都是穷举。只不过与穷举相比,过滤掉不少不需要的搜索路径。然会根据过滤的方法不同,产生了各种各样的算法,深度优先,广度优先,A*,分支定界,动态规划,遗传、蚁群、退火之类的。 我想知道的是,你具体要弄个什么算法,会有可能是NP,还需要近似解。
什么问题啊?本文的这个图像匹配问题么?这个我不是在另一个thread给出解答了么... 另外什么叫“什么算法可以不定解集元素数”啊?你是指哪些算法对问题规模没有限制吧~ 算法本身对问题的规模是没有限制的。只不过不同的算法对同一个问题需要消耗的时间和空间不同。 从而导致实际不可解。
在图像处理技术中,通常做法可能是先找出每个图片的重心坐标系;把图片在重心上旋转对齐,可能还要加上缩小放大,以及色彩灰度处理。然后可以用二维Fourier变换之类的东西,把图片变成频谱。有了频谱,再用均方差之类的方法来比较两个图片的差异。
这样是不行滴~ 你的方法最大的问题: 重心选择+旋转缩放,需要估计的参数太多了, 重心在哪里,旋转多少,放缩多少, 任何一个错了,后面就对不上了。 图片匹配算法,一般都是选用旋转、放缩无关的算法来做的。比如: 先做一次小波变化寻找图像边缘 然后分析边缘的拐点,直线特征 最后提取这些特征的位置信息,生成特征描述。 特征描述一般用特征A被哪些特征包围这样的描述方式,从而回避了旋转问题。 然后在一系列特征描述中搜索匹配的图。 最后在候选的图中,做色域上的直方图匹配,确保色彩也是匹配的。 当然我也只是随便想想给出一种方法,可能的方法也不止这一种。
最优化方法的话,只有一个解集,而解集内的元素数即像素点数,是固定的。 可是呢,实际情况是我不知道那两个图有多少相同的像素点数。 而大侠上面的种种方法,基本属于此类。而对于第一个,则是要全部像素点都要处理一遍然后再搞滴。
什么叫尽可能少的像素点.... 任何算法至少要遍历数据集一遍,才能有结果吧。 除非你这个数据集里面前面的数据包含了后面的信息。比如你已知是个排序的队列,那么你可以在不完全遍历所有的数据情况下,找出某个值。 换个说法吧,比如两本500页的书,其中一本里面有若干页是错的。你必须要把整部书都翻一遍,才能找出那些页是不同的。没有任何算法,能让你翻100页就能确定结果。如果有,那就是超能力了...