عنقدة الصور اعتمادا على طريقة كسورية مطورة وتنقيب المخططات == Image Clustering Based on Developed Fractal Method and Graph Mining
Author name:
فراس صبار مفتن
General topic:
Computer Science
Specific topic:
Computer Science
Degree:
Doctorate
University:
University of Babylon - Information Technology Collage - Department Of Software
Language:
English
University location:
Babylon
First pages:
28T777 - p.pdf
Abstract:
تشير عنقدة الصور الى تقسيم الصور الى عدة مجاميع. حيث كل مجموعة تسمى عنقود حيث يحتوي على صور متشابه في الخصائص ولكنها مختلفة عن الصور في العناقيد الاخرى. يمكن تفسر الخصائص الشاملة كميزات احصائية على انها خاصية للصورة تشمل جميع وحدات البكسل المستخدمة لحساب التشابه بين الصور. استخدمت هذه الاطروحة الكسور كخصائص محلية لتمثيل الصورة تستند الى مناطق بارزة في حين تبقى ثابتة لتغير نقطة النظر والاضاءة. تعتبر الكسور شائعه لقدرتها على استخراج ميزة التشابه الذاتي. ولفترة طويلة، استخدم الباحثون الكسور لضغط الصورة. على مدى السنوات الاخيرة، تم تطبيقها في التنقيب على البيانات. لهذه الاطروحة هدفين رئيسيين : اولا لدراسة القدرة على استخراج خصائص التشابه الذاتي من الصور دون استخدام بعد الكسور والذي يعتبر حساس للضوضاء العددية او التجريبية ومقيد بكمية البيانات. وثانيا لبناء الرسم البياني على اساس الميزات المستخرجة وتطور خوارزمية تجميع بالاعتماد على الرسم البياني.وينقسم النظام المقترح الى مرحلتين، بناء مصفوفة التشابه بواسطة طريقة كسورية وخوارزمية تنقيب المخططات. تم تطبيق PIFSلاستخراج ميزات التشابه الذاتي من صورة واحدة فقط. ولكن في هذه الدراسة كيفت PIFS لاستخراج ميزات التشابه الذاتي من العديد من الصور. بسبب ان PIFS تستغرق وقتا طويلا، فقد تم تكييفها للعمل مع تقنيات المطابقة والتقليل، وايضا تم استخدام الدالة الهاش للحد من تعقيد الوقت. واستخدم النظام المقترح مصفوفة تشابه لبناء المخطط ووضع خوارزمية عنقدة شبكية تعتمد على خصائص كسورية التوصيل بين العقد التي تمثل صور.استخدمت عدة بيانات لاختبار النظام المقترح. ولان النظام ينقسم الى مرحلتين، الاولى بناء مصفوفة التشابه والثانية هي خوارزمية تجميع الرسم البياني. لذلك، تم اختبار كل مرحلة بشكل منفصل. في الاول، يتم اختبار بناء مصفوفة التشابه (الميزات المستخرجة) مع خوارزمبة K - means لمعرفة صحة الميزات المستخرجة.وتم اقتراح طرائق لتقليل وقت التنفيذ ومقارنتها مع الطرائق التقليدية. وخفضت دالة الهاش التعقيد من O(m×n) الى O(m logn) بينما قللت المطابقة والتقليل التعقيد الى O(m×n/t) حيث t عدد دوال المطابقة.اما طريقة التجميع البيانية المقترحة تم اختبار صحتها باستخدام البيانات الحقيقية واستخدمت المقاييس النمطية، الموصلية، التغطية، وكثافة الجودة وتم عرض النتائج والتحقق من صحتها من الناحية العددية والبصرية مع عدد عقد المختلفة. وقد اظهرت النتائج التي تم الحصول عليها دقة بين 0.80 و0.99 لجميع المقاييس.واظهرت النتائج ان للكسور قدرة كبيرة على استخراج ميزة التشابه الذاتي لاستخدامها في التنقيب عن الصور مثل التجميع. واعطت خصائص التشابه الذاتي كسورية نتائج جيدة. وان الميزات المستخرجة مشابه الى مصفوفة المجاورة التي يتم استخدامها لتمثيل الرسم البياني. لذلك، تعتبر بنية جيدة لتمثيل الرسم البياني. | Image clustering refers to the division of images into various sets of images. In this regard, each set known as cluster includes images that are similar in features to each other but different those of other sets. The global features as statistical features can be interpreted as a particular property of image involving all pixels were used to calculating similarity among images by most of the researchers. This thesis used fractal features as local features to represent an image based on salient regions while remaining invariant to viewpoint and illumination changes. Fractal is popular because of their ability to extract the self - similarity feature. For a long time, researchers used fractals for image compression. Over the latest years, they have been applied in mining. This thesis has two major purposes, first to studies the ability to extract fractal Self - similarity features from images without using fractal dimension which is sensitive to numerical or empirical noise and limitations in the amount of data. Second to constructs graph based on extracted features and develops graph cluster algorithm.The proposed system is divided into two phases, the Similarity Matrix construction by a fractal method and a Graph Clustering algorithm. Partitioned Iterated Function Systems (PIFS) is applied to extracting Self - similarity features from just one image. This study developed PIFS to extracting Self - similarity features from many of images. Since the PIFS algorithm is time - consuming, it has been adapted to work with Map - Reduce techniques and also hash function was used to reduce the time complexity. The proposed system used similarity matrix to construct a graph structure and developed a graph clustering algorithm based on connectivity fractal features among nodes that represents as images.Each phase was tested Separately. In the first phase, Similarity Matrix construction (features extraction) is tested with K - means clustering algorithm to find out the correct features extracted. The B - Cubed recall and precision are estimated with good results to precision and recall accuracy.Then proposed methods of reducing time complexity results is presented and compared with traditional methods. The hash function reduced the complexity O(m×n) to O(m logn) while Map/reduce technique reduce the complexity O(m×n) to O(m×n/t) for time where t is a number a of map task.The second phase, Graph Clustering algorithm is tested with the real - world graph dataset. The clustering result was evaluated by Modularity, Conductance, Coverage, and Density Quality Metrics and the results were presented and validated both numerically and visually with different nodes number. The obtained results have shown accuracy between 0.80 and 0.99 for all metrics.
