MyLiveWire1
In [1]:
%matplotlib notebook
In [2]:
# loading standard modules
import numpy as np
import matplotlib.pyplot as plt
# loading custom module (requires file asg1.py in the same directory as the notebook file)
from asg1 import Figure, LiveWirePresenter
In [3]:
import heapq
class Dijkstra:
def __init__(self, img, useFour = True):
num_rows = self.num_rows = img.shape[0]
num_cols = self.num_cols = img.shape[1]
self.img = img.astype(float)
# print(img.shape)
shape = (num_cols,num_rows)
self.colors = np.empty(shape, dtype=int)
self.predec_xs = np.empty(shape, dtype=int)
self.predec_ys = np.empty(shape, dtype=int)
self.distance = np.empty(shape, dtype=float)
self.paths_computed_ = False
if useFour:
# 4-neighbors graph
self.neighbor_xs = [0, 1, 0, -1]
self.neighbor_ys = [1, 0, -1, 0]
else:
# 8-neighbors graph
self.neighbor_xs = [0, 1, 1, 1, 0, -1, -1, -1]
self.neighbor_ys = [1, 1, 0, -1, -1, -1, 0, 1]
def paths_computed(self):
return self.paths_computed_
def compute_paths_starting_at(self, sx, sy):
self.paths_computed_ = False
num_rows = self.num_rows
num_cols = self.num_cols
predec_xs = self.predec_xs
predec_ys = self.predec_ys
neighbor_xs = self.neighbor_xs
neighbor_ys = self.neighbor_ys
num_neighbors = len(neighbor_xs)
distance = self.distance
distance.fill(float(‘inf’))
distance[sx, sy] = 0
predec_xs[sx,sy] = sx
predec_ys[sx,sy] = sy
queue = [(0, sx, sy)]
computed = set()
while len(queue) != 0:
v, x, y = heapq.heappop(queue)
if (x, y) in computed:
continue
computed.add((x, y))
distance[x, y] = v
for k in xrange(num_neighbors):
nx = x + neighbor_xs[k]
ny = y + neighbor_ys[k]
if 0 <= nx and nx < num_cols and 0 <= ny and ny < num_rows: # print(np.sqrt(np.abs(neighbor_xs[k]) + np.abs(neighbor_ys[k]))) w = np.abs(self.img[y, x] - self.img[ny, nx]) * np.sqrt(np.abs(neighbor_xs[k]) + np.abs(neighbor_ys[k])) if distance[x, y] + w < distance[nx, ny]: distance[nx, ny] = distance[x, y] + w heapq.heappush(queue, (distance[nx, ny], nx, ny)) predec_xs[nx,ny] = x predec_ys[nx,ny] = y # print(distance) self.paths_computed_ = True def get_path_to(self, x, y): xs = [] ys = [] xs.append(x) ys.append(y) predec_xs = self.predec_xs predec_ys = self.predec_ys while predec_xs[x,y] != x or predec_ys[x,y] != y: x,y = predec_xs[x,y],predec_ys[x,y] xs.append(x) ys.append(y) return xs,ys In [4]: class MyLiveWire: def __init__(self, img, useFour = True): self.fig = Figure() self.alg = Dijkstra(img, useFour) self.pres = LiveWirePresenter(img, self.alg) self.pres.connect_figure(self.fig) def run(self): self.fig.show() Notes about the live-wire interface:¶ To deliniate a segment boundary (left) click on some point on this boundary. "on_mouse_down" function in "LiveWirePresenter" (implemented in asg1.py) responds to this event by calling "compute_paths_starting_at" function in "alg" object (in the provided version it is BFS, but you should replace it by a LiveWire object with a properly implemented function of the same name). That functions should compute and store paths from all pixels to the specified seed. Note that LiveWire object should compute "shortest paths" on a properly weighted grid graph. BFS above computes some other paths. As the mouse "glides" over the image after each click, "LiveWirePresenter" receives calls to "on_mouse_over" function that calls "get_path_to" in the "alg". This method should return a sequence of points on a path from the last click to the current mouse position. This path is then visualized as a red "livewire". At each new left click the current "red" path is appended to a fixed (blue) contour and "compute_paths_starting_at" is called to recompute paths to the new seed. A right click closes the contour as follows: it appends the current red path to the fixed blue contour, calls "compute_paths_starting_at" the (right) click, gets the path from the starting point of the blue contour to the (right) click, and appends this path to the blue contour (closing it). No new clicks are processed after the contour is closed. Summary:¶ You only need to replace BFS object by your LiveWire object implementation with properly working "compute_paths_starting_at" and "get_path_to" functions. All the GUI details are handled by the fully implemented "LiveWirePresenter" object. In [5]: img = plt.imread('images/uwocampus.bmp') app = MyLiveWire(img[:400,:400], useFour = True) app.run() In [6]: app = MyLiveWire(img[:400,:400], useFour = False) app.run() Compare the results on 4-connected and 8 connected grids¶ In my observation, The algorithm with 8 connected grids can get more accurate boundaries.