Step 3.3: Implementation - Optimization

In the last post, we have defined Camera Coverage Quality Metric (CCQM) that defines the quality of a camera network based on the view of the cameras. In the next step, we would like to perform an optimization search to find the view of the camera that maximizes this metric.

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

Going ahead we will perform experiments to quantify these results and perform comparison with state of the art.

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