In summary, the first step was to simulate the possible trajectories followed by humans in a scenario, followed by identifying the high occupancy regions in the scenario. Expectation Maximization algorithm was used to identify these regions which gave us clusters of regions that have high occupancy. To begin with, we assume that each cluster is viewed by a single camera and the idea is to perform optimization to maximize the CCQM for the cluster. Depending on the size of the cluster, there might be a need for employing multiple cameras for a single cluster which will be addressed later.
Setup: We start by optimizing the camera network for the floor depicted in figure 4. of the previous blog. This triangle mesh constitutes 4562 triangles. We use the same mesh for the ceiling but at a height of 10 ft. To begin with we pursue optimization in a discrete fashion. We assume that the only possible location of the cameras are the centroids of the triangles in the ceiling triangle mesh. The only possible orientations of the cameras are those pointed towards the centroids of the triangles on the floors triangle mesh. As a brute force algorithm would have a complexity of $O(n^2)$. Further more for every possible configurations. we need to locate points in the view of the camera (points not obstructed by geometry) to accumulate their area and human occupancy. This would multiply the complexity to be $O(n^3)$. Given the number of the triangles, this would require significant amount of time and computations. This calls for a heuristic optimization algorithm.
The optimization is applied on one cluster at a time. Given a cluster, first the points in the ceiling that have a view of the centeroid of the cluster are identified and these points are considered as the possible location of the cameras. The only possible orientation for each camera are pointing towards the points in the cluster. This would simplify the problem to finding two points, one on the ceiling to position the camera and the second on the floor to point the camera towards. We use a variation of a Hill Climbing algorithm called the Random-Restart Hill Climbing. Random-Restart Hill Climbing is a relatively simple optimization search approach that provides near optimal performance[1, 2]. The idea is to search a certain number of points randomly and choose the best start location for hill climbing. But this is done at two levels since two variables need to be optimized. Given a point on the ceiling we perform random restart hill climb for points on the floor to find its optimized pair. This process is repeated for a certain percentage of points on the ceiling to find a suitable starting point. This is used as the starting point to perform hill climbing. The search continues through the neighbors until more progress is noticed.
The obtained results are as shown below
To recap the cluster are
| Cluster 0 | Blue |
| Cluster 1 | Red |
| Cluster 2 | Green |
| Cluster 3 | Aqua |
| Cluster 4 | Light Pink |
| Cluster 5 | Pink |
Cluster parameters Info
| Cluster | MeanX | VarX | MeanZ | VarZ | MeanO | VarO |
| 0 | 2627.1913 | 252.0491 | 227.2815 | 25.954 | 0.002 | 0.0016 |
| 1 | 1784.9107 | 502.9819 | 426.3474 | 48.0879 | 0.0029 | 0.0029 |
| 2 | 725.5888 | 280.347 | 219.6706 | 25.6276 | 0.0011 | 0.0009 |
| 3 | 2617.2649 | 258.5819 | 633.8928 | 31.2469 | 0.001 | 0.0008 |
| 4 | 1577.6143 | 1017.7892 | 420.1754 | 163.0683 | 0 | 0 |
| 5 | 700.9391 | 292.696 | 643.3453 | 22.5434 | 0.0011 | 0.0008 |
Considering 5 valid clusters
Optimized parameters
Here var1 = Eye and var2 = center
| Cluster | EyeX | EyeY | EyeZ | CenterX | CenterY | CenterZ |
| 0 | 3001.88 | 119 | 189.971 | 2282.35 | 68 | 460.1 |
| 1 | 2281.82 | 119 | 380.491 | 1169.24 | 68 | 650.761 |
| 2 | 1206.07 | 119 | 209.531 | 216.731 | 68 | 216.935 |
| 3 | 2245.89 | 119 | 671.584 | 2177.13 | 68 | 219.217 |
| 4 | - | - | - | - | - | - |
| 5 | 1205.58 | 119 | 637.524 | 185.957 | 68 | 637.978 |
References
[1] Yuan Zhang, Tao Lei, Regina Barzilay, Tommi Jaakkola Greed is Good if Randomized: New Inference for Dependency Parsing, Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)[2] Filho, C.F.F.C.; Costa, M.G.F.; Filho, J.E.C.; de Oliveira, A.L.M., "Using a random restart hill-climbing algorithm to reduce component assembly time in printed circuit boards," Industrial Technology (ICIT), 2010 IEEE International Conference on , vol., no., pp.1706,1711, 14-17 March 2010
