邻域连通性标记

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)不为零的情况，邻域定义如下：
• ,,, , , ,, , ,逆时针的八个像素构成八邻域
• 这里，4−连接数通过以下等式计算：
• 
• 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连接数

• 将各个的值反转0和1计算
• 

# 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. 如果，不处理。如果，满足下面三个条件时，令：

• 4−近邻像素的取值有一个以上为0；
• x0的4−连接数为1；
• x0的8−近邻中有三个以上取值为1。

3. 重复光栅扫描，直到步骤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. 的话、不进行处理。的话，下面五个条件都满足的时候令：

• 当前像素的4−近邻中有一个以上0；
• x0的8−连接数为1；
• x1至x8の绝对值之和大于2；
  8−近邻像素的取值有一个以上为1；
  对所有xn(n∈[1,8])以下任一项成立：
• 不是−1；
• 当为0时，x0的8−连接数为1。

3. 将每个像素的−1更改为0；
4. 重复进行光栅扫描，直到某一次光栅扫描中步骤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)