[ EDIT - Fully extended answer to provide complete solution ]
Preface
I wouldn't usually work to provide a "solution" since I feel it is well beyond a useful, reusable Q&A format... but it was an interesting problem.
Answer
The following details a base algorithm to detect potential door openings within the floor plan. It is not performance optimized or tested beyond the single case provided. Since the definition of a door has been given by OP only as "an opening of specified width", it is also susceptible to false indications. The algorithm can only detect principle, orthogonal doors.
Example Result:
Approach
The approach is as follows:
- Invert and threshold in the input image, so that the darkest element are cast to white (full byte value).
- Compute a contour detection, to identify the boundaries of the now white areas.
- Filter to only select contours on an area greater that a selected threshold (thus removing text elements an noise).
- "Walk" the selected contours to determine the nodes at which a "corner" occurs. A corner is defined as an angular change above a threshold.
- Analyse the detected corners for pairings that qualify as "doors".
- [Superfluous Rendering] Finally, raster within the rectangular bounds for the filtered contours, in order to white fill them into a resultant image. (Note: This isn't computational efficient or elegant, however the EmguCV methods for contour filling only support convex contours). The "doors" are also rendered in red.
Algorithm
// Open the image
Image<Gray, byte> baseImage = new Image<Gray, byte>(@"TestLayout.jpg");
// Invert the image
Image<Gray, byte> invBaseImage = baseImage.Not();
// Threshold the image so as "close to white" is maintained, all else is black
Image<Gray, byte> blackOnlyImage = invBaseImage.ThresholdBinary(new Gray(200), new Gray(255));
// An output image of the same size to contain the walls
Image<Gray, byte> wallsOnlyImage = new Image<Gray, byte>(blackOnlyImage.Size);
// A set of dected contours
VectorOfVectorOfPoint inputContours = new VectorOfVectorOfPoint();
// A set of validated contours
List<VectorOfPoint> validContours = new List<VectorOfPoint>();
// Perform contour detection
Mat hierarchy = new Mat();
CvInvoke.FindContours(blackOnlyImage, inputContours, hierarchy, RetrType.External, ChainApproxMethod.ChainApproxSimple);
// Filter out to select only contours bounding more that 500 pixels
int areaThreshold = 500;
for (int c = 0; c < inputContours.Size; c++)
{
if (CvInvoke.ContourArea(inputContours[c]) >= areaThreshold)
{
validContours.Add(inputContours[c]);
}
}
// Find all the corner points in the valid contours
List<Point> contourCorners = new List<Point>();
foreach(VectorOfPoint contour in validContours)
{
contourCorners.AddRange(CornerWalk(contour, 80));
}
// Sort the contour corners by proximity to origin in order to optimise following loops
contourCorners.OrderBy(p => Math.Sqrt(Math.Pow(p.X, 2) + Math.Pow(p.Y, 2)));
// Extract all door candidate point pairs from all detected corners
List<Tuple<Point, Point>> doorCandidates = FindDoors(contourCorners, 2, 30, 45);
// Pixels contained within the filtered contours are walls, fill them white
RasterFill(wallsOnlyImage, validContours);
// Output Image
Image<Rgb, byte> outputImage = new Image<Rgb, byte>(wallsOnlyImage.Size);
CvInvoke.CvtColor(wallsOnlyImage, outputImage, ColorConversion.Gray2Rgb);
// Draw the doors
foreach (Tuple<Point,Point> door in doorCandidates)
{
outputImage.Draw(new LineSegment2D(door.Item1, door.Item2), new Rgb(255,0,0), 1);
}
// Display generated output and save it to file
CvInvoke.NamedWindow("TestOutput");
CvInvoke.Imshow("TestOutput", outputImage);
CvInvoke.WaitKey();
outputImage.Save(@"OutputImage.bmp");
Corner Extraction
static List<Point> CornerWalk(VectorOfPoint contour, int threshold)
{
// Create a resultant list of points
List<Point> result = new List<Point>();
// Points are used to store 2D vectors as dx,dy (i,j)
Point reverseVector, forwardVector;
double theta;
// For each point on the contour
for(int p = 1; p < contour.Size; p++)
{
// Determine the vector to the prior point
reverseVector = new Point()
{
X = contour[p].X - contour[p - 1].X,
Y = contour[p].Y - contour[p - 1].Y,
};
// Determine the vector to the next point
forwardVector = p == contour.Size - 1 ?
new Point()
{
X = contour[0].X - contour[p].X,
Y = contour[0].Y - contour[p].Y,
} :
new Point()
{
X = contour[p + 1].X - contour[p].X,
Y = contour[p + 1].Y - contour[p].Y,
};
// Compute the angular delta between the two vectors (Radians)
theta = Math.Acos(((reverseVector.X * forwardVector.X) + (reverseVector.Y * forwardVector.Y)) /
(Math.Sqrt(Math.Pow(reverseVector.X, 2) + Math.Pow(reverseVector.Y, 2)) *
Math.Sqrt(Math.Pow(forwardVector.X, 2) + Math.Pow(forwardVector.Y, 2))));
// Convert the angle to degrees
theta *= 180 / Math.PI;
// If the angle is above or equal the threshold, the point is a corner
if (theta >= threshold) result.Add(contour[p]);
}
// Return the result
return result;
}
Door Detection
static List<Tuple<Point, Point>> FindDoors(
List<Point> cornerPoints,
int inLineTolerance,
int minDoorWidth,
int maxDoorWidth)
{
// Create a resultant list of pairs of points
List<Tuple<Point, Point>> results = new List<Tuple<Point, Point>>();
Point p1, p2;
// For every point in the list
for (int a = 0; a < cornerPoints.Count; a++)
{
p1 = cornerPoints[a];
// Against every other point in the list
for (int b = 0; b < cornerPoints.Count; b++)
{
// Don't compare a point to it's self...
if (a == b) continue;
p2 = cornerPoints[b];
// If p1 to p2 qualifies as a door:
// Vertical Doors - A vertical door will have to points of the same X value, within tolerance, and a Y value delta within the
// min-max limits of a door width.
if (((Math.Abs(p1.X - p2.X) < inLineTolerance) && (Math.Abs(p1.Y - p2.Y) > minDoorWidth) && (Math.Abs(p1.Y - p2.Y) < maxDoorWidth)) ||
// Horizontal Doors - A horizontal door will have to points of the same Y value, within tolerance, and a X value delta within the
// min-max limits of a door width.
((Math.Abs(p1.Y - p2.Y) < inLineTolerance) && (Math.Abs(p1.X - p2.X) > minDoorWidth) && (Math.Abs(p1.X - p2.X) < maxDoorWidth)))
{
// Add the point pair to the result
results.Add(new Tuple<Point, Point>(p1, p2));
// Remove them from further consideration
cornerPoints.Remove(p1);
cornerPoints.Remove(p2);
// Decrement the looping indexes and start over with a new p1
b--; a--;
break;
}
}
}
// Finally return the result
return results;
}
Contour Filling (Render Utility - Not Functional)
static void RasterFill(Image<Gray,byte> dstImg, List<VectorOfPoint> contours)
{
Rectangle contourBounds;
PointF testPoint;
// For each contour detected
foreach(VectorOfPoint contour in contours)
{
// Within the bounds of this contour
contourBounds = CvInvoke.BoundingRectangle(contour);
for (int u = contourBounds.X; u < contourBounds.X + contourBounds.Width; u++)
{
for (int v = contourBounds.Y; v < contourBounds.Y + contourBounds.Height; v++)
{
// Test to determine whether the point is within the contour
testPoint = new PointF(u, v);
// If it is inside the contour, OR on the contour
if (CvInvoke.PointPolygonTest(contour, testPoint, false) >= 0)
{
// Set it white
dstImg.Data[v, u, 0] = 255;
}
}
}
}
}
