Xử lý ảnh là một lĩnh vực đã và đang được quan tâm của nhiều nhà khoa
học trong và ngoài nước bởi tính phong phú và lợi ích của nó được ứng dụng
trong khoa học kỹ thuật, kinh tế, xã hội và đời sống con người. Lĩnh vực xử lý
ảnh liên quan tới nhiều ngành khác như: hệ thống tin học, trí tuệ nhân tạo,
nhận dạng, viễn thám, y học, nông học .
Hiện nay, thông tin hình ảnh đóng vai trò rất quan trọng trong trao đổi
thông tin, bởi phần lớn thông tin mà con người thu được thông qua thị giác.
Do vậy, vấn đề nhận dạng trong xử lý ảnh, đặc biệt là nhận dạng biên ảnh
đang được quan tâm bởi yêu cầu ứng dụng đa dạng của chúng trong thực tiễn.
Mục đích đặt ra cho xử lý ảnh được chia thành hai phần chính: phần
thứ nhất liên quan đến những khả năng từ các ảnh thu lại các ảnh để rồi từ các
ảnh đã được cải biến nhận được nhiều thông tin để quan sát và đánh giá bằng
mắt, chúng ta coi như là sự biến đổi ảnh (image transformation) hay sự làm
đẹp ảnh (image enhancement). Phần hai nhằm vào nhận dạng hoặc đoán nhận
ảnh một cách tự động, đánh giá nội dung các ảnh.
Quá trình nhận dạng ảnh nhằm phân loại các đối tượng thành các lớp
đối tượng đã biết (supervised learning) hoặc thành những lớp đối tượng chưa
biết (unsupervised learning). Sau quá trình tăng cường và khôi phục (đối với
những ảnh có nhiễu), giai đoạn tiếp theo, người ta phải trích rút các đặc tính
quan trọng, quyết định của ảnh cần nhận dạng. Các đặc tính đó có thể là đặc
tính hình học, đặc tính ngữ cảnh.
Các đặc tính hình học chứa những thông tin về vị trí, kích thước hình
học, hình dạng của các đối tượng trong ảnh, là đặc tính rất quan trọng trong
xử lý nhận dạng ảnh. Các đặc tính này thường được trích rút ra thông qua việc
xác định các đường biên các đối tượng trong ảnh. Biên chứa các thông tin về
hình dạng ngoài của đối tượng ảnh. Có thể nói xác định biên là một trong
những vấn đề quan trọng và hấp dẫn trong lĩnh vực nghiên cứu xử lý ảnh bởi
khả năng biểu đạt cấu trúc đối tượng và tính ứng dụng rộng rãi của nó vào
việc giải quyết nhiều bài toán khó như: nhận dạng tự động, thị thực máy tính,
hoạt hình .
Bên cạnh đó, trong những năm gần đây các nghiên cứu về biên ảnh và
phép biến đổi Fourier đã và đang được ứng dụng rộng rãi. Thực tế này đặt ra
các bài toán như: đưa những ứng dụng đó vào xã hội và đời sống con người.
Một số nhóm nghiên cứu trong và ngoài nước đã đưa ra các phương pháp giải
quyết kết hợp các phương pháp phát hiện biên và phép biến đổi Fourier để
hoàn thành những ứng dụng góp phần vào sự phát triển trong xã hội.
Chình vì những ứng dụng thực tiễn đó em đã nghiên cứu luận văn thạc
sĩ với đề tài “ Phát hiện biên, biểu diễn Forier Elliptic và ứng dụng”. Luận văn
gồm phần mở đầu, phần kết luận, và 3 chương nội dung:
Chương 1: Tổng quan về xử lý ảnh và biên.
Chương 2: Một số phương pháp phát hiện biên và phép biểu diễn
Fourier Elliptic.
Chương 3: Chương trình thử nghiệm.
MỤC LỤC
Lời cảm ơn i
Danh mục các ký hiệu, các chữ viết tắt . ii
Danh mục các hình iii
MỞ ĐẦU . 1
CHưƠNG 1. TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN . 3
1.1. Một số khái niệm cơ bản trong xử lý ảnh . 3
1.1.1. Xử lý ảnh. 3
1.1.2 Quá trình thu nhận, biểu diễn và lưu giữ ảnh . 3
1.1.3 Histogram của ảnh 7
1.1.4 Nhận dạng ảnh 8
1.2 Biên ảnh và vai trò trong nhận dạng ảnh . 9
1.2.1 Khái niệm về biên ảnh và các phương pháp phát hiện
biên cơ bản . 9
1.2.2 Vai trò của biên trong nhận dạng ảnh 14
1.2.3 Biểu diễn biên dựa trên mô tả Fourier . 14
1.2.3.1 Phương pháp dựa trên mô tả Fourier . 16
1.2.3.2 Phương pháp góc quay . 19
CHưƠNG 2: MỘT SỐ PHưƠNG PHÁP PHÁT HIỆN BIÊN
VÀ PHÉP BIỂU DIỄN FORIER ELLIPTIC . 22
2.1 Một số phương pháp phát hiện biên 22
2.1.1. Phương pháp phát hiện biện trực tiếp . 22
2.1.2 Phương pháp phát hiện biên gián tiếp 31
2.1.3 Phương pháp phát hiện biên kết hợp 32
2.1.4 Phát hiện biên dựa vào trung bình cục bộ 38
2.1.5 Cải thiện và nâng cao chất lượng biên ảnh 40
2.2 Phép biến đổi Fourier . 49
2.2.1 Định nghĩa 49
2.2.1 Elliptic Fourier 50
2.2.3 Biến đổi Fourier rời rạc . 55
2.2.4 Các thuộc tính khác của biến đổi Fourier 61
CHưƠNG 3: CHưƠNG TRÌNH THỬ NGHIỆM . 62
3.1 Giới thiệu . 62
3.2 Số hóa biên đối tượng ảnh 62
3.2 Chương trình thử nghiệm . 66
KẾT LUẬN . 70
TÀI LIỆU THAM KHẢO 72
Tiếng Việt 72
Tiếng Anh 72
83 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1807 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Luận văn Phát hiện biên, biểu diễn fourier elliptic và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
pháp tiếp cận tối ưu hóa định vị đúng vị trí bằng cách cực tiểu
hóa phương sai σ 2 của vị trí các điểm cắt không (cross-zero) hoặc hạn
chế số điểm cực trị cục bộ để chỉ tạo ra một đường bao.
Nhìn chung các phương pháp phát hiện biên như đã trình bày ở trên đều
có ít nhiều sử dụng đến các kỹ thuật đạo hàm. Ý tưởng chung của các kỹ thuật
tìm biên sử dụng đạo hàm đó là sử dụng các bộ lọc thông cao để làm nổi biên.
Bởi vì các điểm biên là các chi tiết có tần số không gian cao nên khi ảnh được
lọc thông cao, các phần tử có tần số không gian cao sẽ sáng hơn còn các phần
tử có tần số không gian thấp sẽ tối đi. Kỹ thuật lọc thông cao được thực hiện
nhờ thao tác nhân chập.
Việc sử dụng các mặt nạ nhân chập có một nhược điểm chung đó là bản
thân phép lọc không tự động loại bỏ hoặc hạn chế được nhiễu. Bởi vì đặc tính
của nhiễu, nếu xem xét một cách tương đương trong không gian tần số, nhiễu
ứng với các thành phần tần số cao trong ảnh. Các phép lọc thông cao tuy làm
nổi các điểm biên nhưng đồng thời cũng làm nổi các nhiễu. Hơn thế nữa để
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
29
phân tích, nhận dạng ảnh người ta thường muốn xử lý trên các ảnh biên chỉ có
hai màu (màu biên và màu nền) để cho đơn giản. Các ảnh qua lọc lấy biên
không cho ra ảnh biên (hai màu) mà cần phải thông qua một vài phép xử lý
trung gian nữa (chẳng hạn phân ngưỡng) thì mới thu được ảnh biên thực sự.
Bản thân quá trình xử lý này cũng có thể lại làm mất đi các chi tiết của ảnh
biên sau phép lọc.
Ngoài ra, các kỹ thuật tìm biên sử dụng đạo hàm còn có một hạn chế
nữa là không cho phép điều chỉnh độ chi tiết của ảnh biên thu được. Trong
các ảnh chụp thế giới thực, sẽ có rất nhiều các đối tượng trong ảnh có độ chi
tiết (mờ, rõ) khác nhau. Khi nhận dạng, không hẳn là chúng ta sẽ quan tâm
đến tất cả các đối tượng mà chủ yếu là chỉ quan tâm đến các đối tượng chính
trong ảnh. Các đối tượng này thường có độ chi tiết và độ rõ cao. Sử dụng các
mặt nạ nhân chập không cho phép chúng ta điều chỉnh độ chi tiết của các ảnh
biên thu được một cách dễ dàng, rõ ràng buộc tổng các hệ số của bộ lọc phải
bằng 1; nhằm ngăn cản sự tăng quá giới hạn của các giá trị mức xám (các giá
trị điểm ảnh phải giữ được giá trị của nó một cách gần đúng không thay đổi
quá nhiều so với giá trị thực). Phần dưới đây, tôi xin giới thiệu tổng quan kỹ
thuật phát hiện biên thuộc loại phát hiện biên trực tiếp nhưng không dựa và
đạo hàm mà dựa vào phép toán hình thái [29] đang được nhiều nhà khoa học
quan tâm.
2.1.1.3. Tìm biên bằng phép toán hình thái
Ở phần này, em chỉ xin được giới thiệu tổng quan phép toán hình thái để làm
định hướng cho quá trình nghiên cứu sau này. Phép toán hình thái thực hiện
trên cơ sở ảnh ban đầu đã được làm trơn bằng phép lọc trung vị. Giả sử P là
một điểm của ảnh đã được làm trơn, tính hai độ lệch của điểm đó với các giá
trị lớn nhất và nhỏ nhất của cửa sổ xung quanh P, (cửa sổ 33). Giá trị nhỏ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30
hơn trong hai giá trị đó sẽ được chọn làm giá trị điểm ảnh đầu ra. Quá trình
này sẽ được mô tả mhư sau:
Giả sử ảnh gốc I(m,n) được làm trơn bằng bộ lọc trung bình tạo ra ảnh
O1(m,n):
W(m,n) là cửa sổ của (m,n) nhận điểm này làm trung tâm (phép xếp
chồng tại trung tâm) được chọn thích hợp. Nw là số điểm của cửa sổ này. Một
điểm ảnh đầu ra O2(m,n) được tính từ ảnh O1(m,n) thông qua phép so sánh và
lựa chọn bởi:
Trong đó F(m,n) là cửa sổ lân cận của điểm (m,n) cũng được
chọn thích hợp
Như vậy, các điểm biên được làm nổi lên, nhờ phép so sánh, chọn ra độ
sai khác nhỏ nhất giữa nó và giá trị độ sáng của các điểm ảnh thuộc lân cận.
Sai khác này càng lớn thì điểm biên càng được làm nổi.
),(,
1 ),(
1
),(
nmWlkw
lnkmI
N
nm
),(
11
)(
112 ),()(max,)(min),(mi),(
nmFqmnFq
nmOqOqOnmOnm
XTB = ((XB)B)
Xấp xỉ trên của X (chứa X)
XDB = ((XB)B)
Xấp xỉ dưới của X (thuộc X)
X B = XTB\XDB
Xấp xỉ biên của X theo mẫu B
Hình 2.6. Minh hoạ biểu diễn biên nhờ các phép toán hình thái
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31
2.1.2. Phƣơng pháp phát hiện biên gián tiếp
2.1.2.1. Phân vùng ảnh dựa theo ngưỡng biên độ
Ảnh khi được miêu tả thông qua hàm f(x,y) có thể được quan niệm như
một môi trường vật lý. Trong đó, các hiện tượng như phản xạ, truyền sáng,
màu sắc hoặc đáp ứng đa phổ đều có thể mô tả được. Các hàm f(x,y) có thể
đặc trưng cho biên độ của các tính chất vật lý của ảnh, còn các biến (x,y)
ngoài ý nghĩa vị trí có thể được sử dụng như là điện áp, nhiệt độ,
hoặc vận tốc.
Chúng ta có thể dùng ngưỡng biên độ để phân vùng ảnh khi mà biên độ
là đủ lớn để đặc trưng cho ảnh. Kỹ thuật phân ngưỡng theo biên độ được tiến
hành theo các bước như sau:
Xem xét lược đồ xám của ảnh để xác định các đỉnh và các khe. Nếu ảnh
có dạng rắn lượn (nhiều đỉnh và khe), các khe có thể sử dụng để
chọn ngưỡng.
Chọn ngưỡng t sao cho một phần xác định trước của toàn bộ số mẫu là
thấp hơn t.
Điều chỉnh ngưỡng dựa trên xem xét lược đồ xám của các điểm lân cận.
Chọn ngưỡng như xem xét lược đồ xám của những điểm thỏa mãn tiêu
chuẩn chọn. Thí dụ, với ảnh có độ tương phản thấp, lược đồ của những
điểm có biên độ Laplace g(m,n) lớn hơn giá trị t định trước (sao cho từ
5% đến 10% số điểm ảnh với Gradient lớn nhất sẽ coi như biên) sẽ cho
phép xác định các đặc tính của ảnh lưỡng cực tốt hơn ảnh gốc.
Khi có một mô hình phân lớp xác suất, việc xác định ngưỡng dựa vào
tiêu chuẩn nhằm cực tiểu xác suất của sai số hoặc một số tính chất khác theo
luật của Bayes.
2.1.2.2. Phân vùng dựa theo miền đồng nhất
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32
Kỹ thuật phân vùng ảnh thành các vùng đồng nhất dựa vào các tính
chất quan trọng nào đó của miền. Việc lựa chọn các tính chất của miền sẽ xác
định các tính chất phân vùng. Các tiêu chuẩn hay được dùng là sự thuần nhất
về mức xám, màu sắc đối với ảnh màu, kết cấu sợi và chuyển động.
Có 3 cách tiếp cận chủ yếu trong phân vùng ảnh theo miền đồng nhất
và độc lập với tiêu chuẩn chọn lựa tính đồng nhất đó là:
Phương pháp phân tách - cây tứ phân (split-quad stress)
Phương pháp hợp (merge)
Phương pháp tách hợp (split-merge)
Mức độ hiệu quả của các phương pháp là tùy thuộc vào việc chọn tiêu
chuẩn đánh giá độ thuần nhất. Nhìn chung các kỹ thuật phân vùng ảnh cho
phép chúng ta phát hiện biên một cách chính xác hơn các kỹ thuật đạo hàm do
ít chịu ảnh hưởng của nhiễu, nhưng hầu hết các kỹ thuật phân vùng này đều
có cài đặt khá phức tạp và thường làm mất nhiều chi tiết của các đối tượng
trong ảnh nên thường không được sử dụng để tìm biên.
2.1.3. Phƣơng pháp phát hiện biên kết hợp
Để phát hiện biên của đối tượng trong frame ảnh. Phương pháp này
được áp dụng để tìm biên cho ảnh 256 cấp xám đã thử nghiệm và được đánh
giá khá hiệu quả. Việc xử lý và thao tác trên các ảnh xám có một ưu điểm là
dễ xử lý hơn các ảnh màu mà vẫn giữ được nhiều đặc tính của ảnh. Khi muốn
nhận dạng biên cho các ảnh màu, chúng ta có thể dễ dàng chuyển đổi về
khuôn dạng ảnh 256 cấp xám bằng hàm ConvertRGB được cài đặt trong
chương trình Demo. Việc không xử lý ở ảnh đen trắng, bởi các frames ảnh
được quay hoặc thu trực tiếp từ Camera là ảnh màu 16 bits hoặc 24 bits. Do
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33
đó, khi chuyển sang ảnh đen trắng sẽ làm mất rất nhiều thông tin. Hình 2.7,
2.8 và hình 2.9 dưới đây sẽ minh họa điều này.
Hình 2.7 Ảnh gốc
Hình 2.8 Ảnh đen trắng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34
Hình 2.11. biên của ảnh đen trắng
PCX
Hình 2.9 Ảnh đen trắng dùng hàm ConvertRGB
Để xây dựng thuật toán tìm biên cho ảnh đa cấp xám, trước hết chúng
ta nhắc lại một thuật toán tìm biên cho ảnh trắng đen rất đơn giản và hiệu quả.
Ý tưởng của thuật toán này là dựa vào định nghĩa: trong ảnh trắng đen, một
điểm có thể gọi là biên nếu nó là điểm đen và có ít nhất một điểm trắng lân
cận. Ảnh sẽ được quét từ trái sang phải, từ trên xuống dưới, khi gặp điểm đen
đầu tiên sẽ thực hiện quay theo 8 láng giềng để tìm điểm biên tiếp theo, cứ thế
cho đến khi quay được về điểm biên được xác định đầu tiên thì dừng. Kết quả
chúng ta sẽ được biên của ảnh. Hình dưới đây minh họa kết quả dò biên ảnh
đen trắng PCX
Hình 2.10 Ảnh đen trắng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35
Hình 2.11 Biên ảnh đen trắng
Thủ tục phát hiện biên của ảnh đen trắng PCX có thể được viết ngắn
gọn như sau:
LPSTR Detect_Edge_BW_Image(LPSTR pOrgImg, LPSTR pEdgImg)
{ int i,j,k
struct Point { int x,y; };
Point Orient[8] = {(0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1),(1,0),(1,1) };
for (i=0; i<biHeight; i++)
for (j=0; j<biWidth; j++)
if ( GetPoint(pOrgImg,i,j)==BLACK )
for (k=0; k<8; k++)
if (GetPoint(pOrgImg,i+Orient[k].x,j+Orient[k].y)==WHITE)
{ SetPoint(pEdgImg,i,j,BLACK);
break;
}
return pEdgImg;
}
Trong đó:
biWidth, biHeight lần lượt là chiều rộng và chiều cao của ảnh (tính theo
đơn vị pixel) .
GetPoint() và SetPoint() là các hàm đọc, ghi điểm ảnh.
pOrgImg, pEdgImg là các con trỏ lần lượt trỏ tới các vùng dữ liệu của
ảnh gốc và ảnh biên.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
Như vậy, việc tìm biên cho các ảnh trắng đen theo cách dựa vào định
nghĩa là khá dễ dàng (dựa vào 2 mức 0, 1). Chúng ta sẽ dựa theo ý tưởng đó
để tìm biên cho các ảnh đa cấp xám. Tuy nhiên có một khó khăn mắc phải là
ảnh đa cấp xám có 256 màu. Sự biến thiên về giá trị độ xám của điểm ảnh
theo các hướng khác nhau cũng là khác nhau. Do đó nếu đánh giá một điểm là
điểm biên hay không nếu chỉ dựa vào việc đánh giá độ chênh lệch mức xám
của điểm đó với từng điểm láng giềng lân cận sẽ cho kết quả chưa tốt và ảnh
biên thu được vẫn còn khá nhiều nhiễu.
Để cho kết quả chính xác hơn (để hạn chế nhiễu) thay vì so sánh giá trị
xám của điểm ảnh đang xét với từng điểm ảnh lân cận chúng ta sẽ so sánh với
mức xám trung bình của vùng cửa sổ NxN bao quanh điểm đó cộng với một
giá trị 1 cho trước.
PTB+ ä1< P
Hình 2.12 Ảnh gốc Hình 2.13 Ảnh biên với cách đánh giá
độ chênh lệch mức xám của điểm ảnh
với từng điểm láng giềng kế
Hình 2.14 So sánh với mức xám trung bình của cửa sổ trong
trường hợp N=5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37
Hình 2.15 Xác định điểm biên thực sự
Cơ sở đúng đắn của thuật toán là dựa trên lý thuyết về tính dư thừa thông
tin không gian: các điểm ảnh lân cận có thể có cùng hoặc gần cùng một số đặc
tính. Thực nghiệm cho thấy sử dụng các cửa sổ vuông kích thước 5x5 để tìm
biên hạn chế được nhiều nhiễu là hơn các cửa sổ 3x3 nhưng các đường biên
thu được cũng sẽ dày hơn. Việc tăng kích thước của cửa sổ lên nữa không làm
tăng độ chính xác lên nhiều mà lại làm cho độ phức tạp tính toán tăng lên rất
nhanh. Chúng ta sẽ sử dụng các mặt nạ 5x5 để tìm biên nhưng để thu được
các đường biên mảnh cần vận dụng lại ý tưởng sử dụng định nghĩa. Tức là các
điểm ảnh được lọc ra sau khi so sánh với giá trị xám trung bình của cửa sổ
(tạm gọi là các điểm thuộc lân cận biên) lại được so sánh một lần nữa với các
điểm kế cận (thuộc 8 láng giềng của nó) cộng với một giá trị 2 xác định
trước. Và các điểm biên thu được lần này mới được coi là các điểm
biên thực sự.
Pi + 2 < P
Hình dưới đây minh họa kết quả của phương pháp tìm biên kết
hợp với N=5.
Hình 2.16. ảnh biên áp dụng phương pháp kết hợp với N=5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38
Dưới đây là thủ tục tìm biên của chương trình:
LPSTR DetectEdgeGrayImage(LPSTR pOrgImg,LPSTR pEdgImg,int 1,int
2)
{
int i,j,k,ii,jj,P0;
struct Point { int x,y; };
Point Orient[8] = {(0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1),(1,0),(1,1) };
for (i=2; i<biHeight-2; i++)
for (j=2; j<biWidth-2; j++)
{
// tinh gia tri xam trung binh cua cac diem anh thuoc cua so 5x5
for (ii=i-2;ii<=i+2;ii++)
for (jj=j-2;jj<=j+2;jj++)
TG+=GetPoint(pOrgImg,ii,jj);
TG=int(TG/25);
P0=GetPoint(pOrgImg,i,j);
if (P0+1<TG)
for (k=0;k<8;k++)
// so sanh voi cac diem thuoc 8 lang gieng
if (P0+2<GetPoint(pOrgImg,i+Orient[k].x,j+Orient[k].y))
{
SetPoint(pEdgImg,i,j,BLACK); break;
}
}
return pEdgImg;
}
2.1.4 Phát hiện biên dựa vào trung bình cục bộ
Phần này đề cập đến kỹ thuật mới dựa vào trung bình cục bộ trên cơ sở
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39
đánh giá độ chênh lệch về giá trị mức xám của điểm ảnh so với các điểm lân
cận do đó kết hợp được ưu điểm của cả 2 khuynh hướng phát hiện biên trực
tiếp và gián tiếp.
Ý tưởng chính của thuật toán được đề xuất là xác định tất cả các điểm
nằm trên biên không theo hướng tìm kiếm và sử dụng các ma trận lọc mà sẽ
thông qua việc so sánh độ chênh lệch về mức xám của nó so với mức xám
chung của các điểm ảnh lân cận (mức xám nền). Trước hết tính giá trị xám
trung bình của các điểm ảnh nằm trong phạm vi của ma trận 3×3 hoặc 5×5
có tâm là điểm ảnh đang xét. Nếu như độ chênh lệch mức xám giữa điểm
đang xét với giá trị xám trung bình thỏa mãn lớn hơn một mức tối thiểu δ1
nào đó (PTB+ δ1< P) thì chúng ta sẽ coi nó là điểm biên và ghi nhận lại, còn
các điểm không thỏa mãn điều kiện trên sẽ được coi là điểm nền.
N=5
Hình 2.17 Ma trận điểm ảnh trước và sau lọc
Ảnh biên thu được với δ1= 25 Ảnh biên thu được với δ1= 250
Hình 2.18 Các ảnh biên kết quả thu được theo thuật toán đề xuất
*Nhận xét:
Thuật toán dò biên sử dụng trong chương trình tuy đã hạn chế được
nhiều nhiễu so với việc sử dụng các bộ lọc và làm nổi rõ các đường biên
nhưng vẫn không loại bỏ được hầu hết các nhiễu. Khi áp dụng thuật toán
δ1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40
trên chúng ta vẫn có thể làm giảm bớt nhiễu đi nhiều hơn nữa bằng cách
tăng giá trị của hệ số delta lên. Nhưng khi đó các đường biên thu được cũng
bị đứt đoạn và mờ đi nhiều.
2.1.5. Cải thiện và nâng cao chất lƣợng biên ảnh
2.1.5.1. Các kỹ thuật tiền xử lý
Trong giai đoạn tiền xử lý, vấn đề mà chúng ta phải quan tâm đến
nhiều nhất đó là vấn đề nhiễu. Nhiễu là nguyên nhân chủ yếu gây nên những
khó khăn cho phân tích ảnh. Nguyên nhân gây ra nhiễu có thể là do nhiễu
điện tử của máy thu hoặc chất lượng kém của bộ số hóa. Chúng ta hãy xem
xét thể hiện của nhiễu trên ảnh thế nào. Giả sử ảnh là một miền có mức xám
đồng nhất. Như vậy, các phần tử của ma trận biểu diễn ảnh sau quá trình số
hóa phải có cùng giá trị. Nhưng thực tế quan sát kỹ, ta thấy: gần giá trị trung
bình của mức xám có những phần tử trội lên khá nhiều. Đó chính là hiện
tượng nhiễu. Như vậy, nhiễu trong ảnh số được xem là sự dịch chuyển nhanh
của tín hiệu thu nhận (tín hiệu ảnh) trên một khoảng cách ngắn. Xem xét một
cách tương đương trong không gian tần số, nhiễu ứng với các thành phần tần
số cao trong ảnh.
Phần dưới đây, em sẽ trình bày các kỹ thuật khử nhiễu. Trước hết
chúng ta tìm hiểu một số kỹ thuật lọc nhiễu đang được sử dụng phổ biến hiện
nay. Để khử nhiễu, thông thường người ta lấy “tổ hợp” các điểm lân cận
(trong không gian thực) hay lọc các thành phần tần số cao (trong không gian
tần số). Cơ sở lý thuyết của kỹ thuật lọc số cũng dựa trên tính dư thừa thông
tin không gian: các pixel lân cận có thể có cùng hoặc gần cùng một số đặc
tính. Hơn nữa nhiễu cũng có thể coi như sự đột biến của một số điểm ảnh so
với các điểm ảnh lân cận. Tùy theo cách tổ hợp điểm đang xét mà ta có kỹ
thuật lọc tuyến tính hay phi tuyến.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
41
2.1.5.1.1. Kỹ thuật lọc tuyến tính
Với kỹ thuật lọc tuyến tính, ảnh thu được sẽ là tổng trọng số hay là
trung bình trọng số các điểm lân cận với nhân cuộn hay mặt nạ. Nguyên tắc
lọc theo tổng trọng số được minh họa như hình dưới đây:
Tức là: P = P1K1 + P2K2 + P3K3 + P4K4 + P5K5 + P6K6 + P7K7 + P8K8
= X
8 lân cận của P5 nhân cuộn 3x3
Hình 2.19 Lấy tổ hợp các điểm ảnh lân cận.
Các mặt nạ thường dùng là :
Mặt nạ H1 là mặt nạ dùng để tính trung bình không trọng số (không ưu
tiên theo hướng nào cả). Mặt nạ H2 cho trọng số lớn nhất với điểm ở tâm. Còn
mặt nạ H3 ưu tiên cho hướng x,y. Các mặt nạ lọc nói trên, nhìn chung làm
giảm mức nhiễu trắng đi Nw lần, với Nw là số phần tử của mặt nạ. Tuy nhiên,
nếu kích thước của mặt nạ càng lớn thì ảnh càng bị nhòe.
P
P1 P2 P3
P4 P5 P6
P7 P8 P9
K1 K2 K3
K4 K5 K6
K7 K8 K9
1 1 1
H1=1/9 1 1 1
1 1 1
1 1 1
H2=1/10 1 2 1
1 1 1
1 2 1
H3=1/16 2 4 2
1 2 1
Hình 2.20 Một số kiểu mặt nạ sử dụng cho kỹ thuật lọc phi tuyến.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
42
2.1.5.1.2. Kỹ thuật lọc phi tuyến
Khác với lọc tuyến tính, kỹ thuật lọc phi tuyến coi một điểm ảnh là kết
quả không phải là tổ hợp tuyến tính của các điểm lân cận. Bộ lọc phi tuyến
thường dùng là lọc trung vị (median filtering). Trong trường hợp một chiều,
trung vị xa của một chuỗi n phần tử {xn} được định nghĩa:
- Nếu n lẻ: có (n-1)/2 phần tử lớn hơn xa và (n-1)/2 nhỏ hơn hay bằng xa.
- Nếu n chẵn: xa là trung bình cộng của hai phần tử xi và xj{xn} sao cho có
(n-2)/2 phần tử nhỏ hơn hay bằng xi và (n-2)/2 phần tử lớn hơn hay bằng xj.
Thuật toán lọc trung vị được dùng để lọc nhiễu bằng cách trượt trên
mặt phẳng ảnh, mỗi lần trượt di chuyển một điểm. Những phần tử trong cửa
sổ được xem như là một chuỗi {xn} và điểm quan tâm được thay thế bởi giá
trị xn của chuỗi. Thí dụ như chuỗi {1,2,9,5,4}, điểm trung tâm sẽ được thay
thế bởi giá trị 4 được tính theo nguyên tắc ở trên. Rõ ràng trong thí dụ này 9
có thể là nhiễu chọn trong dãy tăng dần. Lọc trung vị thường sử dụng cửa sổ
có kích thước 3. Tuy nhiên nếu không có dấu hiệu quan trọng nào bị mất, kích
thước của cửa sổ có thể tăng lên 5,7,9 …và sẽ kết thúc khi quá trình lọc
không làm thay đổi kết quả. Mở rộng kỹ thuật lọc trung vị cho trường hợp hai
chiều. Giả sử đầu vào là X(m,n) và đầu ra bộ lọc là Y(m,n) lọc trung vị hai
chiều được định nghĩa:
Y(m,n)= Median(X(m-k,n-l)) với k,l [1,L]
Lưu ý rằng công thức Lc = (L+1)/2 còn được gọi là bán kính bộ lọc. Do
vậy, ta có cách viết khác tương đương (k,l) (-r,r) với 2r+1=L.
Khi đó, trung vị của cửa sổ vuông nxn có thể được tính như những
phần tử của chuỗi một chiều. Ta tiến hành sắp xếp dãy đó rồi thay thế những
phần tử ở tâm của cửa sổ bằng trung vị của dãy vừa tìm được.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
43
Lọc trung vị có một nhược điểm là số lượng tính toán khá lớn (có thể
bằng số mũ của kích thước cửa sổ lọc). Vì vậy, để khắc phục nhược điểm này
người ta sử dụng một một phương pháp khác là lọc giả trung vị (Pseudo-
median Filter).
Thuật toán lọc giả trung vị có thể mô tả tổng quát như sau:
Bƣớc 1: Lấy các phần tử trong cửa sổ ra mảng một chiều (L phần tử)
Bƣớc 2: Tìm min của lần lượt các chuỗi con rồi lấy max, gọi m1
là giá trị này.
Bƣớc 3: Tìm max của lần lượt các chuỗi con rồi lấy min, gọi m2 là giá
trị tìm được.
Bƣớc 4: Gán giá trị điểm đang xét là trung bình cộng của m1 và m2.
Lọc giả trung vị có nhiều điểm giống như lọc trung vị. Dãy lấy ra không
cần sắp xếp và giá trị gọi là trung vị, lại được tính theo trung bình cộng của
max của min và của min của max. Các kỹ thuật lọc nhiễu như đã trình bày ở
trên tuy khử nhiễu khá tốt nhưng đồng thời cũng lại làm nhòe các đường biên
ảnh hoặc có tính toán khá phức tạp. Để có thể khắc phục được nhược điểm
này, tôi đã áp dụng kỹ thuật lọc tuyến tính cải tiến để có thể vừa loại bỏ được
phần lớn các nhiễu, vừa có thể giữ được độ nét của các đường biên ảnh.
2.1.5.1.3. Kỹ thuật lọc nhiễu cải tiến
Nội dung của thuật toán lọc nhiễu sử dụng trong chương trình được mô
tả như sau: duyệt toàn bộ ảnh gốc, đối với mỗi điểm ảnh xét các điểm thuộc 8
láng giềng của nó. Nếu có điểm ảnh nào có giá trị xám không chênh lệch quá
(hơn hoặc kém) giá trị xám của điểm ảnh hiện tại một khoảng δ cho trước thì
chúng ta đánh dấu lại. Giá trị của điểm ảnh mới trên ảnh thu được tương ứng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
44
với điểm ảnh đang xét sẽ là trung bình cộng của các điểm được đánh dấu và
điểm đang xét.
Thí dụ: Nếu điểm mà chúng ta đang xét là điểm P và có 5 điểm lân cận của nó
thỏa mãn điều kiện P-δ ≤ Pi ≤ P+ δ là P1, P2, P4, P5, P7 thì giá trị của điểm P
mới sẽ được tính theo công thức:
P = (P1 + P2 + P4 + P5 + P7)/5
Hàm lọc nhiễu cải tiến SmoothImage() được trình bày khái quát như sau :
LPSTR SmoothImage(LPSTRpOrgImg,LPSTR pFltImg,int δ)
{
int i,j,ii,jj,P,nP;
for (i=1; i<biHeight-1; i++)
for (j=1; j<biWidth-1; j++)
{
P0=GetPoint(pOrgImg,i,j);
P=0; nP=0;
for (ii=i-1; ii<=i+1; ii++)
for (jj=j-1; jj<=j+1; jj++)
if((P0-<=GetPoint(pOrgImg,ii,jj))&&(GetPoint(pOrgImg,ii,jj))<=P0+ δ))
{
P=P+GetPoint(pOrgImg,ii,jj);
P1 P2 P3
P8 P P4
P7 P6 P5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
45
nP=nP+1;
}
P=int(P/nP);
SetPoint(pFltImg,i,j,P);
}
return pFltImg;
}
Trong đó:
- pOrgImg, pFltImg lần lượt là các con trỏ trỏ đến vùng dữ liệu của ảnh
gốc và ảnh lọc nhiễu.
- P0,P là các giá trị xám của điểm ảnh thuộc ảnh gốc và điểm ảnh mới.
- nP là số lượng điểm ảnh thỏa mãn điều kiện P0- δ ≤ Pi ≤ P0+ δ.
Chúng ta tạm gọi kỹ thuật vừa trình bày ở trên là lọc phân lớp tuyến tính,
bởi vì chúng ta đã thực hiện phân chia các điểm ảnh trong cửa sổ mặt nạ ra
thành hai phần: một phần có giá trị xám nằm trong lân cận của điểm ảnh ở
tâm cửa sổ, còn phần còn lại là các điểm ảnh có giá trị xám nằm ngoài
khoảng; sau đó mới tính giá trị của điểm ảnh mới. Hạn chế của các kỹ thuật
lọc tuyến tính là không phân biệt được các điểm nhiễu và điểm biên. Thực tế
khi quan sát kỹ các bức ảnh chúng ta sẽ thấy các phần lớn các phần tử nhiễu
là những điểm cô lập và có độ chênh lệch mức xám nhỏ hơn các điểm biên
khi so sánh với các điểm nền. Kỹ thuật lọc phân lớp tuyến tính tỏ ra linh động
hơn vì chúng làm nâng giá trị xám của các điểm nhiễu tới gần mức giá trị xám
của các điểm nền (coi rằng màu nền là màu có giá trị xám cao hơn trong bảng
màu), hoặc giữ nguyên giá trị xám của chúng nếu đó là các điểm nhiễu có độ
biến thiên giá trị xám lớn (chúng ta sẽ còn có một thuật toán khác để khử các
điểm nhiễu cô lập này ở phần hậu xử lý cho ảnh biên). Các điểm biên thường
là những điểm có mức xám thấp và nằm liền kề nhau thành một chuỗi nên khi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46
Hình 2.21 Minh họa thuật toán hậu xử lý
qua lọc nhiễu giá trị của nó sẽ không bị thay đổi nhiều. Do đó thuật toán lọc
nhiễu phân lớp vừa đảm bảo được yêu cầu khử nhiễu cho ảnh biên, vừa không
làm cho các đường biên bị nhòe đi nhiều. Hơn nữa, nó còn cho phép chúng ta
thay đổi độ lọc nhiễu bằng cách cho điểu chỉnh tham số δ ở đầu vào. Tuy
nhiên nếu giá trị của δ càng lớn thì ảnh càng bị nhòe dù rằng tốc độ nhòe ảnh
là chậm khi ta thay đổi giá trị của δ.
2.1.5.2. Kỹ thuật hậu xử lý
Chúng ta biết rằng, ảnh cho dù đã qua lọc nhiễu trước khi dò biên thì
vẫn có thể còn tồn tại các đốm nhiễu. Bởi vì, chúng có thể là các điểm có độ
biến thiên mức xám tương đương với các điểm biên hoặc là các đối tượng nhỏ
trong ảnh. Chúng ta gọi các đối tượng như vậy là các đốm nhiễu. Khi xử lý
nhận dạng ảnh hiếm khi cần phải quan tâm đến các đối tượng này, bởi vậy
việc loại bỏ chúng đi là cần thiết. Chúng ta sẽ tiến hành khử đốm nhiễu trên
các ảnh thu được sau khi làm nổi biên.
Chúng ta có nhận xét là kích thước vùng liên thông (vùng điểm ảnh kế
cận nhau) của các đốm nhiễu là rất nhỏ so với kích thước của các vùng biên
của đối tượng. Đây sẽ là cở sở cho thuật toán khử đốm nhiễu được trình bày
dưới đây. Trong thuật toán này chúng ta sử dụng một Queue. Queue được trỏ
bởi hai con trỏ CF (trỏ trước) và CB (trỏ sau). Con trỏ CF dùng để trỏ tọa độ
của điểm đang xét, CB trỏ tới tọa độ của điểm cuối cùng trong danh sách các
điểm thuộc vùng liên thông đã xác định được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
47
Các bước của thuật toán được mô tả như sau:
Bƣớc 1: đọc điểm ảnh đầu tiên, nếu đó là điểm đen thì ghi lại tọa độ của
nó vào Queue rồi chuyển sang bước 2, nếu không thì chuyển sang điểm
ảnh tiếp theo và thực hiện lại bước 1.
Bƣớc 2: đọc tọa độ điểm ảnh (xo,yo) được trỏ bởi con trỏ CF và đánh
dấu lại vào ảnh gốc (để không duyệt lại nữa).
Bƣớc 3: Xét các điểm ảnh thuộc 8 láng giềng của (xo,yo), nếu đó là
điểm đen thì ghi lại tọa độ của nó vào trong Queue và cho trỏ bởi con trỏ
CB, tăng giá trị của biến đếm kích thước Queue_Size thêm một đơn vị.
Lặp lại bước 2 cho đến khi CF > CB hoặc Queue_Size > Max_Size. Với
Max_size là một giá trị nhập vào quy định kích thước tối đa của vùng
liên thông (kích thước đốm nhiễu) .
Bƣớc 4: đọc giá trị của Queue_Size, nếu Queue_Size > Max_Size thì
xóa tất cả các điểm thuộc Queue; nếu không thì hủy đánh dấu cho
chúng.
Quay lại thực hiện bước 1 cho đến khi toàn bộ các điểm ảnh đều được
xét duyệt hết. Dưới đây là trình bày khái quát của hàm Despecke()
LPSTR Despecke(LPSTR pImg,int Max_Size)
{
struct Point{ int x,y; };
Point *Q=new Point[MaxSize+10];
int i,j,k,CF,CB,QSz,xo,yo;
int dx[8]={-1,-1,-1,0,1,1,1,0},
dy[8]={-1,0,1,1,1,0,-1,-1};
for (i=0;i<biHeight;i++)
for (j=0;j<biWidth;j++)
if (GetPoint(pImg,i,j)==BLACK)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48
{
// luu toa do diem dau tien (i,j) vao Queue
CF=CB=0; QSz=1; Q[0].x=i; Q[0].y=j;
do{
// danh dau la diem da xet
SetPoint(pImg,Q[CF].x,Q[CF].y,GREEN);
xo=Q[CF].x; yo=Q[CF].y;
for (k=0;k<8;k++)
// neu tim thay mot diem ke can diem dang xet thi
// dua no vao Queue
if (GetPoint(pImg,xo+dx[k],yo+dy[k])==BLACK)
{
CB++; QSz++;
Q[CB].x=xo+dx[k]; Q[CB].y=yo+dy[k];
}
CF++;
}while (CF<=CB&&QSz<=MaxSize);
// neu kich thuoc vung lien thong khong vuot qua gia tri
// Max_Size thi xoa no di
if (QSz<=MaxSize)
for (k=0;k<QSz;k++)
SetPoint(pImg,Q[k].x,Q[k].y,WHITE);
else
// nguoc lai huy danh dau cho cac diem trong Queue
for (k=0;k<QSz;k++)
SetPoint(pImg,Q[k].x,Q[k].y,BLACK);
}
delete Q;
return pImg;
}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
49
Hạn chế của thuật toán này là nếu như ảnh biên thu được có các đường
biên bị đứt nét thì nó cũng bị coi là các đốm nhiễu và bị khử bởi thuật toán
của chương trình. Điều này đòi hỏi ảnh biên phải có các đường biên liên tục.
2.2 Phép biến đổi Fourier.
2.2.1 Định nghĩa :
Định nghĩa phép biến đổi Fourier của hàm f(x) như sau:
dxe)x(f)w](f[F iwx
và phép biến đổi Fourier ngược (IFT) là:
dwe)w(f
2
1
)x](f[F iwx1
Phép biến đổi Fourier của hàm f(x) là hàm f(w). F[f] là kí hiệu biến đổi
Fourier của hàm f, hoặc gọn hơn, phép biến đổi của f theo x tại w. Phép biến
đổi thực hiện theo biến độc lập của f (khi f=f(t)), t là biến độc lập; f=f(x) cho
biết x là biến độc lập... tại biến mặc định w. Qui ước F[f] là biến đổi Fourier
của f tại w và F-1[f] là biến đổi Fourier ngược (IFT) của f tại x.
Matlab Symbolic cung cấp 2 hàm fourier và ifourier xác định phép biến
đổi Fourier và phép biến đổi ngược.
Cú pháp của hàm fourier:
F = fourier(f)
-Trả về kết quả phép biến đổi Fourier của hàm vô hướng kí hiệu f với
biến độc lập x. F là hàm của w. Nếu f=f(w), fourier trả về hàm của t: F=F(t).
Theo định nghĩa F(w)=int(f(x)*exp(-i*w*x),x,-inf,inf), với tích phân theo
biến x (Thực tế biến kí hiệu trong f được xác định bởi findsym)
F = fourier(f,v)
-Trả về hàm F theo biến kí hiệu v thay cho biến mặc định w:
fourier(f,v) F(v) = int(f(x)*exp(-i*v*x),x,-inf,inf).
F= fourier(f,u,v)
-Coi f là hàm của u thay cho biến mặc định x. F là hàm của v.
fourier(f,u,v) F(v) = int(f(u)*exp(-i*v*u),u,-inf,inf).
Biến đổi Fourier ngược.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
50
Cú pháp của hàm ifourier:
f = ifourier(F)
-Trả về dạng biến đổi Fourier ngược của biến vô hướng kí hiệu F theo
biến độc lập w. Mặc định trả về hàm f của x. Biến đổi Fourier ngược được áp
dụng cho hàm của w và trả về hàm của x: F = F(w) => f = f(x). Nếu F = F(x),
thì ifourier trả về hàm của t: f = f(t).
Theo định nghĩa, f(x) = 1/(2*pi) * int(F(w)*exp(i*w*x),w,-inf,inf) và
tích phân được tính theo x.
f = ifourier(F,u)
-Trả về hàm f của u thay cho biến mặc định x:
ifourier(F,u) f(u) = 1/(2*pi) * int(F(w)*exp(i*w*u,w,-inf,inf).
ở đây u là biến vô hướng kí hiệu.
f = ifourier(F,v,u)
-Coi F là hàm của v thay cho biến mặc định w:
ifourier(F,v,u)
f(u) = 1/(2*pi) * int(F(v)*exp(i*v*u,v,-inf,inf),
tích phân được lấy theo v.
2.2.2 Fourier Elliptic trong đường biên đóng.
Chain Code đầu tiên được mô tả bởi Freeman là một đường biên liên
tục bằng một đoạn tuyến tính mà bao gồm tám đoạn đường chuẩn hóa. Mã
của một đường biên là chuỗi V của độ dài K.
V = a1a2….ak
Với mỗi một liên kết ai là một số nguyên giữa 0 và 7 định hướng /4 theo
hướng chiều kim đồng hồ truy cập từ trục X của một XY phối hợp hệ thống
của chiều dài 1 hoặc
2
phụ thuộc, tương ứng.
Các đại diện của liên kết vector ai, bằng cách sử dụng ký hiệu phasor là:
i
a
a
4
))1(1(
2
12
1( 1
Vị dụ về chain code trong hình sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51
V1=0005676644422123
H 2.22 Ví dụ về chain code
Chuỗi mã (chain codes)
Để có thể mô tả một chu tuyến của đối tượng ảnh dưới dạng số, người
ta có thể lưu trữ theo phối hợp của một chuỗi các điểm ảnh trong ảnh đó. Hay
là người ta có thể chỉ lưu trữ vị trí tương đối giữa các điểm ảnh liên tiếp. Đó
chính là ý tưởng cơ bản của chuỗi mã. Chuỗi mã là một trong các kỹ thuật lâu
nhất trong lĩnh vực thị giác máy tính (computer vision). Kỹ thuật này được
giới thiệu từ năm đầu thập niên 60 của thế kỷ 20 bởi Freeman, và tiếp tục
được ông phát triển và xem xét đến năm 1974. Với chuỗi mã, tập các điểm
ảnh trong đường biên một hình dạng của đối tượng ảnh được chuyển sang một
tập các kết nối giữa chúng. Về cơ bản nguyên lý của mã chuỗi như sau:
Khi chúng ta thu được một đường biên hoàn chỉnh thì đó là một tập các
điểm ảnh đã được liên kết với nhau, sau đó bắt đầu từ 1 trong các điểm ảnh đó
chúng ta cần xác định chiều đến các điểm ảnh tiếp theo trong đường biên đó.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52
Cụ thể là, điểm tiếp theo là một trong những điểm liền kề theo chiều kim của
la bàn. Do đó, các mã chuỗi được hình thành bởi sự móc nối một số chỉ rõ
chiều của điểm ảnh tiếp theo. Với một điểm ảnh thu được thì chiều kế tiếp từ
điểm ảnh đó tới điểm ảnh tiếp theo trở thành phần tử trong mã cuối. Quá trình
này sẽ được lặp cho mỗi điểm ảnh đến tận khi tới điểm bắt đầu. Khi đó, hình
dạng của đối tượng ảnh được phân tích hoàn toàn.
Việc xác định những kết nối của chuỗi mã có thể được xuất phát từ
nguyên lý của 4-láng giềng và 8-láng giềng như minh họa trong hình 2.23
P1
P2 P P0
P3
P3 P2 P1
P4 P P0
P5 P6 P7
a) b)
c) d)
Hình 2.23. Minh họa sự kết nối của chuỗi mã theo nguyên lý 4-láng giềng,
và 8-láng giềng
a)4-láng giềng; b) 8-láng giềng; c) sự kết nối của các mã chuỗi theo cách 4-
kết nối; d) sự kết nối các mã chuỗi theo cách 8-kết nối.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53
Tương ứng với chỉ số trong hình 2.23, mã code của điểm P sẽ được
đánh số từ 0 đến 3 đối với 4-kết nối, và đánh số từ 0 đến 7 đối với 8-kết nối,
chỉ số này tăng theo chiều kim đồng hồ.
Tiếp theo, em minh họa cách tính chuỗi mã của đối tượng ảnh như hình
2.24. Trong trường hợp này, chúng ta đã xác định chiều của điểm bắt đầu là
từ hướng nam, nên thành phần đầu tiên của chuỗi mã là 2 đối với 4-kết nối, và
là 3 đối với 8-kết nối. Chiều từ điểm P1 điểm tiếp theo, điểm P2 theo hướng
đông, nên thành phần mã chuỗi tiếp theo là 1 đối với 4-kết nối, nhưng đối với
8-kết nối hướng của P2 là nam, nên thành phần tiếp theo của chuỗi mã là 4.
a)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
54
b) c)
Hình 2.24. Minh họa chuỗi mã bởi các kết nối khác nhau
a) Đối tượng ảnh; b) chuỗi mã với 4-kết nối; c) chuỗi mã với 8-kết nối
Điểm tiếp theo sau P2 là P3 có hướng nam nên thành phần tiếp theo có
mã là 2 đối với 4-kết nối, còn với 8-kết nối thì hướng của P3 là hướng đông
nam, nên thành phần tiếp theo có mã là 3. Quá trình này được lặp đi lặp lại
đến khi đến điểm P23 được kết nối về phía đông để tới điểm băt đầu, do đó
thành phần mã cuối cùng sẽ là 1 đối với 4-kết nối, và là 2 đối với 8-kết nối.
Do đó, chuỗi mã của ảnh trong hình 2.24(a) với 4-kết nối và 8-kết nối tương
ứng là như sau:
code4-kết nối={2,1,2,2,12,2,3,2,2,3,0,3,0,3,0,0,1,0,1,0,1}
code8-kết nối={3,4,3,4,4,5,4,6,7,7,7,0,0,1,1,2}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
Rõ ràng, chuỗi mã sẽ khác nhau nếu như điểm bắt đầu khác nhau. Do
đó, chúng ta cần phải có điểm bắt đầu xác định trước và bất biến.
Thuật toán chain code được thể hiện như sau:
Class Chain: Public LineRep{
Declare_members (Chain)
ChainSeq Chain;
Public;
Enum ChainDir { north=0, ne=1, east =2, se=3, south=4, sw=5, west =6,
nw=7 };
Static const int DefautLen;
Chain();
Chain();
Chain (PointXY&, int = Chain: :DefautLen);
Chain (const Chain&);
Int number() const {return chain.length();}
Void append (byte b){chain.append(b);}
Void append (const chain&);
Inline byte operator[] (int) const;
}
2.2.3 Những biến đổi Fourier rời rạc (DFL)
2.2.3.1 Biến đổi một chiều.
Cho rằng mối quan tâm xử lý hình ảnh mẫu dữ liệu, ta yêu cầu một phiên bản
của Fourier biến đổi xử lý đó. Điều này được gọi là biến đổi Fourier rời rạc
(DfL). DFL của một bộ px điểm N (lấy mẫu tại một tần số đó ít nhất bằng với
Nyquist Tỷ lệ lấy mẫu) vào tần số lấy mẫu FP u là:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
1
0
)
2
(1 N
x
xu
N
J
xu eP
N
Fp
Đây là phép biến đổi tương tự rời rạc của Fourier. Tín hiệu liên tục được thay
thế bởi một tập các mẫu:
1
2
0
)
2
(1
N
x
xu
N
J
u eA
N
Fp
Từ đó tổng có thể được đánh giá theo:
n
k
n
k
r
ra
ra
0
1
0
0
1
)1(
Những biến đổi Fourier rời rạc của một xung lấy mẫu được cho bởi:
u
N
J
u
N
N
J
u
e
e
N
A
Fp
2
2
2
1
1
Sắp xếp lại ta có:
)/sin(
)2/sin(
2
1
2
Nu
u
e
N
A
FPu N
u
j
Các modul biến đổi là:
)/sin(
)2/sin(
Nu
u
N
A
FPu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
Khi hàm mũ là 1. Xung ban đầu như H 2.25a và độ lớn của biến đổi Fourier
tần số được đưa ra như H 2.25b
H 2.25 Biến đổi cặp cho xung mẫu
Trong tiến trình này các DFL nghịch đảo. Điều này có thể được sử dụng để tái
tạo lại một phần tín hiệu tần số lấy mẫu từ các thành phần của nó bằng cách:
N
jN
u
eFPuPx
21
0
Có một số giả định được thực hiện trước khi áp dụng DFL. Thứ nhất là các
tiêu chí lấy mẫu được thỏa mãn. Thứ hai là có chức năng lấy mẫu. Khi tọa ra
những biến đổi của một xung Fourier giả định các xung lặp đi lặp lại bên
ngoài. Cuối cùng tần số tối đa tương ứng với một nửa thời gian lấy mẫu. Điều
này là phù hợp với giả định là các tiêu chí lấy mẫu không bị vi phạm.
2.2.3.2 Biến đổi hai chiều.
Biến đổi Fourier hai chiều là biến đổi của các điểm ảnh (lấy mẫu điểm ảnh)
với hai chiều không gian x, y kích thước tần số u,v.
Biến đổi hai chiều Fourier tần số Fp u, v từ N x N điểm ảnh Px,y là:
1
0
))(
2
(1
0
,
1
,
N
y
vy
N
jN
x
yePx
N
vFPu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
Những biến đổi Fourier của một hình ảnh thực sự có thể thu được quang học
bằng cách truyền một laser thông qua một slide ảnh và tạo thành một hình ảnh
bằng cách sử dụng một ống kính. Những biến đổi Fourier của hình ảnh của
slide được hình thành trên mặt phẳng tiêu trước ống kính. Điều này vẫn còn bị
giới hạn cho các hệ thống transmissive trong khi hình thành phản xạ sẽ mở
rộng ứng dụng của nó tiềm năng đáng kể (từ quang học tính toán chỉ là hơi
nhanh hơn so với đối tác kỹ thuật số của nó). Các độ lớn của DFL 2D đến một
hình ảnh của các thanh dọc (Hình 2.26 (a)) là được hiển thị trong (Hình 2.26
(b)). Điều này cho thấy rằng chỉ có ngang tần số không gian; các hình ảnh là
không đổi trong trục thẳng đứng và không có tần số không gian dọc.
Hình 2.26 Áp dụng biến đổi Fourier rời rạc 2D
Hai chiều (2D) nghịch đảo DFL biến đổi từ miền tần số quay trở lại các tên
miền của hình ảnh. Các DFL 2D nghịch đảo được cho bởi:
1
0
))(
2
(1
0
,,
N
v
vy
N
jN
u
vePuvFPu
Các FFT chỉ có thể được áp dụng cho các hình ảnh có kích thước vuông. Tính
toán thực tế liên quan đến việc biến đổi Fourier. Nghĩa là biến đổi Fourier
được tính theo hai giai đoạn: các hàng đầu tiên được chuyển thể sử dụng một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59
FFT 1D, sau đó dữ liệu này được chuyển vào cột, một lần nữa bằng cách sử
dụng một 1D FFT. Quá trình này có thể đạt được kể từ khi các chức năng cơ
sở sinusoidal đang trực giao. Điều này cho rằng DFL 2D có thể bị phân hủy
như sau:
))(
2
(1
0
))(
2
(1
0
1
0
)(
21
0
,
1
,
1 vx
N
jN
y
vy
N
jN
x
N
y
vyux
N
jN
x
eyePx
N
yePx
N
Sắp xếp lại Fourier cho mục đích hiện thị
Sắp xếp lại cho việc biến đổi tính toán
Hiệu ứng đầy đủ của biến đổi Fourier được hiển thị bằng cách áp dụng cho
một hình ảnh của độ phân giải cao hơn nhiều. Hình 2.27 (a) cho thấy hình ảnh
của một khuôn mặt và hình 2.27 (b) cho thấy nó biến đổi. Những biến đổi cho
thấy rằng có rất nhiều thông tin được mang trong những tần số thấp hơn vì
đây là nơi mà hầu hết các thành phần quang phổ tập trung. Điều này là do ảnh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
60
khuôn mặt có nhiều khu vực, nơi độ sáng không thay đổi rất nhiều, như má và
trán. Các thành phần tần số cao phản ánh sự thay đổi trong cường độ. Theo
đó, các thành phần tần số cao phát sinh từ tóc (và lông) và các tính năng của
bộ mặt con người, chẳng hạn như mũi và mắt.
H 2.27a Ảnh mặt H 2.27b Biến đổi ảnh mặt
Hiệu ứng đầy đủ của biến đổi Fourier là như với 1D, có những biến đổi
Fourier 2D cặp, minh hoạ trong Hình 2.28. Các 2D biến đổi Fourier của
một hai chiều xung, hình 2.28 (a), là một hay chiều sinc chức năng,
trong hình 2.28 (b). Các 2D biến đổi Fourier của một hàm Gaussian, trong
hình 2.28 (c), lại là một hai chiều Gaussian chức năng trong lĩnh vực tần số,
trong hình 2.28 (d).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
61
H 2.28 Biến đổi Fourier 2D cặp
2.2.4 Các thuộc tính khác của biến đổi Fourier
2.2.4.1 Dịch chuyển lượng không đổi.
Các phân tích thành tần số không gian không phụ thuộc vào vị trí của
các tính năng bên trong hình ảnh. Nếu ta thay đổi một lượng tính năng cố
định, hoặc thu được hình ảnh từ một vị trí khác nhau, độ lớn của biến đổi
Fourier của nó không thay đổi.
2.2.4.2 Thuộc tính xoay.
Những biến đổi Fourier của một hình ảnh xoay khi xoay hình ảnh gốc.
Điều này được dự kiến kể từ khi phân tích thành tần số không gian phản ánh
sự định hướng của các tính năng trong hình ảnh. Như vậy, định hướng được
xây dựng phụ thuộc vào biến đổi Fourier.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
62
CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM
3.1. Giới thiệu
Trong những năm gần đây, nhiều nhà khoa học quan tâm đến việc ứng
dụng các phép phân tích hình dạng của đối tượng để tìm ra được những đặc
trưng của đối tượng đó, nhằm phục vụ cho quá trình nhận dạng và phân loại
đối tượng. Những lý thuyết và cơ sở toán học về lĩnh vực phân tích hình dạng
đã được phát triển từ thập niên 80 của thế kỷ 20. Từ đó đến nay, nhiều nhà
khoa học đã ứng dụng vào trong lĩnh vực nông nghiệp nhằm phân tích hình
dạng của một số nông sản để phân loại, phát hiện sớm đặc tính giống của
nông sản như quả đậu tương, lá non của cây đậu tương, và nhân lúa mạch.
Những kết quả này đã được ứng dụng phổ biến tại các nước như Nhật Bản,
Hàn Quốc.
Trong luận văn này, em nghiên cứu và cài đặt một số kỹ thuật như phát
hiện biên ảnh nhị phân, biến đổi ảnh, và ứng dụng mã chuỗi (chain code) để
“số hóa” hình dạng biên của đối tượng ảnh.
3.2. Số hóa biên đối tƣợng ảnh
Như chúng ta đã biết việc phát hiện biên, và những thông tin chứa
trong biên của đối tượng ảnh luôn đóng vai trò then chốt trong xử lý ảnh nói
chung, và giai đoạn phân đoạn, nhận dạng, phân loại nói riêng. Chính vì thế,
việc số hóa những thông tin lưu trữ trên biên luôn được nhiều nhà khoa học
quan tâm. Một phương pháp phổ biến để lưu và biểu diễn biên của ảnh là kỹ
thuật mã chuỗi (chain code). Với kỹ thuật mã chuỗi, thay vì chúng ta phải lưu
toàn bộ ảnh để có được thông tin về biên của ảnh, thì ta chỉ cần lưu trữ một
loạt mã chuỗi mô tả vị trí điểm biên của đối tượng ảnh trong ảnh đó. Quá
trình thực hiện số hóa biên của đối tượng ảnh gồm các bước chính sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
63
Bƣớc 1: Biến đổi ảnh sang ảnh đa cấp xám
Bƣớc 2: Phân ngưỡng ảnh
Bƣớc 3: Biến đổi ảnh sang dạng nhị phân
Bƣớc 4: Phát hiện biên
Bƣớc 5: Số hóa biên bằng thuật thoán mã chuỗi
Với 5 bước chính thông tin vị trí của từng điểm biên sẽ được lưu trữ ở
tập tin và tái tạo lại khi cần thiết. Thuật toán số hóa biên của đối tượng ảnh.
Thông tin đầu vào:
- Ảnh *.bmp
Thông tin đầu ra:
- Tập tin chứa mã chuỗi.
Hình 3.1. Thuật toán số hóa biên của đối tượng ảnh
Bắt đầu
Tải ảnh
Biến đổi cấp xám
Phân ngưỡng
Biến đổi nhị phân
Phát hiện biên
Chain code
Kết thúc
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
64
Những quá trình biến đổi ảnh cấp xám, phân ngưỡng, biến đổi sang ảnh
nhị phân (ảnh chỉ có 2 màu trắng và đen) và kỹ thuật phát hiện biên của ảnh
nhị phân đã trình bày ở những phần trên. Dưới đây, tôi tập trung trình bày
thuật toán tính mã chuỗi, CHAINCODEALG() đã được cài đặt trong luận
văn này.
Thuật toán mã chuỗi CHAINCODEALG() gồm những bước chính
như sau:
Bƣớc 1: Xác định vị trí ban đầu P0, STARTPOS()
Bƣớc 2: Lựa chọn kỹ thuật kết nối (4-kết nối, 8-kết nối)
Bƣớc 3: Lưu trữ vị trí biên, STOREDGE()
Bƣớc 4: Xác định điểm kế tiếp bằng thủ tục NEXTPOS()
Bƣớc 5: Kiểm tra điểm đầu CHECKSTARTPOI(), nếu trả về giá trị
False thì quay về bước 3, ngược lại thì thuật toán kết thúc
Hình 3.2. Thuật toán CHAINCODEALG()
Bắt đầu
Tải ảnh, P0, 4-kết
nối; 8-kết nối
STOREDGE
NEXTPOS
Kết thúc
CHECKSTARPOI
False
True
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
65
Tiếp theo, tôi trình bày đoạn chương trình thuật toán CHAINCODEALG()
CHAINCODEALG(BYTE *lpDIBBytes, DWORD StartPos, DWORD
height, DWORD width)
{
DWORD i,j,k,vt,vtx,vty;
BYTE mau;
// Quet trong toan bo anh
for(i=0;i< height;i++)
for(j=0;j<width;j++)
{
Position(i,j, width, height, vt);
//Tim vi tri diem dau
if(vt==StartPos)
{
vtx=j;
vty=i;
for(k=0;k<=height*width;k++)
{
STOREDGE (vt);
vt=NEXTPOS (vt);
if(CHECKSTARPOI(vtx,vty,vt)==true)
{
return 1;
}
}
}
}
}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
66
3.3 Chƣơng trình thử nghiệm.
Trong chương trình em xin trình bày ứng dụng phát hiện biên, Elliptic
Fourier trong việc trích rút đặc tính hình dạng của lá gấc.
Để trích rút đặc tính hình dạng của lá gấc có nghĩa là ta thực hiện biến
đổi hình dạng lá gấc từ màu RGB sang dạng Gray Scale Histogram.
Thực hiện việc đưa ảnh vào chương trình:
Ta có ảnh lá gấc ban đầu như sau:
Hình 3.3 Lá gấc ban đầu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
67
Sau khi load image chọn Gray Scale và make Histogram
ta được ảnh lá gấc sau khi histogram trong hình 3.4
Hình 3.4 Lá gấc sau khi được Histogram
Sau khi Histogram ta thực hiện việc chain code cho lá gấc như sau:
Hình 3.5 Lá gấc sau khi được chain code
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
68
Thực hiện chain code với các lá gấc khác ta được kết quả:
Từ kết quả thử nghiệm ta thấy kết quả của lá gấc trước khi được xử lý
và sau khi được xử lý được mô tả trong hình 3.6
Hình 3.6(a). Lá gấc trước khi xử lý (b) Sau khi được xử lý
So sánh lá gấc trước và sau khi xử lý chain code ta thấy trong hình
3.6(a) những điểm được khoanh đỏ sẽ bị mất đi. Lá gấc sau khi chain code
hình 3.6(b). Như vậy chương trình đã thưc hiện việc chain code cho những
điểm biên đã được xác định.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
69
Kết quả thực nghiệm cho thấy việc nghiên cứu và tìm hiểu về biên ảnh,
Elliptic Fourier là một hướng phát triển để từ đó có những nghiên cứu tiếp
theo trong việc hỗ trợ phân loại sớm đặc tính giống của cây Gấc ở nước ta.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
70
PHẦN KẾT LUẬN
Trong lĩnh vực xử lý ảnh, quá trình phát hiện biên của những đối tượng
ảnh là một giai đoạn rất quan trọng bởi độ chính xác của quá trình nhận diện,
lấy đặc tính hình dạng và phân đoạn ảnh chủ yếu dựa vào giai đoạn này.
Chính vì vậy, bài toán phát hiện biên luôn được quan tâm và không ngừng
được phát triển.
Các đặc tính hình học chứa những thông tin về vị trí, kích thước hình
học, hình dạng của các đối tượng trong ảnh, là đặc tính rất quan trọng trong
xử lý nhận dạng ảnh. Các đặc tính này thường được trích rút ra thông qua việc
xác định các đường biên các đối tượng trong ảnh. Biên chứa các thông tin về
hình dạng ngoài của đối tượng ảnh. Có thể nói xác định biên là một trong
những vấn đề quan trọng và hấp dẫn trong lĩnh vực nghiên cứu xử lý ảnh bởi
khả năng biểu đạt cấu trúc đối tượng và tính ứng dụng rộng rãi của nó vào
việc giải quyết nhiều bài toán như: nhận dạng tự động, thị thực máy tính,
hoạt hình…
Bên cạnh đó, việc kết hợp phương pháp phát hiện biên với phương pháp
khác nhằm hỗ trợ cho công tác phát hiện sớm một số đặc tính của cây trồng
dựa theo hình dạng của lá, hay củ đã và đang được nhiều nhóm khoa học
trong và ngoài nước quan tâm.
Trong luận văn thạc sỹ với đề tài “Phát hiện biên, biểu diễn Forier
Elliptic và ứng dụng” em đã tập trung nghiên cứu một số phương pháp phát
hiện biên, kỹ thuật biến đổi ảnh và phép biểu diễn Fourier Elliptic ứng dụng
trong việc trích rút đặc trưng hình dạng lá của cây Gấc. Kết quả của luận văn
sẽ làm tiền đề cho nghiên cứu sau này trong việc hỗ trợ phân loại sớm đặc
tính giống của cây Gấc ở nước ta.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
71
Do trình độ và thời gian có hạn, chắc chắn luận văn còn nhiều thiếu sót.
Vì vậy, rất mong nhận được sự góp ý quý báu của các thầy giáo, cô giáo và sự
cộng tác của các bạn đồng nghiệp để nội dung luận văn được hoàn thiện hơn.
Cuối cùng một lần nữa em xin chân thành bày tỏ lòng biết ơn sâu sắc
đến thầy hướng dẫn TS. Phạm Việt Bình đã giúp đỡ em hoàn thành
luận văn này.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
72
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Lƣơng Mạnh Bá, Nguyễn Thanh Thủy. Nhập môn xử lý ảnh số.
Nhà xuất bản khoa học và kỹ thuật. Hà Nội, 1999.
[2] Phạm Việt Bình. Luận văn tiến sĩ. Phát triển kỹ thuật dò biên, phát
hiện biên và ứng dụng, 2006
[3] Đặng Văn Đức. Bài giảng Hệ quản trị cơ sở dữ liệu đa phương tiện.
Hà Nội, 2005.
[4] Ngô Quốc Tạo. Bài giảng Xử lý ảnh. Hà Nội, 2005.
[5] Nguyễn Kim Sách. Xử lý ảnh và video số. NXB Khoa học và Kỹ
thuật. Hà Nội, 1997.
[6]
[7]
[8]
Tiếng Anh
[9] Chan Yuk Ming. Shape-based Image Retrieval In Iconic Image
Databasesz. The Chinese University of HongKong, 6-1999.
[10] Dan Fergus and Larry Roof. The Definitive Guide to the .NET
Compact Framework. 2003.
[11] Dan Fox, Jon Box. Building Solutions with the Microsoft .NET
Compact Framework: Architecture and Best Practices for Mobile
Development. Addison Wesley, 2003.
[12] David Fox, Roman Verhosek. Micro Java™ Game Development.
Addison Wesley, 2002.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
73
[13] Dengsheng Zhang. Image Retrieval Based on Shape. Monash
University, 4-2002.
[14] Erik Rubin, Ronnie Yates. Microsoft® .NET Compact Framework
Kick Start. Sams Publishing, 2003.
[15] John C. Russ. The Image Processing Handbook, Second Edition.
CRC Press, 1995.
[16] John Wiley & Sons. Image Processing Principles and Applications.
Wiley-Interscience, 2005.
[17] Parker J. R. Practical Computer Vision Using C. John wiley &
Sons, Inc, 1993.
[18] Remco C. Veltkamp, Michiel Hagedoorn. State-of-the-Art in Shape
Matching. Utrecht University, Netherlands. 1999.
[19] Shuang Fan. Shape Representation and Retrieval Using Distance
Histograms. In Technical Report TR 01-14, Deparment of Computing
Science, University of Alberta, Canada, October 17, 2001.
[20] Tinku Acharya, Ajoy K. Ray. Image Processing Principles and
Applications. A John Wiley & Sons, Inc.
[21] Y. Alp Aslandogan, Clement T. Yu. Techniques and Systems for
Image and Video Retrieval. Departments of EECS, University of Illinois,
Chicago. 1999.
[22]
[23]
[24]
[25]
[26]
b40f-9abc80388620/course-2556-module-1.pdf
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
74
[27]
[28]
[29]
minkowskidistance.html
[30]
doc/default.aspx
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
0
1H1 =
-1
0
Các file đính kèm theo tài liệu này:
- 2LV_09_CNTT_KHMT_PHAM NGOC QUY.pdf