Source code for gridf_new

"""Imago grid fitting module

RANSAC inspired method.
"""

import random
from math import sqrt

from intrsc import intersections_from_angl_dist
import linef
import params
import ransac
import manual_lines as manual
from geometry import l2ad

# TODO comments, refactoring, move methods to appropriate modules

class GridFittingFailedError(Exception):
    pass

class BadGenError(Exception):
    pass

[docs]def plot_line(line, c, size): """Plot a *line* with pyplot.""" points = linef.line_from_angl_dist(line, size) pyplot.plot(*zip(*points), color=c)
[docs]class Diagonal_model: """Ransac model for finding diagonals.""" def __init__(self, data): self.data = [p for p in sum(data, []) if p] self.lines = data self.gen = self.initial_g() def initial_g(self): l1, l2 = random.sample(self.lines, 2) for i in xrange(len(l1)): for j in xrange(len(l2)): if i == j: continue if l1[i] and l2[j]: yield (l1[i], l2[j]) def remove(self, data): self.data = list(set(self.data) - set(data)) def initial(self): try: nxt = self.gen.next() except StopIteration: self.gen = self.initial_g() nxt = self.gen.next() return nxt def get(self, sample): if len(sample) == 2: return ransac.points_to_line(*sample) else: return ransac.least_squares(sample) def score(self, est, dist): cons = [] score = 0 a, b, c = est dst = lambda (x, y): abs(a * x + b * y + c) / sqrt(a*a+b*b) l1 = None l2 = None for p in self.data: d = dst(p) if d <= dist: cons.append(p) if p.l1 == l1 or p.l2 == l2: return float("inf"), [] else: l1, l2 = p.l1, p.l2 else: # TODO delete this or refactor score += min(d, dist) return score, cons
[docs]def intersection((a1, b1, c1), (a2, b2, c2)): """Intersection of two lines, given by coefficients in their equations.""" delim = float(a1 * b2 - b1 * a2) if delim == 0: return None x = (b1 * c2 - c1 * b2) / delim y = (c1 * a2 - a1 * c2) / delim return x, y
[docs]class Point: """Class that represents a point in 2D.""" def __init__(self, (x, y)): self.x = x self.y = y def __getitem__(self, key): if key == 0: return self.x elif key == 1: return self.y def __iter__(self): yield self.x yield self.y def __len__(self): return 2 def to_tuple(self): return (self.x, self.y)
[docs]class Line: """Line with a list of important points that lie on it. This and the Point class in this module serves to implement a model of perspective plain -- a line has a list of intersections with other lines and each intersection has two lines that go through it. """ def __init__(self, (a, b, c)): self.a, self.b, self.c = (a, b, c) self.points = [] @classmethod def from_ad(cls, (a, d), size): p = linef.line_from_angl_dist((a, d), size) return cls(ransac.points_to_line(*p)) def __iter__(self): yield self.a yield self.b yield self.c def __len__(self): return 3 def __getitem__(self, key): if key == 0: return self.a elif key == 1: return self.b elif key == 2: return self.c
[docs]def gen_corners(d1, d2, min_size): """Generate candidates on corner positions from the diagonals.""" for c1 in d1.points: if c1 in d2.points: continue pass try: c2 = [p for p in d2.points if p in c1.l1.points][0] c3 = [p for p in d1.points if p in c2.l2.points][0] c4 = [p for p in d2.points if p in c3.l1.points][0] x_min = min([c1[0], c2[0], c3[0], c4[0]]) x_max = max([c1[0], c2[0], c3[0], c4[0]]) if x_max - x_min < min_size: continue y_min = min([c1[1], c2[1], c3[1], c4[1]]) y_max = max([c1[1], c2[1], c3[1], c4[1]]) if y_max - y_min < min_size: continue except IndexError: continue # there is not a corresponding intersection # TODO create an intersection? try: yield manual.lines(map(lambda p: p.to_tuple(), [c2, c1, c3, c4])) except (TypeError): pass # the square was too small to fit 17 lines inside # TODO define SquareTooSmallError or something
[docs]def dst(p, l): """Distance from a point to a line.""" (x, y), (a, b, c) = p, ransac.points_to_line(*l) return abs(a * x + b * y + c) / sqrt(a*a+b*b)
[docs]def score(lines, points): # TODO find whether the point actualy lies on the line or just in the same # direction score = 0 for p in points: s = min(map(lambda l: dst(p, l), lines)) s = min(s, 2) score += s return score
[docs]def find(lines, size, l1, l2, bounds, hough, show_all, do_something, logger): """Find the best grid given the *lines* and *size* of the image. Last three parameters serves for debugging, *l1*, *l2*, *bounds* and *hough* are here for compatibility with older version of gridf, so they can be easily exchanged, tested and compared. """ new_lines1 = map(lambda l: Line.from_ad(l, size), lines[0]) new_lines2 = map(lambda l: Line.from_ad(l, size), lines[1]) for l1 in new_lines1: for l2 in new_lines2: p = Point(intersection(l1, l2)) p.l1 = l1 p.l2 = l2 l1.points.append(p) l2.points.append(p) points = [l.points for l in new_lines1] def dst_p(x, y): x = x - size[0] / 2 y = y - size[1] / 2 return sqrt(x * x + y * y) for n_tries in xrange(3): logger("finding the diagonals") model = Diagonal_model(points) diag_lines = ransac.ransac_multi(6, points, 2, params.ransac_diagonal_iter, model=model) diag_lines = [l[0] for l in diag_lines] centers = [] cen_lin = [] for i in xrange(len(diag_lines)): line1 = diag_lines[i] for line2 in diag_lines[i+1:]: c = intersection(line1, line2) if c and dst_p(*c) < min(size) / 2: cen_lin.append((line1, line2, c)) centers.append(c) if show_all: import matplotlib.pyplot as pyplot from PIL import Image def plot_line_g((a, b, c), max_x): find_y = lambda x: - (c + a * x) / b pyplot.plot([0, max_x], [find_y(0), find_y(max_x)], color='b') fig = pyplot.figure(figsize=(8, 6)) for l in diag_lines: plot_line_g(l, size[0]) pyplot.scatter(*zip(*sum(points, []))) if len(centers) >= 1: pyplot.scatter([c[0] for c in centers], [c[1] for c in centers], color='r') pyplot.xlim(0, size[0]) pyplot.ylim(0, size[1]) pyplot.gca().invert_yaxis() fig.canvas.draw() size_f = fig.canvas.get_width_height() buff = fig.canvas.tostring_rgb() image_p = Image.fromstring('RGB', size_f, buff, 'raw') do_something(image_p, "finding diagonals") logger("finding the grid") data = sum(points, []) # TODO what if lines are missing? sc = float("inf") grid = None for (line1, line2, c) in cen_lin: diag1 = Line(line1) diag1.points = ransac.filter_near(data, diag1, 2) diag2 = Line(line2) diag2.points = ransac.filter_near(data, diag2, 2) grids = list(gen_corners(diag1, diag2, min(size) / 3)) try: new_sc, new_grid = min(map(lambda g: (score(sum(g, []), data), g), grids)) if new_sc < sc: sc, grid = new_sc, new_grid except ValueError: pass if grid: break else: raise GridFittingFailedError grid_lines = [[l2ad(l, size) for l in grid[0]], [l2ad(l, size) for l in grid[1]]] grid_lines[0].sort(key=lambda l: l[1]) grid_lines[1].sort(key=lambda l: l[1]) if grid_lines[0][0][0] > grid_lines[1][0][0]: grid_lines = grid_lines[1], grid_lines[0] return grid, grid_lines