邻域连通性标记

4− 邻域连通域标记

  • 连通域标记（Connected Component Labeling）是将邻接的像素打上相同的标记的作业。
  • 具体思路
  1. 从左上角开始进行光栅扫描。
  2. 如果当前遍历到的像素i(x,y)是黑像素的什么也不干。如果是白像素，考察该像素的上方像素i(x,y-1)和左边像素i(x-1,y)，如果两个的取值都为0，将该像素分配一个新的标签。
  3. 如果两个像素中有一个不为0（也就是说已经分配了标签），将上方和左边的像素分配的标签中数值较小的那一个（0除外）分配给当前遍历到的像素i(x,y)。在这里，将上方像素和左边像素的标签写入Lookup Table的Source，将当前遍历的像素i(x,y)分配的标签写入Distination。
  4. 最后，对照Lookup Table，对像素分配的标签由Source变为Distination。
  • 像这样的话，邻接像素就可以打上同样的标签了。因为这里是做4−邻域连通域标记，所以我们只用考察上方像素和左边像素
  • 这里需要注意以下，因为要用不同的颜色对不同区域进行填充，因此下方代码中使用的图片是三通道的，尽管可能是对二值化的图像进行处理，但是仍需转为三通道图片
  • 下图为初始图片

  • 依据上述方法打标完毕后，后将白色区域打标为[2,3,4,5,6,7,8]7个值，切分成其部分，其中3，4，5明显为一大块可以合并，同样6，7也为一大块可以合并，下述代码中就巧妙地解决了这个问题


    seg.png
  • 下图为做标记之后的图片
  • out.png
img = cv2.imread("1.jpg").astype(np.float32) #读取图片
H, W, C = img.shape#获取图片尺寸大小
label = np.zeros((H, W), dtype=np.int)#制作label矩阵
label[img[..., 0] > 0] = 1#将label与img对应255的位置标为1，即值为0的不打标，为1的才是我们需要重新打标的范畴
LUT = [0 for _ in range(H * W)]#LUT初始化为0，长度为img像素点个数
n = 1
#这个循环是对每个像素点进行打标
for y in range(H):
    for x in range(W):
        if label[y, x] == 0:#如果为0，跳过本次循环，进入x+1进行下一次循环
            continue
        c3 = label[max(y - 1, 0), x]#不为0，取到(y-1,x)对应坐标的label值，上侧坐标
        c5 = label[y, max(x - 1, 0)]#不为0，取到(y,x-1)对应坐标的label值，左侧坐标
        if c3 < 2 and c5 < 2:#如果c3<2并且c5<2，则表示上侧及左侧像素均未被标记。因为0，1标签号相当于初始号，因此不算新做的标签号
            n += 1#则将标签号加上1
            label[y, x] = n#将该位置设置新的标签号
        else:
            _vs = [c3, c5]#如果上侧或左侧有被标记的像素点
            vs = [a for a in _vs if a > 1]#将两个标签号拿出来，vs可能有一个值，这个时候位于边界上，也可能有两个值，此时涉及到标签合并
            v = min(vs)#取最小但大于1的标签号，因为0，1标签号相当于初始号，因此不算新做的标签号
            label[y, x] = v#将该位置标签号设置为较小的标签号，至此，label矩阵中标签值不会发生变化，后面的代码就涉及到后期的标签值合并
            minv = v#
            for _v in vs:
                if LUT[_v] != 0:
                    minv = min(minv, LUT[_v])#如果位置已被占据，就更新他
            for _v in vs:
                LUT[_v] = minv#如果位置没有被占，就顺次填充LUT
count = 1
for l in range(2, n + 1):
    flag = True
    for i in range(n + 1):
        if LUT[i] == l:
            if flag:
                count += 1
                flag = False
            LUT[i] = count
COLORS = [[0, 0, 255], [0, 255, 0], [255, 0, 0], [255, 255, 0]]#设置颜色范围，这个地方可以优化，基本原理理解即可
out = np.zeros((H, W, C), dtype=np.uint8)
for i, lut in enumerate(LUT[2:]):#对打标的相应位置进行填色
    out[label == (i + 2)] = COLORS[lut - 2]#因为打标从2开始打起，因此用colors[lut-2]来选取颜色

八邻域-连通域标记

  • 要进行8−邻域连通域标记，我们需要考察i(x-1,y-1)，i(x, y-1)，i(x+1,y-1)，i(x-1,y)这4个像素
import cv2
import numpy as np
import matplotlib.pyplot as plt
# Read image
img = cv2.imread("seg.png").astype(np.float32)
H, W, C = img.shape
label = np.zeros((H, W), dtype=np.int)
label[img[..., 0]>0] = 1
LUT = [0 for _ in range(H*W)]
n = 1
for y in range(H):
    for x in range(W):
        if label[y, x] == 0:
            continue
        c2 = label[max(y-1,0), min(x+1, W-1)]#右上
        c3 = label[max(y-1,0), x]#正上
        c4 = label[max(y-1,0), max(x-1,0)]#左上
        c5 = label[y, max(x-1,0)]#左
        if c3 < 2 and c5 < 2 and c2 < 2 and c4 < 2:
            n += 1
            label[y, x] = n
        else:
            _vs = [c3, c5, c2, c4]
            vs = [a for a in _vs if a > 1]
            v = min(vs)
            label[y, x] = v
            minv = v
            for _v in vs:
                if LUT[_v] != 0:
                    minv = min(minv, LUT[_v])
            for _v in vs:
                LUT[_v] = minv 
count = 1
for l in range(2, n+1):
    flag = True
    for i in range(n+1):
        if LUT[i] == l:
            if flag:
                count += 1
                flag = False
            LUT[i] = count
COLORS = [[0, 0, 255], [0, 255, 0], [255, 0, 0], [255, 255, 0]]
out = np.zeros((H, W, C), dtype=np.uint8)
for i, lut in enumerate(LUT[2:]):
    out[label == (i+2)] = COLORS[lut-2]
# Save result
cv2.imwrite("out.png", out)
cv2.imshow("result", out)
cv2.waitKey(0)
cv2.destroyAllWindows()

图像透明混合

  • 将img1和img2按1:1的比例重合的时候，使用下面的式子。通过改变 Alpha 值，你可以更改两张图片重叠的权重。
    out = img1 * alpha + img2 * (1 - alpha)一行代码即可实现，但要确保img1和img2的图像尺寸一致

4连接数

  • 4− 连接数可以用于显示附近像素的状态。通常，对于中心像素x0(x，y)不为零的情况，邻域定义如下：
  • x4(x−1,y−1),x3(x,y−1),x2(x+1,y−1), x5(x−1,y), x0(x,y), x1(x+1,y),x6(x−1,y+1), x7(x,y+1), x8(x+1,y+1),逆时针的八个像素构成八邻域
  • 这里，4−连接数通过以下等式计算：
  • S=(x1−x1x2x3)+(x3−x3x4x5)+(x5−x5 x6x7)+(x7−x7x8x1)
  • S的取值范围为[0,4]：
  • S=0： 内部点；
  • S=1：端点；
  • S=2：连接点；
  • S=3：分支点；
  • S=4：交叉点。
def connect_4(img):
    # get shape
    H, W, C = img.shape#获取图像尺寸
    # prepare temporary image准备临时图片，大小和输入大小一致
    tmp = np.zeros((H, W), dtype=np.int)
    # binarize
    tmp[img[..., 0] > 0] = 1#白色区域打标1
    # prepare out image #准备输出文件
    out = np.zeros((H, W, 3), dtype=np.uint8)
    # each pixel
    for y in range(H):
        for x in range(W):
            if tmp[y, x] < 1:
                continue
            S = 0
            S += (tmp[y,min(x+1,W-1)] - tmp[y,min(x+1,W-1)] * tmp[max(y-1,0),min(x+1,W-1)] * tmp[max(y-1,0),x])
            S += (tmp[max(y-1,0),x] - tmp[max(y-1,0),x] * tmp[max(y-1,0),max(x-1,0)] * tmp[y,max(x-1,0)])
            S += (tmp[y,max(x-1,0)] - tmp[y,max(x-1,0)] * tmp[min(y+1,H-1),max(x-1,0)] * tmp[min(y+1,H-1),x])
            S += (tmp[min(y+1,H-1),x] - tmp[min(y+1,H-1),x] * tmp[min(y+1,H-1),min(x+1,W-1)] * tmp[y,min(x+1,W-1)])
            if S == 0:#内部点
                out[y,x] = [0, 0, 255]
            elif S == 1:#端点
                out[y,x] = [0, 255, 0]
            elif S == 2:#连接点
                out[y,x] = [255, 0, 0]
            elif S == 3:#分支点
                out[y,x] = [255, 255, 0]
            elif S == 4:#交叉点
                out[y,x] = [255, 0, 255]
    out = out.astype(np.uint8)
    return out
# Read image
img = cv2.imread("renketsu.png").astype(np.float32)
# connect 4
out = connect_4(img)
5678.jpg

8连接数

  • 将各个x∗的值反转0和1计算
  • S=(x1−x1 x2 x3)+(x3−x3 x4 x5)+(x5−x5 x6 x7)+(x7−x7x8x1)
# connect 8
def connect_8(img):
    # get shape
    H, W, C = img.shape
    # prepare temporary
    _tmp = np.zeros((H, W), dtype=np.int)
    # get binarize
    _tmp[img[..., 0] > 0] = 1
    # inverse for connect 8
    tmp = 1 - _tmp#与上述代码唯一的差别
    # prepare image
    out = np.zeros((H, W, 3), dtype=np.uint8)
    # each pixel
    for y in range(H):
        for x in range(W):
            if _tmp[y, x] < 1:
                continue
            S = 0
            S += (tmp[y,min(x+1,W-1)] - tmp[y,min(x+1,W-1)] * tmp[max(y-1,0),min(x+1,W-1)] * tmp[max(y-1,0),x])
            S += (tmp[max(y-1,0),x] - tmp[max(y-1,0),x] * tmp[max(y-1,0),max(x-1,0)] * tmp[y,max(x-1,0)])
            S += (tmp[y,max(x-1,0)] - tmp[y,max(x-1,0)] * tmp[min(y+1,H-1),max(x-1,0)] * tmp[min(y+1,H-1),x])
            S += (tmp[min(y+1,H-1),x] - tmp[min(y+1,H-1),x] * tmp[min(y+1,H-1),min(x+1,W-1)] * tmp[y,min(x+1,W-1)])
            if S == 0:
                out[y,x] = [0, 0, 255]
            elif S == 1:
                out[y,x] = [0, 255, 0]
            elif S == 2:
                out[y,x] = [255, 0, 0]
            elif S == 3:
                out[y,x] = [255, 255, 0]
            elif S == 4:
                out[y,x] = [255, 0, 255] 
    out = out.astype(np.uint8)
    return out
# Read image
img = cv2.imread("renketsu.png").astype(np.float32)
# connect 8
out = connect_8(img)

细化处理

细化是将线条宽度设置为1的过程，按照下面的算法进行处理

  1. 从左上角开始进行光栅扫描
  2. 如果x0(x,y)=0，不处理。如果x0(x,y)=1，满足下面三个条件时，令x0=0：
  • 4−近邻像素的取值有一个以上为0；
  • x0的4−连接数为1；
  • x0的8−近邻中有三个以上取值为1。
  1. 重复光栅扫描，直到步骤2中像素值改变次数为0。
# thining algorythm细化处理
def thining(img):
    # get shape
    H, W, C = img.shape#获取图像尺寸
    # prepare out image#准备输出图像
    out = np.zeros((H, W), dtype=np.int)#初始化
    out[img[..., 0] > 0] = 1#对白色区域打标
    count = 1
    while count > 0:
        count = 0
        tmp = out.copy()
        # each pixel ( rasta scan )
        for y in range(H):
            for x in range(W):
                # skip black pixel
                if out[y, x] < 1:#黑色区域直接遍历下一个像素
                    continue                
                # count satisfied conditions
                judge = 0#设置第二步的初始判定值为0，当三个条件满足，判定值每次+1等于3时完成判定                
                ## condition 1
                if (tmp[y, min(x+1, W-1)] + tmp[max(y-1, 0), x] + tmp[y, max(x-1, 0)] + tmp[min(y+1, H-1), x]) < 4:
                    judge += 1                    
                ## condition 2
                c = 0
                c += (tmp[y,min(x+1, W-1)] - tmp[y, min(x+1, W-1)] * tmp[max(y-1, 0),min(x+1, W-1)] * tmp[max(y-1, 0), x])
                c += (tmp[max(y-1,0), x] - tmp[max(y-1,0), x] * tmp[max(y-1, 0), max(x-1, 0)] * tmp[y, max(x-1, 0)])
                c += (tmp[y, max(x-1, 0)] - tmp[y,max(x-1, 0)] * tmp[min(y+1, H-1), max(x-1, 0)] * tmp[min(y+1, H-1), x])
                c += (tmp[min(y+1, H-1), x] - tmp[min(y+1, H-1), x] * tmp[min(y+1, H-1), min(x+1, W-1)] * tmp[y, min(x+1, W-1)])
                if c == 1:
                    judge += 1                    
                ##x condition 3
                if np.sum(tmp[max(y-1, 0) : min(y+2, H), max(x-1, 0) : min(x+2, W)]) >= 4:
                    judge += 1              
                # if all conditions are satisfied
                if judge == 3:
                    out[y, x] = 0
                    count += 1#完成判定，count加1，如果不成立，count等于0跳出最终循环
    out = out.astype(np.uint8) * 255
    return out
# Read image
img = cv2.imread("gazo.png").astype(np.float32)
# thining
out = thining(img)

Hilditch 细化算法

算法如下

  1. 从左上角开始进行光栅扫描；
  2. x0(x,y)=0的话、不进行处理。x0(x,y)=1的话，下面五个条件都满足的时候令x0=−1：
  • 当前像素的4−近邻中有一个以上0；
  • x0的8−连接数为1；
  • x1至x8の绝对值之和大于2；
    8−近邻像素的取值有一个以上为1；
    对所有xn(n∈[1,8])以下任一项成立：
  • xn不是−1；
  • 当xn为0时，x0的8−连接数为1。
  1. 将每个像素的−1更改为0；
  2. 重复进行光栅扫描，直到某一次光栅扫描中步骤3的变化数变为0。

Zhang-Suen细化算法

基本原理

  • 对于中心像素x1(x,y)的8−近邻定义如下：x9 x2 x3 x8 x1 x4 x7 x6 x5
  • 步骤一：执行光栅扫描并标记满足以下5个条件的所有像素：
  1. 这是一个黑色像素；
  2. 顺时针查看x2、x3、⋯、x9、x2时，从0到1​的变化次数仅为1；
  3. x2、x3、⋯、x9中1的个数在2个以上6个以下；
  4. x2、x4、x6中的一个为1；
  5. x4、x6、x8中的一个为1；
    将标记的像素全部变为1。
  • 步骤二：执行光栅扫描并标记满足以下5个条件的所有像素：
  1. 这是一个黑色像素；
  2. 顺时针查看x2、x3、⋯、x9、x2时，从0到1的变化次数仅为1；
  3. x2、x3、⋯、x9中1的个数在2个以上6个以下；
  4. x2、x4、x6中的一个为1；
  5. x2、x6、x8中的一个为1；
    将标记的像素全部变为1。
  • 反复执行步骤一和步骤二直到没有点变化。
# Zhang Suen thining algorythm
def Zhang_Suen_thining(img):
    # get shape
    H, W, C = img.shape
    # prepare out image
    out = np.zeros((H, W), dtype=np.int)
    out[img[..., 0] > 0] = 1
    # inverse
    out = 1 - out
    while True:
        s1 = []
        s2 = []
        # step 1 ( rasta scan )
        for y in range(1, H-1):
            for x in range(1, W-1):           
                # condition 1
                if out[y, x] > 0:
                    continue
                # condition 2
                f1 = 0
                if (out[y-1, x+1] - out[y-1, x]) == 1:
                    f1 += 1
                if (out[y, x+1] - out[y-1, x+1]) == 1:
                    f1 += 1
                if (out[y+1, x+1] - out[y, x+1]) == 1:
                    f1 += 1
                if (out[y+1, x] - out[y+1,x+1]) == 1:
                    f1 += 1
                if (out[y+1, x-1] - out[y+1, x]) == 1:
                    f1 += 1
                if (out[y, x-1] - out[y+1, x-1]) == 1:
                    f1 += 1
                if (out[y-1, x-1] - out[y, x-1]) == 1:
                    f1 += 1
                if (out[y-1, x] - out[y-1, x-1]) == 1:
                    f1 += 1
                if f1 != 1:
                    continue          
                # condition 3
                f2 = np.sum(out[y-1:y+2, x-1:x+2])
                if f2 < 2 or f2 > 6:
                    continue        
                # condition 4
                if out[y-1, x] + out[y, x+1] + out[y+1, x] < 1:
                    continue
                # condition 5
                if out[y, x+1] + out[y+1, x] + out[y, x-1] < 1:
                    continue                    
                s1.append([y, x])
        for v in s1:
            out[v[0], v[1]] = 1
        # step 2 ( rasta scan )
        for y in range(1, H-1):
            for x in range(1, W-1):        
                # condition 1
                if out[y, x] > 0:
                    continue
                # condition 2
                f1 = 0
                if (out[y-1, x+1] - out[y-1, x]) == 1:
                    f1 += 1
                if (out[y, x+1] - out[y-1, x+1]) == 1:
                    f1 += 1
                if (out[y+1, x+1] - out[y, x+1]) == 1:
                    f1 += 1
                if (out[y+1, x] - out[y+1,x+1]) == 1:
                    f1 += 1
                if (out[y+1, x-1] - out[y+1, x]) == 1:
                    f1 += 1
                if (out[y, x-1] - out[y+1, x-1]) == 1:
                    f1 += 1
                if (out[y-1, x-1] - out[y, x-1]) == 1:
                    f1 += 1
                if (out[y-1, x] - out[y-1, x-1]) == 1:
                    f1 += 1
                if f1 != 1:
                    continue
                # condition 3
                f2 = np.sum(out[y-1:y+2, x-1:x+2])
                if f2 < 2 or f2 > 6:
                    continue                
                # condition 4
                if out[y-1, x] + out[y, x+1] + out[y, x-1] < 1:
                    continue
                # condition 5
                if out[y-1, x] + out[y+1, x] + out[y, x-1] < 1:
                    continue
                s2.append([y, x])
        for v in s2:
            out[v[0], v[1]] = 1
        # if not any pixel is changed
        if len(s1) < 1 and len(s2) < 1:
            break
    out = 1 - out
    out = out.astype(np.uint8) * 255
    return out
# Read image
img = cv2.imread("gazo.png").astype(np.float32)
# Zhang Suen thining
out = Zhang_Suen_thining(img)
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,496评论 6赞 501
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,407评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,632评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,180评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,198评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,165评论 1赞 299
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,052评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,910评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,324评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,542评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,711评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,424评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,017评论 3赞 326
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,668评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,823评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,722评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,611评论 2赞 353