tillaart36 2 Light Poster

Hello all,

I've written a piece of code that lets me generate or read a grid where all cells have a value. The grid stands for a simple 2d visualisation of an area where types of housing are to be build. The values of a cell stand for some different housing types. By a floodfill algorithm the program detects 'clusters' of cells with the same value. A cluster of cells hereby stands for 1 building with the type according to the cell value of this cluster.

This is the code so far:

# Create a Python spatial grid.

from math import sqrt
import csv

class Grid(object):
    markcnt = 0
    """Grid class with a width, height, length"""
    def __init__(self, width, height):
        self.grid = []
        self.width = width
        self.height = height
        self.length = width * height
        for x in range(self.width):
            col = []
            for y in range(self.height):
                col.append(Cell(x, y, self.grid))
            self.grid.append(col)

    class Area(object):
        area = 0
        
    def getWidth(self):
        return self.width

    def getHeight(self):
        return self.height

    def getLength(self):
        return self.length

    def __len__(self):
        return self.length

    def setCellValue(self, x, y, i):
        self.grid[x][y].value = i

    def getCellValue(self, x, y):
        return self.grid[x][y].value

    def getCell(self, x, y):
        return self.grid[x][y]

    def __getitem__(self, (x, y)):
        return self.grid[x][y]
   
    def index(self, value):
        return self.grid.index(value)
    
    def fillBlock(self, left, right, top, bottom, value):
        # You can choose if you want to iterate over a range of left - exclusive right
        # or over a range of left - inclusive right. Same goes for top - exclusive bottom
        # or top - inclusive bottom
        # For now it's exclusive
        for x in range(left, right):
            for y in range(top, bottom):
                self[x, y].value = value

    """
    def floodFill(self, x, y, landUse):
        visited = set()
        self.rec_floodFill(x, y, landUse, visited)

    def rec_floodFill(self, x, y, landUse, visited):
        if (x < 0 or y < 0 or x >= self.width or y >= self.height):
            return

        cell = self.grid[x][y]
        if (x, y) in visited:
            return
        visited.add((x,y))

        if (cell.value != landUse):
            return
        
        print visited 
        self.rec_floodFill(x-1, y, landUse, visited)
        self.rec_floodFill(x+1, y, landUse, visited)
        self.rec_floodFill(x, y-1, landUse, visited)
        self.rec_floodFill(x, y+1, landUse, visited)
    """
        
    def firstFreeCell(self):
        for y in range(self.height):
            for x in range(self.width):
                if self.grid[x][y].clusterId == -1:
                    return self.grid[x][y]
        return None

    def reset(self):
        for y in range(self.height):
            for x in range(self.width):
                self.grid[x][y].clusterId == -1
        
    def floodFill(self, x, y, clusterId, landUse):
        if (x < 0 or y < 0 or x >= self.width or y >= self.height):
            return
        
        cell = self.grid[x][y]
        area = 0
        if (cell.clusterId != -1 or cell.value != landUse):
            return
        
        cell.setClusterId(clusterId)
        area += 1

        self.floodFill(x-1, y, clusterId, landUse)
        self.floodFill(x+1, y, clusterId, landUse)
        self.floodFill(x, y-1, clusterId, landUse)
        self.floodFill(x, y+1, clusterId, landUse)

    def analyze(self):
        freeCell = self.firstFreeCell()
        clusterId = 0
        while freeCell != None:
            self.floodFill(freeCell.x, freeCell.y, clusterId, freeCell.value)

            freeCell = self.firstFreeCell()
            clusterId += 1

    def printClusterId(self, clusterId):
        for y in range(self.height):
            for x in range(self.width):
                if self.grid[x][y].clusterId == clusterId:
                    print 'clusterId:',clusterId,'Cell-coordinates:','(',self.grid[x][y].x,',',self.grid[x][y].y,')'


    """
    def printVisited(self, visited):
        for y in range(self.height):
            for x in range(self.width):
                if self.grid[x][y].visited == True:
                    print self.grid[x][y].value,
            print
    """

    def printVisited(self, visited):
        for y in range(self.height):
            for x in range(self.width):
                if self[x, y].visited:
                    print self[x, y].value,
                else:
                    print "x",
            print
            
    def printGrid(self):
        for y in range(self.height):
            for x in range(self.width):
                print self[x, y].value,
            print

    def load(cls, filename):
        print "Loaded csv file"
        loadGrid = []
        reader = csv.reader(open(filename), delimiter=';')
        for line in reader:
            loadGrid.append(line)
        width = len(loadGrid[0])
        height = len(loadGrid)
        grid = Grid(width, height)
        for x in range(width):
            for y in range(height):
                grid.getCell(x, y).value = loadGrid[x][y]
        return grid
    load = classmethod(load)

class Cell(object):
    def __init__(self, x, y, grid):
        self.x = x
        self.y = y
        self.grid = grid
        self.value = 0
        #self.visited = False
        self.clusterId = -1

    def inspect(self):
        "#<Cell: value = #(value), x = #(x), y = #(y)>"

    def getClusterId(self):
        return self.clusterId
    
    def setClusterId(self, clusterId):
        self.clusterId = clusterId


""" 
class ParcelClusterAnalyzer(object):
    def __init__(self, prevLandUseCount, landUseCount, parcel, prevAreaList, areaList, prevLandUseClusters, landUseClusters, prevClusterBoundingBox, clusterBoundingBox):
        self.prevLandUseCount = {}
        self.landUseCount= {}
        self.parcel = parcel
        self.prevAreaList = {}
        self.areaList = {}
        self.prevLandUseClusters = {}
        self.landUseClusters = {}
        self.prevClusterBoundingBox = {}
        self.clusterBoundingBox = {}

    class Area(object):
        area = 0
        
    def ParcelClusterAnalyzer(self):
        pass

    def ParcelClusterAnalyzer(self, parcel):
        self.parcel = parcel
"""
        
my_grid = Grid(7, 7)
my_grid.printGrid()
print '-'*20

my_grid[1, 1].value = 1
my_grid[2, 0].value = 1
my_grid[2, 1].value = 1
my_grid[2, 2].value = 1

my_grid[3, 4].value = 2
my_grid[3, 5].value = 2
my_grid[4, 4].value = 2
my_grid[4, 5].value = 2
my_grid[5, 4].value = 2
my_grid[5, 5].value = 2

my_grid.printGrid()
print '-'*20

my_grid.firstFreeCell()

#my_grid.floodFill(x, y, landUse, area, boundingBox)
print my_grid[1, 1].clusterId
print '-'*20

my_grid.analyze()
print my_grid[0, 0].clusterId
print my_grid[1, 1].clusterId
print my_grid[2, 0].clusterId
print my_grid[2, 1].clusterId
print my_grid[2, 2].clusterId

print my_grid[3, 4].clusterId
print my_grid[3, 5].clusterId
print my_grid[4, 4].clusterId
print my_grid[4, 5].clusterId
print my_grid[5, 4].clusterId
print my_grid[5, 5].clusterId

my_grid.printClusterId(1)
my_grid.printClusterId(2)


"""
Uitkomst met beholp van floodFill moet volgende soort informatie geven:

class Cluster:
    pass

cluster = Cluster()
cluster.cells = []
cluster.cells.append(mygrid[2, 0])
cluster.left = 1
cluster.right = 2
cluster.top = 0
cluster.bottom = 2
cluster.area = 4

cluster_list = [
  cluster    
]
"""

The next idea is that I create a library of 2d templates which are simple 2d representations of the floorplans of the 3d models of buildings. What I have to program is an algorithm that compares the 2d form of the cluster with all the available 2d forms of the templates where the housing type is the same. Say I have a cluster representing detached housing with an L-shape like:

1 1 1 1 1
1 1
1 1

I need to find a template from the subset of detached housing from the library where the shape of the template matches this L-shape cluster the most.

I'm wondering what is the best method of doing this kind of matching tasks. I could compare each cell from the cluster with the value of the template on that place and calculate some scoring based on the matching cells. Or I could try and make some edge detection and compare the edge shape of cluster and template. Or I could go for a real image analysis where both cluster and template are visualised as an image of 2 colors (0 and 1 values have different colors) and try and program some kind of image matching algorithm that for each pixel of the template image evaluates the value of the cluster pixel and tries to find a match like this.

I know it's a bit of a long and difficult problem to explain but maybe someone has experience with these kind of problems or algorithms and can share some insight on it. I searched the internet on terms as image analysis, pattern matching, binary image analysis and so on...but mostly I find difficult mathematical papers that seem to go to deep in the problem for what I need for my program.