用于在图像上布置标签的建议算法/方法

Question

给定一个图像和一组标签附加到图像上的特定点,我正在寻找一种算法,以一定的约束将标签布局到图像的两侧(每侧标签大致相同,标签大致等距离,将标签连接到各自的点,没有线交叉的线.

现在,通过按Y坐标(它们所指的点)对标签进行排序,通常可以非常天真地找到近似解决方案,如本例所示(仅限概念证明,请忽略实际数据的准确度等)!

现在为了满足没有过境的条件,我想到了一些想法:

• 使用遗传算法找到没有交叉的标签的排序;
• 使用另一种方法(例如动态编程算法)来搜索这样的排序;
• 使用上述算法之一,允许间距和排序的变化,找到最小化交叉数和从均匀间距变化的解决方案;
• 也许有一些标准我可以用来在某些标准内粗略搜索标签的每个可能的排序(如果它们的距离大于X,不要重新排序两个标签);
• 如果所有其他方法都失败了,只需尝试数百万的随机排序/间距偏移,并选择一个给出最小交叉/间距变化的偏移量.(优点:直接进行编程,可能会找到一个足够好的解决方案;虽然不是一个显示停止的轻微劣势:也许不能在应用程序中动态运行它,以允许用户更改图像的布局/大小. )

在我开始其中之一之前,我会欢迎其他人的意见:有其他人遇到过类似问题并有任何信息来报告上述任何方法的成功/失败,或者他们是否有更好的/更简单的解决方案,我没有发生？感谢您的输入!

Answer 1

Lucas Bradsheet的荣誉论文使用多目标进化算法标记地图对此有很好的讨论.

首先,本文为许多标签质量指标创建了可用的指标.

例如,清晰度(站点和标签之间的映射有多明显):clear(s)= r _s + r _s ^{1/r _t}
其中r _s是站点与其标签之间的距离,r _t是a之间的距离.网站和那里最近的其他标签).

它还为标签,网站和边框之间的冲突以及测量标签的密度和对称性提供了有用的指标.然后,Bradsheet使用多目标遗传算法生成可行解的" Pareto前沿 ".它还包括有关他如何改变个体的信息,以及关于提高算法速度的一些注意事项.

其中有很多细节,它应该提供一些好的思考食物.

Answer 2

让我们暂时忘记信息设计.此任务回顾了与PCB布线算法相关的一些记忆.实际上有很多共同的要求,包括:

1. 交叉口优化
2. 尺寸优化
3. 差距优化

因此,可以将初始任务转换为类似于PCB布线的任务.

有很多可用的信息,但我建议查看Tan Yan对PCB布线的算法研究.

它提供了许多细节和几十个提示.

适应当前的任务

我们的想法是将图像上的标记和标签视为两组引脚,并使用逃逸路由来解决任务.通常,PCB区域表示为引脚阵列.可以通过可能的优化对图像进行相同的操作:

1. 避免低对比度区域
2. 避免使用文本框
3. 等等

因此,任务可以简化为"在未使用的引脚的情况下路由"

最终结果可能非常接近所请求的样式:

Tan Yan对PCB布线的算法研究是一个继续进行的好地方.

补充说明

为了突出相似性,我稍微改变了绘画的风格.

进行一些逆向转换不应该是一个大问题,保持良好的外观和可读性.

无论如何,简单的擅长(例如我)可以花几分钟时间创造更好的东西(或者不同的东西):

至于我,曲线看起来不像一个完整的解决方案,至少在这个阶段.无论如何,我刚刚试图证明存在增强空间,因此可以考虑将PCB布线方法作为一种选择.

Answer 3

一种选择是将其转换为整数编程问题.

让我们说你已经n points并n corresponding labels分布在图的外面.

n^2如果我们查看所有可能的交叉点,则可能的行数是少于n^4交叉点(如果显示所有可能的行).

在我们的整数编程问题中,我们添加以下约束:

(判断线路是否已打开(即显示在屏幕上))

1. 对于图中的每个点,只能打开连接到它的可能n条线中的一条.

2. 对于每个标签,只能打开连接到它的可能n条线中的一条.

3. 对于每对交叉线段line1和line2,可以仅接通这些线中的零个或一个.

4. 可选地,我们可以最小化所有接通线路的总距离.这增强了美感.

当所有这些约束同时存在时,我们有一个解决方案:

下面的代码为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

Answer 4

我认为这个问题的实际解决方案是略有不同的层.开始解决完全忽略信息设计的算法问题似乎不太合适.有发现了一个有趣的例子在这里

让我们确定一些重要问题:

1. 如何最好地查看数据？
2. 它会让人迷惑吗？
3. 它可读吗？
4. 它真的有助于更好地理解图片吗？

顺便说一句,混乱真的令人困惑.我们喜欢秩序和可预测性.无需向初始图像引入额外的信息噪声.

图形消息的可读性由内容及其表示决定.消息的可读性涉及读者理解文本和图片样式的能力.由于额外的"嘈杂"方法,你有这个有趣的算法任务.消除混乱 - 找到更好的解决方案:)

请注意,这只是一个PoC.这个想法是只使用带有清晰标记的水平线.标签放置是直截了当且具有确定性.可以提出几个类似的想法.

使用这种方法,您可以轻松平衡左右标签,避免线之间的小垂直间隙,为标签提供最佳垂直密度等.

编辑

好的,让我们看看初始流程的外观.

用户故事:作为用户,我希望对重要图像进行注释,以简化理解并提高其解释价值.

重要假设:

1. 初始图像是用户的主要对象
2. 可读性是必须的

因此,最好的解决方案是注释,但没有注释.(我真的建议花点时间阅读有关创造性解决问题的理论).

基本上,用户看到初始图片应该没有障碍,但是注释应该在需要时就在那里.这可能有点令人困惑,对不起.

您认为交叉口问题是下图后面唯一的问题吗？

请注意,开发方法背后的实际目标是提供两个信息流(图像和注释),并帮助用户尽快理解所有内容.顺便说一下,视力记忆也很重要.

人类视觉的背后是什么:

1. 选择性注意
2. 熟悉度检测
3. 模式检测

你想打破这些机制中的至少一个吗？我希望你不要.因为它会使实际结果不是非常人性化.

那会分散我注意力的是什么？

1. 奇怪的线条随机分布在图像上(随机几何物体非常分散注意力)
2. 不统一的注释位置和风格
3. 由于图像和注释图层的最终合并而产生的奇怪的复杂图案

为什么我的建议应该考虑？

1. 它具有简单的模式,因此模式检测将让用户不再注意注释,而是看到图片
2. 它具有统一的设计,因此熟悉度检测也可以
3. 它不像其他解决方案那样影响初始图像,因为线条具有最小宽度.
4. 线条是水平的,不使用抗锯齿,因此它可以保存更多信息并提供干净的结果
5. 最后,它确实简化了路由算法.

一些额外的评论:

1. 不要使用随机点来测试您的算法,使用简单但重要的情况.您会发现自动化解决方案有时可能会失败.
2. 我不建议使用我提出的方法.有很多可能的增强功能.
3. 我真正建议的是升级一级并在元级别上进行多次迭代.

分组可以用来处理Robert King提到的复杂案例:

或者我可以想象一下,某个点位于它的默认位置上方.但只有一秒钟,因为我不想打破主要的处理流程并影响其他标记.

谢谢你的阅读.

Answer 5

您可以找到图表的中心，然后从中心径向向外的点绘制直线。可能存在交叉的唯一方法是，如果两个点位于同一条射线上，在这种情况下，您只需将其中一条线稍微移动一点，而将另一条线稍微移动一点，就像这样：

仅显示实际零件：

如果有两个或多个与中心共线的点，则可以将线稍微向侧面移动：

尽管这不会产生很好的多段线，但是却非常清楚地标记了图表。另外，为了使其更具吸引力，最好为中心选择一个点，该点实际上是对象的中心，而不只是点集的中心。