algorithm - programa - Algoritmos/métodos sugeridos para diseñar etiquetas en una imagen
programa para hacer etiquetas de productos (7)
Dada una imagen y un conjunto de etiquetas adjuntas a puntos particulares de la imagen, estoy buscando un algoritmo para diseñar las etiquetas a los lados de la imagen con ciertas restricciones (aproximadamente el mismo número de etiquetas en cada lado, etiquetas más o menos equidistantes). , líneas que conectan las etiquetas con sus respectivos puntos sin cruzar líneas).
Ahora, una solución aproximada se puede encontrar bastante ingenuamente ordenando las etiquetas por la coordenada Y (del punto al que se refieren), como en este ejemplo (¡prueba de concepto solamente, ignore la exactitud o de lo contrario los datos reales!).
Ahora para satisfacer la condición de no cruces, algunas ideas que se me ocurrieron:
- utilice un algoritmo genético para encontrar un orden de etiquetas sin cruces;
- use otro método (p. ej. algoritmo de programación dinámica) para buscar tal orden;
- utilice uno de los algoritmos anteriores, teniendo en cuenta las variaciones en el espaciado y el orden, para encontrar la solución que minimice el número de cruces y la variación del espaciamiento par;
- tal vez haya criterios que pueda usar para la búsqueda bruta a través de cada orden posible de las etiquetas dentro de ciertos criterios (no reordene dos etiquetas si su distancia es mayor que X);
- si todo lo demás falla, simplemente intente millones de asignaciones aleatorias / separaciones de espacio y tome la que da la mínima variación de cruces / espaciamiento. (Ventaja: sencillo de programar y probablemente encuentre una solución lo suficientemente buena, ligera desventaja, aunque no un stop-stopper: tal vez no pueda ejecutarlo sobre la marcha durante la aplicación para permitir al usuario cambiar el diseño / tamaño de la imagen. )
Antes de embarcarme en uno de estos, me gustaría dar la bienvenida a las opiniones de otras personas: ¿alguien más ha experimentado un problema similar y tiene información para informar sobre el éxito / fracaso de cualquiera de los métodos anteriores, o si tienen una mejor / solución más simple que no me está ocurriendo? ¡Gracias por tu contribución!
Agregaría una cosa más a su prototipo, puede ser que sea aceptable después de esto:
Itere a través de cada intersección e intercambie etiquetas, repita hasta que haya intersecciones.
Este proceso es finito, porque el número de estados es finito y cada intercambio reduce la suma de todas las longitudes de línea, por lo que no es posible ningún ciclo.
Creo que una solución real de este problema está en la capa ligeramente diferente. No parece una buena idea comenzar a resolver problemas algorítmicos ignorando por completo el diseño de la información . Hay un ejemplo interesante que se encuentra aquí
Identifiquemos algunas preguntas importantes:
- ¿Cómo se ven mejor los datos?
- ¿Confundirá a la gente?
- ¿Es legible?
- ¿Ayuda realmente a comprender mejor la imagen?
Por cierto, el caos es realmente confuso. Nos gusta el orden y la previsibilidad. No es necesario introducir ruido informativo adicional a la imagen inicial.
La legibilidad de un mensaje gráfico está determinada por el contenido y su presentación. La legibilidad de un mensaje implica la capacidad del lector para comprender el estilo del texto y las imágenes. Tienes esa tarea algorítmica interesante debido al enfoque "ruidoso" adicional. Elimina el caos - encuentra una mejor solución :)
Tenga en cuenta que esto es solo un PoC . La idea es usar solo líneas horizontales con marcadores claros. La colocación de etiquetas es directa y determinista. Se pueden proponer varias ideas similares.
Con este enfoque, puede equilibrar fácilmente las etiquetas izquierda-derecha, evitar pequeños espacios verticales entre líneas, proporcionar una densidad vertical óptima para las etiquetas, etc.
EDITAR
Ok, veamos cómo se verá el proceso inicial.
Historia del usuario: como usuario, quiero anotar imágenes importantes para simplificar la comprensión y aumentar su valor explicativo.
Supuestos importantes:
- la imagen inicial es un objeto primario para el usuario
- la legibilidad es un deber
Entonces, la mejor solución posible es tener anotaciones, pero no las tienes. (Realmente sugeriría pasar algún tiempo leyendo sobre la teoría de la resolución de problemas inventiva ).
Básicamente, no debería haber obstáculos para que el usuario vea la imagen inicial, pero las anotaciones deben estar allí cuando sea necesario. Puede ser un poco confuso, lo siento por eso.
¿Crees que el problema de las intersecciones es el único detrás de la siguiente imagen?
Tenga en cuenta que el objetivo real detrás del enfoque desarrollado es proporcionar dos flujos de información (imagen y anotaciones) y ayudar al usuario a comprender todo lo más rápido posible. Por cierto, la memoria de visión también es muy importante.
¿Qué hay detrás de la visión humana?
- Atención selectiva
- Detección de familiaridad
- Detección de patrones
¿Quieres romper al menos uno de estos mecanismos? Espero que no. Porque hará que el resultado real no sea muy fácil de usar.
Entonces, ¿qué puede distraerme?
- líneas extrañas distribuidas aleatoriamente sobre la imagen (los objetos geométricos aleatorios son muy distractivos)
- colocación de anotaciones no uniforme y estilo
- patrones complejos extraños como resultado de la fusión final de la imagen y la capa de anotación
¿Por qué mi propuesta debe ser considerada?
- Tiene un patrón simple, por lo que la detección de patrones permitirá que el usuario deje de notar las anotaciones, pero vea la imagen en su lugar
- Tiene un diseño uniforme, por lo que la detección de familiaridad también funcionará
- No afecta tanto la imagen inicial como otras soluciones porque las líneas tienen un ancho mínimo.
- Las líneas son horizontales, no se usa anti-aliasing, por lo que ahorra más información y proporciona resultados limpios
- Finalmente, simplifica mucho el algoritmo de enrutamiento.
Algunos comentarios adicionales:
- No use puntos al azar para probar sus algoritmos, use casos simples pero importantes. Verá que las soluciones automatizadas a veces pueden fallar dramáticamente.
- No sugiero usar el enfoque propuesto por mí tal como es. Hay muchas mejoras posibles.
- Lo que realmente sugiero es subir un nivel y hacer varias iteraciones en el meta-nivel.
La agrupación se puede usar para tratar el caso complejo, mencionado por Robert King:
O puedo imaginar por un segundo que algún punto se encuentra ligeramente por encima de su ubicación predeterminada. Pero solo por un segundo, porque no quiero romper el flujo de procesamiento principal y afectar otros marcadores.
Gracias por leer.
Este problema se puede convertir en un diseño de gráfico.
Te recomiendo que mires, por ejemplo, la biblioteca Graphviz . No he hecho ningún experimento, pero creo que al expresar los puntos que deben etiquetarse y las etiquetas en sí mismas como nodos y las líneas iniciales como bordes, obtendrás buenos resultados.
Tendría que expresar áreas donde las etiquetas no deberían ir como nodos "ficticios" que no deben superponerse.
Graphvis tiene enlaces para muchos idiomas .
Incluso si Graphviz no tiene la flexibilidad suficiente para hacer exactamente lo que necesita, la sección "Teoría" de esa página tiene referencias de minimización de energía y algoritmos de primavera que se pueden aplicar a su problema. La literatura sobre el diseño de gráficos es enorme.
La tesis de honor de Lucas Bradsheet, Mapas de etiquetado que utilizan algoritmos evolutivos multiobjetivos, tiene una buena discusión sobre esto.
En primer lugar, este documento crea métricas utilizables para una serie de métricas de calidad de etiquetado.
Por ejemplo, claridad (qué tan obvio era el mapeo entre sitios y etiquetas): claridad (s) = r s + r s 1 / r t
donde r s es la distancia entre un sitio y su etiqueta y r t es la distancia entre un sitio y la otra etiqueta más cercana).
También tiene métricas útiles para los conflictos entre etiquetas, sitios y bordes, así como para medir la densidad y la simetría de las etiquetas. Bradsheet luego utiliza un algoritmo genético objetivo múltiple para generar una " frontera de Pareto " de soluciones factibles. También incluye información sobre cómo mutó a las personas y algunas notas sobre cómo mejorar la velocidad del algoritmo.
Hay muchos detalles en él, y debería proporcionar algo de buena comida para pensar.
Olvidémonos del diseño de la información por un momento. Esta tarea recuerda algunos recuerdos relacionados con los algoritmos de enrutamiento de PCB . En realidad, hay muchos requisitos comunes, que incluyen:
- optimización de intersecciones
- optimización de tamaño
- optimización de brechas
Por lo tanto, podría ser posible convertir la tarea inicial en algo similar al enrutamiento de PCB.
Hay mucha información disponible, pero sugeriría revisar los estudios algorítmicos sobre enrutamiento de PCB por Tan Yan .
Proporciona muchos detalles y docenas de sugerencias.
Adaptación para la tarea actual
La idea es tratar los marcadores en la imagen y las etiquetas como dos juegos de alfileres y usar el enrutamiento de escape para resolver la tarea. Por lo general, el área de PCB se representa como una matriz de pines. Lo mismo se puede hacer con las posibles optimizaciones de la imagen:
- evitar áreas de bajo contraste
- evitar cuadros de texto si los hay
- etc
Por lo tanto, la tarea se puede reducir a "enrutamiento en caso de pines no utilizados"
El resultado final puede ser realmente cercano al estilo solicitado:
Los estudios algorítmicos sobre enrutamiento de PCB por Tan Yan son un buen lugar para continuar.
Notas adicionales
Cambio el estilo del dibujo un poco, para acentuar la similitud.
No debería ser un gran problema hacer una transformación inversa, manteniendo el buen aspecto y la legibilidad.
De todos modos, los adeptos de la simplicidad (como yo, por ejemplo) pueden pasar varios minutos e inventar algo mejor (o algo diferente):
En cuanto a mí, las curvas no parecen una solución completa, al menos en esta etapa. De todos modos, he intentado mostrar que hay espacio para las mejoras, por lo que el enfoque de enrutamiento de PCB se puede considerar como una opción.
Puede encontrar el centro de su diagrama y luego dibujar las líneas desde los puntos radialmente hacia afuera desde el centro. La única forma en que podrías tener un cruce es si dos de los puntos se encuentran en el mismo rayo, en cuyo caso solo desplazas una de las líneas un poco en una dirección, y desplazas la otra hacia la otra dirección, así:
Con solo partes reales que muestran:
En caso de que haya dos o más puntos colineales con el centro, puede desplazar las líneas ligeramente hacia un lado:
Si bien esto no produce muy buenas líneas de líneas múltiples, es muy claro que marca el diagrama. Además, para que sea más atractivo físicamente, puede ser mejor elegir un punto para el centro que es realmente el centro de su objeto, en lugar de solo el centro del conjunto de puntos.
Una opción es convertirlo en un problema de programación entero.
Digamos que tiene n points n corresponding labels distribuidas alrededor del exterior del diagrama.
El número de líneas posibles es n^2 , si miramos todas las intersecciones posibles, hay menos de n^4 intersecciones (si se muestran todas las líneas posibles).
En nuestro problema de programación entera, agregamos las siguientes restricciones:
(para decidir si una línea está encendida (es decir, se muestra en la pantalla))
Para cada punto del diagrama, solo se debe encender una de las posibles n líneas que se conectan a él.
Para cada etiqueta, solo se debe encender una de las posibles n líneas que se conectan a ella.
Para cada par de segmentos de línea que se intersectan línea1 y línea2, solo se puede encender cero o una de estas líneas.
Opcionalmente, podemos minimizar la distancia total de todas las líneas conectadas. Esto mejora la estética.
Cuando todas estas restricciones se mantienen al mismo tiempo, tenemos una solución:
El siguiente código produjo el diagrama de arriba para 24 puntos aleatorios.
Una vez que comience a obtener más de 15 o más puntos, el tiempo de ejecución del programa comenzará a disminuir.
Usé el paquete PULP con su solucionador predeterminado. Utilicé PyGame para la pantalla.
Aquí está el código:
__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