ویرگول
ورودثبت نام
ماهان فتحی
ماهان فتحی
خواندن ۹ دقیقه·۶ سال پیش

جمع‌آوری نقاط مهم کل نقشه‌ی ایران: یک مساله‌ی کامپیوتر ویژن؟

بلد، نقشه و مسیریاب ایرانی، یکی از محصولات شرکت کافه‌بازار است که با سرعت زیادی در حال پیشرفت است. ما روزانه با مسائل داده‌ای پیچیده‌ای مثل جمع‌آوری و دسته‌بندی داده‌ها (Aggregation)، جست‌و‌جوی هوشمند (Information Retrieval)، بررسی رفتار (Behavior Monitoring) و بهینه‌سازی در گراف‌ها روبه‌رو می‌شویم. بلد قابلیت‌های جذاب زیادی دارد، و خیلی اجمالی می‌شود به مسیریابی، پیش‌بینی ترافیک، پیشنهاد راه‌های مختلف سفر در شهر، جستجو در نقشه، و به طور کلی ارائهٔ مکان‌های منتخب نقشه، اشاره کرد. من یک دانشمند داده در تیم جمع‌آوری این مکان‌های منتخب (Points of Interest) هستم. منظور از این مکان‌ها، همه‌ی بنگاه‌های اقتصادی یا دولتی، مثل رستوران‌ها، کلینیک پزشکان، ایستگاه‌های مترو، باجه‌های تلفن یا حتی یک کلیدسازی محلی هست. وظیفه‌ی اصلی تیم ما این است که از هیچ کدام از این مکان‌ها ساده نگذریم و تا می‌توانیم آن‌ها را در پایگاه دادهٔ نقشه بگنجانیم. متاسفانه این کار در ایران هیچ‌وقت به طور سازمان‌یافته و با به خرج دادن وسواس لازم انجام نشده است. سرویس‌هایی مثل گوگل مپس (Google Maps) و ویز (Waze) هم که در ایران محبوبیت زیادی دارند، فقط توانسته‌اند بخش کوچکی از این مکان‌ها را جمع‌آوری کنند. شاید فکر کنید کمی بلند پروازانه ا‌ست که هدفمان، جمع آوری همه‌ٔ این مکان‌ها باشد، ولی غافلگیر می‌شوید وقتی بدانید چقدر این مساله برای ما مهم است و ما چقدر برایش وقت گذاشته‌ایم، و بنابراین هدفمان هم آنقدرها بی‌راه نیست.


محصول ما، بلد!
محصول ما، بلد!


تیم ما دو ستون اصلی برای رسیدن به هدفش دارد. اولی وانت‌های مجهز به دوربین‌های عکس‌برداری هستن، و دومی هم اپراتورها که وظیفهٔ وارد کردن اطلاعات این عکس‌ها در پایگاه داده را دارند. این وانت‌ها، با داشتن همه‌ی مجوزهای قانونی، یک مسیر بهینه برای عکس‌برداری از تمام خیابان‌ها و راه‌های شهر را طی می‌کنند، و با فریم‌ریت بالا و زاویه دید کامل ۳۶۰ درجه از تمام شهر (و نه از قسمت‌هایی که عکس‌برداری از آن‌ها ممنوع است) عکس‌برداری می‌کنند. اپراتورهای ما هم موازی این عکس‌ها را تگ می‌زنند و به ما خبر می‌دهند که چه مکان‌های منتخبی در عکس‌هایی که زیر دستشان می‌آید می‌بینند. وظیفه‌ی من به عنوان دانشمند داده‌ی تیم، این است که این فرآیند را برای اپراتورها تسهیل کنم و سرعت وارد کردن اطلاعات را بالا ببرم. مسیر من برای این کار، این است که با استفاده از روش‌های هوشمند در علم بینش کامپیوتر، این مکان‌های منتخب را از پیش در عکس‌ها تشخیص دهم.


نمونه عکس‌های وانت!
نمونه عکس‌های وانت!


اما این چطور به اپراتورها کمک می‌کند؟ بد نیست که آماری از عکس‌های گرفته شده توسط وانت‌ها ارائه کنم. ما تقریبا در دو سوم از عکس‌ها هیچ مکان منتخبی نداریم، بنابراین اگر بتوانیم عکس‌هایی که اطلاعات ارزشمندی در آن‌ها نیست را از اول دور بریزیم، می‌توانیم وقتی که قبلاً اپراتورها برای بررسی این عکس‌ها صرف می‌کردند را برای وارد کردن اطلاعات عکس‌های مهم ذخیره کنیم. طبق آمارمان، این کار سرعت اپراتورها را ۲ تا ۳ برابر بیشتر می‌کند. برای این کار، می‌توانیم برای تشخیص مکان‌های منتخب، تابلوهای این بنگاه‌ها را در نظر بگیریم. به این معنی که در الگوریتم تشخیص این مکان‌ها (Object Detection) کافی است تابلوهایشان را تشخیص دهیم. از آنجا که عکس‌برداری با فریم‌ریت نسبتاً بالایی انجام می‌شود، ممکن است یک تابلو در دو یا سه عکس پشت سر هم (یا حتی بیشتر!) تکرار شود. این تابلوی یکسان، توسط الگوریتم ما در همه‌ی این عکس‌ها تشخیص داده می‌شود و ممکن است سه بار زیر دست اپراتورهای ما برود. بنابراین اگر بتوانیم تابلو‌های مشابه را در عکس‌های متوالی تشخیص دهیم، می‌توانیم دوباره این فرآیند را ۲ تا ۳ برابر سریع‌تر بکنیم و از وارد کردن اطلاعات بی‌مورد و تکراری جلوگیری کنیم. به الگوریتمی که برای این بخش استفاده می‌کنیم با اسم ترکینگ (Tracking) اشاره می‌کنیم.

برای فاز اول پروژه، که تشخیص تابلوهاست، از اپراتورها خواستیم تا برای تعداد نسبتاً زیادی از عکس‌ها، دور تمام تابلو‌هایی که برایمان مهم هستند، یک مستطیل (باکس) بکشند تا بتوانیم برای فاز یادگیری شبکه از آن‌ها استفاده کنیم. برای این کار الگوریتم‌های Object Detection زیادی را امتحان کردیم. YOLO و R-CNN دو تا از اصلی‌ترین این روش‌ها هستند. اینجا سعی نمی‌کنم برتری‌ها و نقص‌ها این روش‌ها را توضیح دهم، اما توضیح می‌دهم که چرا سمت R-CNNها رفتیم و آن‌ها را انتخاب کردیم. اولین دلیلش این بود که طبق تجربه‌‌ای که با YOLO داشتیم، خروجی، چه برای تشخیص تابلو‌ها، و چه برای دقت باکس‌هایی که الگوریتم برای تابلو‌ها برمی‌گرداند، دقت پایین‌تری داشت. دلیلش هم می‌تواند این باشد که دیتای ما، چه در ماهیت عکس‌های داخل شهری‌ای که می‌گیریم، چه باکس‌هایی که اپراتورها برای تابلوها می‌کشند، نویز زیادی دارد؛ و از آنجا که YOLO مساله‌ی Object Detection را یک مساله‌ی رگرسیون (Regression Problem) می‌بیند، این نویز می‌تواند روی این الگوریتم اثر مخربی داشته باشد. یک خاصیت مهم Mask R-CNN این است که مساله‌ی Data Hunger را تا حد خوبی حل کرده است، به این معنی که به تعداد کمی نمونه‌ی مثبت برای تعمیمش به باقی دیتا نیاز دارد، و به همین دلیل نسبت به این دسته از نویزها مقاوم است. بنابراین Faster R-CNN را به عنوان الگوریتم نهایی انتخاب کردیم. برای این کار این پیاده‌سازی از ‌Mask R-CNN را، با حذف قسمت‌هایی که وظیفه‌ی برگرداندن یک ماسک برای ابجکت‌ها را داشت، تبدیل به یک نسخه‌ی قوی‌تر از Faster R-CNN کردیم. اینطوری توانستیم از بهبودهایی که Mask R-CNN نسبت به Faster R-CNN داشت، که آن‌ها را مدیون به کارگیری از Feature Pyramid Network و RoI Align است، استفاده کنیم. بعدها به دلیل مشکلات پرفورمنسی و سرعت، از این پیاده‌سازی Keras و TensorFlow، به PyTorch مهاجرت کردیم، که باید اعتراف کنم خیلی بهتر بود.

حالا که مساله‌ی تشخیص را توانستیم با دقت خوبی حل کنیم، قدم بعدی این است که الگوریتم ترکینگ را بسازیم. راه اول ما برای ترکینگ، کراپ کردن نواحی تشخیص داده شده، استخراج فیچرها با استفاده از فید کردن این عکس‌ها به Backbone شبکه‌ی تشخیص، و مقایسه‌ی این فیچرها با هم بود. توقع داشتیم تابلوهای یکسان، بتوانند در فضای فیچر نزدیک به هم بمانند و بتوانیم با بدست آوردن یک متریک شباهت (‌Similarity Metric) جفت‌هایی که از حدی شبیه‌تر به هم بودند را به عنوان یک تابلو تشخیص دهیم. برای تست این فرضیه، اولین کاری که کردیم بدست آوردن نمایش t-SNE این فیچر‌ها بود. نتایج در این بخش به ما این امید را داد که فرضیه‌ی قابل اعتمادی داریم و می‌شود با تنظیم متریک شباهت به یک الگوریتم خوب رسید. علیٰ‌رغم وقت زیادی که برای این‌کار گذاشتیم، نتیجه‌ی خیلی خوبی نگرفتیم. برای مثال، تابلویی که در دو عکس متوالی تکرار می‌شد، ممکن بود تابلوی دیگری (اما با شباهت بالا) در عکس دوم را، به عنوان نزدیک‌ترین تابلو به خودش تشخیص بدهد. این موضوع را می‌شود ناشی از دو دلیل دانست: یک اینکه شبکه هنوز نسبت به محتوای متنی تابلوها حساس نشده و با استفاده از فیچر‌های دیگری مساله‌ی تشخیص را حل می‌کند، و دوم اینکه متریک شباهت هنوز نقص‌هایی دارد و کامل نیست. برای اصرار به حل این مساله با استفاده از روش شباهت، می‌توانستیم برای افزایش حساسیت شبکه به محتوای متنی و فیچر‌های مرتبط‌تر، مشغول آموزش (Train) یک شبکه‌ی Siamese بشویم؛ اما در عوض کار هوشمندانه‌تری کردیم، که نتیجه‌ی خیلی خوبی داشت.


نمایش t-SNE تابلو‌های تشخیص داده شده!
نمایش t-SNE تابلو‌های تشخیص داده شده!


به این توجه کردیم که مکان تابلو‌های تشخیص داده شده در عکس‌ها، اطلاعات خیلی ارزشمندی هستند و دخیل کردن آن‌ها در محاسباتمان می‌تواند خیلی مفید باشد. در حال حاضر الگوریتم ترکینگ ما بر این پایه است که اگر موقعیت یک جفت از باکس‌ها، در دو عکس متوالی نسبت به هم حفظ شود، جدا از محتوای باکس‌ها، احتمال زیادی برای یکسان بودن این باکس‌ها برمی‌گردانیم. برای مثال یک دسته از باکس‌های کنار هم (مثلاً تابلوهای یک ساختمان پزشکان) را در نظر بگیرید؛ می‌توانیم تصور کنیم که این الگو در عکس دوم عیناً (البته با کمی تخفیف) تکرار می‌شود، و این دقیقاً مبنای الگوریتم ترکینگ ما خواهد بود. باید به این نکته اشاره کرد که لازم است این جفت از باکس‌ها در فاصله‌ی یکسان از دوربین باشند، چراکه آبجکت‌هایی که نزدیک‌تر به دوربین هستند، در عکس دوم فاصله بیشتری را پیمایش می‌کنند و برعکس. این تفاوت عمق هم در الگوریتم دیده شده و در نظر گرفته می‌شود. در بخش‌های بعدی سعی می‌کنم پیاده‌سازی ریاضی این فرضیات را بیان کنم.


یک نمونه از دو عکس متوالی که در آن‌ها تابلو‌ها تکرار می‌شوند!
یک نمونه از دو عکس متوالی که در آن‌ها تابلو‌ها تکرار می‌شوند!


برای نام‌گذاری، باکس‌های ?₁ و ?₁ را در عکس اول، که در آن‌ها کلاً به تعداد ?₁ تا تشخیص موفق وجود دارد را در نظر بگیرید؛ ?₂، ?₂ و ?₂ هم متعلق به عکس دوم هستند. در مرحله‌ی اول یک ماتریس با سایز (?₁، ?₂، 2) می‌سازیم که از ?₁×?₂ بردار دو بعدی (x و y) تشکیل شده‌است. هر کدام از این بردارها وظیفه‌ی انتقال مختصات مرکز یک باکس از تصویر اول به مرکز یک باکس در تصویر دوم را دارد. با ایتریت (Iterate) کردن روی این بردار‌ها و برداشتن یک بردار جابه‌جایی در هر دور، تمامی باکس‌های تصویر اول را با این بردار جابه‌جا می‌کنیم؛ بنابراین در ایتریشن ?₁×?₂، مرکز باکس‌های ?₁ و ?₂ روی هم هستند و باقی باکس‌های تصویر اول هم به همین میزان جابه‌جا شده‌اند. برای باکس‌های جابه‌جا شده‌ی تصویر اول، و باکس‌های دست نخورده‌ی تصویر دوم، در هر ایتریشن یک ماتریس دیگر با سایز (?₁، ?₂) می‌سازیم که هر درایه‌اش به ما می‌گوید باکس‌ها چقدر با هم اشتراک (Intersection over Union یا به اختصار IoU) داشته‌اند؛ برای مثال درایه‌ی (?₁، ?₂) نشان‌دهنده‌ی IoU ی باکس جابه‌جا شده‌ی ?₁ از عکس اول و باکس ?₂ از عکس دوم است. می‌شود تمام این ماتریس‌ها را تبدیل به یک ماتریس چهار بعدی با سایز (?₁، ?₂، ?₁، ?₂) کرد که در آن درایه‌ی (?₁‌، ?₂، ?₁، ?₂) نشان‌دهنده‌ی IoU باکس ?₁ از تصویر اول که با بردار ?₁ → ?₂ جابه‌جا شده، و باکس ?₂ از تصویر دوم است. این ماتریس را Ψ نام‌گذاری می‌کنیم. ببخشید که این قسمت کمی خسته‌کننده بود!


باکس‌های تشخیص داده شده در دو تصویر قبلی!
باکس‌های تشخیص داده شده در دو تصویر قبلی!
هر فریم نشان‌دهنده‌ی یک ایتریشن است!
هر فریم نشان‌دهنده‌ی یک ایتریشن است!


حالا می‌شود مبنای الگوریتم را به ریاضی اینطور بیان کرد که، اگر در اثر جابه‌جایی ?₁ → ?₂، باکس‌های ?₁ و ?₂ اشتراک زیادی دارند، و در قرینه، در اثر جابه‌جایی ?₁ → ?₂، باکس‌های ?₁ و ?₂ هم اشتراک زیادی دارند، احتمال زیادی برای مچ شدن باکس‌های ?₁ و ?₂، و باکس‌های ?₁ و ?₂ در نظر می‌گیریم. در ادامه توضیح می‌دهم که چطور می‌توان این احتمال را از ماتریس Ψ بدست آورد. از ماتریس Ψ، ماتریس Ψᵀ را بدست میاوریم که "جفت ترانهاده"ی Ψ هست؛ بدین معنی که جای محور‌های اول و دومش را با محور‌های سوم و چهارمش عوض می‌کنیم. این دو ماتریس سایز‌های یکسانی دارند و می‌توانیم آن‌ها را در هم ضرب درایه‌ای کنیم و ماتریس Φ را تشکیل دهیم. برای ارضای شرط مچ شدن دو جفت از باکس‌ها کافی است درایه‌ی (?₁‌، ?₂، ?₁، ?₂) از Φ از یک حد مشخص بزرگتر باشد. به همین سادگی.

در ادامه برای بدست آوردن یک احتمال یک‌به‌یک برای مچ شدن هر کدام از باکس‌های تصویر اول به دوم، می‌شود از دو بعد آخر ماتریس Φ (یا دو بعد اول، چون ماتریس نسبت به این جفت بعد قرینه‌ست) ماکسیمم گرفت. حالا می‌توانیم این احتمال‌ها را کنار احتمالاتی که با روش تشابه بدست آوردیم قرار دهیم تا به یک احتمال جامع‌تر برسیم. در نهایت برای مچ یک‌به‌یک تابلو‌ها از الگوریتم Hungarian استفاده می‌کنیم که یک مچینگ بهینه (با بیشترین احتمال) را برمی‌گرداند. و در آخر الگوریتم ترکینگ ما کامل می‌شود.

برای این که به طور رسمی این الگوریتم را روی پروداکشن ببریم، سرویسی بالا آوردیم که به سرور وصل می‌شود و داده‌ها را دریافت می‌کند. در اجرا هم با استفاده از یک کلاستر GPU، باکس‌ها را تشخیص می‌دهد، روی هر دو عکس متوالی الگوریتم ترکینگ را اجرا می‌کند و نتایج را روی پایگاه داده می‌نویسد. در نهایت اپراتورها می‌توانند با دیدن یک تابلو، اطلاعاتش را وارد کنند و ماموریت ما تمام می‌شود!


این یک نمونه از چالش‌ها و مسايلی بود که در کوتاه مدت با آن‌ها روبه‌برو هستیم و امیدوارم با خواندن این مقاله ایده‌ی بهتری درباره‌ی فضای کاری شرکتمان داشته باشید. در آینده امیدواریم بتوانیم سمت کارهایی مثل تشخیص اتوماتیک کتگوری بنگاه‌ها، و توسعه و به کار گیری OCRهای فارسی برویم. در ضمن می‌توانید یک نسخه‌ی انگلیسی از این مقاله را در بلاگ شخصی خودم و در این آدرس پیدا کنید. ممنون! ✌️

بلدکافه بازاربینایی ماشینیادگیری ماشینیادگیری ژرف
یک دیتا ساینتیست، که قبلا بکند می‌زده، قبلشم مدیریت می‌خونده، قبل اونم مکانیک می‌خونده، قبل اونم فیزیک. github.com/MahanFathi
شاید از این پست‌ها خوشتان بیاید