Предлагаемые алгоритмы/методы для нанесения меток на изображение

Учитывая изображение и набор меток, прикрепленных к определенным точкам на изображении, я ищу алгоритм для выкладки меток по сторонам изображения с определенными ограничениями (примерно одинаковое количество меток на каждой стороне, метки примерно равноудалены, линии, соединяющие метки с соответствующими точками без пересечения линий).

Теперь приблизительное решение обычно можно найти довольно наивно, упорядочив метки по координате Y (точки, на которую они ссылаются), как в этом примере (только доказательство концепции, пожалуйста, игнорируйте точность или иные данные!).

Теперь, чтобы удовлетворить условию отсутствия пересечений, возникли некоторые идеи, которые пришли мне в голову:

используйте генетический алгоритм, чтобы найти упорядочение меток без кроссоверов;
использовать другой метод (например, алгоритм динамического программирования) для поиска такого упорядочения;
используйте один из вышеперечисленных алгоритмов, позволяющий изменять интервалы, а также порядок, находить решение, которое минимизирует количество пересечений и варьирование от четного интервала;
возможно, есть критерии, которые я могу использовать для грубого поиска через все возможные упорядочивания меток в определенных критериях (не переупорядочивайте две метки, если их расстояние больше X);
Если все остальное не удается, попробуйте миллионы случайных упорядочений/смещений и возьмите тот, который дает минимальное изменение пересечений/интервалов. (Преимущество: прямое программирование и, вероятно, найдет достаточно хорошее решение, небольшой недостаток, хотя и не шоу-стоппер: возможно, он не сможет запустить его на лету во время приложения, чтобы пользователь мог изменить макет/размер изображения. )

Прежде чем я приступлю к одному из них, я просто приветствую некоторых других людей: кто-то еще сталкивается с подобной проблемой и имеет любую информацию, сообщающую об успехах/неудачах любого из вышеуказанных методов или если они имеют лучшее/более простое решение, которое не происходит со мной? Спасибо за ваш вклад!

Ответ 1

Lucas Bradsheet почитает тезис Маркировка карт с использованием многоцелевых эволюционных алгоритмов имеет довольно хорошее обсуждение этого.

Во-первых, этот документ создает удобные показатели для ряда показателей качества маркировки.

Например, ясность (насколько очевидно сопоставление между сайтами и метками): ясность = r _s + r _s^{1/r < к югу > тсуб >}
где r _s - расстояние между сайтом и его меткой, а r _t - расстояние между сайтом и ближайшей другой меткой).

Он также имеет полезные показатели для конфликтов между метками, сайтами и границами, а также для измерения плотности и симметрии меток. Затем Bradsheet использует множественный объективный генетический алгоритм для создания " границы Парето" возможных решений". Он также содержит информацию о том, как он мутировал людей, и некоторые замечания об улучшении скорости алгоритма.

В нем много подробностей, и это должно обеспечить хорошую пищу для размышлений.

Ответ 2

Я думаю, что фактическое решение этой проблемы находится на немного другом слое. Кажется, нет правильной идеи начать решение алгоритмической проблемы, полностью игнорируя Информационный дизайн. Существует интересный пример здесь

Определите некоторые важные вопросы:

Как лучше всего просматривать данные?
Будет ли это путать людей?
Является ли это доступным для чтения?
Помогает ли это лучше понять картину?

Кстати, хаос действительно запутан. Нам нравится порядок и предсказуемость. Нет необходимости вводить дополнительный информационный шум в исходное изображение.

Читаемость графического сообщения определяется содержимым и его представлением. Читаемость сообщения позволяет читателям понять стиль текста и изображений. У вас есть интересная алгоритмическая задача из-за дополнительного "шумного" подхода. Удалите хаос - найдите лучшее решение:)

Обратите внимание, что это просто PoC. Идея состоит в том, чтобы использовать только горизонтальные линии с четкими маркерами. Размещение ярлыков является простым и детерминированным. Можно предложить несколько аналогичных идей.

При таком подходе вы можете легко сбалансировать метки слева направо, избегать небольших вертикальных зазоров между линиями, обеспечивать оптимальную вертикальную плотность для меток и т.д.

ИЗМЕНИТЬ

Хорошо, посмотрим, как может выглядеть исходный процесс.

История пользователя: как пользователь я хочу, чтобы важные изображения были аннотированы, чтобы упростить понимание и увеличить его пояснительную ценность.

Важные предположения:

начальное изображение является основным объектом для пользователя.
читаемость является обязательной

Таким образом, наилучшим возможным решением является аннотация, но не его. (Я бы действительно предложил потратить некоторое время на чтение теории решения изобретательских задач).

В принципе, не должно быть никаких препятствий для пользователя, чтобы увидеть исходное изображение, но аннотации должны быть там, где это необходимо. Это может быть немного запутанным, извините за это.

Считаете ли вы, что проблема пересечений является единственной за следующим изображением?

Обратите внимание, что фактическая цель разработанного подхода - предоставить два информационных потока (изображение и аннотации) и помочь пользователю понять все как можно быстрее. Кстати, память видения также очень важна.

Что стоит за человеческим видением:

Выборочное внимание
Обнаружение знакомых
Обнаружение паттерна

Вы хотите сломать хотя бы один из этих механизмов? Надеюсь, вы этого не сделаете. Потому что это сделает фактический результат не очень удобным для пользователя.

Итак, что может отвлечь меня?

странные строки, случайно распределенные по изображению (случайные геометрические объекты очень отвлекают)
неравномерное размещение аннотаций и стиль
странные сложные шаблоны в результате окончательного слияния изображения и слоя аннотации

Почему мое предложение следует рассматривать?

Он имеет простой шаблон, поэтому обнаружение шаблона позволит пользователю перестать замечать аннотации, но вместо этого увидеть изображение
Он имеет единую конструкцию, поэтому обнаружение знакомства также будет работать.
Это не влияет на исходное изображение так же, как и на другие решения, потому что линии имеют минимальную ширину.
Линии горизонтальны, сглаживание не используется, поэтому оно сохраняет больше информации и обеспечивает чистый результат.
Наконец, он значительно упрощает алгоритм маршрутизации.

Некоторые дополнительные комментарии:

Не используйте случайные точки для проверки ваших алгоритмов, используйте простые, но все же важные случаи. Вы увидите, что автоматические решения иногда могут резко потерпеть неудачу.
Я не предлагаю использовать предложенный мной подход как есть. Существует множество возможных улучшений.
Я действительно предлагаю перейти на один уровень вверх и выполнить несколько итераций на мета уровне.

Группировка может использоваться для решения сложного случая, упомянутого Робертом Кингом:

Или я могу себе представить, что какой-то момент немного расположен над его местоположением по умолчанию. Но только на секунду, потому что я не хочу нарушать основной поток обработки и влиять на другие маркеры.

Спасибо, что прочитали.

Ответ 3

Забудьте о информационном дизайне на мгновение. Эти задачи напоминают некоторые воспоминания, связанные с алгоритмами маршрутизации печатных плат. На самом деле существует множество общих требований, в том числе:

Оптимизация переходов
оптимизация размера Оптимизация пробелов

Таким образом, можно было бы превратить первоначальную задачу в нечто похожее на маршрутизацию печатных плат.

Имеется много информации, но я бы предложил просмотреть Алгоритмические исследования маршрутизации печатных плат Tan Yan.

Он предоставляет множество подробностей и множество подсказок.

Адаптация для текущей задачи

Идея состоит в том, чтобы обрабатывать маркеры на изображении и метки как два набора контактов и использовать escape-маршрутизацию для решения задачи. Обычно область печатной платы представлена в виде массива контактов. То же самое можно сделать с изображением с возможной оптимизацией:

избегать областей с низкой контрастностью.
избегать текстовых полей, если есть
и т.д.

Таким образом, задача может быть сведена к "маршрутизации в случае неиспользуемых контактов"

Конечный результат может быть действительно близок к запрошенному стилю:

Алгоритмические исследования маршрутизации печатных плат Tan Yan - это хорошее место для продолжения.

Дополнительные примечания

Я немного изменил стиль рисунка, чтобы подчеркнуть сходство.

Не должно быть большой проблемой делать обратное преобразование, сохраняя хороший внешний вид и удобочитаемость.

В любом случае, адепты простоты (например, я, например) могут потратить несколько минут и придумать что-то лучше (или что-то другое):

Как и для меня, кривые не выглядят как полное решение, по крайней мере, на этом этапе. Во всяком случае, я просто попытался показать, что есть место для усовершенствований, поэтому подход к маршрутизации печатной платы можно рассматривать как вариант.

Ответ 4

Один из вариантов заключается в том, чтобы превратить его в проблему с целым программированием.

Допустим, что у вас есть n points и n corresponding labels, распределенные по внешней стороне диаграммы.

Число возможных строк n^2, если мы посмотрим на все возможные пересечения, пересечений n^4 меньше (если были показаны все возможные строки).

В нашей задаче целочисленного программирования мы добавляем следующие ограничения:

(чтобы решить, включена ли линия (т.е. отображается на экране))

Для каждой точки диаграммы только одна из возможных n строк подключение к нему должно быть включено.
Для каждой метки только одна из возможных n строк, соединяющихся с ней, для включения.
Для каждой пары пересекающихся отрезков линии line1 и line2 только нуль или одна из этих строк может быть включена.
По желанию мы можем минимизировать общее расстояние всех включенных линий. Это усиливает эстетику.

Когда все эти ограничения сохраняются одновременно, у нас есть решение:

В приведенном ниже коде приведена приведенная выше диаграмма для 24 случайных точек.

Как только вы начнете получать более 15 баллов, время запуска программы начнет замедляться.

Я использовал PULP пакет с его решателем по умолчанию. Я использовал PyGame для отображения.

Вот код:

__author__ = 'Robert'

import pygame
pygame.font.init()
import pulp
from random import randint

class Line():
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2
        self.length = (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

    def intersect(self, line2):
        #Copied some equations for wikipedia. Not sure if this is the best way to check intersection.
        x1, y1 = self.p1
        x2, y2 = self.p2
        x3, y3 = line2.p1
        x4, y4 = line2.p2
        xtop = (x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4)
        xbottom = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
        ytop = (x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4)
        ybottom = xbottom
        if xbottom == 0:
            #lines are parallel. Can only intersect if they are the same line. I'm not checking that however,
            #which means there could be a rare bug that occurs if more than 3 points line up.
            if self.p1 in (line2.p1, line2.p2) or self.p2 in (line2.p1, line2.p2):
                return True
            return False
        x = float(xtop) / xbottom
        y = float(ytop) / ybottom
        if min(x1, x2) <= x <= max(x1, x2) and min(x3, x4) <= x <= max(x3, x4):
            if min(y1, y2) <= y <= max(y1, y2) and min(y3, y4) <= y <= max(y3, y4):
                return True
        return False

def solver(lines):
    #returns best line matching
    lines = list(lines)
    prob = pulp.LpProblem("diagram labelling finder", pulp.LpMinimize)

    label_points = {} #a point at each label
    points = {} #points on the image
    line_variables = {}
    variable_to_line = {}

    for line in lines:
        point, label_point = line.p1, line.p2
        if label_point not in label_points:
            label_points[label_point] = []
        if point not in points:
            points[point] = []
        line_on = pulp.LpVariable("point{0}-point{1}".format(point, label_point),
            lowBound=0, upBound=1, cat=pulp.LpInteger) #variable controls if line used or not
        label_points[label_point].append(line_on)
        points[point].append(line_on)
        line_variables[line] = line_on
        variable_to_line[line_on] = line

    for lines_to_point in points.itervalues():
        prob += sum(lines_to_point) == 1 #1 label to each point..

    for lines_to_label in label_points.itervalues():
        prob += sum(lines_to_label) == 1 #1 point for each label.

    for line1 in lines:
        for line2 in lines:
            if line1 > line2 and line1.intersect(line2):
                line1_on = line_variables[line1]
                line2_on = line_variables[line2]
                prob += line1_on + line2_on  <= 1 #only switch one on.

    #minimize length of switched on lines:
    prob += sum(i.length * line_variables[i] for i in lines)

    prob.solve()
    print prob.solutionTime
    print pulp.LpStatus[prob.status] #should say "Optimal"
    print len(prob.variables())

    for line_on, line in variable_to_line.iteritems():
        if line_on.varValue > 0:
            yield line #yield the lines that are switched on

class Diagram():
    def __init__(self, num_points=20, width=700, height=800, offset=150):
        assert(num_points % 2 == 0) #if even then labels align nicer (-:
        self.background_colour = (255,255,255)
        self.width, self.height = width, height
        self.screen = pygame.display.set_mode((width, height))
        pygame.display.set_caption('Diagram Labeling')
        self.screen.fill(self.background_colour)
        self.offset = offset
        self.points = list(self.get_points(num_points))
        self.num_points = num_points
        self.font_size = min((self.height - 2 * self.offset)//num_points, self.offset//4)

    def get_points(self, n):
        for i in range(n):
            x = randint(self.offset, self.width - self.offset)
            y = randint(self.offset, self.height - self.offset)
            yield (x, y)

    def display_outline(self):
        w, h = self.width, self.height
        o = self.offset
        outline1 = [(o, o), (w - o, o), (w - o, h - o), (o, h - o)]
        pygame.draw.lines(self.screen, (0, 100, 100), True, outline1, 1)
        o = self.offset - self.offset//4
        outline2 = [(o, o), (w - o, o), (w - o, h - o), (o, h - o)]
        pygame.draw.lines(self.screen, (0, 200, 0), True, outline2, 1)

    def display_points(self, color=(100, 100, 0), radius=3):
        for point in self.points:
            pygame.draw.circle(self.screen, color, point, radius, 2)

    def get_label_heights(self):
        for i in range((self.num_points + 1)//2):
            yield self.offset + 2 * i * self.font_size

    def get_label_endpoints(self):
        for y in self.get_label_heights():
            yield (self.offset, y)
            yield (self.width - self.offset, y)

    def get_all_lines(self):
        for point in self.points:
            for end_point in self.get_label_endpoints():
                yield Line(point, end_point)


    def display_label_lines(self, lines):
        for line in lines:
            pygame.draw.line(self.screen, (255, 0, 0), line.p1, line.p2, 1)

    def display_labels(self):
        myfont = pygame.font.SysFont("Comic Sans MS", self.font_size)
        label = myfont.render("label", True, (155, 155, 155))
        for y in self.get_label_heights():
            self.screen.blit(label, (self.offset//4 - 10, y - self.font_size//2))
            pygame.draw.line(self.screen, (255, 0, 0), (self.offset -  self.offset//4, y), (self.offset, y), 1)
        for y in self.get_label_heights():
            self.screen.blit(label, (self.width - 2*self.offset//3, y - self.font_size//2))
            pygame.draw.line(self.screen, (255, 0, 0), (self.width - self.offset + self.offset//4, y), (self.width - self.offset, y), 1)

    def display(self):
        self.display_points()
        self.display_outline()
        self.display_labels()
        #self.display_label_lines(self.get_all_lines())
        self.display_label_lines(solver(self.get_all_lines()))

diagram = Diagram()
diagram.display()

pygame.display.flip()
running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

Ответ 5

Вы можете найти центр вашей диаграммы, а затем нарисовать линии из точек радиально наружу от центра. Единственный способ, которым вы могли бы пересечься, - это то, что две точки лежат на одном луче, и в этом случае вы просто переставляете одну из строк немного в одну сторону, а другую - наоборот:

Если отображаются только фактические части:

Если в центре есть две или более точки с коллинером, вы можете слегка сдвинуть строки в сторону:

В то время как это не создает очень хорошие многосегментные линии, он очень четко намечает диаграмму. Кроме того, чтобы сделать его более привлекательным, лучше выбрать точку для центра, которая на самом деле является центром вашего объекта, а не только центром набора точек.

Ответ 6

Я бы добавил еще одну вещь к вашему прототипу - возможно, это будет приемлемо после этого:

Итерации через все метки пересечения и замены, повторяйте до тех пор, пока не будут пересечения.

Этот процесс является конечным, так как число состояний является конечным, и каждый своп уменьшает сумму всех длин линий, поэтому цикл невозможен.

Ответ 7

Эта проблема может быть выбрана как макет графика.

Я рекомендую вам посмотреть, например. библиотека Graphviz. Я не делал никаких экспериментов, но считаю, что, выражая точки, которые должны быть помечены, и метки сами по себе как узлы и ведущие линии как ребра, вы получите хорошие результаты.

Вам нужно будет выражать области, где метки не должны быть "dummy" узлами, которые не должны перекрываться.

Graphvis имеет привязки для многих языков.

Даже если Graphviz не обладает достаточной гибкостью для выполнения именно того, что вам нужно, в разделе "Теория" этой страницы есть ссылки для минимизации энергии и алгоритмы spring, которые могут быть применены к вашей проблеме. Литература по расположению графа огромна.