الگوریتم Canny در سی پلاس پلاس قسمت 4

 

مرحله 4: سرکوب لبه های غیر حداکثر

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

 

</pre>
<pre>#include "stdafx.h"
#include "tripod.h"
#include "tripodDlg.h"

#include "LVServerDefs.h"
#include "math.h"
#include <fstream>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>


#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

using namespace std;

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg dialog

CTripodDlg::CTripodDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CTripodDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CTripodDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

	//////////////// Set destination BMP to NULL first 
	m_destinationBitmapInfoHeader = NULL;

}

////////////////////// Additional generic functions

static unsigned PixelBytes(int w, int bpp)
{
    return (w * bpp + 7) / 8;
}

static unsigned DibRowSize(int w, int bpp)
{
    return (w * bpp + 31) / 32 * 4;
}

static unsigned DibRowSize(LPBITMAPINFOHEADER pbi)
{
    return DibRowSize(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibRowPadding(int w, int bpp)
{
    return DibRowSize(w, bpp) - PixelBytes(w, bpp);
}

static unsigned DibRowPadding(LPBITMAPINFOHEADER pbi)
{
    return DibRowPadding(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibImageSize(int w, int h, int bpp)
{
    return h * DibRowSize(w, bpp);
}

static size_t DibSize(int w, int h, int bpp)
{
    return sizeof (BITMAPINFOHEADER) + DibImageSize(w, h, bpp);
}

/////////////////////// end of generic functions


void CTripodDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CTripodDlg)
	DDX_Control(pDX, IDC_PROCESSEDVIEW, m_cVideoProcessedView);
	DDX_Control(pDX, IDC_UNPROCESSEDVIEW, m_cVideoUnprocessedView);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CTripodDlg, CDialog)
	//{{AFX_MSG_MAP(CTripodDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDEXIT, OnExit)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg message handlers

BOOL CTripodDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here

	// For Unprocessed view videoportal (top one)
	char sRegUnprocessedView[] = "HKEY_LOCAL_MACHINE\\Software\\UnprocessedView";
	m_cVideoUnprocessedView.PrepareControl("UnprocessedView", sRegUnprocessedView, 0 );	
	m_cVideoUnprocessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoUnprocessedView.ConnectCamera2();
	m_cVideoUnprocessedView.SetEnablePreview(TRUE);

	// For binary view videoportal (bottom one)
	char sRegProcessedView[] = "HKEY_LOCAL_MACHINE\\Software\\ProcessedView";
	m_cVideoProcessedView.PrepareControl("ProcessedView", sRegProcessedView, 0 );	
	m_cVideoProcessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoProcessedView.ConnectCamera2();
	m_cVideoProcessedView.SetEnablePreview(TRUE);

	// Initialize the size of binary videoportal
	m_cVideoProcessedView.SetPreviewMaxHeight(240);
	m_cVideoProcessedView.SetPreviewMaxWidth(320);

	// Uncomment if you wish to fix the live videoportal's size
	// m_cVideoUnprocessedView.SetPreviewMaxHeight(240);
	// m_cVideoUnprocessedView.SetPreviewMaxWidth(320);

	// Find the screen coodinates of the binary videoportal
	m_cVideoProcessedView.GetWindowRect(m_rectForProcessedView);
	ScreenToClient(m_rectForProcessedView);
	allocateDib(CSize(320, 240));

	// Start grabbing frame data for Procssed videoportal (bottom one)
	m_cVideoProcessedView.StartVideoHook(0);

	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CTripodDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CTripodDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CTripodDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CTripodDlg::OnExit() 
{
	// TODO: Add your control notification handler code here

	// Kill live view videoportal (top one)
	m_cVideoUnprocessedView.StopVideoHook(0);
    m_cVideoUnprocessedView.DisconnectCamera();	
	
	// Kill binary view videoportal (bottom one)
	m_cVideoProcessedView.StopVideoHook(0);
    m_cVideoProcessedView.DisconnectCamera();	

	// Kill program
	DestroyWindow();	

	

}

BEGIN_EVENTSINK_MAP(CTripodDlg, CDialog)
    //{{AFX_EVENTSINK_MAP(CTripodDlg)
	ON_EVENT(CTripodDlg, IDC_PROCESSEDVIEW, 1 /* PortalNotification */, OnPortalNotificationProcessedview, VTS_I4 VTS_I4 VTS_I4 VTS_I4)
	//}}AFX_EVENTSINK_MAP
END_EVENTSINK_MAP()

void CTripodDlg::OnPortalNotificationProcessedview(long lMsg, long lParam1, long lParam2, long lParam3) 
{
	// TODO: Add your control notification handler code here
	
	// This function is called at the camera's frame rate
    
#define NOTIFICATIONMSG_VIDEOHOOK	10

	// Declare some useful variables
	// QCSDKMFC.pdf (Quickcam MFC documentation) p. 103 explains the variables lParam1, lParam2, lParam3 too 
	
	LPBITMAPINFOHEADER lpBitmapInfoHeader; // Frame's info header contains info like width and height
	LPBYTE lpBitmapPixelData; // This pointer-to-long will point to the start of the frame's pixel data
    unsigned long lTimeStamp; // Time when frame was grabbed

	switch(lMsg) {
		case NOTIFICATIONMSG_VIDEOHOOK:
			{
				lpBitmapInfoHeader = (LPBITMAPINFOHEADER) lParam1; 
				lpBitmapPixelData = (LPBYTE) lParam2;
				lTimeStamp = (unsigned long) lParam3;

				grayScaleTheFrameData(lpBitmapInfoHeader, lpBitmapPixelData);
				doMyImageProcessing(lpBitmapInfoHeader); // Place where you'd add your image processing code
				displayMyResults(lpBitmapInfoHeader);

			}
			break;

		default:
			break;
	}	
}

void CTripodDlg::allocateDib(CSize sz)
{
	// Purpose: allocate information for a device independent bitmap (DIB)
	// Called from OnInitVideo

	if(m_destinationBitmapInfoHeader) {
		free(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader = NULL;
	}

	if(sz.cx | sz.cy) {
		m_destinationBitmapInfoHeader = (LPBITMAPINFOHEADER)malloc(DibSize(sz.cx, sz.cy, 24));
		ASSERT(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader->biSize = sizeof(BITMAPINFOHEADER);
		m_destinationBitmapInfoHeader->biWidth = sz.cx;
		m_destinationBitmapInfoHeader->biHeight = sz.cy;
		m_destinationBitmapInfoHeader->biPlanes = 1;
		m_destinationBitmapInfoHeader->biBitCount = 24;
		m_destinationBitmapInfoHeader->biCompression = 0;
		m_destinationBitmapInfoHeader->biSizeImage = DibImageSize(sz.cx, sz.cy, 24);
		m_destinationBitmapInfoHeader->biXPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biYPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biClrImportant = 0;
		m_destinationBitmapInfoHeader->biClrUsed = 0;
	}
}

void CTripodDlg::displayMyResults(LPBITMAPINFOHEADER lpThisBitmapInfoHeader)
{
	// displayMyResults: Displays results of doMyImageProcessing() in the videoport
	// Notes: StretchDIBits stretches a device-independent bitmap to the appropriate size

	CDC				*pDC;	// Device context to display bitmap data
	
	pDC = GetDC();	
	int nOldMode = SetStretchBltMode(pDC->GetSafeHdc(),COLORONCOLOR);

	StretchDIBits( 
		pDC->GetSafeHdc(),
		m_rectForProcessedView.left,				// videoportal left-most coordinate
		m_rectForProcessedView.top,					// videoportal top-most coordinate
		m_rectForProcessedView.Width(),				// videoportal width
		m_rectForProcessedView.Height(),			// videoportal height
		0,											// Row position to display bitmap in videoportal
		0,											// Col position to display bitmap in videoportal
		lpThisBitmapInfoHeader->biWidth,			// m_destinationBmp's number of columns
		lpThisBitmapInfoHeader->biHeight,			// m_destinationBmp's number of rows
		m_destinationBmp,							// The bitmap to display; use the one resulting from doMyImageProcessing
		(BITMAPINFO*)m_destinationBitmapInfoHeader, // The bitmap's header info e.g. width, height, number of bits etc
		DIB_RGB_COLORS,								// Use default 24-bit color table
		SRCCOPY										// Just display
	);
 
	SetStretchBltMode(pDC->GetSafeHdc(),nOldMode);

	ReleaseDC(pDC);

	// Note: 04/24/02 - Added the following:
	// Christopher Wagner cwagner@fas.harvard.edu noticed that memory wasn't being freed

	// Recall OnPortalNotificationProcessedview, which gets called everytime
	// a frame of data arrives, performs 3 steps:
	// (1) grayScaleTheFrameData - which mallocs m_destinationBmp
	// (2) doMyImageProcesing
	// (3) displayMyResults - which we're in now
	// Since we're finished with the memory we malloc'ed for m_destinationBmp
	// we should free it: 
	
	free(m_destinationBmp);

	// End of adds
}

void CTripodDlg::grayScaleTheFrameData(LPBITMAPINFOHEADER lpThisBitmapInfoHeader, LPBYTE lpThisBitmapPixelData)
{

	// grayScaleTheFrameData: Called by CTripodDlg::OnPortalNotificationBinaryview
	// Task: Read current frame pixel data and computes a grayscale version

	unsigned int	W, H;			  // Width and Height of current frame [pixels]
	BYTE            *sourceBmp;		  // Pointer to current frame of data
	unsigned int    row, col;
	unsigned long   i;
	BYTE			grayValue;

	BYTE			redValue;
	BYTE			greenValue;
	BYTE			blueValue;

    W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows

	// Store pixel data in row-column vector format
	// Recall that each pixel requires 3 bytes (red, blue and green bytes)
	// m_destinationBmp is a protected member and declared in binarizeDlg.h

	m_destinationBmp = (BYTE*)malloc(H*3*W*sizeof(BYTE));

	// Point to the current frame's pixel data
	sourceBmp = lpThisBitmapPixelData;

	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {

			// Recall each pixel is composed of 3 bytes
			i = (unsigned long)(row*3*W + 3*col);
        
			// The source pixel has a blue, green andred value:
			blueValue  = *(sourceBmp + i);
			greenValue = *(sourceBmp + i + 1);
			redValue   = *(sourceBmp + i + 2);

			// A standard equation for computing a grayscale value based on RGB values
			grayValue = (BYTE)(0.299*redValue + 0.587*greenValue + 0.114*blueValue);

			// The destination BMP will be a grayscale version of the source BMP
			*(m_destinationBmp + i)     = grayValue;
			*(m_destinationBmp + i + 1) = grayValue;
			*(m_destinationBmp + i + 2) = grayValue;
			
		}
	}
}


void CTripodDlg::doMyImageProcessing(LPBITMAPINFOHEADER lpThisBitmapInfoHeader)
{
	// doMyImageProcessing:  This is where you'd write your own image processing code
	// Task: Read a pixel's grayscale value and process accordingly

	unsigned int	W, H;			// Width and Height of current frame [pixels]
	unsigned int    row, col;		// Pixel's row and col positions
	unsigned long   i;				// Dummy variable for row-column vector
	int	    upperThreshold = 60;	// Gradient strength nessicary to start edge
	int		lowerThreshold = 30;	// Minimum gradient strength to continue edge
	unsigned long iOffset;			// Variable to offset row-column vector during sobel mask
	int rowOffset;					// Row offset from the current pixel
	int colOffset;					// Col offset from the current pixel
	int rowTotal = 0;				// Row position of offset pixel
	int colTotal = 0;				// Col position of offset pixel
	int Gx;							// Sum of Sobel mask products values in the x direction
	int Gy;							// Sum of Sobel mask products values in the y direction
	float thisAngle;				// Gradient direction based on Gx and Gy
	int newAngle;					// Approximation of the gradient direction
	bool edgeEnd;					// Stores whether or not the edge is at the edge of the possible image
	int GxMask[3][3];				// Sobel mask in the x direction
	int GyMask[3][3];				// Sobel mask in the y direction
	int newPixel;					// Sum pixel values for gaussian
	int gaussianMask[5][5];			// Gaussian mask

	W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows
	
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {
			edgeDir[row][col] = 0;
		}
	}

	/* Declare Sobel masks */
	GxMask[0][0] = -1; GxMask[0][1] = 0; GxMask[0][2] = 1;
	GxMask[1][0] = -2; GxMask[1][1] = 0; GxMask[1][2] = 2;
	GxMask[2][0] = -1; GxMask[2][1] = 0; GxMask[2][2] = 1;
	
	GyMask[0][0] =  1; GyMask[0][1] =  2; GyMask[0][2] =  1;
	GyMask[1][0] =  0; GyMask[1][1] =  0; GyMask[1][2] =  0;
	GyMask[2][0] = -1; GyMask[2][1] = -2; GyMask[2][2] = -1;

	/* Declare Gaussian mask */
	gaussianMask[0][0] = 2;		gaussianMask[0][1] = 4;		gaussianMask[0][2] = 5;		gaussianMask[0][3] = 4;		gaussianMask[0][4] = 2;	
	gaussianMask[1][0] = 4;		gaussianMask[1][1] = 9;		gaussianMask[1][2] = 12;	gaussianMask[1][3] = 9;		gaussianMask[1][4] = 4;	
	gaussianMask[2][0] = 5;		gaussianMask[2][1] = 12;	gaussianMask[2][2] = 15;	gaussianMask[2][3] = 12;	gaussianMask[2][4] = 2;	
	gaussianMask[3][0] = 4;		gaussianMask[3][1] = 9;		gaussianMask[3][2] = 12;	gaussianMask[3][3] = 9;		gaussianMask[3][4] = 4;	
	gaussianMask[4][0] = 2;		gaussianMask[4][1] = 4;		gaussianMask[4][2] = 5;		gaussianMask[4][3] = 4;		gaussianMask[4][4] = 2;	
	

	/* Gaussian Blur */
	for (row = 2; row < H-2; row++) {
		for (col = 2; col < W-2; col++) {
			newPixel = 0;
			for (rowOffset=-2; rowOffset<=2; rowOffset++) {
				for (colOffset=-2; colOffset<=2; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					newPixel += (*(m_destinationBmp + iOffset)) * gaussianMask[2 + rowOffset][2 + colOffset];
				}
			}
			i = (unsigned long)(row*3*W + col*3);
			*(m_destinationBmp + i) = newPixel / 159;
		}
	}

	/* Determine edge directions and gradient strengths */
	for (row = 1; row < H-1; row++) {
		for (col = 1; col < W-1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			Gx = 0;
			Gy = 0;
			/* Calculate the sum of the Sobel mask times the nine surrounding pixels in the x and y direction */
			for (rowOffset=-1; rowOffset<=1; rowOffset++) {
				for (colOffset=-1; colOffset<=1; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					Gx = Gx + (*(m_destinationBmp + iOffset) * GxMask[rowOffset + 1][colOffset + 1]);
					Gy = Gy + (*(m_destinationBmp + iOffset) * GyMask[rowOffset + 1][colOffset + 1]);
				}
			}

			gradient[row][col] = sqrt(pow(Gx,2.0) + pow(Gy,2.0));	// Calculate gradient strength			
			thisAngle = (atan2(Gx,Gy)/3.14159) * 180.0;		// Calculate actual direction of edge
			
			/* Convert actual edge direction to approximate value */
			if ( ( (thisAngle < 22.5) && (thisAngle > -22.5) ) || (thisAngle > 157.5) || (thisAngle < -157.5) )
				newAngle = 0;
			if ( ( (thisAngle > 22.5) && (thisAngle < 67.5) ) || ( (thisAngle < -112.5) && (thisAngle > -157.5) ) )
				newAngle = 45;
			if ( ( (thisAngle > 67.5) && (thisAngle < 112.5) ) || ( (thisAngle < -67.5) && (thisAngle > -112.5) ) )
				newAngle = 90;
			if ( ( (thisAngle > 112.5) && (thisAngle < 157.5) ) || ( (thisAngle < -22.5) && (thisAngle > -67.5) ) )
				newAngle = 135;
				
			edgeDir[row][col] = newAngle;		// Store the approximate edge direction of each pixel in one array
		}
	}

	/* Trace along all the edges in the image */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) {
			edgeEnd = false;
			if (gradient[row][col] > upperThreshold) {		// Check to see if current pixel has a high enough gradient strength to be part of an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]){		
					case 0:
						findEdge(0, 1, row, col, 0, lowerThreshold);
						break;
					case 45:
						findEdge(1, 1, row, col, 45, lowerThreshold);
						break;
					case 90:
						findEdge(1, 0, row, col, 90, lowerThreshold);
						break;
					case 135:
						findEdge(1, -1, row, col, 135, lowerThreshold);
						break;
					default :
						i = (unsigned long)(row*3*W + 3*col);
						*(m_destinationBmp + i) = 
						*(m_destinationBmp + i + 1) = 
						*(m_destinationBmp + i + 2) = 0;
						break;
					}
				}
			else {
				i = (unsigned long)(row*3*W + 3*col);
					*(m_destinationBmp + i) = 
					*(m_destinationBmp + i + 1) = 
					*(m_destinationBmp + i + 2) = 0;
			}	
		}
	}
	
	/* Suppress any pixels not changed by the edge tracing */
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {	
			// Recall each pixel is composed of 3 bytes
			i = (unsigned long)(row*3*W + 3*col);
			// If a pixel's grayValue is not black or white make it black
			if( ((*(m_destinationBmp + i) != 255) && (*(m_destinationBmp + i) != 0)) || ((*(m_destinationBmp + i + 1) != 255) && (*(m_destinationBmp + i + 1) != 0)) || ((*(m_destinationBmp + i + 2) != 255) && (*(m_destinationBmp + i + 2) != 0)) ) 
				*(m_destinationBmp + i) = 
				*(m_destinationBmp + i + 1) = 
				*(m_destinationBmp + i + 2) = 0; // Make pixel black
		}
	}

	/* Non-maximum Suppression */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			if (*(m_destinationBmp + i) == 255) {		// Check to see if current pixel is an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]) {		
					case 0:
						suppressNonMax( 1, 0, row, col, 0, lowerThreshold);
						break;
					case 45:
						suppressNonMax( 1, -1, row, col, 45, lowerThreshold);
						break;
					case 90:
						suppressNonMax( 0, 1, row, col, 90, lowerThreshold);
						break;
					case 135:
						suppressNonMax( 1, 1, row, col, 135, lowerThreshold);
						break;
					default :
						break;
				}
			}	
		}
	}
	
}

void CTripodDlg::findEdge(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow;
	int newCol;
	unsigned long i;
	bool edgeEnd = false;

	/* Find the row and column values for the next possible pixel on the edge */
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
		
	/* Determine edge directions and gradient strengths */
	while ( (edgeDir[newRow][newCol]==dir) && !edgeEnd && (gradient[newRow][newCol] > lowerThreshold) ) {
		/* Set the new pixel as white to show it is an edge */
		i = (unsigned long)(newRow*3*W + 3*newCol);
		*(m_destinationBmp + i) =
		*(m_destinationBmp + i + 1) =
		*(m_destinationBmp + i + 2) = 255;
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
	}	
}

void CTripodDlg::suppressNonMax(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow = 0;
	int newCol = 0;
	unsigned long i;
	bool edgeEnd = false;
	float nonMax[320][3];			// Temporarily stores gradients and positions of pixels in parallel edges
	int pixelCount = 0;					// Stores the number of pixels in parallel edges
	int count;						// A for loop counter
	int max[3];						// Maximum point in a wide edge
	
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	/* Find non-maximum parallel edges tracing up */
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Find non-maximum parallel edges tracing down */
	edgeEnd = false;
	colShift *= -1;
	rowShift *= -1;
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;	
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Suppress non-maximum edges */
	max[0] = 0;
	max[1] = 0;
	max[2] = 0;
	for (count = 0; count < pixelCount; count++) {
		if (nonMax[count][2] > max[2]) {
			max[0] = nonMax[count][0];
			max[1] = nonMax[count][1];
			max[2] = nonMax[count][2];
		}
	}
	for (count = 0; count < pixelCount; count++) {
		i = (unsigned long)(nonMax[count][0]*3*W + 3*nonMax[count][1]);
		*(m_destinationBmp + i) = 
		*(m_destinationBmp + i + 1) = 
		*(m_destinationBmp + i + 2) = 0;
	}
}

 

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

Canny in C++ -No2

رمز فایل : behsanandish.com

الگوریتم Canny در سی پلاس پلاس قسمت 1
الگوریتم Canny در سی پلاس پلاس قسمت 2
الگوریتم Canny در سی پلاس پلاس قسمت 3
الگوریتم Canny در سی پلاس پلاس قسمت 4

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

الگوریتم Canny در سی پلاس پلاس قسمت 3

 

مرحله 3: ردیابی در امتداد لبه ها

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

 

#include "stdafx.h"
#include "tripod.h"
#include "tripodDlg.h"

#include "LVServerDefs.h"
#include "math.h"
#include <fstream>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>


#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

using namespace std;

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg dialog

CTripodDlg::CTripodDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CTripodDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CTripodDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

	//////////////// Set destination BMP to NULL first 
	m_destinationBitmapInfoHeader = NULL;

}

////////////////////// Additional generic functions

static unsigned PixelBytes(int w, int bpp)
{
    return (w * bpp + 7) / 8;
}

static unsigned DibRowSize(int w, int bpp)
{
    return (w * bpp + 31) / 32 * 4;
}

static unsigned DibRowSize(LPBITMAPINFOHEADER pbi)
{
    return DibRowSize(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibRowPadding(int w, int bpp)
{
    return DibRowSize(w, bpp) - PixelBytes(w, bpp);
}

static unsigned DibRowPadding(LPBITMAPINFOHEADER pbi)
{
    return DibRowPadding(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibImageSize(int w, int h, int bpp)
{
    return h * DibRowSize(w, bpp);
}

static size_t DibSize(int w, int h, int bpp)
{
    return sizeof (BITMAPINFOHEADER) + DibImageSize(w, h, bpp);
}

/////////////////////// end of generic functions


void CTripodDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CTripodDlg)
	DDX_Control(pDX, IDC_PROCESSEDVIEW, m_cVideoProcessedView);
	DDX_Control(pDX, IDC_UNPROCESSEDVIEW, m_cVideoUnprocessedView);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CTripodDlg, CDialog)
	//{{AFX_MSG_MAP(CTripodDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDEXIT, OnExit)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg message handlers

BOOL CTripodDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here

	// For Unprocessed view videoportal (top one)
	char sRegUnprocessedView[] = "HKEY_LOCAL_MACHINE\\Software\\UnprocessedView";
	m_cVideoUnprocessedView.PrepareControl("UnprocessedView", sRegUnprocessedView, 0 );	
	m_cVideoUnprocessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoUnprocessedView.ConnectCamera2();
	m_cVideoUnprocessedView.SetEnablePreview(TRUE);

	// For binary view videoportal (bottom one)
	char sRegProcessedView[] = "HKEY_LOCAL_MACHINE\\Software\\ProcessedView";
	m_cVideoProcessedView.PrepareControl("ProcessedView", sRegProcessedView, 0 );	
	m_cVideoProcessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoProcessedView.ConnectCamera2();
	m_cVideoProcessedView.SetEnablePreview(TRUE);

	// Initialize the size of binary videoportal
	m_cVideoProcessedView.SetPreviewMaxHeight(240);
	m_cVideoProcessedView.SetPreviewMaxWidth(320);

	// Uncomment if you wish to fix the live videoportal's size
	// m_cVideoUnprocessedView.SetPreviewMaxHeight(240);
	// m_cVideoUnprocessedView.SetPreviewMaxWidth(320);

	// Find the screen coodinates of the binary videoportal
	m_cVideoProcessedView.GetWindowRect(m_rectForProcessedView);
	ScreenToClient(m_rectForProcessedView);
	allocateDib(CSize(320, 240));

	// Start grabbing frame data for Procssed videoportal (bottom one)
	m_cVideoProcessedView.StartVideoHook(0);

	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CTripodDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CTripodDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CTripodDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CTripodDlg::OnExit() 
{
	// TODO: Add your control notification handler code here

	// Kill live view videoportal (top one)
	m_cVideoUnprocessedView.StopVideoHook(0);
    m_cVideoUnprocessedView.DisconnectCamera();	
	
	// Kill binary view videoportal (bottom one)
	m_cVideoProcessedView.StopVideoHook(0);
    m_cVideoProcessedView.DisconnectCamera();	

	// Kill program
	DestroyWindow();	

	

}

BEGIN_EVENTSINK_MAP(CTripodDlg, CDialog)
    //{{AFX_EVENTSINK_MAP(CTripodDlg)
	ON_EVENT(CTripodDlg, IDC_PROCESSEDVIEW, 1 /* PortalNotification */, OnPortalNotificationProcessedview, VTS_I4 VTS_I4 VTS_I4 VTS_I4)
	//}}AFX_EVENTSINK_MAP
END_EVENTSINK_MAP()

void CTripodDlg::OnPortalNotificationProcessedview(long lMsg, long lParam1, long lParam2, long lParam3) 
{
	// TODO: Add your control notification handler code here
	
	// This function is called at the camera's frame rate
    
#define NOTIFICATIONMSG_VIDEOHOOK	10

	// Declare some useful variables
	// QCSDKMFC.pdf (Quickcam MFC documentation) p. 103 explains the variables lParam1, lParam2, lParam3 too 
	
	LPBITMAPINFOHEADER lpBitmapInfoHeader; // Frame's info header contains info like width and height
	LPBYTE lpBitmapPixelData; // This pointer-to-long will point to the start of the frame's pixel data
    unsigned long lTimeStamp; // Time when frame was grabbed

	switch(lMsg) {
		case NOTIFICATIONMSG_VIDEOHOOK:
			{
				lpBitmapInfoHeader = (LPBITMAPINFOHEADER) lParam1; 
				lpBitmapPixelData = (LPBYTE) lParam2;
				lTimeStamp = (unsigned long) lParam3;

				grayScaleTheFrameData(lpBitmapInfoHeader, lpBitmapPixelData);
				doMyImageProcessing(lpBitmapInfoHeader); // Place where you'd add your image processing code
				displayMyResults(lpBitmapInfoHeader);

			}
			break;

		default:
			break;
	}	
}

void CTripodDlg::allocateDib(CSize sz)
{
	// Purpose: allocate information for a device independent bitmap (DIB)
	// Called from OnInitVideo

	if(m_destinationBitmapInfoHeader) {
		free(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader = NULL;
	}

	if(sz.cx | sz.cy) {
		m_destinationBitmapInfoHeader = (LPBITMAPINFOHEADER)malloc(DibSize(sz.cx, sz.cy, 24));
		ASSERT(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader->biSize = sizeof(BITMAPINFOHEADER);
		m_destinationBitmapInfoHeader->biWidth = sz.cx;
		m_destinationBitmapInfoHeader->biHeight = sz.cy;
		m_destinationBitmapInfoHeader->biPlanes = 1;
		m_destinationBitmapInfoHeader->biBitCount = 24;
		m_destinationBitmapInfoHeader->biCompression = 0;
		m_destinationBitmapInfoHeader->biSizeImage = DibImageSize(sz.cx, sz.cy, 24);
		m_destinationBitmapInfoHeader->biXPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biYPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biClrImportant = 0;
		m_destinationBitmapInfoHeader->biClrUsed = 0;
	}
}

void CTripodDlg::displayMyResults(LPBITMAPINFOHEADER lpThisBitmapInfoHeader)
{
	// displayMyResults: Displays results of doMyImageProcessing() in the videoport
	// Notes: StretchDIBits stretches a device-independent bitmap to the appropriate size

	CDC				*pDC;	// Device context to display bitmap data
	
	pDC = GetDC();	
	int nOldMode = SetStretchBltMode(pDC->GetSafeHdc(),COLORONCOLOR);

	StretchDIBits( 
		pDC->GetSafeHdc(),
		m_rectForProcessedView.left,				// videoportal left-most coordinate
		m_rectForProcessedView.top,					// videoportal top-most coordinate
		m_rectForProcessedView.Width(),				// videoportal width
		m_rectForProcessedView.Height(),			// videoportal height
		0,											// Row position to display bitmap in videoportal
		0,											// Col position to display bitmap in videoportal
		lpThisBitmapInfoHeader->biWidth,			// m_destinationBmp's number of columns
		lpThisBitmapInfoHeader->biHeight,			// m_destinationBmp's number of rows
		m_destinationBmp,							// The bitmap to display; use the one resulting from doMyImageProcessing
		(BITMAPINFO*)m_destinationBitmapInfoHeader, // The bitmap's header info e.g. width, height, number of bits etc
		DIB_RGB_COLORS,								// Use default 24-bit color table
		SRCCOPY										// Just display
	);
 
	SetStretchBltMode(pDC->GetSafeHdc(),nOldMode);

	ReleaseDC(pDC);

	// Note: 04/24/02 - Added the following:
	// Christopher Wagner cwagner@fas.harvard.edu noticed that memory wasn't being freed

	// Recall OnPortalNotificationProcessedview, which gets called everytime
	// a frame of data arrives, performs 3 steps:
	// (1) grayScaleTheFrameData - which mallocs m_destinationBmp
	// (2) doMyImageProcesing
	// (3) displayMyResults - which we're in now
	// Since we're finished with the memory we malloc'ed for m_destinationBmp
	// we should free it: 
	
	free(m_destinationBmp);

	// End of adds
}

void CTripodDlg::grayScaleTheFrameData(LPBITMAPINFOHEADER lpThisBitmapInfoHeader, LPBYTE lpThisBitmapPixelData)
{

	// grayScaleTheFrameData: Called by CTripodDlg::OnPortalNotificationBinaryview
	// Task: Read current frame pixel data and computes a grayscale version

	unsigned int	W, H;			  // Width and Height of current frame [pixels]
	BYTE            *sourceBmp;		  // Pointer to current frame of data
	unsigned int    row, col;
	unsigned long   i;
	BYTE			grayValue;

	BYTE			redValue;
	BYTE			greenValue;
	BYTE			blueValue;

    W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows

	// Store pixel data in row-column vector format
	// Recall that each pixel requires 3 bytes (red, blue and green bytes)
	// m_destinationBmp is a protected member and declared in binarizeDlg.h

	m_destinationBmp = (BYTE*)malloc(H*3*W*sizeof(BYTE));

	// Point to the current frame's pixel data
	sourceBmp = lpThisBitmapPixelData;

	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {

			// Recall each pixel is composed of 3 bytes
			i = (unsigned long)(row*3*W + 3*col);
        
			// The source pixel has a blue, green andred value:
			blueValue  = *(sourceBmp + i);
			greenValue = *(sourceBmp + i + 1);
			redValue   = *(sourceBmp + i + 2);

			// A standard equation for computing a grayscale value based on RGB values
			grayValue = (BYTE)(0.299*redValue + 0.587*greenValue + 0.114*blueValue);

			// The destination BMP will be a grayscale version of the source BMP
			*(m_destinationBmp + i)     = grayValue;
			*(m_destinationBmp + i + 1) = grayValue;
			*(m_destinationBmp + i + 2) = grayValue;
			
		}
	}
}


void CTripodDlg::doMyImageProcessing(LPBITMAPINFOHEADER lpThisBitmapInfoHeader)
{
	// doMyImageProcessing:  This is where you'd write your own image processing code
	// Task: Read a pixel's grayscale value and process accordingly

	unsigned int	W, H;			// Width and Height of current frame [pixels]
	unsigned int    row, col;		// Pixel's row and col positions
	unsigned long   i;				// Dummy variable for row-column vector
	int	    upperThreshold = 60;	// Gradient strength nessicary to start edge
	int		lowerThreshold = 30;	// Minimum gradient strength to continue edge
	unsigned long iOffset;			// Variable to offset row-column vector during sobel mask
	int rowOffset;					// Row offset from the current pixel
	int colOffset;					// Col offset from the current pixel
	int rowTotal = 0;				// Row position of offset pixel
	int colTotal = 0;				// Col position of offset pixel
	int Gx;							// Sum of Sobel mask products values in the x direction
	int Gy;							// Sum of Sobel mask products values in the y direction
	float thisAngle;				// Gradient direction based on Gx and Gy
	int newAngle;					// Approximation of the gradient direction
	bool edgeEnd;					// Stores whether or not the edge is at the edge of the possible image
	int GxMask[3][3];				// Sobel mask in the x direction
	int GyMask[3][3];				// Sobel mask in the y direction
	int newPixel;					// Sum pixel values for gaussian
	int gaussianMask[5][5];			// Gaussian mask

	W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows
	
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {
			edgeDir[row][col] = 0;
		}
	}

	/* Declare Sobel masks */
	GxMask[0][0] = -1; GxMask[0][1] = 0; GxMask[0][2] = 1;
	GxMask[1][0] = -2; GxMask[1][1] = 0; GxMask[1][2] = 2;
	GxMask[2][0] = -1; GxMask[2][1] = 0; GxMask[2][2] = 1;
	
	GyMask[0][0] =  1; GyMask[0][1] =  2; GyMask[0][2] =  1;
	GyMask[1][0] =  0; GyMask[1][1] =  0; GyMask[1][2] =  0;
	GyMask[2][0] = -1; GyMask[2][1] = -2; GyMask[2][2] = -1;

	/* Declare Gaussian mask */
	gaussianMask[0][0] = 2;		gaussianMask[0][1] = 4;		gaussianMask[0][2] = 5;		gaussianMask[0][3] = 4;		gaussianMask[0][4] = 2;	
	gaussianMask[1][0] = 4;		gaussianMask[1][1] = 9;		gaussianMask[1][2] = 12;	gaussianMask[1][3] = 9;		gaussianMask[1][4] = 4;	
	gaussianMask[2][0] = 5;		gaussianMask[2][1] = 12;	gaussianMask[2][2] = 15;	gaussianMask[2][3] = 12;	gaussianMask[2][4] = 2;	
	gaussianMask[3][0] = 4;		gaussianMask[3][1] = 9;		gaussianMask[3][2] = 12;	gaussianMask[3][3] = 9;		gaussianMask[3][4] = 4;	
	gaussianMask[4][0] = 2;		gaussianMask[4][1] = 4;		gaussianMask[4][2] = 5;		gaussianMask[4][3] = 4;		gaussianMask[4][4] = 2;	
	

	/* Gaussian Blur */
	for (row = 2; row < H-2; row++) {
		for (col = 2; col < W-2; col++) {
			newPixel = 0;
			for (rowOffset=-2; rowOffset<=2; rowOffset++) {
				for (colOffset=-2; colOffset<=2; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					newPixel += (*(m_destinationBmp + iOffset)) * gaussianMask[2 + rowOffset][2 + colOffset];
				}
			}
			i = (unsigned long)(row*3*W + col*3);
			*(m_destinationBmp + i) = newPixel / 159;
		}
	}

	/* Determine edge directions and gradient strengths */
	for (row = 1; row < H-1; row++) {
		for (col = 1; col < W-1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			Gx = 0;
			Gy = 0;
			/* Calculate the sum of the Sobel mask times the nine surrounding pixels in the x and y direction */
			for (rowOffset=-1; rowOffset<=1; rowOffset++) {
				for (colOffset=-1; colOffset<=1; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					Gx = Gx + (*(m_destinationBmp + iOffset) * GxMask[rowOffset + 1][colOffset + 1]);
					Gy = Gy + (*(m_destinationBmp + iOffset) * GyMask[rowOffset + 1][colOffset + 1]);
				}
			}

			gradient[row][col] = sqrt(pow(Gx,2.0) + pow(Gy,2.0));	// Calculate gradient strength			
			thisAngle = (atan2(Gx,Gy)/3.14159) * 180.0;		// Calculate actual direction of edge
			
			/* Convert actual edge direction to approximate value */
			if ( ( (thisAngle < 22.5) && (thisAngle > -22.5) ) || (thisAngle > 157.5) || (thisAngle < -157.5) )
				newAngle = 0;
			if ( ( (thisAngle > 22.5) && (thisAngle < 67.5) ) || ( (thisAngle < -112.5) && (thisAngle > -157.5) ) )
				newAngle = 45;
			if ( ( (thisAngle > 67.5) && (thisAngle < 112.5) ) || ( (thisAngle < -67.5) && (thisAngle > -112.5) ) )
				newAngle = 90;
			if ( ( (thisAngle > 112.5) && (thisAngle < 157.5) ) || ( (thisAngle < -22.5) && (thisAngle > -67.5) ) )
				newAngle = 135;
				
			edgeDir[row][col] = newAngle;		// Store the approximate edge direction of each pixel in one array
		}
	}

	/* Trace along all the edges in the image */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) {
			edgeEnd = false;
			if (gradient[row][col] > upperThreshold) {		// Check to see if current pixel has a high enough gradient strength to be part of an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]){		
					case 0:
						findEdge(0, 1, row, col, 0, lowerThreshold);
						break;
					case 45:
						findEdge(1, 1, row, col, 45, lowerThreshold);
						break;
					case 90:
						findEdge(1, 0, row, col, 90, lowerThreshold);
						break;
					case 135:
						findEdge(1, -1, row, col, 135, lowerThreshold);
						break;
					default :
						i = (unsigned long)(row*3*W + 3*col);
						*(m_destinationBmp + i) = 
						*(m_destinationBmp + i + 1) = 
						*(m_destinationBmp + i + 2) = 0;
						break;
					}
				}
			else {
				i = (unsigned long)(row*3*W + 3*col);
					*(m_destinationBmp + i) = 
					*(m_destinationBmp + i + 1) = 
					*(m_destinationBmp + i + 2) = 0;
			}	
		}
	}
	
	/* Suppress any pixels not changed by the edge tracing */
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {	
			// Recall each pixel is composed of 3 bytes
			i = (unsigned long)(row*3*W + 3*col);
			// If a pixel's grayValue is not black or white make it black
			if( ((*(m_destinationBmp + i) != 255) && (*(m_destinationBmp + i) != 0)) || ((*(m_destinationBmp + i + 1) != 255) && (*(m_destinationBmp + i + 1) != 0)) || ((*(m_destinationBmp + i + 2) != 255) && (*(m_destinationBmp + i + 2) != 0)) ) 
				*(m_destinationBmp + i) = 
				*(m_destinationBmp + i + 1) = 
				*(m_destinationBmp + i + 2) = 0; // Make pixel black
		}
	}

	/* Non-maximum Suppression */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			if (*(m_destinationBmp + i) == 255) {		// Check to see if current pixel is an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]) {		
					case 0:
						suppressNonMax( 1, 0, row, col, 0, lowerThreshold);
						break;
					case 45:
						suppressNonMax( 1, -1, row, col, 45, lowerThreshold);
						break;
					case 90:
						suppressNonMax( 0, 1, row, col, 90, lowerThreshold);
						break;
					case 135:
						suppressNonMax( 1, 1, row, col, 135, lowerThreshold);
						break;
					default :
						break;
				}
			}	
		}
	}
	
}

void CTripodDlg::findEdge(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow;
	int newCol;
	unsigned long i;
	bool edgeEnd = false;

	/* Find the row and column values for the next possible pixel on the edge */
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
		
	/* Determine edge directions and gradient strengths */
	while ( (edgeDir[newRow][newCol]==dir) && !edgeEnd && (gradient[newRow][newCol] > lowerThreshold) ) {
		/* Set the new pixel as white to show it is an edge */
		i = (unsigned long)(newRow*3*W + 3*newCol);
		*(m_destinationBmp + i) =
		*(m_destinationBmp + i + 1) =
		*(m_destinationBmp + i + 2) = 255;
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
	}	
}

void CTripodDlg::suppressNonMax(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow = 0;
	int newCol = 0;
	unsigned long i;
	bool edgeEnd = false;
	float nonMax[320][3];			// Temporarily stores gradients and positions of pixels in parallel edges
	int pixelCount = 0;					// Stores the number of pixels in parallel edges
	int count;						// A for loop counter
	int max[3];						// Maximum point in a wide edge
	
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	/* Find non-maximum parallel edges tracing up */
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Find non-maximum parallel edges tracing down */
	edgeEnd = false;
	colShift *= -1;
	rowShift *= -1;
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;	
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Suppress non-maximum edges */
	max[0] = 0;
	max[1] = 0;
	max[2] = 0;
	for (count = 0; count < pixelCount; count++) {
		if (nonMax[count][2] > max[2]) {
			max[0] = nonMax[count][0];
			max[1] = nonMax[count][1];
			max[2] = nonMax[count][2];
		}
	}
	for (count = 0; count < pixelCount; count++) {
		i = (unsigned long)(nonMax[count][0]*3*W + 3*nonMax[count][1]);
		*(m_destinationBmp + i) = 
		*(m_destinationBmp + i + 1) = 
		*(m_destinationBmp + i + 2) = 0;
	}
}

الگوریتم Canny در سی پلاس پلاس قسمت 1
الگوریتم Canny در سی پلاس پلاس قسمت 2
الگوریتم Canny در سی پلاس پلاس قسمت 3
الگوریتم Canny در سی پلاس پلاس قسمت 4

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

الگوریتم Canny در سی پلاس پلاس قسمت 2

مرحله 2: پیدا کردن قدرت و جهت گرادیان لبه.

گام بعدی استفاده از Mask های Sobel برای پیدا کردن قدرت و جهت گرادیان لبه برای هر پیکسل است. ابتدا ماسک های Sobel به محدوده پیکسل 3×3 پیکسل فعلی در هر دو جهت x و y اعمال می شود. سپس مجموع مقدار هر ماسک ضربدر پیکسل مربوطه به ترتیب به عنوان مقادیر Gx و Gy محاسبه می شود. ریشه دوم مربع Gx به اضافه Gy مربع برابر قدرت لبه است. Tangent معکوس Gx / Gy جهت لبه را تولید می کند. سپس جهت لبه تقریب شده است به یکی از چهار مقادیر ممکن که ایجاد می کند جهت های ممکن را که  یک لبه می تواند در یک تصویر از یک شبکه پیکسل مربع باشد. این جهت لبه در edgeDir [row] [col] ذخیره می شود و قدرت گرادیان در  array gradient[row] [col] ذخیره می شود.

 

CannyEdgeWeel

هر زاویه لبه در 11.25 درجه از یکی از  زاویه های ممکن به آن مقدار تغییر می کند.

 

#include "stdafx.h"
#include "tripod.h"
#include "tripodDlg.h"

#include "LVServerDefs.h"
#include "math.h"
#include <fstream>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>


#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

using namespace std;

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg dialog

CTripodDlg::CTripodDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CTripodDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CTripodDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

	//////////////// Set destination BMP to NULL first 
	m_destinationBitmapInfoHeader = NULL;

}

////////////////////// Additional generic functions

static unsigned PixelBytes(int w, int bpp)
{
    return (w * bpp + 7) / 8;
}

static unsigned DibRowSize(int w, int bpp)
{
    return (w * bpp + 31) / 32 * 4;
}

static unsigned DibRowSize(LPBITMAPINFOHEADER pbi)
{
    return DibRowSize(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibRowPadding(int w, int bpp)
{
    return DibRowSize(w, bpp) - PixelBytes(w, bpp);
}

static unsigned DibRowPadding(LPBITMAPINFOHEADER pbi)
{
    return DibRowPadding(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibImageSize(int w, int h, int bpp)
{
    return h * DibRowSize(w, bpp);
}

static size_t DibSize(int w, int h, int bpp)
{
    return sizeof (BITMAPINFOHEADER) + DibImageSize(w, h, bpp);
}

/////////////////////// end of generic functions


void CTripodDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CTripodDlg)
	DDX_Control(pDX, IDC_PROCESSEDVIEW, m_cVideoProcessedView);
	DDX_Control(pDX, IDC_UNPROCESSEDVIEW, m_cVideoUnprocessedView);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CTripodDlg, CDialog)
	//{{AFX_MSG_MAP(CTripodDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDEXIT, OnExit)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg message handlers

BOOL CTripodDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here

	// For Unprocessed view videoportal (top one)
	char sRegUnprocessedView[] = "HKEY_LOCAL_MACHINE\\Software\\UnprocessedView";
	m_cVideoUnprocessedView.PrepareControl("UnprocessedView", sRegUnprocessedView, 0 );	
	m_cVideoUnprocessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoUnprocessedView.ConnectCamera2();
	m_cVideoUnprocessedView.SetEnablePreview(TRUE);

	// For binary view videoportal (bottom one)
	char sRegProcessedView[] = "HKEY_LOCAL_MACHINE\\Software\\ProcessedView";
	m_cVideoProcessedView.PrepareControl("ProcessedView", sRegProcessedView, 0 );	
	m_cVideoProcessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoProcessedView.ConnectCamera2();
	m_cVideoProcessedView.SetEnablePreview(TRUE);

	// Initialize the size of binary videoportal
	m_cVideoProcessedView.SetPreviewMaxHeight(240);
	m_cVideoProcessedView.SetPreviewMaxWidth(320);

	// Uncomment if you wish to fix the live videoportal's size
	// m_cVideoUnprocessedView.SetPreviewMaxHeight(240);
	// m_cVideoUnprocessedView.SetPreviewMaxWidth(320);

	// Find the screen coodinates of the binary videoportal
	m_cVideoProcessedView.GetWindowRect(m_rectForProcessedView);
	ScreenToClient(m_rectForProcessedView);
	allocateDib(CSize(320, 240));

	// Start grabbing frame data for Procssed videoportal (bottom one)
	m_cVideoProcessedView.StartVideoHook(0);

	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CTripodDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CTripodDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CTripodDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CTripodDlg::OnExit() 
{
	// TODO: Add your control notification handler code here

	// Kill live view videoportal (top one)
	m_cVideoUnprocessedView.StopVideoHook(0);
    m_cVideoUnprocessedView.DisconnectCamera();	
	
	// Kill binary view videoportal (bottom one)
	m_cVideoProcessedView.StopVideoHook(0);
    m_cVideoProcessedView.DisconnectCamera();	

	// Kill program
	DestroyWindow();	

	

}

BEGIN_EVENTSINK_MAP(CTripodDlg, CDialog)
    //{{AFX_EVENTSINK_MAP(CTripodDlg)
	ON_EVENT(CTripodDlg, IDC_PROCESSEDVIEW, 1 /* PortalNotification */, OnPortalNotificationProcessedview, VTS_I4 VTS_I4 VTS_I4 VTS_I4)
	//}}AFX_EVENTSINK_MAP
END_EVENTSINK_MAP()

void CTripodDlg::OnPortalNotificationProcessedview(long lMsg, long lParam1, long lParam2, long lParam3) 
{
	// TODO: Add your control notification handler code here
	
	// This function is called at the camera's frame rate
    
#define NOTIFICATIONMSG_VIDEOHOOK	10

	// Declare some useful variables
	// QCSDKMFC.pdf (Quickcam MFC documentation) p. 103 explains the variables lParam1, lParam2, lParam3 too 
	
	LPBITMAPINFOHEADER lpBitmapInfoHeader; // Frame's info header contains info like width and height
	LPBYTE lpBitmapPixelData; // This pointer-to-long will point to the start of the frame's pixel data
    unsigned long lTimeStamp; // Time when frame was grabbed

	switch(lMsg) {
		case NOTIFICATIONMSG_VIDEOHOOK:
			{
				lpBitmapInfoHeader = (LPBITMAPINFOHEADER) lParam1; 
				lpBitmapPixelData = (LPBYTE) lParam2;
				lTimeStamp = (unsigned long) lParam3;

				grayScaleTheFrameData(lpBitmapInfoHeader, lpBitmapPixelData);
				doMyImageProcessing(lpBitmapInfoHeader); // Place where you'd add your image processing code
				displayMyResults(lpBitmapInfoHeader);

			}
			break;

		default:
			break;
	}	
}

void CTripodDlg::allocateDib(CSize sz)
{
	// Purpose: allocate information for a device independent bitmap (DIB)
	// Called from OnInitVideo

	if(m_destinationBitmapInfoHeader) {
		free(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader = NULL;
	}

	if(sz.cx | sz.cy) {
		m_destinationBitmapInfoHeader = (LPBITMAPINFOHEADER)malloc(DibSize(sz.cx, sz.cy, 24));
		ASSERT(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader->biSize = sizeof(BITMAPINFOHEADER);
		m_destinationBitmapInfoHeader->biWidth = sz.cx;
		m_destinationBitmapInfoHeader->biHeight = sz.cy;
		m_destinationBitmapInfoHeader->biPlanes = 1;
		m_destinationBitmapInfoHeader->biBitCount = 24;
		m_destinationBitmapInfoHeader->biCompression = 0;
		m_destinationBitmapInfoHeader->biSizeImage = DibImageSize(sz.cx, sz.cy, 24);
		m_destinationBitmapInfoHeader->biXPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biYPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biClrImportant = 0;
		m_destinationBitmapInfoHeader->biClrUsed = 0;
	}
}

void CTripodDlg::displayMyResults(LPBITMAPINFOHEADER lpThisBitmapInfoHeader)
{
	// displayMyResults: Displays results of doMyImageProcessing() in the videoport
	// Notes: StretchDIBits stretches a device-independent bitmap to the appropriate size

	CDC				*pDC;	// Device context to display bitmap data
	
	pDC = GetDC();	
	int nOldMode = SetStretchBltMode(pDC->GetSafeHdc(),COLORONCOLOR);

	StretchDIBits( 
		pDC->GetSafeHdc(),
		m_rectForProcessedView.left,				// videoportal left-most coordinate
		m_rectForProcessedView.top,					// videoportal top-most coordinate
		m_rectForProcessedView.Width(),				// videoportal width
		m_rectForProcessedView.Height(),			// videoportal height
		0,											// Row position to display bitmap in videoportal
		0,											// Col position to display bitmap in videoportal
		lpThisBitmapInfoHeader->biWidth,			// m_destinationBmp's number of columns
		lpThisBitmapInfoHeader->biHeight,			// m_destinationBmp's number of rows
		m_destinationBmp,							// The bitmap to display; use the one resulting from doMyImageProcessing
		(BITMAPINFO*)m_destinationBitmapInfoHeader, // The bitmap's header info e.g. width, height, number of bits etc
		DIB_RGB_COLORS,								// Use default 24-bit color table
		SRCCOPY										// Just display
	);
 
	SetStretchBltMode(pDC->GetSafeHdc(),nOldMode);

	ReleaseDC(pDC);

	// Note: 04/24/02 - Added the following:
	// Christopher Wagner cwagner@fas.harvard.edu noticed that memory wasn't being freed

	// Recall OnPortalNotificationProcessedview, which gets called everytime
	// a frame of data arrives, performs 3 steps:
	// (1) grayScaleTheFrameData - which mallocs m_destinationBmp
	// (2) doMyImageProcesing
	// (3) displayMyResults - which we're in now
	// Since we're finished with the memory we malloc'ed for m_destinationBmp
	// we should free it: 
	
	free(m_destinationBmp);

	// End of adds
}

void CTripodDlg::grayScaleTheFrameData(LPBITMAPINFOHEADER lpThisBitmapInfoHeader, LPBYTE lpThisBitmapPixelData)
{

	// grayScaleTheFrameData: Called by CTripodDlg::OnPortalNotificationBinaryview
	// Task: Read current frame pixel data and computes a grayscale version

	unsigned int	W, H;			  // Width and Height of current frame [pixels]
	BYTE            *sourceBmp;		  // Pointer to current frame of data
	unsigned int    row, col;
	unsigned long   i;
	BYTE			grayValue;

	BYTE			redValue;
	BYTE			greenValue;
	BYTE			blueValue;

    W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows

	// Store pixel data in row-column vector format
	// Recall that each pixel requires 3 bytes (red, blue and green bytes)
	// m_destinationBmp is a protected member and declared in binarizeDlg.h

	m_destinationBmp = (BYTE*)malloc(H*3*W*sizeof(BYTE));

	// Point to the current frame's pixel data
	sourceBmp = lpThisBitmapPixelData;

	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {

			// Recall each pixel is composed of 3 bytes
			i = (unsigned long)(row*3*W + 3*col);
        
			// The source pixel has a blue, green andred value:
			blueValue  = *(sourceBmp + i);
			greenValue = *(sourceBmp + i + 1);
			redValue   = *(sourceBmp + i + 2);

			// A standard equation for computing a grayscale value based on RGB values
			grayValue = (BYTE)(0.299*redValue + 0.587*greenValue + 0.114*blueValue);

			// The destination BMP will be a grayscale version of the source BMP
			*(m_destinationBmp + i)     = grayValue;
			*(m_destinationBmp + i + 1) = grayValue;
			*(m_destinationBmp + i + 2) = grayValue;
			
		}
	}
}


void CTripodDlg::doMyImageProcessing(LPBITMAPINFOHEADER lpThisBitmapInfoHeader)
{
	// doMyImageProcessing:  This is where you'd write your own image processing code
	// Task: Read a pixel's grayscale value and process accordingly

	unsigned int	W, H;			// Width and Height of current frame [pixels]
	unsigned int    row, col;		// Pixel's row and col positions
	unsigned long   i;				// Dummy variable for row-column vector
	int	    upperThreshold = 60;	// Gradient strength nessicary to start edge
	int		lowerThreshold = 30;	// Minimum gradient strength to continue edge
	unsigned long iOffset;			// Variable to offset row-column vector during sobel mask
	int rowOffset;					// Row offset from the current pixel
	int colOffset;					// Col offset from the current pixel
	int rowTotal = 0;				// Row position of offset pixel
	int colTotal = 0;				// Col position of offset pixel
	int Gx;							// Sum of Sobel mask products values in the x direction
	int Gy;							// Sum of Sobel mask products values in the y direction
	float thisAngle;				// Gradient direction based on Gx and Gy
	int newAngle;					// Approximation of the gradient direction
	bool edgeEnd;					// Stores whether or not the edge is at the edge of the possible image
	int GxMask[3][3];				// Sobel mask in the x direction
	int GyMask[3][3];				// Sobel mask in the y direction
	int newPixel;					// Sum pixel values for gaussian
	int gaussianMask[5][5];			// Gaussian mask

	W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows
	
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {
			edgeDir[row][col] = 0;
		}
	}

	/* Declare Sobel masks */
	GxMask[0][0] = -1; GxMask[0][1] = 0; GxMask[0][2] = 1;
	GxMask[1][0] = -2; GxMask[1][1] = 0; GxMask[1][2] = 2;
	GxMask[2][0] = -1; GxMask[2][1] = 0; GxMask[2][2] = 1;
	
	GyMask[0][0] =  1; GyMask[0][1] =  2; GyMask[0][2] =  1;
	GyMask[1][0] =  0; GyMask[1][1] =  0; GyMask[1][2] =  0;
	GyMask[2][0] = -1; GyMask[2][1] = -2; GyMask[2][2] = -1;

	/* Declare Gaussian mask */
	gaussianMask[0][0] = 2;		gaussianMask[0][1] = 4;		gaussianMask[0][2] = 5;		gaussianMask[0][3] = 4;		gaussianMask[0][4] = 2;	
	gaussianMask[1][0] = 4;		gaussianMask[1][1] = 9;		gaussianMask[1][2] = 12;	gaussianMask[1][3] = 9;		gaussianMask[1][4] = 4;	
	gaussianMask[2][0] = 5;		gaussianMask[2][1] = 12;	gaussianMask[2][2] = 15;	gaussianMask[2][3] = 12;	gaussianMask[2][4] = 2;	
	gaussianMask[3][0] = 4;		gaussianMask[3][1] = 9;		gaussianMask[3][2] = 12;	gaussianMask[3][3] = 9;		gaussianMask[3][4] = 4;	
	gaussianMask[4][0] = 2;		gaussianMask[4][1] = 4;		gaussianMask[4][2] = 5;		gaussianMask[4][3] = 4;		gaussianMask[4][4] = 2;	
	

	/* Gaussian Blur */
	for (row = 2; row < H-2; row++) {
		for (col = 2; col < W-2; col++) {
			newPixel = 0;
			for (rowOffset=-2; rowOffset<=2; rowOffset++) {
				for (colOffset=-2; colOffset<=2; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					newPixel += (*(m_destinationBmp + iOffset)) * gaussianMask[2 + rowOffset][2 + colOffset];
				}
			}
			i = (unsigned long)(row*3*W + col*3);
			*(m_destinationBmp + i) = newPixel / 159;
		}
	}

	/* Determine edge directions and gradient strengths */
	for (row = 1; row < H-1; row++) {
		for (col = 1; col < W-1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			Gx = 0;
			Gy = 0;
			/* Calculate the sum of the Sobel mask times the nine surrounding pixels in the x and y direction */
			for (rowOffset=-1; rowOffset<=1; rowOffset++) {
				for (colOffset=-1; colOffset<=1; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					Gx = Gx + (*(m_destinationBmp + iOffset) * GxMask[rowOffset + 1][colOffset + 1]);
					Gy = Gy + (*(m_destinationBmp + iOffset) * GyMask[rowOffset + 1][colOffset + 1]);
				}
			}

			gradient[row][col] = sqrt(pow(Gx,2.0) + pow(Gy,2.0));	// Calculate gradient strength			
			thisAngle = (atan2(Gx,Gy)/3.14159) * 180.0;		// Calculate actual direction of edge
			
			/* Convert actual edge direction to approximate value */
			if ( ( (thisAngle < 22.5) && (thisAngle > -22.5) ) || (thisAngle > 157.5) || (thisAngle < -157.5) )
				newAngle = 0;
			if ( ( (thisAngle > 22.5) && (thisAngle < 67.5) ) || ( (thisAngle < -112.5) && (thisAngle > -157.5) ) )
				newAngle = 45;
			if ( ( (thisAngle > 67.5) && (thisAngle < 112.5) ) || ( (thisAngle < -67.5) && (thisAngle > -112.5) ) )
				newAngle = 90;
			if ( ( (thisAngle > 112.5) && (thisAngle < 157.5) ) || ( (thisAngle < -22.5) && (thisAngle > -67.5) ) )
				newAngle = 135;
				
			edgeDir[row][col] = newAngle;		// Store the approximate edge direction of each pixel in one array
		}
	}

	/* Trace along all the edges in the image */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) {
			edgeEnd = false;
			if (gradient[row][col] > upperThreshold) {		// Check to see if current pixel has a high enough gradient strength to be part of an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]){		
					case 0:
						findEdge(0, 1, row, col, 0, lowerThreshold);
						break;
					case 45:
						findEdge(1, 1, row, col, 45, lowerThreshold);
						break;
					case 90:
						findEdge(1, 0, row, col, 90, lowerThreshold);
						break;
					case 135:
						findEdge(1, -1, row, col, 135, lowerThreshold);
						break;
					default :
						i = (unsigned long)(row*3*W + 3*col);
						*(m_destinationBmp + i) = 
						*(m_destinationBmp + i + 1) = 
						*(m_destinationBmp + i + 2) = 0;
						break;
					}
				}
			else {
				i = (unsigned long)(row*3*W + 3*col);
					*(m_destinationBmp + i) = 
					*(m_destinationBmp + i + 1) = 
					*(m_destinationBmp + i + 2) = 0;
			}	
		}
	}
	
	/* Suppress any pixels not changed by the edge tracing */
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {	
			// Recall each pixel is composed of 3 bytes
			i = (unsigned long)(row*3*W + 3*col);
			// If a pixel's grayValue is not black or white make it black
			if( ((*(m_destinationBmp + i) != 255) && (*(m_destinationBmp + i) != 0)) || ((*(m_destinationBmp + i + 1) != 255) && (*(m_destinationBmp + i + 1) != 0)) || ((*(m_destinationBmp + i + 2) != 255) && (*(m_destinationBmp + i + 2) != 0)) ) 
				*(m_destinationBmp + i) = 
				*(m_destinationBmp + i + 1) = 
				*(m_destinationBmp + i + 2) = 0; // Make pixel black
		}
	}

	/* Non-maximum Suppression */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			if (*(m_destinationBmp + i) == 255) {		// Check to see if current pixel is an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]) {		
					case 0:
						suppressNonMax( 1, 0, row, col, 0, lowerThreshold);
						break;
					case 45:
						suppressNonMax( 1, -1, row, col, 45, lowerThreshold);
						break;
					case 90:
						suppressNonMax( 0, 1, row, col, 90, lowerThreshold);
						break;
					case 135:
						suppressNonMax( 1, 1, row, col, 135, lowerThreshold);
						break;
					default :
						break;
				}
			}	
		}
	}
	
}

void CTripodDlg::findEdge(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow;
	int newCol;
	unsigned long i;
	bool edgeEnd = false;

	/* Find the row and column values for the next possible pixel on the edge */
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
		
	/* Determine edge directions and gradient strengths */
	while ( (edgeDir[newRow][newCol]==dir) && !edgeEnd && (gradient[newRow][newCol] > lowerThreshold) ) {
		/* Set the new pixel as white to show it is an edge */
		i = (unsigned long)(newRow*3*W + 3*newCol);
		*(m_destinationBmp + i) =
		*(m_destinationBmp + i + 1) =
		*(m_destinationBmp + i + 2) = 255;
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
	}	
}

void CTripodDlg::suppressNonMax(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow = 0;
	int newCol = 0;
	unsigned long i;
	bool edgeEnd = false;
	float nonMax[320][3];			// Temporarily stores gradients and positions of pixels in parallel edges
	int pixelCount = 0;					// Stores the number of pixels in parallel edges
	int count;						// A for loop counter
	int max[3];						// Maximum point in a wide edge
	
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	/* Find non-maximum parallel edges tracing up */
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Find non-maximum parallel edges tracing down */
	edgeEnd = false;
	colShift *= -1;
	rowShift *= -1;
	if (colShift < 0) {
		if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;	
	if (rowShift < 0) {
		if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) {
			if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) {
			if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Suppress non-maximum edges */
	max[0] = 0;
	max[1] = 0;
	max[2] = 0;
	for (count = 0; count < pixelCount; count++) {
		if (nonMax[count][2] > max[2]) {
			max[0] = nonMax[count][0];
			max[1] = nonMax[count][1];
			max[2] = nonMax[count][2];
		}
	}
	for (count = 0; count < pixelCount; count++) {
		i = (unsigned long)(nonMax[count][0]*3*W + 3*nonMax[count][1]);
		*(m_destinationBmp + i) = 
		*(m_destinationBmp + i + 1) = 
		*(m_destinationBmp + i + 2) = 0;
	}
}

الگوریتم Canny در سی پلاس پلاس قسمت 1
الگوریتم Canny در سی پلاس پلاس قسمت 2
الگوریتم Canny در سی پلاس پلاس قسمت 3
الگوریتم Canny در سی پلاس پلاس قسمت 4

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

الگوریتم Canny در سی پلاس پلاس قسمت 1

الگوریتم Canny در ++C

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

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

 

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

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

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

 

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

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

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

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

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

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

 

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

 

 

 

کد الگوریتم Canny در ++C:

برای الگوریتم Canny دو کد زیر ارائه می شود که کد شماره 2 کد کاملتری است.

کد شماره  الگوریتم 1 الگوریتم Canny در ++C:

در زیر استفاده از الگوریتم کنی در ++C است. توجه داشته باشید که تصویر ابتدا به تصویر سیاه و سفید تبدیل می شود، سپس فیلتر گاوسی برای کاهش نویز در تصویر استفاده می شود. سپس الگوریتم Canny برای تشخیص لبه استفاده می شود.

 

// CannyTutorial.cpp : Defines the entry point for the console application. 
// Environment: Visual studio 2015, Windows 10
// Assumptions: Opecv is installed configured in the visual studio project
// Opencv version: OpenCV 3.1

#include "stdafx.h"
#include<opencv2/highgui/highgui.hpp>
#include<opencv2/imgproc/imgproc.hpp>
#include<string>
#include<iostream>


int main()
{

    //Modified from source: https://github.com/MicrocontrollersAndMore/OpenCV_3_Windows_10_Installation_Tutorial
    cv::Mat imgOriginal;        // input image
    cv::Mat imgGrayscale;        // grayscale of input image
    cv::Mat imgBlurred;            // intermediate blured image
    cv::Mat imgCanny;            // Canny edge image

    std::cout << "Please enter an image filename : ";     std::string img_addr;     std::cin >> img_addr;

    std::cout << "Searching for " + img_addr << std::endl;

    imgOriginal = cv::imread(img_addr);            // open image

    if (imgOriginal.empty()) {                                    // if unable to open image
        std::cout << "error: image not read from file\n\n";        // show error message on command line
        return(0);                                                // and exit program
    }

    cv::cvtColor(imgOriginal, imgGrayscale, CV_BGR2GRAY);        // convert to grayscale

    cv::GaussianBlur(imgGrayscale,            // input image
        imgBlurred,                            // output image
        cv::Size(5, 5),                        // smoothing window width and height in pixels
        1.5);                                // sigma value, determines how much the image will be blurred

    cv::Canny(imgBlurred,            // input image
        imgCanny,                    // output image
        100,                        // low threshold
        200);                        // high threshold


    // Declare windows
    // Note: you can use CV_WINDOW_NORMAL which allows resizing the window
    // or CV_WINDOW_AUTOSIZE for a fixed size window matching the resolution of the image
    // CV_WINDOW_AUTOSIZE is the default
    cv::namedWindow("imgOriginal", CV_WINDOW_AUTOSIZE);        
    cv::namedWindow("imgCanny", CV_WINDOW_AUTOSIZE);

    //Show windows
    cv::imshow("imgOriginal", imgOriginal);        
    cv::imshow("imgCanny", imgCanny);

    cv::waitKey(0);                    // hold windows open until user presses a key
    return 0;
}

 

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

رمز فایل : behsanandish.com

 

 

کد شماره 2:

مرحله 1: یک blur(تار کننده) گاوسی را اعمال کنید.

اول متغیرهای ضروری اعلام شده اند و بعضی از آنها اولیه هستند. سپس Blur گاوسی اعمال می شود. برای انجام این کار یک ماسک 5×5 بر روی تصویر منتقل می شود. هر پیکسل به صورت مجموع مقادیر پیکسل در محدوده 5×5 آن ضربدر وزن گاوسی متناظر تقسیم شده توسط وزن مجموع کل ماسک تعریف می شود.

 

ماسک گاوسی

ماسک گاوسی

 

#include "stdafx.h"
#include "tripod.h"
#include "tripodDlg.h"

#include "LVServerDefs.h"
#include "math.h"
#include <fstream>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>


#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

using namespace std;

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg dialog

CTripodDlg::CTripodDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CTripodDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CTripodDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

	//////////////// Set destination BMP to NULL first 
	m_destinationBitmapInfoHeader = NULL;

}

////////////////////// Additional generic functions

static unsigned PixelBytes(int w, int bpp)
{
    return (w * bpp + 7) / 8;
}

static unsigned DibRowSize(int w, int bpp)
{
    return (w * bpp + 31) / 32 * 4;
}

static unsigned DibRowSize(LPBITMAPINFOHEADER pbi)
{
    return DibRowSize(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibRowPadding(int w, int bpp)
{
    return DibRowSize(w, bpp) - PixelBytes(w, bpp);
}

static unsigned DibRowPadding(LPBITMAPINFOHEADER pbi)
{
    return DibRowPadding(pbi->biWidth, pbi->biBitCount);
}

static unsigned DibImageSize(int w, int h, int bpp)
{
    return h * DibRowSize(w, bpp);
}

static size_t DibSize(int w, int h, int bpp)
{
    return sizeof (BITMAPINFOHEADER) + DibImageSize(w, h, bpp);
}

/////////////////////// end of generic functions


void CTripodDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CTripodDlg)
	DDX_Control(pDX, IDC_PROCESSEDVIEW, m_cVideoProcessedView);
	DDX_Control(pDX, IDC_UNPROCESSEDVIEW, m_cVideoUnprocessedView);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CTripodDlg, CDialog)
	//{{AFX_MSG_MAP(CTripodDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDEXIT, OnExit)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTripodDlg message handlers

BOOL CTripodDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000); CMenu* pSysMenu = GetSystemMenu(FALSE); if (pSysMenu != NULL) { CString strAboutMenu; strAboutMenu.LoadString(IDS_ABOUTBOX); if (!strAboutMenu.IsEmpty()) { pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here

	// For Unprocessed view videoportal (top one)
	char sRegUnprocessedView[] = "HKEY_LOCAL_MACHINE\\Software\\UnprocessedView";
	m_cVideoUnprocessedView.PrepareControl("UnprocessedView", sRegUnprocessedView, 0 );	
	m_cVideoUnprocessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoUnprocessedView.ConnectCamera2();
	m_cVideoUnprocessedView.SetEnablePreview(TRUE);

	// For binary view videoportal (bottom one)
	char sRegProcessedView[] = "HKEY_LOCAL_MACHINE\\Software\\ProcessedView";
	m_cVideoProcessedView.PrepareControl("ProcessedView", sRegProcessedView, 0 );	
	m_cVideoProcessedView.EnableUIElements(UIELEMENT_STATUSBAR,0,TRUE);
	m_cVideoProcessedView.ConnectCamera2();
	m_cVideoProcessedView.SetEnablePreview(TRUE);

	// Initialize the size of binary videoportal
	m_cVideoProcessedView.SetPreviewMaxHeight(240);
	m_cVideoProcessedView.SetPreviewMaxWidth(320);

	// Uncomment if you wish to fix the live videoportal's size
	// m_cVideoUnprocessedView.SetPreviewMaxHeight(240);
	// m_cVideoUnprocessedView.SetPreviewMaxWidth(320);

	// Find the screen coodinates of the binary videoportal
	m_cVideoProcessedView.GetWindowRect(m_rectForProcessedView);
	ScreenToClient(m_rectForProcessedView);
	allocateDib(CSize(320, 240));

	// Start grabbing frame data for Procssed videoportal (bottom one)
	m_cVideoProcessedView.StartVideoHook(0);

	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CTripodDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CTripodDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CTripodDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CTripodDlg::OnExit() 
{
	// TODO: Add your control notification handler code here

	// Kill live view videoportal (top one)
	m_cVideoUnprocessedView.StopVideoHook(0);
    m_cVideoUnprocessedView.DisconnectCamera();	
	
	// Kill binary view videoportal (bottom one)
	m_cVideoProcessedView.StopVideoHook(0);
    m_cVideoProcessedView.DisconnectCamera();	

	// Kill program
	DestroyWindow();	

	

}

BEGIN_EVENTSINK_MAP(CTripodDlg, CDialog)
    //{{AFX_EVENTSINK_MAP(CTripodDlg)
	ON_EVENT(CTripodDlg, IDC_PROCESSEDVIEW, 1 /* PortalNotification */, OnPortalNotificationProcessedview, VTS_I4 VTS_I4 VTS_I4 VTS_I4)
	//}}AFX_EVENTSINK_MAP
END_EVENTSINK_MAP()

void CTripodDlg::OnPortalNotificationProcessedview(long lMsg, long lParam1, long lParam2, long lParam3) 
{
	// TODO: Add your control notification handler code here
	
	// This function is called at the camera's frame rate
    
#define NOTIFICATIONMSG_VIDEOHOOK	10

	// Declare some useful variables
	// QCSDKMFC.pdf (Quickcam MFC documentation) p. 103 explains the variables lParam1, lParam2, lParam3 too 
	
	LPBITMAPINFOHEADER lpBitmapInfoHeader; // Frame's info header contains info like width and height
	LPBYTE lpBitmapPixelData; // This pointer-to-long will point to the start of the frame's pixel data
    unsigned long lTimeStamp; // Time when frame was grabbed

	switch(lMsg) {
		case NOTIFICATIONMSG_VIDEOHOOK:
			{
				lpBitmapInfoHeader = (LPBITMAPINFOHEADER) lParam1; 
				lpBitmapPixelData = (LPBYTE) lParam2;
				lTimeStamp = (unsigned long) lParam3;

				grayScaleTheFrameData(lpBitmapInfoHeader, lpBitmapPixelData);
				doMyImageProcessing(lpBitmapInfoHeader); // Place where you'd add your image processing code
				displayMyResults(lpBitmapInfoHeader);

			}
			break;

		default:
			break;
	}	
}

void CTripodDlg::allocateDib(CSize sz)
{
	// Purpose: allocate information for a device independent bitmap (DIB)
	// Called from OnInitVideo

	if(m_destinationBitmapInfoHeader) {
		free(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader = NULL;
	}

	if(sz.cx | sz.cy) {
		m_destinationBitmapInfoHeader = (LPBITMAPINFOHEADER)malloc(DibSize(sz.cx, sz.cy, 24));
		ASSERT(m_destinationBitmapInfoHeader);
		m_destinationBitmapInfoHeader->biSize = sizeof(BITMAPINFOHEADER);
		m_destinationBitmapInfoHeader->biWidth = sz.cx;
		m_destinationBitmapInfoHeader->biHeight = sz.cy;
		m_destinationBitmapInfoHeader->biPlanes = 1;
		m_destinationBitmapInfoHeader->biBitCount = 24;
		m_destinationBitmapInfoHeader->biCompression = 0;
		m_destinationBitmapInfoHeader->biSizeImage = DibImageSize(sz.cx, sz.cy, 24);
		m_destinationBitmapInfoHeader->biXPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biYPelsPerMeter = 0;
		m_destinationBitmapInfoHeader->biClrImportant = 0;
		m_destinationBitmapInfoHeader->biClrUsed = 0;
	}
}

void CTripodDlg::displayMyResults(LPBITMAPINFOHEADER lpThisBitmapInfoHeader)
{
	// displayMyResults: Displays results of doMyImageProcessing() in the videoport
	// Notes: StretchDIBits stretches a device-independent bitmap to the appropriate size

	CDC				*pDC;	// Device context to display bitmap data
	
	pDC = GetDC();	
	int nOldMode = SetStretchBltMode(pDC->GetSafeHdc(),COLORONCOLOR);

	StretchDIBits( 
		pDC->GetSafeHdc(),
		m_rectForProcessedView.left,				// videoportal left-most coordinate
		m_rectForProcessedView.top,					// videoportal top-most coordinate
		m_rectForProcessedView.Width(),				// videoportal width
		m_rectForProcessedView.Height(),			// videoportal height
		0,											// Row position to display bitmap in videoportal
		0,											// Col position to display bitmap in videoportal
		lpThisBitmapInfoHeader->biWidth,			// m_destinationBmp's number of columns
		lpThisBitmapInfoHeader->biHeight,			// m_destinationBmp's number of rows
		m_destinationBmp,							// The bitmap to display; use the one resulting from doMyImageProcessing
		(BITMAPINFO*)m_destinationBitmapInfoHeader, // The bitmap's header info e.g. width, height, number of bits etc
		DIB_RGB_COLORS,								// Use default 24-bit color table
		SRCCOPY										// Just display
	);
 
	SetStretchBltMode(pDC->GetSafeHdc(),nOldMode);

	ReleaseDC(pDC);

	// Note: 04/24/02 - Added the following:
	// Christopher Wagner cwagner@fas.harvard.edu noticed that memory wasn't being freed

	// Recall OnPortalNotificationProcessedview, which gets called everytime
	// a frame of data arrives, performs 3 steps:
	// (1) grayScaleTheFrameData - which mallocs m_destinationBmp
	// (2) doMyImageProcesing
	// (3) displayMyResults - which we're in now
	// Since we're finished with the memory we malloc'ed for m_destinationBmp
	// we should free it: 
	
	free(m_destinationBmp);

	// End of adds
}

void CTripodDlg::grayScaleTheFrameData(LPBITMAPINFOHEADER lpThisBitmapInfoHeader, LPBYTE lpThisBitmapPixelData)
{

	// grayScaleTheFrameData: Called by CTripodDlg::OnPortalNotificationBinaryview
	// Task: Read current frame pixel data and computes a grayscale version

	unsigned int	W, H;			  // Width and Height of current frame [pixels]
	BYTE            *sourceBmp;		  // Pointer to current frame of data
	unsigned int    row, col;
	unsigned long   i;
	BYTE			grayValue;

	BYTE			redValue;
	BYTE			greenValue;
	BYTE			blueValue;

    W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows

	// Store pixel data in row-column vector format
	// Recall that each pixel requires 3 bytes (red, blue and green bytes)
	// m_destinationBmp is a protected member and declared in binarizeDlg.h

	m_destinationBmp = (BYTE*)malloc(H*3*W*sizeof(BYTE));

	// Point to the current frame's pixel data
	sourceBmp = lpThisBitmapPixelData;

	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) { // Recall each pixel is composed of 3 bytes i = (unsigned long)(row*3*W + 3*col); // The source pixel has a blue, green andred value: blueValue = *(sourceBmp + i); greenValue = *(sourceBmp + i + 1); redValue = *(sourceBmp + i + 2); // A standard equation for computing a grayscale value based on RGB values grayValue = (BYTE)(0.299*redValue + 0.587*greenValue + 0.114*blueValue); // The destination BMP will be a grayscale version of the source BMP *(m_destinationBmp + i) = grayValue; *(m_destinationBmp + i + 1) = grayValue; *(m_destinationBmp + i + 2) = grayValue; } } } void CTripodDlg::doMyImageProcessing(LPBITMAPINFOHEADER lpThisBitmapInfoHeader) { // doMyImageProcessing: This is where you'd write your own image processing code // Task: Read a pixel's grayscale value and process accordingly unsigned int W, H; // Width and Height of current frame [pixels] unsigned int row, col; // Pixel's row and col positions unsigned long i; // Dummy variable for row-column vector int upperThreshold = 60; // Gradient strength nessicary to start edge int lowerThreshold = 30; // Minimum gradient strength to continue edge unsigned long iOffset; // Variable to offset row-column vector during sobel mask int rowOffset; // Row offset from the current pixel int colOffset; // Col offset from the current pixel int rowTotal = 0; // Row position of offset pixel int colTotal = 0; // Col position of offset pixel int Gx; // Sum of Sobel mask products values in the x direction int Gy; // Sum of Sobel mask products values in the y direction float thisAngle; // Gradient direction based on Gx and Gy int newAngle; // Approximation of the gradient direction bool edgeEnd; // Stores whether or not the edge is at the edge of the possible image int GxMask[3][3]; // Sobel mask in the x direction int GyMask[3][3]; // Sobel mask in the y direction int newPixel; // Sum pixel values for gaussian int gaussianMask[5][5]; // Gaussian mask W = lpThisBitmapInfoHeader->biWidth;  // biWidth: number of columns
    H = lpThisBitmapInfoHeader->biHeight; // biHeight: number of rows
	
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {
			edgeDir[row][col] = 0;
		}
	}

	/* Declare Sobel masks */
	GxMask[0][0] = -1; GxMask[0][1] = 0; GxMask[0][2] = 1;
	GxMask[1][0] = -2; GxMask[1][1] = 0; GxMask[1][2] = 2;
	GxMask[2][0] = -1; GxMask[2][1] = 0; GxMask[2][2] = 1;
	
	GyMask[0][0] =  1; GyMask[0][1] =  2; GyMask[0][2] =  1;
	GyMask[1][0] =  0; GyMask[1][1] =  0; GyMask[1][2] =  0;
	GyMask[2][0] = -1; GyMask[2][1] = -2; GyMask[2][2] = -1;

	/* Declare Gaussian mask */
	gaussianMask[0][0] = 2;		gaussianMask[0][1] = 4;		gaussianMask[0][2] = 5;		gaussianMask[0][3] = 4;		gaussianMask[0][4] = 2;	
	gaussianMask[1][0] = 4;		gaussianMask[1][1] = 9;		gaussianMask[1][2] = 12;	gaussianMask[1][3] = 9;		gaussianMask[1][4] = 4;	
	gaussianMask[2][0] = 5;		gaussianMask[2][1] = 12;	gaussianMask[2][2] = 15;	gaussianMask[2][3] = 12;	gaussianMask[2][4] = 2;	
	gaussianMask[3][0] = 4;		gaussianMask[3][1] = 9;		gaussianMask[3][2] = 12;	gaussianMask[3][3] = 9;		gaussianMask[3][4] = 4;	
	gaussianMask[4][0] = 2;		gaussianMask[4][1] = 4;		gaussianMask[4][2] = 5;		gaussianMask[4][3] = 4;		gaussianMask[4][4] = 2;	
	

	/* Gaussian Blur */
	for (row = 2; row < H-2; row++) {
		for (col = 2; col < W-2; col++) {
			newPixel = 0;
			for (rowOffset=-2; rowOffset<=2; rowOffset++) {
				for (colOffset=-2; colOffset<=2; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					newPixel += (*(m_destinationBmp + iOffset)) * gaussianMask[2 + rowOffset][2 + colOffset];
				}
			}
			i = (unsigned long)(row*3*W + col*3);
			*(m_destinationBmp + i) = newPixel / 159;
		}
	}

	/* Determine edge directions and gradient strengths */
	for (row = 1; row < H-1; row++) {
		for (col = 1; col < W-1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			Gx = 0;
			Gy = 0;
			/* Calculate the sum of the Sobel mask times the nine surrounding pixels in the x and y direction */
			for (rowOffset=-1; rowOffset<=1; rowOffset++) {
				for (colOffset=-1; colOffset<=1; colOffset++) {
					rowTotal = row + rowOffset;
					colTotal = col + colOffset;
					iOffset = (unsigned long)(rowTotal*3*W + colTotal*3);
					Gx = Gx + (*(m_destinationBmp + iOffset) * GxMask[rowOffset + 1][colOffset + 1]);
					Gy = Gy + (*(m_destinationBmp + iOffset) * GyMask[rowOffset + 1][colOffset + 1]);
				}
			}

			gradient[row][col] = sqrt(pow(Gx,2.0) + pow(Gy,2.0));	// Calculate gradient strength			
			thisAngle = (atan2(Gx,Gy)/3.14159) * 180.0;		// Calculate actual direction of edge
			
			/* Convert actual edge direction to approximate value */
			if ( ( (thisAngle < 22.5) && (thisAngle > -22.5) ) || (thisAngle > 157.5) || (thisAngle < -157.5) ) newAngle = 0; if ( ( (thisAngle > 22.5) && (thisAngle < 67.5) ) || ( (thisAngle < -112.5) && (thisAngle > -157.5) ) )
				newAngle = 45;
			if ( ( (thisAngle > 67.5) && (thisAngle < 112.5) ) || ( (thisAngle < -67.5) && (thisAngle > -112.5) ) )
				newAngle = 90;
			if ( ( (thisAngle > 112.5) && (thisAngle < 157.5) ) || ( (thisAngle < -22.5) && (thisAngle > -67.5) ) )
				newAngle = 135;
				
			edgeDir[row][col] = newAngle;		// Store the approximate edge direction of each pixel in one array
		}
	}

	/* Trace along all the edges in the image */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) { edgeEnd = false; if (gradient[row][col] > upperThreshold) {		// Check to see if current pixel has a high enough gradient strength to be part of an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]){		
					case 0:
						findEdge(0, 1, row, col, 0, lowerThreshold);
						break;
					case 45:
						findEdge(1, 1, row, col, 45, lowerThreshold);
						break;
					case 90:
						findEdge(1, 0, row, col, 90, lowerThreshold);
						break;
					case 135:
						findEdge(1, -1, row, col, 135, lowerThreshold);
						break;
					default :
						i = (unsigned long)(row*3*W + 3*col);
						*(m_destinationBmp + i) = 
						*(m_destinationBmp + i + 1) = 
						*(m_destinationBmp + i + 2) = 0;
						break;
					}
				}
			else {
				i = (unsigned long)(row*3*W + 3*col);
					*(m_destinationBmp + i) = 
					*(m_destinationBmp + i + 1) = 
					*(m_destinationBmp + i + 2) = 0;
			}	
		}
	}
	
	/* Suppress any pixels not changed by the edge tracing */
	for (row = 0; row < H; row++) {
		for (col = 0; col < W; col++) {	
			// Recall each pixel is composed of 3 bytes
			i = (unsigned long)(row*3*W + 3*col);
			// If a pixel's grayValue is not black or white make it black
			if( ((*(m_destinationBmp + i) != 255) && (*(m_destinationBmp + i) != 0)) || ((*(m_destinationBmp + i + 1) != 255) && (*(m_destinationBmp + i + 1) != 0)) || ((*(m_destinationBmp + i + 2) != 255) && (*(m_destinationBmp + i + 2) != 0)) ) 
				*(m_destinationBmp + i) = 
				*(m_destinationBmp + i + 1) = 
				*(m_destinationBmp + i + 2) = 0; // Make pixel black
		}
	}

	/* Non-maximum Suppression */
	for (row = 1; row < H - 1; row++) {
		for (col = 1; col < W - 1; col++) {
			i = (unsigned long)(row*3*W + 3*col);
			if (*(m_destinationBmp + i) == 255) {		// Check to see if current pixel is an edge
				/* Switch based on current pixel's edge direction */
				switch (edgeDir[row][col]) {		
					case 0:
						suppressNonMax( 1, 0, row, col, 0, lowerThreshold);
						break;
					case 45:
						suppressNonMax( 1, -1, row, col, 45, lowerThreshold);
						break;
					case 90:
						suppressNonMax( 0, 1, row, col, 90, lowerThreshold);
						break;
					case 135:
						suppressNonMax( 1, 1, row, col, 135, lowerThreshold);
						break;
					default :
						break;
				}
			}	
		}
	}
	
}

void CTripodDlg::findEdge(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow;
	int newCol;
	unsigned long i;
	bool edgeEnd = false;

	/* Find the row and column values for the next possible pixel on the edge */
	if (colShift < 0) { if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) { if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) { newRow = row + rowShift; } else edgeEnd = true; /* Determine edge directions and gradient strengths */ while ( (edgeDir[newRow][newCol]==dir) && !edgeEnd && (gradient[newRow][newCol] > lowerThreshold) ) {
		/* Set the new pixel as white to show it is an edge */
		i = (unsigned long)(newRow*3*W + 3*newCol);
		*(m_destinationBmp + i) =
		*(m_destinationBmp + i + 1) =
		*(m_destinationBmp + i + 2) = 255;
		if (colShift < 0) { if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) { if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
	}	
}

void CTripodDlg::suppressNonMax(int rowShift, int colShift, int row, int col, int dir, int lowerThreshold)
{
	int W = 320;
	int H = 240;
	int newRow = 0;
	int newCol = 0;
	unsigned long i;
	bool edgeEnd = false;
	float nonMax[320][3];			// Temporarily stores gradients and positions of pixels in parallel edges
	int pixelCount = 0;					// Stores the number of pixels in parallel edges
	int count;						// A for loop counter
	int max[3];						// Maximum point in a wide edge
	
	if (colShift < 0) { if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;		// If the next pixel would be off image, don't do the while loop
	if (rowShift < 0) { if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	/* Find non-maximum parallel edges tracing up */
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) { if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) { if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Find non-maximum parallel edges tracing down */
	edgeEnd = false;
	colShift *= -1;
	rowShift *= -1;
	if (colShift < 0) { if (col > 0)
			newCol = col + colShift;
		else
			edgeEnd = true;
	} else if (col < W - 1) {
		newCol = col + colShift;
	} else
		edgeEnd = true;	
	if (rowShift < 0) { if (row > 0)
			newRow = row + rowShift;
		else
			edgeEnd = true;
	} else if (row < H - 1) {
		newRow = row + rowShift;
	} else
		edgeEnd = true;	
	i = (unsigned long)(newRow*3*W + 3*newCol);
	while ((edgeDir[newRow][newCol] == dir) && !edgeEnd && (*(m_destinationBmp + i) == 255)) {
		if (colShift < 0) { if (newCol > 0)
				newCol = newCol + colShift;
			else
				edgeEnd = true;	
		} else if (newCol < W - 1) {
			newCol = newCol + colShift;
		} else
			edgeEnd = true;	
		if (rowShift < 0) { if (newRow > 0)
				newRow = newRow + rowShift;
			else
				edgeEnd = true;
		} else if (newRow < H - 1) {
			newRow = newRow + rowShift;
		} else
			edgeEnd = true;	
		nonMax[pixelCount][0] = newRow;
		nonMax[pixelCount][1] = newCol;
		nonMax[pixelCount][2] = gradient[newRow][newCol];
		pixelCount++;
		i = (unsigned long)(newRow*3*W + 3*newCol);
	}

	/* Suppress non-maximum edges */
	max[0] = 0;
	max[1] = 0;
	max[2] = 0;
	for (count = 0; count < pixelCount; count++) { if (nonMax[count][2] > max[2]) {
			max[0] = nonMax[count][0];
			max[1] = nonMax[count][1];
			max[2] = nonMax[count][2];
		}
	}
	for (count = 0; count < pixelCount; count++) {
		i = (unsigned long)(nonMax[count][0]*3*W + 3*nonMax[count][1]);
		*(m_destinationBmp + i) = 
		*(m_destinationBmp + i + 1) = 
		*(m_destinationBmp + i + 2) = 0;
	}
}

الگوریتم Canny در سی پلاس پلاس قسمت 1
الگوریتم Canny در سی پلاس پلاس قسمت 2
الگوریتم Canny در سی پلاس پلاس قسمت 3
الگوریتم Canny در سی پلاس پلاس فسمت 4

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

عامل های هوشمند قسمت 5

عامل های هوشمند در هوش مصنوعی

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

عامل ها و محیط ها

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

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

تأکید میکنیم که فرضیه ی عامل، ابزاری برای تحلیل سیسیتم هاست، نه یک ویژگی خاص برای تقسیم دنیا به عامل و غیر عامل ها. ماشین حساب را میتوان عاملی در نظر گرفت که با توجه به “دنباله ادراک” ، “=2+2” نماد “4” را نمایش میدهد. اما این تحلیل منجر به درک ماشین حساب نمیشود. از جهاتی تمام حوزه های مهندسی را می توان طراحی کننده ی محصولات مصنوعی دانست که با دنیا تعامل دارند؛ AI (از نظر مؤلفین) در انتهای این طیف واقع است، که در آنجا، محصولات مصنوعی، منابع محاسباتی ارزشمندی دارند و محیط کار ، نیازمند تصمیم گیری مهم است.

رفتار خوب : مفهوم خردمندی یا عقلانیت

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

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

روشن است برای تمام کارها و عامل ها، یک معیار کارایی ثابت وجود ندارد؛ معمولا طراح، یک معیار را برای شرایط خاصی ، مناسب می بیند. این کار، چندان آسان نیست.

• خردمندی یا عقلانیت (rationality)

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

1. معیار کارایی که ملاک های موفقیت را تعریف می کند.

2. دانش قبلی عامل نسبت به محیط.

3. فعالیتهایی که عامل میتواند انجام دهد.

4. دنباله ی ادراک عامل در این زمان.

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

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

• همه چیزدانی، یادگیری و خود مختاری

باید بین “همه چیزدانی” و خردمندی تمایز قائل شویم. عامل “همه چیزدان”، خروجی واقعی فعالیت های خودش را می داند و می تواند بر اساس آن عمل کند. اما “همه چیزدان” بودن عامل، غیرممکن است. این مثال را در نظر بگیرید: من روزی در حال قدم زدن با احمد هستم و دوست قدیمی خود را در آن طرف خیابان می بینم. هیچ ترافیکی وجود ندارد و “خردمندی” حکم میکند که در عرض خیابان حرکت کنم. در همین حال، در فاصله 33000 فوتی، یک هواپیمای مسافری با هواپیمای باری برخورد میکند و قبل از اینکه به آن طرف خیابان بروم، نقش بر زمین میشوم. آیا عبور از عرض خیابان، عقلایی (خردمندی) نبود؟ بعید است کسی بگوید که عبور از عرض خیابان حماقت بوده است.

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

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

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

منبع

منابع

1.https://fa.wikipedia.org

2.http://retro-code.ir

3.http://www.sourcecodes.ir

 

 

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

عامل های هوشمند قسمت 4

♦ عامل های مبتنی بر هدف (goal-based agents)

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

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

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

گرچه عامل مبتنی ببر هدف کارایی چندانی ندارد، قابلیت انعطاف آن بیشتر است. زیرا دانشی که از تصمیمات آن پشتیبانی می کند، صریحا نمایش داده می شود و قابل اصلاح است. برای عامل واکنشی، باید بسیاری از “قوانین شرط فعالیت” را بازنویسی کنیم. رفتار عامل مبتنی بر هدف می تواند تغییر کند تا به هدف مورد نظر برسد.

♦ عامل های مبتنی بر سودمندی (utility-based agents)

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

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

این روش، تنها روش خردمند بودن نیست، اما همانند عامل های مبتنی بر هدف، عامل های مبتنی بر سودمندی از نظر قابلیت انعطاف و یادگیری، امتیازات زیادی دارند. علاوه بر این، در دو مورد اهداف چندان روشن نیستند، ولی عامل مبتنی بر سودمندی هنوز میتواند تصمیمات خردمندانه بگیرد.

اولا، وقتی اهداف با هم متضاد باشند فقط بعضی از آنها قابل دستیابی هستند، که در این مورد تابع سودمندی، توازن مناسبی را بین اهداف متضاد برقرار میکند. ثانیا، وقتی چندین هدف وجود دارند که عامل میتواندبرای دستیابی به آنها کمک کند،ولی هیچ کدام از آنها با اطمینان قابل دستیابی نباشند، تابع سودمندی میتواند احتمال موفقیت اهداف را بر حسب اهمیت آنها ، افزایش دهد.

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

ماهیت محیط های عامل های هوشمند

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

تعیین کردن محیط کار

تعیین نوع عامل، معیار کارایی، محیط، حسگرها (سنسورها) و محرک ها را تحت عنوان محیط کار دسته بندی می کنیم. برای خلاصه ، این ها را به نام PEAS می خوانیم. اولین قدم در طراحی عامل، مشخص کردن محیط کار آن است. برای مثال، از مسئله ی “راننده تاکسی خودکار” (اتوماتیک) استفاده میکنیم. توجه کنید که تاکسی خودکار مورد بحث ما، خارج از قابلیت های فناوری فعلی است. وظیفه رانندگی، محدودیتی در ترکیب شرایط ندارد. هر یک از عناصر محیط کار را بیشتر مورد بحث قرار میدهیم.

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

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

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

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

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

خواص محیط های کار (task environment)

بدیهی است که حدود محیط های کار AI بسیار گسترده است. می توانیم محیط های کار را به چند بعد تقسیم کنیم. این ابعاد، طراحی مناسب عامل و قابلیت اجرای هر خانواده از تکنیک ها را برای محیط عامل تعیین میکنند. این ابعاد عبارتنداز:

• “کاملا قابل مشاهده” در مقابل “پاره ای قابل مشاهده” (Fully observable vs. partially observable) :

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

• تک عاملی در برابر چند عاملی (Single agent vs. multiagent) :

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

• قطعی در مقابل اتفاقی (Deterministic vs. stochastic) :

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

• مرحله ای در مقابل ترتیبی (Episodic vs. sequential) :

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

• ایستا در مقابل پویا (Static vs. dynamic) :

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

• گسسته در مقابل پیوسته (Discrete vs. continuous) :

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

• شناخته شده در مقابل ناشناخته (Known vs. unknown) :

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

 

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

عامل های هوشمند قسمت 3

عامل های هدف گرا

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

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

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

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

عامل های مبتنی بر سودمندی

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

تنها موردی که برای عامل اهمپیت دارد رسیدن به هدف است! بدین ترتیب در این مثال سفر 5 ساعته ما به 50 ساعت افزایش پیدا خواهد کرد و عملا هوشمندی عامل مورد نظر شکست خورده و فاقد ارزش میباشد. (در مطالبی که مرتبط با الگورتیم های جستجوی هدف میباشند این مشکل را به وضوح مشاهده خواهید کرد.) پس میتوان نتیجه گیری نمود که  در مسئله فوق عواملی جز هدف وجود دارند که در استراتژی انتخاب واکنش ها تتاثیر چشم گیری میگذارند.

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

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

منبع : http://retro-code.ir

ساختار عامل های هوشمند

کار AI طراحی برنامه ی عامل است که “تابع عامل” را پیاده سازی می کند. تابع عامل، ادراکات را به فعالیت ها نگاشت می کند. فرض میکنیم این برنامه بر روی یک دستگاه محاسباتی با حسگرها و محرک های فیزیکی، یعنی معماری اجرا می شود: برنامه + معماری = عامل

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

♦ برنامه های عامل  (agent programs)

برنامه های عامل درک فعلی را به عنوان ورودی از حسگرها (سنسورها) می پذیرند، و فعالیت را از طریق محرک ها انجام می دهند. توجه داشته باشید که ، برنامه عامل درک فعلی را به عنوان ورودی می گیرد، ولی تابع عامل کل سابقه درک را دریافت میکند. برنامه ی عامل، فقط درک فعلی را به عنوان ورودی می پذیرد، زیرا هیچ چیز دیگری از محیط در دسترس نیست. اگر فعالیت های عامل ، به کل “دنباله ی ادراک” بستگی داشته باشد، عامل باید کل ادراک ها را به یاد بیاورد.

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

function TABLE-DRIVEN-AGENT (percept) returns an action
  presistent: percepts, a sequence, initially empty table, a table of actions, indexed by percept sequences, initially fully specified
    
  append percept to end of percepts
  action  &amp;amp;amp;lt; - -  LOOKUP(percepts,table)
  return action

برای هر درک جدید فراخوانی می شود و هر بار فعالیتی را بر می گرداند. با استفاده از برنامه TABLE-DRIVEN-AGENT ساختمان داده های خود، دنباله ادراک را ردیابی می کند.
برنامه TABLE-DRIVEN-AGENT  تابع عامل مطلوب را پیاده سازی میکند. چالش مهم AI، چگونگی نوشتن برنامه ای است که با استفاده از یک کد کوچک (به جای جدول بزرگ)، رفتار عقلایی را انجام دهد. مثال های زیادی داریم که نشان می دهد، این کار امکان پذیر است. به عنوان مثال، جدول های بزرگ ریشه دوم که قبل از دهه 1970 توسط مهندسین و دانش آموزان مورد استفاده قرار گرفت، جای خود را به یک برنامه  5 خطی داده است که از روش نیوتن استفاده میکند و در ماشین حساب های الکترونیکی قابل استفاده است. AI همان کاری را انجام می دهد که نیوتن برای ریشه دوم انجام میدهد.

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

♦ عامل های واکنشی ساده (simple reflex agents)

ساده ترین نوع عامل ها، عامل واکنشی ساده است. این عامل ها فعالیت ها را بر اساس درک فعلی و بدون در نظر گرفتن سابقه ی ادراک، انتخاب میکنند. فرض کنید راننده ی تاکسی خودکار هستید. اگر اتومبیل جلویی ترمز کند و چراغ ترمز آن روشن شود، باید آن را تشخیص دهید و ترمز کنید. به عبارت دیگر ، برخی پردازش ها بر روی دریافت اطلاعات تصویر ورودی صورت می گیرد تا شرایطی که ما آن را “ترمزکردن اتومبیل جلویی” می نامیم رخ دهد، سپس این رویداد موجب فعال شدن برخی اتصالات موجود در برنامه عامل خواهد شد و عمل “اقدام به ترمز” را فعال می سازد. این اتصال را قانون شرط فعالیت یا قانون شرط کنش می نامیم: اگر اتومبیل جلویی ترمز کرد آنگاه اقدام به ترمز کن.

انسان نیز  چنین اتصالاتی دارد، که بعضی از آنها پاسخ های آموخته شده هستند (مثل رانندگی) و بعضی دیگر غریزی هستند (مثل بستن چشم هنگام نزدیک شدن شی ء ای به آن). روش کلی و قابل انعطاف این است که یک مفسر همه منظوره برای قوانین شرط فعالیت ساخته شود و سپس مجموعه ای از قوانین برای محیط های کار خاص ایجاد گردد. در شکل زیر، برنامه ی عامل نشان داده شده است که خیلی ساده است. تابع INTERPRET-INPUT با استفاده از ادراک، یک توصیف انتزاعی از حالت فعلی ایجاد میکند، و تابع RULE-MATCH اولین قانون موجود در مجموعه ای از قوانین را بر می گرداند که با توصیف حالت خاص مطابقت دارد:

function  SIMPLE-REFLEX-AGENT (percept) returns an action
  presistent: ruless, a set of condition-action rules
    
  state  &amp;amp;amp;lt;  - - INTEERPRET-INPUT (percept)
  rule  &amp;amp;amp;lt; - -  RULE-MATCH (state,rules)
  action  &amp;amp;amp;lt;  - -  rule.ACTION
  return action

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

اجتناب از حلقه های بی نهایت، در صورتی ممکن است که عامل بتواند فعالیت خود را تصادفی کند. در بعضی موارد، “عامل واکنشی ساده ی تصادفی” ممکن است مثل “عامل واکنشی ساده ی قطعی” عمل کند. رفتار تصادفی درست، در بعضی از محیط های چند عاملی میتواند عقلایی باشد. در محیط های تک عاملی، فعالیت تصادفی معمولا عقلایی نیست. این روش، در بعضی از وضعیت ها به عامل واکنشی ساده کمک می کند. اما در اغلب موارد، با استفاده از عامل های قطعی تخصصی، بهتر می توان عمل کرد.

♦ عامل های واکنشی مبتنی بر مدل (model-based reflex  agents)

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

تغییر این اطلاعات داخلی با مرور زمان، مستلزم دو نوع دانش است که باید در برنامه عامل کدنویسی شود. اولا باید بدانیم که دنیا چگونه مستقل از عامل تکامل می یابد. ثانیا، باید بدانیم که فعالیت های عامل، چه تاثیری در دنیا دارد. این دانش درباره ی “چگونگی عملکرد جهان” چه به صورت مدارهای منطقی ساده پیاده سازی شود یا به صورت تئوری های علمی، مدلی از دنیا نام دارد. عاملی که از چنین مدلی استفاده میکند، عامل مبتنی بر مدل نام دارد. برنامه عامل در شکل زیر نشان داده شده است. بخش جالب، تابع UPDATE-STATE است که مسئول ایجاد توصیف جدیدی از حالت داخلی است. جزئیات چگونگی نمایش مدل ها و حالت ها، به نوع محیط و فناوری استفاده شده در طراحی عامل بستگی دارد.

function  MODEL-BASED-REFLEX-AGENT (percept) returns an action
  presistent: state, the agent's current conception of the world state
              model, a description of how the next state depends on current state and action
              rules, a set of condition-action rules 
              action, the most recent action, initially none
  
  state  &amp;amp;amp;amp;amp;lt; -- UPDATE-STATE (state, action, peercept, model)
  rule  &amp;amp;amp;amp;amp;lt; -- RULE-MATCH (state,rules)
  action  &amp;amp;amp;amp;amp;lt; -- rule.ACTION
  return action

عامل واکنشی مبتنی بر مدل، حالت فعلی دنیا را با یک مدل داخلی ردیابی، و همانند عامل واکنشی ساده، فعالیتی را انتخاب میکند.

عامل های هوشمند قسمت 1
عامل های هوشمند قسمت 2
عامل های هوشمند قسمت 3
عامل های هوشمند قسمت 4
عامل های هوشمند قسمت 5

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

عامل های هوشمند قسمت 1

عامل‌ های هوشمند

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

تعریف عامل:

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

نحوه کار عامل:

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

عامل خود مختار

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

انواع محیط ها

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

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

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

ایستا و پویا: اگر محیط در زمان تصمیم‌گیری عامل تغییر کند آنگاه محیط پویا است. و در غیر آن صورت محیط ایستا است. اما اگر محیط در زمان تصمیم‌گیری ثابت بماند اما زمان، کارایی عامل را کاهش دهد، محیط را نیمه پویا مینامیم.

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

ساختار عامل های هوشمند

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

عامل های واکنشی ساده

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

منبع

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

ساختار یک عامل

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

عامل هوشمند (Rational Agent)

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

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

برای رفع ابهام در مورد موفقیت عامل هوشمند، مفهومی با عنوان اندازه گیری عملکرد یا performance measure تعریف میشود. اندازه گیری عملکرد در واقع مجموعه ای از قوانین هستند که ما به عنوان طراحان یا شاهدان عملکرد عامل هشومند، وضع مینماییم تا بتوانیم عامل هوشمند خود را مورد سنجش قرار دهیم.

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

تفاوت ِعقلانیت و علم لایتناهی

نکته ای که از اهمیت بسیاری برخوردا است، تمیز دادن بین دو مفهوم عقلانیت و علم لایتناهی میباشد. یک عامل با علم لایتناهی نتیجه خروجی تمامی اعمال خود را میداند که بسیار هم عالی و خوب است! اما در دنیای واقعی عملا همچین عاملی وجود نخواهد داشت! به مثالی که در ادامه آماده توجه فرمایید.

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

سوالی که پیش می آید این است که تصمیم شما برای عبور از خیابان یک تصمیم اشتباه و غیر هوشمندانه بوده است؟ آیا از عمل شما به عنوان یک عمل غیر عقلانی یاد خواهد شد؟

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

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

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

عامل هوشمند ایده آل

مجموعه تعاریف و مطالب فوق، ما را به سمت تعرف مفوهم عامل هوشمند ایده آل هدایت مینماید. عامل هوشمند ایده آل، عاملی است که برای هر مجموعه از توالی مشاهدات، با توجه به شواهد موجود در محیط و دانش پیش ساخته خود، آن عملِ مورد انتظاری را انجام دهد که باعث افزایش اندازه عملکرد و یا همان performance measure بشود.

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

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

نگاشت ایده آل، از توالی مشاهدات به عمل

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

به چنین جدولی، جدول “نگاشت مشاهدات به عمل” میگویند. در اصول میتوان با تست اینکه چه عملی برای مشاهدات مناسب است این جدول را تکمیل نمود. باید توجه نمود که اگر میتوانیم از روی نگاشت، عامل هوشمند داشته باشیم از روی نگاشت ایده آل نیز میتوان به عامل هوشمند ایده آل رسید.

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

 

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

الگوریتم های ضروری یادگیری ماشین

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

انواع الگوریتم های یادگیری ماشین

سه نوع اصلی الگوریتم های یادگیری ماشین از قرار زیرند :

  • یادگیری نظارت شده (هدایت شده – Supervised Learning) : در این نوع از الگوریتم ها که بار اصلی یادگیری ماشین را بر دوش می کشند (از لحاظ تعداد الگوریتم های این نوع)، با دو نوع از متغیرها سروکار داریم . نوع اول که متغیرهای مستقل نامیده میشوند، یک یا چند متغیر هستند که قرار است بر اساس مقادیر آنها، یک متغیر دیگر را پیش بینی کنیم. مثلا سن مشتری و تحصیلات و میزان درآمد و وضعیت تاهل برای پیش بینی خرید یک کالا توسط یک مشتری ، متغیرهای مستقل هستند. نوع دوم هم متغیرهای وابسته یا هدف یا خروجی هستند و قرار است مقادیر آنها را به کمک این الگوریتم ها پیش بینی کنیم . برای این منظور باید تابعی ایجاد کنیم که ورودیها (متغیرهای مستقل) را گرفته و خروجی موردنظر (متغیر وابسته یا هدف) را تولید کند. فرآیند یافتن این تابع که در حقیقت کشف رابطه ای بین متغیرهای مستقل و متغیرهای وابسته است را فرآیند آموزش (Training Process) می گوئیم که روی داده های موجود (داده هایی که هم متغیرهای مستقل و هم متغیرهای وابسته آنها معلوم هستند مثلا خریدهای گذشته مشتریان یک فروشگاه) اعمال میشود و تا رسیدن به دقت لازم ادامه می یابد.  نمونه هایی از این الگوریتم ها عبارتند از رگرسیون، درختهای تصمیم ، جنگل های تصادفی، N نزدیک ترین همسایه، و رگرسیون لجستیک می باشند.
  • یادگیری بدون ناظر (unsupervised learning) : در این نوع از الگوریتم ها ، متغیر هدف نداریم و خروجی الگوریتم، نامشخص است. بهترین مثالی که برای این نوع از الگوریتم ها می توان زد، گروه بندی خودکار (خوشه بندی) یک جمعیت است مثلاً با داشتن اطلاعات شخصی و خریدهای مشتریان، به صورت خودکار آنها را به گروه های همسان و هم ارز تقسیم کنیم . الگوریتم Apriori و K-Means از این دسته هستند.

 

type of machine learning

  • یادگیری تقویت شونده (Reinforcement Learning) : نوع سوم از الگوریتم ها که شاید بتوان آنها را در زمره الگوریتم های بدون ناظر هم دسته بندی کرد، دسته ای هستند که از آنها با نام یادگیری تقویت شونده یاد میشود. در این نوع از الگوریتم ها، یک ماشین (در حقیقت برنامه کنترل کننده آن)، برای گرفتن یک تصمیم خاص ، آموزش داده می شود و ماشین بر اساس موقعیت فعلی (مجموعه متغیرهای موجود) و اکشن های مجاز (مثلا حرکت به جلو ، حرکت به عقب و …) ، یک تصمیم را می گیرد که در دفعات اول، این تصمیم می تواند کاملاً تصادفی باشد و به ازای هر اکشن یا رفتاری که بروز می دهد، سیستم یک فیدبک یا بازخورد یا امتیاز به او میدهد و از روی این فیدبک، ماشین متوجه میشود که تصمیم درست را اتخاذ کرده است یا نه که در دفعات بعد در آن موقعیت ، همان اکشن را تکرار کند یا اکشن و رفتار دیگری را امتحان کند.  با توجه به وابسته بودن حالت و رفتار فعلی به حالات و رفتارهای قبلی، فرآیند تصمیم گیری مارکوف ، یکی از مثالهای این گروه از الگوریتم ها می تواند باشد . الگوریتم های شبکه های عصبی هم می توانند ازین دسته به حساب آیند. منظور از کلمه تقویت شونده در نام گذاری این الگوریتم ها هم اشاره به مرحله فیدبک و بازخورد است که باعث تقویت و بهبود عملکرد برنامه و الگوریتم می شود .

نمونه ای از دسته بندی کلاسیک الگوریتم های یادگیری ماشین که بر اساس وجود یا عدم وجود عامل کنترل کننده (ناظر) و گسسته و پیوسته بودن متغیرها انجام شده است را می توانید در این شکل ببینید :

 

Machine learning algorithms

 

الگوریتم های اصلی و رایج یادگیری ماشین

در این سری از مقالات به آموزش الگوریتم های زیر با نمونه کدهای لازم و مثالهای تشریحی، خواهیم پرداخت :

  1. رگرسیون خطی
  2. رگرسیون لجستیک
  3. درخت تصمیم
  4. SVM
  5. Naive Bayes
  6. KNN
  7. K-Means
  8. جنگل تصادفی
  9. الگوریتم های کاهش ابعاد
  10. Gradient Boost & Ada Boost

 

طبقه بندی الگوریتم های مختلف یادگیری ماشین

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

در سال ۲۰۰۷ یک مقاله با عنوان ده الگوریتم برتر حوزه داده کاوی در دنیا توسط دانشگاه ورمونت مطرح شد که نسخه فارسی شده و حتی آماده انتشار به صورت کتاب آنرا هم در ایران داریم . مقاله فارسی را می توانید از این لینک دانلود نمایید.

10 الگریتم برترین های داده کاوی

رمز : behsanandish.com

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

در سال ۲۰۱۱، در سایت پرسش و پاسخ معروف Qura در پاسخ به سوالی که ده الگوریتم برتر داده کاوی را پرسیده بود، موارد زیر توسط کاربران برشمرده شده اند :

  1. Kernel Density Estimation and Non-parametric Bayes Classifier
  2. K-Means
  3. Kernel Principal Components Analysis
  4. Linear Regression
  5. Neighbors (Nearest, Farthest, Range, k, Classification)
  6. Non-Negative Matrix Factorization
  7. Dimensionality Reduction
  8. Fast Singular Value Decomposition
  9. Decision Tree
  10. Bootstapped SVM
  11. Decision Tree
  12. Gaussian Processes
  13. Logistic Regression
  14. Logit Boost
  15. Model Tree
  16. Naïve Bayes
  17. Nearest Neighbors
  18. PLS
  19. Random Forest
  20. Ridge Regression
  21. Support Vector Machine
  22. Classification: logistic regression, naïve bayes, SVM, decision tree
  23. Regression: multiple regression, SVM
  24. Attribute importance: MDL
  25. Anomaly detection: one-class SVM
  26. Clustering: k-means, orthogonal partitioning
  27. Association: A Priori
  28. Feature extraction: NNMF

و در سال ۲۰۱۵ این لیست به صورت زیر در آمده است :

  1. Linear regression
  2. Logistic regression
  3. k-means
  4. SVMs
  5. Random Forests
  6. Matrix Factorization/SVD
  7. Gradient Boosted Decision Trees/Machines
  8. Naive Bayes
  9. Artificial Neural Networks
  10. For the last one I’d let you pick one of the following:
  11. Bayesian Networks
  12. Elastic Nets
  13. Any other clustering algo besides k-means
  14. LDA
  15. Conditional Random Fields
  16. HDPs or other Bayesian non-parametric model

سایت DataFloq اخیراً یک طبقه بندی گرافیکی از الگوریتم های ضروری یادگیری ماشین ارائه کرده است که به صورت طبقه بندی شده ، این الگوریتم ها را فهرست کرده است :

 

12-algorithms-every-data-scientist-should-know

 

این طبقه بندی را به صورت نقشه ذهن یا Mind Map هم می توانیم مشاهده کنیم :

 

Machine Learning Algorithms

 

 

منبع

 

 

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