Структура данных, которая всегда сохраняет n-best элементы
Вот код. Он использует грубые линии для обнаружения линий, а не просто обрезает области изображения, заданные линиями
img = cv2.imread('PECross.png')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
lines_coords = []
edges = cv2.Canny(gray, 50,150,3)
lines = cv2.HoughLines(edges,1,np.pi/180,200)
for rho,theta in lines.squeeze():
a = np.cos(theta)
b = np.sin(theta)
x0 = a*rho
y0 = b*rho
x1 = int(x0 + 1000*(-b))
y1 = int(y0 + 1000*(a))
x2 = int(x0 - 1000*(-b))
y2 = int(y0 - 1000*(a))
lines_coords.append((x1,y1,x2,y2))
vertical_left = lines_coords[0]
vertical_right = lines_coords[1]
horizontal_up = lines_coords[2]
horizontal_down = lines_coords[3]
x1,y1,x2,y2=vertical_left
left_arm = img[:, :x1]
x1,y1,x2,y2=vertical_right
right_arm = img[:, x1:]
x1,y1,x2,y2=horizontal_up
upper_arm = img[:y1, :]
x1,y1,x2,y2=horizontal_down
lower_arm = img[y1:, :]
cv2.imwrite('left_arm.png', left_arm)
cv2.imwrite('right_arm.png', right_arm)
cv2.imwrite('upper_arm.png', upper_arm)
cv2.imwrite('lower_arm.png', lower_arm)
5 ответов
Определенный datastructure, который Вы хотите, является, вероятно, неявной "кучей". Сырые данные datastructure являются просто массивом; для удобства скажите, что это - элементы N=2^n в размере, и что Вы хотите поддержать самые большие N-1 элементы.
Идея состоит в том, чтобы рассматривать массив (назовите это A) как полное двоичное дерево глубины n:
- проигнорируйте [0]; рассматривайте [1] как корневой узел
- для каждого узла [k], дети [2*k] и [2*k+1]
- узлы [N/2.. N-1] являются листами
Для поддержания дерева как "кучи" необходимо удостовериться, что каждый узел меньше, чем (или равен), его дети. Это называют "условием "кучи"":
- [k] <= [2*k]
- [k] <= [2*k+1]
Использовать "кучу" для поддержания самых больших элементов N:
- обратите внимание, что корень [1] является самым маленьким элементом в "куче".
- сравните каждый новый элемент (x) с корнем: если это меньше (x <[1]), отклоните его.
- иначе вставьте новый элемент в "кучу", следующим образом:
- удалите корень ([1], самый маленький элемент) от "кучи", и отклоните его
- замените его новым элементом ([1]: = x)
- теперь, восстановите условие "кучи":
- если x меньше чем или равен обоим из своих детей, Вы сделаны
- иначе подкачайте x с самым маленьким ребенком
- повторите test&swap в каждом новом положении, пока условие "кучи" не будут соблюдать
В основном это заставит любой заменяющий элемент "фильтровать" дерево, пока это не достигнет своего естественного места. Это сделает в большей части n=log2 (N) шаги, который так хорош, как можно добраться. Кроме того, неявная форма дерева позволяет очень внедрение FAST; существующие bounded-priority-queue библиотеки будут, скорее всего, использовать неявную "кучу".
В Java можно использовать реализованный SortedSet, например, TreeSet. После каждой проверки вставки, если набор является слишком большим, если да удаляют последний элемент.
Это довольно эффективно, я использовал его успешно для решения нескольких Euler проблем Проекта.
priority_queue является самой близкой вещью в C++ с STL. Вы могли перенести его в другой класс для создания собственной реализации, которая обрезает размер автоматически.
Язык агностически (хотя, возможно, не фрагментация памяти безопасно):
- Вставьте данные
- Вид
- Удалите все после энного элемента
станд.:: priority_queue делает шаг 2 для Вас.
Ограниченная приоритетная очередь, я думаю... Java имеет что-то вроде этого в своей стандартной библиотеке.Править: это называют LinkedBlockingQueue. Я не уверен, включает ли STL C++ что-то подобное.
Разве не возможно просто брать первые n элементы от отсортированного набора?