最近英语课上聊到了互联网兴起以来，交流方式的变化，博客是互联网最早的形式之一，已经相当老了，现在的交流变得更加简短，与微博和朋友圈不到一百字的简短相比，博客是相当长的了。可能是现代人太吝啬自己时间了，写博客的人越来越少，并且博客质量下降，得益于信息的快速传播，也出现了天下文章一大抄的现象。不过我想，还是有些东西需要实实在在的篇幅来沉淀的，于是想起有还有坑没有填，就快点过来把坑填完了。
通常我们使用游程编码的原因是因为游程编码更快，并且更加节省内存，游程编码可以做很多事情，其中就包括形态学操作，这篇博客将详细介绍在游程编码上实现形态学操作。
一、参考资料
首先给出论文paper和论文代码
论文代码（在imgrl中）
https://github.com/tmbdev/iulib
二、方法概述
论文中将了三种形态学操作方法，第一种太粗暴，我们关心的是后面的两种：行内操作方法、行间操作方法。
利用行内操作进行的形态学操作通常只能实现矩形模板的腐蚀和膨胀。先对一行进行腐蚀，然后将H行腐蚀结果进行转置，然后再对转置后的游程进行行腐蚀，将V行腐蚀的结果进行转置，就得到了腐蚀结果。
进行一维的游程腐蚀膨胀很容易实现，关键就在于如何对游程进行转置。游程转置见第三部分介绍。
行间操作方式就可以针对任意的模板进行操作了，并且根据测试，在行数少的时候（个人测试是模板小于等于五行时，较行间操作更快）。
三、游程转置
游程的转置操作如下图所示。通过游程编码逐行扫描，扫描游程的同时，不断维护一个数组Open，Open的长度为图像的宽度，Open中的内容为对应列纵向的起始位置。
转置的逻辑是这样的：
- 如上图第一行，我们现在记录的每一列的起始位置如open，open中数值为3则表示这一列的游程是从第3行开始的。
- 扫描到下一行，那么会出现三种情况。Open中存有列游程开始位置的话，这一行也有游程，则open不变，如果之前的行有游程，这一行游程中断，则这一列的游程进行保存，重置Open对应的列为无效值。如果之前Open为无效值，这一列新增了游程，则将本列的Open置为当前列，记录为一个列游程的起始。
- 不断维护Open的同时存储转置后的列游程至扫描结束。最后整理转置后的游程，按照行顺序排列进行输出（这里可以维护一个堆或者有限队列来对转置后的游程重新排序）
看看伪代码
iulib中也是实现了类似的算法，只不过有一点不同，就是open_runs的表示，再iulib代码中也使用游程进行表示了，使得代码有些复杂。
方法对比：将游程转回位图，位图转置再转化成游程也可以实现游程转置的，并且速度比单纯再游程上进行转置要快一些（这个也不一定，游程很少时候，游程方法会更快）。但是如果时出于节省内存角度出发的化，那么在游程上进行操作会更有优势。
这里第一种方法就介绍完了，如果是非矩形模板，那么就要用到行间与或的方法。
四、游程的行间与或
先粘一段代码，对着代码说:
行间与或的方法是二指针法，把游程想象成区间，两条线的区间进行与或操作，就是通过二指针的移动，来不断修改结果游程。（好吧，说了等于没说，这个如果刷过LeetCode应该会见到很多这样的题目）总之，代码中给出的逻辑，就是区间求交并补的逻辑。
void line_invert(RLELine &out,int n) {
int last = 0;
for(int i=0;i<out.length();i++) {
RLERun &r = out[i];
int temp = r.end;
r.end = r.start;
r.start = last;
last = temp;
}
if(last<n) out.push(RLERun(last,n));
if(out.length()>0 && out(0).end==0) delete_at(out,0);
verify_line(out);
}
void line_and(RLELine &out,RLELine &l1,RLELine &l2,int offset2,int total) {
TransitionSink sink(out,total);
TransitionSource src1(l1,0);
TransitionSource src2(l2,offset2);
int where = -30000;
bool b1 = false;
bool b2 = false;
while(src1 || src2) {
if(src1.coord()<src2.coord()) {
b1 = src1.value();
where = src1.coord();
src1.next();
} else {
b2 = src2.value();
where = src2.coord();
src2.next();
}
sink.append(where,b1&&b2);
}
sink.finish();
}
void line_or(RLELine &out,RLELine &l1,RLELine &l2,int offset2,int total) {
TransitionSink sink(out,total);
TransitionSource src1(l1,0),src2(l2,offset2);
int where = -999;
bool b1 = false;
bool b2 = false;
while(src1 || src2) {
if(src1.coord()<src2.coord()) {
b1 = src1.value();
where = src1.coord();
src1.next();
} else {
b2 = src2.value();
where = src2.coord();
src2.next();
}
sink.append(where,b1||b2);
}
sink.finish();
}这个我再考虑下怎么说更清楚。应该是要画个图的…
五、进行任意模板的形态学操作
在游程编码上进行形态学操作，就是遍历模板每一行，每一行的模板和图像进行1D的腐蚀操作，然后纵向的腐蚀通过行间的与操作的实现。后面画了一个图，来解释任意模板腐蚀的过程
贴代码
void rle_erode_mask(RLEImage &image,RLEImage &mask,int dx,int dy) {
RLEImage result;
result.resize(image.dim(0),image.dim(1));
result.fill(1);
for(int mi=0;mi<mask.nlines();mi++) {
RLELine &mline = mask.line(mi);
if(mline.length()==0) continue;
RLERun run = mask.line(mi)(0);
RLELine temp;
RLELine out;
for(int i=mi;i<image.dim(0);i++) {
copy(temp,image.line(i));
for(int j=0;j<mline.length();j++)
erode_runs(temp,run.end-run.start,image.dim(1),run.start);
line_and(out,result.line(i-mi),temp,0,image.dim(1));
swap(out,result.line(i-mi));
}
}
image.take(result);
}同时代码里没有实现任意模板的膨胀操作，通过将&&改成||，也是可以实现的。这种方法比第一种方法，在模板较小时要快一些，并且不需要转置操作，所以会更省内存。但是模板较大时，尤其是模板行数较多时，会更慢些。
好了，抛砖引玉，体会一下。