精与杂

昨天读Andrei Alexandrescu那本著名的《Modern C++ Design》(《C++设计新思维》这个中文译名大概老侯取的吧,反正我是不太喜欢)的时候,偶然看到译者之一的於春景的序里说到:他是三年前(此书于2003年出版,照算此处应该是指2000年)开始接触template的,不觉大寒。

想当年与朋友“太可怕”在福州琢磨着自己写一个template library时(那时还不知道有STL,后来知道STL后就作罢了),大概还是98年吧。时至今日,忽然发现自己的C++水平居然一直都没有大的长进。这些年来,为了混饭吃,什么方面的软件都要做,结果下来终于发现会的多,精的少。

这个於春景我是知道的,他的网名叫做lostmouse,我手上有一个Scott.Meyers的《Effective C++》的电子版就是lostmose做的,手上还有一本他译的书《C++网络编程(卷1)》(Douglas C.Schmidt的《C++ Network Programming Volume 1》)。相信他的C++功力已经相当不俗了,在他面前,我大概只有汗的份。

“业精于勤,技精于专”果然是所言非虚啊。

用线性插值算法实现图像缩放

用线性插值算法实现图像缩放

 

猛禽[Mental Studio](个人专栏)(BLOG)

http://mental.8gua.me

 

Windows中做过图像方面程序的人应该都知道WindowsGDI有一个API函数:StretchBlt,对应在VCL中是TCanvas类的StretchDraw方法。它可以很简单地实现图像的缩放操作。但问题是它是用了速度最快,最简单但效果也是最差的“最近邻域法”,虽然在大多数情况下,它也够用了,但对于要求较高的情况就不行了。

不久前我做了一个小玩意儿(见《人个信息助理之我的相册》),用于管理我用DC拍的一堆照片,其中有一个插件提供了缩放功能,目前的版本就是用了StretchDraw,有时效果不能令人满意,我一直想加入两个更好的:线性插值法和三次样条法。经过研究发现三次样条法的计算量实在太大,不太实用,所以决定就只做线性插值法的版本了。

从数字图像处理的基本理论,我们可以知道:图像的变形变换就是源图像到目标图像的坐标变换。简单的想法就是把源图像的每个点坐标通过变形运算转为目标图像的相应点的新坐标,但是这样会导致一个问题就是目标点的坐标通常不会是整数,而且像放大操作会导致目标图像中没有被源图像的点映射到,这是所谓“向前映射”方法的缺点。所以一般都是采用“逆向映射”法。

但是逆向映射法同样会出现映射到源图像坐标时不是整数的问题。这里就需要“重采样滤波器”。这个术语看起来很专业,其实不过是因为它借用了电子信号处理中的惯用说法(在大多数情况下,它的功能类似于电子信号处理中的带通滤波器),理解起来也不复杂,就是如何确定这个非整数坐标处的点应该是什么颜色的问题。前面说到的三种方法:最近邻域法,线性插值法和三次样条法都是所谓的“重采样滤波器”。

所谓“最近邻域法”就是把这个非整数坐标作一个四舍五入,取最近的整数点坐标处的点的颜色。而“线性插值法”就是根据周围最接近的几个点(对于平面图像来说,共有四点)的颜色作线性插值计算(对于平面图像来说就是二维线性插值)来估计这点的颜色,在大多数情况下,它的准确度要高于最近邻域法,当然效果也要好得多,最明显的就是在放大时,图像边缘的锯齿比最近邻域法小非常多。当然它同时还带业个问题:就是图像会显得比较柔和。这个滤波器用专业术语来说(呵呵,卖弄一下偶的专业^_^)叫做:带阻性能好,但有带通损失,通带曲线的矩形系数不高。至于三次样条法我就不说了,复杂了一点,可自行参考数字图像处理方面的专业书籍,如本文的参考文献。

再来讨论一下坐标变换的算法。简单的空间变换可以用一个变换矩阵来表示:

[x’,y’,w’]=[u,v,w]*T

其中:x’,y’为目标图像坐标,u,v为源图像坐标,w,w’称为齐次坐标,通常设为1T为一个3X3的变换矩阵。

这种表示方法虽然很数学化,但是用这种形式可以很方便地表示多种不同的变换,如平移,旋转,缩放等。对于缩放来说,相当于:

[Su  0  0]

[x, y, 1] = [u, v, 1] * | 0  Sv  0 |

[0   0  1]

其中Su,Sv分别是X轴方向和Y轴方向上的缩放率,大于1时放大,大于0小于1时缩小,小于0时反转。

矩阵是不是看上去比较晕?其实把上式按矩阵乘法展开就是:

{ x = u * Su

{ y = v * Sv

就这么简单。^_^

有了上面三个方面的准备,就可以开始编写代码实现了。思路很简单:首先用两重循环遍历目标图像的每个点坐标,通过上面的变换式(注意:因为是用逆向映射,相应的变换式应该是:u = x / Su v = y / Sv)取得源坐标。因为源坐标不是整数坐标,需要进行二维线性插值运算:

P = n*b*PA + n * ( 1 – b )*PB + ( 1 – n ) * b * PC + ( 1 – n ) * ( 1 – b ) * PD

其中:nv(映射后相应点在源图像中的Y轴坐标,一般不是整数)下面最接近的行的Y轴坐标与v的差;同样b也类似,不过它是X轴坐标。PA-PD分别是(u,v)点周围最接近的四个(左上,右上,左下,右下)源图像点的颜色(用TCanvasPixels属性)。P(u,v)点的插值颜色,即(x,y)点的近似颜色。

这段代码我就不写的,因为它的效率实在太低:要对目标图像的每一个点的RGB进行上面那一串复杂的浮点运算。所以一定要进行优化。对于VCL应用来说,有个比较简单的优化方法就是用TBitmapScanLine属性,按行进行处理,可以避免Pixels的像素级操作,对性能可以有很大的改善。这已经是算是用VCL进行图像处理的基本优化常识了。不过这个方法并不总是管用的,比如作图像旋转的时候,这时需要更多的技巧。

无论如何,浮点运算的开销都是比整数大很多的,这个也是一定要优化掉的。从上面可以看出,浮点数是在变换时引入的,而变换参数Su,Sv通常就是浮点数,所以就从它下手优化。一般来说,Su,Sv可以表示成分数的形式:

Su = ( double )Dw / Sw; Sv = ( double )Dh / Sh

其中Dw, Dh为目标图像的宽度和高度,Sw, Sh为源图像的宽度和高度(因为都是整数,为求得浮点结果,需要进行类型转换)。

将新的Su, Sv代入前面的变换公式和插值公式,可以导出新的插值公式:

因为:

b = 1 – x * Sw % Dw / ( double )Dw;  n = 1 – y * Sh % Dh / ( double )Dh

设:

B = Dw – x * Sw % Dw; N = Dh – y * Sh % Dh

则:

b = B / ( double )Dw; n = N / ( double )Dh

用整数的BN代替浮点的b, n,转换插值公式:

P = ( B * N * ( PA – PB – PC + PD ) + Dw * N * PB + DH * B * PC + ( Dw * Dh – Dh * B – Dw * N ) * PD ) / ( double )( Dw * Dh )

这里最终结果P是浮点数,对其四舍五入即可得到结果。为完全消除浮点数,可以用这样的方法进行四舍五入:

P = ( B * N … * PD + Dw * Dh / 2 ) / ( Dw * Dh )

这样,P就直接是四舍五入后的整数值,全部的计算都是整数运算了。

简单优化后的代码如下:

int __fastcall TResizeDlg::Stretch_Linear(Graphics::TBitmap * aDest, Graphics::TBitmap * aSrc)

{

    int sw = aSrc->Width – 1, sh = aSrc->Height – 1, dw = aDest->Width – 1, dh = aDest->Height – 1;

    int B, N, x, y;

    int nPixelSize = GetPixelSize( aDest->PixelFormat );

    BYTE * pLinePrev, *pLineNext;

    BYTE * pDest;

    BYTE * pA, *pB, *pC, *pD;

    for ( int i = 0; i <= dh; ++i )

    {

        pDest = ( BYTE * )aDest->ScanLine[i];

        y = i * sh / dh;

        N = dh – i * sh % dh;

        pLinePrev = ( BYTE * )aSrc->ScanLine[y++];

        pLineNext = ( N == dh ) ? pLinePrev : ( BYTE * )aSrc->ScanLine[y];

        for ( int j = 0; j <= dw; ++j )

        {

            x = j * sw / dw * nPixelSize;

            B = dw – j * sw % dw;

            pA = pLinePrev + x;

            pB = pA + nPixelSize;

            pC = pLineNext + x;

            pD = pC + nPixelSize;

            if ( B == dw )

            {

                pB = pA;

                pD = pC;

            }

            for ( int k = 0; k < nPixelSize; ++k )

                *pDest++ = ( BYTE )( int )(

                    ( B * N * ( *pA++ – *pB – *pC + *pD ) + dw * N * *pB++

                    + dh * B * *pC++ + ( dw * dh – dh * B – dw * N ) * *pD++

                    + dw * dh / 2 ) / ( dw * dh )

                );

        }

    }

    return 0;

}

应该说还是比较简洁的。因为宽度高度都是从0开始算,所以要减一,GetPixelSize是根据PixelFormat属性来判断每个像素有多少字节,此代码只支持2432位色的情况(对于1516位色需要按位拆开因为不拆开的话会在计算中出现不期望的进位或借位,导致图像颜色混乱处理较麻烦;对于8位及8位以下索引色需要查调色板,并且需要重索引,也很麻烦,所以都不支持;但8位灰度图像可以支持)。另外代码中加入一些在图像边缘时防止访问越界的代码。

通过比较,在PIII-733的机器上,目标图像小于1024×768的情况下,基本感觉不出速度比StretchDraw有明显的慢(用浮点时感觉比较明显)。效果也相当令人满意,不论是缩小还是放大,图像质量比StretchDraw方法有明显提高。

不过由于采用了整数运算,有一个问题必须加以重视,那就是溢出的问题:由于式中的分母是dw * dh,而结果应该是一个Byte8位二进制数,有符号整数最大可表示31位二进制数,所以dw * dh的值不能超过23位二进制数,即按2:1的宽高比计算目标图像分辨率不能超过4096*2048。当然这个也是可以通过用无符号数(可以增加一位)及降低计算精度等方法来实现扩展的,有兴趣的朋友可以自己试试。

当然这段代码还远没有优化到极致,而且还有很多问题没有深入研究,比如抗混叠(anti-aliasing)等,有兴趣的朋友可以自行参考相关书籍研究,如果你有什么研究成果,非常欢迎你为我的程序编写插件实现。

 

[Mental Studio]猛禽

2004-3-28

参考文献:

崔屹《数字图像处理技术与应用》电子工业出版社,1997

春游

昨天有朋友讨论要在这个春天出游,在研究要去什么地方玩的时候,我一下就想到了扬州。

春风十里扬州路,卷上珠帘总不如。

十年一觉扬州梦,赢得青楼薄倖名。

二十四桥明月夜,玉人何处教吹箫?

淮左名都,竹西佳处,解鞍少驻初程。
过春风十里,尽荠麦青青。
自胡马窥江去后,废池乔木,犹厌言兵。
渐黄昏,清角吹寒,都在空城。
杜郎俊赏,算而今、重到须惊。
纵豆蔻词工,青楼梦好,难赋深情。
二十四桥仍在,波心荡、冷月无声。
念桥边红药,年年知为谁生。

西西,我的BLOG名称就来自这里。

Looser们

看到一篇不错的文章《值得中国人借鉴的美国短处》,虽然讨论的东东和技术没什么关系,不过其中有个词很有意思,就是looser(看来偶英文差啊,多谢tinyfool兄指正^_^)

软件业好像也蛮多这种looser的,一边在抱怨自己混得差,一边却自觉义务地为MS之类的吹鼓,打击开源等。殊不知在MS眼里,这些人不过是一些loosers。

午饭时间到,吃饭去。

BTW:今天你LOOSER了吗?

沙漠加油站

今天看到一则笑话:

沙漠加油站
进入沙漠区之前的小镇上,第一家加油站站前的巨型广告版上写着:此去即是沙漠地区,除本站外,您举目所见的其它加油站皆为海市蜃楼,务请即刻加满油箱以策安全。

好像有些软件公司也是这样宣传他们的“先进”技术的。^_^

随机应变的XP与按部就班的RUP等

昨天上海下了中雨,碰上一件很不爽的事:因为GF要出国,我们从火车站提了一件比较大的行李,要运到一个离火车站不远的一家宾馆,但是拦了几辆TAXI都拒载。只好自己动手冒雨步行搬运,累S人了,真TMD想投诉。麻烦的是今天还要一早把这件行李运回火车站,从这里上机场大巴运到浦东机场。为了这事我们昨晚研究了一晚的计划,如何才能让TAXI不拒载。包括向宾馆服务台咨询了几套方案。

结果正应了一句话:计划没有变化快。

今天雨停了,虽然在门口没打到车,但很方便地就通过电话叫了一辆,司机也居然很爽快就答应了,麻烦的事情就这样简单搞定。

其实软件开发有时候也是这样,常常要考虑到客户需求的方方面面,而且在设计开发中也需要到处为未来留下改进空间。结果却常常是我们考虑的方面根本就是客户不需要的方面,甚至影响到客户的真实需求,而我们为未来的留下改进空间的地方也许永远也用不上,反而给我们带的无穷的BUG。回头一看,原来客户的需求比你想的简单得多。

于是乎,有了XP。

其实正如我在《效颦篇:编程本质论》一文中所说的:“只要能解决问题的办法,都是好办法。”XP也罢,RUP也罢都是如此,还是需要根据情况选择取舍的。

三层、自增类型、李维及其它

早上与一个朋友讨论他在做MIDAS应用开发时碰到的一个跟MSSQL的Identity类型有关的问题。基本上真正有在实际应用中用过MIDAS的程序员都碰到过那个经典的:Data changed by another user的问题。其实原因不外乎那几个:Trigger、Default value和Identity类型。而且绝大多数用MIDAS做多层应用开发的,都是看李维那三本书来的。

问题李维在书里并没有很明显地提到这一点。就像比基尼:露出来的,都是你感兴趣的,隐藏的,却是关键的。

不敢说李维没有实践过,但是真正用于商业应用时,和写DEMO是完全不同的情况。BORLAND的技术在某种程度上说,普遍存在这样的问题,不论是MIDAS还是早夭的Kylix和WebSnap。

在这点上Microsoft做得要好得多,虽然它的很多产品都不能算最好,但一般都“足够好”,据说这也正是MS一向的产品目标。

正在没落的BORLAND与同样没落的李维

这个标题有点哗众取宠的意思。其实Borland是否真的没落,还要靠市场来最终检验,但原生Win32开发领域的开发人员大批跳向JAVA和.net却是不争的事实。Borland在用户心目中的地位也几乎是降到了一个历史性的低点。在NASDAQ上,代号BORL的股票价格也已经跌到了$10左右。

至于李维,现在在中国Borland开发者眼里,差不多已经等同于Borland的吹鼓手了。但在我看来,还是可以理解的,毕竟他是Borland的员工,所谓拿人钱财,与人消灾,无可厚非。

自打上月爆出Borland的几个重要头目–包括Black.Stone, Chuck.Jazdzewski,Simon.Thronhill等人–相继离开。特别是Black.Stone和Chuck.Jazdzewski的去向都是Microsoft,严重地动摇了Borland用户的信心。

然而事情并非始于此事,早在去年上半年,随着Borland的几个新产品问世,但却令人大失所望之时,Borland就已经种下危机的种子。而且现在Borland无限期暂停Linux下的Kylix项目,原生Win32下的Delphi/BCB项目都被冷却,全力投奔.net,但在.net下也并不成功,C#Builder和Delphi.net不但没吸引到多少新用户,反而把不少用户推向VS.net。

历史上Borland经历过多次的危机,每一次都需要Borland花上数年的时间才能重振旗鼓,而且往往无法回复危机前的风光。

但这次危机会对Borland有什么影响,我现在也不敢说,但众多Borland用户的态度明摆在那里。

然而抵制.net的人也还有:

==================

getit911:   .net是什么?是一个ms又挖下的坑,给她披上最美丽的外衣,在ms press出版的那些"红宝书"里,给我们彻底地洗了一次脑,于是我们高呼".net万岁“,这个世界上没有什么是她解决不了的,这是万能的工具.但恶魔总是吹着笛子来,当我们都虔诚地朝拜在前往.net的路上时,回首一望,所有的语言都生长在clr的土壤上.等到那一天,bill就会眼里凶光一闪,"是时候了",又一个什么.net++推出,利用ms的垄断特权,填平那个曾经吹捧得无所不能的.net大坑,被埋没的将是离开了clr便不知所措的我们(这样的悲剧已在mfc上演过).剩下的只有什么clr++了,
  转自一个网友,.net就是垃圾
     (2004.03.15)

======================

getit911:   .net根本就是个商业陷阱,技术垃圾,根本没有什么技术创新,那个所谓clr不过是个让软件开发人员上套的鬼把戏,.net上的开发语言的已经没有意义,再NB闪闪的语言到最后都必须使用M$的编译器编译,C#、VB.NET、ASP.NET还他妈的有什么搞头,不如直接写IL了,还有一个反编译问题.net也没有什么好的解决方法,即使加了混淆器也不怎么灵,代码根本没有保障。M$就是眼看Win32API被人操翻了,垄断地位不保,急忙弄个.net出来搞个语言新圈地运动,当然这对在中国用3.5元/张光盘的软件公司没用,否则开发软件的挣的那点糟银子都捐M$都不够。   (2004.03.16)

====================

不能说他说的不对,但是以Microsoft目前的垄断优势,偶们这些小开发人员除了屈从,恐怕也没有什么更好的出路了。

在这种情况下,如果Borland轰然倒下,那么除非Borland将所有开发工具都OpenSource,像Eclipse那样,否则Visual Studio.net一统开发工具市场将成必然。

开源与理想主义

很久以前,我看过一篇短文,说的是父亲给儿子的几个忠告,其中一条便是:不要嘲笑别人的梦想。

不过有些人好像很不以为然,却不知道已经无梦的人更加可悲。

成功的开源项目如LINUX等,得到IBM的包装,如同被包装过的演艺明星。

如同中国的演艺界,据说在北京的很多地下室里,活跃着数以万计的自称歌手的人物,他们中有人梦想着有朝一日被星探发现,一举成名;有人混了几年,一事无成,最终堕落;当然也有人是真正热爱歌唱,是为了自己和欣赏自己的人歌唱。这些人中,成功的毕竟是少数,失败的还是大多数。在这些失败的人中,不排除真的有怀才不遇的,但也有很大的可能是:你根本就不是那块料!

正如同那些反对开源的人,好像开源抢了他们的饭碗,问题是,他们写的那点烂东东,就是开了源,倒贴钱,估计也不会有什么BMI会看得上的。

居然还敢说开源的人都是毛少的人:

======================
FireAngel (2004-3-17 8:53:05) 

总的来说,只有毛少的人喜欢谈opensource:一种是毛没长齐的,开源是他们的精神寄托;一种是毛掉光的,开源是他们赚钱的工具 
======================

四条腿的动物一般毛比较多的说。