Game-theoretic surveillance over arbitrary floor plan using a video camera network | Signal, Image and Video Processing Skip to main content
Springer Nature Link
Log in

Game-theoretic surveillance over arbitrary floor plan using a video camera network

  • Original Paper
  • Published:
Signal, Image and Video Processing Aims and scope Submit manuscript

Abstract

Coordinated multi-resolution tracking over arbitrary floor plan is addressed using a game-theoretic approach. An enhanced radial sweep algorithm is devised to find the polygon of visibility at any point on or inside a polygon that contains vision-obstructing polygonal entities. By sampling the edges of a polygon and edges of any polygonal hole inside that polygon, a two-pass 0–1 programming process is formulated to find a near-optimal set of camera samples that can dynamically cover, at a high probability, area under surveillance in the presence of camera handoffs. Radius Multiplier is introduced to handle partial visibility and is set to 1 by default to avoid insolvability of 0–1 programming problems. As a remedy to excessive redundancy triggered by camera clustering, we set camera redundancy to a fixed value of 3 for any block with concave Valid Area. Branch-and-cut algorithm is employed to solve 0–1 programming problems. Assigning a fixed value to Camera Redundancy of blocks with concave Valid Area, setting Radius Multiplier to a nonzero value, and utilizing secondary utility yielded better simulation results for various types of floor plans. Raising Camera Redundancy of blocks with non-concave Valid Area contributed to performance boost and in the meantime, increased the number of cameras needed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22

Similar content being viewed by others

References

  1. Song, B., Soto, C., Roy-Chowdhury, A.K., Farrell, J.A.: Decentralized camera network control using game theory. In: Proceedings of the 2nd ACM/IEEE International Conference on Distributed Smart Cameras, Stanford, CA, USA, September 7–11, pp. 1–8 (2008)

  2. Yang, A., Maji, S., Christoudas, M., Darrell, T., Malik, J., Sastry, S.: Multiple-view object recognition in band-limited distributed camera networks. In: Proceedings of the 3rd ACM/IEEE International Conference on Distributed Smart Cameras, Como, Italy, pp. 1–8 (2009)

  3. Quinn, M., Mudumbai, R., Kuo, T., Ni, Z., Leo, C.D., Manjunath, B.S.: Visnet: a distributed vision testbed. In: Proceedings of the 2nd ACM/IEEE International Conference on Distributed Smart Cameras, Stanford, CA, USA, September 7–11, pp. 364–371 (2008)

  4. Ermis, E.B., Clarot, P., Jodoin, P.-M., Saligrama, V.: Activity based matching in distributed camera networks. IEEE Trans. Image Process. 19(10), 2595–2613 (2010)

    Article  MathSciNet  Google Scholar 

  5. Black, J., Ellis, T.: Multi camera image tracking. Image Vis. Comput. 24(11), 1256–1267 (2006)

    Article  Google Scholar 

  6. Comaniciu, D., Berton, F., Ramesh, V.: Adaptive resolution system for distributed surveillance. Real Time Imaging 8(5), 427–437 (2002)

    Article  MATH  Google Scholar 

  7. Huang, K.S., Trivedi, M.M.: Video arrays for real-time tracking of person, head, and face in an intelligent room. Mach. Vis. Appl. 14(2), 103–111 (2003)

    Google Scholar 

  8. Song, B., Ding, C., Kamal, A., Farrell, J., Roy-Chowdhury, A.: Distributed camera networks: integrated sensing and analysis for wide area scene understanding. IEEE Signal Process. Mag. 28(3), 20–31 (2011)

    Google Scholar 

  9. Roy-Chowdhury, K., Song, B.: Camera networks: the acquisition and analysis of videos over wide areas. Synth. Lect. Comput. Vis. 3(1), 1–133 (2012)

    Google Scholar 

  10. Mittal, A., Davis, L.: A general method for sensor planning in multi-sensor systems: extension to random occlusion. Int. J. Comput. Vis. 76(1), 31–52 (2008)

    Article  Google Scholar 

  11. Park, J., Bhat, P.C., Kak, A.C.: A look-up table based approach for solving the camera selection problem in large camera networks. In: Proceedings of International Workshop on Distributed Smart Cameras (2006)

  12. Kansal, A., Kaiser, W., Pottie, G., Srivastava, M., Sukhatme, G.: Reconfiguration methods for mobile sensor networks. ACM Trans. Sens. Netw. 3(4), 22 (2007)

    Article  Google Scholar 

  13. Piciarelli, C., Micheloni, C., Foresti, G.L.: PTZ camera network reconfiguration. In: Proceedings of International Workshop on Distributed Smart Cameras, pp. 1–7 (2009)

  14. Soto, C., Song, B., Roy-Chowdhury, A.K.: Distributed multi-target tracking in a self-configuring camera network. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 1486–1493 (2009)

  15. Fudenberg, D., Tirole, J.: Game Theory. MIT Press, Cambridge (1991)

    Google Scholar 

  16. Tu, Z., Bhattacharya, P.: A game-theoretic design for collaborative tracking in a video camera. In: Proceedings of 3rd Workshop on Activity Monitoring by Multi-camera Surveillance Systems, Klagenfurt, Austria, pp. 474–479 (2011)

  17. Erdem, U.M., Sclaroff, S.: Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements. Comput. Vis. Image Understand. 103(3), 156–169 (2006)

    Article  Google Scholar 

  18. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

    Google Scholar 

  19. TRENDnet: ProView PTZ Internet Camera TV-IP600. http://www.trendnet.com/products/proddetail.asp?prod=155_TV-IP600

  20. Wolsey, L.A.: Integer Programming. Wiley, New York (1998)

    MATH  Google Scholar 

  21. Makhorin: GLPK (GNU Linear Programming Kit). http://www.gnu.org/s/glpk/

  22. Cai, Y.: How many pixels do we need to see things? In: Proceedings of International Conference on Computational Science, vol. 2659, p. 700 (2003)

  23. Barron, E.N.: Game Theory: An Introduction. Wiley, Hoboken (2008)

Download references

Acknowledgments

This work was partially supported by United States Air Force Office of Scientific Research [FA9550-01-1-0519]. We also thank the College of Engineering and Applied Sciences, University of Cincinnati for partial support of this project.

Author information

Authors and Affiliations

  1. School of Computing Sciences and Informatics, University of Cincinnati, 2600 Clifton Ave., Cincinnati, OH, 45221, USA

    Zongjie Tu & Prabir Bhattacharya

Authors
  1. Zongjie Tu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Prabir Bhattacharya
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zongjie Tu.

Appendix

Appendix

To make this paper self-contained, we briefly review the definition of Nash equilibrium. Further details regarding Nash equilibrium can be found in [23] and [15].

Nash equilibrium is a situation in which no player in a game involving two or more players can increase its utility by changing its strategy alone, given the strategies that the other players are using. More formally, Nash equilibrium corresponds to a strategy profile in which each strategy is a best response to the other strategies in the strategy profile, where the best response is defined as the strategy that yields the most favorable result for a player. The concept of Nash equilibrium has been extended to Bayesian Nash equilibrium where the information each player has regarding characteristics of the other players is incomplete.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tu, Z., Bhattacharya, P. Game-theoretic surveillance over arbitrary floor plan using a video camera network. SIViP 7, 705–721 (2013). https://doi.org/10.1007/s11760-013-0484-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11760-013-0484-8

Keywords

Search

Navigation