# Image processing: Floor plan - detecting rooms' borders (area) and room names' texts

Here is a simple building floor plan. I would like to derive the rooms as (rectangular) components and the names of the rooms. This is very common representation of building floor plans.

The problem

So far I could clean up the floor plan. However, only the walls are left as one component but I would like to derive the rooms as rectangular components. In the solution - The rooms may have polygonal shapes as well as rectangles with small rectangular components called circulation areas, corridors or an other function name... alternatively they could added to living room or any other near function. My Question is how to proceed from here?

img = Import["http://i.stack.imgur.com/qDhl7.jpg"]
nsc = DeleteSmallComponents[Binarize[img, {0, .2}]];
m = MorphologicalTransform[nsc, {"Min", "Max"}]


Cleaned up floor plan

EDIT 1

Some further information about the image.

The image contains 2 types of information.

1. The geometric
2. The Spatial

The Spatial information; it is important to abstract the room names for defining adjacency of spaces. The door and windows helps to define the adjacency matrix. The adjacency matrix with the geometric information can be used to calculate areas or boundaries. For example :

-
Your living room isn't a rectangle i.stack.imgur.com/AqOUt.png – Dr. belisarius Feb 13 '13 at 15:41
Whats been left from the rectangles can be called circulation areas, corridors or an other function name... alternatively they could added to living room or any other near function. The solution image is sort of what I need. – s.s.o Feb 13 '13 at 15:49
In any case, the treatment of that degree of freedom should be specified in the question – Dr. belisarius Feb 13 '13 at 15:57
I don't need exact solutions so they can rough n.p. Because the drawings are abstraction of real buildings and such representations you can tolerate that much of information. Edit the Q. as well. – s.s.o Feb 13 '13 at 16:04

EDIT: Updated the algorithm, new part below

Fun problem!

Ok, my first would be to find the room centers. This is relatively easy using a distance transform and geodesic erosion.

distTransform = DistanceTransform[ColorNegate@m];


The distance transform image contains for every pixel the distance to the closest wall. We're looking for the bright "peak" in the distance transform, i.e. the center of each room.

centerAreas = ImageDifference[
GeodesicDilation[Image[ImageData[distTransform] - 10],
distTransform], distTransform]


EDIT: The next part is new

With this, we can use a watershed transform to find the rooms. The watershed transform (intuitively speaking) finds "basins" in a 3d landscape. We'll invert the distance transform image to turn the "peaks" into "basins" and use the room centers as markers:

watershed =
DeleteSmallComponents[
DeleteBorderComponents[
Binarize[
Image[WatershedComponents[ColorNegate[distTransform],
centerAreas]]]], 1000]


This segments the rooms quite well. Unfortunately, the watershed transform ignores the walls - the components we found are too big. But they're close enough that this simple "grow the room rectangle until it hits the wall"-algorithm finds the actual room areas:

rooms = ComponentMeasurements[watershed, "BoundingBox"];

Clear[growRect]
growRect[{{x1_, y1_}, {x2_, y2_}}] :=
Module[{checkRectEmpty, growSingleDirection, growSingleStep, cx, cy,
left, top, right, bottom, sizeEstimate, size},
(
{cx, cy} = Round[{x1 + x2, y1 + y2}/2];

checkRectEmpty[{left_, top_, right_, bottom_}] :=
Max[ImageValue[
m, {cx - left ;; cx + right, cy - top ;; cy + bottom}]] == 0;
growSingleDirection[size_, grow_] :=
If[checkRectEmpty[size + grow], size + grow, size];
growSingleStep[size_] :=
Fold[growSingleDirection, size, IdentityMatrix[4]];

sizeEstimate =
Abs[Round[{x2 - x1, y2 - y1, x2 - x1, y2 - y1}/2 - 20]];
{left, top, right, bottom} =
FixedPoint[growSingleStep, sizeEstimate, 20];
Rectangle[{cx - left, cy - top}, {cx + right, cy + bottom}]
)]


Using this, all that's left is to display the results:

finalRectangles = growRect /@ rooms[[All, 2]];

feetAndInch[n_] := ToString[Round[n/12]] <> "'" <> ToString[Mod[n, 12]]
Show[m,
Graphics[
{
finalRectangles[[ ;; ]] /.
rect : Rectangle[{x1_, y1_}, {x2_, y2_}] :>
{
{EdgeForm[Red], Transparent, rect},
{Red,
Text[StringForm[" x \n", feetAndInch@(x2 - x1),
feetAndInch@(y2 - y1), (x2 - x1)*(y2 - y1)/(144.)], {x1 + x2,
y1 + y2}/2]}
}
}]]


or, using the original floor plan as background:

-
Thank you for putting a lot of thinking and effort! Thinning the walls might help improving it fit the rectangles. If you look at the bed rooms they are over divided. See my edit to Question. – s.s.o Feb 13 '13 at 20:32
+1 nice! Only works in mathematica 9 though. – chris Feb 13 '13 at 20:39
@chris: I think the only new function is GeodesicDilation, right? You could get the same result using a combination of FixedPoint, Dilation and MapThread[Min, {dilation, mask},2]. Could be a lot slower, though. – nikie Feb 13 '13 at 21:28
I thing it is really great answer! One minor point needs to be considered is the rectangle where eating is written as text. The rectangle should be smaller bounded by living room (most) east side and kitchens south walls. – s.s.o Feb 18 '13 at 19:14
@s.s.o: That rectangle is not a room at all. It's an artifact of the segmentation used. You could e.g. remove every rectangle that doesn't touch a wall e.g. 50% of its border. Implementation should be straightforward and is left as an exercise to the reader ;-) – nikie Feb 18 '13 at 20:52

first of all, this is a very interesting problem. I cannot provide you with a complete answer, however, if you apply

m = MorphologicalTransform[nsc, {"Max", "Min", "Max"}]


you can use

(mc = MorphologicalComponents[ColorNegate@m]) // Colorize


to find a fair number of the rooms. The expressions

lines = ImageLines[m, Method -> "RANSAC", MaxFeatures -> 15];
Show[m, Graphics[{Thickness[0.01], Blue, Line /@ lines}]]


actually let you find the walls. ImageLines has more options, so

lines = ImageLines[m, Method -> "Hough", "Segmented" -> True];
Show[m, Graphics[{Thickness[0.01], Blue, Line /@ lines}]]


can restrict the search to walls inside the house.

-
img = Import["http://i.stack.imgur.com/qDhl7.jpg"];
nsc = DeleteSmallComponents[Binarize[img, {0, .2}]];
iD = ImageDimensions[img];
mWS = 70; (*Max window span*)
sLT = 5;(*Straight line tolerance*)
i4 = Thinning@(i1 = Closing[MorphologicalTransform[nsc, {"Min", "Max"}], 3])


Now let's find the endpoints for each door and window by using HitMissTransform[] . We define some masks first:

k1 = ConstantArray[-1, 8];
v = {k1, {-1, -1, 0, 0, 1, 0, -1, -1}};
h = {k1[[;; 4]], {-1, -1, 1, 1}, {-1, -1, 0, 0}};


Now we find the candidate endpoints:

p = Position[ImageData@HitMissTransform[i4, #], 1] & /@ {v, Reverse@v, h, Reverse /@ h};
ListPlot[(Union @@ p) /. {a_, b_} -> {b, iD[[2]] - a}, Axes -> False, Frame -> True]


Now we select only paired endpoints:

lin = Union[
Select[Tuples[p[[1;;2]]], 0 < #[[1,1]] - #[[2,1]] < mWS && Abs[#[[1,2]] - #[[2,2]]] < sLT &],
Select[Tuples[p[[3;;4]]], 0 < #[[1,2]] - #[[2,2]] < mWS && Abs[#[[1,1]] - #[[2,1]]] < sLT &]] /.
{{a_, b_}, {c_, d_}} -> {{b, iD[[2]] - a}, {d, iD[[2]] - c}};
Graphics[{Point@(Union @@ lin), Line@lin},
PlotRange -> iD /. {x_, y_} -> {{1, x}, {1, y}}, Axes -> False, Frame -> True]


We finally "close" the doors and windows and use MorphologicalComponents[] to identify the rooms:

ColorNegate@ImageSubtract[img, Colorize@MorphologicalComponents@ Binarize@
Erosion[Show[ColorNegate@i1,
Graphics[Line@lin, PlotRange -> iD /. {x_, y_} -> {{1, x}, {1, y}}]], 1]]


-
Graphics[Line@lin, PlotRange -> ImageDimensions[i1] /. {x_, y_} -> {{1, x}, {1, y}}] this pace of code is quite useful. If one needs to find the openings of buildings such as doors and windows, ect. It can also be used for adjacency of rooms. – s.s.o Feb 18 '13 at 19:04
Could you explain what k1, v and h is used for ? And do you think it is possible to separate living room and kitchen as components too. Because it has also sort of separator between them. – s.s.o Feb 18 '13 at 19:07
@s.s.o I don't think there is a clean way to separate the kitchen from the living room using this algorithm. I'm using the fact that a door or a window have a pair of right/left or up/down endpoints framing it. In fact the k1, v and hare the masks for the HitMissTransform[] used to identify those endpoints – Dr. belisarius Feb 18 '13 at 21:26
@s.s.o You may however postprocess the areas afterwards to see if one of them isn't rectangular :) – Dr. belisarius Feb 18 '13 at 21:28