# AVSS: Airborne Video Surveillance System
## 4 UAV Placement Algorithm
### Placement Score Metric  
The deployment of the cameras plays a critical role in surveillance systems. Because our system is an improvised mobile surveillance infrastructure, an automatic algorithm is much more preferable to manual deployment, which requires human labor. Deploying as many UAVs as possible will always make surveillance more effective, but when the number of UAVs is limited, efficient deployment is crucial to achieve maximum efficacy. Therefore, we have devised a novel algorithm that can automatically deploy UAVs to form a surveillance system based on the information given by the administrator. In this section, the algorithm and the model the algorithm is operating on are explained in steps. The operations, evaluations and analysis of the model will be given in later section. Each region has different degree of importance, and varying importance of region requires different level of attention. We have assumed all regions and camera placements are rectangles that are perfectly aligned with the \(x,y\) axes. Camera images are circular, but the edges of a camera capture are distorted so that they are improper for surveillance. We assume the captures are rectangular as rectangles are the end results of most camera captures. In this paper, the region with higher importance is notated as focusing area. The importance of an area is expressed with a score, focusing score. A camera's quality is expressed as UAV score, which is proportional to the number of pixels in a camera image. The score of a camera placement is expressed as:  
\[F\times\left(\frac{D}{h^{2}}+\alpha\right), \tag{1}\]  
Figure 3: The map of focusing area and UAV placement before and after all placements of 45 UAVs. where \(F\) is focusing score \(\times\) area of the intersecting region, \(D\) is the UAV score, \(h\) is the altitude of the UAV, and \(\alpha\) is the coverage score. The UAV score is inversely proportional to \(h^{2}\) because the number of pixels per distance is inversely proportional to the altitude of the UAV, and \(\alpha\) is to ensure UAV covers larger region if there is no score difference or it is less significant. Our algorithm places a UAV that maximizes the global sum of the score of each UAV placement. When placing multiple cameras, it is generally better to avoid duplicate placement, but not always. Avoiding redundancies of captures can be useful, but having redundancy in much more important region may be preferable to capturing completely insignificant location. Therefore, Equation (1) is generalized for multiple placements as,  
\[F\times\left(\sqrt[k]{\sum\vec{D^{k}}}+\alpha\right) \tag{2}\]  
for the intersecting camera regions, where \(\vec{D}\) is \(D/h^{2}\). In the perspective of a new UAV to be placed, the equation acts as an incentive to avoid overlaps, because the score of new UAV means subtraction of the score of previous overlapping UAVs as in,  
\[S_{n}=F\times\left[\left(\sqrt[k]{\sum\limits_{m=1}^{n}D_{x}^{-k}}+\alpha \right)-\left(\sqrt[k]{\sum\limits_{m=1}^{n-1}D_{x}^{-k}}+\alpha\right)\right],\]  
when \(k=1\), each placement acts as if there is no other UAV placed in the system. In Equation (1) and (2), \(F\) is the area of coverage with the area score. The coverage of a camera is proportional to the square of the altitude of the UAV, \(h\). In other words, \(F\) is inversely proportional to \(\vec{D}\), which makes different sized coverage of the same scored focusing area always has the same incentive. The coverage coefficient alpha acts as the incentive to cover a larger region within the same scored region. In summary, our algorithm deploys UAVs under given focusing scores of each region and global coverage coefficient alone. Because many countries have legal limitations such as no-capture or no-fly zones for UAVs, we devised a method to support such features with our system. In our algorithm, a no-capture or a no-fly zone can also be set by giving a region a large negative focusing score, which will result in UAVs placed around that region.