[Insight-developers] FloodFill Iterator : Stack vs Queue

[Luis Ibanez]

This is a multi-part message in MIME format.
--------------060305070502080005030601
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit


Hi,

As we discussed in one of the recent Tcons, the FloodFill
iterator is using the STL stack container for holding the
pixels to be visited.

However,  the queue is more appropriate for this task


Andy Cedilnik just made a very convincing test of the
advantge of using the Queue instead of the Stack.

His test is a python script that implements both
approaches for flood fill and display their evolution.

The test prints out both the computing time and the
maximum depth of the container (queue or stack).


Andy's  script is attached.

I'll give it a shot at replacing the std::stack container with
the std::queue container in the itkFloodFill iterator.


    Luis


BTW
Andy is joking about rewriting ITK in Python,
at least I think it was a joke...    :-)

--------------060305070502080005030601
Content-Type: text/plain;
 name="flood.py"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="flood.py"

#!/usr/bin/env python

import sys
import time

width = 300
height = 200
factor = 2
do_stack = 0
radius = min(width, height)/6
gui = 1

radius_sq = radius * radius
if len(sys.argv) > 1:
  do_stack = 1

if gui:
  import Tkinter
  root = Tkinter.Tk()
  cv = Tkinter.Canvas(root)
  cv["width"] = width*factor
  cv["height"] = height*factor
  cv.pack(fill=Tkinter.BOTH, expand=1)

point = (width/2, height/2)
screen = []
for x in range(width):
  line = []
  px = x - width/2
  for y in range(height):
    py = y - height/2
    if px*px + py*py > radius_sq:
      line.append( 1 )
    else:
      line.append( 0 )
  screen.append(line)

class Queue:
  def __init__(self):
    self.Data = []
    self.Maxlen = 0
  def Put(self, point):
    self.Data.append(point)
    self.Maxlen = max(self.Maxlen, len(self.Data))
  def Get(self):
    if len(self.Data) == 0:
      return 0
    pt = self.Data[0]
    self.Data = self.Data[1:]
    return pt

class Stack:
  def __init__(self):
    self.Data = []
    self.Maxlen = 0
  def Put(self, point):
    self.Data.append(point)
    self.Maxlen = max(self.Maxlen, len(self.Data))
  def Get(self):
    if len(self.Data) == 0:
      return 0
    pt = self.Data[len(self.Data)-1]
    self.Data = self.Data[:len(self.Data)-1]
    return pt


def Check(x, y):
  if (x < 0 or y < 0 or 
      x >= width or 
      y >= height ):
    return 1
  if screen[x][y]:
    return 1
  return 0

def PutCheck(pt, ds):
  if Check(pt[0], pt[1]):
    return
  ds.Put(pt)
  


def process_one_step():
  pt = ds.Get()
  if not pt:
    End()
    return 0
  # check if pixel set
  pixel_set = Check(pt[0], pt[1])

  if not pixel_set:
    #print "Create pixel at:", pt
    if gui:
      cv.create_oval((pt[0]*factor, pt[1]*factor, (pt[0]+1)*factor, (pt[1]+1)*factor))
      root.update()
    screen[pt[0]][pt[1]] = 1
   
    PutCheck((pt[0]-1, pt[1]-1), ds)
    PutCheck((pt[0]  , pt[1]-1), ds)
    PutCheck((pt[0]+1, pt[1]-1), ds)
    PutCheck((pt[0]-1, pt[1]), ds)
    PutCheck((pt[0]+1, pt[1]), ds)
    PutCheck((pt[0]-1, pt[1]+1), ds)
    PutCheck((pt[0]  , pt[1]+1), ds)
    PutCheck((pt[0]+1, pt[1]+1), ds)
  return 1

def End():
  end_timer = time.time()
  print "Maximum size of data structure: %d" % ds.Maxlen
  print "                  Elapsed time: %.3f" % (end_timer-start_timer)

start_timer = time.time()
if do_stack:
  print "Process stack"
  ds = Stack()
else:
  print "Process queue"
  ds = Queue()
ds.Put(point)

while process_one_step():
  pass

if gui:
  root.mainloop()

--------------060305070502080005030601--