بایگانی برچسب برای: ازمون یار

مقالات و جزوات آموزشی پیرامون هیستوگرام

,

مقالات

1.بررسی روشهای متعادل سازی هیستوگرام در بهبود تصویر

چکیده: افزایش کنتراست به عنوان یکی از مسائل مهم در پردازش تصویر است.متعادل سازی هیستوگرام (HE) یکی از روش های معمول برای بهبود کنتراست در تصاویر دیجیتال است و یک روش افزایش کنتراست ساده و موثر است با این حال، این روش معمولا باعث کنتراست بیش از حد می شود که باعث ظاهر غیر طبیعی در تصویر پردازش شده می شود. هم چنین HE میانگین روشنایی تصویر را به خوبی حفظ نمی کند بنابراین روش های دیگری برای متعادل سازی تصویر با حفظ روشنایی تصویر ارائه شده است. این مقاله به بررسی فرم های جدید هیستوگرام برای افزایش کنتراست تصویر می پردازد. تفاوت عمده میان روش ها معیارهای مورد استفاده، تقسیم هیستوگرام ورودی است. متعادل سازی دو هیستوگرام با حفظ روشنایی(BBHE) میانگین مقادیر شدت به عنوان نقطه جداسازی استفاده می کند. متعادل سازی دو هیستوگرام با حداقل خطای متوسط روشنایی(MMBEBHE) است. متعادل سازی هیستوگرام متوسط – مجرای بازگشتی(RMSHE) بهبود یافته BBHE است. روش یکنواخت سازی پویلی هیستوگرام با حفظ روشنایی(BPDHE) بسط یافته MPHBP و DHE است.
واژه های کلیدی: بهبود کنتراست، متعادل سازی هیستوگرام، خطای متوسط روشنایی، تقسیم بندی هیستوگرام، حفظ روشنایی
فایل PDF – در 22 صفحه- نویسنده : نوشین الله بخشی

بررسی روشهای متعادل سازی هیستوگرام در بهبود تصویر

رمز فایل : behsanandish.com

2. بهبود کیفیت تصاویر آندوسکوپی از طریق تعدیل هیستوگرام فازی و توزیع ناهمسانگرد کنتراست

چکیده: در این مقاله روشی جدید برای بهبود کیفیت تصاویر آندوسکوپی به وسیله ی تعدیل هیستوگرام فازی و توزیع ناهمسانگرد کنتراست ارائه می شود. تصاویر آندوسکوپی موجود در کشورمان از لحاظ نور و کیفیت وضعیت مناسبی ندارند و همین موضوع تبدیل به چالشی جهت تشخیص انواع بیماری های دستگاه گوارش شده است. برای غلبه بر این مشکلات و کمک به پزشکان برای تشخیص بهتر، در این مقاله یک روش وفقی با استفاده از تعدیل هیستوگرام فازی و توزیع کنتراست ارائه می شود. همچنین در روش پیشنهادی مفهوم جدیدی از توزیع کنتراست بر اساس آنالیز محلی تصاویر آندوسکوپی معرفی می شود. سپس به وسیله انتخاب وفقی پارامتر هدایت که نقشی مهم در توزیع ایفا می کند، توزیع کنتراست به منظور بهبود کیفیت تصاویر آندوسکوپی به تصویر اعمال می شود و در نهایت بعد از انتقال به سه فضای رنگ YIQ ،XYZ و HSI به کمک روش تعدیل هیستوگرام فازی، تغییرات نامحسوس رنگ نمایان تر می شود. نتایج تجربی نشان می دهد که روش ارئه شده عملکرد قابل توجهی در افزایش قابلیت دیداری تصاویر آندوسکوپی از خود نشان می دهد.

 

واژه های کلیدی: تصاویر آندوسکوپی، توزیع ناهمسانگرد کنتراست، تعدیل هیستوگرام فازی

فایل PDF – در 6 صفحه- نویسندگان : حسین قیصری، میرحسین دزفولیان

بررسی روشهای متعادل سازی هیستوگرام در بهبود تصویر

رمز فایل : behsanandish.com

3. تشخیص زود هنگام پوسیدگی دندان با استفاده از آنالیز هیستوگرام و طیف توان

چکیده: این مقاله به تشخیص پوسیدگی در مراحل اولیه با استفاده از آنالیز هیستوگرام و طیف توان می پردازد. داده های مورد نیاز شامل تصاویر اشعه ایکس دندان های نرمال و پوسیده از هر شخص می باشد که توسط ابزار پردازش سیگنال MATLAB آنالیز می شود. برای هر تصویر، هیستوگرام و طیف توان محاسبه می شود. سپس یک بررسی دقیق انجام می گیرد. نتایج نشان می دهد که هیستوگرام شدت پیکسل برای دندان های نرمال و پوسیده در محدوده های مختلف متمرکز شده است و تفاوت های آشکاری در بخش های طیفی بدست آمده بین دندان های نرمال و پوسیده وجود دارد. طیف توان دندان پوسیده در مقایسه با طیف دندان نرمال دارای بخش های فرکانس بالااست. هم چنین به کارگیری GUI(واسط کاربر گرافیکی) این کار را آسان تر و وابسته به تعامل کاربر می کند. این روش برای دندان پزشکان در تشخیص پوسیدگی در مراحل اولیه بسیار سودمند می باشد.

واژه های کلیدی: پوسیدگی دندان، هیستوگرام، طیف توان، GUI، شدت پیکسل

فایل PDF – در 6 صفحه- نویسندگان : محمد کریمی مریدانی، شبنم قهاری و فاطمه غلامی

تشخیص زود هنگام پوسیدگی دندان با استفاده از آنالیز هیستوگرام و طیف توان

رمز فایل : behsanandish.com

4. بازیابی تصاویر چهره با استفاده از ترکیب هیستوگرام گرادیان و الگوی باینری محلی

چکیده: بازیابی چهره، یک موضوع تحقیقاتی مهم در پردازش تصویر است که هدف آن استخراج تصاویر چهره ای است که مشابه با یک تصویر جستار باشند. در این مقاله روشی برای بازیابی تصاویر چهره با استفاده از ترکیب هیستوگرام گرادیان و الگوی باینری محلی(LBP) پیشنهاد شده است. ترکیب این دو روش مقاومت در مقابل تغییرات موجود در تصاویر چهره را افزایش می دهد و در نتیجه عملکرد سیستم را در بازیابی تصاویر بهبود می بخشد. برای افزایش توانایی سیستم، یک طرح فیدبک ارتباطی مبتنی بر ماشین بردار پشتیبان(SVM) معرفی می کنیم. آزمایش ها بر روی پایگاه داده ی AR و در دو حالت بدون تصاویر با مانع و با تصاویر با مانع اناجم شده است. نتایج آزمایش ها نشان می دهد که روش پیشنادی ما به خوبی می تواند تصاویر چهره را بازیابی کند. در ادامه، روش پیشنهادی خود را با برخی از روش های موفق در توصیف چهره مقایسه کرده ایم. معیار دقت متوسط میانگین(MAP) برای روش پیشنهادی در حالت های اول و دوم آزمایش به ترتیب برابر است با 94/40%  و 68/12%. در حالی که بهترین نرخ برای روش های مقایسه شده برابر است با 90/37% و 61/99%. این نتایج نشان می دهد روش پیشنهادی ما نسبت به این روش ها بهتر عمل می کند و یک روش خوب برای بازیابی تصاویر چهره است.

واژه های کلیدی: الگوی باینری محلی، بازیابی چهره، فیدبک ارتباطی، ماشین بردار پشتیبان، هیستوگرام گرادیان.

فایل PDF – در 11 صفحه- نویسندگان : محمد قاصری و حسین ابراهیم نژاد

ﺑﺎزﯾﺎﺑﯽ ﺗﺼﺎوﯾﺮ ﭼﻬﺮه ﺑﺎ اﺳﺘﻔﺎده از ﺗﺮﮐﯿﺐ ﻫﯿﺴﺘﻮﮔﺮام ﮔﺮادﯾﺎن و اﻟﮕﻮی ﺑﺎﯾﻨﺮی ﻣﺤﻠﯽ

رمز فایل : behsanandish.com

5. بهبود وفقی کنتراست با استفاده از متعادل سازی بهینه هیستوگرام دو بعدی

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

واژه های کلیدی: بهبود کنتراست، هیستوگرام دوبعدی، هموارسازی هیستوگرام

فایل PDF – در 10 صفحه- نویسندگان : سحر ایروانی و مهدی ازوجی

ﺑﻬﺒﻮد وﻓﻘﯽ ﮐﻨﺘﺮاﺳﺖ ﺑﺎ اﺳﺘﻔﺎده از ﻣﺘﻌﺎدل ﺳﺎزی ﺑﻬﯿﻨﻪ ی ﻫﯿﺴﺘﻮﮔﺮام دوﺑﻌﺪی

رمز فایل : behsanandish.com

6. A Study for Applications of Histogram in Image Enhancement

مطالعه برای کاربرد هیستوگرام در بهبود تصویر

Abstract- Image Enhancement aims at improving the visual quality of input image for a particular area. The criterion used by enhancement algorithms to enhance the image is; using histogram details of that image. This paper defines the various applications of histograms through which they help in the enhancement process. The paper also represents three basic histogram processing techniques- histogram sliding, histogram stretching, and histogram equalization, and how these techniques help in enhancement process, which factors effect these techniques. We examine subjectively the effect of these processing techniques. Comparative analysis of these techniques is also carried out.

Keywords: Histogram Equalization, Histogram Sliding, Histogram Stretching, Image Enhancement, Visual Quality.

فایل PDF – در 5 صفحه- نویسندگان : Harpreet Kaur, Neelofar Sohi

A Study for Applications of Histogram in Image Enhancement

رمز فایل : behsanandish.com

7. An Adaptive Histogram Equalization Algorithm on the Image Gray Level Mapping

الگوریتم انعکاس هیستوگرام سازگار بر روی نقشه سطح خاکستری تصویر

Abstract
The conventional histogram equalization algorithm is easy causing information loss. The paper presented an adaptive histogram-based algorithm in which the information entropy remains the same. The algorithm introduces parameter ȕ in the gray level mapping formula, and takes the information entropy as the target function to adaptively adjust the spacing of two adjacent gray levels in the new histogram. So it avoids excessive gray pixel merger and excessive bright local areas of the image. Experiments show that the improved algorithm may effectively improve visual effects under the premise of the same information entropy. It is useful in CT image processing.

Keywords: Histogram Equalization; Image Enhancement; Gray Level Mapping; Information Entropy

فایل PDF – در 8 صفحه- نویسندگان : Youlian Zhu, Cheng Huang

An Adaptive Histogram Equalization Algorithm on the Image

رمز فایل : behsanandish.com

8. Contrast Enhancement Algorithm Based on Gap Adjustment for Histogram Equalization

الگوریتم تقویت کنتراست براساس تنظیم گاف برای برابری هیستوگرام

Abstract: Image enhancement methods have been widely used to improve the visual effects of images. Owing to its simplicity and effectiveness histogram equalization (HE) is one of the methods used for enhancing image contrast. However, HE may result in over-enhancement and feature loss problems that lead to unnatural look and loss of details in the processed images. Researchers have proposed various HE-based methods to solve the over-enhancement problem; however, they have largely ignored the feature loss problem. Therefore, a contrast enhancement algorithm based on gap adjustment for histogram equalization (CegaHE) is proposed. It refers to a visual contrast enhancement algorithm based on histogram equalization (VCEA), which generates visually pleasing enhancedimages,andimprovestheenhancementeffectsofVCEA.CegaHEadjuststhegapsbetween two gray values based on the adjustment equation, which takes the properties of human visual perception into consideration, to solve the over-enhancement problem. Besides, it also alleviates the feature loss problem and further enhances the textures in the dark regions of the images to improve the quality of the processed images for human visual perception. Experimental results demonstrate that CegaHE is a reliable method for contrast enhancement and that it significantly outperforms VCEA and other methods.

Keywords: cumulative distribution function (CDF); contrast enhancement; histogram equalization (HE); human visual perception; gap adjustment

فایل PDF – در 18 صفحه- نویسندگان : Chung-Cheng Chiu , and Chih-Chung Ting

Contrast Enhancement Algorithm Based on Gap

رمز فایل : behsanandish.com

9. Enhancement of Images Using Histogram Processing Techniques

بهبود تصاویر با استفاده از تکنیک های پردازش هیستوگرام

Abstract- Image enhancement is a mean as the improvement of an image appearance by increasing dominance of some features or by decreasing ambiguity between different regions of the image. Image enhancement processes consist of a collection of techniques that seek to improve the visual appearance of an image or to convert the image to a form better suited for analysis by a human or machine. Many images such as medical images, remote sensing images, electron microscopy images and even real life photographic pictures, suffer from poor contrast. Therefore it is necessary to enhance the contrast.The purpose of image enhancement methods is to increase image visibility and details. Enhanced image provide clear image to eyes or assist feature extraction processing in computer vision system. Numerous enhancement methods have been proposed but the enhancement efficiency, computational requirements, noise amplification, user intervention, and application suitability are the common factors to be considered when choosing from these different methods for specific image processing application.

Keywords: Enhancement, Histogram processing techniques, PSNR,MSE.

فایل PDF – در 5 صفحه- نویسندگان :Komal Vij , Yaduvir Singh

Enhancement of Images Using Histogram Processing

رمز فایل : behsanandish.com

10. USE OF HISTOGRAM EQUALIZATION IN IMAGE PROCESSING FOR IMAGE ENHANCEMENT

استفاده از تعادل هیستوگرام در پردازش تصویر برای افزایش تصویر

Abstract— Digital Image Processing is a rapidly evolving field with the growing applications in science & engineering. Image Processing holds the possibility of developing an ultimate machine that could perform visual functions of all living beings. The image processing is a visual task, the foremost step is to obtain an image i.e. image acquisition then enhancement and finally to process. In this paper there are details for image enhancement for the purpose of image processing. Image enhancement is basically improving the digital image quality. Image histogram is helpful in image enhancement. The histogram in the context of image processing is the operation by which the occurrences of each intensity value in the image is shown and Histogram equalization is the technique by which the dynamic range of the histogram of an image is increased.

Keywords- Image processing, image enhancement, image histogram, Histogram equalization

فایل PDF – در 5 صفحه- نویسندگان :Sapana S. Bagade , Vijaya K. Shandilya

USE OF HISTOGRAM EQUALIZATION IN IMAGE PROCESSING FOR IMAGE ENHANCEMENT

رمز فایل : behsanandish.com

جزوات آموزشی

1. Computer Vision – Histogram Processing

1. بینایی کامپیوتر- پردازش هیستوگرام

فایل PDF – در 40 صفحه- نویسنده : Dr. S. Das 

Computer Vision -histogram processing

رمز فایل : behsanandish.com

2. Digital Image Processing (CS/ECE 545)  Lecture 2: Histograms and Point Operations (Part 1)

پردازش تصویر دیجیتال(CS/ECE 545)  درس 2: هیستوگرام و عملیات نقطه

فایل PDF – در 56 صفحه- نویسنده : Prof Emmanuel Agu

Digital Image Processing-histograms and point operations

رمز فایل : behsanandish.com

3. Part 3: Image Processing – Digital Images and Intensity Histograms

بخش 3: پردازش تصویر – تصاویر دیجیتال و هیستوگرام های شدت

فایل PDF – در 57 صفحه- نویسنده : Georgy Gimel’farb

Digital Images and Intensity Histograms

رمز فایل : behsanandish.com

4.  Digital Imaging and Multimedia Histograms of Digital Images

تصویربرداری دیجیتالی و هیستوگرام های چند رسانه ای از تصاویر دیجیتال

فایل PDF – در 12 صفحه- نویسنده : Ahmed Elgammal

Digital Imaging and Multimedia

رمز فایل : behsanandish.com

/0 دیدگاه /توسط

الگوریتم Canny در (Visual Basic)

الگوریتم Canny

لبه یاب کنی توسط جان اف کنی در سال 1986 ایجاد شد و هنوز یک لبه یاب استاندارد و با دقت و کیفیت بالا میباشد.الگوریتم لبه یابی کنی یکی از بهترین لبه یابها تا به امروز است. در ادامه روش کار این الگوریتم و هم چنین کد الگوریتم Canny در Visual Basic را بررسی خواهیم کرد. این الگوریتم لبه یابی از سه بخش اصلی زیر تشکیل شده:

  • تضعیف نویز
  • پیدا کردن نقاطی که بتوان آنها را به عنوان لبه در نظر گرفت
  • حذب نقاطی که احتمال لبه بودن آنها کم است

 

معیارهایی که در لبه یا کنی مطرح است:
1 -پایین آوردن نرخ خطا- یعنی تا حد امکان هیچ لبه ای در تصویر نباید گم شود و هم چنین هیچ چیزی که لبه نیست نباید به جای لبه فرض شود. لبه هان پیدا شده تا حد ممکن به لبه ها اصلی
نزدیک باشند.

2 -لبه در مکان واقعی خود باشد- یعنی تا حد ممکن لبه ها کمترین فاصله را با مکان واقعی خود داشته باشند.
3 -بران هر لبه فقط یک پاسخ داشته باشیم.

4 -لبه ها کمترین ضخامت را داشته باشند- (در صورت امکان یک پیکسل).
لبه یاب کنی بخاطر توانایی در تولید لبه های نازک تا حد یک ییکسل برای لبه های پیوسته معروف شده است. این لبه یاب شامل چهار مرحله و چهار ورودی زیر است:
یک تصویر ورودی
یک پارامتر به نام سیگما جهت مقدار نرم کنندگی تصویر
یک حد آستانه بالا (Th)
یک حد آستانه پایین (Tl)

 

مراحل الگوریتم Canny:

1- در ابتدا باید تصویر رنگی را به جهت لبه یابی بهتر به یک تصویر سطح خاکسترن تبدیب کرد.

2- نویز را از تصویر دریافتی حذف کرد. بدلیل اینکه فیلتر گاوسین از یک ماسک ساده برای حذف نویز استفاده می کند لبه یاب کنی در مرحله اول برای حذف نویز آن را بکار میگیرد.

3- در یک تصویر سطح خاکستر جایی را که بیشترین تغییرات را داشته باشند به عنوان لبه در نظر گرفته می شوند و این مکانها با گرفتن گرادیان تصویر با استفاده عملگر سوبل بدست می آیند. سپس لبه های مات یافت شده به لبه های تیزتر تبدیل می شوند.

4- برخی از لبه های کشف شده واقعا لبه نیستند و در واقع نویز هستند که باید آنها توسط حد آستانه هیسترزیس فیلتر شوند.هیسترزیس از دو حد آستانه بالاتر (Th) و حد آستانه پایین تر (Tl) استفاده کرده و کنی پیشنهاد می کند که نسبت استانه بالا به پایین سه به یک باشد.

 این روش بیشتر به کشف لبه های ضعیف به درستی می پردازد و کمتر فریب نویز را می خورد و از بقیه روش ها بهتر است.

 

الگوریتم Canny    عملکرد الگوریتم Canny

 

الگوریتم Canny در Visual Basic:

کد زیر یک کد تکمیل نشده است.تکمیل آن به عنوان تمرین به خواننده واگذار می شود.

 

Imports System.Drawing
Imports System.Drawing.Imaging

Public Class clsEdges

    Public Sub EdgeDetectDifference(ByVal b As Bitmap, ByVal threshold As Byte)
        ' first we create a clone o the image we want to find the edges on
        Dim b2 As Bitmap = b.Clone
        ' we create bitmapdata of the images at the same time locking them
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        ' the stride describes the distance between image bytes
        Dim stride As Integer = bmData2.Stride
        ' scan0 is some sort of OS handle or something to identify the actual data in the memory
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        ' we need to know how big the data is so that we can create the correct size for the file
        Dim bytes As Integer = b.Height * b.Width * 3
        ' we create the byte arrays so that we can edit them
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte
        ' put the images into the byte arrays
        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)

        ' the nWidth describes the width of the actual image multiplied by three for each byte in the pixel (3 bytes per pixel 24 bits ;))
        Dim nWidth As Integer = b2.Width * 3
        ' for some reason although the original code show a formula to come up with the offset this doesn't work very well.
        ' I found that it is just easier to make the offset 0 and so all bits are handled. Basically the problem comes when 
        ' using this on files that don't have
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3
        Dim p2minusplus As Integer, p2plusminus As Integer, p2plusplus As Integer, p2minusminus As Integer
        Dim p2minusstride As Integer, p2plusstride As Integer
        Dim p2plus As Integer, p2minus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2minusplus = pos2 - stride + 3
                p2plusminus = pos2 + stride - 3
                p2plusplus = pos2 + stride + 3
                p2minusminus = pos2 - stride - 3
                p2minusstride = pos2 - stride
                p2plusstride = pos2 + stride
                p2minus = pos2 - 3
                p2plus = pos2 + 3
                If p2minusplus <= p02.Length - 1 And p2minusplus >= 0 And p2plusminus <= p02.Length - 1 And p2plusminus >= 0 And _
                p2plusplus <= p02.Length - 1 And p2plusplus >= 0 And p2minusminus <= p02.Length - 1 And p2minusminus >= 0 And _
                p2minusstride <= p02.Length - 1 And p2minusstride >= 0 And p2plusstride <= p02.Length - 1 And p2plusstride >= 0 And _
                p2plus <= p02.Length - 1 And p2plus >= 0 And p2minus <= p02.Length - 1 And p2minus >= 0 And pos1 < p01.Length Then
                    npixelmax = Math.Abs(CInt(p02(p2minusplus)) - CInt(p02(p2plusminus)))
                    nPixel = Math.Abs(CInt(p02(p2plusplus)) - CInt(p02(p2minusminus)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    nPixel = Math.Abs(CInt(p02(p2minusstride)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    nPixel = Math.Abs(CInt(p02(p2plus)) - CInt(p02(p2minus)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    If npixelmax < CInt(threshold) Then npixelmax = 0
                    p01(pos1) = CByte(npixelmax)
                End If
                pos1 += 1
                pos2 += 1

            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

    End Sub
    Public Sub EdgeDetectHomogenity(ByVal b As Bitmap, ByVal threshold As Byte)
        Dim b2 As Bitmap = b.Clone
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim stride As Integer = bmData2.Stride
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        Dim bytes As Integer = b.Height * b.Width * 3
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte

        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)
        Dim nWidth As Integer = b2.Width * 3
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3

        Dim p2plusminus As Integer, p2plusstride As Integer, p2plusplus As Integer, p2minusstride As Integer, _
        p2minusminus As Integer, p2minusplus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2plusminus = pos2 + stride - 3
                p2plusstride = pos2 + stride
                p2plusplus = pos2 + stride + 3
                p2minusstride = pos2 - stride
                p2minusminus = pos2 - stride - 3
                p2minusplus = pos2 - stride + 3

                If p2plusminus < p02.Length And p2plusminus >= 0 And p2plusstride < p02.Length And p2plusstride >= 0 And _
                p2plusplus < p02.Length And p2plusplus >= 0 And p2minusstride < p02.Length And p2minusstride >= 0 And _
                p2minusstride < p02.Length And p2minusstride >= 0 And p2minusminus < p02.Length And p2minusminus >= 0 And _
                p2minusplus < p02.Length And p2minusplus >= 0 Then

                    npixelmax = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusminus)))
                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusplus)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusminus)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusplus)))
                    If nPixel > npixelmax Then npixelmax = nPixel


                    If npixelmax < threshold Then npixelmax = 0

                    p01(pos1) = CByte(npixelmax)

                End If

                pos1 += 1
                pos2 += 1
            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

    End Sub


    Public Function EdgeEnhance(ByVal b As Bitmap, ByVal threshold As Byte) As Boolean
        Dim b2 As Bitmap = b.Clone
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim stride As Integer = bmData2.Stride
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        Dim bytes As Integer = b.Height * b.Width * 3
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte

        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)
        Dim nWidth As Integer = b2.Width * 3
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3
        Dim p2minusplus As Integer, p2plusminus As Integer, p2plusplus As Integer, p2minusminus As Integer
        Dim p2minusstride As Integer, p2plusstride As Integer
        Dim p2plus As Integer, p2minus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2minusplus = pos2 - stride + 3
                p2plusminus = pos2 + stride - 3
                p2plusplus = pos2 + stride + 3
                p2minusminus = pos2 - stride - 3
                p2minusstride = pos2 - stride
                p2plusstride = pos2 + stride
                p2minus = pos2 - 3
                p2plus = pos2 + 3
                If p2minusplus <= p02.Length - 1 And p2minusplus >= 0 And p2plusminus <= p02.Length - 1 And p2plusminus >= 0 And _
                p2plusplus <= p02.Length - 1 And p2plusplus >= 0 And p2minusminus <= p02.Length - 1 And p2minusminus >= 0 And _
                p2minusstride <= p02.Length - 1 And p2minusstride >= 0 And p2plusstride <= p02.Length - 1 And p2plusstride >= 0 And _
                p2plus <= p02.Length - 1 And p2plus >= 0 And p2minus <= p02.Length - 1 And p2minus >= 0 And pos1 < p01.Length Then
                    npixelmax = Math.Abs(CInt(p02(pos2 - stride + 3)) - CInt(p02(pos2 + stride - 3)))
                    nPixel = Math.Abs(CInt(p02(pos2 + stride + 3)) - CInt(p02(pos2 - stride - 3)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2 - stride)) - CInt(p02(pos2 + stride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2 + 3)) - CInt(p02(pos2 - 3)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    If npixelmax > threshold And npixelmax > p01(pos1) Then
                        p01(pos1) = CByte(Math.Max(CInt(p01(pos1)), npixelmax))
                    End If

                End If

                pos1 += 1
                pos2 += 1
            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

        Return True
    End Function

End Class

 

 

این کد کامل نیست!

دانلود کد فوق از طریق لینک زیر:

CannyInVisualBasic

رمز فایل : behsanandish.com

 

/0 دیدگاه /توسط

جزوه پردازش تصویر با متلب_ دانشگاه پیام نور

جزوه پردازش تصویر با متلب (Matlab)_ دانشگاه پیام نور

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

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

‫این جزوه گه توسط گروه رباتیک دانشگاه پیام نور قم به صورت تایپ شده گردآوری شده است شامل آموزش پردازش تصویر با متلب است.

لینک دانلود: جزوه پردازش تصویر با متلب_ دانشگاه پیام نور

پسورد فایل: behsanandish.com

تعداد صفحات : 51

/1 دیدگاه/توسط

بهينه‌سازی و معرفي روش‌های آن قسمت 2

3-5-انواع روش‌هاي فرا ابتكاري برگرفته از طبيعت

1-3-5-الگوريتم ژنتيك

الگوريتم ژنتيك (Genetic Algorithm) روشي عمومي از روش‌هاي فرا ابتكاري براي بهينه‌سازي گسسته مي‌باشد كه مسائل جدول زمانبندي را حل مي‌نمايد. روش شبيه‌سازي كه در ادامه مورد بحث قرار می‌گيرد، راهبرد تكاملي نام دارد. اين روش در سال 1975 به وسيله هولند (Holland) و در سال 1989 توسط  گولدبرگ (Goldberg) ابداع شده است.

اين روش نوعي روش جستجوي همسايه است كه عملكردي مشابه ژن دارد. در طبيعت، فرايند تكامل هنگامي ايجاد مي‌شود كه چهار شرط زير برقرار باشد:

الف) يك موجود توانايي تكثير داشته باشد (قابليت توليد مثل).

ب) جمعيتي از اين موجودات قابل تكثير وجود داشته باشد.

پ) چنين وضعيتي داراي تنوع باشد.

ت) اين موجودات به وسيله قابليت‌هايي در زندگي از هم جدا شوند.

در طبيعت، گونه‌هاي متفاوتي از يك موجود وجود دارند كه اين تفاوت‌ها در كروموزوم‌هاي اين موجودات ظاهر مي‌شود و باعث تنوع در ساختار و رفتار اين موجودات مي‌شود.

اين تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثير مي‌گذارد. موجوداتي كه قابليت‌ها و توانايي بيشتري براي انجام فعاليت‌ها در محيط دارند (موجودات متكامل‌تر)، داراي نرخ زاد و ولد بالاتري خواهند بود و طبعاً موجوداتي كه سازگاري كمتري با محيط دارند، از نرخ زاد و ولد پايين‌تري برخوردار خواهند بود. بعد از چند دوره زماني و گذشت چند نسل، جمعيت تمايل دارد كه موجوداتي را بيشتر در خود داشته باشد كه كروموزوم‌هايشان با محيط اطراف سازگاري بيشتري دارد.

در طي زمان، ساختار افراد جامعه به علت انتخاب طبيعي تغيير مي‌كند و اين نشانه تكامل جمعيت است.

6- آنيلينگ شبيه‌سازي شده

اين روش توسط متروپوليس (Metropolis) و همكاران در سال 1953 پيشنهاد شده و جهت بهينه‌سازي به وسيله وچی (Vecchi)، گلات (Gelatt) و کرک‌پاتريک (kirkpatrick ) در سال 1983 مورد بازبيني قرار گرفته است. اين روش در مسائل تاكسي تلفني كاربرد دارد.

الگوريتم آنيلينگ شبيه‌سازي شده (Simulated Annealing) در شکل عمومي، بر اساس شباهت ميان سرد شدن جامدات مذاب و حل مسائل بهينه‌سازي تركيبي به وجود آمده است. در فيزيك مواد فشرده، گرم و سرد كردن فرايندي است فيزيكي كه طي آن يك ماده جامد در ظرفي حرارت داده مي‌شود تا مايع شود؛ سپس حرارت آن بتدريج كاهش مي‌يابد. بدين ترتيب تمام ذرات فرصت مي‌يابند تا خود را در پايين‌ترين سطح انرژي منظم كنند. چنين وضعي در شرايطي ايجاد مي‌شود كه گرمادهي كافي بوده و سرد كردن نيز به آهستگي صورت گيرد. جواب حاصل از الگوريتم گرم و سرد كردن شبيه‌سازي شده، به جواب اوليه وابسته نيست و مي‌توان توسط آن جوابي نزديك به جواب بهينه به دست آورد. حد بالايي زمان اجراي الگوريتم نيز قابل تعيين است. بنابراين الگوريتم گرم و سرد كردن شبيه‌سازي شده، الگوريتمي است تكراري كه اشكالات روش‌هاي عمومي مبتني بر تكرار را ندارد.

در روش آنيلينگ شبيه‌سازي شده، به صورت پي در پي از جواب جاري به يكي از همسايه‌هاي آن انتقال صورت مي‌گيرد. اين سازوکار توسط زنجيره ماركوف به صورت رياضي قابل توصيف است. در اين روش، يك مجموعه آزمون انجام مي‌گيرد؛ اين آزمون‌ها به نحوي است كه نتيجه هر يك به نتيجه آزمون قبل وابسته است. در روش آنيلينگ شبيه‌سازي شده، منظور از يك آزمون، انتقال به نقطه جديد است و روشن است كه نتيجه انتقال به نقطه جديد تنها وابسته به مشخصات جواب جاري است.

روش جستجوي همسايه و روش آنيلينگ شبيه‌سازي شده، هر دو روش‌هاي تكراري هستند. در الگوريتم آنيلينگ شبيه‌سازي شده، هر بار كه شاخص كنترل‌كننده به مقدار نهايي خود مي‌رسد، در حقيقت يك عمليات تكراري انجام شده است. در الگوريتم جستجوي همسايه، هنگامي كه تعداد تكرارها به سمت بي‌نهايت ميل مي‌كند، روش به جواب بهينه نزديك مي‌شود. اما عملكرد الگوريتم آنيلينگ شبيه‌سازي شده سريع‌تر است.

7-شبکه‌های عصبی

شبکه‌های عصبی (Neural Networks) مصنوعی سيستم‌هاي هوشمندی هستند که از شبکه‌هاي عصبي طبيعي الهام گرفته شده‌اند. شبکه‌هاي عصبي مصنوعي در واقع تلاشي براي حرکت از سمت مدل محاسباتي فون نيومن به سمت مدلي است که با توجه به عملکرد و ويژگي‌هاي مغز انسان طراحي شده است. مدل فون نيومن گرچه هم اکنون بسيار استفاده می‌شود، اما از کمبودهايي رنج مي‌برد که تلاش شده است اين کمبودها در شبکه‌هاي عصبي مصنوعي برطرف شود.

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

مدل پایه ای نرون

مدل پايه‌اي نورون به صورت شکل 1-3 تعريف می‌شود.

مدل پایه ای نرون

مدل پایه ای نرون

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

جستجوي ممنوع

روشی عمومي است كه به وسيله گلوور (Glover) در سال 1989 پيشنهاد شده و در حل مسائل برنامه‌ريزي كاري ـ خريد کاربرد دارد.

روش جستجوي ممنوع (Tabu Search)، همانند روش آنيلينگ شبيه‌سازي شده بر اساس جستجوي همسايه بنا شده است. در اين روش عملكرد حافظه انسان شبيه‌سازي شده است. حافظه انسان با به كارگيري ساختماني مؤثر و در عين حال ساده از اطلاعات، آنچه را در قبل رؤيت شده، ذخيره مي‌كند. اين مركز همچنين فهرستی از حركات منع شده را تنظيم مي‌كند و اين فهرست همواره بر اساس آخرين جستجوها منظم مي‌شود. اين روش از انجام هر گونه عمليات مجدد و تكراري جلوگيري مي‌كند.

شكل نوين جستجوي ممنوع توسط گلوور مطرح شده است. روش جستجوي مبتني بر منع، با ايجاد تغييري كوچك در روش جستجوي همسايه به وجود مي‌آيد. هدف اين روش آن است كه بخش‌هايي از مجموعه جواب كه پيش از اين بررسي نشده است، مد نظر قرار گيرد. بدين منظور حركت به جواب‌هايي كه اخيراً جستجو شده، ممنوع خواهد بود.

ساختار كلي روش جستجوي ممنوع بدين صورت است كه ابتدا يك جواب اوليه امكان‌پذير انتخاب مي‌شود؛ سپس براي جواب مربوط، بر اساس يک معيار خاص مجموعه‌اي از جواب‌هاي همسايه امكان‌پذير در نظر گرفته مي‌شود.

در گام بعد، پس از ارزيابي جواب‌هاي همسايه تعيين شده، بهترين آنها انتخاب مي‌شود و جابه‌جايي از جواب جاري به جواب همسايه انتخابي صورت مي‌گيرد. اين فرايند به همين ترتيب تكرار مي‌شود تا زماني كه شرط خاتمه تحقق يابد.

در روش جستجوي ممنوع، فهرستي وجود دارد كه جابه‌جايي‌هاي منع شده را نگهداري مي‌كند و به فهرست تابو معروف است و كاربرد اصلي آن، پرهيز از همگرا شدن به جواب‌هاي بهينه محلي است. به عبارت ديگر، به كمك فهرست تابو جابه‌جايي به جواب‌هايي كه اخيراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هايي از مجموعه جواب كه پيش از اين مورد بررسي قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جايي از جواب جاري به جواب همسايه امكان‌پذير زماني انجام مي‌شود كه در فهرست تابو قرار نداشته باشد. در غير اين صورت، جواب همسايه ديگري كه در ارزيابي جواب‌هاي همسايه در رده بعدي قرار گرفته است، انتخاب شده و جابه‌جايي به آن صورت مي‌گيرد.

در روش جستجوي ممنوع بعد از هر جابه‌جايي، فهرست تابو بهنگام مي‌شود، به نحوي كه جابه‌جايي جديد به آن فهرست اضافه شده و جابه‌جايي كه تا n  تكرار مشخص در فهرست بوده است، از آن حذف مي‌شود. نحوه انتخاب مي‌تواند با توجه به شرايط و نوع مسأله متفاوت باشد.

سيستم مورچه (Ant System)

اين روش در سال 1991 توسط مانيه‌زو (Maniezzo) دوريگو (Dorigo) و کولورنی (Colorni) پيشنهاد شده است كه در حل مسأله فروشنده دوره‌گرد و مسائل تخصيص چندوجهي کاربرد دارد.

الگوريتم بهينه‌سازي كلوني مورچه‌ها از عامل‌هاي ساده‌اي كه مورچه ناميده مي‌شوند، استفاده مي‌كند تا به صورت تكراري جواب‌هايي توليد كند. مورچه‌ها می‌توانند كوتاه‌ترين مسير از يك منبع غذايي به لانه را با بهره‌گيري از اطلاعات فرموني پيدا کنند. مورچه‌ها در هنگام راه رفتن، روي زمين فرمون مي‌ريزند و با بو كشيدن فرمون ريخته شده بر روي زمين راه را دنبال مي‌كنند؛ چنانچه در طي مسير به سوي لانه به يك دوراهي برسند، از آن جايي كه هيچ اطلاعي درباره راه بهتر ندارند، راه را به تصادف برمي‌گزينند. انتظار مي‌رود به طور متوسط نيمي از مورچه‌ها مسير اول و نيمي ديگر مسير دوم را انتخاب كنند.

فرض مي‌شود كه تمام مورچه‌ها با سرعت يكسان مسير را طي كنند. از آنجا كه يك مسير كوتاه‌تر از مسير ديگر است، مورچه‌هاي بيشتري از آن مي‌گذرند و فرمون بيشتري بر روي آن انباشته مي‌شود. بعد از مدت كوتاهي مقدار فرمون روي دو مسير به اندازه‌اي مي رسد كه روي تصميم مورچه‌هاي جديد براي انتخاب مسير بهتر تأثير مي‌گذارد. از اين به بعد، مورچه‌هاي جديد با احتمال بيشتري ترجيح مي‌دهند از مسير كوتاه‌تر استفاده كنند، زيرا در نقطه تصميم‌گيري مقدار فرمون بيشتري در مسير كوتاه‌تر مشاهده مي‌كنند. بعد از مدت كوتاهي تمام مورچه‌ها اين مسير را انتخاب خواهند كرد.

منبع

مقدمه ای بر بهینه سازی و الگوریتم های موجود

هدف از بهينه‌سازي يافتن بهترين جواب قابل قبول، با توجه به محدوديت‌ها و نيازهاي مسأله است. براي يك مسأله، ممكن است جواب‌هاي مختلفي موجود باشد كه براي مقايسه آنها و انتخاب جواب بهينه، تابعي به نام تابع هدف تعريف مي‌شود. انتخاب اين تابع به طبيعت مسأله وابسته است. به عنوان مثال، زمان سفر يا هزينه از جمله اهداف رايج بهينه‌سازي شبكه‌هاي حمل و نقل مي‌باشد. به هر حال، انتخاب تابع هدف مناسب يكي از مهمترين گام‌هاي بهينه‌سازي است. گاهي در بهينه‌سازي چند هدف  به طور همزمان مد نظر قرار مي‌گيرد؛ اين گونه مسائل بهينه‌سازي را كه دربرگيرنده چند تابع هدف هستند، مسائل چند هدفي مي‌نامند. ساده‌ترين راه در برخورد با اين گونه مسائل، تشكيل يك تابع هدف جديد به صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص مي‌شود. هر مسأله بهينه‌سازي داراي تعدادي متغير مستقل است كه آنها را متغيرهاي طراحي می‌نامند كه با بردار n  بعدي x  نشان داده مي‌شوند.

هدف از بهينه‌سازي تعيين متغيرهاي طراحي است، به گونه‌اي كه تابع هدف كمينه يا بيشينه شود.

مسائل مختلف بهينه‌سازي  به دو دسته زير تقسيم مي‌شود:

الف) مسائل بهينه‌سازي بي‌محدوديت: در اين مسائل هدف، بيشينه يا كمينه كردن تابع هدف بدون هر گونه محدوديتي بر روي متغيرهاي طراحي مي‌باشد.

ب) مسائل بهينه‌سازي با محدوديت: بهينه‌سازي در اغلب مسائل كاربردي، با توجه به محدوديت‌هايي صورت مي‌گيرد؛ محدوديت‌هايي كه در زمينه رفتار و عملكرد يك سيستم مي‌باشد و محدوديت‌هاي رفتاري و محدوديت‌هايي كه در فيزيك و هندسه مسأله وجود دارد، محدوديت‌هاي هندسي يا جانبي ناميده مي‌شوند.

معادلات معرف محدوديت‌ها ممكن است  به صورت مساوي يا نامساوي باشند كه در هر مورد، روش بهينه‌سازي متفاوت مي‌باشد. به هر حال محدوديت‌ها، ناحيه قابل قبول در طراحي را معين مي‌كنند.

فرايند بهينه ­سازي

فرموله كردن مسئله: در اين مرحله، يك مسئله ­ي تصميم ­گيري، همراه با يك ساختار كلي از آن تعريف مي‌شود. اين ساختار كلي ممكن است خيلي دقيق نباشد اما وضعيت كلي مسئله را، كه شامل فاكتورهاي ورودي و خروجي و اهداف مسئله است، بيان مي­ كند. شفاف­ سازي و ساختاردهي به مسئله، ممكن است براي بسياري از مسايل بهينه­ سازي، كاري پيچيده باشد.

مدل­ سازي مسئله:

در اين مرحله يك مدل رياضي كلي براي مسئله، ساخته مي­ شود. مدل­سازي ممكن است از مدل­ هاي مشابه در پيشينه ­ي موضوع كمك بگيرد. اين گام موجب تجزيه مسئله به يك يا چند مدل بهينه‌سازي مي­ گردد.

بهينه­ سازي مسئله:

پس از مدل سازي مسئله، روال حل، يك راه ­حل خوب براي مسئله توليد مي­ كند. اين راه‌حل ممكن است بهينه يا تقريباً بهينه باشد. نكته ­اي كه بايد به آن توجه داشت اين است كه راه ­حل به دست آمده، راه­ حلي براي مدل طراحي شده است، نه براي مسئله ­ي واقعي. در هنگام فرموله كردن و مدلسازي ممكن است تغييراتي در مسئله واقعي به وجود آمده و مسئله­ ي جديد، نسبت به مسئله­ ي واقعي تفاوت زيادي داشته باشد.

استقرار مسئله:

راه ­حل به دست آمده توسط تصميم گيرنده بررسي مي­ شود و در صورتي كه قابل قبول باشد، مورد استفاده قرار مي­ گيرد و در صورتي كه راه­حل قابل قبول نباشد، مدل يا الگوريتم بهينه­ سازي بايد توسعه داده شده و فرايند بهينه­ سازي تكرار گردد.

الگوریتم­ های بهینه­ سازی

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

 روش‌هاي فرا ابتكاري برگرفته از طبيعت

الگوريتم ­هاي فراابتكاري الگوريتم ­هايي هستند كه با الهام از طبيعت، فيزيك و انسان طراحي شده ­اند و در حل بسياري از مسايل بهينه­ سازي استفاده می­ شوند. معمولاً از الگوريتم­ هاي فراابتكاري در تركيب با ساير الگوريتم­ ها، جهت رسيدن به جواب بهينه يا خروج از وضعيت جواب بهينه محلي استفاده مي­گردد. در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات، «روش‌هاي ابتكاري برگرفته از طبيعت» بوده است؛ اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. كاربرد ‌آنها برگرفته از روش‌هاي ابتكاري پيوسته می‌باشد كه در حل مسائل مشكل تركيبي (NP-Hard) نتايج بسيار خوبی داشته است.

در ابتدا با تعريفي از طبيعت و طبيعي بودن روش‌ها شروع مي‌كنيم؛ روش‌ها برگرفته از فيزيك، زيست‌شناسي و جامعه‌شناسي هستند و به صورت زير تشكيل شده‌اند:

–         استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري

–          استفاده از يك يا چند عامل (نرون، خرده‌ريز، كروموزوم، مورچه و غيره)

–          عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت

–          ايجاد روش‌هاي خود تغييري و خود تبديلي

طبيعت داراي دو تدبير بزرگ مي‌باشد:

1-    انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛

2-     جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.

به طور كلي دو وضعيت وجود دارد كه در روش‌هاي ابتكاري برگرفته از طبيعت ديده مي‌شود، يكي انتخاب و ديگري جهش. انتخاب ايده‌اي مبنا براي بهينه‌سازي و جهش ايده‌اي مبنا براي جستجوي پيوسته مي‌باشد.

از خصوصيات روش‌هاي ابتكاري  برگرفته از طبيعت، مي‌توان به موارد زير اشاره كرد:

1-    پديده‌اي حقيقي در طبيعت را مدل‌سازي مي‌كنند.

2-     بدون قطع مي‌باشند.

3-     اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.

4-     تطبيق‌پذير هستند.

خصوصيات بالا باعث رفتاري معقول در جهت تأمين هوشمندي مي‌شود. تعريف هوشمندي نيز عبارت است از قدرت حل مسائل مشكل؛ بنابراين هوشمندي به حلمناسب مسائل بهينه‌سازي تركيبي منجر می‌شود.

برخی الگوریتم های بهینه سازی مهم عبارت انداز:

 الگوریتم بهینه سازی ازدحام ذرات

در سال 1995 ابرهارت و کنیدی براي اولین بار PSOبه عنوان یک روش جستجوي غیر قطعی براي بهینه سازي تابعی مطرح گشت این الگوریتم از حرکت دسته جمعیپرندگانی که به دنبال غذا می­باشند، الهام گرفته شده است. گروهي از پرندگان در فضايي به صورت تصادفي دنبال غذا مي­گردند. تنها يك تكه غذا در فضاي مورد بحث وجود دارد. هيچ يك از پرندگان محل غذا را نمي­دانند. يكي از بهترين استراتژي­ها مي­تواند دنبال كردن پرنده­اي باشد كه كمترين فاصله را تا غذا داشته باشد.  ايناستراتژي در واقع جانمايه الگوريتم است. هر راه­حل كه به آن يك ذره گفته مي­شود،PSO  در الگوريتم معادل يك پرنده در الگوريتم حركت جمعي پرندگان مي­باشد.هر ذره يك مقدار شايستگي دارد كه توسط يك تابع شايستگي محاسبه مي­شود. هر چه ذره در فضا­ي جستجو به هدف – غذا در مدل حركت پرندگان-  نزدیكتر باشد،شايستگي بيشتري دارد. همچنين هر ذره داراي يك سرعت است كه هدايت حركت ذره را بر عهده دارد. هرذره با دنبال كردن ذرات بهينه در حالت فعلي، به حركت خوددر فضاي مساله ادامه مي­دهد.

الگوریتم کرم شب­ تاب

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

الگوریتم کلونی مورچگان

بهینه‌سازی گروه مورچه‌ها یا ACO همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می‌توان مطرح کرد. در این روش(ACo)، مورچه‌های مصنوعی به‌وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می‌توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.

 الگوریتم ژنتیک

الگوریتم‌های ژنتیک، تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند. این الگوریتم برای اولین بار توسط جان هنری هالند معرفی شد. در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. در هوش مصنوعی الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه‌حلها تبدیل می‌شود سپس راه حلها بعنوان کاندیداها توسط تابع ارزیاب (Fitness Function) مورد ارزیابی قرار می‌گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می‌یابد. الگوریتم ژنتیک بطور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش‌های آن به صورت فرایندهای تصادفی انتخاب می‌شوند.

منبع
بهينه‌سازی و معرفي روش‌های آن قسمت 1
بهينه‌سازی و معرفي روش‌های آن قسمت 2
بهينه‌سازی و معرفي روش‌های آن قسمت 3

/0 دیدگاه /توسط

آزمون تورینگ چیست؟ قسمت 2

واتسون، کابوس آزمون تورینگ!

واتسون را که به‌طور حتم به خاطر می‌آورید؟ ماشین ساخت آی‌بی‌ام که در سال 2011 با شکست دادن رقبای انسانی خبره در بازی Jeopardy سر‌و‌صدای زیادی به پا کرد. این ماشین به عنوان یکی از مدرن‌ترین نمونه‌های ماشین‌های هوشمند امروزی می‌تواند مورد بسیار خوبی برای بررسی وضعیت آزمون تورینگ در جهان امروز به شمار می‌رود.

خبر بد این است که واتسون آزمون تورینگ را با موفقیت پشت سر نگذاشته است و با تعاریف کلاسیک، به هیچ عنوان ماشین هوشمندی به شمار نمی‌آید. اما این باعث نمی‌شود تا این ماشین، انقلابی در حوزه هوش مصنوعی محسوب نشود. ماهنامه ساینتیفیک امریکن در شماره ماه مارس 2011 و کمی پس از موفقیت واتسون در Jeopardy مصاحبه‌ای را با استفن بیکر، روزنامه‌نگاری که در فرآیند ساخت واتسون با تیم آی‌بی‌ام همراه بود انجام داد که در آن بیکر به نکات جالبی در رابطه با وضعیت کنونی هوش مصنوعی اشاره می‌کند. بیکر ابتدا در پاسخ به این پرسش که چگونه واتسون دنیای هوش مصنوعی را تغییر داده، می‌گوید: «رؤیای اولیه در مورد هوش مصنوعی هیچ‌گاه به ثمر نرسید. در واقع دانشمندان پس از چندین دهه تحقیق، به این نتیجه رسیدند که ساخت سیستمی شبیه به مغز انسان، خیلی سخت‌تر از آن چیزی است که تصور می‌شد.

حتی واتسون نیز که انسان را در Jeopardy شکست داد، به این رؤیا چندان نزدیک نشده است. با این حال، در عرض 15 سال گذشته پیشرفت‌های خیره‌کننده‌ای در جنبه‌های کاربردی هوش مصنوعی صورت گرفته است. راهبردهای آماری برای شبیه‌سازی بعضی جنبه‌های آنالیز انسانی توانسته سیستم‌هايی کاربردی را در اختیار مردم قرار دهد که در هر زمینه‌ای، از دیپ بلو گرفته تا نت فلیکس، آمازون و گوگل زندگی ما را قبضه کرده‌اند.» بیکر سپس در مورد واتسون می‌گوید: «موضوع جدید درباره واتسون، راهبرد تماماً عمل‌گرای آن است. این ماشین روش‌های مختلفی را برای پاسخ به یک پرسش امتحان می‌کند. در اینجا راهبرد درست یا نادرست وجود ندارد بلکه واتسون در طول زمان یاد می‌گیرد تا چه زمانی به کدام روش تکیه کند. به نوعی می‌توان گفت در جنگ بین راهبردهای مختلف در هوش مصنوعی واتسون به مانند یک ندانم‌گرا (آگنوستیسیست) عمل می‌کند. جنبه جدید دیگر، توانایی بالای این ماشین در فهم زبان انگلیسی است. توانایی‌ای که به عقیده من از تمرین داده شدن این سیستم با دیتاست‌های عظیم ناشی شده است و با وجود خیره‌کننده بودن، یک روش جدید و بکر به شمار نمی‌‌‌آید.» بیکر سپس به توضیح مقایسه واتسون با مغز انسان پرداخته و می‌گوید: «تیم آی‌بی‌ام در هنگام برنامه‌ریزی واتسون توجه چنداني به ساختار مغز انسان نداشته است.

به عقیده من واتسون محصول واقعی مهندسی است‌: استفاده از فناوری‌های موجود برای ساخت ماشینی با ویژگی‌های مشخص در زمانی خاص.» بیکر سپس اضافه می‌کند: «با این حال من شباهت‌هایی را در شیوه تفکر واتسون و انسان‌ها مشاهده می‌کنم که البته به این دليل نیست که ما از یک طراحی یکسان سود می‌بریم، بلکه ما در واقع به دنبال حل مسائلی یکسان هستیم. به عنوان مثال، برخلاف بسیاری از کامپیوترها واتسون برای عدم قطعیت برنامه‌ریزی شده است. این سیستم هیچ‌گاه از جوابی که می‌دهد صد درصد مطمئن نیست بلکه در مورد آن شک و تردید دارد. این برای ماشینی که قرار است با زبان انسان‌ها ارتباط برقرار کند، راهبردی هوشمندانه به شمار می‌رود.»

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

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

این همان چیزی است که مدیران Diapers.com را به سمت اداره کل سیستم انبار به دست روبات‌ها سوق می‌دهد. یا فدکس را قانع می‌کند که می‌توان تعداد اپراتورهای شرکت را به حداقل رسانده و از ماشین‌هایی برای خدمات‌رساني به تماس‌های مشتریان استفاده کرد. چندین دهه قبل، انسان‌ها می‌ترسیدند روزی ماشین‌ها آن قدر هوشمند شوند که کنترل انسان‌ها را در دست گیرند. با این حال نزدیک به سی سال قبل و با شروع زمستان هوش مصنوعی، این ترس معنای سنتی خود را از دست داد و هم‌اکنون توانسته به شیوه‌ای جدید خود را وارد زندگی انسان‌ها کند. حقیقت تلخی در پس‌زمینه ماشین‌هایی مانند واتسون وجود دارد‌: بسیاری از کارهایی که تصور می‌کنیم هوشمندی انسان‌محورمان، ما را قادر به انجامشان می‌سازد در واقع آن‌قدر‌ها هم از نظر ماشین‌ها کار پیچیده‌ای به شمار نمی‌آید. اگر باور ندارید، می‌توانید از مبادله‌گران سنتی بورس در حوالی وال‌استریت سراغی بگیرید.

آينده

رابرت فرنچ، دانشمند علوم شناختی در مرکز ملی تحقیقات علمی فرانسه در رابطه با آینده آزمون تورینگ می‌گوید: «دو پیشرفت مهم در حوزه فناوری اطلاعات می‌تواند آزمون تورینگ را از بازنشستگی خارج کند. اول دسترسی بسیار گسترده به داده‌های خام؛ از فیدهای ویدیویی گرفته تا محیط‌های کاملاً صوتی و از مکالمه‌های عادی تا اسناد فنی. چنین اطلاعاتی در هر زمینه‌ای که به مغز انسان خطور می‌کند به صورت گسترده در دسترس هستند. پیشرفت دوم ایجاد روش‌های پیشرفته جمع‌آوری، مدیریت و پردازش این مجموعه غنی از داده‌ها است.»

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

با این حال، هنوز هم رؤیای ساخت ماشینی انسان نما برای انسان به صورت معمایی جذاب و البته بسیار سخت باقی مانده است. همه ما سال‌ها تصویر این رؤیا را در فیلم‌های هالیوودی تماشا کرده‌ایم و هر‌چند در واقعیت، رسیدن به آن نقطه خیلی سخت‌تر از آن چیزی بود که تورینگ و دیگر پیشگامان هوش مصنوعی تصور می‌کردند، اما پیشرفت‌هایی مانند ساخت واتسون، ماشینی که می‌تواند زبان انسانی را به خوبی تحليل کند، همچنان محققان را به آینده امیدوار می‌کند. پیشرفت چنین پروژه‌هایی به‌شدت وابسته به تعهد دولت‌ها و سرمایه‌ای است که آنان در اختیار مؤسسات تحقیقاتی قرار می‌دهند زیرا به دلیل فاصله چنین تحقیقاتی از حوزه کاربرد، از نظر اقتصادی نمی‌توان آن‌ها را یک سرمایه‌گذاری منطقی قلمداد کرد. آینده پر از شگفتی‌هایی است که ما انتظارش را نداریم اما مسیر تا به همین جا نیز به حد کافی لذت‌بخش بوده است که دغدغه آینده، ما را از ادامه راه دلسرد نکند.

نظریه و آزمون تورینگ (هوش مصنوعی)

 

نظریه و آزمون تورینگ

بیش از نیم قرن پیش، هنگامی که هنوز هیچ تراشه‌ سیلیکونی‌ای ساخته نشده بود، آلن تورینگ یکی از بحث ‌بر‌انگیزترین پرسش‌های فلسفی تاریخ را پرسید. او گفت آیا ماشین می‌تواند فکر کند و اندکی بعد کوشید به پیروی از این قاعده که هر ادعای علمی باید از بوته آزمایش سربلند بیرون بیاید، پرسش فلسفی خود را با یک آزمایش ساده و در عین حال پیچیده جایگزین کند. او پرسید آیا یک ماشین یک کامپیوتر می‌تواند بازی تقلید را با موفقیت پشت سر بگذارد.
آیا ماشین می‌تواند از انسان چنان تقلید کند که در یک آزمون محاوره‌ای نتوانیم تفاوت انسان و ماشین را تشخیص دهیم. او در سال ۱۹۵۰ براساس محاسباتی تخمین زد که ۵۰ سال بعد کامپیوتری با یک میلیارد بیت حافظه خواهد توانست به موفقیت‌هایی در این زمینه دست پیدا کند. اکنون که در نیمه سال ۲۰۰۸ میلادی هستیم، حتی هشت سال بیشتر از زمانی که او لازم دانسته بود، هنوز هیچ ماشینی نتوانسته است از بوته آزمون تورینگ با موفقیت خارج شود. در سال ۲۰۰۰ مفهوم هوش مصنوعی برای هیچ‌کس غیر قابل باور نبوددر این مقاله نگاهی داریم به سیر تحولاتی که پس از این پرسش تاریخی در دنیای علم و مهندسی به‌وقوع پیوستند. یکی از جالب‌ترین و هیجان‌انگیزترین پرسش‌هایی که تاکنون تاریخ فلسفه به خود دیده این پرسش است که آلن تورینگ فیلسوف و ریاضیدان انگلیسی در سال ۱۹۵۰ طی مقاله‌ای به نام: Computing Machinery and Intelligence یا {ماشین محاسباتی و هوشمند} مطرح کرد او پرسید آیا ماشین می‌تواند فکر کند. خود تورینگ نتوانست پاسخ قطعی این پرسش را پیدا کند. اما برای یافتن پاسخ مناسب در آینده یک راهبرد خلاقانه پیشنهاد کرد.

او آزمونی طراحی کرد که خود، آن را بازی تقلید نامید. او آزمون بازی تقلید را چنین شرح داد: یک پرسشگر- یک انسان- همزمان در حال گفت‌وگو با دو نفر است. هر یک از این دو نفر در اتاق‌های جداگانه قرار گرفته‌اند و پرسشگر نمی‌تواند هیچیک از آنها را ببیند یکی از این دو نفر انسان است و دیگری یک ماشین یعنی یک کامپیوتر. پرسشگر باید با این دو نفر شروع به گفت‌وگو کند و بکوشد بفهمد کدا‌میک از این دو، انسان است و کدامیک ماشین. اگر کامپیوتر بتواند طوری جواب دهد که پرسشگر نتواند انسان را از ماشین تمیز دهد آنگاه می‌توان ادعا کرد که این ماشین هوشمند است. تورینگ برای آسان‌کردن شرایط این آزمون و پرهیز از پیچیدگی‌های اضافی آن را به محاوره‌ای متنی و روی کاغذ محدود کرد تا مجبور به درگیر شدن با مسائل انحرافی مانند تبدیل متن به گفتار شفاهی و تنظیم تن صدا و لهجه نباشیم.او همچنین بر اساس یک سری محاسبات پیش‌بینی کرد که ۵۰ سال بعد یعنی در سال ۲۰۰۰ انسان قادر خواهد بود کامپیوترهایی بسازد که در یک گفت‌وگوی پنج‌ دقیقه‌ای، فقط ۷۰درصد پرسشگرها بتوانند کشف کنند که در حال گفت‌وگو با یک انسان هستند یا یک ماشین. او برخورداری از یک میلیارد بیت حافظه (۱۲۵ میلیون بایت- حدود ۱۲۰ مگابایت) را یکی از مشخصه‌های اصلی این کامپیوتر دانست.تورینگ همچنین در این مقاله یک سری استدلال‌های مخالف با نظریه و آزمون خود را مطرح کرد و کوشید به آنها پاسخ دهد، تصور اینکه ماشین‌های هوشمندی ساخته شوند که بتوانند فکر کنند وحشتناک است. تورینگ در پاسخ می‌گوید این نکته‌ای انحرافی است، زیرا بحث اصلی او بایدها و نبایدها نیست بلکه بحث درباره ممکن‌هاست.

دیگر اینکه، ادعا می‌شود محدودیت‌هایی درباره نوع پرسش‌هایی که می‌توان از کامپیوتر پرسید وجود دارد، زیرا کامپیوتر از منطق خاصی پیروی می‌کند. اما تورینگ در پاسخ می‌گوید:‌ خود انسان هنگام گفت‌وگو پرغلط ظاهر می‌شود و نمی‌توان گفتار هر انسانی را لزوما منطقی کرد. او پیش‌بینی کرد که منشأ اصلی هوشمندی ماشین فرضی او، حافظه بسیار زیاد و سریعی است که یک کامپیوتر می‌تواند داشته باشد. بنابراین از نگاه تورینگ، ماشین همچون کامپیوتر Deep Blue که کاسپاروف، قهرمان شطرنج را شکست داد، می‌تواند یک ماشین هوشمند تلقی شود. در عین حال تورینگ این نظر را که {آزمون مورد بحث معتبر نیست، زیرا انسان دارای احساسات است و مثلا موسیقی دراماتیک می‌سازد} رد کرد و گفت: هنوز هیچ سند قابل قبولی وجود ندارد که ثابت کند فقط ما انسان‌ها دارای احساسات هستیم، زیرا مشخص نیست مفهوم دقیق این واژه به لحاظ علمی چیست.

در سال ۱۹۵۶ جان مک‌ کارتی، یکی از نظریه‌پردازان پیشگام این نظریه در آن زمان، اصطلاح (هوشمند مصنوعی) را برای اولین‌بار در نخستین کنفرانسی که به این موضوع اختصاص یافته بود، به کار برد. او همچنین زبان‌ برنامه‌نویس Lisp را ابداع کرد که در همین زمینه کاربرد دارد. دانشمندان بعدا این تاریخ را به عنوان تاریخ تولد علم هوش مصنوعی انتخاب کردند. تقریبا در همان زمان جان فون نیومان نظریه بازی‌ها را معرفی کرد. این نظریه نقش موثری در پیشبرد جنبه‌های نظری و علمی هوش مصنوعی داشت. چند سال بعد، در سال ۱۹۶۸ آرتور سرکلارک، در رمان معروف خود، یعنی اودیسه فضایی ۲۰۰۱ اصطلاح (آزمون تورینگ) را به جای (بازی‌ تقلید)‌ سر زبان‌ها انداخت. از زمانی که تورینگ این فرضیه را مطرح کرده است، هزاران دانشمند با هدف ساختن ماشینی که بتواند آزمون تورینگ را با موفقیت تمام کند، دست به کار شده‌اند. اما هنوز کسی موفق نشده است چنین ماشینی بسازد و پیش‌بینی تورینگ هم درست از آب در نیامده است.

● چالش‌های بنیادین هوش مصنوعی 

البته امروزه هوش مصنوعی به واقعیت نزدیک شده است و تقریبا می‌توان گفت وجود دارد اما دلایل اصلی متعددی وجود دارد که نشان می‌دهند چرا هنوز شکل تکامل یافته هوش که تورینگ تصور می‌کرد، به وقوع نپیوسته است. یکی از مهم‌ترین مباحث مطرح در این زمینه، موضوع شبیه‌سازی است. غالبا پرسیده می‌شود آیا صرف اینکه ماشین بتواند نحوه صحبت کردن انسان را شبیه‌سازی کند، به معنی آن است که هوشمند است؟ به عنوان مثال، شاید شما هم درباره روبات‌های نرم‌افزاری که می‌توانند چت کنند چیزهایی شنیده باشید. این روبات‌ها از روش‌های تقلیدی استفاده می‌کنند و به تعبیری نمونه مدرن و اینترنتی آزمون تورینگ هستند. مثلا روبات Eliza یکی از اینهاست. این روبات را ژزف وایزن‌بام، یکی دیگر از پژوهشگران نامدار این حوزه اختراع کرد. الیزا در برخی مکالمات ساده می‌تواند طرف مقابل خود را به اشتباه بیندازد طوری که مخاطب ممکن است فکر کند در حال گپ‌زدن با یک انسان است. البته الیزا هنوز نتوانسته است آزمون تورینگ را با موفقیت پشت سر بگذارد.

 

● شاخه‌های علم هوش مصنوعی 

امروزه دانش مدرن هوش مصنوعی به دو دسته تقسیم می‌شود:‌چ
ا) هوش مصنوعی سمبلیک یا نمادین Symbolic Ai
۲) هوش غیر سمبلیک یا پیوندگرا Connection Ai
هوش مصنوعی سمبلیک از رهیافتی مبتنی بر محاسبات آماری پیروی می‌کند و اغلب تحت عنوان «یادگیری ماشین» یا Machune Learning طبقه‌بندی می‌شود. هوش سمبلیک می‌کوشد سیستم و قواعد آن را در قالب سمبل‌ها بیان کند و با نگاشت اطلاعات به سمبل‌ها و قوانین به حل مسئله بپردازد. در میان معروف‌ترین شاخه‌های هوش مصنوعی سمبلیک می‌توان به سیستم‌های خبره (Expert Systems) و شبکه‌های Bayesian اشاره کرد. اما هوش پیوندگرا متکی بر یک منطق استقرایی است و از رهیافت «آموزش/ بهبود سیستم از طریق تکرار» بهره می‌گیرد. این آموزش‌ها نه بر اساس نتایج و تحلیل‌های دقیق آماری، بلکه مبتنی بر شیوه آزمون و خطا و «یادگیری از راه تجربه»‌ است. در هوش مصنوعی پیوندگرا، قواعد از ابتدا در اختیار سیستم قرار نمی‌گیرد، بلکه سیستم از طریق تجربه، خودش قوانین را استخراج می‌کند.
متدهای ایجاد شبکه‌های عصبی (Network Neural) و نیز به کارگیری منطق فازی (Fuzzy Logic) در این دسته قرار می‌گیرد.برای درک بهتر تفاوت میان دو شیوه به یک مثال توجه کنید. فرض کنید می‌خواهیم یک سیستم OCR بسازیم. سیستم OCR نرم‌افزاری است که پس از اسکن کردن یک تکه نوشته روی کاغذ می‌تواند متن روی آن را استخراج کند و به کاراکترهای متنی تبدیل نماید. بدیهی است که چنین نرم‌افزاری به نوعی هوشمندی نیاز دارد. این هوشمندی را با دو رهیافت متفاوت می‌توان فراهم کرد. اگر از روش سمبلیک استفاده کنیم، قاعدتا باید الگوی هندسی تمام حروف و اعداد را در حالت‌های مختلف در بانک اطلاعاتی سیستم تعریف کنیم و سپس متن اسکن‌شده را با این الگوها مقایسه کنیم تا بتوانیم متن را استخراج نماییم.روش دوم یا متد «پیوندگرا» این است که سیستم هوشمند سمبلیک درست کنیم و متن‌های متعددی را یک به یک به آن بدهیم تا آرام‌آرام آموزش ببیند و سیستم را بهینه کند.
در اینجا سیستم هوشمند می‌تواند مثلا یک شبکه عصبی یا مدل مخفی مارکوف باشد. در این شیوه سمبل‌ها پایه هوشمندی نیستند، بلکه فعالیت‌های سلسله اعصاب یک شبکه و چگونگی پیوند میان آنها مبنای هوشمندی را تشکیل می‌دهند. در طول دهه ۱۹۶۰ و ۱۹۷۰ به دنبال ابداع اولین برنامه نرم‌افزاری موفق در گروه سیستم‌های مبتنی بر دانش (Knowledge- based) توسط جوئل موزس، سیستم‌های هوش سمبلیک به یک جریان مهم تبدیل شد. ایده و مدل‌های شبکه‌های عصبی ابتدا در دهه ۱۹۴۰ توسط «Walter pitts, Warren McCulloch» معرفی شد.

سپس در دهه ۱۹۵۰ کارهای روزنبالت (Rosenblatt) در مورد شبکه‌های دو لایه مورد توجه قرار گرفت. در دهه ۱۹۴۷ الگوریتم backpropagation توسط Werbos معرفی شد ولی متدولوژی شبکه‌های عصبی عمدتا از دهه ۱۹۸۰ به این سو رشد زیادی کرد و مورد استقبال دانشمندان قرار گرفت. منطق‌ فازی ابتدا توسط پروفسور لطفی‌زاده،‌ در سال ۱۹۶۵ معرفی شد و از آن زمان به بعد توسط خود او و دیگر دانشمندان دنبال شد.در دهه ۱۹۸۰ تلاش‌های دانشمندان ژاپنی برای کاربردی کردن منطق فازی به ترویج و معرفی منطق فازی کمک زیادی کرد. مثلا طراحی و شبیه‌سازی سیستم کنترل فازی برای راه‌آهن Sendiaتوسط دو دانشمند به نام‌های Yasunobo و Miyamoto در سال ۱۹۸۵، نمایش کاربرد سیستم‌های کنترل فازی از طریق چند تراشه‌ مبتنی بر منطق فازی در آزمون «پاندول معکوس» توسطTakeshi Yamakawa در همایش بین‌المللی پژوهشگران منطق فازی در توکیو در سال ۱۹۸۷ و نیز استفاده از سیستم‌های فازی در شبکه مونوریل توکیو و نیز معرفی سیستم ترمز ABS مبتنی بر کنترل‌های فازی توسط اتومبیل‌‌سازی هوندا در همین دهه تاثیر زیادی در توجه مجدد دانشمندان جهان به این حوزه از علم داشت.

 

● فراتر از هوشمندی ماشین

چنان که گفتیم، هوش مصنوعی دانش و مهندسی ساختن ماشین‌های هوشمند، به ویژه کامپیوترهای هوشمند است. اما به‌راستی هوشمند چیست؟ در واقع هنوز دانشمندان نتوانسته‌اند تعریف واحدی از هوشمندی ارائه دهند که مستقل از «هوش انسان» باشد. ما می‌دانیم که برخی از ماشین‌ها یا جانداران می‌توانند هوشمند باشند، اما بشر هنوز نمی‌داند که مایل است کدام دسته از فرآیندهای محاسباتی یا پردازش را هوشمندی بنامد. بنابراین برای پاسخ دادن به این پرسش که «آیا فلان ماشین هوشمند است؟» هنوز فرمول مشخصی وجود ندارد، در واقع هوشمندی، خود یک مفهوم‌ فازی و نادقیق است. هوشمندی را می‌توان فرآیندی تلقی کرد که دانشمندان هنوز در حال شبیه‌سازی، تحلیل و حتی تعریف مشخصه‌های آن هستند.

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

/fa.wikipedia.org

http://www.meta4u.com

http://www.meta4u.com

 

 

/0 دیدگاه /توسط

خوشه بندی k میانگین (k-means Clustering) قسمت 2

معایب و مزایای خوشه‌بندی k-میانگین

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

به منظور ارزیابی نتایج خوشه‌بندی از معیارهای متفاوتی کمک گرفته می‌شود. ممکن است از قبل برچسب خوشه‌ها مشخص باشد و بخواهیم کارایی الگوریتم را با توجه به مقایسه برچسب‌های واقعی و حاصل از خوشه‌بندی، اندازه‌گیری کنیم. در این حالت، شاخص‌های ارزیابی بیرونی، بهترین راهنما و معیار برای سنجش صحت نتایج خوشه‌بندی محسوب می‌شوند. معمولا به این برچسب‌ها، استاندارد طلایی (Golden Standard) و در کل چنین عملی را ارزیابی Benchmark می‌گویند. برای مثال شاخص رَند (Rand Index) یکی از این معیارها و شاخص‌های بیرونی است که از محبوبیت خاصی نیز برخوردار است.

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

منبع

KMeans شاید ساده‌ترین الگوریتمِ خوشه‌بندی باشد که در بسیاری از مواقع جزوِ بهترین الگوریتم‌های خوشه‌بندی نیز هست. این الگوریتم از دسته الگوریتم‌هایی است که بایستی تعداد خوشه‌ها (گروه ها) را از قبل به او گفته باشیم. فرض کنید یک سری داده داریم و مانندِ درسِ شبکه های عصبی دو دسته داده داریم (پراید و اتوبوس) با این تفاوت که در یک مسئله‌ی خوشه‌بندی، نمی‌دانیم که کدام پراید است کدام اتوبوس؟ و فقط یک سری داده با دو ویژگی (طول ماشین و ارتفاع ماشین) در اختیار داریم. اجازه دهید اینبار این دو دسته را بدون دانستنِ برچسبِ آن ها بر روی نمودار رسم کنیم (برای اینکه بدانید چگونه این نمودار رسم می شود و بُعدهای مختلف آن چگونه ساخته می‌شود، درسِ شبکه‌ی عصبی را خوانده باشید) به صورت ساده، ما یک تعداد ماشین (اتومبیل) داریم که هر کدام ارتفاع و طولِ مشخصی را دارند. آن‌ها را به این گونه در دو بُعد در شکلِ زیر نمایش می‌دهیم):

برای مثال، ماشین شماره‌ی ۴#، دارای طولِ ۹ و ارتفاع ۴ است. در الگوریتمِ KMeans بایستی تعدادی نقطه در فضا ایجاد کنیم. تعداد این نقاط باید به تعداد خوشه‌هایی که می‌خواهیم در نهایت به آن برسیم، باشد (مثلا فرض کنید می‌خواهیم داده‌ها را به ۲خوشه تقسیم‌بندی کنیم، پس ۲نقطه به صورت تصادفی در فضای ۲بُعدیِ شکلِ بالا رسم می‌کنیم). شکل زیر را نگاه کنید:

الان ما دو نقطه‌ی سبز و قرمز انتخاب کردیم و این دو نقطه را جایی در فضا (به صورت تصادفی) قرار دادیم. حال فاصله‌ی هر کدام از نمونه‌ها را (۷ماشین) با این دو نقطه حساب می‌کنیم. برای این کار می‌توانیم از فاصله منهتن (Manhatan) استفاده کنیم. در واقع برای هر کدام از نمونه‌ها نسبت به دو نقطه‌ی سبز و قرمز در هر بُعد، با هم مقایسه کرده و از هم کم (تفاضل) میکنیم، سپس نتیجه‌ی کم کردنِ هر کدام از بُعد ها را با یکدیگر جمع میکنیم.

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

الان یک مرحله از الگوریتم را تمام کرده ایم. یعنی یک دور از الگوریتم تمام شد و می‌توانیم همین جا هم الگوریتم را تمام کنیم و نقاطی که سبز رنگ شده اند را در خوشه‌ی سبزها و نقاطی که قرمز رنگ شده‌اند را در خوشه‌ی قرمز‌ها قرار دهیم. ولی الگوریتمِ KMeans را بایستی چندین مرتبه تکرار کرد. ما هم همین کار را انجام می‌دهیم. برای شروعِ مرحله‌ی بعد، باید نقطه‌ی سبز و قرمز را جا‌به‌جا کنیم و به جایی ببریم که میانگینِ نمونه‌های مختلف در خوشه‌ی مربوط به خودشان قرار دارد. یعنی مثلا برای نقطه قرمز بایستی نقطه را به جایی ببریم که میانگینِ نمونه‌های قرمزِ دیگر (در مرحله‌ی قبلی) باشد. برای نقطه سبز هم همین طور. این کار را در شکل زیر انجام داده‌ایم:

الان دو نقطه قرمز و سبز جا‌به‌جا شدند. حال بایستی دوباره تمامیِ نمونه‌ها را هر کدام با دو نقطه‌ی سبز و قرمز مقایسه کنیم و مانند دور قبلی، آن نمونه‌هایی که به نقطه‌ی قرمز نزدیک‌تر هستند، خوشه‌ی قرمز و آن هایی که به نقطه‌ی سبز نزدیک هستند رنگِ سبز می‌گیرند. مانند شکل زیر:

دورِ دوم نیز به اتمام رسید و به نظرْ الگوریتم خوشه‌های خوبی را تشخیص داد. ولی اجازه بدهید یک دور دیگر نیز الگوریتم را ادامه دهیم. مانند شکل زیر دور سوم را انجام می شود (یعنی نقاطِ قرمز و سبز به مرکز خوشه‌ی خود (در مرحله‌ی قبلی) می‌روند و فاصله‌ی هر کدام از نمونه‌ها دوباره با نقاطِ قرمز و سبز (در محلِ جدید) محاسبه شده و هر کدام همرنگِ نزدیک‌ترین نقطه‌ی قرمز یا سبز می‌شود):

همان طور که می‌بینید در انتهای دورِ سوم، تغییری در خوشه‌ی هر کدام از نمونه‌ها رخ نداد. یعنی سبزها سبز ماندند و قرمزها، قرمز.این یکی از شروطی است که می‌تواند الگوریتم را خاتمه دهد. یعنی الگوریتمْ وقتی به این حالت رسید که در چند دورِ متوالی تغییری در خوشه‌ی نمونه‌ها (در این‌جا ماشین‌ها) به وجود نیامد، یعنی الگوریتمْ دیگر نمی‌تواند زیاد تغییر کند و این حالتِ پایانی برای خوشه‌هاست. البته می‌توان شرطی دیگر نیز برای پایان الگوریتم در نظر گرفت. برای مثال الگوریتمْ حداکثر در ۲۰دورِ متوالی می‌تواند عملیات را انجام دهد و دورِ ۲۰ام آخرین دورِ الگوریتم خواهد بود و الگوریتم دیگر بیشتر از آن پیشروی نخواهد کرد. به طور کل در الگوریتم‌های مبتنی بر دور (Iterative Algorithms) می‌توان تعدادِ دورها را محدود کرد تا الگوریتمْ بی‌نهایت دور نداشته باشد.

همان طور که دیدیم، این الگوریتم می‌تواند یک گروه‌بندیِ ذاتی برای داده‌ها بسازد، بدون اینکه برچسب داده‌ها یا نوع آن‌ها را بداند.

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

منبع

مروری بر الگوریتم K-Means

خوشه‌بندی داده‌ها رو بر اساس شباهتی که دارن، به طوری که داده‌های هر خوشه دارای بیشترین شباهت به هم و کم‌ترین شباهت به داده‌های خوشه‌های دیگه هستن، در یک خوشه قرار میده. الگوریتم K-Means یکی از الگوریتم‌های مورد استفاده در داده کاوی و یادگیری ماشینی هست که برای خوشه‌بندی(Clustering) یا دسته‌بندی بدون نظارت از اون استفاده میشه. در ادامه نحوه کار این الگوریتم رو با یک مثال و پیاده‌سازی اون به کمک زبان جاوا توضیح میدم.

برای مشخص کردن شباهت داده‌ها از معیار و راه‌های مختلفی استفاده میشه که یکی از اونا فاصله اقلیدسی هست و در این‌جا هم ما از اون استفاده می‌کنیم.

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

در شکل زیر نمونه‌ای از خوشه‌بندی نشون داده شده که در اون داده‌ها به سه خوشه تقسیم‌ و به کمک سه رنگ نمایش داده شدن.

برای درک بهتر نحوه کار الگوریتم K-Means از مثال زیر استفاده می‌کنم:

فرض می‌کنیم که مجموعه داده‌ای داریم که شامل هر ۷ رکورد هست و همه رکوردهای اون ۲ ویژگی یا خصوصیت A و B رو دارن. (دز این‌جا میتونیم این ویژگی‌ها رو به عنوان طول و عرض در یک صفحه دو بعدی در نظر بگیریم)

رکورد A B
۱ ۱.۰ ۱.۰
۲ ۱.۵ ۲.۰
۳ ۳.۰ ۴.۰
۴ ۵.۰ ۷.۰
۵ ۳.۵ ۵.۰
۶ ۴.۵ ۵.۰
۷ ۳.۵ ۴.۵

فرض می‌کنیم که قراره داده‌ها به ۲ خوشه تقسیم بشن. پس برای این منظور به صورت تصادفی ۲ رکورد رو به عنوان مرکز این ۲ خوشه در نظر می‌گیریم.

رکورد مختصات
خوشه ۱ ۱ (۱.۰ و ۱.۰)
خوشه ۲ ۴ (۷.۰ و ۵.۰)

در ادامه الگوریتم داده‌ها رو به خوشه‌ای که فاصله اقلیدسی کمتری تا مرکز اون داره اختصاص میده. و هربار که داده جدیدی رو به یک خوشه اضافه می‌کنه مرکز اون خوشه رو هم دوباره محاسبه و مشخص میکنه.

خوشه ۱ خوشه ۲
گام رکورد مرکز خوشه رکورد مرکز خوشه
۱ ۱ (۱.۰ و ۱.۰) ۴ (۷.۰ و ۵.۰)
۲ ۱ و ۲ (۱.۵ و ۱.۲) ۴ (۷.۰ و ۵.۰)
۳ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ (۷.۰ و ۵.۰)
۴ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ (۶.۰ و ۴.۲)
۵ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ و ۶ (۵.۷ و ۴.۳)
۶ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ و ۶ و ۷ (۵.۴ و ۴.۱)

پس در ادامه مرکزهای خوشه‌ها به صورت زیر در میان.

رکورد مرکز خوشه
خوشه ۱ ۱ و ۲ و ۳ (۲.۳ و ۱.۸)
خوشه ۲ ۴ و ۵ و ۶ و ۷ (۵.۴ و ۴.۱)

در ادامه فاصله داده‌ها تا این مرکز‌های خوشه‌های جدید به شکل جدول زیر در میان.

رکورد فاصله تا خوشه ۱ فاصله تا خوشه ۲
۱ ۱.۵ ۵.۴
۲ ۰.۴ ۴.۳
۳ ۲.۱ ۱.۸
۴ ۵.۷ ۱.۸
۵ ۳.۲ ۰.۷
۶ ۳.۸ ۰.۶
۷ ۲.۸ ۱.۱

در نتیجه و بر اساس این مراحل و اطلاعات مشاهده می‌کنیم رکورد ۳ که مربوط به خوشه ۱ بوده، فاصلش تا مرکز خوشه ۲ کمتر میشه. پس این رکورد رو باید به خوشه ۲ اختصاص بدیم.

رکورد مرکز خوشه
خوشه ۱ ۱ و ۲ خوشه ۱
خوشه ۲ ۳ و ۴ و ۵ و ۶ و ۷ خوشه ۲

و کل این فرایند و مراحل تا زمانی انجام میشه که تغییر و جابجایی در خوشه‌ها اتفاق نیفته.

این الگوریتم رو به راحتی و به کمک زبان‌های برنامه‌نویسی مختلفی میشه پیاده‌سازی کرد و در ادامه من پیاده‌سازی این الگوریتم رو برای همین مثال و به زبان جاوا و پایتون در این‌جا شرح میدم.

پیاده‌سازی الگوریتم  K-Means به زبان Java

 

import java.util.ArrayList;
public class KMeans_Ex {
    private static final int NUM_CLUSTERS = 2;    // Total clusters.
    private static final int TOTAL_DATA = 7;      // Total data points.
    private static final double SAMPLES[][] = new double[][]{{1.0, 1.0},
            {1.5, 2.0},
            {3.0, 4.0},
            {5.0, 7.0},
            {3.5, 5.0},
            {4.5, 5.0},
            {3.5, 4.5}};
    private static ArrayList    &amp;amp;lt; Data &amp;amp;gt;    dataSet = new ArrayList   &amp;amp;lt; Data &amp;amp;gt;  ();
    private static ArrayList   &amp;amp;lt; Centroid &amp;amp;gt;    centroids = new ArrayList   &amp;amp;lt; Centroid &amp;amp;gt;  ();
    private static void initialize() {
        System.out.println(&amp;quot;Centroids initialized at:&amp;quot;);
        centroids.add(new Centroid(1.0, 1.0)); // lowest set.
        centroids.add(new Centroid(5.0, 7.0)); // highest set.
        System.out.println(&amp;quot;     (&amp;quot; + centroids.get(0).X() + &amp;quot;, &amp;quot; + centroids.get(0).Y() + &amp;quot;)&amp;quot;);
        System.out.println(&amp;quot;     (&amp;quot; + centroids.get(1).X() + &amp;quot;, &amp;quot; + centroids.get(1).Y() + &amp;quot;)&amp;quot;);
        System.out.print(&amp;quot;\n&amp;quot;);
        return;
    }
    private static void kMeanCluster() {
        final double bigNumber = Math.pow(10, 10);    // some big number that's sure to be larger than our data range.
        double minimum = bigNumber;                   // The minimum value to beat.
        double distance = 0.0;                        // The current minimum value.
        int sampleNumber = 0;
        int cluster = 0;
        boolean isStillMoving = true;
        Data newData = null;
        // Add in new data, one at a time, recalculating centroids with each new one.
        while (dataSet.size()  &amp;amp;lt;  TOTAL_DATA) {
            newData = new Data(SAMPLES[sampleNumber][0], SAMPLES[sampleNumber][1]);
            dataSet.add(newData);
            minimum = bigNumber;
            for (int i = 0; i  &amp;amp;lt;  NUM_CLUSTERS; i++) {
                distance = dist(newData, centroids.get(i));
                if (distance &amp;amp;lt; minimum) {
                    minimum = distance;
                    cluster = i;
                }
            }
            newData.cluster(cluster);
            // calculate new centroids.
            for (int i = 0; i  &amp;amp;lt;  NUM_CLUSTERS; i++) {
                int totalX = 0;
                int totalY = 0;
                int totalInCluster = 0;
                for (int j = 0; j   &amp;amp;lt; dataSet.size(); j++) { if (dataSet.get(j).cluster() == i) { totalX += dataSet.get(j).X(); totalY += dataSet.get(j).Y(); totalInCluster++; } } if (totalInCluster &amp;amp;gt;    0) {
                    centroids.get(i).X(totalX / totalInCluster);
                    centroids.get(i).Y(totalY / totalInCluster);
                }
            }
            sampleNumber++;
        }
        // Now, keep shifting centroids until equilibrium occurs.
        while (isStillMoving) {
            // calculate new centroids.
            for (int i = 0; i  &amp;amp;lt;  NUM_CLUSTERS; i++) {
                int totalX = 0;
                int totalY = 0;
                int totalInCluster = 0;
                for (int j = 0; j   &amp;amp;lt; dataSet.size(); j++) { if (dataSet.get(j).cluster() == i) { totalX += dataSet.get(j).X(); totalY += dataSet.get(j).Y(); totalInCluster++; } } if (totalInCluster &amp;amp;gt;   0) {
                    centroids.get(i).X(totalX / totalInCluster);
                    centroids.get(i).Y(totalY / totalInCluster);
                }
            }
            // Assign all data to the new centroids
            isStillMoving = false;
            for (int i = 0; i   &amp;amp;lt;   dataSet.size(); i++) {
                Data tempData = dataSet.get(i);
                minimum = bigNumber;
                for (int j = 0; j   &amp;amp;lt;   NUM_CLUSTERS; j++) {
                    distance = dist(tempData, centroids.get(j));
                    if (distance   &amp;amp;lt;   minimum) {
                        minimum = distance;
                        cluster = j;
                    }
                }
                tempData.cluster(cluster);
                if (tempData.cluster() != cluster) {
                    tempData.cluster(cluster);
                    isStillMoving = true;
                }
            }
        }
        return;
    }
    /**
     * // Calculate Euclidean distance.
     *
     * @param d - Data object.
     * @param c - Centroid object.
     * @return - double value.
     */
    private static double dist(Data d, Centroid c) {
        return Math.sqrt(Math.pow((c.Y() - d.Y()), 2) + Math.pow((c.X() - d.X()), 2));
    }
    private static class Data {
        private double mX = 0;
        private double mY = 0;
        private int mCluster = 0;
        public Data() {
            return;
        }
        public Data(double x, double y) {
            this.X(x);
            this.Y(y);
            return;
        }
        public void X(double x) {
            this.mX = x;
            return;
        }
        public double X() {
            return this.mX;
        }
        public void Y(double y) {
            this.mY = y;
            return;
        }
        public double Y() {
            return this.mY;
        }
        public void cluster(int clusterNumber) {
            this.mCluster = clusterNumber;
            return;
        }
        public int cluster() {
            return this.mCluster;
        }
    }
    private static class Centroid {
        private double mX = 0.0;
        private double mY = 0.0;
        public Centroid() {
            return;
        }
        public Centroid(double newX, double newY) {
            this.mX = newX;
            this.mY = newY;
            return;
        }
        public void X(double newX) {
            this.mX = newX;
            return;
        }
        public double X() {
            return this.mX;
        }
        public void Y(double newY) {
            this.mY = newY;
            return;
        }
        public double Y() {
            return this.mY;
        }
    }
    public static void main(String[] args) {
        initialize();
        kMeanCluster();
        // Print out clustering results.
        for (int i = 0; i    &amp;amp;lt;    NUM_CLUSTERS; i++) {
            System.out.println(&amp;quot;Cluster &amp;quot; + i + &amp;quot; includes:&amp;quot;);
            for (int j = 0; j    &amp;amp;lt;    TOTAL_DATA; j++) {
                if (dataSet.get(j).cluster() == i) {
                    System.out.println(&amp;quot;     (&amp;quot; + dataSet.get(j).X() + &amp;quot;, &amp;quot; + dataSet.get(j).Y() + &amp;quot;)&amp;quot;);
                }
            } // j
            System.out.println();
        } // i
        // Print out centroid results.
        System.out.println(&amp;quot;Centroids finalized at:&amp;quot;);
        for (int i = 0; i    &amp;amp;lt;    NUM_CLUSTERS; i++) {
            System.out.println(&amp;quot;     (&amp;quot; + centroids.get(i).X() + &amp;quot;, &amp;quot; + centroids.get(i).Y() + &amp;quot;)&amp;quot;);
        }
        System.out.print(&amp;quot;\n&amp;quot;);
        return;
    }

 

پیاده‌سازی الگوریتم K-Means به زبانPython

 

import math
NUM_CLUSTERS = 2
TOTAL_DATA = 7
LOWEST_SAMPLE_POINT = 0  # element 0 of SAMPLES.
HIGHEST_SAMPLE_POINT = 3  # element 3 of SAMPLES.
BIG_NUMBER = math.pow(10, 10)
SAMPLES = [[1.0, 1.0], [1.5, 2.0], [3.0, 4.0], [5.0, 7.0], [3.5, 5.0], [4.5, 5.0], [3.5, 4.5]]
data = []
centroids = []
class DataPoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def set_x(self, x):
        self.x = x
    def get_x(self):
        return self.x
    def set_y(self, y):
        self.y = y
    def get_y(self):
        return self.y
    def set_cluster(self, clusterNumber):
        self.clusterNumber = clusterNumber
    def get_cluster(self):
        return self.clusterNumber
class Centroid:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def set_x(self, x):
        self.x = x
    def get_x(self):
        return self.x
    def set_y(self, y):
        self.y = y
    def get_y(self):
        return self.y
def initialize_centroids():
    # Set the centoid coordinates to match the data points furthest from each other.
    # In this example, (1.0, 1.0) and (5.0, 7.0)
    centroids.append(Centroid(SAMPLES[LOWEST_SAMPLE_POINT][0], SAMPLES[LOWEST_SAMPLE_POINT][1]))
    centroids.append(Centroid(SAMPLES[HIGHEST_SAMPLE_POINT][0], SAMPLES[HIGHEST_SAMPLE_POINT][1]))
    print(&amp;quot;Centroids initialized at:&amp;quot;)
    print(&amp;quot;(&amp;quot;, centroids[0].get_x(), &amp;quot;, &amp;quot;, centroids[0].get_y(), &amp;quot;)&amp;quot;)
    print(&amp;quot;(&amp;quot;, centroids[1].get_x(), &amp;quot;, &amp;quot;, centroids[1].get_y(), &amp;quot;)&amp;quot;)
    print()
    return
def initialize_datapoints():
    # DataPoint objects' x and y values are taken from the SAMPLE array.
    # The DataPoints associated with LOWEST_SAMPLE_POINT and HIGHEST_SAMPLE_POINT are initially
    # assigned to the clusters matching the LOWEST_SAMPLE_POINT and HIGHEST_SAMPLE_POINT centroids.
    for i in range(TOTAL_DATA):
        newPoint = DataPoint(SAMPLES[i][0], SAMPLES[i][1])
        if (i == LOWEST_SAMPLE_POINT):
            newPoint.set_cluster(0)
        elif (i == HIGHEST_SAMPLE_POINT):
            newPoint.set_cluster(1)
        else:
            newPoint.set_cluster(None)
        data.append(newPoint)
    return
def get_distance(dataPointX, dataPointY, centroidX, centroidY):
    # Calculate Euclidean distance.
    return math.sqrt(math.pow((centroidY - dataPointY), 2) + math.pow((centroidX - dataPointX), 2))
def recalculate_centroids():
    totalX = 0
    totalY = 0
    totalInCluster = 0
    for j in range(NUM_CLUSTERS):
        for k in range(len(data)):
            if (data[k].get_cluster() == j):
                totalX += data[k].get_x()
                totalY += data[k].get_y()
                totalInCluster += 1
        if (totalInCluster    &amp;gt;     0):
            centroids[j].set_x(totalX / totalInCluster)
            centroids[j].set_y(totalY / totalInCluster)
    return
def update_clusters():
    isStillMoving = 0
    for i in range(TOTAL_DATA):
        bestMinimum = BIG_NUMBER
        currentCluster = 0
        for j in range(NUM_CLUSTERS):
            distance = get_distance(data[i].get_x(), data[i].get_y(), centroids[j].get_x(), centroids[j].get_y())
            if (distance     &amp;lt;     bestMinimum):
                bestMinimum = distance
                currentCluster = j
        data[i].set_cluster(currentCluster)
        if (data[i].get_cluster() is None or data[i].get_cluster() != currentCluster):
            data[i].set_cluster(currentCluster)
            isStillMoving = 1
    return isStillMoving
def perform_kmeans():
    isStillMoving = 1
    initialize_centroids()
    initialize_datapoints()
    while (isStillMoving):
        recalculate_centroids()
        isStillMoving = update_clusters()
    return
def print_results():
    for i in range(NUM_CLUSTERS):
        print(&amp;quot;Cluster &amp;quot;, i, &amp;quot; includes:&amp;quot;)
        for j in range(TOTAL_DATA):
            if (data[j].get_cluster() == i):
                print(&amp;quot;(&amp;quot;, data[j].get_x(), &amp;quot;, &amp;quot;, data[j].get_y(), &amp;quot;)&amp;quot;)
        print()
    return
perform_kmeans()
print_results()

 

در این الگوریتم وقتی مرکز خوشه محاسبه میشه خیلی پیش میاد که این مرکز خوشه محاسبه‌شده در بین داده‌های واقعی موجود نباشه و صرفا یه میانگین محسوب میشه که همین موضوع باعث مقاوم نبودن این الگوریتم در برابر داده‌های پرت مبشه. برای حل این مشکل الگوریتمی پیشنهاد شده به نام K-Medoids که در این الگوریتم مرکز خوشه جدید وقتی محاسبه میشه خودش هم در بین داده‌های اصلی موجود هست. با کمی تغییر در الگوریتم K-Means می‌تونیم K-Medoids رو هم داشته باشیم.

این برنامه در سایت گیتلب قابل دسترس هست و شما می‌تونید اون رو تغییر بدین و بهترش کنید.

 

پیاده‌سازی الگوریتم KMEANS به زبان JAVA در گیتلب

پیاده‌سازی الگوریتم KMEANS به زبان PYTHON در گیتلب

منبع

/0 دیدگاه /توسط

سیستم ایمنی مصنوعی (AIS) قسمت 5

دو مثال از کاربردهای سیستم ایمنی مصنوعی

الگوريتم هاي سيستم ايمني مصنوعي در گروه الگوريتم هاي بهينه سازي اتفاقي قرار دارند كه در آنها از قوانين موجود در سيستم ايمني بيولوژيکي به منظور بهينه سازي استفاده مي شود. اين الگوريتم ها در مسائل بهينه سازي که بيش از یک بهينه مورد نظر است نسبت به الگوريتم هاي ژنتيک کارايي بيشتري از خود نشان مي دهند. به دليل اينکه هيچ اطلاع قبلي از پاسخ بهينه سراسري وجود ندارد، الگوريتم هاي سيستم ايمني مصنوعي در تعيين مناسب نرخ ابر جهش دچار مشکل هستند که از اشکالات عمده اين الگوريتم ها مي توان به همگرايي کٌند به بهينه سراسري و عدم پايداري در اجراهاي مختلف اشاره نمود.

در اولین مثال ارائه شده، هدف از ارائه مدل، محلي کردن ارتباط بين آنتي بادي ها و استفاده از دانش خبره به منظور تعيين کاراي پارامترهاي اساسي اين الگوريتم بر اساس ارزيابي محلي مي باشد که علاوه بر سرعت بخشيدن به محاسبات مي تواند باعث بهبود کيفيت نتايج بدست آمده گردد. در اين مدل با کمک توابع تعلق فازی و در نظر گرفتن خاصيت محلي براي آنتي بادي ها با استفاده از اتوماتاي سلولي، نرخ ابر جهش به صورت کارا تعیین می شود. براي اعتبار سنجي راهکار پيشنهادي شبيه-سازي هايي توسط جوادزاده و میبدی صورت گرفته که نتايج آن ها نشان مي دهد راه کار پيشنهادي پاسخ هاي به مراتب بهتري نسبت به الگوريتم استاندارد سيستم ايمني مصنوعي نتيجه مي دهد.

مثال (۱) : مدل تركيبي مبتني بر سيستم ايمني مصنوعي و اتوماتاي سلولي فازی (FCA-AIS)

الگوريتم هاي سيستم ايمني مصنوعي در گروه الگوريتم هاي بهينه سازي اتفاقي قرار دارند كه در آنها از قوانين موجود در سيستم ايمني بيولوژيکي بمنظور بهينه سازي استفاده مي شود. رفتار الگوريتم سيستم ايمني مصنوعي وابستگي شديدي به پارامترهايي نظیر نحوه تعريف و احتمال عملگرهاي ابَرجهش، اندازه جامعه ايجاد شده براي هر آنتي بادي، اندازه جمعيت ها و تعداد دوره هاي توليد شده دارد.

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

سال ۲۰۰۳ تیمیس در مقاله ” A Comment on opt-AiNET: An Immune Network Algorithm for Optimisation” براي حل اين مشكل روشي ارائه نموده که با محاسبه ميزان وابستگي تناسبي، که با نرمال کردن مقادير وابستگي هر آنتي بادي در هر مرحله زماني بدست مي آيد تا اندازه اي اين مشکل حل شده است. همچنين جوادزاده در سال ۲۰۰۸ میلادی در مقاله “Hybrid Models based on Artificial Immune systems and Cellular Automata and Their Applications to Optimization Problems” مدل ترکيبيCA-AIS را به منظور تعيين پارامترهاي اساسي براساس ارزيابي وابستگي محلي توسط مفاهیم اتوماتای سلولی ارائه نموده است. اما هدف از ارائه مدل در مثال ارائه شده ، حل اين مشكل با استفاده از روش ارزيابي وابستگي محلي و همچنين دانش خبره مي باشد.

اتوماتای سلولی

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

قوانين اتوماتاي سلولي، نحوه تأثير پذيرفتن سلول از سلول هاي همسايه خود را مشخص مي‌کند. يک سلول، همسايه سلول ديگر گفته مي شود هرگاه بتواند آن را در يک مرحله و براساس قانون حاکم تحت تأثير قرار دهد.

اتوماتاي سلولي فازی

مشکل عمده در مدلسازی سيستم هاي پيچيده توسط اتوماتاي سلولي، اين است که نمي‏توان رابطه دقيقي بين عمل و عکس‏ العمل رفتارهاي طبيعي تعريف کرد. تعريف دقيق رفتار سيستم مستلزم دانش دقيق از حالت هاي سيستم و تغيير حالت سيستم تحت ورودي هاي مختلف است. براي مقابله با اين مشکل راهبرد منطق فازي را مورد استفاده قرار مي ‏دهند، كه با استفاده از آن مي‏توان کميت هاي غير دقيق و مبهمي که در تصميم‏گيري درباره قوانين انتقال و تغيير حالت هاي سيستم موثرند را تعريف نمود.

با توجه به توانايي منطق فازي در پردازش داده هاي غير قطعي، ساختاري از CA معرفي شده است که در آن به جاي استفاده از مقادير قطعي در سلول ها و توابع انتقال شان از مقادير غير قطعي و فازي استفاده مي شود. تعاريف متفاوتي از اتوماتاي سلولي فازي ارائه شده است که هر يک باعث ايجاد ويژگيها و رفتار خاصي در اتوماتاي سلولي فازي مي شود.

مدل ترکيبي مبتنی بر سيستم ايمني مصنوعي و اتوماتاي سلولي فازي(FCA-AIS)

در روش پيشنهادي از اتوماتاي سلولي فازي به منظور تعيين مقادير مناسب نرخ ابر جهش براي آنتي بادي ها استفاده مي شود. قوانين فازي در هر سلول اتوماتاي سلولي فازي عهده دار تعيين مقدار مناسب نرخ ابر جهش براي آنتي بادي ها متناظر با آن سلول مي باشد. در واقع اتوماتاي سلولي فازي تعيين مي کند که براي کدام آنتي بادي ها نرخ ابرجهش بايستي پايين و براي کدام آنتي بادي ها نرخ ابرجهش بايستي بالا در نظر گرفته شود. براي اين منظور در موقعيت هايي كه ميزان وابستگي آنتي بادي ها نسبت به وابستگي بهترين آنتي بادي در همسايگي از ارزش بالايي برخوردار نيست بايد از مقادير بالا براي نرخ ابرجهش استفاده نمود و در مقابل در موقعيت هايي كه ميزان وابستگي آنتي بادي ها نسبت به وابستگي بهترين آنتي بادي در همسايگي از ارزش بالايي برخوردار است بايد از مقادير پايين براي نرخ ابر جهش آن آنتي بادي استفاده نمود.

هدف از ارائه اين مدل استفاده از مفاهيم اتوماتاي سلولي فازی است تا نرخ ابر جهش بطور مناسب و کارا انتخاب شود. همچنين با استفاده از مفاهيم توزيعي و توازي اتوماتاي سلولي، مي توان محاسبات را در اين مدل پيشنهادي به صورت موازي انجام داد. براي تعيين نرخ ابر جهش از يک اتوماتاي سلولي دو بعدي استفاده مي شود. هر آنتي بادي ها در سيستم ايمني مصنوعي به يکي از سلولهاي اتوماتاي سلولي فازي نگاشت مي شود (تصویر زیر).در اين مدل از همسايگي ون-نيومن با شعاع همسايگي يک استفاده شده است.

 

همسایگی ون نیومن

 

در تصویری که در زیر آورده شده نمايي از يک سلول را در مدل ترکيبي پيشنهادي به تصوير کشيده شده است. به دليل اينکه هيچ اطلاع قبلي از پاسخ بهينه سراسري وجود ندارد، الگوريتم هاي سيستم ايمني مصنوعي در تعيين مناسب نرخ ابر جهش دچار مشکل هستند. ايده اصلي اين راه کار اينست که از ارزيابي وابستگي محلي بصورت فازي استفاده شود. به منظور استفاده از دانش خبره، تئوري مجموعه هاي فازي و منطق فازي ابزار قدرتمندي براي ارائه و پردازش دانش بشري به شکل قوانين اگر-آنگاه فازي مي باشند.

نمایی از یک سلول در مدل ترکیبی FCA-AIS

براي تعيين نرخ ابر جهش با استفاده از FCA نياز به مشخص نمودن کيفيت وابستگي آنتي بادي ها، وجود دارد. براي اين منظور، از ميزان تعلق وابستگي آنتي بادي به مجموعه هاي فازي Near و Far استفاده مي شود که در نمودار ۱ نشان داده شده است. مرکز اين مجموعه ها بر ميزان وابستگي بهترين آنتي بادي در همسايگي آن آنتي بادي  منطبق شده است و ميزان ابر جهش بر اساس رابطه های (۱) و (۲) تعيين مي شود.

رابطه (۱) : If Affinity is Near then Mutatin is Low
رابطه (۲) : If Affinity is Far then Mutatin is High

 

توابع عضویت Near و Far

نمودار ۱ – توابع عضويت Near و Far

در توابع عضويت مجموعه هاي فازي Near و Far (نمودار ۱) ، Ab* بهترين آنتي بادي در همسايگي آنتي بادي مورد پردازش مي باشد، همچنين مقدار α برابر با قدرمطلق تفاضل بهترين و بدترين آنتي بادي  در همسايگي آنتي بادي  مورد نظر است. اين امر باعث مي شود دامنه توابع عضويت مجموعه هاي فازيNear و Far در روند تکاملي راه کار پيشنهادي به صورت پويا خود را با شرايط محيط وفق دهند. توابع عضويت Low و High در نمودار ۲ آمده است و نقاط a، b، c و d به ترتيب برابر مقادیر ۰، ۱ ، ۲ و ۳ انتخاب شده اند.

 

نمودار ۲ – توابع عضويت Low و Highنمودار ۲ – توابع عضويت Low و High

 

نتایج آزمایش ها

در اين بخش نتايج شبيه سازي سيستم ايمني مصنوعي مبتني بر اتوماتاي سلولي فازی (FCA-AIS)براي چهار تابع محك استاندارد (روابط ۳ تا ۶) که دارای بهینه سراسری در صفر است به ازاء كيفيت جواب بدست آمده در مقابل مدل ترکیبی سيستم ايمني مصنوعي ، اتوماتای سلولی و الگوريتم سيستم ايمني مصنوعي استاندارد مورد مطالعه قرار گرفته است.

براي ارزيابي راهکار پيشنهادي توابع مورد آزمايش به صورت سي بعدي و آنتي-بادي ها بصورت اعداد حقيقي کدگذاري شده اند و راهکار پيشنهادي با ۱۰۰ تکرار براي بدست آوردن پاسخ بهينه مورد آزمون قرار گرفته شده است. با توجه به ماهيت آزمون‌هاي آماري، پس از ۳۰ بار اجراي مكرر به ازاي هر تابع، از شاخص‌هاي بهترين پاسخ و ميانگين پاسخ‌ها براي مقايسه كارايي الگوريتم و از شاخص واريانس (كه يكي از شاخص‌هاي پراكندگي است) براي مقايسه پايداري استفاده شده است. نتايج شبيه‌سازي‌هاي انجام شده با استفاده از راه کار پيشنهادي، مدل ترکیبی سيستم ايمني مصنوعي و اتوماتای سلولی و الگوريتم سيستم ايمني مصنوعي به ترتيب در جدول های ۱ ، ۲ و ۳ آورده شده است.

 

روابط

 

همان گونه که در جدول های ۱ ، ۲ و ۳ در ستون بهترین نتیجه که حاصل بهترین نتیجه در ۱۰۰ اجرای مختلف و ستون میانگین که حاصل میانگین ۱۰۰ اجرای مختلف می باشد، بیانگر این است که، راهکار پیشنهادی در مقایسه با مدل ترکیبی سيستم ايمني مصنوعي، اتوماتای سلولی و الگوریتم استاندارد سیستم ایمنی مصنوعی در نقاط بهینه دارای دقت بسیار بالاتری می باشد. همچنین با توجه به ستون واریانس، که حاصل واریانس نتایج ۱۰۰ مرتبه اجرای مختلف می باشد بیانگر پايداري این مدل در اجراهاي مختلف و گریز از بهینه های محلی می باشد، که می تواند بهبودی بر کارایی سیستم ایمنی مصنوعی تلقی گردد. بر این اساس می توان کارايي راه کار پيشنهادي نسبت به مدل ترکیبی سيستم ايمني مصنوعي ، اتوماتای سلولی و الگوريتم استاندارد سيستم ايمني مصنوعي را تاييد کرد.

تعداد سلول ها، پارامتري مهم است كه بر كارايي مدل FCA-AIS تاثير مستقيم دارد .نمودار ۳ تاثير تعداد سلول ها را بر سرعت همگرايي مدل پيشنهادي در بهینه یابی تابع نشان داده است. هر نقطه نشان داده شده در اين نمودارها ارزش بهترين جواب بدست آمده در هر تكرار الگوريتم را نشان مي دهد. نتايج شبيه سازي ها نشان داد با افزايش تعداد سلول ها، روند همگرايي به بهينه سراسري شتاب بخشيده مي شود. اما تا حدي افزايش تعداد سلول ها مي تواند بر سرعت همگرايي بيافزايد و با افزايش تعداد سلول ها از تعداد ۳۶ سلول، تاثير چشمگيري در سرعت رسيدن به بهينه سراسري مشاهده نمي شود و با توجه به حجم محاسبات کمتر، مدل با ۳۶ سلول  پیشنهاد می شود.

به منظور مطالعه تاثير شعاع همسايگي بر كارايي مدل پيشنهادي چندين شبيه سازي با شعاع همسایگی ۱ تا ۴ انجام شده كه نتايج آن در بهینه یابی تابع در نمودار ۴ ارائه شده است. نتايج شبيه سازي ها نشان مي-دهد كه مدل پيشنهادي FCA-AIS با شعاع همسايگي ۱ جواب هايي با كيفيتي قابل قبول توليد مي كند که در مقايسه با ديگر شعاع هاي همسايگي به دليل حجم محاسبات کمتر، داراي امتياز است.

 

جدول 1       جدول 2

 

جدول 3

 

نمودار 3            نمودار 4

 

نتيجه‌گيري

در اين مثال ارائه شده ، مدل ترکيبي FCA-AIS به منظور محلي کردن ارتباط بين آنتي بادي ها و استفاده از دانش خبره در الگوريتم هاي سيستم ايمني مصنوعي به منظور تعيين کاراي پارامترهاي اساسي اين الگوريتم ارائه شده است. در اين الگوريتم آنتي بادي ها بروي يک شبکه سلولي در کنار يکديگر قرار مي گيرند. در هر زمان تمام سلول ها به صورت همزمان فعال مي شوند و بر اساس مقادير آنتي بادي خود و بهترين همسايه با استفاده از مجموعه ها و قوانين فازي نرخ ابرجهش را تعيين مي نمايند.

نتايج بدست آمده نشان مي دهد مدل پيشنهادي علاوه بر سرعت بخشيدن به محاسبات داراي دقت بيشتري نسبت به الگوريتم استاندارد سيستم ايمني مصنوعي مي باشد. اجراي مكرر شبيه‌سازي‌ها نيز نشان داد كه اين الگوريتم از پايداري بيشتري برخوردار مي‌باشد. همچنين به منظور مطالعه تاثير پارامترها بر روند همگرايي، پارامترهايي همچون تعداد سلول هاي شبکه و شعاع همسايگي مورد بررسي قرار گرفت که نتايج حاکي از آن است که با افزايش تعداد سلول ها، مدل ترکيبي پيشنهادي با سرعت بالاتري به بهينه سراسري نزديک مي شد اين در حالي است که در يک شبکه سلولي افزايش شعاع همسايگي تاثير چشمگيري بر سرعت همگرايي نداشته و اتوماتاي سلولي با شعاع همسايگي يک به دليل حجم محاسبات کمتر از مقبوليت بيشتري برخوردار است.

/0 دیدگاه /توسط

فشرده سازی تصویر قسمت 2

فناوری فشرده سازی تصویر چگونه عمل می کند؟

فشرده سازی تصویر یکی از تکنولوژی هایی است که در فضای رسانه و رایانه بسیار مفید و با اهمیت است و با استفاده از آن می توان حجم تصاویر را تا حد خوبی کاهش داد. اهمیت از این تکنولوژی زمانی مشخص می شود که حجم عکس برای شما مهم باشد و کاهش چند درصد از حجم آن نیز برای شما غنیمت باشد. در این صورت است که به فناوری و تکنولوژی فشرده سازی تصاویر اهمیت خواهید داد.

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

چرا باید تصاویر را فشرده سازی کرد؟

در ابتدا شاید این سوال بوجود آید که چرا باید تصاویر و یا فایل ها را فشرده سازی کرد؟ در پاسخ به این سوال باید گفت که اصلی ترین دلیل فشرده سازی فایل ها و تصاویر کاهش حجم آن می باشد. این موضوع در ارسال و دریافت فایل ها بسیار تاثیرگذار است و زمان لازم برای آن را کاهش می دهد. همچنین باعث می شود زمان بارگذاری وب سایت ها نیز کاهش یابد و باعث می شود مجموع حجم مصرف شده از حافظه رایانه شما کمتر شود. در بعضی حتی امکان ارسال فایل های حجم بالا وجود ندارد و به ناچار باید حجم فایل را کاهش داد که در این صورت فشرده سازی تصویر روش مناسبی می باشد. خب همین چند دلیل برای فشرده سازی تصاویر کافیست و باعث می شود افراد از این فناوری استفاده نمایند.

فشرده سازی تصویر چیست؟

تکنولوژی فشرده سازی تصویر در حقیقت فشرده سازی اطلاعات داخل تصویر می باشد. در این روش افزونگی محتویات داخل تصویر کاهش می یابد و باعث بهینه سازی شدن تصویر می شود که نتیجه آن فشرده یا کم حجم شدن تصویر می باشد. به این صورت که بخش های اضافی و زاید (افزونگی) موجود در اطلاعات تصویر حذف می شوند و همین باعث بهینه شدن و کم حجم شدن تصویر می شود.

برای فشرده سازی تصاویر روشهای مختلف با الگوریتم های مختلفی وجود دارد که هر یک از این روشها در نهایت منجر به کاهش حجم تصویر می شود. اما در نوع انجام با یکدیگر متفاوت هستند و بسته به روش مورد استفاده مقدار حجم کاهش یافته نیز متغیر خواهد بود.

روشهای فشرده سازی تصویر

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

فشرده سازی بدون اتلاف

این روش را روش فشرده سازی بازگشت پذیر نیز می گویند. زیرا با استفاده از این روش امکان بازگردانی تصویر فشرده شده به تصویر اصلی وجود دارد. این روش ضریب فشرده سازی کمتری دارد و کیفیت تصویر را کاهش نمی دهد. برای فشرده سازی عکس ها با این روش الگوریتم های مختلفی وجود دارند که نتیجه بالا را به دست می دهند. رایج ترین الگوریتم حذف محتواهای تکراری با روشی خاص است. به این صورت سیستم از عبارات و متون تکراری فاکتور می گیرد و محتواهای اضافی را حذف می کند. برای درک بهتر موضوع به این مثال توجه کنید. تصر کنید محتوای ما «whatisimage whatisimage2 whatisimage3» باشد. اگر بخواهیم این متن را با روش فوق فشرده سازی کنیم لازم است از عبارت تکراری «whatisimage» فاکتور بگیریم و بقیه آنها را حذف نماییم. نتیجه به صورت «w (w)2 (w)3» در می آید. در این روش عبارت «(w)» به جای «whatisimage» قرار گرفته است و همین باعث شده طول متن مورد نظر تا حد زیادی کاهش یابد.

البته روش کمی پیچیده تر از این است و توسط رایانه انجام می شود. اما کلیت آن به این صورت می باشد. در تصاویر نیز به همین صورت است. فایل تصویر در رایانه حاوی مقدار زیادی کد به زبان رایانه است که پس از اجرا توسط کامپیوتر نتیجه آن که یک تصویر است نمایش داده می شود. بنابراین با این روش فشرده سازی می توان کدهای تصویر را بهینه کرد و از بخش های تکراری آن فاکتورگیری نمود که نتیجه آن کاهش حجم تصویر و فشرده شدن آن می باشد.

فشرده سازی بااتلاف

روش دیگر فشرده سازی بااتلاف یا فشرده سازی بازگشت ناپذیر می باشد که در آن کیفیت تصویر کاهش می یابد و بر خلاف روش قبلی امکان بازگردانی تصویر فشرده شده به تصویر اصلی وجود نخواهد داشت. در حقیقت نقطه ضعف اصلی این روش از دست رفتن اطلاعات و داده های موجود در تصویر طی فرایند می باشد. به همین دلیل استفاده از آن برای تصاویر مهم و لازم برای آرشیو اطلاعاتی مناسب نمی باشد.

فشرده سازی با اتلاف

البته باید توجه داشت که این روش یک امتیاز مهمی دارد و آن ضریب بالای فشرده سازی می باشد. یعنی حجم کاهش یافته از تصویر طی این فرایند بیشتر است و در نتیجه تصویر فشرده شده حجم کمترین خواهد داشت.

از این روش در شبکه های اجتماعی، پیام رسان ها، نرم افزارهای ارسال فایل، وب سایت ها و … که حجم تصویر بر کیفیت آن ارجحیت دارد استفاده می شود.

ابزارهای فشرده سازی عکس

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

بدی این روش این است که شما باید ابتدا فایل اصلی خود را که احتمالا حجم بالایی نیز دارد ارسال کنید تا وب سایت سرویس دهنده عملیات فشرده سازی را انجام دهد. برای تصاویر حجم بالا و یا تصاویر خصوصی و شخصی این روش اصلا مناسب نیست و عملا امکان ارسال فایل وجود ندارد. به جای آن بهتر است از نرم افزارهای فشرده سازی تصویر استفاده کنید. Advanced JPEG Compressor و PicShrink دو برنامه فشرده سازی مخصوص دسکتاپ هستند که با استفاده از آنها می توانید تصاویر حجم بالا را نیز فشرده نمایید. مزیت استفاده از نرم افزار این است که دیگر نیازی به ارسال تصاویر و فایل ها به وب سایت سرویس دهنده وجود ندارد و می توان عملیات را در رایانه شخصی انجام داد.

انواع روشهای فشرده سازی تصویر

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

در روشهای فشرده اگر بخواهیم درصد فشرده سازی بیشتر باشد باید قبول کنیم که بخش‌هایی از اطلاعات و داده‌های موجود در تصویر کنار گذاشته شود و به عبارت دیگر حذف شود. در این صورت مشاهده می شود که تصویر فشرده شده تا حدودی کیفیت خود را از دست داده است. اما در روشهای بدون اتلاف چنین نیست و کیفیت تصویر تغییری نمی کند اما در عوض مقدار فشرده سازی و کاهش حجم فایل در این روشها پایین تر می باشد.

در روش فشرده سازی تصویر میزان کنار گذاشتن یا حذف بخشهای از تصویر به وسیله ضریب یا نسبت فشرده‌سازی معین می شود. هرچه این ضریب بیشتر باشد مقدار فشرده سازی و مقدار حذف اطلاعات بیشتر خواهد بود و در نهایت کیفیت تصویر نیز بیشتر کاهش می یابد. اما باید گفت که در این روش ذخیره‌سازی و انتقال داده ها بسیار راحت تر بوده و عملیات فشرده سازی تصویر سریع تر انجام می شود.

امروزه برای فشرده‌سازی عکس روشهای مختلفی وجود دارد که بسیار پیشرفته هستند. فشرده‌سازی تصویر از اصلی مهم پیروی می کند و آن این است که چشم انسان فاصله بین دو نقطه کوچک در تصویر را تقریبا یکسان می بیند. بر همین اساس در روشهای مختلف فشرده سازی از این اصل استفاده کرده و طیف خاصی از رنگ ها که توسط چشم انسان قابل تشخیص نمی باشد را حذف می کنند.

روشهای فشرده سازی تصویر

اما پس از توضیحات ابتدایی برویم سر اصل موضوع یعنی روشهای فشرده سازی تصویر. به طور کلی ۵ روش فشرده سازی تصویر (JPEG، MPEG، MP3، MPEG2، MPEG) مد نظر ما می باشد که یک یک آنها را ذکر کرده و توضیح می دهیم.

روش JPEG 
این فرمت مخفف عبارت JOINT PHOTOGRAPHIC EXPERT GROUP و به معنی «گروه مشترک کارشناسان گرافیک» است. از این نام برای نوعی فشرده سازی تصویر نیز استفاده شده است. روش JPEG اولین و البته ساده ترین روش فشرده سازی تصویر می باشد که جهت فشرده‌سازی تصاویر گرافیکی استفاده ایجاد شده است.

فشرده سازی به روش jpeg

از این روش همچنین جهت فشرده‌سازی تصاویر متحرک نیز استفاده شد. برای دستیابی به این هدف تصاویر مورد نظر فریم به فریم فشرده می‌شدند. اما برای حل این مشکل روش دیگری به نام MOTION JPEG به معنی «JPEG متحرک» ابداع شد که از آن جهت ارتباط دادن تصاویر فریم شده به هم و ساخت یک عکس متحرک استفاده شد.

روش MPEG
نام فرمت MPEG مخفف عبارت MOVING PICTURE EXOERT GROUP و به معنی «گروه کارشناسان تصویر متحرک» می باشد. روش مذکور در ابتدا آن داده های تصویری را با سرعت حدود ۵ مگابیت در ثانیه انتقال می داد که در نهایت منجر به ایجاد تصاویر ویدئویی می‌شد. با این روش از فشرده سازی تصاویر امکان ذخیره سازی تصاویر متحرک برای ۷۰ دقیقه و به اندازه ۶۵۰ مگابایت فراهم بود. در روش MPEG بیت‌ (Bit) های داده به صورت سریالی ارسال می‌شوند که در کنار آنها بیت‌های کنترل و هماهنگ‌کننده نیز ارسال می شوند که مکان و نوع جاگذاری بیت‌های اطلاعاتی را برای ثبت اطلاعات صدا و تصویر تعیین می کند. البته روش کار کمی پیچیده تر از این است که توسط رایانه انجام می شود.

روش MPEG2
در این روش که MPEG2 نام دارد از ضریب فشرده‌سازی بالاتری نسبت به روشهای پیشین استفاده می شود. در این روش امکان بررسی داده ها ۱۵ مگابیت در ثانیه وجود دارد و از آن در DVD ها استفاده می شود. لازم به ذکر است که در روش MPEG2 هر فریم (Frame) تصویر شامل چندین سطر از اطلاعات دیجیتالی می باشد که با روشهای پیشرفته جایگذاری می شوند.

روش MPEG-4
از این روش در تجهیزاتی استفاده می شود که با انتقال کند یا سریع اطلاعات فعالیت می کنند. در این روش توانایی جبران خطا و ارائه کیفیت بالای تصویر وجود دارد. موضوع جبران خطا در مورد رایانه، تلفن همراه و شبکه اهمیت بالایی دارد که در این روش مدنظر گرفته شده است. به عنوان مثال در شبکه های کامپیوتری تصویر مورد نظر باید برای کاربران دارای مودم کند یا سریع به خوبی نمایش داده شود. در این صورت استفاده از روش MPEG-4 مناسب می باشد. همچنین از این روش در دوربین‌های تلویزیونی نیز استفاده می شود.

روش MPEG-4 کاربرد فراوان دارد که نمونه آن در فیلم صحنه بازی تنیس است. در این حالت می توان صحنه را به دو مولفه بازیکن و زمین بازی تقسیم کرد که در آن زمین بازی دائما ثابت می باشد و در تمام تصاویر تکرار می شود. اما بازیکن همواره در حال حرکت می باشد. در این روش پهنای باند اشغالی بسیار کاهش می یابد و با روشهای پیشرفته حجم فایل ها کاهش می یابد.

لازم به ذکر است که علاوه بر این روشها اخیرا روش جدیدی توسط شرکت گوگل ابداع شده که می تواند حجم تصاویر را تا حد زیادی کاهش دهد. گفته می شود استفاده از این روش کاربران شاهد کاهش ۳۵ درصدی حجم تصویر خواهند بود.

در ادامه مطالعه فایل های زیر می تواند کمک کننده باشد:

الگوریتم های فشرده سازی بدون اتلاف

رمز فایل: behsanandish.com

فشرده سازی بدون اتلاف

رمز فایل: behsanandish.com

فشرده سازی تصویر به روش MPEG

رمز فایل: behsanandish.com

فشرده سازی تصویر قسمت 1
فشرده سازی تصویر قسمت 2

/0 دیدگاه /توسط