علوم و تکنولوژی محیط زیست، دورهبیست و دوم، شماره هشت، آبان ماه 99

مکان گزینی و بهینه سازی پوشش دوربین های مدار بسته به منظور حمایت از مونیتورینگ بهتر با استفاده از الگوریتم S-ROPE و بصری سازی سه بعدی

جعفر کریمی[1]

 محمد حسن وحیدنیا[2]^*

vahidnia84@gmail.com

چکیده

زمینه و هدف: در جوامع مدرن مونیتورینگ براساس دوربین های مداربسته مسئله­ای ضروری برای حفظ محیط زیست و امنیت اجتماعی به شمار می آید. بهینه سازی شبکه های دوربین و نحوه طراحی شبکه آن ها از جمله چالش های مطالعات شبکه های دوربین است. هدف از این مقاله توسعه شیوه ای مکانمند برای یافتن پیکربندی دوربین های مداربسته جهت ایجاد حداکثر پوشش تصویری ممکن در یک فضای شهری است.

روش بررسی: به طور کلی این پژوهش در دو مرحله در سال 96 انجام گرفته است. در مرحله اول اعمال الگوریتم مکانیابی دوربین ها در فضای دو بعدی صورت می پذیرد و خروجی به دست آمده از آن در مرحله دوم در فضای سه بعدی و به صورت بصری تجزیه و تحلیل می گردد. اولین مرحله با استفاده از نرم افزار ArcGIS و زبان برنامه نویسی Python انجام پذیرفت و از الگوریتم S-ROPE به عنوان روشی با میزان دقت بالا در زمینه استقرار دوربین ها استفاده شد. ضمن این که تعدیلاتی در الگوریتم شامل زاویه دید و غیر دودویی بودن منطقه انجام گرفت. در مرحله دوم از مدلسازی سه بعدی در محیطcity  Engine برای اعتبارسنجی خروجی به دست آمده در یک محدوده شهری استفاده شد.

یافته ها: با الگوریتم S-ROPE یک مکان گزینی اتوماتیک برای دوربین ها انجام گرفت به گونه ای که مساحت 28/1798 متر مربع از کل مساحت 98/1953 مترمربعی محدوده مطالعاتی، یعنی 92%، تحت پوشش قرار گرفت. پس از بررسی سه بعدی تنها دو عدد دوربین به مجموع دوربین ها برای پوشش 100% اضافه شد.

بحث و نتیجه گیری: با روش پیشنهادی اولاً در تعداد دوربین های به کار رفته به تعداد قابل توجهی صرفه جویی صورت می پذیرد و در عین حال بیشترین پوشش ممکن نیز به دست خواهد آمد.تنها چالش پیش رو زمان اجرای فرآیند برای مساحت های بزرگ می باشد که با توجه به غیر آنی بودن ماهیت مسئله، خللی در روش پیشنهادی ایجاد نمی کند.

واژه های کلیدی: خط دید و تحلیل محدوده دید، دوربین های مدار بسته، بصری سازی سه بعدی ,S-ROPE روش ساده رتبه بندی و حذف همپوشانی

Locating and Optimizing Coverage of CCTV Cameras to Support Better Monitoring Using S-ROPE Algorithm and 3D Visualization

Jafar Karmi[3]

Mohammad H. Vahidnia[4]^*

vahidnia84@gmail.com

Abstract

Background and Objective: Modern surveillance systems based on CCTV cameras is an essential element for protecting the environment and social security. Camera network optimization and designing its architecture are among the issues of camera network studies. The purpose of this paper is to develop a geospatial solution to find configurations for CCTV cameras in such a way that creates the maximum possible visual coverage in an urban area.

Methods: In general, this research is performed in two steps. In the first step, the algorithm is used to locate cameras in two-dimensional space, and the resulting output is analyzed in the second step in a three-dimensional space and visually. The first step was performed using ArcGIS software and Python programming language, and the S-ROPE algorithm was used as a high-precision method for 2D camera deployment. After the modifications were made at the viewing and non-binary regions of the region, the location of the cameras was determined. In the second stage, the three-dimensional model of City Engine software was used to validate the output obtained using the S-ROPE algorithm. The evaluation of the applied method was performed on an urban study area.

Findings: With the S-ROPE algorithm, an automated location determination for cameras was taken so that the area of 1798.28 m² was covered by a total area of 1953.98 m² of study area, i.e. 92%. After a three-dimensional review, only two cameras were added to the total of cameras to cover 100%.

Discussion and Conclusion: With the proposed method, the number of cameras used makes significant savings, and the most possible coverage is achieved. The only challenge is the process time for large areas, which, due to the non-urgent nature of the problem, does not create a dent in the proposed method.

Keywords: Line of Sight and Visibility Analysis, Close Circuit Television (CCTV), 3D Visualization, Simple Rank and Overlap Elimination Method (S-ROPE).

مقدمه

نصب دوربین های مداربسته یکی از روشهای هوشمند و موثر کنترل افراد، پایش محیط زیست و پیشگیری از جرایم است (1). در حال حاضر کشورهای اروپایی و پیشرفته از این روش بهره می گیرند، به عنوان مثال انگلستان با نصب دوربین های متعدد در خیابانها و مناطق عمومی شهر، به کشور دوربین ها معروف شده است. شبکه این سیستم های نظارتی به تمامی خیابانها، مدارس و گاهی حتی داخل اتاقهای کار نیز سرایت می کند.  بارزترین مورد آن در منطقه خاور میانه شهر تجاری و بندری دبی در امارت متحده عربی است که بنا بر ادعای مسئولان امنیتی در این شهر هیچ نقطه از شهر دبی خارج از دید دوربین های مداربسته^[5] آنها نیست (2). دوربین های مداربسته ای که این روزها در گوشه و کنار شهر می بینیم، تا به حال کاشف بسیاری از سرقتها و جنایتها بوده اند سیستم های نظارتی می توانند از نحوه رفتار و عملکرد مجرمان سابقه دار در اماکن عمومی اطلاع یابند و بر آنها نظارت کنند (برای مثال افرادی که از فروشگاههای بزرگ سرقت می کنند). اپراتورهای این سیستم ها معمولاً چهره این گونه افراد را می­شناسند و از طریق دوربین ها بر حرکات آنان نظارت می کنند که در حقیقت این روش نسبت به کارگیری نیروهای پلیس بسیار بهتر می نماید (3). استفاده از سیستم های اطلاعات جغرافیایی و فناوری های جدید، جهت هر چه بهتر نمودن موقعیت این دوربین ها و کاهش آن ها و در عین حال پوشش بیشتر، موضوعی است که در این تحقیق به آن پرداخته می شود. از آنجا که بسیاری از تجزیه و تحلیل های مربوط به پوشش دوربین ها فضایی و جغرافیایی می باشد، لذا GIS در این زمینه می تواند نقش پررنگی داشته باشد. شبکه دوربین های مدار بسته (CCVT) یکی از متداولترین اشکال نظارت بصری در محیط های اداری و فضاهای عمومی در محیط می­باشد. به طور سنتی، طراحی شبکه های نظارت بصری از نوع CCTV توسط معماران و طراحان چشم انداز شهری از طریق یک روند تکراری و فرایند gut feel با استفاده از نرم افزار CAD انجام می گرفته است. در نتیجه، می تواند پوشش تصویری بیش از حد و یا ناقص فضای باز را به وجود بیاورد و در اثر آن اتلاف هزینه صرف شده برای تهیه شبکه CCTV را در پی خواهد داشت. علاوه بر این افراط در نصب این دوربین ها به زیبایی منظر شهری نیز لطمه وارد می­کند. انتخاب مکان بهینه برای سایت های نظارت بصری در یک فضای باز شبیه به مسئله هندسه محاسباتی شناخته شده NP-hard، موسوم به مشکل گالری هنر^[6](AGP)^[7] (4) و نیز به طور گسترده ای مشابه مشکل تخصیص مکان در سیستم اطلاعات جغرافیایی (GIS) است. Fisk با ارائه یک الگوریتم سه رنگی^[8]، استدلالی  مختصر و زیبا از این محاسبه بدترین حالت تعداد نگهبانان فراهم کرد (5). در پژوهش های دیگری Bose و همکاران (6) و همچنین Marengoni و همکاران (7) مشکل گالری هنر را برای حل سه بعدی مسائل امنیتی در نظر گرفتند. Cole و Sharir نشان دادند که مشکل نظارت بر سطح یک  NP-complete است (8). Eidenbenz نیز استدلال ها و الگوریتم تقریبی برای این مشکل پیشنهاد نموده است (9). مشکل گالری هنر موضوع کار بسیاری تحقیقات نظری و الگوریتم های کارآمد پیشنهاد شده برای راه حل موضوع نظارت بصری است و البته همچنان محور تمرکز فعالیت های پژوهشی نیز می باشد. برخی از تحقیقات علاقه مند به پرداختن به محدوده دید گارد یا همان ناظر (مثلا دوربین) بوده اند (10 و 11). اما به طور کلی قابلیت های غیر واقعی برای نگهبان فرض می شود. به عنوان مثال، منظقه دید نامحدود و در نتیجه، روش توسعه یافته برای گالری هنری با این فرض ممکن است مناسب برای مکانیابی استقرار سنسورها نباشند. علاوه بر این، هیچ گونه قابلیتی برای در نظر گرفتن محدودیت های بودجه یا ناهمگن بودن منطقه وجود ندارد. درحالی که در عمل ممکن است فقط تعداد مشخصی از سنسورها به علت هزینه لحاظ شوند و یا برخی از مناطق برای نظارت، بیشتر از بقیه اهمیت داشته باشند. از آن جا که Floriani و همکاران (12) نشان دادند تعیین حداقل مجموعه ای از نقاط دید معادل با مشکل پوشش مجموعه^[9] است، پس مدل های پوشش محل، کارایی بیشتری برای حل  مشکلات پوشش دید^[10] دارند. Goodchild و Lee (13) و در تحقیق دیگری Lee (14) با اعمال مشکلات پوشش مجموعه محل و پوشش حداکثری محل، مشکلات پوشش سطوح ناهموار را مورد بررسی قرار داده و این مشکلات را با استفاده از رویکردهای حریصانه^[11] حل نمودند. Kim و همکاران این مشکلات را بر روی مدل رقومی ارتفاع (DEM)  مورد بررسی قرار داده و با استفاده از تکنیک های ابتکاری آنها را حل نموده اند (15). Kaucic و Zalik مشکل پوشش چند سطحی^[12] را براساس مسأله مجموعه پوشش محل معرفی نموده و پیشنهادی  برای حل آن ارائه کرده اند (16). مسائل مربوط به پوشش سطح، با LSCP[13] و MCLP[14]، و نیز  مجموعه مسائل بهینه سازی NP-complete مرتبط هستند. بدین معنا که هنگام تلاش برای حل این مسائل، مشکلات و چالش های محاسباتی مورد انتظار است. قرار دادن تجهیزات مانند دوربین ها در سیستم های نظارتی شهری (داخلی و خارجی) نیز مورد بحث قرار گرفته است (10و 17). سیستم های نظارت از چندین جهت ، مانند آشکارسازی شی، شناسایی، ردیابی، تجزیه و تحلیل فعالیت ها و تلفیق داده ها و نیز مکانیابی استقرار آنها قابل مطالعه هستند. اکثر تحقیقات در مورد سیستمهای نظارتی بر روی موارد اولیه متمرکز شده و عمدتا مورد مکانیابی را نادیده گرفته اند (18). پژوهش Pavlidis و همکاران یک استثنا است، آنها در یک سیستم تجزیه و تحلیل گسترده تر مسأله استقرار دوربین ها را مورد بحث قرار داده و تجهیزات را با استفاده از استدلال ad hoc مستقر نمودند (17). Erdem و Sclaroff قابلیت های دوربین ها، نظیر میدان دید، تفکیک مکانی و عمق میدان، و محدودیت های هزینه را در فرایند استقرار دوربین ها را در نظر گرفتند (10). آنها راه حل این مشکل را با استفاده از بهینه سازی دودویی به عنوان یک مسئله فضایی گسسته یافتند. هدف اصلی مکانیابی بهینه دوربین ها تعیین موقعیت ناظر (دوربین) است، تا اشراف بصری کامل بر چشم انداز مورد نظر داشته باشد. Bocca و همکاران در پژوهش خود این هدف را با رویکرد علمی دنبال کرده اند (19). Ercan و همکاران همچنین مکانیابی استقرار دوربین ها در یک شهرک مسکونی را مورد مطالعه قرار داده اند (20). Bodor و همکاران مکانیابی استقرار دوربین ها را با در نظر گرفتن پارامترهای محدودیت های مالی، محدودیت های فیزیکی و تفاوت بخش های مختلف منطقه از لحاظ اهمیت نظارتی مورد مطالعه قرار دادند (21). Fehr و همکاران مباحث تحلیل سه بعدی و همچنین سنسورهای سه بعدی و اتوماتیک را مورد بررسی قرار داده اند (22). Ghosh به طور مفصل و از زاویه ای جدید به مسأله گالری هنری پرداخته است و راه حل های ارائه شده برای این مسأله را مورد نقد و تحلیل قرار داده و نقاط ضعف و قوت آنها را بیان نموده است (23). یعقوبی و همکاران دریک مقاله مفصل و طی فرایندی سه مرحله ای مدلی برای استقرار بهینه دوربین ها در شهر بندری جده در عربستان سعودی را ارائه داده اند (24)، در مرحله اول از این مدل یک نمودار Voronoi از رد پای^[15] ساختمان ها تولید شد و دوربین ها در لبه های Voronoi قرار گرفتند، سپس در مرحله دوم سطح پوشش از طریق محاسبه محدوده دید بر اساس یک مدل رقومی ارتفاع از منطقه مورد نظر ارزیابی گردید. با توجه به این مقدمه هرچه بهتر انجام گرفتن تعیین مکان این دوربین ها و بهبود پوشش آن ها در سیستم های اطلاعات جغرافیایی به مسئله اصلی این تحقیق تبدیل می شود. به طور کلی آنچه مد نظر این پژوهش است، یافتن راه حلی به منظور انجام عملیات مکان گزینی و بهبود پوشش دوربین ها در دو مرحله می باشد. در مرحله اول اعمال الگوریتم مکانیابی و تخصیص دوربین ها در فضای دو بعدی انجام گیرد و پس از آن خروجی به دست آمده در فضای سه بعدی و به صورت بصری تجزیه و تحلیل گردد، تا به مناسبترین حالت استقرار دوربین ها برای دستیابی به پوشش بهتر دست پیدا کنیم.

روش بررسی

تجزیه و تحلیل محدوده دید

ناحیه تحت پوشش یا قابل مشاهده یک ناظر، محدوده دید آن ناظر را تشکیل می دهد. محدوده قابل مشاهده به سبب ویژگی­های جغرافیایی، مانند ساختمان ها و درختان و همچنین ویژگی های ناظر (دوربین) محدود شده است. چنین ویژگی­هایی شامل ارتفاع نسبی، فاصله عمودی از سطح و قابلیت های ناظر، مانند محدودیت های زاویه افقی و عمودی است. ناحیه قابل مشاهده یک ناظر شبیه مفهوم برد در نظریه مکان مرکزی^[16] می باشد که در آن دید به واسطه حداکثر فاصله موثر محدود می شود. سیستم های اطلاعات جغرافیایی (GIS) برای مشخص کردن محدوده قابل مشاهده یک ناظر، با توجه به توانایی های محاسبات هندسی آنها مفید هستند. محدوده قابل رویت^[17]، منطقه ای قابل رویت از یک نقطه   با مختصات معین  است. یک محدوده قابل رویت  را می­توان به عنوان مجموعه ای از نقاط یا سلول های سطح  تعریف کرد که از   قابل مشاهده می باشند و تا  بخشی از حداکثر فاصله  از نقطه دید ادامه می یابد (25). به زبان ریاضی؛

                   (1)

شکل 1- خط دید و قابلیت دید

Figure 1. Line of sight and viewshed

محاسبه محدوده قابل مشاهده بر روی سطح معمولا بر اساس خط دید است. اگر پاره خط متصل به دو نقطه به صورت واضح در بالای سطح قرار گیرد، دو نقطه به طور متقابل قابل مشاهده می باشند. برای مثال در شکل 1 نقطه  از  قابل مشاهده است، اما غیر قابل مشاهده از نقطه  می باشد. این بدان  دلیل است که پاره خط  بالای سطح قرار دارد، اما  به وسیله سطح قطع  شده است.

1-مکان گزینی دو بعدی استقرار دوربین ها

رتبه بندی تصادفی و از بین بردن همپوشانی (S-ROPE) اساسا یک شیوه ابتکاری (27) مبتنی بر جستجوی حریص و رتبه بندی ساده و از بین بردن همپوشانی^[18] است. تکنیک ROPE ساده با انتخاب ناظر دارای بالاترین رتبه شروع می­شود و سپس کل ناظران در N را که از ناظر با بالاترین رتبه قابل مشاهده می باشند، حذف می کند. این مرحله سپس برای ناظر با بالاترین رتبه بعدی ادامه می یابد، تا زمانی که N به طور کامل تخلیه بشود. شبه کد زیر نشان می دهد که چگونه ROPE می تواند پوشش کامل بصری را با چند ناظر ایجاد بکند:

while () {

            Get with maximum rank i.e.

            Add to

             Remove  from N

} loop

که  در آن  مجموعه ناظران بهینه است. بار محاسباتی تکنیک ROPE بین  و برای هر دو مورد فشرده همپوشانی متقابل است، یعنی یک پوشش کامل بصری از فضای باز توسط یک ناظر و بدون هیچ همپوشانی بین مناظر منحصر به فرد. شکل 2 خروجی روش ROPE را نشان می دهد که بیان کننده موقعیت 13 ناظر مطلوب است، اگر چه در واقع تنها 9 ناظر برای پوشش کامل بصری کافی می باشند.

این مثال یک ضعف کلیدی الگوریتم های نوع جستجوی حریص را نشان می دهد: نتیجه، بستگی به راه حل انتخاب شده در مرحله اول دارد. بنابراین، در حالت خاص، روش ROPE مجموعه ای ناظران را کاهش می دهد هرچند که تضمین پوشش بصری کامل فضای باز ممکن است لزوما با حداقل تعداد ناظران بهینه تحقق نیابد (به عنوان مثال، به شکل 2- ت مراجعه شود). یک تکنیک ساده برای بهبود روش ROPE، پیروی از یک رویکرد تصادفی است که اجازه می دهد تا یک ناظر بالقوه (یا حتی هر ناظر برای یک مورد جامع) انتخاب شده به صورت تصادفی به عنوان اولین راه حل معرفی گردد، نتیجه این کار N مجموعه از ناظران بهینه خواهد بود که از میان آنها کوچکترین مجموعه، مجموعه بهینه ناظران می باشد. شبه کد S-ROPE برای اجرای جامع این روش به شرح زیر است (که  در آن  مجموعه ناظران بهینه است):

for each

              Add

              Remove

              while () {

                      Get with maximum rank i.e.

                      Add to

                       Remove  from N

             } loop

} loop

شکل 2- یک فضای باز چند ضلعی. الف- شبکه متراکم از بیش از 20،000 ناظر بالقوه، ب- بزرگترین چند ضلعی قابل مشاهده و منشا آن، ت- 13ناظر مبتنی بر  ROPE(مربع پر شده) و 9 ناظر بهینه صحیح (دایره های توخالی).

Figure 2. An outdoor polygon; a) dense network of more than 20,000 potential observers, b) The largest visible polygon and its origin, c) 13 ROPE-based observers (filled squares) and 9 correct optimal observers (hollow circles)

در نتیجه بار محاسباتی به دامنه بین  و افزایش می یابد. بار محاسباتی می تواند با انتخاب پیشینی ناظران بالقوه که برای تست  ناظران بهینه استفاده می شوند، کاهش داده شود. در بعضی موارد، در واقع عدم پوشش بصری کامل، عمدی است زیرا تنها نظارت بر چند سایت مهم در فضای باز برای ما مهم و در اولویت باشد. در این موارد، مناسب آن است که شبکه را به این مناطق حساس محدود بکنیم. یک محیط کار غنی با اطلاعات GIS گزینه ای ایده آل برای چنین کارهایی است که نیاز به تعامل گرافیکی و ترکیب چندین معیار دارند. بدیهی است، تکنیک S-ROPE همیشه حداقل تعداد ناظران را تضمین نمی کند، اما دارای دو ویژگی مهم است که هنوز این تکنیک را روش ایده آل برای ایجاد یک پوشش کامل بصری قرار داده اند. این دو ویژگی یکی آن است که S-ROPE وابسته به هندسه و توپولوژی فضای باز نیست. و دوم S-ROPE مشکل نابرابری فضایی را از طریق یکی از آزمونهای بی نظیر اتحاد و نابرابری کاهش می دهد. در این تحقیق الگوریتم S-ROPE در محیط GIS و با زبان Python جهت اعمال در منطقه اجرا می شود.

2-بازسازی مدل سه بعدی شهری و بهینه سازی پوشش دوربین ها

هر دوی مدل GIS و سه بعدی منطقه مورد مطالعه باید قبل از طراحی سیستم نظارت تصویری ایجاد شوند. جهت دستیابی به بهترین نتایج از لحاظ مکان نصب یا استقرار دوربین های مدار بسته و نیز تحرک بدون محدودیت انها، نیاز به مدل سه بعدی شهری از مناطق نظارت شده و کل منظره شهر است. هنگامی که اشیا یا مناطق در فضای باز تحت نظارت قرار می­گیرند، اشیاء متحرک در ناحیه تحت نظارت ممکن است بخشی از نمای  آنها را مهار کنند (26). نقاط کور می تواند در پشت اشیا تشکیل شود. ناحیه کور نامناسب، امنیت سیستم را تهدید می کند. ابعاد هندسی اشیا، فاصله و ارتفاع بین اشیا و دوربین ها و سطح زمین دارای نوسان، عوامل عمده ای برای تعیین اندازه و توزیع نقاط کور هستند. به همین دلیل لازم است هنگامی که یک مدل سه بعدی شهری تولید می شود، ملاحظات سطح زمین به منظور نمایش واقعی از چشم انداز و محاسبه نقاط کور مورد توجه قرار داده شود (شکل 3). بدیهی است که یک ساختمان در یک شهر همواره دارای ارتفاع یکسان است. از این رو، مدل رقومی ارتفاع (DEM)  این منطقه، با ارتفاع مرز پایین ساختمان، اصلاح می شود. خود تهیه مدل سه بعدی شهری نیز می تواند به روشهای مختلفی صورت بگیرد، اما معمولا نهادهای مربوط این لایه ها را با دقت بالا در اختیار دارند و پژوهشگر می تواند با مراجعه به آنها دریافت نماید. در این تحقیق مدل سه بعدی در نرم افزار City Engine شبیه سازی می گردد و به وسیله آن پوشش دوربین ها بهبود می یابند.

شکل 3- اگرچه در فضای دو بعدی کل منطقه پوشش داده شده است اما در فضای سه بعدی پوشش کامل به شمار نمی رود (26)

Figure 3. Although it is covered in the 2D space of the entire area, it is not considered to be full coverage in 3D

مدل مفهومی تحقیق

در شکل 4 مدل مفهومی تحقیق ملاحظه می شود که شامل تهیه اطلاعات محدوده شهری مورد نظر هم به صورت دو بعدی و هم سه بعدی می باشد. در مدل دو بعدی به کمک زبان Python و نرم افزار ArcGIS فرآیند الگوریتم بهبودیافته S-ROPE اجرا می شود، که محل و تعداد دوربین ها را به عنوان ورودی دریافت می نماید. این الگوریتم به عنوان خروجی موقعیت دوربین ها را برای دستیابی به پوشش مناسب ارائه می دهد. در مدل سه بعدی با استفاده از نرم افزار City Engine و با سعی و خطا محدوده پوشش بهبود یافته و در صورت لزوم تعداد دوربین ها افزایش می یابد.

شکل 4- مدل مفهومی تحقیق

Figure 4. Conceptual model of the research

یافته ها

در این پژوهش از ابتدا منطقه شهری و به طور خاص شهر تهران به عنوان منطقه مورد مطالعه انتخاب گردید (شکل 5). محدوده تحت بررسی بخش کوچکی از منطقه 11 شهر تهران می باشد. لایه های عرصه و اعیان، شبکه راه ها و همچنین ارتفاع ساختمان مربوط به این منطقه از سازمان نقشه برداری کشور تهیه گردید و به منظور اجرای الگوریتم شرح داده شده، در این پژوهش مورد استفاده قرار گرفت. جهت ساده سازی روش کار الگوریتم S-ROPE، شکل 6- الف را در نظر بگیرید که با یک شبکه منظم به طور مساوی به خانه هایی تقسیم شده است. اندازه هریک از خانه های این شبکه به طور مستقیم به مقدار برد دوربین بستگی دارد. جهت شرح مفهوم نقاط کور، اندازه خانه ها اندکی بزرگتر فرض شده اند تا نقاط کور (نقاطی که به وسیله هیچ دوربین شبکه دیده نمی شوند) در آن ایجاد شوند و سپس خواننده با مفهوم و نحوه ایجاد آنها آشنا شود، لیکن در نهایت این خلأ پر و اصلاح می گردد. بنابراین فرض شده است که دوربین ها میدان دایره ای شکل با شعاع 40 متر را دارند.

شکل 5- منطقه مورد مطالعه

Figure 5. The case study

                                      الف                                                                                     ب

شکل 6- تصویر شماتیک از اعمال شبکه بندی اولیه الگوریتم S-ROPE ، الف- قرار دادن دوربین در هر تقاطع شبکه؛ ب- قرار دادن دوربین در مرکز هر خانه برای جلوگیری از حدوث نقطه کور در پوشش تصویری

Figure 6. A schematic illustration of the primitive gridding operations by the S-ROPE algorithm, a) placing the camera at each intersection of the grid; b) Place the camera at the center of each home to prevent the blind spot from appearing in the area

الگوریتم S-ROPE برای تهیه شبکه دوربین هایی با این ویژگی در ابتدا شبکه منظم بر روی منطقه ایجاد می کند که در آن هر تقاطع مکان یک دوربین فرض می شود. به دلیل آن که از ابتدا، شبکه بندی منطبق با محاسبات الگوریتم S-ROPE نمی باشد، دایره های اتحاد دایره های ایجاد شده کل منطقه مورد نظر را پوشش نمی دهد، در حالی که در اصل باید شبکه بندی طوری صورت گیرد که اتحاد این دایره ها کل منطقه را تحت پوشش قرار دهد. همان گونه که گفته شد، این خطا به طور عمدی ایجاد شد تا خواننده به طور ملموس مفهوم نقطه کور را درک نماید. مطابق تحلیل ها قرار دادن دوربین هایی با زاویه دید 360 درجه و شعاع دید 40 متر در تقاطعات یک شبکه بندی مشابه شکل 6-الف نمی تواند کل منطقه مورد نظر را پوشش دهد و  لاجرم برای حذف این نقاط کور می بایست در مرکز هر خانه نیز دوربینی مستقر گردد تا خلأ موجود را پر نماید (شکل 6-ب).

در حالت معمولی الگوریتم S-ROPE آن گونه که در تصاویر بالا نیز دیده شد، متناسب با ویژگی دوربین از لحاظ زاویه و محدوده دید، شبکه ای را بر منطقه مورد نظر اعمال می کند، نقاط استقرار دوربین ها را در تقاطعات این شبکه فرض می­کند و سپس با حذف دوربین های اضافی که تنها همپوشانی را به وجود می آورند، دوربین هایی را که وجود انها ضروری می­باشد، ابقا می کند. اما بنابر آنچه گفته شد، این الگوریتم در حالت پیش فرض منطقه را دو بعدی در نظر می گیرد، زاویه دید را 360 درجه متصور می شود و محدوده دید را کاملا دودویی در نظر می گیرد.

شکل 7- مشاهده محدوده دید زاویه ای هر دوربین. محدوده دید غیر باینری تلقی گردید و  بر همین اساس نقاطی که خارج از محدوده دید دوربین دیده می شوند نیز به دلیل غیر باینری بودن دید در واقع در پوشش شبکه هستند.

Figure 7. Viewing angle of each camera. The range of non-binary viewing is considered, and accordingly, points that are outside the camera's viewing area are also due to non-binary visibility in the network coverage.

مکان بهینه دوربین ها در خروجی این الگوریتم ممکن است وسط خیابان، بر روی سقف خانه و سایر اماکنی که امکان نصب دوربین در آنها وجود ندارد، انتخاب بشود. لذا خروجی آن باید متناسب با شرایط و قابلیت های منطقه تحت نظر تعدیل گردد و با دستکاری مکان دوربین ها به صورت مکرر از وضعیت حداکثری پوشش باید اطمینان حاصل شود. البته گرچه می توان تنها محدوده فضای باز (بدون ساختمان ها) را به عنوان منطقه مور نظر به الگوریتم معرفی کرد که در این صورت شبکه تنها در درون این منطقه شکل می گیرد و کمتر به دستکاری نیاز است، اما این امر تبعات منفی دیگری را در پی دارد که باعث شد ما کل منطقه را بر جزئی از آن ترجیح بدهیم. لذا وارد کردن تعدیلاتی بر الگوریتم S-ROPE ضروری می نمود. که مهمترین این تغییرات زوایه ای بودن دید دوربین و برد 80 متری و غیر باینری است (شکل7). نتیجه شکل 7 پس از اعمال این تغییرات و نوشتن کد آن در زبان برنامه نویسی پایتون و ویرایش خروجی ها به دست آمده است.

محیط واقعی شهری یک محیط سه بعدی است و نمی توان با برخورد دو بعدی با آن تجزیه و تحلیل بهینه ای انجام داد. به ویژه در حالتی که کاربرد ما نصب دوربین ها باشد که در آن نگاه سه بعدی به محیط نه تنها مطلوب بلکه ضروری است. نرم افزار CityEngine یک نرم افزار سه بعدی است که برای طراحی شهری استفاده می شود. این برنامه همچنین عمل مدلسازی را انجام داده و در واقع برای برنامه ریزی و طراحی فضاهای شهری به کار می رود.  این نرم افزار امکان طراحی نماها، راه ها و مسیرهای شهری و بلوک های شهر را میسر می سازد. این نرم افزار امکان سه بعدی کردن اطلاعات GIS را به ما می دهد. پس از آن که فرایند اجرای الگوریتم S-ROPE در فضای دو بعدی تمام شد، لایه GIS ای منطقه مورد مطالعه وارد نرم افزار CityEngine گردید و به صورت نمای سه بعدی مدلسازی شد و پس از آن مکان دوربین های تعیین شده بر روی لایه سه بعدی قرار گرفت و با تغیر زاویه دید عمودی و افقی هر دوربین پوشش کامل دوربین ها از لحاظ سه بعدی تجزیه و تحلیل شد، تا این که حد اکثر پوشش محقق گردید و خروجی نهایی به صورت شکل 8 حاصل شد.

شکل 8-  نمای سه بعدی استقرار دوربین ها، دوربین های اضافه شده با رنگ قرمز مشخص شده اند

Figure 8. 3D camera coverage deployment. Added cameras are marked in red

کل مساحت منطقه مورد مطالعه که نیاز به آن دارد تا به واسطه دوربین ها مانیتور گردد برابر با 98/1953 متر مربع می باشد، این سطوح در واقع فضای خالی بین ساختمان­ها می باشد. پس از اجرای الگوریتم S-ROPE گرچه، خروجی الگوریتم گویای این بود که تمام منطقه مد نظر تحت پوشش دوربین ها قرار گرفته است، منتها به علت پایه دو بعدی آن، نمی تواند پوشش 100 درصدی را تضمین کند و بنابراین پس از بررسی سه بعدی ملاحظه گردید که به واسطه الگوریتم S-ROPE  28/1798 متر مربع از منطقه مورد مطالعه تحت پوشش دوربین ها قرار گرفته است و هنوز 69/155 خارج از دید دوربین ها می باشد که با افزودن بعد سوم ارتفاع به داده­های منطقه این خلأ نیز برداشته شد و تعداد دو دوربین اضافه گردید. ارزیابی روش ها در جدول 1 مشاهده می شود.

جدول 1- ارزیابی روش های به کارگرفته شده برای تعیین تعداد و محل استقرار دوربین های مدار بسته

Table 1. Evaluation of methods used to determine the number and location of CCTV cameras

بحث و نتیجه گیری

در این تحقیق به مسئله پوشش دوربین های مداربسته در فضای شهری به کمک GIS و مدلسازی سه بعدی پرداخته شد. مهمترین دستاورد تحقیق آن است که نشان داده ایم چگونه با اندکی دخل و تصرف در الگوریتم S-ROPE جهت انطباق بیشتر آن با واقعیات زمینی، می توان نتایج قابل قبولی از ان به دست آورد. با روش پیشنهادی اولاً در تعداد دوربین های به کار رفته به تعداد قابل توجهی صرفه جویی صورت می پذیرد و در عین حال بیشترین پوشش ممکن نیز به دست خواهد آمد.تنها چالش پیش رو زمان اجرای فرآیند برای مساحت های بزرگ می باشد که با توجه به غیر آنی بودن ماهیت مسئله، خللی در روش پیشنهادی ایجاد نمی کند. حالت پیش فرض این الگوریتم زاویه دید 360 درجه و محدوده حساسیت کاملا دودویی است، در حالی که در واقع هرگز این گونه نیست و تقریبا تمام دوربین های استفاده شده در جهت نظات بصری از دید زاویه ای برخوردارند. در نتیجه لازم بود تا این مورد تعدیل گردد. همچنین محدوده دید باینری در حالت دوربین های تصویر برداری مصداق پیدا نمی کند و دید دوربین ها با افزایش فاصله کاهش می یابد و یا به وسیله مانعی در محیط محدود می گردد. با لحاظ کردن این دو پارامتر S-ROPE برای شرایط واقعی تری تعدیل گردید. جهت بررسی سه بعدی خروجی به دست آمده از نرم افزار پر قدرت مدلسازی سه بعدی شرکت ESRI یعنی CityEngine استفاده شد و با تغییر در زاویه هر یک از دوربین ها تا رسیدن به حالت پوشش کامل به یک حد اکثری از پوشش دست یافته ایم. ضروری نبود تا حتما محدوده های دید دوربین ها با یکدیگر همپوشانی داشته باشند و یا به طور بلافصل در مجاورت همدیگر قرار گیرند، چراکه دید باینری برای الگوریتم تعریف گردید و هر نقطه از فضا در میدان دید دوربینی قرار دارد. مدت زمان اجرای این الگوریتم بر حسب مقیاس منطقه تحت مطالعه متفاوت می باشد، در این مطالعه که به دنبال اهداف پژوهشی می باشد، منطقه نسبتا کم وسعتی انتخاب گردید تا در زمان و هزینه صرفه جویی صورت گیرد و اجرا نیز به مثابه یک نمونه کوچک و به راحتی قابل فهم تلقی گردد. اما مکانیابی دوربین ها در فضای باز معمولا مقیاس های فراتری از قبیل بلوک، محله یا ناحیه از یک شهر و شاید بیشتر را شامل می شود. بزرگی مقیاس از یک طرف و اصل وقت گیر بودن پردازش کدهای سنگین از طرف دیگر، زمان اجرای این روش را می افزاید. تبعا اجرای روش اعمال شده در این پژوهش برای محیط های شهری نیازمند رایانه هایی با قدرت پردازشی بالا می باشد، چراکه ممکن در حالتهایی چندین روز به طول بیانجامد تا رایانه پس از پردازش خروجی نهایی را ارائه کند. طبق نتایج این تحقیق تقریبا به ازای هر 1500 متر مربع مساحت نیاز به 15 دقیقه برای اجرای مدل داریم. البته در مساحت های بزرگتر این رقم حتی می تواند به کمتر از نصف کاهش یابد.

Reference

1. Ratcliffe, J.H., Taniguchi, T., Taylor, R.B., 2009. The Crime Reduction Effects of Public CCTV Cameras: A Multi-Method Spatial Approach. Justice Quarterly, Vol. 26, pp. 4746-770.
2. Jalali, G., Pirhouri, H., 2016. Developing smart city strategies from a passive defense perspective using SWOT analysis with an emphasis on transportation. First International Conference on Urban Economics (with Respectable Economic Approach and Action). Scientific Society of Urban Economics of Iran pp. 899-910, Tehran, Iran(Persian).
3. Welsh, B.C., Farrington, D.P., 2002. Crime prevention effects of closed circuit television: a systematic review. Home Office Research Study Number 252. Home Office, London.
4. Chvatal, V., 1975. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Vol. 18, pp.39-41.
5. Fisk, S., 1999. A Short Proof of Chvatal’s Watchman Theorem. Journal of Combinatorial Theory, Vol. 24, pp. 374-375.
6. Bose, S.P., Toussaint, G., Zhu, B., 1997. Guarding polyhedral terrains. Computational Geometry, Vol. 1, pp. 173–185.
7. Marengoni, M., Draper, B., Hanson, A., Sitaraman, R., 2000. A system to place observers on a polyhedral terrain in polynomial time. Image and Vision Computing, Vol. 18, 773–780.
8. Cole, R., Sharir, M., 1989. Visibility problems for polygedral terrain. Journal of Symbolic Computation, Vol. 17, pp. 11–30.
9. Eidenbenz, S., 2002. Approximation algorithms for terrain guarding. Information Processing Letters, Vol. 82, pp. 99–105.
10. Erdem, U., Sclaroff, S., 2004. Optimal placement of cameras in floorplan to satisfy task requirements and Classical Cameras. Proceedings of the fifth Workshop on Omnidirectional Vision, Camera Networks and Non-Classical Cameras. Prague, Czech Republic.
11. Kazazakis, G., Argyros, A., 2002. Fast positioning of limited-visibility guards for the inspection of 2D Workspaces. Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2843–2848. Lausanne, Switzerland.
12. Floriani, L., Falcidieno, B., Pienovi, C., Allen, D., Nagy, G., 1986. A visibility-based model for terrain features. Proceedings, Second International Symposium on Spatial Data Handling, (pp. 235–250). Seattle, WA, USA.
13. Goodchild, M., Lee, J., 1989. Coverage problems and visibility regions on topographic surfaces. Annals of Operations Research, Vol. 18, pp. 175–186.
14. Lee, J., 1991. Analyses of visibility sites on topographic surfaces. International Journal of Geographical Information Systems, Vol. 5, 413-429.
15. Kim, Y., Rana, S., Wise, S., 2004. Exploring multiple viewshed analysis using terrain features and optimisation techniques. Computers & Geosciences, Vol. 30, pp. 1019–1032.
16. Kaucic, B., Zalik, B., 2004. K-guarding of polyhedral terrain. International Journal of Geographical Information Science, Vol. 18, pp. 709–718.
17. Pavlidis, I., Morellas, V., Tsiamyrtzia, P., Harp, S., 2001. Urban surveillance systems: From the laboratory to the commercial world. Proceedings of the IEEE, pp. 1478–1497.
18. Valera, M., Velastin, S., 2001. Intelligent distributed surveillance systems: A review. IEEE Proceedings Vision, Image and Signal Processing, Vol. 152, pp. 192–204.
19. Bocca, E., Viazzo, S., Longo, F., Mirabelli, G., 2005. Developing data fusion systems devoted to security control in port facilities. In Proceedings of the 2005 Winter Simulation Conference, pp. 445-449. Orlando, FL, USA.
20. Ercan, A., Yang, D., El Gamal, A., Guibas, L., 2006. Optimal placement and selection of camera network nodes for target localization. In Proc. IEEE Int. Conf. Distributed Computing in Sensor System, 2006, vol. 4026, pp. 389–404.
21. Bodor, R., Drenner, A., Schrater, P., Papanikolopoulos, N., 2007. Optimal camera placement for automated surveillance tasks. Journal of Intelligent and Robotic Systems, Vol. 50, pp. 257–295.
22. Fehr, D., Fiore, L., Papanikolopoulos, N., 2009. Issues and solutions in surveillance camera placement. In Proceedings of 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009), pp. 3780–3785. St. Louis, MO, USA.
23. Ghosh, S., 2010. Approximation algorithms for art gallery problems in polygons. Discrete Applied Mathematics, Vol. 158, pp. 718-722.
24. Yaagoubi, R., El Yarmani, M., Kamel, A., Khemiri, W., 2015. HybVOR: A Voronoi-Based 3D GIS Approach for Camera Surveillance Network Placement. ISPRS International Journal of Geo-Information, Vol. 4, pp. 754-782.
25. de Floriani, L., Magillo, P., 2003. Algorithms for visibility computation on terrains: A survey. Environment and Planning B: Planning and Design, Vol. 30, pp. 709–728.
26. Choi, K., Lee, I., 2015. CCTV coverage index based on surveillance resolution and its evaluation using 3D spatial analysis. Sensors, Vol. 15, pp. 23341-23360.
27. Vahidnia, M.H., Vafaeinejad, A., Shafiei, M., 2019. Heuristic game-theoretic equilibrium establishment with application to task distribution among agents in spatial networks. Journal of Spatial Science, Vol. 64, pp. 131-152.