Framework de Base

  1 from numpy import array, ravel
  2 
  3 # constants
  4 # neighbourhood 2D
  5 N4 = array([[-1,0],[0,1],[1,0],[0,-1]])
  6 N8 = array([[-1,0],[0,1],[1,0],[0,-1],[-1,-1],[-1,1],[1,1],[1,-1]])
  7 
  8 # neighbourhood 3D
  9 N6 = array([[-1,0,0],[0,1,0],[1,0,0],[0,-1,0],[0,0,1],[0,0,-1]])
 10 
 11 
 12 # values
 13 inf = 1e400
 14 BORDER = inf
 15 
 16 def isBorder(v):
 17     """ Tests if the value is a border value """
 18     return v == BORDER
 19 
 20 # common classes for the algorithms
 21 class wsImage():
 22     """ Class for storing the images """
 23 
 24     def __init__(self, array):
 25         """ Constructor for storing the N-D input image """
 26         self.input = array
 27         self.work = None
 28         self.label = None
 29         self.output = None
 30 
 31     def begin(self, offsets):
 32         """ Prepare the image for processing """
 33         from numpy import zeros, ravel
 34 
 35         if len(self.input.shape) != offsets.shape[1]:
 36             raise Exception("Image shape does not fit offsets dimensions")
 37 
 38         # initialise the neighbour
 39         self.neighbour = wsNeighbour(offsets)
 40         # pad the input image
 41         self.work = self._pad()
 42         # store the padded shape
 43         self.workshape = self.work.shape
 44         # ravel the padded image (make 1-D)
 45         self.work = ravel(self.work)
 46         # make a zeroed copy of it
 47         self.label = zeros(self.work.shape)
 48         # initialise the output
 49         self.output = None
 50         # initialise the shape of the image
 51         self.neighbour.setImageShape(self.workshape)
 52         self.neighbour.setImage(self.work)
 53         # initialise the domain object
 54         D = wsDomain(self.work.size)
 55         D.setImage(self.work)
 56 
 57         # returns the neighbourhood relation, the working image, the label
 58         # image and the domain of the image
 59         return self.neighbour.N, self.work, self.label, D
 60 
 61 
 62     def _pad(self):
 63         from numpy import zeros
 64         """ Pads the N-D image with the BORDER constant as necessary for
 65         containing all the offsets from the list
 66         """
 67         # generate the newshape by iterating through the original and
 68         # adding the extra space needed at each dimension
 69         newshape = tuple(map(lambda orig, d: orig + (d-1), self.input.shape, self.neighbour.shape))
 70         # generate the slicing list
 71         slicing = map(lambda orig, d: slice((d-1)/2, (d-1)/2 + orig), self.input.shape, self.neighbour.shape)
 72         # create the padded image
 73         workimage = zeros(newshape)
 74         workimage[:] = BORDER
 75         workimage[slicing] = self.input
 76         return workimage
 77 
 78     def _crop(self):
 79         return self.crop(self.label)
 80 
 81     def crop(self, x):
 82         """ Reshape and crops the N-D label image to the original size (same as self.input) """
 83         from numpy import reshape
 84         # generate the slicing list
 85         slicing = map(lambda orig, d: slice((d-1)/2, (d-1)/2 + orig), self.input.shape, self.neighbour.shape)
 86         # reshape the label image to the original shape
 87         temp = reshape(x, self.workshape)
 88         # crop the temp image
 89         return temp[slicing]
 90 
 91     def end(self):
 92         return self._crop().astype('int32')
 93 
 94     def makeWorkCopy(self, default=0):
 95         """ Make a copy of the work image filled with the value and type of parameter default """
 96         copied = self.work.copy()
 97         copied = copied.astype(type(default))
 98         copied.fill(default)
 99         return copied
100 
101     def getCoordinate(self, p):
102         """ Get the coordinates in (x,y) form for index p"""
103         return (p / self.workshape[1], p % self.workshape[1])
104 
105 
106 class wsNeighbour():
107     """ Class for neighbourhood processing """
108 
109     def __init__(self, offsets):
110         """ Constructor for the list of offsets in N-D (neighbours)
111             offsets must be a m x N matrix, where m is the number of
112             offsets (neighbours) and N is the dimensions of the image"""
113         self.offsets = array(offsets)
114         self._shape()
115         self.s = None
116 
117     def _shape(self):
118         """ Calculates the shape of the offsets """
119         N = self.offsets.shape[1]
120         self.shape = []
121         for i in range(N):
122             dmax = max(self.offsets[:,i])
123             dmin = min(self.offsets[:,i])
124             if abs(dmax) != abs(dmin):
125                 raise Exception("Offsets must be symmetrical")
126             d = dmax - dmin + 1
127             # make the dimension always odd
128             if d % 2 == 0:
129                 d += 1
130             self.shape.append(d)
131         self.shape = tuple(self.shape)
132 
133     def setImageShape(self, imshape):
134         """ Set the image shape and calculates the offsets in 1-D """
135         self.s = imshape
136         if len(self.s) != self.offsets.shape[1]:
137             raise Exception("Image shape does not fit offsets dimensions")
138 
139         # calculate the offsets in 1-D
140         # the process occurs like this:
141         # each offset is multiplied by the multiplication of the values of
142         # the next components of the shape of the image and summed:
143         # example:
144         # shape: (3, 10, 15)
145         # offset: [1, 1, 2]
146         # offset in 1-D: (1 * 10 * 15) + (1 * 15) + (2)
147         #
148         # of course, the offsets must follow the order of the shape
149         # (Nth-D, ..., 3rd-D, 2nd-D, 1st-D), that is usually
150         # (time, channel, row, column) or in grayscale images (time, row, column)
151         # or simple 2-D images (row, column)
152 
153         # LONG VERSION
154         # self.roffsets = []
155         # for offset in self.offsets:
156             # roffset = 0
157             # for i in range(len(offset)):
158                 # n = offset[i]
159                 # roffset += n * reduce(lambda x,y: x*y, self.s[(i+1):], 1)
160             # self.roffsets.append(roffset)
161 
162         # SHORT VERSION (using map and reduce - I like this one better)
163         self.roffsets = map(
164             lambda offset: sum(
165                 map(lambda n, i:
166                         n * reduce(lambda x,y: x*y, self.s[(i+1):], 1),
167                     offset, range(len(offset))
168                     )
169                 ),
170             self.offsets)
171 
172     def setImage(self, im):
173         """ Set the working image to query for border values on neighbourhood calculation """
174         self.im = im
175 
176     def N(self, pixel):
177         """ Returns the list of indexes of neighbours of pixel in 1-D """
178         if not self.s:
179             raise Exception("Set the image shape first!")
180 
181         # calculate the coordinates of the neighbours based on the offsets in 1-D
182         n = map(lambda c: c + pixel, self.roffsets)
183         r = list()
184 
185         for i in n:
186             if isBorder(self.im[i]):
187                 continue
188 
189             r.append(i)
190 
191         return r
192 
193     def query(self, c):
194         """ Lookup on the roffsets for the index of the offset c """
195         for i in range(len(self.roffsets)):
196             if self.roffsets[i] == c:
197                 return i
198         return -1
199 
200     def addOffset(self, p, index):
201         """ Adds the offset of the desired index to the value p """
202         if index < 0 or index >= len(self.roffsets):
203             return None
204         else:
205             c = self.roffsets[index]
206             return p + c
207 
208 class wsDomain:
209     def __init__(self, length):
210         self.inner = xrange(length)
211         self.count = 0
212 
213     def next(self):
214         if self.count >= len(self.inner):
215             self.count = 0
216             raise StopIteration
217 
218         while isBorder(self.im[self.inner[self.count]]):
219             self.count += 1
220             if self.count >= len(self.inner):
221                 self.count = 0
222                 raise StopIteration
223 
224         c = self.count
225         self.count = c + 1
226         return self.inner[c]
227 
228     def __getitem__(self, item):
229         return self.inner[item]
230 
231     def __iter__(self):
232         return self
233 
234     def __len__(self):
235         return len(self.inner)
236 
237     def setImage(self, im):
238         self.im = im
239 
240 class wsQueue():
241     """ Simple queue class for abstracting list methods """
242 
243     def __init__(self):
244         self.array = list()
245 
246     def push(self, a):
247         """ Pushes an element to the end of the queue """
248         self.array.append(a)
249 
250     def pop(self):
251         """ Pops the first element of the queue """
252         return self.array.pop(0)
253 
254     def empty(self):
255         """ Returns whether the queue is empty or not """
256         return len(self.array) == 0
257 
258     def clear(self):
259         """ Clear the list """
260         self.array = list()
261 
262 class wsStack():
263     """ Simple stack class for abstracting list methods """
264 
265     def __init__(self):
266         self.array = list()
267 
268     def push(self, a):
269         """ Pushes an element to the top of the stack """
270         self.array.append(a)
271 
272     def pop(self):
273         """ Pops the top element of the stack """
274         return self.array.pop()
275 
276     def empty(self):
277         """ Returns whether the stack is empty or not """
278         return len(self.array) == 0
279 
280     def clear(self):
281         """ Clear the list """
282         self.array = list()
283 
284 class wsHeapQueue():
285     """ Priority queue class for abstracting list methods with FIFO policy """
286 
287     def __init__(self):
288         self.queue = dict()
289 
290     def push(self, a, c):
291         """ Pushes an element to the queue """
292         if self.queue.has_key(c):
293             self.queue[c].append(a)
294         else:
295             self.queue[c] = [a]
296 
297     def pop(self):
298         """ Pops the first element of the queue """
299         key = min(self.queue.keys())
300         element = self.queue[key].pop(0)
301         if len(self.queue[key]) == 0:
302             self.queue.pop(key)
303         return element
304 
305     def empty(self):
306         """ Returns whether the queue is empty or not """
307         return len(self.queue) == 0
308 
309     def clear(self):
310         """ Clear the queue """
311         self.queue = dict()
312 
313     def remove(self, a, c):
314         """ Remove the element a at cost c """
315         self.queue[c].remove(a)
316 
317     def contains(self, a, c):
318         """ Verifies if the queue contains element a at cost c """
319         for x in self.queue[c]:
320             if x == a:
321                 return True
322         return False
323 
324 class wsRandHeapQueue():
325     """ Priority queue class for abstracting list methods without FIFO policy """
326 
327     class wsPixel():
328 
329         def __init__(self, p, l):
330             self.p = p
331             self.l = l
332 
333         def __lt__(self, other):
334             return self.l < other.l
335 
336         def __le__(self, other):
337             return self.l <= other.l
338 
339         def __eq__(self, other):
340             return self.l == other.l and self.p == other.p
341 
342         def __ne__(self, other):
343             return not (self.l == other.l and self.p == other.p)
344 
345         def __gt__(self, other):
346             return self.l > other.l
347 
348         def __ge__(self, other):
349             return self.l >= other.l
350 
351     def __init__(self):
352         self.queue = []
353 
354     def push(self, a, c):
355         from heapq import heappush
356         """ Pushes an element to the queue """
357         px = wsRandHeapQueue.wsPixel(a, c)
358         heappush(self.queue, px)
359 
360     def pop(self):
361         from heapq import heappop
362         """ Pops the first element of the queue """
363         px = heappop(self.queue)
364         return px.p
365 
366     def empty(self):
367         """ Returns whether the queue is empty or not """
368         return len(self.queue) == 0
369 
370     def clear(self):
371         """ Clear the queue """
372         self.queue = []
373 
374     def remove(self, a, c):
375         from heapq import heapify
376         """ Remove the element a at cost c """
377         self.queue.remove(wsRandHeapQueue.wsPixel(a,c))
378         heapify(self.queue)
379 
380     def contains(self, a, c):
381         """ Verifies if the queue contains element a at cost c """
382         for px in self.queue:
383             if px.p == a and px.l == c:
384                 return True
385         return False
386 
387 
388 def findMinima(im, N, D):
389 
390     UNVISITED = 0
391     PENDING = 1
392     VISITED = 2
393 
394     work = im.copy()
395     work[:] = UNVISITED
396 
397     qPending = wsQueue()
398     qMinima = wsQueue()
399 
400     minima = list()
401 
402     count = 1
403 
404     for p in D:
405         if work[p] != UNVISITED:
406             continue
407 
408         qPending.push(p)
409         work[p] = PENDING
410 
411         is_minima = True
412         qMinima.clear()
413 
414         while not qPending.empty():
415 
416             q = qPending.pop()
417             qMinima.push(q)
418             work[q] = VISITED
419 
420             for u in N(q):
421 
422                 if im[u] == im[q] and work[u] == UNVISITED:
423                     work[u] = PENDING
424                     qPending.push(u)
425                 elif im[u] < im[q]:
426                     is_minima = False # keep flooding the plateau
427 
428 
429 
430         if is_minima:
431             count += 1
432             seed = list()
433             while not qMinima.empty():
434                 q = qMinima.pop()
435                 seed.append(q)
436             minima.append(seed)
437 
438     return minima
439 
440 def lowerComplete(im, offsets):
441 
442     # initialise variables
443     ws = wsImage(im)
444     N, im, lc, D = ws.begin(offsets)
445 
446     FICTITIOUS_PIXEL = -1
447     queue = wsQueue()
448 
449     lc[:] = BORDER
450 
451     for p in D:
452 
453         lc[p] = 0
454         for q in N(p):
455             if im[q] < im[p]:
456                 queue.push(p)
457                 lc[p] = -1
458                 break
459 
460     cur_dist = 1
461 
462     queue.push(FICTITIOUS_PIXEL)
463 
464     while not queue.empty():
465         p = queue.pop()
466         if p == FICTITIOUS_PIXEL:
467             if not queue.empty():
468                 queue.push(FICTITIOUS_PIXEL)
469                 cur_dist += 1
470         else:
471             lc[p] = cur_dist
472             for q in N(p):
473 
474                 if im[q] == im[p] and lc[q] == 0:
475                     queue.push(q)
476                     lc[q] = -1
477 
478     for p in D:
479 
480         if lc[p] == 0:
481             lc[p] = cur_dist * im[p]
482         else:
483             lc[p] = cur_dist * im[p] + lc[p] - 1
484 
485     return ws.end()
 1 def relabel(im, se):
 2     from morph import mmlabelflat, mmsecross
 3     from numpy import nonzero
 4 
 5     wslbl = mmlabelflat(im, se)
 6     wslbl[nonzero(im == 0)] = 0 # recoloca o label 0
 7 
 8     return wslbl
 9 
10 def run(function):
11     from morph import mmreadgray, mmgradm, mmareaclose, mmhmin, mmgshow, mmlabelflat, mmsecross, mmglblshow
12     from numpy import nonzero
13 
14     im = mmreadgray('MVBook/jangada.png')
15     im = im[99:-50,:]
16     im = mmareaclose(mmgradm(im), 10)
17     im = mmhmin(im, 8)
18     im = mmgshow(im)[0]
19 
20     ws = function(im, N4)
21     a = mmgshow(im)
22     wslbl = relabel(ws, mmsecross())
23     b = mmglblshow(wslbl)
24 
25     return a, b
 1 L = {0: 'W', 1: 'A', 2: 'B', 3: 'C', 4: 'D'}
 2 
 3 def expand(im, mapping, mins):
 4     from numpy import zeros, ones, nonzero
 5     from morph import mmtext, mmdil, mmneg, mmfreedom, mmseshow, mmimg2se
 6     from ia636_numpy import iaresize
 7 
 8     mmfreedom(2)
 9 
10     CELL_HEIGHT = 40
11     CELL_WIDTH = 40
12 
13     s = im.shape
14 
15     out = zeros((CELL_HEIGHT * s[0], CELL_WIDTH * s[1]))
16 
17     out[:, ::CELL_WIDTH] = 1
18     out[:, -1] = 1
19 
20     out[::CELL_HEIGHT, :] = 1
21     out[-1, :] = 1
22 
23     S = im.astype('int32').ravel()
24     done = dict()
25 
26     for n in S:
27         if done.has_key(n):
28             continue
29         else:
30             done[n] = True
31 
32         if mapping.has_key(n):
33             se = mmtext(mapping[n])
34         else:
35             se = mmtext(str(n))
36         se = mmseshow(se).astype('uint8')
37 
38         newshape = [CELL_HEIGHT - 15, 0]
39         newshape[1] = (newshape[0]/se.shape[0]) * se.shape[1]
40 
41         se = iaresize(se, newshape)
42         se = mmimg2se(se)
43 
44         board = zeros(out.shape)
45         c = nonzero(im == n)
46         crow = c[0] * CELL_HEIGHT + (CELL_HEIGHT / 2)
47         ccol = c[1] * CELL_WIDTH + (CELL_WIDTH / 2)
48         board[(crow, ccol)] = 1
49         board = mmdil(board, se)
50         out += board
51 
52     temp = ones(out.shape) * 255
53     for m in mins:
54         temp[m[0]*CELL_HEIGHT:(m[0]+1)*CELL_HEIGHT, m[1]*CELL_WIDTH:(m[1]+1)*CELL_WIDTH] = 180
55 
56     temp[nonzero(out)] = 0
57 
58     return temp
1 from common import *
2 
3 im = array([[0,1,2],[3,4,5],[6,7,8],[9,10,11],[97,98,99]])
4 out = expand(im, {0: 'W', 1: 'A', 98: 'C'}, [(0,0), (3,2)])
5 mmshow(out)