当前位置: 首页 > 模式/算法 > 图形图像处理-之-一个复杂度为常数的快速局部自适应算法 下篇

图形图像处理-之-一个复杂度为常数的快速局部自适应算法 下篇

         图形图像处理-之-一个复杂度为常数的快速局部自适应算法 下篇
                      
   2008.04.12

 

(2009.03.10  可以到这里下载完整的可以编译的项目源代码:

 

tag: 图像二值化,局部自适应,二维模板
  
摘要: 图像处理中,某些算法在对一个像素的处理都需要根据周围很多像素的综合信息
来做处理,这类算法一般叫做局部自适应算法;用以得到更好的处理效果,但很多时候
这都可能成为一个性能瓶颈,因为对一个像素点都需要做大量的处理;本文将提供我使
用的一个复杂度为常数的快速局部自适应算法。
(当然,某些二维模板不一定能够拆解成常数算法,但很多还是可以拆解成线性算法的)
       
正文:
  代码使用C++,编译器:VC2005
  测试平台:(CPU:AMD64x2 4200+(2.37G); 内存:DDR2 677(双通道); 编译器:VC2005)
 
(请先参看文章的上篇)


E:我们来优化它,得到一个线性复杂度的算法
  考虑一下,一行上相邻的两个像素,如果知道了上一个像素周围的亮度和,那么模板
移动一个像素后的亮度和也能很容易根据上一个亮度和得到;所以有了新的实现:

     // 返回图像src中坐标为(x,y0)的纵轴上距离localHalfWidth内的所有像素的亮度和
     long  getLocalLight_linearV( const  TPicRegion &  src, long  x, long  y0, long  localHalfWidth)
    {
        
long  sumYLight = 0 ;
        
for  ( long  y = y0 - localHalfWidth;y <= y0 + localHalfWidth; ++ y)
        {
            
const  TARGB32 &  mapBorderColor = getMapBorderColor(src,x,y);
            sumYLight
+= getGrayInt(mapBorderColor);
        }
        
return  sumYLight;
    }
    
// 返回图像src中坐标为(x0,y)的横轴上距离localHalfWidth内的所有像素的亮度和
     long  getLocalLight_linearH( const  TPicRegion &  src, long  x0, long  y, long  localHalfWidth)
    {
        
long  sumXLight = 0 ;
        
for  ( long  x = x0 - localHalfWidth;x <= x0 + localHalfWidth; ++ x)
        {
            
const  TARGB32 &  mapBorderColor = getMapBorderColor(src,x,y);
            sumXLight
+= getGrayInt(mapBorderColor);
        }
        
return  sumXLight;
    }
void  localAdaptiveThreshold_linear( const  TPicRegion &  dst, const  TPicRegion &  src, long  localWidth)
{
    
long  width = dst.width;
    
if  (src.width < width) width = src.width;
    
long  height = dst.height;
    
if  (src.height < height) height = src.height;
    TARGB32
*  srcLine = src.pdata;
    TARGB32
*  dstLine = dst.pdata;
    
long  localHalfWidth = localWidth / 2 ;
    
long  tLocalWidth = localHalfWidth * 2 + 1 ;
    
long  tLocalWidthSqr = tLocalWidth * tLocalWidth;
    
long  sumLight0 = getLocalLight_quadratic(src, - 1 , - 1 ,localHalfWidth);
    
for  ( long  y = 0 ;y < height; ++ y)
    {
        sumLight0
= sumLight0 
                
+ getLocalLight_linearH(src, - 1 ,y + localHalfWidth,localHalfWidth)
                
- getLocalLight_linearH(src, - 1 ,y - localHalfWidth - 1 ,localHalfWidth);
        
long  sumLight = sumLight0;
        
for  ( long  x = 0 ;x < width; ++ x)
        {
            sumLight
= sumLight
                    
+ getLocalLight_linearV(src,x + localHalfWidth,y,localHalfWidth)
                    
- getLocalLight_linearV(src,x - localHalfWidth - 1 ,y,localHalfWidth);
            
long  light = getGrayInt(srcLine[x]);
            TUInt32 color
= ((sumLight - light * tLocalWidthSqr) >> 31 );
            ((TUInt32
* )dstLine)[x] = color; 
        }
        (TUInt8
*& )srcLine += src.byte_width;
        (TUInt8
*& )dstLine += dst.byte_width;
    }
}

 

localAdaptiveThreshold_linear函数的功能和localAdaptiveThreshold_quadratic的完全一样;
速度测试:

//////////////////////////////////////////////////////////////
//                      localWidth=   5 |  17 |  51 | 151 
//------------------------------------------------------------
//localAdaptiveThreshold_linear    21.25  7.20  2.33  0.72 FPS
//////////////////////////////////////////////////////////////

恩,随着localWidth的增大,函数速度成线性降低

F:继续优化,得到一个常数复杂度的算法
  我们考虑了水平方向的计算优化,再来看看垂直方向上的计算节约,保留上一行的所有亮度和,
为下一行的计算服务;算法实现如下:

    inline  long  getLocalLight_constant( const  TPicRegion &  src, long  x, long  y)
    {
        
return  getGrayInt(getMapBorderColor(src,x,y));
    }
void  localAdaptiveThreshold_constant( const  TPicRegion &  dst, const  TPicRegion &  src, long  localWidth)
{
    
long  width = dst.width;
    
if  (src.width < width) width = src.width;
    
if  (width <= 0 return ;
    
long  height = dst.height;
    
if  (src.height < height) height = src.height;
    TARGB32
*  srcLine = src.pdata;
    TARGB32
*  dstLine = dst.pdata;
    
long  localHalfWidth = localWidth / 2 ;
    
long  tLocalWidth = localHalfWidth * 2 + 1 ;
    
long  tLocalWidthSqr = tLocalWidth * tLocalWidth;

    
long *  _sumLightArray = new   long [width + 1 ];
    
long *  sumLightArray =& _sumLightArray[ 1 ];
    sumLightArray[
- 1 ] = getLocalLight_quadratic(src, - 1 , - 1 ,localHalfWidth);
    
for  ( long  x = 0 ;x < width; ++ x)
    {
        sumLightArray[x] 
=  sumLightArray[x - 1 ]
                
+ getLocalLight_linearV(src,x + localHalfWidth, - 1 ,localHalfWidth)
                
- getLocalLight_linearV(src,x - localHalfWidth - 1 , - 1 ,localHalfWidth);
    }

    
for  ( long  y = 0 ;y < height; ++ y)
    {
        
long  sumLight0 = sumLightArray[ - 1 ]
                
+ getLocalLight_linearH(src, - 1 ,y + localHalfWidth,localHalfWidth)
                
- getLocalLight_linearH(src, - 1 ,y - localHalfWidth - 1 ,localHalfWidth);
        
for  ( long  x = 0 ;x < width; ++ x)
        {
            
long  sumLight = sumLight0 + sumLightArray[x] - sumLightArray[x - 1 ]
                     
+ getLocalLight_constant(src,x - localHalfWidth - 1 ,y - localHalfWidth - 1 )
                     
+ getLocalLight_constant(src,x + localHalfWidth,y + localHalfWidth)
                     
- getLocalLight_constant(src,x + localHalfWidth,y - localHalfWidth - 1 )
                     
- getLocalLight_constant(src,x - localHalfWidth - 1 ,y + localHalfWidth);

            sumLightArray[x
- 1 ] = sumLight0;
            sumLight0
= sumLight;

            
long  light = getGrayInt(srcLine[x]);
            TUInt32 color
= ((sumLight - light * tLocalWidthSqr) >> 31 );
            ((TUInt32
* )dstLine)[x] = color; 
        }
        sumLightArray[width
- 1 ] = sumLight0;
        (TUInt8
*& )srcLine += src.byte_width;
        (TUInt8
*& )dstLine += dst.byte_width;
    }

    delete []_sumLightArray;
}

 

localAdaptiveThreshold_constant函数的功能和localAdaptiveThreshold_quadratic的完全一样;
速度测试:
//////////////////////////////////////////////////////////////
//                      localWidth=   5 |  17 |  51 | 151 
//------------------------------------------------------------
//localAdaptiveThreshold_constant  57.30 56.00 51.89 43.00 FPS
//////////////////////////////////////////////////////////////

:D 随着localWidth的增大,速度变化不大!

  当然,该函数还可以继续优化的,比如将边界和内部区域分开处理;
比如使用MMX、SSE等的指令,等等;
   该常数复杂度算法的实现也可以用两次模板运算来实现的,申请一个和源图片一样大的临时缓
冲区,先计算缓冲区的每个点(x,y)在源图片(x,y)点垂直M范围内的亮度和(可以做到常数复杂度),
那么计算源图片(x,y)点周围的亮度和就可以通过计算缓冲区(x,y)点水平M范围内的亮度和(也可
以做到常数复杂度)来获得;


 

文章来源于网络

转载时请以 超链接的形式 注明:转自疯狂泰克