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.