LỜI NÓI ĐẦU
Ngày nay khoa học nhận dạng có một vai trò vô cùng quan trọng bởi
các ứng dụng to lớn của nó trong nhiều lĩnh vực khoa học.Thining (làm mảnh)
là một bước tiền xử lý nhằm phục vụ cho những bước tiếp theo trong quá trình
nhận dạng. Đồ án này giới thiệu các khái niệm, cách phân loại, và một số thuật
toán làm mảnh, những đánh giá cho từng loại thuật toán. Cấu trúc của đồ án
gồm 4 chương bao gồm 3 chương lý thuyết và 1 chương về cài đặt thực
nghiệm.
Chương 1: Tổng quan về làm mảnh ảnh.
Chương 2: Các thuật toán làm mảnh tuần tự.
Chương 3: Các thuật toán làm mảnh song song.
Chương 4: Cài đặt thực nghiệm.
55 trang |
Chia sẻ: banmai | Lượt xem: 2651 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Đồ án Tìm hiểu phương pháp làm mảnh, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
điểm ảnh, các điểm ảnh được qui cho xương dựa trên tiêu chuẩn
liên thông. Do đó, các điểm ảnh này được giữ lại trong quá trình làm mảnh.
1.4. Các tính chất và yêu cầu đối với làm mảnh
Phần này giới thiệu về các yêu cầu, tính chất đối với một thuật toán làm
mảnh và khả năng đáp ứng của từng loại thuật toán.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
12
Các tính chất bao gồm việc duy trì được những thuộc tính tô pô và các
tính chất hình học, tính đẳng hướng, tính bất biến, khả năng tái tạo,không mất
tính liên thông , không tạo ra lỗ hổng , không mất điểm cuối và tốc độ xử lý
cao.
1.4.1 Yêu cầu về thời gian và số phép toán
Các phương thức làm mảnh không lặp, không phụ thuộc vào điểm ảnh
có hiệu quả trong việc giảm số các phép toán cần thiết, chúng giữ lại được tốt
hơn những nét đặc trưng chi tiết của mẫu. Nhìn chung, các thuật toán làm
mảnh song song đã làm tăng tốc độ xử lý, đặc biệt khi mà các cấu trúc xử lý
ảnh song song đang ngày càng tăng. Đây là một bước tiến quan trọng trong
lĩnh vực làm mảnh.
1.4.2 Yêu cầu về khả năng tái tạo mẫu ban đầu
Khả năng tái tạo, hay còn gọi là khả năng phục hồi lại mẫu ban đầu từ
một xương, là một thước đo khách quan về độ chính xác đối với mỗi một mẫu
xương. Những điều kiện này, nhìn chung, phù hợp với những thuật toán dựa
trên trục trung vị.
1.4.3 Yêu cầu về tính đẳng hướng và tính bất biến
Đa số các thuật toán lặp đều đảm bảo tính đẳng hướng hoặc tính bất
biến dưới một phép quay. Trong các thuật toán tuần tự, kết quả thu được dựa
trên thứ tự của các điểm ảnh được kiểm tra, còn trên các thuật toán song song
xoá đi một hay hai kiểu điểm biên trên mỗi vòng lặp con, thì xương thu được
phụ thuộc vào thứ tự của các vòng lặp con này. Trong khi đó thì việc thay đổi
trục trung vị không bất biến dưới một phép quay bởi vì tính không đầy đủ của
các thuật toán.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
13
1.4.4 Yêu cầu tính liên thông và tính Tô pô
Việc duy trì tính liên thông và tính chất Tô pô khi làm mảnh cũng đã
được giải quyết bằng những cách khác nhau. Trong các thuật toán tuần tự,
kiểm tra một vùng 3 × 3 láng giềng dưới dạng số giao. Các thuật toán song
song giải quyết vấn đề này bằng cách chia mỗi chu trình ra thành nhiều vòng
lặp con hoặc bằng cách giữ một vùng láng giềng rộng hơn trên một vòng lặp
con.
1.4.5 Yêu cầu về tính hình học
Đảm bảo những thuộc tính hình học, là vấn đề gặp nhiều khó khăn
nhất. Khó khăn chính là việc đạt được tính đơn giản của thuật toán, nó cho
phép giữ lại một vùng nhỏ các láng giềng, nhưng các láng giềng này lại không
thể đáp ứng được cho tổng thể, các thông tin có cấu trúc loại này lại cần thiết
để phân biệt giữa điểm cuối giả và các điểm cuối thực. Để tránh sự xói mòn
quá mức và việc tạo ra các điểm cuối giả tạo cùng một lúc, chúng ta phải có
những cách khác nhau nhằm loại trừ điều kiện điểm cuối, tạo ra những điều
kiện tổng quát và thích hợp hơn, hoặc chỉ áp dụng điều kiện trên các giai đoạn
trước làm mảnh.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
14
CHƯƠNG 2
CÁC THUẬT TOÁN LÀM MẢNH TUẦN TỰ
Khi sử dụng các thuật toán làm mảnh tuần tự, các điểm biên được kiểm
tra để xoá đi theo một thứ tự định trước, điều này có thể được hoàn thành bằng
cách dò theo loạt hoặc theo biên.
2.1. Làm mảnh theo các điểm biên
Các thuật toán dò biên có thể xét đến tất cả các điểm ảnh biên của một
đối tượng đơn liên thông (Rosenfeld [6]), hay một đa liên thông, nếu tất cả các
biên của ảnh và các lỗ hổng được kế tiếp nhau. Các đường biên được theo vết
sử dụng chuỗi mã hóa kiểu Freeman [7].
Khi một điểm ảnh p được kiểm tra, nó sẽ được xoá đi hay giữ lại tuỳ
theo cấu trúc của N(p). Để ngăn chặn việc xoá đi một cách tuần tự cả một
nhánh trên một vòng lặp, một thuật toán tuần tự thường đánh dấu các điểm
ảnh sẽ được xoá đi, và tất cả các điểm ảnh đánh dấu được xoá ở cuối vòng lặp.
Điều này đảm bảo rằng chỉ có một lớp các điểm ảnh sẽ được xoá đi trên mỗi
chu trình.
Để tránh phải nhắc lại, chúng ta giả sử rằng một điểm p được xoá đi
nếu tất cả các điều kiện sau đây được thoả mãn:
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
15
1. p là một điểm ảnh đen.
2. p không phải là một điểm bị cô lập hoặc điểm cuối, b(p) ≥ 2.
3. p là một điểm ảnh đường biên, p có ít nhất một trong 4_láng giềng
là trắng.
2.1.1. Thuật toán của Chu và Suen
Trong thuật toán này việc làm trơn được thực hiện trước mỗi vòng lặp.
Trên mỗi vòng lặp các điểm biên thoả mãn các điều kiện của thuật toán được
đánh dấu xoá với điều kiện điểm cuối. Khi không còn điểm ảnh nào có thể xoá
được nữa, một giai đoạn chỉnh lý cuối cùng được đưa ra mà trên đó các điểm
ảnh xương sẽ được chuyển cho một trong 4_láng giềng của nó nếu điểm ảnh
sau cùng có khoảng cách lớn hơn 8 kể từ nền. Trong quá trình xử lý, tính liên
thông của xương được đảm bảo trong khi các điểm xương được di chuyển dần
tới đường trung vị của mẫu gốc.
2.1.2. Thuật toán của Arcelli
Số giao Rutovitz XR(p) được sử dụng để xác định việc xoá các điểm
ảnh. Trên các thuật toán này, một định nghĩa khác của điểm biên được sử
dụng: ở đây, một điểm biên đen có ít nhất một 8_láng giềng là trắng. Điều
kiện này cùng với việc sử dụng XR(p) đòi hỏi một điều kiện bổ sung (F = x1 x3
x5 x7 = 0) để đảm bảo rằng không tạo ra các lỗ hổng khi các điểm đường biên
được xoá đi. Bổ sung các điều kiện cho khả năng xoá p nhưng vẫn đảm bảo
tính liên thông được đưa ra trong thuật toán này như sau:
1. Nếu XR(p) = 0 hoặc 8 thì p không thể xoá được.
2. Nếu XR(p) = 2 thì p được xoá đi nếu F = 0 và p không phải là
một điểm cuối.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
16
3. Nếu XR(p) = 4 thì p được xoá đi nếu và chỉ nếu F = 0 và một
trong 4 điểm ảnh góc là 0 với 1 trên cả hai phía. Điều kiện
cuối tương đương với
i=
∑
1
4
x2i - 1 x 2ix2i + 1 = 1
4. Nếu XR(p) = 6 thì p được xoá đi nếu và chỉ nếu một trong
4_láng giềng của nó là 0 và ba láng giềng khác là 1 thuộc về
từng 4_thành phần,
hoặc
i=
∑
1
4
x2i - 1 = 3.
Tuy nhiên, sử dụng các điều kiện trên bản thân chúng sẽ tạo các điểm
cuối giả và các góc ăn mòn.
Khi thu được một bộ S f với một lõi rỗng, mỗi điểm ảnh p được giữ lại
trên S f được gán cho một nhãn :
e(p) = 2(x5 + x3) + x1 + x7 + 1
Các điểm ảnh không lớn nhất dưới nhãn này được xoá đi, kết quả thu
được, đa số, là xương có độ dày 2 điểm ảnh.
Xương thu được theo cách này có thể bị ảnh hưởng mạnh tại điểm cuối
cùng một nhánh bởi hình dạng của một khối lồi ra trên một mặt.
2.1.3. Thuật toán của Pavlidis
Trong thuật toán này, đặc điểm của các điểm bội được định nghĩa lại
trên giới hạn của các vùng láng giềng, và do đó có thể xác định được trên tuần
tự hay song song thông qua việc so sánh các bộ mặt nạ với nhau. Đòi hỏi vùng
láng giềng phải có dạng như Hình 3 và các dạng quay 900 của nó đối với các
điểm bội.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
17
Định nghĩa các điểm bội cũng được thay đổi đôi chút. Người ta cũng đề
xuất một sự phối hợp giữa tuần tự và song song rất có thể có hiệu quả hơn đối
với những ảnh mà trên đó đa số các điểm ảnh không đòi hỏi phải được xử lý.
Đối với những ảnh như vậy, mẫu có thể được chia ra thành các phần và ấn
định cho từng bộ điều khiển. Mỗi một điều khiển hoạt động trên các điểm ảnh
trong phần của nó một cách lần lượt, và khi các bước đã hoàn thành, nó đợi
đến khi tất cả các bộ điều khiển khác hoàn thành trên cùng bước như vậy để
cho các bộ điều khiển có thể được tiến hành đồng thời.
Thuật toán này chủ yếu đảm bảo tính liên thông của xương bằng cách
phát hiện và gán các điểm bội M cho xương S rồi tìm và gán cho S các điểm
ảnh thích hợp để liên kết M với bên trong của P. Vì điều này có thể thu được
các xương có độ dày không thích hợp khi P không đảm bảo rằng làm mảnh
được đa số, do đó phải đan xen xoá đi được các điểm không bội từ biên C và
giữ lại phần S. Đồng thời, biên được sử dụng để xác định xem một điểm có
phải biên sẽ phải :
a) coi như nhiễu và không được ghi nhãn là bội, hoặc
b) được quan tâm đến độ lồi và ấn định cho S là chẵn dù nó là không đa. Điều
này được hoàn thiện bởi việc tính toán n mã của các điểm biên từ mã xích
Freeman nhận được trong dò biên. Mã ci của điểm ảnh pi là khác với mã xích
pi , và với n > 1, mã n
c in = nci +
k
n
=
−∑
1
1
(n-k)(ci - k + ci + k)
xác định độ cong của đường biên tại pi. Giá trị của ci được sử dụng để xác
định a), và nếu c in vượt quá ngưỡng thì pi được gán cho S để nó có thể biểu
diễn độ lồi có nghĩa. Một cách tự nhiên, nếu như ngưỡng có giá trị nhỏ hơn,
thì thuật toán này sẽ nhạy cảm với những chỗ đường biên lồi ra.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
18
Khái niệm điểm bội được phát triển theo một quan điểm khác, nó được
xem như là đối lập với những đường cong đơn giản. Trong mặt phảng liên tục,
một đường cong (kín) được gọi là đơn giản nếu và chỉ nếu nó không bao giờ
cắt chính nó; bởi thế đường cong đơn giản chia mặt phẳng thành hai phần liên
thông gọi là bên trong và bên ngoài. Điều này cũng được mở rộng trên đường
biên C của một mẫu số P cho một mẫu đơn liên thông và cho một mẫu đa liên
thông. Đặc biệt C được coi là đơn giản, qui định rằng nó không chạm hay gối
lên chính nó, và một khái niệm tổng thể được tìm ra tương đương với những
điều kiện địa phương. Nếu chúng ta coi P - C là bên trong của C và P là bên
ngoài của C, thì C là đơn giản, qui ước rằng mọi điểm p trong C đều phải thoả
mãn các điều kiện sau:
A1: N(p) ∩ C gồm có một thành viên (8_liên thông) nằm trong và một
thành viên (4_liên thông) nằm ngoài.
A2: N(p) ∩ C có chứa ít nhất hai điểm ảnh theo chiều ngang hay theo
chiều dọc: một thuộc bên trong, một thuộc bên ngoài.
Các điểm ảnh thoả mãn các điều kiện A1 và A2 được gọi là điểm ảnh
thường, còn những cái không phải là thường thì đồng nghĩa với điểm bội trên
các đường biên cánh cung khác trùng hay kề nhau. Xa hơn nữa, do A1 phải
tính toán phức tạp nên tương đương với A1, A2 ta có, các điểm ảnh p là bội
nếu nó thoả mãn ít nhất một trong các điều kiện sau:
A3: Các điểm ảnh p hoặc dọc hoặc ngang thì cứ một thuộc P - C một
thuộc P - C .
A4: N(p) có 3 điểm liên tiếp ở giữa mà một là láng giềng chéo và thuộc
vào C, hai điểm còn lại thuộc vào P .
Các điều kiện A3 và A4 có những thuận lợi của các điều kiện địa
phương mà được kiểm tra rất dễ dàng một khi các điểm biên được định vị.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
19
Bằng cách kiểm tra các điểm bội trên sự biến đổi 4_khoảng cách của P, mỗi
đường biên kế tiếp được xác định bởi nhãn của nó trên biến đổi khoảng cách,
do đó làm mảnh có thể được hoàn thành trên một loạt. Trong suốt quá trình
kiểm tra này, các láng giềng của một điểm ảnh đã bị xoá đã được kiểm tra rồi
nhưng vẫn phải kiểm tra lần nữa để xác minh xem chúng có bị trở thành điểm
ảnh bội do việc bắt buộc phải giữ tính liên thông không. Xương bao gồm tất
cả các điểm bội đã bị xoá, và nó có thể giảm độ dày đơn vị.
2.1.4. Thuật toán của Kwok
Các thuật toán được nói ở trên thường dựa trên việc kiểm tra các điểm
biên để xoá đi hay giữ lại. Một phương thức cài đặt khác để thu được xương là
từ việc tạo sinh biên hoặc tạo sinh lặp một đường biên mới tồn tại bên trong
cho đến khi chỉ còn lại xương . Quá trình này được dựa trên hướng của các
điểm biên. Khi các điểm biên được dò theo một thứ tự, ba điểm liên tiếp sẽ tạo
nên một góc θ với đỉnh là điểm p hiện thời. Các điểm trong của N(p) gần nhất
với phân giác của góc θ được coi như một điểm trên đường biên tiếp theo, và
p được xoá đi. Khi thủ tục này lặp lại cho đến lúc không còn các điểm ảnh bên
trong xoá được, thì các đường biên còn lại tạo thành bởi một xương giả.
Phương thức đơn giản này được lọc kỹ càng và mở rộng bằng cách sử
dụng mã xích Freeman của các điểm biên sinh ra các đường biên mới. Mã
xích này được sử dụng, cùng với việc xét các điểm ngắt và các điểm cuối, để
nhận được tập các qui tắc để sinh ra các chu tuyến mới. Khi các điểm biên
mới được xác định, thì mã xích cũng được tạo sinh. Thuật toán này cũng được
cài đặt trên môi trường phân tán bằng cách gán các tập con không gối lên nhau
của mẫu cho các bộ điều khiển khác nhau để làm mảnh sau đó đồng bộ hoá
thông tin của các biên khi kết thúc mỗi vòng lặp. Trong một số sản phẩm gần
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
20
đây, một điểm biên được xoá đi nếu tất cả 4_láng giềng của nó trên mặt
“trong” đều là đen, trong trường hợp này, chuỗi các mã xích tương ứng với
các đoạn của đường biên mới thu được từ một bộ các điều kiện tiền định nghĩa
có liên quan đến độ cong địa phương.
2.2. Làm mảnh theo loạt
O’ Gorman đưa ra tiêu chuẩn làm mảnh mở rộng các cửa sổ thành kích
thước k×k (k > 3), ở đây tâm của các điểm ảnh (k-2) × (k-2) có thể bị xoá đi
cùng nhau nếu như các điểm ảnh biên trên của sổ có số giao Hilditch là 1 và
nếu chúng chứa nhiều hơn (k - 2) các điểm ảnh trắng 4_liên thông và nhiều
hơn (k - 2) các điểm ảnh đen. Đối với tất cả các điểm ảnh đen, cửa sổ k × k
của nó được kiểm tra theo thứ tự k giảm cho đến khi k < 3 hoặc xoá đi điểm
trung tâm. Với các giá trị lớn hơn của k, các lớp điểm ảnh dày hơn có thể được
xoá đi trên một vòng lặp, do đó, để thu được xương của các mẫu dày thì chỉ
cần số vòng lặp ít hơn. Tuy nhiên, việc tăng tốc độ này phải đổi lại kết quả
thu được xương thô hơn (xương có nhiễu). Khi làm mảnh các mẫu lớn hơn,
việc sử dụng một số k lớn hơn có thể làm ảnh hưởng không tốt đến tốc độ xử
lý.
2.2.1. Thuật toán làm mảnh của Yakei
Trong thuật toán này, mọi điểm ảnh đen được kiểm tra và gán theo qui
tắc:
L(p) = 2 nếu x3 = 0 hoặc x 3 + x 5 + x7 = 0
L(p) = 3 nếu x 3 + x 5 = 0 hoặc x 3 + x 5 + x 7 + x1 = 0
Hai loạt ngược chiều nhau được thực hiện để xoá đi các điểm ảnh được
đánh dấu 2 và 3, một cách tương ứng, các điểm ảnh được cung cấp không phải
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
21
là các điểm cuối và có số liên thông bằng 1 (ở đây 4_liên thông hoặc 8_liên
thông đều có thể được dùng). Mặc dù thuật toán này đơn giản và cho xương
liên thông, nhưng các đường dọc có độ dày là một số chẵn các điểm ảnh có thể
bị loại bỏ hoàn toàn.
2.2.2. Thuật toán làm mảnh SPTA
SPTA [1] là một thuật toán tuần tự sử dụng hai loạt trên một chu trình,
đầu tiên là từ trái qua phải, và rồi từ trên xuống dưới. Trên mỗi bước quét, p
được đánh dấu để giữ lại (p là một điểm an toàn “safe point”) nếu như một
trong các điều kiện sau là đúng:
N1: N(p) thoả mãn một trong hai cửa sổ như Hình 4 hoặc các dạng quay
của nó.
N2: N(p) chứa đúng hai điểm kề 4 là đen.
Các điều kiện này là tương đương với một điểm đường biên phía tây an
toàn p nếu có biểu thức lôgic sau:
x1(x2 + x3 + x7 + x8)(x3 + x 4)(x7 + x 6) = 0
Trên bước quét đầu tiên, các điểm đường biên phía tây được đánh dấu,
sau đó là đến các điểm đường biên phía đông mà không phải là các điểm an
toàn phía tây, và lặp lại quá trình này. Điều kiện N2 có tác dụng ngăn chặn sự
xói mòn quá mức của các đường chéo có độ dày 2 điểm ảnh, nhưng nó có thể
dẫn đến các nhánh nhiễu. Beffert và Shinghal [1] đã đề xuất một sự thay đổi
đối với SPTA nhằm loại (trong đa số trường hợp) vòng kiểm tra cuối cùng
khi không còn điểm ảnh nào có thể xoá được nữa, và sự thay đổi của thuật
toán này được thực hiện trên một bộ đa xử lý sử dụng các phương pháp của
hàm (a) và phân tích dữ liệu (b). Trong (a), mỗi bộ xử lý thực hiện một bước
quét, và mỗi dòng hoàn chỉnh được xoá đi bởi bộ xử lý thực hiện bước quét
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
22
tiếp theo, mặt khác trên (b) mỗi bộ xử lý quét một phần của ảnh với các đường
biên gối lên nhau.
(b)
(a) (b)
Hình 4 Cấu hình các điểm ngắt, ít nhất một điểm ảnh trên mỗi nhóm được
đánh dấu x hoặc y phải khác không
(a) (b) (c)
Hình5 : Cấu hình của điểm bội p. Mỗi một nhóm của các điểm ảnh
được đánh dấu x hoặc y phải có ít nhất một thành viên nonzero. Trên (c), có
ít nhất một điểm ảnh có đánh dấu z phải là nonzero; nếu chúng đều là nonzero
thì các điểm ảnh x, y nhận giá trị bất kỳ đều được; điểm ảnh d là một điểm
ảnh đường biên.
2.3. NHẬN XÉT
x x x
0 1 x
1 0 x
x x x
0 1 0
y y y
x x x
0 1 0
y y y
x x x
0 1 x
1 0 x
x x z
0 1 d
y y z
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
23
Nhìn chung, khi các điểm ảnh của P được xử lý một cách tuần tự, sẽ
không có vấn đề gì trong việc đảm bảo tính liên thông của P và P khi các điều
khiển tương thích với vùng 3 × 3 được sử dụng. Do đó trong các thuật toán
này cần phải đảm bảo tính tô pô. Tuy nhiên nó cũng đòi hỏi nhiều hơn các
thông tin tổng thể để giữ lại những đặc trưng hình học có ý nghĩa đối với khối
hình số của P. Với mục đích này, xương thu được từ một loạt của P ít khi là có
ý nghĩa, trái lại thuật toán dựa trên việc dò biên tuần tự lại có thể dẫn đến các
kết quả tốt hơn. Phương pháp của Kwork cho phép sự tương quan giữa dạng
của xương và những đường biên bên ngoài của mẫu mà thường là không thể
đạt được chỉ với các điều khiển địa phương. Tất nhiên, việc xét tổng thể hơn
này sẽ tăng thời gian tính toán và các thủ tục phức tạp hơn, và phần lớn độ
phức tạp của các thuật toán làm mảnh tuần tự [2] là kết quả của việc cố gắng
giữ lại nhiều đặc trưng hình học hơn.
CHƯƠNG 3
CÁC THUẬT TOÁN LÀM MẢNH SONG SONG
Trong làm mảnh song song, các điểm ảnh được kiểm tra để xoá dựa trên
kết quả của vòng lặp trước đó. Vì nguyên nhân này, các thuật toán làm mảnh
song song phù hợp để cài đặt trên các bộ xử lý song song, các điểm ảnh phải
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
24
thoả mãn tập các điều kiện để có thể được xoá đồng thời. Nhưng đáng tiếc là
các thuật toán hoàn toàn song song khó có thể giữ được sự liên thông đối với
một ảnh chỉ cho phép tác động lên khối 3 x 3 các điểm ảnh lân cận. Ví dụ, một
hình chữ nhật với độ dầy 2 điểm ảnh rất có thể bị xoá trong một quá trình làm
mảnh song song. Do đó cách thông thường là sử dụng các láng giềng 3 x 3
nhưng phải chia mỗi vòng lặp ra thành các vòng lặp con hoặc các chu trình
con trên đó chỉ có một tập con các điểm biên được xét để xoá. Kết thúc mỗi
vòng lặp con, ảnh được thay đổi để chuẩn bị cho bước tiếp theo. Tùy theo số
chu trình con mà các thuật toán làm mảnh song song được chia ra thành các
kiểu như sau:
• Các thuật toán sử dụng 4_chu trình con, trên mỗi chu trình con có một
kiểu của điểm biên (Đông, Tây, Nam, Bắc) được xoá đi.
• Các thuật toán sử dụng 2_chu trình con, ví dụ, một chu trình xoá theo
hướng Bắc rồi đến hướng Nam, một chu trình khác xoá trên các hướng
còn lại.
• Các thuật toán chỉ sử dụng 1_chu trình con, nhưng nó luôn phải thoả
mãn một tập hợp có thứ tự các điều kiện để đảm bảo sự liên thông.
3.1. Làm mảnh song song sử dụng 1 chu trình con
3.1.1 Thuật toán Rutovitz
Đây là một thuật toán song song cơ bản, một điểm ảnh p được xoá đi
nếu tất cả các điều kiện sau đều được thoả mãn:
R1: b(p)>=2
R2: Xr(p)=2
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
25
R3: x1.x3.x5 = 0 hoặc XR (x3) ≠ 0
R4: x7.x1.x3 = 0 hoặc XR (x1) ≠ 0
Thuật toán này còn có thêm một điều kiện phụ b(p) ≤ 6 đảm bảo p có
4_láng giềng là trắng, do đó việc xoá p không tạo ra lỗ hổng.
Đây là một thuật toán 1_vòng lặp con sử dụng các thông tin từ một cửa
sổ 4 x 4, và nó cho ta các xương liên thông mà không nhạy cảm đối với nhiễu
biên, nhưng lại có tạo ra xói mòn quá mức.
Từ 4_thành phần rời nhau có thể là 8_liên thông, việc xoá đi các điểm p
thoả mãn các điều kiện trên không giảm độ rộng đơn vị điểm ảnh của các
đường chéo. Các điều kiện được thêm vào nhằm giải quyết vấn đề này, và cho
phép xoá điểm p với XR(p) = 4 khi p nằm trên một đường chéo có độ rộng 2
điểm ảnh, nhưng vẫn đảm bảo được tính liên thông. Do tính không đối xứng
tự nhiên của các điều kiện R3 và R4 nên xương thu được không nằm vào
trung tâm. Do đó, sau phép quay 1800 các qui tắc này ta thu được tập đầy đủ
các điều kiện cho phép xoá điểm p:
D1: XR (p) = 0, 2 hoặc 4
D2: b(p) ≠ 1
D3: x1.x3.x5 = 0
D4: x1.x3.x7 = 0
D5: Nếu XR(p) = 4 thì thêm vào một trong 2 điều kiện a) hoặc b)
a) x1.x7 = 1, x2 + x6 ≠ 0, và x3 + x4 + x5 + x8 = 0
b) x1.x3 = 1, x4 + x8 ≠ 0, và x2 +x5 + x6 + x7 = 0
D6-D8 nhận được từ do việc quay D3-D5 1800.
Người ta cũng đã đề nghị rằng nên sử dụng 2 vòng lặp con cho thuật
toán này, vòng thứ nhất xoá những điểm ảnh thoả mãn các điều kiện D1-D5,
vòng lặp thứ hai xóa những điểm ảnh phù hợp với D1,D2 và D6-D8. Tất
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
26
nhiên, thuật toán này xoá đi những điểm ảnh đã bị cô lập. Độ phức tạp của các
điều kiện D1-D5 dẫn đến một điều rằng nếu 2 sự phối hợp 4_láng giềng của p
là 1, thì giá trị của điểm ảnh p nằm chính giữa góc nối sẽ không có hiệu lực
đối với việc p sẽ bị xoá hay không, vì vậy p chỉ được quan tâm đến với giá trị
1. Trong các trường hợp này, p có thể bị xoá đi nếu như sự thay đổi số giao
của nó là 2 với điều kiện là b(p) > 1. Cũng cần phải chú ý rằng sự thay đổi này
của số giao nhau là xử lý cắt góc, bởi vậy số kết quả thực sự thu gấp 2 lần XH
(p), và tất nhiên nó đo sự 8_liên thông chứ không phải 4_liên thông.
3.1.2.Thuật toán của Holt
Holt đưa ra biểu thức logic cho sự tồn tại của một điểm ảnh như sau :
v(C) ^ (~edge(C) ∨
(edge(E) ^ v(N) ^ v(S)) ∨
(edge(S) ^ v(W) ^ v(E)) ∨
(edge(E) ^ edge(SE) ^ edge(S))
Trong đó ~ biểu diễn cho phủ định (NOT).Hàm v trả về giá trị của điểm
ảnh ( 1 =true cho điểm ảnh của đối tượng , 0 =false cho điểm ảnh nền) . Hàm
edge(i) trả về giá trị true nếu i là điểm biên của đối tượng. Các kí tự E, SE, S,
SW, W, NW, N biểu diễn cho 8_láng giềng , kí tự C biểu diễn cho điểm trung
tâm như hình 6a.
NW N NE
W C E
SW S SE
Hình 6a cửa sổ 3x3 các điểm ảnh
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
27
Đôi khi quá trình làm mảnh hoàn thành , vẫn còn có những điểm ảnh có
thể xoá được. Chủ yếu là dạng cầu thang gác , gần như một nửa số điểm ảnh
trong một cầu thang gác có thể xoá được mà không làm ảnh hưởng hình dạng
cũng như tính liên thông của mẫu.
Hình 6b cho thấy những ví dụ về cầu thang gác mà trong mỗi cửa sổ
điểm trung tâm có thể bị xoá. 1 biểu diễn cho điểm ảnh của đối tượng , 0 biểu
diễn điểm ảnh nền , x không quan tâm đến giá trị .
Hình 6b cửa sổ có dạng cầu thang gác
Để tránh tạo ra các lỗ hổng thì một điều kiện được thêm vào, đó là một
trong các giá trị x chuyển thành 0. Đối với cửa sổ có một góc hướng bắc như
cửa sổ thứ 2 trong hình 6b biểu thức logic cho sự tồn tại được đưa ra như sau :
v(C) ^ (v(N) ^((v(E) ^ ~v(NE) ^ ~v(SW) ^ (~v(W) ∨ ~v(S)) ∨
(v(W) ^ ~v(NW) ^ ~v(SE) ^ (~v(E) ∨ ~v(S))))))
Tương tự đối với hưóng nam và có sự thay đổi tương ứng.
3.1.3. Thuật toán của Favre và Keller
Đây là một thuật toán sử dụng sơ đồ gán nhãn trong làm mảnh song
song. Thuật toán này làm mảnh trên 1_chu trình và được hoàn thiện bởi việc
mã lại các điểm ảnh mẫu để kết hợp thông tin liên thông từ một của sổ 5 × 5
vào các điểm ảnh đã được mã trên N(p). Hai đường quét đầu tiên được sử
dụng để mã lại các điểm ảnh ở tâm, trong, biên và các điểm xương (tương ứng
c, i, r và s). Điều kiện cơ bản là thay các điểm ảnh r bởi các điểm ảnh b (nền)
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
28
nếu có mặt dãy irb theo chiều dọc hoặc ngang, trừ trường hợp cần giữ lại
được tính liên thông và các điểm cuối. Điều này cũng giống như phương thức
làm mảnh “lý tưởng” mà Eckhardt và Maderlechner đưa ra, trên đó p là D
hoàn chỉnh nếu nó thuộc một cấu trúc ipb dọc hoặc ngang, trong đó i là một
điểm trong, còn b là một điểm nền. Một điểm I hoàn chỉnh được định nghĩa
tương tự theo thuật ngữ của sự sắp chéo với điều kiện bổ sung là cả hai điểm
ảnh kề 4 đối với cả b và p đều là trắng. Chúng ta cũng đưa ra giả thuyết rằng
việc xoá song song các điểm ảnh là đơn và hoàn chỉnh (D hoặc I hoàn chỉnh)
sẽ thu được xương giả được định nghĩa tốt và không bị biến đổi trong quá
trình tịnh tiến và quay. Việc giữ lại các điểm cuối được thực hiện một cách rõ
ràng bởi vì chúng chẳng bao giờ hoàn chỉnh.
Bởi không thể xác định được một láng giềng của một điểm biên có là
điểm bên trong hay không (điểm i) nếu chỉ sử dụng cửa sổ 3 × 3, nên các
thông tin bổ xung được kết hợp chặt chẽ từ cửa sổ bên ngoài bởi việc định
nghĩa các điểm không phải là điểm cuối. Nếu SC là tập các điểm biên đơn, B
= P - SC, thì p ∈ P không phải là điểm cuối nếu và chỉ nếu:
T1 : p là liền kề với một điểm trên B.
T2 : mọi láng giềng của p ∈ P đều ∈ B hoặc kề với một điểm ∈ B
∩ N(p).
T3 : Các điểm trên B ∩ N(p) đều được liên thông trên N(p) và T4 : b(p)
≥ 2.
Quá trình hoạt động này xoá song song các điểm đơn, không phải là
điểm cuối, đường biên giữ lại được tính chất tô pô.
Để mở rộng giới hạn được đặt trên các vùng 3 × 3, sơ đồ ghép lai cũng
đã được đề xuất để chứa những sự thay đổi khoảng cách trong làm mảnh. Việc
sử dụng biến đổi khoảng cách này đã cung cấp thêm nhiều thông tin tổng thể
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
29
hơn. Nó cũng đã chứng tỏ rằng quá trình làm mảnh có thể giữ lại được tính
liên thông trong khi quá trình thay đổi khoảng cách có khả năng xây dựng lại,
kết hợp hai quá trình sẽ là hợp lý nếu cả hai thuộc tính đều được yêu cầu. Thủ
tục này được đề nghị trên mỗi vòng lặp, tập I các điểm trong của các mẫu
đang tồn tại P sẽ được xác nhận, và sự mở rộng của nó E(I) được định nghĩa là
E(I) = { q|q ∈ I hoặc có một láng giềng trong I }. Do vậy, tập các điểm cực đại
địa phương (độ lồi) có thể thu được là P - E(I), và các điểm đường biên có thể
được xoá đi loại trừ các điểm cực đại địa phương không phải điểm đơn, hoặc
điểm cuối (như đã nói ở trên). Các điểm biên còn lại được bổ xung vào xương,
và xử lý được lặp lại với I như một mẫu đang tồn tại. Nó cũng chứng tỏ rằng
một sơ đồ lai có là hiệu quả nhất vì có thể sử dụng phép biến đổi khoảng cách
ban đầu để xoá đi số lượng lớn các điểm ảnh bên ngoài trên một số vòng cố
định, và sau đó, có thể sử dụng một thuật toán bóc để làm mảnh phần ảnh còn
lại thành độ rộng đơn vị.
3.1.4. Thuật toán của Huang , Wan , Liu
Trong thuật toán này các tác giả tổng kết từ 256 dạng của 8_láng giềng
của điểm ảnh p để đưa ra 1 bảng loại trừ , theo đó điểm ảnh p được xét có bị
xoá hay không. Cột thứ nhất của bảng biểu thị số lượng điểm ảnh đen trong
8_láng giềng của p , cột thứ hai gồm các cửa sổ 3 x 3 nếu điểm p được xét phù
hợp với một trong các cửa sổ đó thì p sẽ bị xoá. Điểm p được coi là điểm an
toàn nếu không phù hợp với bất kỳ cửa sổ nào trong bảng loại trừ. Nếu
b(p)=0,1 hoặc 8 thì p không bị xoá.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
30
Hình 7a Bảng loại trừ
1 biểu thị cho điểm đen , ô trống biểu thị cho điểm trắng
Tuy nhiên những đường có độ rộng 2 pixel sẽ bị xoá và có thể làm mất
tính liên thông của mẫu. Vì vậy nhóm tác giả sử dụng thêm các mẫu lưu trữ
như hình 7b gồm các cửa sổ 3x4 , 4x3, 4x4 để lưu lại các điểm ảnh p thoả
mãn để giải quyết vấn đề trên.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
31
Hình 7b mẫu lưu trữ : ô trống biểu diễn điểm trắng,
1 biểu diễn điểm đen, x là điểm không cần quan tâm
Thuật toán gồm 4 bước như sau:
Bước 1 : Tính b(p).
Bước 2 : Đối chiếu với bảng loại trừ xem p có là điểm an toàn hay
không , nếu là điểm an toàn nhảy tới bước 4.
Bước 3: xét p có thuộc đường có độ rộng 2 pixel hay không , nếu có sử
dụng nhãn lưu trữ để quyết định có nên xoá p hay không.
Bước 4 : lặp lại các bước trên cho đến khi không còn điểm ảnh nào bị
xoá.
3.2. LÀM MẢNH SONG SONG 2 CHU TRÌNH CON
3.2.1. Thuật toán của Zang-Suen
Đây là phép cài đặt dựa trên tập các điều kiện D1-D8 trong thuật toán
Rutovitz theo 2 vòng lặp con. Vòng thứ nhất, p được xoá đi nếu nó thoả mãn
các điều kiện sau:
Z1: 2 ≤ b(p) ≤ 6
Z2: XR (p) = 2
Z3: x1.x3.x7 = 0
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
32
Z4: x1.x7.x5 = 0
Trong vòng lặp thứ hai, Z3 và Z4 được thay bởi phép xoay chúng 1800.Nghĩa
là :
Z3: x1.x3.x5 = 0
Z4: x3.x5.x7 = 0
Vì vậy, chu trình con thứ nhất xoá đi 4 điểm ảnh đơn trên biên phía
Đông-Nam cũng như các điểm ảnh góc Tây-Bắc, ngược lại chu trình thứ hai
xoá các điểm biên theo hướng ngược lại. Đây là một thuật toán đơn giản và
hiệu quả mà nó loại được nhiễu biên. Tuy nhiên, các đường chéo có độ rộng 2
điểm ảnh có thể bị xoá hẳn, và các hình vuông 2 × 2 cũng có thể bị xoá hoàn
toàn. Người ta cũng đề nghị rằng điều kiện Z1 nên được thay bằng: 3 ≤ b(p) ≤
6 để giữ lại được các cấu trúc đó. Đúng như dự đoán, sự cải biên này đã có
hiệu quả. Bởi vậy, một bước xử lý phụ được đề xuất thêm để làm mảnh thành
độ dày 1.
Mặc dù việc xói mòn quá mức các đường chéo không phải là một vấn
đề liên quan đến tính chất tô pô, nhưng sự biến mất hoàn toàn của một hình
vuông 2 x 2 trong quá trình làm mảnh cho thấy sự thiếu sót của thuật toán về
mặt tô pô. Đây chính là điều bất hợp lý của thuật toán này, do đó một sự thay
đổi đã được đề xuất để tất cả các trường hợp đều có thể được xử lý đúng. Sự
thay đổi này dựa trên 4_láng giềng đen của p khi XR (p) = 2. Nếu p có ít hơn 2
láng giềng thì không cần thay đổi gì. Nếu p có từ 2 đến 3 láng giềng và p thoả
mãn các điều kiện hiện có thì p có thể bị xoá trong vòng lặp con đầu tiên nếu
x1 = 0 hoặc x7 = 0 và trong vòng thứ hai nếu x3 = 0, x5 = 0.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
33
3.2.2. Thuật toán của Suzuki
Đây là thuật toán làm mảnh song song sử dụng số giao XH (p) để kiểm
tra việc xoá đi các điểm trên 2_chu trình con, và sử dụng cửa sổ 4 × 4 (một
cách xấp xỉ) như trên Hình 8 . Các điểm ảnh được xoá trên chu trình con thứ
nhất là a) với các điểm biên phía Bắc, và b) với các điểm biên phía Tây được
xoá đi sau khi các các điểm ảnh trên a) đã được xoá. Yêu cầu cuối cùng là đưa
ra được các kết cấu ổn định hơn trong khi tăng số láng giềng cần thiết và hoàn
chỉnh thuật toán. Trong chu trình thứ nhất, p sẽ được xoá đi nếu :
S1 : XH (p) < 2,
S2 : (b(p) > 2) ∨ [(b(p) = 2) ∧
i=
∑
1
8
xk xk + 1 = 0] và
S3 : (x3 = 0) ∨ [(x5 = 0) ∧ S4 ∧ S5], trong đó
S4 : x2 ∨ x 8(y1 ∨ y2 ∨ y3) ∨ y 2y3 = 1, và
S5: x 4 ∨ y5 ∨ x2y4 = 1.
Trên chu trình con thứ hai, các điều kiện là S1, S2 và các dạng quay 1800 của
S3-S5.
Hình 8 Cửa sổ các láng giềng của Suzuki
y5 y4
x4 x3 x2 y3
x5 p x1 y2
x6 x7 x8 y1
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
34
3.2.3. Thuật toán của Guo
Thuật toán này cũng sử dụng XH (p) thực hiện việc làm mảnh trên
2_chu trình con, ảnh được chia thành 2 trường con riêng biệt trên một bảng
kiểm tra mẫu và mỗi một vòng lặp con lại xoá đi các điểm ảnh p trên một
trường con nếu p là điểm ảnh đường biên, b(p) > 1 và XH (p) = 1. Thủ tục này
có kết quả trên các đường cong và các đường răng cưa ngang hoặc dọc. Thuật
toán này thực chất chỉ là một sự biến đổi dựa vào thuật toán của Zhang để làm
mảnh đến các xương 8_liên thông và giữ lại các đường chéo và các hình
vuông độ dày 2 × 2. Theo sơ đồ dưới đây, p sẽ được xoá đi nếu:
G1 : XH (p) = 1
G2 : 2 < min{n1(p), n2(p)} ≤ 3, trong đó:
n1(p) =
i=
∑
1
4
x2k -1 ∨ x2k và n2(p) =
i=
∑
1
4
x2k ∨ x2k + 1
tương ứng với số các cặp điểm ảnh kề 4 trong N(p) chứa 1 hoặc 2 điểm
ảnh đen và
G3 : (x2 ∨ x3 ∨ x 8) ∧ x1 = 0 trên vòng lặp con thứ nhất và các dạng quay
1800 của nó trên vòng thứ hai.
3. 3. LÀM MẢNH SONG SONG 4 CHU TRÌNH CON
3.3.1. Thuật toán của Bel-lan và Monoto
Đây là một thuật toán 4_vòng lặp con, ở đây, các điểm ảnh xương được
tìm thấy trên mỗi vòng lặp được phân định số vòng lặp để cho các phép tính
toán độ rộng của đối tượng tiếp sau đó. Các giá trị của các điểm ảnh xương từ
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
35
các vòng lặp trước được giữ không thay đổi, trái lại giá trị của các điểm ảnh
bên trong lại được tăng lên 1 sau mỗi vòng lặp. Trong vòng lặp thứ n, điểm
ảnh p được kiểm tra để xoá đi như một thành phần trên đường biên Bắc nếu x3
= 0, p có giá trị là n, và x7 ≠ 0. Như một thành phần biên p được giữ lại làm
xương nếu có tồn tại xi ∈ N(p) sao cho xi > 0 và N(xi) ∩ N(p) = {p, xi}, nếu
không, p được nhận giá trị 0 và bị xoá đi. Thuật toán này giữ lại được tính
chất tô pô nhưng nhạy cảm với nhiễu biên và phải phụ thuộc vào thứ tự của
các vòng lặp con.
3.3.2. Thuật toán của Rosenfeld và điều kiện Hilditch
Đây là thuật toán cũng sử dụng các cửa sổ làm mảnh [1], trên đó các
mặt nạ để xét các điểm được xoá như trên Hình 9 cùng với các dạng quay 900
của chúng.
(a) (b)
Hình 9 Các điều kiện xoá điểm ảnh của Rosenfeld.
Mỗi mặt nạ được áp dụng một cách song trên P, và các mặt nạ có thứ tự
như (a) và (b), hay các dạng quay 900 của chúng v.v... Vì thế, thuật toán này
xoá đi các điểm ảnh từ 8 biên hợp lệ nw, w, v.v... Bản chất phản đối xứng của
mặt nạ (b) là kết quả thu được do đòi hỏi P không bị xoá hoàn toàn trong xử lý
song song. Thuật toán này được xác nhận thực hiện chính xác. Nó cũng đặc
biệt tương thích để thực hiện trên các bộ xử lý song song mà có thể trích ra
các thành phần “0” và “1”, có định trước số các thành viên “0” hoặc “1” trong
0 0
0 1 1
1
0 0 0
1
1 1
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
36
việc chọn vị trí các láng giềng. Và nó được thực hiện trên bộ 4 xử lý song
song. Do không phải tất cả các điểm ảnh đủ tiêu chuẩn xoá đều bị xoá, nên các
mặt nạ khác được thêm vào như trên Hình 10 và các dạng quay của nó.
(a) (b) (c) (d)
Hình10: Điều kiện xoá điểm ảnh của Hilditch.
Điều kiện phụ cho các kết quả tốt khi việc xoá đi được giới hạn cho các
điểm ảnh không chỉ thoả mãn các tiêu chuẩn mà phải thoả mãn chúng ngay
khi bắt đầu vòng lặp hiện tại. điều này đảm bảo rằng chỉ một lớp các điểm ảnh
được xoá đi xung quanh P dẫn đến thuật toán có thể dự đoán nhiều hơn với độ
bất thường nhỏ hơn tại các góc có hai lớp điểm ảnh có thể bị xoá đi. Đây là
một phép toán biên song song, trái với cơ bản là biên tuần tự. Thực hiện một
thuật toán đường biên song song trên một bộ 4 xử lý không liên quan đến các
phép tính ngoài vì các láng giềng có giá trị 1, 0 được xoá đi trên từng bước
riêng trong bất cứ tình trường hợp nào. Vì vậy, chỉ cần kiểm tra các điểm 1
trên mẫu khi bắt đầu vòng lặp, trái lại các điểm 0 được kiểm tra trên mẫu đến
khi được giữ lại. Thời gian tính toán được đòi hỏi hơn nữa là do số điểm ảnh
được xoá đi trên mỗi chu trình ít hơn. Các điều kiện biên song song như trên
Hình 10 là tương đương với bộ 4_vòng lặp xoá biên song song của các điểm
biên với số giao XH (p) = 1.
0 0 0
1
1 1
0
1 1 1
1
0 0 0
1 1
1
0
0 1 1
1
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
37
Do việc sử dụng các bảng kiểm tra, nên việc thực hiện đã dựa trên các
điều kiện biên song song như Hình 10, trên đó mặt nạ (c) và các dạng quay
của nó bị bỏ sót và thêm vào các điều kiện điểm cuối. Để ngăn chặn việc xói
mòn của các đường có độ dày 2 điểm ảnh, thông tin bổ sung được sử dụng để
mà các điểm ảnh này được giữ lại nếu các điểm ảnh láng giềng có trước của
nó đã bị xoá đi.
3.3.3. Thuật toán của Stentiford
Thuật toán được phát biểu như sau :
1. Tìm các điểm ảnh (i,j) thích hợp với mẫu M1 trong hình 11.
2. Nếu điểm trung tâm không phải là điểm cuối và có số kết nối =1
, đánh dấu để thực hiện xoá.
3. Lặp lại bước 1 và 2 cho tất cả các điểm ảnh so khớp với mẫu M1.
4. Lặp lại bước 1,2 và 3 đối vơí mẫu M2,M3 và M4.
5. Nếu điểm ảnh bào đó được đánh dấu thì xoá.
6. Lặp lại từ bước 1 cho đến khi không còn điểm ảnh nào bị xoá ở
bước 5.
M1 M2 M3 M4
Hình 11 các mẫu cửa sổ Stentiford
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
38
Mục đích của các mẫu M1, M2, M3, M4 là tìm các điểm ảnh để xoá là
các điểm rìa trên, bên trái, bên dưới và bên phải của đối tượng. Kiểu lý thuyết
và hướng áp dụng đảm bảo các điểm ảnh sẽ bị xoá một cách đối xứng.
Số kết nối được tính như sau :
Cn = ∑∈sk Xk – (Xk . Xk+1. Xk+2)
Trong đó Nk là giá trị của 8_láng giềng ( =1 nếu là điểm trắng , 0 nếu là
điểm đen) , s= { 1,3,5,7} , Nk=Nk-8 nếu k>8.
3.4. NHẬN XÉT
Các thuật toán song song, trong nhưng năm gần đây đã được tập trung
chú ý đến tốc độ thực hiện, và điều này dẫn đến việc so sánh với những dạng
thuật toán khác về thới gian tính toán và số vòng lặp con được sử dụng [2].
Tuy nhiên một số so sánh về số vòng lặp cũng không hoàn toàn đúng. Một
thuật toán 1 vòng kiểm tra (ví dụ như Holt) thường được thực hiện trên một
vùng hỗ trợ lớn hơn 3 × 3, điều này sinh ra việc cần phải có một kết quả trung
gian hoặc thông tin rìa trên các điểm ảnh láng giềng. Với lý do này, cần phải
có một cơ cấu chung để định nghĩa thế nào là “vòng lặp” để cho các thuật toán
song song được so sánh một cách có ý nghĩa. Người ta đưa ra một sơ đồ cho
rằng trong mỗi vòng lặp, mỗi thành phần của một mạng máy tính có thể tính
toán bất cứ một hàm logic nào của một láng giềng 3 × 3, và tốc độ song song
của một thuật toán được đánh giá bằng số các vòng lặp cần thiết. Khi sử dụng
độ đo này, thì tốc độ song song của thuật toán Holt không tốt hơn các thuật
toán hai vòng lặp con như là thuật toán của Zhang.
Có thể nói rằng, đối lập với các thuật toán tuần tự, sự phức tạp của các
thuật toán song song là kết quả của việc cần thiết giữ tính liên thông trong khi
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
39
sử dụng các phép toán song song trên một vùng lân cận nhỏ. Đây là một vấn
đề đặc thù tự nhiên của làm mảnh song song, và nó đã được khắc phục bằng
cách sử dụng các vòng lặp con hoặc bằng cách mở rộng vùng lân cận để kiểm
tra. Trong trường hợp khác, các kết quả thực được tính toán tức thời và sử
dụng mẫu để giữ được nhiều cấu trúc tổng thể hơn.
CHƯƠNG 4
CÀI ĐẶT THỰC NGHIỆM
MỘT SỐ THUẬT TOÁN LÀM MẢNH
Chương trình thực hiện mở file ảnh dạng bitmap 256 màu, sau đó vào
menubar lựa chọn ‘Thinning’, chọn một thuật toán làm mảnh , ví dụ
Thinning/Huang . Chương trình sẽ đưa ảnh về dạng nhị phân và làm mảnh ảnh
trên . Chương trình cài đặt thành công các thuật toán : Hilditch, Huang, Zang-
Suen, Stentiford. Giao diện của chương trình như sau :
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
40
Một kết quả của làm mảnh :
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
41
Trong 4 thuật toán đã cài đặt được đều cho xương tốt đối với các chữ in, đặc
biệt là thuật toán của Zhang-Suen các xương của các kí tự được tạo thành từ
các đường thẳng ngang và dọc như : E, F, H, I, L,T cho xương thẳng hơn các
thuật toán khác. Tuy nhiên đối với các hình có dạng đóng trong 1 vùng như
hình vuông, chữ nhật hoặc hình tròn các thuật toán trên không đảm bảo tính
hình học , đối với hình tròn xương thu được là 1 điểm ảnh còn đối với hình
vuông, hình chữ nhật xương thu được là đường thẳng hoặc điểm ảnh. Vì vậy
nhìn vào các xương này chúng ta không thể nhận biết được hình dạng nguyên
thuỷ của chúng.
Các hàm cơ bản trong chương trình
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
42
Hàm chuyển đổi về ảnh nhị phân
void nhiphan()
{
for(i=0;i<h-1;i++)
for(j=0;j<w-1;j++)
{
if(matran[i][j]<128)
matran[i][j]=1;
else matran[i][j]=0;
}
}
Hàm tính b(p)
void dem()
{
tong=0;
if(x[1]!=0) tong=tong+1;
if(x[2]!=0) tong=tong+1;
if(x[3]!=0) tong=tong+1;
if(x[4]!=0) tong=tong+1;
if(x[5]!=0) tong=tong+1;
if(x[6]!=0) tong=tong+1;
if(x[7]!=0) tong=tong+1;
if(x[8]!=0) tong=tong+1;
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
43
}
Hàm tính số giao XH
int SoGiaoXH()
{
int xh=0;
if (x[1]==255)
{
if(x[2]!=255||x[3]!=255) xh++;
}
if (x[3]==255)
{
if(x[4]!=255||x[5]!=255) xh++;
}
if (x[5]==255)
{
if(x[6]!=255||x[7]!=255) xh++;
}
if (x[7]==255)
{
if(x[8]!=255||x[1]!=255) xh++;
}
return xh;
}
Hàm tính số giao XR
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
44
int SoGiaoXR()
{
int a[9];
for(int k=1;k<=8;k++)
{
if(x[k]==1) a[k]=1;
else a[k]=0;
}
return(abs(a[1]-a[2])+abs(a[2]-a[3])+abs(a[3]-a[4])+abs(a[4]-
a[5])+abs(a[5]-a[6])+abs(a[6]-a[7])+abs(a[7]-a[8])+abs(a[8]-a[1]));
}
MỘT SỐ THUẬT TOÁN TRONG CHƯONG TRÌNH
Thuật toán của Huang, Wan, Liu
while(tieptuc==true)
{
delpixel=false;
for(i=0;i<h-1;i++)
for(j=0;j<w-1;j++)
{
if(matran[i][j]==1)
{
x[1]=matran[i][j+1];
x[2]=matran[i-1][j+1];
x[3]=matran[i-1][j];
x[4]=matran[i-1][j-1];
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
45
x[5]=matran[i][j-1];
x[6]=matran[i+1][j-1];
x[7]=matran[i+1][j];
x[8]=matran[i+1][j+1];
x[9]=matran[i+2][j+1];
x[10]=matran[i+2][j];
x[11]=matran[i+2][j-1];
x[12]=matran[i-2][j+1];
x[13]=matran[i-2][j];
x[15]=matran[i-1][j+2];
x[16]=matran[i][j+2];
x[17]=matran[i+1][j+2];
x[18]=matran[i+2][j+2];
x[19]=matran[i-1][j-1];
x[20]=matran[i][j-2];
dem();
luu();
}
}
for(i=0;i<h-1;i++)
for(j=0;j<w-1;j++)
{
if(matran[i][j]==125) matran[i][j]=0;
}
if(delpixel==true) tieptuc=true;
else tieptuc=false;
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
46
}
Thuật toán Zhang-Suen
while(tieptuc==true)
{
delpixel=false;
for(i=1;i<h-2;i++)
for(j=1;j<w-2;j++)
{
matran2[i][j]=matran[i][j];
}
for(i=1;i<=h-2;i++)
for(j=1;j<=w-2;j++)
{
if(matran2[i][j]==1)
{
x[1]=matran2[i][j+1];
x[2]=matran2[i-1][j+1];
x[3]=matran2[i-1][j];
x[4]=matran2[i-1][j-1];
x[5]=matran2[i][j-1];
x[6]=matran2[i+1][j-1];
x[7]=matran2[i+1][j];
x[8]=matran2[i+1][j+1];
dem2();
if(2<=tong2&&tong2<=6)
{
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
47
if(SoGiaoXR2()==2)
{
if(x[1]==0||x[7]==0||x[3]&&x[5]==0)
{
matran[i][j]=0;delpixel=true;
}
}
}
}
for(i=1;i<h-2;i++)
for(j=1;j<w-2;j++)
{
matran2[i][j]=matran[i][j];
}
for(i=1;i<h-2;i++)
for(j=1;j<w-2;j++)
{
if(matran2[i][j]==1)
{
x[1]=matran2[i][j+1];
x[2]=matran2[i-1][j+1];
x[3]=matran2[i-1][j];
x[4]=matran2[i-1][j-1];
x[5]=matran2[i][j-1];
x[6]=matran2[i+1][j-1];
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
48
x[7]=matran2[i+1][j];
x[8]=matran2[i+1][j+1];
dem2();
if(2<=tong2&&tong2<=6)
{
if(SoGiaoXR2()==2)
{
if(x[3]==0||x[5]==0||x[1]==0&&x[7]==0)
{
matran[i][j]=0;delpixel=true;
}
}
}
}
}
if(delpixel==true) tieptuc=true;
else tieptuc=false;
}
Thuật toán Stentiford
//chu trinh con thu 1
for(i=0;i<=h-1;i++)
for(j=0;j<=w-1;j++)
{
x[1]=matran[i][j+1];
x[2]=matran[i-1][j+1];
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
49
x[3]=matran[i-1][j];
x[4]=matran[i-1][j-1];
x[5]=matran[i][j-1];
x[6]=matran[i+1][j-1];
x[7]=matran[i+1][j];
x[8]=matran[i+1][j+1];
fprintf(f,"ket noi= %d",ketnoi());
if(matran[i][j]==1&&matran[i+1][j]==1&&matran[i-1][j]==0)
{
dem2();
if(tong2!=1&&ketnoi()==1)
{
matran2[i][j]=0;
}
}
}
for(i=0;i<h-1;i++)
for(j=0;j<w-1;j++)
{
matran[i][j]=matran2[i][j];
}
//chu trinh con thu 2
for(i=0;i<=h-1;i++)
for(j=0;j<=w-1;j++)
{
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
50
x[1]=matran[i][j+1];
x[2]=matran[i-1][j+1];
x[3]=matran[i-1][j];
x[4]=matran[i-1][j-1];
x[5]=matran[i][j-1];
x[6]=matran[i+1][j-1];
x[7]=matran[i+1][j];
x[8]=matran[i+1][j+1];
if(matran[i][j]==1&&matran[i][j+1]==1&&matran[i][j-1]==0)
{
dem2();
if(tong2!=1&&ketnoi()==1)
{
matran2[i][j]=0;
}
}
}
for(i=0;i<h-1;i++)
for(j=0;j<w-1;j++)
{
matran[i][j]=matran2[i][j];
}
//chu trinh con thu 3
for(i=0;i<=h-1;i++)
for(j=0;j<=w-1;j++)
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
51
{
x[1]=matran[i][j+1];
x[2]=matran[i-1][j+1];
x[3]=matran[i-1][j];
x[4]=matran[i-1][j-1];
x[5]=matran[i][j-1];
x[6]=matran[i+1][j-1];
x[7]=matran[i+1][j];
x[8]=matran[i+1][j+1];
if(matran[i][j]==1&&matran[i+1][j]==0&&matran[i-1][j]==1)
{
dem2();
if(tong2!=1&&ketnoi()==1)
{
matran2[i][j]=0;
}
}
}
for(i=0;i<h-1;i++)
for(j=0;j<w-1;j++)
{
matran[i][j]=matran2[i][j];
}
//chu trinh con thu 4
for(i=0;i<=h-1;i++)
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
52
for(j=0;j<=w-1;j++)
{
x[1]=matran[i][j+1];
x[2]=matran[i-1][j+1];
x[3]=matran[i-1][j];
x[4]=matran[i-1][j-1];
x[5]=matran[i][j-1];
x[6]=matran[i+1][j-1];
x[7]=matran[i+1][j];
x[8]=matran[i+1][j+1];
if(matran[i][j]==1&&matran[i][j-
1]==1&&matran[i][j+1]==0)
{
dem2();
if(tong2!=1&&ketnoi()==1)
{
matran2[i][j]=0;
}
}
}
for(i=0;i<h-1;i++)
for(j=0;j<w-1;j++)
{
matran[i][j]=matran2[i][j];
}
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
53
KẾT LUẬN
Đồ án đã giải quyết được một số vấn đề cơ bản sau:
1.Tìm hiểu tổng quan về làm mảnh ảnh :
Khái niệm ảnh số, xử lý ảnh, cách biểu diễn.
Tìm hiểu khái niệm về xương ảnh,làm mảnh ảnh.
Phân loại các phương pháp tìm xương.
Phân loại các phương pháp làm mảnh ảnh.
Các khái niệm trong thuật toán làm mảnh : láng giềng , số thành phần
liên thông, điểm biên, điểm trong, điểm cuối, điểm đơn, điểm bội, số
giao.
2.Tìm hiểu về các thuật toán làm mảnh tuần tự : bao gồm 4 thuật toán làm
mảnh theo điểm biên và 2 thuật toán làm mảnh theo loạt.
3.Tìm hiểu về các thuật toán làm mảnh song song :
Thuật toán làm mảnh song song sử dụng 1 chu trình con : 4 thuật toán.
Thuật toán làm mảnh song song sử dụng 2 chu trình con : 3 thuật toán.
Thuật toán làm mảnh song song sử dụng 4 chu trình con : 3 thuật toán.
4.Cài đặt thành công 4 thuật toán làm mảnh : Hilditch, Zhang-Suen ,
Stentiford
,Huang-Wan-Liu.
Hướng phát triển tiếp theo của đồ án
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
54
Em mong rằng qua đồ án này với sự nhận xét, đánh giá của thầy cô giáo và
các bạn em sẽ rút ra nhiều kinh nghiệm về các phương pháp làm mảnh trên
ảnh nhị phân. Từ đó có thể có những hiểu biết cần thiết để tiếp tục nghiên cứu
các phương pháp làm mảnh trên ảnh đa cấp xám, ảnh màu , ảnh 3D để xây
dựng những chương trình thiết thực trong cuộc sống.
TÀI LIỆU THAM KHẢO
1. Louisa Lam, Seong - Whan Lee, Member, “Thinning Methodologies
- A Comprehensive Survey”, IEEE Trans on Pattern Analysis and Machine
Itelligence, vol 14, no.9, 9-1992.
2. Louisa Lam, Ching Y Suen, “An Evaluation of Prallel Thinning
Algorithms for Character Recognition”, IEEE Trans on Pattern Analysis and
Machine Itelligence, vol 17, no.9, 9-1992.
3. C.Arcelli and G. Sanniti di Baja, “On the sequential approach to
median line transfornation”, IEEE Trans. Syst. Man cybern, vol. SMC 8, no.
2, pp. 139-144. 1992.
4. C. J. Hilditch “Linear skeletons form square cupboards”, in Machine
Intell. (B. Meltzer and D. Michic, Eds). New York: Amer. Elsevier. 1969,
pp.403-420, vol. 4.
5. D. Rutovitz “Pattern recognition” J. Roy.Stat. Soc., vol. 192. Serries
A, pp. 504-530. 1966.
6. A.Rosenfeld “A characterization of parallel thinning algorithm”
Inform. Contr., vol29, no. 3, pp 286-2910, 1995.
Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh
ảnh
Sinh viên Hà Đức Kiên - CT702 Trang
55
7. P. C. K. Kwok “A thinning algorithm by contour generation” Comm.
ACM, vol. 31, no.11, 1314-1324, 1998.
8. T. Pavlidis “A thinning algorithm for discrete binary images”
Comput. Graphics Image Processing, vol. 13, pp. 142-157, 1980.
9. O.Baruch “Line thinning by line following” Patt. Recogn. Lett., vol.
8, no. 4, pp, 271-276, 1989.
10. Huang, L., Wan, G. and Liu, C. “An Improved Parallel Thinning
Algorithm”. Proceedings of. Seventh International Conference on
Document Analysis and Recognition, 780 – 783, 2003.
11.Lương Mạnh Bá, Nguyễn Thanh Thuỷ , “Nhập môn xử lý ảnh số” ,
Nhà xuất bản khoa học và kỹ thuật , 1999.
Các file đính kèm theo tài liệu này:
- a1.PDF