Ну, за последние дни я создал что-то, что, кажется, работает. Буду признателен за любые мысли и комментарии о том, как его улучшить. Я использую Python 3.7.
Сначала создается словарь с метками регионов в качестве ключей и списками векторов, связанных с 8 соседями, в качестве значений:
def extract_regions(image):
# find the entire 8-neighbors-connected region of the given pixel
def label_region(center_x=0, center_y=0, region_label=0):
# define the 3x3 neighborhood around the center pixel; I try not wrap around, not sure if that's needed
from_x = center_x - 1 if center_x >= 1 else 0
to_x = center_x + 2 if center_x + 2 <= len(image) else len(image)
from_y = center_y - 1 if center_y >= 1 else 0
to_y = center_y + 2 if center_y + 2 <= len(image[center_x]) else len(image[center_x])
# find pixels in the neighborhood and label them
b = from_x
for line in image[from_x:to_x]:
a = from_y
for neighbor in line[from_y:to_y]:
if neighbor:
if not (a, b) in coords_to_label:
coords_to_label.update({(a, b): region_label})
# repeat for neighbor
label_region(b, a, region_label)
a += 1
b += 1
# find pixels in the image, which are not labeled yet
coords_to_label = {}
y = 0
label = 0
for line in image:
x = 0
for pixel in line:
if pixel: # i.e. pixel is 1
if not (x, y) in coords_to_label: # i.e. pixel is not labeled
# apply new label to the pixel
coords_to_label.update({(x, y): label})
# label the whole region the pixel belongs to
label_region(y, x, label)
# update label
label += 1
# keep track of pixel position
x += 1
y += 1
# invert coords_to_label, i.e. set labels as keys and lists of vectors as values
label_to_region = {}
for i in range(label):
label_to_region.update({i: []})
for key, val in coords_to_label.items():
label_to_region[val].append(key)
return label_to_region
Далее эти регионы «разделены» на множество ломаных линий (мне кажется, это самая схематичная функция из всей группы, но, может быть, это нормально?):
def polylines_from_regions(dictionary_label_to_region):
neighborhood_size_squared = 2 ** 2
polylines = []
line_nr = -1
for key in dictionary_label_to_region: # i.e. for every region
line_nr += 1
# add first (starting) vector to the polyline
polylines.append([dictionary_label_to_region[key][0]])
for vector in dictionary_label_to_region[key][1:]:
# calculate distance between current vector and the vector last added to current polyline
x_diff = (vector[0] - polylines[line_nr][-1][0]) ** 2
y_diff = (vector[1] - polylines[line_nr][-1][1]) ** 2
distance_squared = x_diff + y_diff
if distance_squared < neighborhood_size_squared: # i.e. current vector is neighbor
# add neighbor to current polyline
polylines[line_nr].append(vector)
else:
# start new polyline
polylines.append([vector])
line_nr += 1
# remove single vector "lines"
long_lines = []
for i in polylines:
if len(i) > 1:
long_lines.append(i)
return long_lines
Эти ломаные затем «выпрямляются» out ":
def straight_line_segments_from_polylines(poly_line_list):
max_distance_from_line_squared = 4 ** 2
# turn a polyline into a (set of) straight line(s)
def straighten(p_line):
end = len(p_line) - 1
# get coordinates of first and last vector of the polyline
x1, y1 = p_line[0]
x2, y2 = p_line[-1]
# for distance calculation, see below
factor_x = y2 - y1
factor_y = x2 - x1
term = x2 * y1 - y2 * x1
denominator = (y2 - y1) ** 2 + (x2 - x1) ** 2
for i in range(1, end): # i.e. all vectors except first and last
x0, y0 = p_line[i]
# calculate distance between current vector and the line between first and last vector of the polyline
numerator = abs(factor_x * x0 - factor_y * y0 + term) ** 2
distance = numerator / denominator
if distance > max_distance_from_line_squared: # i.e. current vector is too far away from the straight line
# split the polyline at current vector, convert the now 2 polylines into sets of straight lines
return straight_line_segments_from_polylines([p_line[:i], p_line[i:]])
# return start and end vector of the polyline (a now straight line)
straight_line = [[p_line[0], p_line[-1]]]
return straight_line
straight_lines = []
for polyline in poly_line_list:
straight_lines += straighten(polyline)
return straight_lines
Наконец, эти прямые линии сравниваются друг с другом и объединяются, если они достаточно близки и достаточно похожи (для выполнения этой задачи требуется больше всего времени, поэтому любые советы приветствуются вдвойне):
import numpy as np
def combine_straight_lines(line_list):
distance_tolerance_squared = 5 ** 2
angle_tolerance = 2
min_line_length_squared = 15 ** 2
temp_line_list = line_list.copy()
lines_to_skip = []
# translates indices of the distance list (see below) to the corresponding vectors of the 2 lines (0: starting vector, 1: end vector)
vector_nr_table = {
0: (0, 0),
1: (1, 0),
2: (0, 1),
3: (1, 1)
}
for i in range(len(line_list)): # all lines
# vector coordinates of i
x0, y0 = temp_line_list[i][0]
x1, y1 = temp_line_list[i][1]
for j in range(i + 1, len(line_list)): # all lines _after_ i, as to not "double reference" (a -> b & b -> a)
# vector coordinates of j
a0, b0 = temp_line_list[j][0]
a1, b1 = temp_line_list[j][1]
# calculate distances between each pair of vectors from i and j
distance = (
(a0 - x0) ** 2 + (b0 - y0) ** 2, (a0 - x1) ** 2 + (b0 - y1) ** 2, (a1 - x0) ** 2 + (b1 - y0) ** 2,
(a1 - x1) ** 2 + (b1 - y1) ** 2)
smallest_distance = min(distance)
if smallest_distance <= distance_tolerance_squared: # i.e. the closest vectors are close enough
# calculate angle of the lines and compare
angle0 = get_straight_line_angle(temp_line_list[i])['deg']
angle1 = get_straight_line_angle(temp_line_list[j])['deg']
angle_diff = abs(angle1 - angle0)
if angle_diff <= angle_tolerance: # i.e. angles are similar
# determine the vectors of each line farthest away from each other, replace j with these vectors
max_dist = int(np.argmax(distance))
v0, v1 = vector_nr_table[max_dist]
temp_line_list[j] = [temp_line_list[i][v0], temp_line_list[j][v1]]
# line i has been incorporated into j, can be left out from result
lines_to_skip.append(i)
if lines_to_skip: # means lines have been combined
# remove incorporated lines
new_line_list = []
for i in range(len(temp_line_list)):
if i in lines_to_skip:
continue
else:
new_line_list.append(temp_line_list[i])
# rerun the function; not 100% sure whether additional runs are necessary
return combine_straight_lines(new_line_list)
else:
# remove short lines
new_line_list = []
for line in line_list:
if get_straight_line_length_squared(line) >= min_line_length_squared:
new_line_list.append(line)
return new_line_list
def get_straight_line_angle(line):
numerator = line[1][1] - line[0][1]
denominator = line[1][0] - line[0][0]
angle = np.pi / 2 if denominator == 0 else np.arctan(numerator / denominator)
result = {'rad': angle, 'deg': 360 * angle / (2 * np.pi)}
return result
def get_straight_line_length_squared(line):
a = line[1][0] - line[0][0]
b = line[1][1] - line[0][1]
length_squared = a ** 2 + b ** 2
return length_squared
Это дает мне кучу прямых линий (наборов по 2 вектора) разумного размера для работы.