zeuux-universe  - 讨论区

标题:[zeuux-universe] 求助一个算法:如何把一个矩形图片压缩转换成一个等腰梯形?

2009年12月18日 星期五 16:38

Kermit Mei kermit.mei在gmail.com
星期五 十二月 18 16:38:21 CST 2009

Dear all,

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

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


Thanks
Kermit



[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月18日 星期五 18:08

Kermit Mei kermit.mei在gmail.com
星期五 十二月 18 18:08:59 CST 2009

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

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


[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月20日 星期日 12:43

guo yixuan culu.gyx在gmail.com
星期日 十二月 20 12:43:55 CST 2009

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)。

希望能有所帮助。

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月20日 星期日 22:55

Kermit Mei kermit.mei在gmail.com
星期日 十二月 20 22:55:03 CST 2009

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)。
> 
> 希望能有所帮助。

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


[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月22日 星期二 16:14

pan shizhu pan.shizhu在gmail.com
星期二 十二月 22 16:14:57 CST 2009

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

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

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

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月22日 星期二 16:38

Kermit Mei kermit.mei在gmail.com
星期二 十二月 22 16:38:01 CST 2009

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



[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月22日 星期二 18:53

pan shizhu pan.shizhu在gmail.com
星期二 十二月 22 18:53:37 CST 2009

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性能摆那里在

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月23日 星期三 09:45

Kermit Mei kermit.mei在gmail.com
星期三 十二月 23 09:45:05 CST 2009

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兆……






[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月23日 星期三 10:47

pan shizhu pan.shizhu在gmail.com
星期三 十二月 23 10:47:25 CST 2009

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

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

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月23日 星期三 10:57

Kermit Mei kermit.mei在gmail.com
星期三 十二月 23 10:57:40 CST 2009

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)了。 要是能比这个再高效一些就好了……


[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月23日 星期三 11:04

pan shizhu pan.shizhu在gmail.com
星期三 十二月 23 11:04:29 CST 2009

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

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

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

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

2009年12月23日 星期三 11:13

Kermit Mei kermit.mei在gmail.com
星期三 十二月 23 11:13:43 CST 2009

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最底层的操作,拿到一张图片要画出来也应该
是这个效率吧? 它至少也要把所有像素遍历一次才行呐。



[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-universe]

如下红色区域有误,请重新填写。

    你的回复:

    请 登录 后回复。还没有在Zeuux哲思注册吗?现在 注册 !

    Zeuux © 2024

    京ICP备05028076号