کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6941175 870156 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graph Edit Distance: Moving from global to local structure to solve the graph-matching problem
ترجمه فارسی عنوان
گراف ویرایش فاصله: حرکت از ساختار جهانی به ساختار محلی برای حل مشکل تطبیق گراف
کلمات کلیدی
ترجمه چکیده
رویکردهای گراف کلاسیک برای برنامه های کاربردی تشخیص الگو بر روی محاسبات فاصله ها بین نمودار ها در یک دامنه گراف مشخص استوار است. به عبارت دیگر، فاصله بین دو گراف با به دست آوردن مستقیما بهینه سازی یک تابع هدف، که گره و گره را در نظر می گیرد، به دست می آید. تطبیق گراف دو طرفه برای اولین بار در سال 2009 منتشر شد و نسخه های جدید به نظر می رسد که سرعت آن را افزایش دهند، مانند تطبیق سریع دو طرفه گراف. این الگوریتم بر مبنای تعریف یک ماتریس هزینه بین تمام گره های هر دو گراف و حل متناظر گره از طریق یک روش انتساب خطی است. برای ساخت ماتریس، چندین ساختار محلی را می توان از ساده ترین (تنها گره) تا پیچیده ترین (یک کل یا یک ساختار خاص) تعریف کرد. در این مقاله، هشت گزینه مختلف را پیشنهاد می کنیم و نشان می دهیم که نوع ساختار محلی و فاصله بین این سازه ها نسبت به زمان اجرا و نسبت طبقه بندی مناسب است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر چشم انداز کامپیوتر و تشخیص الگو
پیش نمایش مقاله
گراف ویرایش فاصله: حرکت از ساختار جهانی به ساختار محلی برای حل مشکل تطبیق گراف
چکیده انگلیسی
Classical graph approaches for pattern recognition applications rely on computing distances between graphs in a certain graph domain. That is, the distance between two graphs is obtained by directly optimising some objective function, which consider node and edge attributes. Bipartite Graph Matching was first published in a journal in 2009 and new versions have appeared to speed up its runtime such as the Fast Bipartite Graph Matching. This algorithm is based on defining a cost matrix between the whole nodes of both graphs and solving the node correspondence through a linear assignment method. To construct the matrix, several local structures can be defined from the simplest one (only the node) to the most complex (a whole clique or eigenvector structure). In this paper, we propose eight different options and we show that the type of local structure and the distance defined between these structures is relevant for the runtime and classification ratio.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Pattern Recognition Letters - Volume 65, 1 November 2015, Pages 204-210
نویسندگان
, ,