本文主要是发布 Photoshop 油画效果滤镜（OilPaint）。算法并非我提出，可以参考本文的参考资料。该滤镜在用 C# 开发的国产软件 PhotoSprite 中可以看到。2010 年曾有人请求我帮助开发该滤镜，现在我花了大概几天时间将其开发出来并免费提供。
（1）对油画滤镜的算法的概念性描述
这是我通过阅读 FilterExplorer 源码后得到的理解。该滤镜有两个参数，一个是模板半径（radius），则模板尺寸是（radius * 2 + 1）*（radius * 2 + 1）大小，也就是以当前像素为中心，向外扩展 radius 个像素的矩形区域，作为一个搜索范围，我们暂时将它称为“模板”（实际上该算法并不是例如高斯模糊，自定滤镜那种标准模板法，仅仅是处理过程类似，因此我才能实现稍后介绍的优化）。
另一个参数是光滑度（smoothness），实际上他是灰度桶的个数。我们假设把像素的灰度/亮度（ 0 ~ 255 ）均匀的分成 smoothness 个区间，则每个区间我们在此称它为一个桶（bucket），这样我们就有很多个桶，暂时称之为桶阵列（buckets）。
该算法遍历图上的每个像素，针对当前位置 (x, y) 像素，将模板范围内的所有像素灰度化，即把图像变成灰度图像，然后把像素值进一步离散化，即根据像素的灰度落入的区间，把模板内的像素依次投入到相应的桶中。然后从这些桶中找到一个落入像素个数最多的桶，并对该桶中的所有像素求出颜色平均值，作为位置 (x, y) 的结果值。
上面的算法描述，用下面的示意图来表示。中间的图像是从原图灰度化+离散化（相当于 Photoshop 中的色调分离）的结果，小方框表示的是模板。下方表示的是桶阵列（8 个桶，即把0~255的灰度值离散化成 8 个区间段）。
（2）对老外已有代码的效率的改进
如果把已有的代码原样移植到 PS 滤镜中并不难，我大概花了 1 ~ 2 天的业余时间就基本调试成功了。但是在阅读老外的源码时，我明显感觉到原有代码的效率不够高。该算法遍历一次图像即可完成，对每个像素的处理是常数时间，因此针对像素数量（图像长度*图像宽度）是O（n）复杂度，但是原有代码的常系数较大，例如，每次计算像素结果时，都要重新计算模板范围内像素的灰度，并把它投入桶中，实际上造成大量的重复性计算。
2.1 为此，我的第一个改进是在 PS 中把当前的整个图像贴片进行灰度化并离散化（投入桶中），这样在用模板遍历贴片时，就不需要重复性的计算灰度并离散化了。这样大概把算法的运行速度提高了一倍左右（针对某个样本，处理速度从20多秒提高到10秒左右）。
2.2 但这样对速度的提高仍不够显著。因此我进行另一项更重要的优化，即把针对模板尺寸的复杂度从平方降低到线性复杂度。这个依据是，考虑模板在当前行间从左向右逐格移动，模板中部像素（相邻两个模板的交集）在结果中的统计数据是不变的。仅有最左侧一列移出模板，最右侧一列进入模板，因此我们在遍历图像时就不必管模板中部像素，只需要处理模板的两个边缘即可。如下图所示（半径为2，模板尺寸是 5 * 5 像素）：
当到达贴片右侧边缘时，我们不是类似回车换行那样重新复位到行首，而是把模板向下移动一行，进入下一行尾部，然后再向左平移，这样模板的行进轨迹就成为一个蛇形迂回步进的轨迹。当这样改进以后，我们遍历像素的时候就仅仅需要处理模板的两个边缘像素即可。这样，就把针对模板尺寸（参数中的半径）从O（n^2）降低到O（n），从而使该算法的运算速度大大提高，结合优化 2.1 ，最终使算法的运算速度大概提高了 11 倍（该数值仅仅是粗略估算，未经过大量样本测试），优化后的算法对大图像的处理时间也是变得可以接受的。
【注意】我能做到这样的优化的原因是该滤镜算法并不是标准的模板算法，它的本质是求模板范围内的统计信息，即结果和像素的模板坐标无关。这就好像是我们想得到某局部范围的人口数，男女比例等信息一样。因此我们按以上方法进行优化。
模板移动的轨迹是蛇形迂回步进，例如：
→ → → → → → →
↓
← ← ← ← ← ← ←
↓
→ → ...
下面我将给出本滤镜的核心算法的代码，位于 algorithm.cpp 中的全部代码：
code_FilterData_OilPaint
#include "Algorithm.h"
//=========================================
// 缩略图和实际处理共享的滤镜算法
//=========================================
//
// 默认把数据当作是RGB, GrayData 是单通道数据，矩形和 InRect 一致
//
// bInitGray: 是否需要算法重新计算灰度数据
// rowBytes: inData/outData, 扫描行宽度
// colBytes: inData/outData, 对于interleave分布，等于通道数，集中分布时该为1
// planeBytes: 每个通道的字节数（对于interleave分布，该参数的值为1）
// grayData: 由于仅一个通道，所以grayColumnBytes一定是1；
// buckets: 灰度桶； 每个灰度占据4个UINT，0-count，1-redSum，2-greenSum，3-blueSum
// abortProc: 用于测试是否取消的回调函数（在滤镜处理过程中，即测试用户是否按了Escape）
// 在缩略图中用于测试是否已经产生了后续的Trackbar拖动事件
// retVal：如果没有被打断，返回TRUE，否则返回FALSE（说明被用户取消或后续UI事件打断）
//
BOOL FilterData_OilPaint(
uint8* pDataIn, Rect& inRect, int inRowBytes, int inColumnBytes, int inPlaneBytes,
uint8* pDataOut, Rect& outRect, int outRowBytes, int outColumnBytes, int outPlaneBytes,
uint8* pDataGray, int grayRowBytes, BOOL bInitGray,
int radius,
int smoothness,
UINT* buckets,
TestAbortProc abortProc
)
{
int indexIn, indexOut, indexGray, x, y, i, j, i2, j2, k; //像素索引
uint8 red, green, blue;
//设置边界
int imaxOut = (outRect.right - outRect.left);
int jmaxOut = (outRect.bottom - outRect.top);
int imaxIn = (inRect.right - inRect.left);
int jmaxIn = (inRect.bottom - inRect.top);
//获取两个矩形（inRect和outRect）之间的偏移，即 outRect 左上角在 inRect 区中的坐标
int x0 = outRect.left - inRect.left;
int y0 = outRect.top - inRect.top;
// 灰度离散化应该作为原子性操作，不应该分割
if(bInitGray)
{
//把 In 贴片灰度化并离散化
double scale = smoothness /255.0;
for(j =0; j < jmaxIn; j++)
{
for(i =0; i < imaxIn; i++)
{
indexIn = i * inColumnBytes + j * inRowBytes; //源像素[x, y]
red = pDataIn[indexIn];
green = pDataIn[indexIn + inPlaneBytes];
blue = pDataIn[indexIn + inPlaneBytes*2];
pDataGray[grayRowBytes * j + i] = (uint8)(GET_GRAY(red, green, blue) * scale);
}
}
}
if(abortProc != NULL && abortProc())
return FALSE;
// 模板和统计数据
// 灰度桶 count, rSum, gSum, bSum
//
memset(buckets, 0, (smoothness +1) *sizeof(UINT) *4);
int colLeave, colEnter, yMin, yMax;
int rowLeave, rowEnter, xMin, xMax;
int direction;
//初始化第一个模板位置的数据
yMin = max(-y0, -radius);
yMax = min(-y0 + jmaxIn -1, radius);
xMin = max(-x0, -radius);
xMax = min(-x0 + imaxIn -1, radius);
for(j2 = yMin; j2 <= yMax; j2++)
{
for(i2 = xMin; i2 <= xMax; i2++)
{
indexIn = (j2 + y0) * inRowBytes + (i2 + x0) * inColumnBytes;
indexGray = (j2 + y0) * grayRowBytes + (i2 + x0);
buckets[ pDataGray[indexGray] *4 ]++; //count
buckets[ pDataGray[indexGray] *4+1 ] += pDataIn[indexIn]; //redSum
buckets[ pDataGray[indexGray] *4+2 ] += pDataIn[indexIn + inPlaneBytes]; //greenSum
buckets[ pDataGray[indexGray] *4+3 ] += pDataIn[indexIn + inPlaneBytes*2]; //greenSum
}
}
if(abortProc != NULL && abortProc())
return FALSE;
//进入模板的蛇形迂回循环
for(j =0; j < jmaxOut; j++)
{
if(abortProc != NULL && abortProc())
return FALSE;
//direction：水平移动方向（ 1 - 向右移动； 0 - 向左移动）
direction =1- (j &1);
//找到最大的那个像素
GetMostFrequentColor(buckets, smoothness, &red, &green, &blue);
if(direction)
{
indexOut = j * outRowBytes;
}
else
{
indexOut = j * outRowBytes + (imaxOut -1) * outColumnBytes;
}
pDataOut[ indexOut ] = red;
pDataOut[ indexOut + outPlaneBytes ] = green;
pDataOut[ indexOut + outPlaneBytes *2 ] = blue;
i = direction?1 : (imaxOut -2);
for(k =1; k < imaxOut; k++) //k 是无意义的变量，仅为了在当前行中前进
{
//每 64 个点测试一次用户取消 ( 在每行中间有一次测试 )
if((k &0x3F) ==0x3F&& abortProc != NULL && abortProc())
{
return FALSE;
}
if(direction) //向右移动
{
colLeave = i - radius -1;
colEnter = i + radius;
}
else//向左移动
{
colLeave = i + radius +1;
colEnter = i - radius;
}
yMin = max(-y0, j - radius);
yMax = min(-y0 + jmaxIn -1, j + radius);
//移出当前模板的那一列
if((colLeave + x0) >=0&& (colLeave + x0) < imaxIn)
{
for(j2 = yMin; j2 <= yMax; j2++)
{
indexIn = (j2 + y0) * inRowBytes + (colLeave + x0) * inColumnBytes;
indexGray = (j2 + y0) * grayRowBytes + (colLeave + x0);
buckets[ pDataGray[indexGray] *4 ]--; //count
buckets[ pDataGray[indexGray] *4+1 ] -= pDataIn[indexIn]; //redSum
buckets[ pDataGray[indexGray] *4+2 ] -= pDataIn[indexIn + inPlaneBytes]; //greenSum
buckets[ pDataGray[indexGray] *4+3 ] -= pDataIn[indexIn + inPlaneBytes*2]; //greenSum
}
}
//进入当前模板的那一列
if((colEnter + x0) >=0&& (colEnter + x0) < imaxIn)
{
for(j2 = yMin; j2 <= yMax; j2++)
{
indexIn = (j2 + y0) * inRowBytes + (colEnter + x0) * inColumnBytes;
indexGray = (j2 + y0) * grayRowBytes + (colEnter + x0);
buckets[ pDataGray[indexGray] *4 ]++; //count
buckets[ pDataGray[indexGray] *4+1 ] += pDataIn[indexIn]; //redSum
buckets[ pDataGray[indexGray] *4+2 ] += pDataIn[indexIn + inPlaneBytes]; //greenSum
buckets[ pDataGray[indexGray] *4+3 ] += pDataIn[indexIn + inPlaneBytes*2]; //greenSum
}
}
//找到最大的那个像素
GetMostFrequentColor(buckets, smoothness, &red, &green, &blue);
//目标像素[i, j]
indexOut = j * outRowBytes + i * outColumnBytes;
pDataOut[ indexOut ] = red;
pDataOut[ indexOut + outPlaneBytes ] = green;
pDataOut[ indexOut + outPlaneBytes *2 ] = blue;
i += direction?1 : -1;
}
//把模板向下移动一行
rowLeave = j - radius;
rowEnter = j + radius +1;
if(direction)
{
xMin = max(-x0, (imaxOut -1) - radius);
xMax = min(-x0 + imaxIn -1, (imaxOut -1) + radius);
indexOut = (j +1) * outRowBytes + (imaxOut -1) * outColumnBytes; //目标像素[i, j]
}
else
{
xMin = max(-x0, -radius);
xMax = min(-x0 + imaxIn -1, radius);
indexOut = (j +1) * outRowBytes; //目标像素[i, j]
}
//移出当前模板的那一列
if((rowLeave + y0) >=0&& (rowLeave + y0) < jmaxIn)
{
for(i2 = xMin; i2 <= xMax; i2++)
{
indexIn = (rowLeave + y0) * inRowBytes + (i2 + x0) * inColumnBytes;
indexGray = (rowLeave + y0) * grayRowBytes + (i2 + x0);
buckets[ pDataGray[indexGray] *4 ]--; //count
buckets[ pDataGray[indexGray] *4+1 ] -= pDataIn[indexIn]; //redSum
buckets[ pDataGray[indexGray] *4+2 ] -= pDataIn[indexIn + inPlaneBytes]; //greenSum
buckets[ pDataGray[indexGray] *4+3 ] -= pDataIn[indexIn + inPlaneBytes*2]; //greenSum
}
}
//进入当前模板的那一列
if((rowEnter + y0) >=0&& (rowEnter + y0) < jmaxIn)
{
for(i2 = xMin; i2 <= xMax; i2++)
{
indexIn = (rowEnter + y0) * inRowBytes + (i2 + x0) * inColumnBytes;
indexGray = (rowEnter + y0) * grayRowBytes + (i2 + x0);
buckets[ pDataGray[indexGray] *4 ]++; //count
buckets[ pDataGray[indexGray] *4+1 ] += pDataIn[indexIn]; //redSum
buckets[ pDataGray[indexGray] *4+2 ] += pDataIn[indexIn + inPlaneBytes]; //greenSum
buckets[ pDataGray[indexGray] *4+3 ] += pDataIn[indexIn + inPlaneBytes*2]; //greenSum
}
}
}
return TRUE;
}
//从灰度桶阵列中，提取出最多像素的那个桶，并把桶中像素求平均值作为 RGB 结果。
void GetMostFrequentColor(UINT* buckets, int smoothness, uint8* pRed, uint8* pGreen, uint8* pBlue)
{
UINT maxCount =0;
int i, index =0;
for(i =0; i <= smoothness; i++)
{
if(buckets[ i *4 ] > maxCount)
{
maxCount = buckets[ i *4 ];
index = i;
}
}
if(maxCount >0)
{
*pRed = (uint8)(buckets[ index *4+1 ] / maxCount); //Red
*pGreen = (uint8)(buckets[ index *4+2 ] / maxCount); //Green
*pBlue = (uint8)(buckets[ index *4+3 ] / maxCount); //Blue
}
} 更多Photoshop 油画效果滤镜 相关文章请关注PHP中文网！