by Amit Moran CTO and Co-Founder
Facility managers are faced daily with the need to place cameras to ensure the monitoring of indoor spaces. Optimally, every inch of the space should be monitored to allow full coverage.
How can we plan such an installation?
If we assume that the cameras can “see” in all directions, 360 degrees, one camera will be enough for a square or rectangular room. But real-life facilities are rarely rectangular shaped and are much more complex. One will then need a larger number of cameras. But how many actually? And where to place them?
A little while ago, I read an article about placing cameras in an indoor space. Now, I like geometrical riddles! Let me present one to you which is very much related to what we do also at Indoor Robotics.
Background
It is actually a well known problem named “the art gallery problem” .
I recently read that it all started in 1973 where Victor Kelly presented the problem to Václav Hvatel, who solved it within six months. In 1978 Steve Fisk found a surprising, elegant and relatively simple way to prove it. Fisk presented the proof in only one paragraph at sciencedirect.com!
Solution
I will try to explain the concept. Like in any other problems in your life, you should always start with something simple to try to understand the basics. If we draw some shapes we can see that for a simple convex shape it is easy to solve, right? (Basically a convex shape or a polygon is a polygon in which you can connect any two points in a straight segment that is entirely inside the polygon. A triangle is the simplest case of a convex shape .
In a convex shaped room, one camera (no matter its position) will always have a straight line of sight between it and every other point in space, which means the camera sees everything (with some assumptions like 360 deg and no dead-zone due to furniture etc.)
So now we will try to generalize it a bit. What do we do for a more complex shaped room (or a set of rooms). If only we could divide that room into smaller convex shapes, we can place a camera in each of those convex sub-shapes, and thus we will surely cover the entire premises… But we can! Every shape can be split into triangles. There are very efficient algorithms for triangulation . I won’t get into this now but trust me here (or even better don’t! And verify what I write here) that the minimal number of triangles that can be created from any shape is equal to N-2 where N is the number of edges of that shape (for example, a square can always be divided into 2 triangles by drawing one diagonal line, and a pentagon can be divided into 3 triangles etc.). Without adding extra vertices of course.
That’s it! For a facility with 10 walls, we can be sure that we don’t require more than 8 cameras as we can simply place a camera in each resulting triangle.
Well… we can even do better than that!
Imagine placing a 360 deg camera on a common vertex of several resulting triangles. This camera can monitor all those triangles together. Can we determine a lower upper bound of the minimum number of required cameras?
What Fisk suggested is to 3-color the vertices of the resulting triangulation. That means that each vertex of each triangle is given one distinct color (red, green, blue for example). Under a 3-coloring, every triangle must have all three colors.
Now, we simply need to choose a color and this set of vertices is a valid set for placing all the cameras. This is because every triangle of the complex shape (or facility) is monitored by its vertex with that color (complex shape divided into triangles => each triangle has all 3 colors vertices => you have one color vertex in each triangle => this vertex can be a spot to place a camera).
So how many do we have?
There cannot be more than N/3 vertices in each color, because if there were, the total number of vertices would be greater than N. Therefore there is a color that appears at most N/3 times.
So, in order to monitor a complex facility of N walls, the upper bound of the minimum number of 360 cameras needed is N/3 !
This means that for our facility of 10 walls, we can be sure we won’t need more than 3 cameras.
360° Camera View for Indoor Spaces
Real life has much more edge cases and constraints. Some of which are still in the geometry space, such as: What if the field of view of the cameras is not 360 deg? The world is 3D, not 2D. What if the height of the facility is significant (like a warehouse)? What if there are spontaneous appearing blocking objects (pallets in a warehouse, boxes, new tables etc)? Resolution of the cameras is limited to a certain distance. Unfortunately, the number of cameras is quickly rising…
There are even more problems outside of geometry, such as: What if you cannot film and record every area 24/7 due to privacy regulations? What if there is a limit of the infrastructure for the number of connected cameras?
We, at Indoor Robotics, found a way to solve those problems. We developed Tando™, a fleet of autonomous flying robots which autonomously patrols the facility and monitors every inch of it – behind objects, at different heights, adaptable to changes and can be scheduled to run at specific hours to avoid compromising privacy.
When Tando™ is not patrolling, it is docked on a ceiling docking tile, charging and monitoring as a regular security camera.
So, in order to monitor a complex facility of N walls, the upper bound of the minimum number of Tandos™ needed is simply 1 !
Here, you don’t need to be a mathematician in order to understand how this works 🙂
This is why we claim that Tando™ is hands down the most efficient way to monitor (and collect data) for indoor spaces.
