Dear all,

    有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形？就是类似
于Linux下的3D桌面转动时候的效果，我想用2D模拟一个这种效果， 我尝试过很
多，但效率都差强人意。 我目前的做法是从网上找的一些投影原理，按照角度来
算，然后一个像素一个像素的取，但是效率极差，基本都到O（n^2）了，请问有没
有更好的算法？  

    把这个问题简化一下：就是要把一个矩形变成一个等腰梯形，就像GIMP中
Perspective Transformation Matrix 那样。


Thanks
Kermit

On Fri, 2009-12-18 at 01:38 -0700, Kermit Mei wrote:
> Dear all,
> 
>     有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形？就是类似
> 于Linux下的3D桌面转动时候的效果，我想用2D模拟一个这种效果， 我尝试过很
> 多，但效率都差强人意。 我目前的做法是从网上找的一些投影原理，按照角度来
> 算，然后一个像素一个像素的取，但是效率极差，基本都到O（n^2）了，请问有没
> 有更好的算法？  
> 
>     把这个问题简化一下：就是要把一个矩形变成一个等腰梯形，就像GIMP中
> Perspective Transformation Matrix 那样。

哎，这个问题貌似没这么简单。下午搜索了很多资料，这是个矩阵变换的问题，看
来我得回去好好研究一下线性代数了，呵呵。

2009/12/18 Kermit Mei <kermit.mei在gmail.com>:
> On Fri, 2009-12-18 at 01:38 -0700, Kermit Mei wrote:
>>     有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形？就是类似
>>     把这个问题简化一下：就是要把一个矩形变成一个等腰梯形，就像GIMP中
>> Perspective Transformation Matrix 那样。
>
> 哎，这个问题貌似没这么简单。下午搜索了很多资料，这是个矩阵变换的问题，看
> 来我得回去好好研究一下线性代数了，呵呵。

矩阵变换其实就是一个仿射变换或者射影变换:
在仿射变换中  X1 = A * X + C
X是初始点，X1是变到的点，都是二维向量，A是一个2x2的非退化矩阵，C是位移向量。

射影变换复杂一些，每个点可以用三个分量表示，变换矩阵A是3x3的非退化矩阵，变换式为   X1 = A * X
三位向量的含义：设X = (x, y, z)' ，那么 z!=0时 X就代表点(x/z, y/z)。

希望能有所帮助。

On Sun, 2009-12-20 at 12:43 +0800, guo yixuan wrote:
> 2009/12/18 Kermit Mei <kermit.mei在gmail.com>:
> > On Fri, 2009-12-18 at 01:38 -0700, Kermit Mei wrote:
> >>     有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形？就是类似
> >>     把这个问题简化一下：就是要把一个矩形变成一个等腰梯形，就像GIMP中
> >> Perspective Transformation Matrix 那样。
> >
> > 哎，这个问题貌似没这么简单。下午搜索了很多资料，这是个矩阵变换的问题，看
> > 来我得回去好好研究一下线性代数了，呵呵。
> 
> 矩阵变换其实就是一个仿射变换或者射影变换:
> 在仿射变换中  X1 = A * X + C
> X是初始点，X1是变到的点，都是二维向量，A是一个2x2的非退化矩阵，C是位移向量。
> 
> 射影变换复杂一些，每个点可以用三个分量表示，变换矩阵A是3x3的非退化矩阵，变换式为   X1 = A * X
> 三位向量的含义：设X = (x, y, z)' ，那么 z!=0时 X就代表点(x/z, y/z)。
> 
> 希望能有所帮助。

恩，谢谢提示！ 我再学习一下，现在才意识到线代功底不行关键时候是要掉链子
的:)

2009/12/18 Kermit Mei <kermit.mei在gmail.com>:
> Dear all,
>    有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形？就是类似
> 于Linux下的3D桌面转动时候的效果，我想用2D模拟一个这种效果， 我尝试过很
> 多，但效率都差强人意。

准确的说，这个问题的运算目前都是用 GPU 完成的。因为大量的并行运算与浮点运算是GPU的强项。

简单的说，只讲究效率不讲究效果的话这个问题其实可以非常简单：你只要按比例抽取一定像素走就可以。当然，如果你需要消除锯齿和平滑缩放的话，估计是非GPU不可的，建议直接找3D相关函数完成吧。

On Tue, 2009-12-22 at 16:14 +0800, pan shizhu wrote:
> 2009/12/18 Kermit Mei <kermit.mei在gmail.com>:
> > Dear all,
> >    有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形？就是类似
> > 于Linux下的3D桌面转动时候的效果，我想用2D模拟一个这种效果， 我尝试过很
> > 多，但效率都差强人意。
> 
> 准确的说，这个问题的运算目前都是用 GPU 完成的。因为大量的并行运算与浮点运算是GPU的强项。
> 
> 简单的说，只讲究效率不讲究效果的话这个问题其实可以非常简单：你只要按比例抽取一定像素走就可以。当然，如果你需要消除锯齿和平滑缩放的话，估计是非GPU不可的，建议直接找3D相关函数完成吧。

我要拿到板子上跑，别说GPU，就连CPU的效率都很底，比现在的2440慢多了。 所
以希望按照一定比例抽取像素……

但是我分析的效率最高的算法还是O(n^2)的，一直想找一个O(n)的……如果屏幕宽度
是320x240，那么每次图片大小都是320x240=76800。

Thanks
B.R
Kermit

2009/12/22 Kermit Mei <kermit.mei在gmail.com>:
> 但是我分析的效率最高的算法还是O(n^2)的，一直想找一个O(n)的……如果屏幕宽度
> 是320x240，那么每次图片大小都是320x240=76800。

你是说的O(n^2)指的是 76800^2么？

如果是这样的话，抽取算法确实是 O(n)的，假设你把 320x240 的图片变成 160
为顶边，320为底边，240为高的等腰梯形。那么你把第一行每两个点抽取一个点就可以了。剩下的可以依此类推，按比例抽掉一部分点，最后一行就还是320点不变，完工。

这样出来的图像效果是不好的，不过如果仅仅是用于动画的话，问题也不大。对于诸如两三百兆的嵌入式CPU，320x240最优状态达到5帧是可能的。――当然，如果你对动画的平滑度要求更高的话，那真的没办法了。毕竟你CPU性能摆那里在

On Tue, 2009-12-22 at 18:53 +0800, pan shizhu wrote:
> 2009/12/22 Kermit Mei <kermit.mei在gmail.com>:
> > 但是我分析的效率最高的算法还是O(n^2)的，一直想找一个O(n)的……如果屏幕宽度
> > 是320x240，那么每次图片大小都是320x240=76800。
> 
> 你是说的O(n^2)指的是 76800^2么？

不是，是320*240，一个for遍历320中要抽取的项，另一个嵌套在这个for里，遍历
240中要抽取的像素。


for(遍历要抽取的列) {
  for(遍历该列中每一个像素) ｛
     画这个点(x,y)
  ｝
}


我幻想得到一个遍历320次就能搞定的算法……貌似不合乎逻辑。

> 如果是这样的话，抽取算法确实是 O(n)的，假设你把 320x240 的图片变成 160
> 为顶边，320为底边，240为高的等腰梯形。那么你把第一行每两个点抽取一个点就可以了。剩下的可以依此类推，按比例抽掉一部分点，最后一行就还是320点不变，完工。
> 
> 这样出来的图像效果是不好的，不过如果仅仅是用于动画的话，问题也不大。对于诸如两三百兆的嵌入式CPU，320x240最优状态达到5帧是可能的。――当然，如果你对动画的平滑度要求更高的话，那真的没办法了。毕竟你CPU性能摆那里在

我的主频不到200兆……

2009/12/23 Kermit Mei <kermit.mei在gmail.com>:
> 不是，是320*240，一个for遍历320中要抽取的项，另一个嵌套在这个for里，遍历
> 240中要抽取的像素。
>
> for(240) {
>  for(320) ｛
>     画这个点(x,y)
>  ｝
> }
>
> 我幻想得到一个遍历320次就能搞定的算法......貌似不合乎逻辑。

从你的这个描述来看，你只遍历了一次，而不是320次。正确的定义是：把所有点访问一次，算作一次遍历。

On Wed, 2009-12-23 at 10:47 +0800, pan shizhu wrote:
> 2009/12/23 Kermit Mei <kermit.mei在gmail.com>:
> > 不是，是320*240，一个for遍历320中要抽取的项，另一个嵌套在这个for里，遍历
> > 240中要抽取的像素。
> >
> > for(240) {
> >  for(320) ｛
> >     画这个点(x,y)
> >  ｝
> > }
> >
> > 我幻想得到一个遍历320次就能搞定的算法......貌似不合乎逻辑。
> 
> 从你的这个描述来看，你只遍历了一次，而不是320次。正确的定义是：把所有点访问一次，算作一次遍历。

的确只遍历了一次，但单从代码上看，我算的是两个嵌套的for循环，这样下来粗
略地估计就是O(n^2)了。 要是能比这个再高效一些就好了……

2009/12/23 Kermit Mei <kermit.mei在gmail.com>:
>
> 的确只遍历了一次，但单从代码上看，我算的是两个嵌套的for循环，这样下来粗
> 略地估计就是O(n^2)了。 要是能比这个再高效一些就好了……

算法复杂度的标记不是你这样算的。作为图像处理来说，一个点遍历一遍，你这就是 O(n) 算法。

如果对于每一个点，都需要把整个图像遍历一遍。这才是 O(n^2)算法，它的复杂度是基于 76800*76800。

On Wed, 2009-12-23 at 11:04 +0800, pan shizhu wrote:
> 2009/12/23 Kermit Mei <kermit.mei在gmail.com>:
> >
> > 的确只遍历了一次，但单从代码上看，我算的是两个嵌套的for循环，这样下来粗
> > 略地估计就是O(n^2)了。 要是能比这个再高效一些就好了……
> 
> 算法复杂度的标记不是你这样算的。作为图像处理来说，一个点遍历一遍，你这就是 O(n) 算法。
> 
> 如果对于每一个点，都需要把整个图像遍历一遍。这才是 O(n^2)算法，它的复杂度是基于 76800*76800。

恩。我在猜想，即便是Frame Buffer最底层的操作，拿到一张图片要画出来也应该
是这个效率吧？ 它至少也要把所有像素遍历一次才行呐。