区域生长：广度优先和深度优先搜索
区域生长算法：从图像的某个点开始，使每块区域扩大，直到被比较的像素与区域像素具有显著差异为止。
区域生长可以用于图像分割。
问题定义：
给定一个生长的起始种子点(starty,startx)，作为初始区域；
以一定规则向其邻域生长，即将周围相似的点包含在区域内并作为新的种子继续生长；
直到没有满足规则条件的点时停止。
本代码采用的生长准则：待测像素点和区域平均像素值的差小于等于20，8邻域生长，停止生长条件为区域饱和。
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
# 读取图像(这种方法读出来就是array类型)(高、宽、色彩)
Image = mpimg.imread('C:/Users/Jichen/Downloads/lotus.jpg')
height = len(Image)
width = len(Image[0])
color = len(Image[0][0]) # 若== 3,为RGB
# 获取红色通道的值(RGB)
Redpath = np.zeros([height,width])
for i in range(height):
for j in range(width):
Redpath[i][j] = Image[i][j][0]
def AreaGrowth(Image,starty,startx,neighbors,diff):
'''
从位置(startx,starty)开始，增长区域，直到被比较的像素与区域像素有显著差异为止
Parameters
----------
Image : array
startx : int
starty : int
neighbors : list
邻域
diff : int
当当前像素与区域像素差值小于等于diff时，生长
Returns
-------
生长后的region_array
'''
height = len(Image)
width = len(Image[0])
region = np.zeros([height,width]) # 初始化生长区域
region[starty,startx] = 1 # 初始点为生长区域内一点
region_pixel_num = 1 # 生长区域只有一个点(startx,starty)
region_pixel_mean = Image[starty,startx] # 初始化区域平均像素值
flag = np.zeros([height,width]); # 标记点是否被访问过，避免重复访问
flag[starty,startx] = 1 # 标记起始点已被访问
neighbor_num = len(neighbors) # 生长邻域数目
waiting = [] # 待搜索的点
for i in range(neighbor_num): # 访问起始点
neighbor = neighbors[i]
y = starty + neighbor[0] # 邻域内点的坐标
x = startx + neighbor[1]
waiting.append([y,x]) # 加入待搜索列表并作带搜索标记
flag[y,x] = 2
pos = 0
waitlen = len(waiting)
while(pos<waitlen):
current = waiting[pos] # 取出当前的坐标
pixel = Image[current[0],current[1]] # 取出当前坐标的像素值
# 判断当前像素值和区域平均像素值之间的差异
real_diff = abs(pixel - region_pixel_mean)
if(real_diff <= diff):
region[current[0],current[1]] = 1 # 小于差异，该点为区域内一点
region_pixel_mean = region_pixel_mean * region_pixel_num + pixel # 更新区域数目和均值
region_pixel_num = region_pixel_num + 1
region_pixel_mean = region_pixel_mean / region_pixel_num
# 该点的邻域如果合法且没有被访问或加入到访问列表中，将被加入到待访问列表
for neighbor in neighbors:
neighbor_y = current[0] + neighbor[0]
neighbor_x = current[1] + neighbor[1]
if(neighbor_y>=0 and neighbor_y<height and neighbor_x>=0 and neighbor_x<width and flag[neighbor_y][neighbor_x]==0):
waiting.append([neighbor_y,neighbor_x])
flag[neighbor_y,neighbor_x] = 2
pos += 1
waitlen = len(waiting)
return region
# 应用区域生长函数
starty = round(height/2) # 从中心点开始生长
startx = round(width/2)
neighbors = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]] # 八邻域
diff = 20 # 与区域平均值差异为20时生长
growth_region = AreaGrowth(Redpath, starty, startx, neighbors, diff)
# 将array画图
plt.figure()
subplot(121)
plt.imshow(Redpath)
subplot(122)
plt.imshow(growth_region)
还尝试了一下深度优先搜索，但是内核down了。我不太清楚原因，可能是由于该图像的像素值太接近了，导致搜索深度太深。
这里设置diff=3
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
# 读取图像(这种方法读出来就是array类型)(高、宽、色彩)
Image = mpimg.imread('C:/Users/Jichen/Downloads/lotus.jpg')
height = len(Image)
width = len(Image[0])
color = len(Image[0][0])
# 获取红色通道的值(RGB)
Redpath = np.zeros([height,width])
for i in range(height):
for j in range(width):
Redpath[i][j] = Image[i][j][1]
### 用深度优先搜索
# 会出现一种情况：diff大了，图像又比较相似，会不断深搜，陷入大量重复判断,kernel会down
def dfs(Image,visited,region,y,x,neighbors,region_pixel_mean,region_num,diff):
height = len(Image)
width = len(Image[0])
pixel = Image[y,x]
if(abs(pixel - region_pixel_mean) <= diff): # 判断当前像素属于区域
region[y,x] = 1
region_pixel_mean = region_pixel_mean*region_num + pixel
region_num = region_num + 1
region_pixel_mean = region_pixel_mean / region_num
for neighbor in neighbors:
yy = y + neighbor[0]
xx = x + neighbor[1]
if(yy>=0 and yy<height and xx>=0 and xx < width and visited[yy,xx]==0): # 如果合法且没有被访问过
visited[yy,xx] = 1 # 标记已经被访问
dfs(Image,visited,region,yy,xx,neighbors,region_pixel_mean,region_num,diff) # 递归进行深度优先搜索
def AreaGrowth2(Image,starty,startx,neighbors,diff):
# 图像的大小
height = len(Image)
width = len(Image[0])
# 创建访问矩阵，避免重复访问
visited = np.zeros([height,width])
# 创建区域矩阵并初始化
region = np.zeros([height,width])
region[starty,startx] = 1
region_pixel_mean = Image[starty,startx]
region_num = 1
# 深度优先搜索
visited[starty,startx] = 1
dfs(Image,visited,region,starty,startx,neighbors,region_pixel_mean,region_num,diff)
return region
# 应用区域生长函数
starty = round(height/2)
startx = round(width/2)
neighbors = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
diff = 3
growth_region = AreaGrowth2(Redpath, starty, startx, neighbors, diff)
# 将array画图
plt.subplot(121)
plt.imshow(Redpath)
plt.subplot(122)
plt.imshow(growth_region)
