Đề tài Xử lý ảnh các phương pháp dò biên

ủa ảnh là điểm có sự biến đổi đột ngột về độ xám. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M Như vậy, phát hiện biên một cách lý tưởng là xác định được tất cả cả các đường bao trong đối tượng. Định nghĩa toán học của biên ở trên là cơ sở cho các kỹ thuật phát hiện biên. Điều quan trọng là sự biến thiên mức xám giữa các điểm ảnh trong một vùng thường là nhỏ, trong khi đó biến thiên mức xám của điểm giáp ranh lại khá hơn. 1.2. Phân loại các kỹ thuật phát hiện biên Xuất phát từ định nghĩa toán học của biên người ta thường sử dụng 2 phương pháp phát hiện biên sau: - Phương pháp phát hiện biên trực tiếp: Phương pháp này nhằm làm nổi biên dựa vào sự biến thiên về giá trị độ sáng của điểm ảnh.Kỹ thuật chủ yếu dùng phát hiện biên ở đây là kỹ thuật đạo hàm.Nếu lấy đạo hàm bậc nhất của ảnh, ta có phương pháp Gradient.Nếu lấy đạo hàm bậc hai, ta có phương pháp Laplace.Hai kỹ thuật trên gọi là phương pháp dò biên cục bộ.Ngoài ra, người ta cũng sử dụng phương pháp “đi theo đường bao” : dựa vào nguyên lý quy hoạch động và được gọi là phương pháp dò biên tổng thể. - Phương pháp phát hiện biên gián tiếp: Bằng cách nào đó, ta phân được ảnh thành các vùng thì đường phân ranh giữa các vùng đó chính là biên.Việc phân vùng ảnh thường dựa vào kết cấu bề mặt ảnh. Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu của nhau.Thực vậy, dò biên để thực hiện phân lớp đối tượng và một khi đã phân lớp xong có nghĩa là đã phân vùng được ảnh.Và ngược lại, khi đã phân vùng, ảnh đã phân lập được thành các đối tượng, ta có thể phát hiện được biên.Phương pháp dò biên trực tiếp tỏ ra khá hiệu quả vì ít chịu ảnh hưởng của nhiễu.Nếu biến đổi gián tiếp tuy khó cài đặt, song lại áp dụng khá tốt khi sự biến thiên độ sáng nhỏ. 2.Quá trình phát hiện biên -Vì ảnh thu nhận thường có nhiễu nên bước đầu tiên là khử nhiễu. -Tiếp theo là tiến hành làm nổi biên bởi các toán tử đạo hàm. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M - Định vị điểm biên.Vì các kỹ thuật làm nổi biên có hiệu ứng phụ là tăng nhiễu, do vậy sẽ có một điểm biên giả cần bị loại bỏ. -Liên kết và trích chọn biên. Chương II.Các phương pháp dò biên 1.Sự phân đoạn và dò biên 1.1.Thao tác vùng Việc khám phá các vùng có thể là một việc rất đơn giản ,như được minh hoạ trong mục 1.1.1.tuy nhiên thường không nhiều hơn ,những vùng được yêu cầu mà bao trùm một vùng thật của ảnh hơn là mổh nhóm các diểm ảnh. 1.2.Dò biên thô Sử dụng: xem xét một hình ảnh như là một tập hợp các vùng . thuật toán:dò biên thô không phải là một phương pháp phức tạp .những vùng đơn giản được xác định như vùng các điểm cùng mức xám , đường biên của các vùng là tách những điểm ảnh hơn tại vị trí điểm. như việc dò một vùng có thể đưa ra một số các vùng hữu ích (trừ khi số các mức xám là tương đối nhỏ ).như vậy một phương pháp đơn giản là nhóm lại những điểm ảnh vào trong hững phạm vi của những giá trị gần (q hoặc tự nhóm).các vùng(miền) có thể là việc xem xét các biểu đồ hình ảnh để xác định tốt sự tự nhhóm cho mục đích vùng kết quả trong việc kết hợp toàn bộ mức xám vùng cơ sở nhiều hơn các mức xám của điểm ảnh mà nó gần với một vùng khác . 1.3. Kết hợp các vùng Việc kết hợp các vùng là rất hữu ích cho việc tách thô các mức xám và thực hiện một số kỹ thuật trên những vết rạn giữa những vùng_không làm tăng biên nhưng để THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN xác định khi toàn bộ các vùng cần phải nối (kết hợp_-như vậy làm giảm số các vùng từ việc tìm vùng thô ở trên . 2. Các phương pháp dò biên cơ bản Biên của một hình ảnh giữ nhiều thông tin trong hình ảnh đó .các biên cho biết các đối tượng ở đâu ,hình dạng và kích thước của đối tượng,và cái gì đó để kết cấu của đối tượng .biên là nơi cương độ của một hình ảnh di chuyển từ một giá trị thấp đến giá trị cao. Rất nhiều các ứng dụng cho phương pháp dò biên ,mà được sử dụng cho một số hiệu ứng đặc biệt .những nghệ sỹ kỹ thuật số sử dụng nó để làm rõ nét các đường nét của hình ảnh .kết quả của việc dò biên có thể đưa thêm vào hình ảnh để làm nổi bật các đường biên. Biên trong ảnh là những vùng có cường độ tương phản mạnh, một bước nhảy từ điểm ảnh tới điểm ảnh kế tiếp.Dò biên một ảnh giúp giảm đáng kể số lượng và lọc ra những thông tin không hữu ích, trong khi đó bảo quản được các thuộc tính cấu trúc của ảnh.Có rất nhiều cách thực hiện dò biên.Tuy nhiên các phương pháp chính khác nhau có thể được nhóm vào thành hai loại, Gradient và Laplacian.Phương pháp Gradient dò biên bằng cách tìm kiếm giá trị lớn nhất và giá trị nhỏ nhất trong đạo hàm bậc nhất của ảnh.Phương pháp Laplace tìm kiếm các vạch không trong đạo hàm bậc hai của ảnh để tìm biên.Biên có dạng một chiều và tính toán đạo hàm của ảnh có thể làm nổi vị trí đó.Chúng ta có thể sử dụng kí hiệu f(t) sau với biên chỉ ra bước nhảy của cường độ bên dưới: Nếu ta lấy gradient của kí hiệu này ở dạng một chiều, chỉ ra đạo hàm bậc một của biến t, ta nhận được: Rõ ràng đạo hàm bậc một cho xác định giá trị lớn nhất tại tâm của biên.Phương pháp xác định biên này là đặc trưng của nhóm lọc gradient nếu giá trị của gradient vượt quá vài ngưỡng.Như đã đề cập, biên sẽ có giá trị cường độ điểm ảnh cao hơn so với các vùng khác.Nên mỗi lần, một ngưỡng được đặt, ta có thể so sánh giá trị gradient với giá trị một ngưỡng và dò biên khi mà ngưỡng được mở rộng.Hơn nữa khi mà đạo hàm bậc nhất đạt giá trị lớn nhất, đạo hàm bậc hai bằng 0.Một cách khác để tìm ra vị trí của biên là xác định các giá trị 0 của đạo hàm bậc hai của hàm bên dưới: Phương pháp dò biên thường bước đầu tiên là việc phân vùng hình ảnh .phân vùng ảnh là một lĩnh vực của phân tích ảnh , được sử dụng đểvnhóm những điểm vào trong các vùng để xác định thành phần cấu tạo một ảnh . một ví dụ phổ biến của phân vùng ảnh là”magic wand”( đũa thần ma thuật )công cụ phần mền trong xử lý ảnh .công cụ này cho phép người dùng lựa chọn một diểm trong một hình ảnh .phần mền này vẽ một đường bao quanh những điểm có giá trị giống nhau.người dùng có thể lựa chọn một diểm trong vùng bầu trời và đuã thần ma thuật sẽ vẽ một đường bao kín vùng bầu trời trong ảnh .người dùng có thể sửa đổi màu của vùng trời mà không gây ra sự biến đổi màu cắc các dãy núi hoặc bất cứ phần nào có mặt trong hình ảnh . phương pháp dò biên cũng sử dụng đăng ký (registration) ảnh .việc đăng ký hình ảnh sắp thẳng hàng hai hình ảnh mà có thể thu đựoc tại các phần mền riêng biệt hoặt từ những phân tử nhảy khác nhau. roof edge line edge step edge ramp edge Hình1.1 Một số đường biên khác nhau. K IL O BO O K S. CO M Có rất nhiều các kiểu biên,về chiều và hình dạng (hình1.1).Một số biên là đường thẳng trong khi những biên khác được uốn cong bằng việc thay đổi giá trị radian.có rất nhiều phương pháp dò biên sử dụng tất cả ngững đường biên trên,từng cái có những điểm mạnh của riêng nó .một vài phương pháp dò biêncó thể sử dụng tốt trong một số ứng dụng và thực hiện kém (không hiệu quả)trong ứng dụng khác. Đôi khi nó được sử dụng thí nghiệm để xác định đâu là phương pháp dò biên tốt nhất cho một ứng dụng. Phương pháp dò biên đơn giản nhất và nhanh nhất là xác định giá trị cực đằit một loạt các phép thuần nhất (đồng nhất)trừ điểm ảnh.phép toán trừ mỗi 8 điểm ảnh phụ cận (vây quanh)từ một điểm trung tâm của một cửa sổ 3x3 trong hình 1.2 đầu ra của phép toán là giá trị tuyệt đối cực đại của mỗi phần khác nhau. homogenety operator image 11 11 11 11 1216 16 13 15 Phép toán đồng nhất ảnh Hình 1.2 sử dụng các thuật toán đồng nhất. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M điểm ảnh mới=max{|11-11|,|11-13|,|11-15|,|11-16|,|11-11|,|11-16|,|11-12|,|11-11|}=5 Tương tự thuật toán thuần nhất là thiết bị dò biên khác .các thao tác của nó nhanh hơn bởi vì nó chỉ phụ thuộc vào 4 phép trừ mỗi điểm ảnh khác với thuật toán thuần nhất cần 8 phép trừ.các phép trừ là phần trên trái -phần dưới phải,giữa trái -giữa phải ,dưới trái –trên phải ,và giá trị giữa trên-giá trị dưới ở giữa(hình1.3) homogenety operator image 11 11 11 11 1216 16 13 15 Thuật toán thuần nhất ảnh Hình 1.3 Sử dụng thuật toán khác. điểm ảnh mới=max{|11-11|,|13-12|,|15-16|,|11-16|}=5 2.1. Phép lấy đạo hàm bậc nhất cho phương pháp dò biên. Nếu chúng ta đang tìm kiếm mọi đường biên nằm ngang nào nó sẽ nhận được tính toán sự khác nhau giữa một giá trị điểm và giá trị điểm tiếp theo,hoặc lên trên hoặc xuống từ đầu(được gọi là sự tách khác nhau)ví dụ giả thiết đỉnh trái gốc. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M Hc=yk(x,y)=(x,y)-(x,y+1) trên thực tế nó tương đương với việc thu nhỏ hình với mẫu 2x1 1 -1 Tương tự Hr=Xk(x,y)=(x,y)-(x-1,y) Sử dụng kết quả -1 1 Hc và Hr là các giá trị xác định cột và dòng. Đôi khi nó rất tiện lợi để phát hoạ cả Xk và Yk việc kết hợp chúng tạo nên độ lớn gradien(ví dụ cường độ của biên).việc kết hợp chúng bằng việc gộp hoàn toàn chúng có thể cho giá trị trung bình hai biên loại bỏ ngoài lẫn nhau(một là xác thực,một là không xác thực),vì vậy nó là tốt nhất cho việc tính tổng các giá trị thực(không cần quan tâm đến dấu )hoặc tính tông các bình phương của nó và khi đó có thể lấy căn bậc hai bình phương của kết quả thu được . Nó cũng chia Xk bởi Yk và xác định một chiều gradien(góc của biên ở giữa các vùng):       = − y)ce(x,X_differen y)ce(x,Y_differen tanirectiongradient_d 1 Độ lớn có thể tính bằng tổng vectơ Hc và Hr: )y,x(H)y,x(H)y,x(H 2c2r += THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M Đôi khi cho việc tính toán đơn giản , độ lớn được tính là: )y,x(H)y,x(H)y,x(H cr += Việc định hướng biên có thể tìm bởi ( ) ( )y,xH y,xH tan r c1− =θ trong hình ảnh thực tế ,các hàng ít khi được định nghĩa tốt như vậy,thường thì sự thay đổi giữa các vùng là từ từvà sặc sỡ hơn. Hình ảnh sau đây là điển hình việc đọc biên.mẫu này đã càn để tính tỷung bình gradien thông qua một số các điểm ảnh ,hơn là việc tính toán với hai con số 3444332100 2342334010 3333433100 3233430200 2420001000 3302000000 Các toán tử đạo hàm được áp dụng khá nhiều. Ở đây ta chỉ xét một số toán tử tiêu biểu: Robert, Sobel,… 2.2. Phương pháp dò biên Sobel Toán tử sobel nhạy cảm với các biên chéo hơn so với các biên thẳng đứng và các biên nằm ngang.chuẩn sobel 3x3 thương đựoc sử dụng như: X THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 121 000 121 −−− Y 101 202 101 − − − ảnh gốc : 3444332100 2342334010 3333433100 3233420200 2420001000 3302000000 |A|+|B| 8842212122 42421014104 061216201086 414121410464 giới hạn tại 12 0000110 00000100 00111002 11110000 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN Dựa trên phân tích một chiều, lý thuyết này có thể được áp dụng vào trường hợp hai chiều, tính toán được chính xác xấp xỉ đạo hàm ảnh hai chiều.Toán tử Sobel thực hiện phép đo gradient không gian hai chiều trong một ảnh. Điển hình nó được sử dụng tìm ra giá trị tuyệt đối xấp xỉ độ rộng gradient tại mỗi điểm trong độ xám ảnh đầu vào.Phương pháp dò biên Sobel sử dụng cặp mặt nạ xoắn 3X3, ước lượng gradient theo cột x, hàng y.Một mặt nạ xoắn thường nhỏ hơn nhiều so với ảnh thực.Mặt nạ là slide trên ảnh, thao tác thực hiện các điểm ảnh trên cùng một lúc.Mặt nạ Sobel được chỉ ra ở hình dưới. Độ dài đường dốc được tính bởi công thức: Tính xấp xỉ: K IL O BO O K S. CO M |G| = |Gx| + |Gy| Mã của phương pháp dò biên Sobel : FILE: edgeSob.c - WORKS!! AUTH: Bill Green DESC: 2 3x3 Sobel masks for edge detection DATE: 07/23/02 REFS: edgeLap.c */ #include #include #include #include /*-------STRUCTURES---------*/ typedef struct {int rows; int cols; unsigned char* data;} sImage; /*-------PROTOTYPES---------*/ long getImageInfo(FILE*, long, int); void copyImageInfo(FILE* inputFile, FILE* outputFile); void copyColorTable(FILE* inputFile, FILE* outputFile, int nColors); int main(int argc, char* argv[]) { FILE *bmpInput, *bmpOutput; THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M sImage originalImage; sImage edgeImage; unsigned int X, Y; int I, J; long sumX, sumY; int nColors, SUM; unsigned long vectorSize; unsigned long fileSize; int GX[3][3]; int GY[3][3]; unsigned char *pChar, someChar; unsigned int row, col; someChar = '0'; pChar = &someChar; /* 3x3 GX Sobel mask. Ref: www.cee.hw.ac.uk/hipr/html/sobel.html */ GX[0][0] = -1; GX[0][1] = 0; GX[0][2] = 1; GX[1][0] = -2; GX[1][1] = 0; GX[1][2] = 2; GX[2][0] = -1; GX[2][1] = 0; GX[2][2] = 1; /* 3x3 GY Sobel mask. Ref: www.cee.hw.ac.uk/hipr/html/sobel.html */ GY[0][0] = 1; GY[0][1] = 2; GY[0][2] = 1; GY[1][0] = 0; GY[1][1] = 0; GY[1][2] = 0; GY[2][0] = -1; GY[2][1] = -2; GY[2][2] = -1; if(argc < 2) { printf("Usage: %s bmpInput.bmp\n", argv[0]); exit(0); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M }; printf("Reading filename %s\n", argv[1]); /*-------DECLARE INPUT & OUTPUT FILES-------*/ bmpInput = fopen(argv[1], "rb"); bmpOutput = fopen("edgeSob.bmp", "wb"); /*---SET POINTER TO BEGINNING OF FILE----*/ fseek(bmpInput, 0L, SEEK_END); /*-------GET INPUT BMP DATA--------*/ fileSize = getImageInfo(bmpInput, 2, 4); originalImage.cols = (int)getImageInfo(bmpInput, 18, 4); originalImage.rows = (int)getImageInfo(bmpInput, 22, 4); edgeImage.rows = originalImage.rows; edgeImage.cols = originalImage.cols; /*--------PRINT DATA TO SCREEN----------*/ printf("Width: %d\n", originalImage.cols); printf("Height: %d\n", originalImage.rows); printf("File size: %lu\n", fileSize); nColors = (int)getImageInfo(bmpInput, 46, 4); printf("nColors: %d\n", nColors); /*------ALLOCATE MEMORY FOR FILES--------*/ vectorSize = fileSize - (14+40+4*nColors); printf("vectorSize: %lu\n", vectorSize); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M edgeImage.data = farmalloc(vectorSize*sizeof(unsigned char)); if(edgeImage.data == NULL) { printf("Failed to malloc edgeImage.data\n"); exit(0); } printf("%lu bytes malloc'ed for edgeImage.data\n", vectorSize); originalImage.data = farmalloc(vectorSize*sizeof(unsigned char)); if(originalImage.data == NULL) { printf("Failed to malloc originalImage.data\n"); exit(0); } printf("%lu bytes malloc'ed for originalImage.datt\n", vectorSize); /*------COPY HEADER AND COLOR TABLE---------*/ copyImageInfo(bmpInput, bmpOutput); copyColorTable(bmpInput, bmpOutput, nColors); fseek(bmpInput, (14+40+4*nColors), SEEK_SET); fseek(bmpOutput, (14+40+4*nColors), SEEK_SET); /* Read input.bmp and store it's raster data into originalImage.data */ for(row=0; row<=originalImage.rows-1; row++) { for(col=0; col<=originalImage.cols-1; col++) { fread(pChar, sizeof(char), 1, bmpInput); *(originalImage.data + row*originalImage.cols + col) = *pChar; } } THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M /*--------------------------------------------------- SOBEL ALGORITHM STARTS HERE ---------------------------------------------------*/ for(Y=0; Y<=(originalImage.rows-1); Y++) { for(X=0; X<=(originalImage.cols-1); X++) { sumX = 0; sumY = 0; /* image boundaries */ if(Y==0 || Y==originalImage.rows-1) SUM = 0; else if(X==0 || X==originalImage.cols-1) SUM = 0; /* Convolution starts here */ else { /*-------X GRADIENT APPR XIMATION------*/ for(I=-1; I<=1; I++) { for(J=-1; J<=1; J++) { sumX = sumX + (int)( (*(originalImage.data + X + I + (Y + J)*originalImage.cols)) * GX[I+1][J+1]); } } if(sumX>255) sumX=255; if(sumX<0) sumX=0; /*-------Y GRADIENT APPROXIMATION-------*/ THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M for(I=-1; I<=1; I++) { for(J=-1; J<=1; J++) { sumY = sumY + (int)( (*(originalImage.data + X + I + (Y + J)*originalImage.cols)) * GY[I+1][J+1]); } } if(sumY>255) sumY=255; if(sumY<0) sumY=0; SUM = abs(sumX) + abs(sumY); /*---GRADIENT MAGNITUDE APPROXIMATION (Myler p.218)----*/ } *(edgeImage.data + X + Y*originalImage.cols) = 255 - (unsigned char)(SUM); /* make edges black and background white */ fwrite( (edgeImage.data + X + Y*originalImage.cols), sizeof(char), 1, bmpOutput); } } printf("See edgeSob.bmp for results\n"); fclose(bmpInput); fclose(bmpOutput); farfree(edgeImage.data); /* Finished with edgeImage.data */ farfree(originalImage.data); /* Finished with originalImage.data */ return 0; } THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M /*----------GET IMAGE INFO SUBPROGRAM--------------*/ long getImageInfo(FILE* inputFile, long offset, int numberOfChars) { unsigned char *ptrC; long value = 0L; unsigned char dummy; int i; dummy = '0'; ptrC = &dummy; fseek(inputFile, offset, SEEK_SET); for(i=1; i<=numberOfChars; i++) { fread(ptrC, sizeof(char), 1, inputFile); /* calculate value based on adding bytes */ value = (long)(value + (*ptrC)*(pow(256, (i-1)))); } return(value); } /* end of getImageInfo */ /*-------------COPIES HEADER AND INFO HEADER----------------*/ void copyImageInfo(FILE* inputFile, FILE* outputFile) { unsigned char *ptrC; unsigned char dummy; THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M int i; dummy = '0'; ptrC = &dummy; fseek(inputFile, 0L, SEEK_SET); fseek(outputFile, 0L, SEEK_SET); for(i=0; i<=50; i++) { fread(ptrC, sizeof(char), 1, inputFile); fwrite(ptrC, sizeof(char), 1, outputFile); } } /*----------------COPIES COLOR TABLE-----------------------------*/ void copyColorTable(FILE* inputFile, FILE* outputFile, int nColors) { unsigned char *ptrC; unsigned char dummy; int i; dummy = '0'; ptrC = &dummy; fseek(inputFile, 54L, SEEK_SET); fseek(outputFile, 54L, SEEK_SET); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M for(i=0; i<=(4*nColors); i++) /* there are (4*nColors) bytesin color table */ { fread(ptrC, sizeof(char), 1, inputFile); fwrite(ptrC, sizeof(char), 1, outputFile); } } Giải thích Sobel: Mặt nạ Sobel được phủ trên một vùng của ảnh vào, thay đổi giá trị của điểm ảnh và sau đó chuyển đổi ảnh sang phải và tiếp tục sang phải cho đến khi nó tìm ra vị trí cuối cùng của hàng.Sau đó nó lại bắt đầu tại vị trí đầu của hàng kế tiếp.Ví dụ dưới đây chỉ ra mặt nạ được phủ trên vùng trái phía đầu của ảnh và hiển thị bởi đường màu xanh.Phương thức đó chỉ ra một điểm ảnh sẽ được tính toán.Tâm của mặt nạ được xác định trên một điểm ảnh ta đang thao tác trên ảnh.Giá trị I và J được sử dụng để chuyển file con trỏ. Ví dụ: ảnh 22 tương ứng giá trị mặt nạ m22. Chú ý rằng các điểm ảnh ở hàng đầu tiên và cuối cùng cũng như cột cuối cùng không thể được thực hiện bởi mặt nạ 3X3.Bởi vì khi xác định điểm giữa của mặt nạ trên một điểm ảnh ví dụ ở hàng đầu tiên, mặt nạ sẽ ở bên ngoài viền ảnh. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN Mặt nạ GX làm nổi biên theo hướng nằm ngang .Trong khi mặt nạ GY làm nổi biên theo hướng thẳng đứng.Sau khi xác định độ lớn của cả 2, kết quả dò biên theo cả 2 hướng được đưa ra. 2.3 Phép toán được quan tâm khác : Toán tử Roberts có hiểu quả nhỏ hơn so với các thuật toán khác ,nó dễ tạo ra các tạp nhiễu.          − =           − = 000 010 001 H 000 010 100 H cr Thuật toán Prewit nhạy cảm đối với các biên thẳng đứng và ngang hơn so với các biên đường chéo.           − − − =           −−− = 101 101 101 H 111 000 111 H cr K IL O BO O K S. CO M mặy nạ Frei-chen.           −−− =           − − = 121 000 121 H 100 202 100 H cr 3. Dò bậc hai Trong nhiều ứng dụng ,chiều rông biên không được quan tâm đến .trong những ứng dụng khác ,như các thiết bị dò tìm ,nó khá được chú trọng đến .thuật toán gradien đã nói ở trên đã giải đáp giữa hai vẫn đề trên tại vùng mà biên đang xét .nó là tốt nhất cho việc xây dựng dần các đường biên gốc . đúng như ý tưởng ,việc tìm một đường biên cần phải chỉ ra mọi đường biên tại trung tâm của một biên . được đề cập ở đây là sự định vị .nếu việc xác định một biên tạo ra một bản đồ hình ảnh với các biên khác nhau mở rộng các điểm ảnh ,nó là khó khăn để định vị các trung tâm của các biên .nó trở thành cần thiết để mượn một tiến trình nghèo nàn để làm bớt bề rộng của biên tới một điểm ảnh .phần này cung cấp tốt hơn sự định vị biên . Ví dụ: Một hình ảnh như sau: 987654321 987654321 987654321 987654321 987654321 Toán tử cơ bản Sobel dò biên thẳng đứng như miêu tả ở trên sẽ nhượng bộ một giá trị đúng kéo dài từ bên này sang bên kia hình ảnh.Ví dụ nếu: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 101 202 101 − − − được sử dụng thì kết quả là: 8888888 8888888 8888888 Thực hiện giống như chuẩn trên đây “tất cả 8 hình ảnh đã nhượng bộ “. 00000000 Nó không khác như các thuật toán khác với một đường thẳng ,ví dụ nếu y=3x-2 2 2 dx yd and3 dx dy = Một lần chúng ta có đường dốc ,nếu đường dốc đã được phân biệt và kết quả là không ,nó chỉ ra rằng đường gốc là đường thẳng . Các hình ảnh thường là màu xám mức”khuynh hướng”với chúng ,…một mặt các vùng là sáng hơn các vùng khác ,nhưng ở đó không có biên nào sẽ được tim ta trong vùng ,hiệu ứng đánh bóng là trơn tru,nói ngắn gọn một nguồn sáng mà nó là rõ ràng hơn ở thời điểm kết thúc ,hoặc thay đổi màu dần dần qua bề mặt. điểm thuận lợi khác của phương pháp lấy đạo hàm bậc hai là dò các viền biên là những đường cong khép kín . điều này rất quan trọng trong việc phân đoạn hình ảnh .ngoài ra,nó không phản ứng lại các vùng của sự thay đổi tuyến tính smoot trong cường độ . THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M kỹ thuật Laplace là một thí dụ trong kỹ thuật lấy đạo hàm bậc hai .nó tương đối như những toán tử khác bởi vì nó tác dụng theo mọi hướng .nó sẽ tô sáng điểm biên trong tất cả các hướng .toán tử laplace sẽ đưa ra các biên không chuẩn xác hơn ( sharper)so với đa số các kỹ thuật khác .các vùng sáng bao gồm giá trị dương và âm của cường độ dốc(slope). Biên laplace của một ảnh có thể tìm được bởi kết hợp với các mặt nạ như : 010 141 010 − −− − or 111 181 111 −−− −− −−− Tập hợp các toán tử laplace được sử dụng rông rãi .nó có hiệu quả loại bỏ gradient tổng quát của ánh sáng hoặc màu từ một hình ảnh nó chỉ tìm ra và tăng sự thay đổi rời rạc (chậm)hơn,cho thí dụ ,với toán tử sobel.nó không đưa ra mọi thông tin trên hướng mà nó xem xét như một chức năng của sự dân dân thay đổi .nó làm tăng tạp nhiễu ,mặc dù các toán tử laplace lớn hơn và những họ tương đồng của các toán tử có khuynh hướng lờ đi tạp nhiễu . 3.1. Xác định cắt điểm không Đối với biên đang xét phương thức của việc cắt điểm không với một vài yêu cầu giới hạn là thông qua một mặt nạ 3x3 qua hình ảnh mà đang xác định giá trị max và min.nếu sự khác nhau giữa các giá trị max và min vượt quá giới hạn định đã cho trước .thông báo số lớn các biên với giới hạn nhỏ hơn.chú ý chiều rộng của tất cả các biên là một điểm ảnh mở rộng . một kỹ thuật dò biên lấy đạo hàm bậc hai là ít nhạy cảm với nhiễu là laplace của gauss(log).dò biên LoG do gauss thực hiện làm nhẵn trước ứng dụng của Laplace.cả hai toán tử có thể thực hiện bằng việc hợp với một mặt nạ của biểu mẫu: 2 22 2 )y(x 2 22 4 e2 yx11y)LoG(x, σ +−       σ + − piσ = THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN ở đây x,y đang xét là các dòng và cột của một hình ảnh ,0 là một giá trị của sự tán sắc mà các điều khiển có kết quả spread. Do hình dạng của nó ,hàm này được gọi là lọc .hình biểu diễn đoạn của toán tử dò biên LoG với các giá trị khác nhau của o .hàm được mở rộng hơn ,biên mở rộng mà nó sẽ tìm được.thu hẹp một hàm sẽ tìm được hình dạng và các chi tiết các biên hơn. Hình 1.4 Giao của LoG với giá trị Giá trị lớn hơn của 0, mở rộng sự xoắn lại mặt nạ cần thiết .cắt điểm không đầu tiên của hàm LoG tại σ2 .The width of the positive center lobe is twice that. để có một cuộn mặt nạ mà chứa đựng nhứng giá trị khác không của hàmLoG yêu cầu chiều rộng bằng ba lần chiều rộng của vành dương trung tâm. Phương pháp dò biên dựa trên hàm nhẵn gauss nhằm giảm bớt tạo nhiễu trong hình ảnh .nó sẽ làm giảm bớt đi các biên đã tìm không đúng và cũng tìm được các biên mơ rộng . Đa số các mặt nạ dò biên ít khi lớn hơn 7x7 .vì hình dạng của thuật toán LoG ,nó yêu cầu nhiều mặt nạ kích thước lớn hơn .ban đầu phản đối (work in)sự phát triển thuật toán log dã làm việc với một mặt nạ kích thước 35x35. bởi vì những yêu cầu tính toán lớn của thuật toán log ,thuật toán khác của gauss (dog)có thể sử dụng như một phép tính xấp xỉ cho log.dog có thể được cho: 2 2 2 yx 2 1 2 yx 2 e 2 ey)DoG(x, 2 2 22 2 1 22 piσ − piσ =         piσ + −         piσ + − Thuật toán dog đựoc thưc hiện bởi phép quẫn lại một hình ảnh với một mặt nạ bằng kết quả của phép trừ hai mặt nạ gauss với các giá trị khác nhau.kết qua tỷ số  1/ 2 = 1.6 thu được trong phép tính xấp xỉ của LoG.Hình 4.5 so sánh hàm LoG ( = 12.35) với hàm DoG (1 = 10, 2 = 16). Hình 1.5 Hàm LoG và hàm DoG. Một thuận lợi của DoG là khả năng định rõ bề rộng của các biên để dò tìm bằng các giá trị khác nhau của và . ở đây xé một hai cặp mặt nạ .mạt nạ 9x9 sẽ tìm được các biên rộng hơn mặt nạ 7x7. Mặt nạ7x7, K IL O BO O K S. CO M0011100 0233320 1355531 13516531 1355531 0233320 0011100 −−− −−−−− −−−− −−−− −−−− −−−−− −−− Mặt nạ 9x9, 000111000 022333320 033111230 131999131 1319199131 131999131 033111230 022333320 000111000 −−− −−−−−−− −−−−−−− −−−−−− −−−−−− −−−−−− −−−−−−− −−−−−−− −−− 3.2. Dò biên màu Phương thức của sự dò tìm các biên trong ảnh màu phụ thuộc vào việc định nghĩa biên của bạn . định nghĩa một biên là gián đoạn (tính không liên tục ) độ chói trong một hình ảnh . đò biên sẽ được thực hiện trê kênh cường độ của một màu trong không gian HIS. định nghĩa khác đòi hỏi rằng một biên tồn tại nếu có mặt kênh màu đỏ ,xanh lục và xanh.dò biên có thể được làm bằng việc thực hiện trên mỗi màu thành phần của nó ,sau đó phối hợp các màu thành phần ,hình ảnh thu được màu vẫn giữ nguyên (still color).xem hình 1.6. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN Hình 1.6(a)hình ảnh gốc ;(b)kênh màu đỏ ;(c)kênh màu xanh lục;(d) kênh màu xanh;(e)biên kênh màu đỏ;(e)Biên kênh màu xanh lục ;(e)biên kênh màu xanh. Dò biên cũng có thể thực hiện trên mỗi phần màu và các thành phần có thể được tổng hợp lại đẻ tạo ra một bản đồ biên dải màu xám .ngoài ra ,các thành phần màu có thể là tổng các vec to để tạo ra bản đồ biên dải màu xám. 2 blue 2 green 2 red GGGy)G(x, ++= Nó đã được chỉ ra rằng phần lớn các biên dựa trên các phân tử màu của một hình ảnh ngoài ra cũng dựa trên thành phần cường độ . 4. Phương pháp dò biên Phương pháp dò biên Laplace. Ma trận Laplace 5 X 5 được sử dụng trong một mặt nạ xoắn để xấp xỉ đạo hàm bậc hai.Không giống phương pháp Sobel xấp xỉ đường dốc, thay thế cho hai mặt nạ Sobel 3 X 3 theo hướng x và y.Laplace sử dụng một mặt nạ 5 X 5 cho đạo hàm bậc hai trong cả hướng x và y.Tuy nhiên bởi vì những mặt nạ này xấp xỉ phép đo đạo hàm bậc hai trên ảnh.Chúng rất dễ bị hỏng, gây nhiễu. Đây được xem như so sánh với phương pháp Sobel.Mặt nạ Laplace và mã dưới đây: /* FILE: edgeLap.c - WORKS! AUTH: P.Oh DESC: 5x5 Laplace mask for edge detection DATE: 05/02/02 23:30 REFS: edgedeta.c K IL O BO O K S. CO M */ #include #include #include #include /*-------STRUCTURES---------*/ typedef struct {int rows; int cols; unsigned char* data;} sImage; /*-------PROTOTYPES---------*/ long getImageInfo(FILE*, long, int); void copyImageInfo(FILE* inputFile, FILE* outputFile); void copyColorTable(FILE* inputFile, FILE* outputFile, int nColors); int main(int argc, char* argv[]) { FILE *bmpInput, *bmpOutput; sImage originalImage; sImage edgeImage; unsigned int X, Y; int I, J; long SUM; int nColors; unsigned long vectorSize; unsigned long fileSize; int MASK[5][5]; unsigned char *pChar, someChar; THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M unsigned int row, col; someChar = '0'; pChar = &someChar; /* 5x5 Laplace mask. Ref: Mysler Handbook p. 135 */ MASK[0][0] = -1; MASK[0][1] = -1; MASK[0][2] = -1; ASK[0][3] = -1; MASK[0][4] = -1; MASK[1][0] = -1; MASK[1][1] = -1; MASK[1][2] = -1; MASK[1][3] = -1; MASK[1][4] = -1; MASK[2][0] = -1; MASK[2][1] = -1; MASK[2][2] = 24; MASK[2][3] = -1; MASK[2][4] = -1; MASK[3][0] = -1; MASK[3][1] = -1; MASK[3][2] = -1; MASK[3][3] = -1; MASK[3][4] = -1; MASK[4][0] = -1; MASK[4][1] = -1; MASK[4][2] = -1; MASK[4][3] = -1; MASK[4][4] = -1; if(argc < 2) { printf("Usage: %s bmpInput.bmp\n", argv[0]); exit(0); }; printf("Reading filename %s\n", argv[1]); /* open files for reading and writing to */ bmpInput = fopen(argv[1], "rb"); bmpOutput = fopen("edgeLap.bmp", "wb"); /* start pointer at beginning of file */ fseek(bmpInput, 0L, SEEK_END); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M /* retrieve and print filesize and number of cols and rows */ fileSize = getImageInfo(bmpInput, 2, 4); originalImage.cols = (int)getImageInfo(bmpInput, 18, 4); originalImage.rows = (int)getImageInfo(bmpInput, 22, 4); edgeImage.rows = originalImage.rows; edgeImage.cols = originalImage.cols; printf("Width: %d\n", originalImage.cols); printf("Height: %d\n", originalImage.rows); printf("File size: %lu\n", fileSize); /* retrieve and print Number of colors */ nColors = (int)getImageInfo(bmpInput, 46, 4); printf("nColors: %d\n", nColors); vectorSize = fileSize - (14+40+4*nColors); printf("vectorSize: %lu\n", vectorSize); edgeImage.data = farmalloc(vectorSize*sizeof(unsigned char)); if(edgeImage.data == NULL) { printf("Failed to malloc edgeImage.data\n"); exit(0); } printf("%lu bytes malloc'ed for edgeImage.data\n", vectorSize); originalImage.data = farmalloc(vectorSize*sizeof(unsigned char)); if(originalImage.data == NULL) { printf("Failed to malloc originalImage.data\n"); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M exit(0); } printf("%lu bytes malloc'ed for originalImage.datt\n", vectorSize); copyImageInfo(bmpInput, bmpOutput); copyColorTable(bmpInput, bmpOutput, nColors); fseek(bmpInput, (14+40+4*nColors), SEEK_SET); fseek(bmpOutput, (14+40+4*nColors), SEEK_SET); /* Read input.bmp and store it's raster data into originalImage.data */ for(row=0; row<=originalImage.rows-1; row++) { for(col=0; col<=originalImage.cols-1; col++) { fread(pChar, sizeof(char), 1, bmpInput); *(originalImage.data + row*originalImage.cols + col) = *pChar; } } for(Y=0; Y<=(originalImage.rows-1); Y++) { for(X=0; X<=(originalImage.cols-1); X++) { SUM = 0; /* image boundaries */ if(Y==0 || Y==1 || Y==originalImage.rows-2 || Y==originalImage.rows-1) SUM = 0; else if(X==0 || X==1 || X==originalImage.cols-2 || X==originalImage.cols- 1) SUM = 0; THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M /* Convolution starts here */ else { for(I=-2; I<=2; I++) { for(J=-2; J<=2; J++) { SUM = SUM + (int)( (*(originalImage.data + X + I + (Y + J)*originalImage.cols)) * MASK[I+2][J+2]); } } } if(SUM>255) SUM=255; if(SUM<0) SUM=0; *(edgeImage.data + X + Y*originalImage.cols) = 255 - (unsigned char)(SUM); /* make edges black and background white */ fwrite( (edgeImage.data + X + Y*originalImage.cols), sizeof(char), 1, bmpOutput); } } printf("See edgeLap.bmp for results\n"); fclose(bmpInput); fclose(bmpOutput); farfree(edgeImage.data); /* Finished with edgeImage.data */ farfree(originalImage.data); /* Finished with originalImage.data */ return 0; } THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M /*----------GET IMAGE INFO SUBPROGRAM--------------*/ long getImageInfo(FILE* inputFile, long offset, int numberOfChars) { unsigned char *ptrC; long value = 0L; unsigned char dummy; int i; dummy = '0'; ptrC = &dummy; fseek(inputFile, offset, SEEK_SET); for(i=1; i<=numberOfChars; i++) { fread(ptrC, sizeof(char), 1, inputFile); /* calculate value based on adding bytes */ value = (long)(value + (*ptrC)*(pow(256, (i-1)))); } return(value); } /* end of getImageInfo */ /*-------------COPIES HEADER AND INFO HEADER----------------*/ void copyImageInfo(FILE* inputFile, FILE* outputFile) { unsigned char *ptrC; unsigned char dummy; THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M int i; dummy = '0'; ptrC = &dummy; fseek(inputFile, 0L, SEEK_SET); fseek(outputFile, 0L, SEEK_SET); for(i=0; i<=50; i++) { fread(ptrC, sizeof(char), 1, inputFile); fwrite(ptrC, sizeof(char), 1, outputFile); } } /*----------------COPIES COLOR TABLE-----------------------------*/ void copyColorTable(FILE* inputFile, FILE* outputFile, int nColors) { unsigned char *ptrC; unsigned char dummy; int i; dummy = '0'; ptrC = &dummy; fseek(inputFile, 54L, SEEK_SET); fseek(outputFile, 54L, SEEK_SET); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M for(i=0; i<=(4*nColors); i++) /* there are (4*nColors) bytesin color table */ { fread(ptrC, sizeof(char), 1, inputFile); fwrite(ptrC, sizeof(char), 1, outputFile); } } Giải thích Laplace: Toán tử Laplace thực hiện chính xác như Sobel, phương pháp này có một chút đơn giản bởi nó sử dụng một mặt nạ thay vì hai. 5. Phương pháp dò biên hình chóp(pyramid EDGE detection) Nó thường xảy ra với các biên quan trọng trong hình ảnh đã được tách rời thành các khoảng từ hình ảnh đó và tương đối dàng để xác định.Tuy nhiên, đó có thể là một số các biên đậm trong hình ảnh đó và tương đối dễ dàng để xác định( từ hình ảnh người sử dung j đang xét) bởi vì chúng ngắn hoặc rời rạc. Vấn đề là làm thế nào để lảm nổi bật biên lớn (substantial) nhưng lờ đi biên không đạt(ngắn). Sử dụng: làm tăng các biên lớn (đậm và dài) nhưng bỏ qua các biên mờ hoặc ngắn. Nguyên lý: hình ảnh được cắt bớt thành bốn phần bằng việc cjia đôi chiều dài của cạnh( cả chiều ngang và chiều dọc). Mỗi điểm trong một hình ảnh thu được bằng trung bình của bốn điểm ảnh tương ứng trong hình ảnh đầy đủ.Lặp lại quá trình này cho đến khi hình ảnh được tạo ra ở đây các biên lớn vãn còn rõ ràng nhưng các biên khác đã được loại bỏ. Hình chóp ở đây là đường ngang trong hướng khác. Việc dò biên đã áp dụng với hình ảnh nhỏ và điểm ảnh biên đã tìm được ở đó, việc dò biên áp dụng bốn điểm THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M ảnh tương ứng trong hình ảnh lớp tiếp theo- và dựa trên hình ảnh có kích thước lớn đầy đủ. Thuật toán: Đặt kích thước của hình ảnh gốc m x n. Tạo một hình ảnh tiếp theo có kích thước m/2 x n/2 bằng việc ước lượng giá trị cho mỗi 0<i<m và <j<n. [ ]1)j1,I(i1)jI(i,j)1,I(ij)I(i, 4 1 2 j , 2 i newI +++++++=      Bình phương tương ứng của bốn phần tử trong hình ảnh gốc đươc tính trung bình để đưa giá trị và hình ảnh mới. Lặp lại quá trình được lặp lại( có thể dùng để quy) x lần, và mỗi giữ lại hình ảnh thu được. Lúc này với hình ảnh nhỏ nhất, thực hiện một số thuật toán dò biên- như sobel. Trong các điểm ảnh ở đây các biên đã đượ tìm ra khi thực hiện thuật toán dò biên trên nhóm của bốn điểm ảnh tương ứng trong hình ảnh lốn nhất tiếp theo.Ta tiếp tục thực hiện giảm bớt các biên tốt nhất đến cuối hình chóp của hình ảnh cho đến khi các biên chính trong hình ảnh gốc đã tìm được. 6. Crack edge relation(Tách giới hạn biên) Giới hạn biên hình ảnh: Hầu hết các giá trị điểm ảnh là hiện hữu ở biên hình ảnh, những giá trị biên nhỏ phù hợp cho mức xám không đáng kể, làm thay đổi kết quả từ lượng tạp nhiễu, ánh sáng nhỏ không đều… Chọn một giới hạn chung thích hợp thường là khó khăn và đôi khi không thể đạt được; P-giới hạn xếp kề có thể áp dụng t ừ định nghĩa giới hạn. Như một sự lựa chọn, không giảm độ lớn cực đại và hiện tượng trễ giới hạn có thể được sử dụng như là đã đưa vào phép dò biên chi tiết. Phục hồi biên: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M Khung cuối cùng từ các phương pháp trước chịu ảnh hưởng lớn bởi hình ảnh gốc. Tất cả thuộc tính hình ảnh trong bối cảnh liên quan với nhau có thể tăng chất lượng hình ảnh cuối cùng. Hầu hết các thuộc tính hình ảnh, tính đến cả biên thực sự mờ là đánh giá chính xác hơn trừ khi ngữ cảnh biên là hoàn toàn làm sạch – cơ bản trên độ dài của các biên liên quan trong tìm kiếm đặc biệt, sự tin cậy của mỗi biên là tăng hay giảm. Một vị trí biên mờ giữa 2 biên rõ là một ví dụ cụ thể; nó là khả năng lớn dể vị trí biên mờ là một phần của đường biên cuối cùng. Nếu trong 1 trường hợp khác, một biên rõ vị trí của nó không tồn tại nó sẽ không là phần nhỏ của bất kì đường biên nào. Giãn đường biên là phương pháp lập đi lập lại để độ tin cậy của đường biên hội tụ về 0 hay 1. Sự tin cậy của mỗi đường biên e trong lần giãn đầu tiên là độ lớn bình thường của đường biên rõ. Thuật toán: 1. Đánh giá độ tin cậy C(1)(e) cho tất cả các đường biên e tách ra trong hình ảnh. 2. Tìm kiểu đường biên của mỗi đường biên cơ bản trên đường biên tin cậy trong nhóm liên quan. 3. cập nhật độ tin cậy C(k+1)(e) của mỗi đường biên e theo kiểu của nó và theo độ tin cậy cho trước C(k)(e). 4. Dừng lại, nếu độ tin cậy đã hội tụ về 0 hay 1. Lặp lại bước (2) và (3) cho các trường hợp khác. - Các bước chính của thuật toán ở trên là ước lượng nhưng điểm tốt nhất bởi ước lượng của kiểu đường biên và theo cách này độ tin cậy của đường biên đã giảm bớt. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M - Ước lượng là tính toán ở kiểu i nếu: Type(i)=max(type(k)) k=0,1,2,3 Type(0)=(m-a)(m-b)(m-c) Type(1)=a(m-b)(m-c) Type(2)=ab(m-c) Type(i)=abc a, b, c là giá trị thường thấy gắn liền với đường biên mẫu m= max(a,b,c,q) đưa vào lượng q đảm bảo type(0) khác 0 và mang giá trị a. - Một ví dụ khi chọn q=0,1 một ước lượng (a,b,c)=(0.5,0.05,0.005) là ước lượng kiểu 1 khi đó kiểu ước lượng (0.3,0.2,0.2) là ước lượng kiểu 3. - Đánh giá kết quả đạt được bằng cách đếm đơn giản những con cố của đường biên gốc từ ước lượng ở trên một giá trị giới hạn. - Kiểu biên được tìm thấy khi móc nối đơn giản các kiểu biên và độ tin cậy của đường biên là giảm đi trong lân cận tiếp theo. - Tăng độ tin cậy C(k+1)(e) = min (1, C(k)(e)+δ) - Giảm độ tin cậy C(k+1)(e) = min (1, C(k)(e)-δ) - Sự giãn đường biên mô tả ở trên nhanh chóng được dùng tạo đường biên ban đầu trong lần lặp đầu tiên. - Nó thường hội tục chậm và cho kết quả xấu hơn mong muốn khi lặp những số lớn. - Nguyên nhân của nó được tìm từ toàn bộ số lớn nhất của đường biên kiểm định nằm ngoài tiêu chuẩn của hình ảnh, điều không phải tìm kiếm cho kết quả tốt nhất. - Vấn đề là tìm đường biên tin cậy từ một giới hạn chắc chắn và nội giới hạn khác, giới hạn làm tăng lên độ bóng bẩy của hình ảnh gốc. - Một bước đã được thêm vào để tìm đường biên tin cậy: Nếu C(k+1)(e)>T1 thì assign(C(k+1)(e))=1 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M Nếu C(k+1)(e)<T2 thì assign(C(k+1)(e))=0 T1,T2 là các tham số điều khiển sự hội tụ dần của phép giãn biên và độ chính xác của đường biên cuối cùng. 7. Kỹ thuật đạo hàm tích chập – phương pháp Canny Phương pháp này thực hiện cách lấy đạo hàm của một ảnh chập với bộ lọc Gauss. Đạo hàm của một ảnh được lọc: yx ffIGf +=⊗∇=∇ )( (3.11) với fx, fy là đạo hàm theo x và y của f Do vậy: )()()()( IGIGIGIGf yxyx ⊗+⊗=⊗∇+⊗∇=∇ (3.12) Lấy đạo hàm riêng theo x và y của G ta được: ) 2 exp( 2 2 22 ),( σσ yxx x yxG + − − = ) 2 exp( 2 2 22 ),( σσ yxy y yxG + − − = Gx(x) G(y) fx fy Gy(y) G(x) Hình 5: Mô hình tính của phương pháp Canny 8. Dò biên theo quy hoach động 8.1. Mô tả phương pháp I(x,y) Arctan fy/fx 22 yx ff + THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M Dò biên theo phương pháp gradient là xác định cực trị cục bộ của gradient theo các hướng; còn phương pháp Laplace dựa vào cắt điểm không của đạo hàm bậc hai. Phương pháp dò biên theo quy hoạch động là phương pháp tìm cực trị tổng thể của các quá trình nhiều bước. Nó dựa vào nguyên lý tối ưu của Bellman. Nguyên lý Bellman phát biểu như sau: “con đường tối ưu giữa 2 điểm cho trước cũng là tối ưu giữa 2 điểm bất kỳ nằm trên đường tối ưu đó”. Thí dụ, nếu C là một điểm trên đường tối ưu giữa A và B thì đoạn CB cũng là con đường tối ưu từ C đến B không kể đến C bằng cách nào. E B C A D Trong kỹ thuật này, ta giả sử bản đồ biên đã được xác định và được biểu diễn dưới dạng một đồ thị liên thông N chặng. Hơn nữa, giả sử hàm đánh giá được tính theo công thức: ∑∑∑ = − = − = −−−= N k NN N k kk N k kN xxdxxxgNxxS 2 1 1 1 1 1 ),()()()(),,...,( βθθα Với: Xk, k=1,…,N: biểu diễn các đỉnh của đồ thị trong chặng thứ k; d(x,y): khoảng cách giữa 2 đỉnh x và y tính theo các định nghĩa tương ứng về khoảng cách; THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M |g(xk)| và θ(xk) là gradient biên độ và gradient hướng ở đỉnh xk; α và β là các tham số không âm. Đường bao tối ưu sẽ nhân được bằng cách nối các đỉnh x , k=1,…,N nào đó thỏa mãn, sao cho S(x1,…,xN) đạt cực đại. Ta định nghĩa hàm như sau: 11 ,.. 1 )},,..,({),( − =Φ Nxx NN NxxSMaxNx Khi đó ta được: ),()()()()1,,..,(),,..,( 11111 −−− −−++−= NNkkNNN xxdxxxgNxxSNxxS βθθα Với cách thức này, thay vì tìm tối ưu toàn cục của S(x1,,…,xN,N) một vấn đề phức tạp, ta đi tìm tối ưu của N chặng của tối ưu 2 biến. Trong mỗi chặng, với mỗi xk ta phải tìm tối ưu Φ(xk,k). Ví dụ: Giả sử ta có bản đồ biên biểu diễn đồ thị liên thông sau: D 4 7 Φ(xk 6 5 D(11,12) E(16) F(23) A 5 B A 5 C B 3 2 6 I(8) (18,28) 2 3 G(8) H(8,10) j(13,10) 1 2 3 4 5 k Theo phương pháp trên ta có Φ(xk,k)=5. với k=2 có Φ(D,2)=max(11,12)=12. Điều đó có nghĩa là con đường từ A đến D di qua C và ACD là biên được chọn với k=2. Một cách tương tự, với k=4 có 2 con đường được chọn là ACDEF và AGHJ. Tuy nhiên, với k=5 thì đoạn JB bị loại và chỉ tồn tại con đường duy nhất với cực đại là 28. Như vậy biên được xác định là ADEFB. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 8.2. Thuật toán Theo phân tích trên, thuật toán dò biên theo qui hoạch động được mô tả một cách hình thức như sau: • Xuất phát từ điểm ban đầu XA, ta xác định con đường gồm các đỉnh để đạt đến đỉnh XB • Việc dò tìm này giống như phép duyệt đồ thị theo bề sâu: tại thời điểm hiện thời xi (lúc xuất phát là XA), ta xác định các điểm kế tiếp, dựa vào 8 lân cận theo hướng của điểm hiện tại và điểm trước đó. Nếu hướng đó hợp lệ, ta chọn nó như một đỉnh trên con đường cần tìm. Ngược lại, để tìm đỉnh có khả năng ta sẽ chọn 1 trong 8 lân cận của đỉnh đang xét với chi phi lớn nhất. Có thể có nhiều đỉnh thỏa mãn và như vậy ta cần lưu trữ các đỉnh này coi như các đỉnh có khả năng. Nếu không có đỉnh nào được chọn trong 8 lân cận đó, ta phải quay lui và chọn đỉnh khác đã lưu trữ. • Quá trình được lặp lại cho đến đỉnh được xem xét hiện tại chính là đích X8 Để cài đặt giải thuật này, cần sử dụng các cấu trúc dữ liệu và các thủ tục sau:
Stack winerstack: lưu trữ các đỉnh trên con đường tối ưu từ đỉnh xuất phát X đến đỉnh đích X8.
Stack tempstack: lưu trữ các đỉnh có khả năng để xem xét lúc quay lui một khi thất bại tạm thời.
Véc tơ Index: gồm 9 phần tử. Mỗi phần tử của véc tơ gồm 3 trường: hàng, cột và giá. Giá là tiêu chí xét điểm thỏa mãn;
Image: ảnh vào
XA, XB, last: có cấu trúc như một phần tử của véc tơ Index
Find_Direc (last, current): hàm cung cấp giá trị về hướng của điểm đang xét và điểm trước nó. - Thủ tục Find_Successor(ImageIn,X,last, Index): tìm các điểm tiếp theo có thể và đặt vào véc tơ Index. Điểm tiếp theo này phải nằm THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M trong giới hạn của ảnh, khác với điểm hiện thời và điểm trước đó và cường độ mức xám phải lớn hơn ngưỡng T. Khi điểm ảnh được chọn, trường giá sẽ tăng lên một lượng: bằng mắc xám của điểm ảnh đó. - Thủ tục Init_index(Index): đặt lại giá trị cho mỗi phần tử của véc tơ Index bằng -1 mỗi khi khởi tạo một đợt tìm mới. - Thủ tục sort_pixel(Index): sắp xếp lại véc tơ index theo trường giá tăng dần để tìm các đỉnh có khả năng làm cực đạiΦ Giải thuật dò biên theo qui hoạch động được viết như sau: Edge_Dynamic(XA,XB,ImageIn,T,Index,Last,WinerStack) /*XA, XB, T, ImageIn: các tham số vào WinerStack” tham số ra. Chứa các đỉnh biên trên đường từ XA đến XB*/ 1. if XA=XB then kết thúc; 2. khởi tạo ban đầu Last=XA; Push(WinerStack,XA); ImageIn[XA]=0;{đánh dấu để không xét lại} Init_Index(Index); Find_Successor(ImageIn, Xi,T,Index, last); Sort_pixel(Index); If Index[8]=-1 then {điểm hiện tại không có điểm tiếp theo – đã xét hết} Begin Xi<-tiếp theo trong index Init_Index(Index); End 3. vòng lặp chính While true do Begin Push(WinerStack,Xi); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M ImageIn[Xi]=0; If Xi=XB then exit; {kết thúc} Find_Successor(ImageIn, Xi,T,Index, last); D=Find_Direc(Last,Xi); Last=Xi; If (d>0) & (ImageIn[Index[d]] là thỏa then Xi=Index[d]; Sort_pixel(Index); /* xác định đỉnh có khả năng*/ For i=1 to 8 do If Index[i].gia-1 then Push(TempStack, Index[i]); If Index[8]-1 & ImageIn[index[8]]=0 then Xi=Index[8]; Else While (TempStack not Empty) & (ImageIn[Xi]=0) do Begin Xi=pop(TempStack); If TempStack is Empty then quay lui; While (WinerStack not Empty and XiX0 )do X0=pop(winerStack); End Init_Index(Index); End 4. Kết thúc 9. Một số thuật toán khác • Thuật toán: tìm đường cong sử dụng biến đổi Hough THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 1. Lượng tử hóa không gian số tổng giới hạn của tham số a. Không gian tham số với n chiều được cho bởi tham số của véc tơ a. 2. bộ nhớ n chiều là mảng A(a) với cấu trúc lượng tử hóa của không gian tham số; tập hợp các phần tử tới 0. 3. Từ một điểm ảnh (x1,x2) trong độ dốc thích hợp của hình ảnh, tăng tất cả các ô nhớ A(a) nếu f(x,a)=0 A(a)=A(a)+∆A Cho tất cả giá trị a bên trong giới hạn dùng trong bước (1) 4. tìm số lớn nhất trong mảng A phù hợp với sự mô tả đường cong f(x,a) hiện có trong hình ảnh gốc. - Nếu chúng ta tìm được đường tròn, phân tích biểu thức f(x,a) được hình tròn mong muốn là : (x1-a)2 + (x2-b)2= r2 - bộ chứa cấu trúc dữ liệu phải là không gian 3 chiều - phép biến đổi Hough là kĩ thuật mạnh cho phép tìm ra đường cong, theo phát triển luật số mũ của bộ chứa cấu trúc dữ liệu sự ra tăng của những hạn chế về tham số đường cong là điều kiện thuận lợi để tìm ra đường cong có những tham số nhỏ. - Nếu ưu tiên những thông tin về quản lý biên được sử dụng thì lượng tính toán cần thiết có thể giảm đáng kể. - Ngoài việc sử dụng thông tin đường biên định hướng, tất cả các ô bộ chứa A(a,b) là tăng lên trong không gian tham số nếu con trỏ (a,b) là một đường tròn với tâm x. Sự hiểu biết mang tính định hướng chỉ là số nhỏ trong bộ nhớ cần tăng lên. Nếu đường biên định hướng là lượng tử hóa 8 giá trị có thể, chỉ giá trị thứ 8 của đường tròn cần thêm phần nhỏ trong tăng dung lượng ô chứa Sử dụng đường tròn định hướng, ứng với tham số a và b có thể được định nghĩa từ công thức sau: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M a=x1-R1cos(Ψ(x)) b=x1-Rsin(Ψ(x)) Ψ(x) })(,){( ∆Φ−Φ∆Φ−Φ∈ xx ∆Φ là số đường biên định hướng cũ trong ô x, ∆Φ là số lớn nhất đã biết của đường cong định hướng Ta tìm ra rằng vòng tròn tìm thấy có đóng góp lớn từ các ô bộ nhớ A(a) bằng dung lượng đường biên trong ô x. • Thuật toán: Tổng quan biến đổi Hough 1. đặt 1 bảng R mô tả yêu cầu của đối tượng 2. Dạng cấu trúc dữ liệu A miêu tả khả năng trước đó xem như những con trỏ A(x1,x2,T). tập hợp ô nhớ giá trị A(x1,x2,T)=0 3. Từ một điểm (x1,x2) trong độ dốc giới hạn, hình ảnh đã được xác định đường biên định hướng ∆Φ ; tìm tất cả các khả năng trước đó con trỏ xR và tăng tất cả A(xR,T): A(xR,T)= A(xR,T)+ ∆A Cho tất cả các giá trị đạt được của vòng lặp và cỡ thay đổi ))(cos()(11 TSxx R +ΦΦΓ+= α ))(sin()(22 TSxx R +ΦΦΓ+= α 4. Tìm những vùng phù hợp được cho bởi số lớn nhất trong ô A cấu trúc dữ liệu. • Thuật toán: Định dạng vùng từ từng phần các khung Từ mỗi khung điểm x tìm một đường biên đối với a một khoảng cách không vượt quá a cho giá trị lớn nhất M. Nếu 1 điểm biên đã tìm, đánh dấu một điểm trên đường thẳng kết nối khi đó có một vùng nhớ tiềm năng. Tính số đánh dấu cho mỗi điểm trong hình ảnh, số đánh dấu cho biết một điểm là đường kết nối giữa các điểm biên. Lấy b(x) là số đánh dấu cho điểm x Số đánh dấu b(x) là: B(x) =0.0 từ b(x)=0 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M =0.1 từ b(x)=1 =0.2 từ b(x)=2 =0.5 từ b(x)=3 =1.0 từ b(x)>3 Phương pháp này là cách biểu diễn chính xác các điểm đường bao quanh. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN