rt,要求两幅图的相关性,假设两幅图分别为f,g。相关公式为:
[attach]3229[/attach]
其中F(x,y),G(x,y)是两幅图像,Fm,Gm是两幅图的均值,下标欧米伽表示对整个区域计算。
具体的讲:假设图F(x,y)为F=[1,2,3;4,5,6;7,8,9],图G(x,y)为G=[2,1,4;5,1,1;2,1,1];具体做法是先每幅图都减去其均值,比如对于图F:
1):先求其均值Fm=(1+2+3+…+9)/9=5;
2):每个元素减去均值Fm得到矩阵F’=[-4,-3,-2;-1,0,1,2,3,4];
3):对于图G做相同操作。得到矩阵均值Gm=2,减去均值的矩阵G‘=[0,-1,2;3,-1,-1;0,-1,-1];
4):带入上面公式就可以得到相关系数c。
但是现在有下面几个问题:
1):一般来讲是对两个30*30的矩阵做相关,我现在是把矩阵做为一个块,每个像素做为一个线程来做。因为实际中其实还要找F中每个像素在G中的对应关系,这个比较复杂,所以感觉不适合用一个线程来做一个矩阵;
2):在一个像素对应一个线程的基础上,在带入公式的过程中有两个问题:
a:因为这里涉及到多次线程块里面的线程求和,用什么方法比较好。这里是否合适用规约方法求和呢?
b:因为这个均值是一个矩阵的线程共用的,是否需要把它定义成share变量;
谢谢。。
LZ您好:
求均值可以通过并行规约实现,这不是个问题。
以及请您说明一下您公式分子和分母中的求和的具体形式(给出具体公式或伪码或串行代码均可)。您这个形式过于笼统了,看不出是点乘求和形式的还是一点对多点相乘求和的。以及多年不看概率统计,已经忘记了相关的专业知识,无法自行脑补了。
如果是点乘形式的,是十分便于处理的。
大致如此,期待您的回帖。
祝您好运~
LZ还没有回复,我再稍微写点。
如果您那个乘法是矩阵相乘的形式,或者是卷积的形式,那么依然可以并行实现的,此时使用shared memory效果会好一些。
所以您的计算步骤大致为:
0:您可以考虑一个block甚至一个warp计算一个矩阵分块。
1:针对每个矩阵分块,并行规约求出均值。
2:并行实现每个分块的相乘求和,其中分子需要计算一个和,分母需要计算两个。并开方做后处理。
3:得出最后结果。
大致如此,待LZ给出公式中相乘的具体形式,即可最终判断并确定实现方式。
祝您好运~
楼主的:
“因为实际中其实还要找F中每个像素在G中的对应关系”,
这个是个神马操作?为何在你的公式里面没有体现?
是否是F不确定,然后在G中进行搜索出来F块?
我和ICE的意见一致,您先说明白问题,然后再考虑实现和优化。
嗯。。谢谢斑竹。中午回去睡午觉去了。。o(╯□╰)o。。现在才来。。罪过罪过。。
1:这里乘法是矩阵相乘,具体的讲就是对应点相乘然后求和。比如上面的
F’=[-4,-3,-2;-1,0,1,2,3,4];G‘=[0,-1,2;3,-1,-1;0,-1,-1];带入公式有:分子的具体形式如下:
(-4)0+(-3)(-1)+(-2)2+(-1)(3)+…+4*(-1),分母是类似的。因为在算法中要进行多次的这种形式的计算,想知道用 规约是不是最有效的?
2:而且因为求出来的均值是block共有的,不知道这里是否定义成share,以及这样的区别是什么?
3:还有个问题,如果我一个块中有一个线程不符合要求,我就要结束这个块,并且给这个块的共享数组赋值为0,请问一下这个该怎么写
4:我后面把自己写的代码发上来,还望斑竹都给指导。。可能写的很不好。。o(╯□╰)o。。谢谢
嗯。。先谢过斑竹。本来怕问题比较多,麻烦斑竹了。。所以有的地方就没有讲,这样的话我就详细的说一下。假设有两幅图A和图B,其中图B是图A经过变形得到的,这里的变形是指包括拉压、剪切等方法造成的变形,而我要做的是找两幅图像素点的对应关系,从而得到变形。具体的步骤有:
[attach]3233[/attach]
1):对图A进行分块,假设图1是图A的一个小块,要求图1中每个点在图B中的对应点。假设对应关系是已知的如下:
x‘=x+u+uxi+uyj;
y’=y+v+vxi+vyj
其中这里u,ux,i,uy,j,v,vx,vy 假设是已知的,,那么可以通过该公式求出图1中的点与图2的对应点,但是有个问题就是这样算出来的x‘,y’一般都是小数,必须对图2进行图像插值从而得到B(x’,y‘)d的值。
2):把上面得到的B(x’,y‘)组成一个块,那么用1#的公式计算相关系数,从而判定两幅图的相关程度。
3):问题的前一段基本如上面1,2点所述。。后面的我在整理整理,后面把代码发上来比较好讲。。谢谢
楼主看到你午睡后的补充信息了:
我已知:
(1)对图像2中的每个3x3的块m1,可以通过x’ = f(x,y)和y’ = g(x,y)的关系,得到图像1中的块m2.
f()和g()均是对x,y的线性函数。
(2)需要对块m1和块m2求平均值avg1和平均值avg2(即所有元素的和除以9)
(3)计算m1’ = m1 - {avg1}和m2’ = m2 - {avg2}
(4)计算m1’ 点乘 m1’,然后求的和k1。计算m2’ 点乘 m2’ ,然后求的和k2。计算m1’ 点乘 m2’ 然后求的和k3。
(5)计算C = k3 / sqrt(k1 * k2)
这是对楼主的问题描述的整理。
(3)对应的每个(x,y)和(x’,y’) (后者可能需要插值得出,但您没给出插值公式,这里假设是线性临近插值)。
LZ您好:
首先声明一下,这里的答复仅限于您1#和5#的描述,以及认为F,G这两幅图是已知的,不考虑G的生成和插值以及讨论在此前提下您1#中相关系数C的求解。
那么:
1.1:根据您的描述,这个是矩阵对应元素的乘法,又称为点乘(类似于矢量的点乘),而不是您文字表述的矩阵的乘法。
1.2:这种点乘用CUDA是十分容易实现的,只需要安排线程铺开合并读取并计算乘法,之后局部规约求和即可。(所谓局部指的是,如果您一个分块的乘法是一个block计算的,那么是block内规约;如果是一个warp实现的,那么是warp内部规约)
如果您前面计算元素相乘的读取是合并的,以及后面使用的规约操作,效率应该是可以的。
2:这里需要将计算的均值结果写在shared memory里面,这样才是整个block的线程都可见的。(以及原则上写到global memory里面整个block线程也是可见的,但是global memory较慢。)以及您在您的问题2中最后问的区别指的是?
3:一个线程无法直接干掉一个block的,或许可以通过标记+反复判断的方法实现,但是我尚未想到较好的方法。以及,如果一个block结束了,那么他的shared memory也随之释放,无所谓赋值为0还是不赋值。
大致这样,祝您好运~
那么我们看这个过程的这些计算:
(1)用你的一个block对于一个块的做法,每个线程读取G中的块的每个点的值。以及求坐标变换,每个线程对G的块进行坐标变换,得到F中的坐标,同时进行插值读取(一般是临近的2个或者4个或者8个像素),然后进行插值出来值。这个用你的方式挺好,个人干个人的,同时进行。
(2)每个线程读取(x,y)和(x’,y’)的值后,将此2个块的所有元素写入shared memory, 然后大家集体规约求出平均数avg1和avg2,然后将avg1和avg2的值传播到每个线程,你的做法也挺好。
(3)每个线程分别将自己之前的(x,y)和(x’,y’)点的值减去avg1和avg2(这里假设得到t0和t1值), 分别计算t0^2 , t1^2 , t1xt2这三个值,大家都在并行,楼主这样做也挺好。
(4)将这三个值写入shared memory, 然后block规约得到和k1,k2,k3,楼主这样做也挺好。
(5)然后随意选出一个线程,将shared memory中的k1,k2,k3计算出C= k3 / sqrt(k1 * k2),别最终保存结果。楼主这样也挺好。
因为楼主的5个步骤不是分头计算就是block规约,没啥不好的。
所以您可以直接实现的。
(至于是否有更好的做法那是另外一个问题,您这个做法就不错)。
以及,只有3x3的小区域太小,对CUDA的一个这样的block(9线程)不合算,您可以尝试考虑将多个小区域的计算合并起来,弄上较大的block shape.