GuoXin Li's Blog

区域生长&区域分割与合成&分水岭算法

BuaaAssignments
字数统计: 1.7k阅读时长: 9 min
2020/11/14 Share

区域生长算法，区域分裂与合成算法，分水岭分割算法

区域生长算法

算法实现

  • 根据图像的不同应用选择一个或一组种子，它或为最亮或最暗或点簇中心的点
  • 确定相似性准则即生长准则（条件）
  • 从该种子开始不断向外扩张，首先将种子像素加入集合，然后不断将与几何中各个像素连通、且满足描述准则的像素加入集合
  • 上一过程进行到不再有满足条件的新的节点加入集合为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import cv2
import numpy as np
import random
import sys
import numpy

#class pour une pile
class Stack():
    def __init__(self):
        self.item = []
        self.obj=[]
    def push(self, value):
        self.item.append(value)

    def pop(self):
        return self.item.pop()

    def size(self):
        return len(self.item)

    def isEmpty(self):
        return self.size() == 0

    def clear(self):
        self.item = []

class regionGrow():

    def __init__(self,im_path,th):
        self.readImage(im_path)
        self.h, self.w,_ =  self.im.shape
        self.passedBy = np.zeros((self.h,self.w), np.double)
        self.currentRegion = 0
        self.iterations=0
        self.SEGS=np.zeros((self.h,self.w,3), dtype='uint8')
        self.stack = Stack()
        self.thresh=float(th)
    def readImage(self, img_path):
        self.im = cv2.imread(img_path,1)


    def getNeighbour(self, x0, y0):
        neighbour = []
        for i in (-1,0,1):
            for j in (-1,0,1):
                if (i,j) == (0,0):
                    continue
                x = x0+i
                y = y0+j
                if self.limit(x,y):
                    neighbour.append((x,y))
        return neighbour
    def ApplyRegionGrow(self):
        randomseeds=[[self.h/2,self.w/2],
            [self.h/3,self.w/3],[2*self.h/3,self.w/3],[self.h/3-10,self.w/3],
            [self.h/3,2*self.w/3],[2*self.h/3,2*self.w/3],[self.h/3-10,2*self.w/3],
            [self.h/3,self.w-10],[2*self.h/3,self.w-10],[self.h/3-10,self.w-10]
                    ]
        np.random.shuffle(randomseeds)
        for x0 in range (self.h):
            for y0 in range (self.w):

                if self.passedBy[x0,y0] == 0 and (int(self.im[x0,y0,0])*int(self.im[x0,y0,1])*int(self.im[x0,y0,2]) > 0) :
                    self.currentRegion += 1
                    self.passedBy[x0,y0] = self.currentRegion
                    self.stack.push((x0,y0))
                    self.prev_region_count=0
                    while not self.stack.isEmpty():
                        x,y = self.stack.pop()
                        self.BFS(x,y)
                        self.iterations+=1
                    if(self.PassedAll()):
                        break
                    if(self.prev_region_count<8*8):
                        self.passedBy[self.passedBy==self.currentRegion]=0
                        x0=random.randint(x0-4,x0+4)
                        y0=random.randint(y0-4,y0+4)
                        x0=max(0,x0)
                        y0=max(0,y0)
                        x0=min(x0,self.h-1)
                        y0=min(y0,self.w-1)
                        self.currentRegion-=1

        for i in range(0,self.h):
            for j in range (0,self.w):
                val = self.passedBy[i][j]
                if(val==0):
                    self.SEGS[i][j]=255,255,255
                else:
                    self.SEGS[i][j]=val*35,val*90,val*30
        if(self.iterations>200000):
            print("Max Iterations")
        print("Iterations : "+str(self.iterations))
        cv2.imshow("",self.SEGS)
        # return self.SEGS
        cv2.waitKey(0)
        cv2.destroyAllWindows()

    def BFS(self, x0,y0):
        regionNum = self.passedBy[x0,y0]
        elems=[]
        elems.append((int(self.im[x0,y0,0])+int(self.im[x0,y0,1])+int(self.im[x0,y0,2]))/3)
        var=self.thresh
        neighbours=self.getNeighbour(x0,y0)

        for x,y in neighbours:
            if self.passedBy[x,y] == 0 and self.distance(x,y,x0,y0)<var:
                if(self.PassedAll()):
                    break
                self.passedBy[x,y] = regionNum
                self.stack.push((x,y))
                elems.append((int(self.im[x,y,0])+int(self.im[x,y,1])+int(self.im[x,y,2]))/3)
                var=np.var(elems)
                self.prev_region_count+=1
            var=max(var,self.thresh)


    def PassedAll(self):

        return self.iterations>200000 or np.count_nonzero(self.passedBy > 0) == self.w*self.h

    def limit(self, x,y):
        return  0<=x<self.h and 0<=y<self.w
    def distance(self,x,y,x0,y0):
        return ((int(self.im[x,y,0])-int(self.im[x0,y0,0]))**2+(int(self.im[x,y,1])-int(self.im[x0,y0,1]))**2+(int(self.im[x,y,2])-int(self.im[x0,y0,2]))**2)**0.5

img = "./food.jpg"
imgorin = cv2.imread(img,1)
# imgorin = imgorin[:,:,[2,1,0]]  #show original in plt: cv2 is BGR, plt is RGB
cv2.imshow("original", imgorin)
exemple = regionGrow(img,15)
exemple.ApplyRegionGrow()

Screen Shot 2020-11-13 at 19.20.32

区域分裂与合成算法

算法实现

  • 对于图像中灰度级别不同的区域，均分为四个子区域
  • 如果相邻的子区域所有像素的灰度级相同，则将其合并
  • 反复进行上述两步操作，直至不再有新的分裂与合并为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import cv2
from matplotlib.pyplot import imread
import numpy as np
import matplotlib.pyplot as plt

# calculate std of a cube of the image
def stdRight(h0, w0, h, w):
    value = img[h0 : h0+h, w0: w0+w]
    # print(value)
    cal_std = np.std(value, ddof=1)
    print(cal_std)
    if abs(cal_std) < 20:
        return False
    else:
        return True

def thresholdFuc(h0, w0, h, w):
    for i in range(w0, w0+w):
        for j in range(h0, h0 + h):
            if img[j, i] > 127:
                img[j, i] = 255
            else:
                img[j, i] = 0

# iteration for split when condition is true(condition is the std of a cube of img )
def iterationSplit(h0, w0, h, w):
    if stdRight(h0, w0, h, w) and min(h,w) > 5:
        iterationSplit(h0, w0, int(h / 2), int( w / 2 ))
        iterationSplit(h0 + int(h / 2), w0, int(h / 2), int( w / 2 ))
        iterationSplit(h0, w0 + int( w / 2), int(h / 2), int( w / 2 ))
        iterationSplit(h0 + int(h / 2), w0 + int( w / 2), int(h / 2), int( w / 2 ))
    else:
        thresholdFuc(h0, w0, h, w)
        # ret, img[h0 : h, w0 : w]= cv2.threshold(img[h0:h, w0 : w], 50, 255, cv2.THRESH_BINARY)

img = cv2.imread("./hy.jpg", 0)
img_copy = img.copy()
print(img.shape)
h, w = img.shape
iterationSplit(0, 0, h, w)

#cv2.cvtColor() change BGR to RGB
plt.subplot(1,2,1), plt.imshow(cv2.cvtColor(img_copy, cv2.COLOR_BGR2RGB)), plt.title("Original")
plt.subplot(1,2,2), plt.imshow(cv2.cvtColor(img, cv2.COLOR_BGR2RGB)), plt.title("Result")
plt.show()

image-20201113223633344

Reference:

分水岭分割算法

分割原理

  • 任何的灰度级图像都可以被看作是一个地形图

    image-20201111163807118

  • 假设从每个区域的最小值地方水位上涨，直至淹没整个地形，当处于不同的汇聚盆地的水将要汇聚到一起的时候，修剪大坝阻止聚合，最后得到水坝分界就是分水岭的分割线。

  • 用1标记非对象（背景）的区域

  • 用0标记不确定的区域

  • 然后应用分水岭算法，用之前标记出的标签进行不断更新，标记对象的边界值为-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt

def watershedFuc(img):
    #threshold Otsu
    gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
    ret, thresh = cv.threshold(gray,0,255,cv.THRESH_BINARY_INV+cv.THRESH_OTSU)

    # noise removal
    kernel = np.ones((3,3),np.uint8)
    opening = cv.morphologyEx(thresh,cv.MORPH_OPEN,kernel, iterations = 5)
    # sure background area
    sure_bg = cv.dilate(opening,kernel,iterations=5)
    # Finding sure foreground area
    dist_transform = cv.distanceTransform(opening,cv.DIST_L2, 5)
    ret, sure_fg = cv.threshold(dist_transform,0.7*dist_transform.max(),255,0)
    # Finding unknown region
    sure_fg = np.uint8(sure_fg)
    unknown = cv.subtract(sure_bg,sure_fg)

    # Marker labelling
    ret, markers = cv.connectedComponents(sure_fg)
    # Add one to all labels so that sure background is not 0, but 1
    markers = markers+1
    # Now, mark the region of unknown with zero
    markers[unknown==255] = 0

    # Apply watershed
    markers = cv.watershed(img,markers)
    img[markers == -1] = [255,0,0]

    return img

if __name__ == "__main__":
    img1 = cv.imread('./egg.jpg')
    plt.subplot(2,2,1),plt.imshow(img1), plt.title("eggOrin"), plt.xticks([]), plt.yticks([])

    img2 = cv.imread('./coins.jpg')
    plt.subplot(2,2,3),plt.imshow(img2), plt.title("coinOrin"), plt.xticks([]), plt.yticks([])

    img = [img1, img2]
    title = ["coinwatershed", 'eggwatershed']
    for i in range(2):
        result = watershedFuc(img[i])
        plt.subplot(2,2,2**(i+1)),plt.imshow(result), plt.title(title[i]), plt.xticks([]), plt.yticks([])
    plt.show()

效果图

image-20201111164111409

Reference： https://docs.opencv.org/master/d3/db4/tutorial_py_watershed.html

总结

  • 区域生长算法能够显示出具有相同特征的一些像素块，区分度较高，但是算法较为非时间，要确定好初始种子值和不再继续扩张的条件
  • 区域分裂与合成算法，分块进行相同灰度级像素的合并和不同像素灰度级的分裂，直至不能再分裂为止，这里设定的不能分裂的条件使用的是方差，对于相差小的大块状的背景很容易在前几次分裂与合并中被直接去分开（例如，天空中的白云）进而直接被差值化
  • 分水岭算法对于寻找边界非常明显，可以很好的找出目标对象的轮廓
CATALOG
  1. 1. 区域生长算法，区域分裂与合成算法，分水岭分割算法
    1. 1.1. 区域生长算法
    2. 1.2. 区域分裂与合成算法
    3. 1.3. 分水岭分割算法
      1. 1.3.1. 分割原理
      2. 1.3.2. 总结
Total : 89
2022
2021
2020
2019
2018
essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
Machine-Learning Data-Structure