XỬ LÝ ẢNH NHỊ PHÂN


I. Các phép toán nhị phân

Ký hiệu chuẩn cho tập các thao tác nhị phân cơ bản

NOT

OR

AND

XOR
SUB

Ở đây mỗi thao tác sẽ được áp dụng cho từng điểm ảnh một.

Lấy ví dụ, . Định nghĩa của mỗi thao tác được cho sau đây:

NOT a

 

0

1

1

0

 

OR

a

b

0

1

0

0

1

1

1

1

 

AND

a

b

0

1

0

0

0

1

0

1

XOR

a

b

0

1

0

0

1

1

1

0

SUB

a

b

0

1

0

0

0

1

1

0

Hình dưới đây minh họa những thao tác nói trên với giá trị nhị phân “1” có màu đen, còn giá trị nhị phân “0” có màu trắng.

a) Ảnh a b) Ảnh b

Not (b) ; Or(a,b) ; And(a,b)

Xor(a,b) ; Sub(a,b)

Phép toán SUB(*) sẽ rất hữu ích khi ảnh a thể hiện vùng quan tâm mà chúng ta muốn phân tích một cách hệ thống, còn ảnh b thể hiện các đối tượng đã được phân tích và có thể loại đi khỏi vùng đó.

II. Phép toán morphology

Ta đã định nghĩa ảnh là một hàm hai biến thực hoặc một mảng các giá trị rời rạc . Chúng ta còn có một đinh nghĩa khác về ảnh, dựa trên quan sát là mỗi ảnh có thể xem như là một tập hợp các tọa độ rời rạc hoặc liên tục.

Theo một nghĩa nào đó, tập hợp này tương ứng với các điểm ảnh thuộc về các đối tuợng hiện hữu trong ảnh.

Hình trên minh họa ý tưởng này bằng cách cho thấy có hai đối tượng, hay hai tập A B trong ảnh. Ở đây chúng ta cần phải xác định rằng hệ trục tọa độ như trong hình vẽ. Trong phần này, chúng ta chỉ cần quan tâm đến các giá trị điểm ảnh nhị phân và giới hạn không gian làm việc trên không gian rời rạc .

Đối tượng A gồm những điểm có cùng tính chất sau:

Đối tượng A =

Ví dụ đối tượng B trong hình trên gồm các điểm ảnh ở tọa độ .

Phần nền của A được ký hiệu bởi (phần bù của A), sẽ bao gồm các điểm ảnh không thuộc A:

Phần nền –

Ta thấy là nếu một đối tượng A được định nghĩa trên một lân cận liên thông C (C = 4, 6 hoặc 8 ) thì phần nền tương ứng sẽ có tính liên thông cho bởi 12-C;

1. Các định nghĩa cơ bản

Các phép toán cơ bản ứng với một đối tượng chính là tập các phép toán tập hợp chuẩn bao gồm phép hội, phép giao, phép lấy bù và phép tịnh tiến:

Phép tịnh tiến – Cho trước một vector x và một tập hợp A, phép tịnh tiến A + x được định nghĩa như sau:

Chú ý rằng những phần tử riêng lẻ hợp thành B không chỉ có các điểm ảnh mà còn có cả những vector khi chúng có vị trí tọa độ xác định so với điểm gốc. Cho hai tập hợp AB, chúng ta có:

Phép cộng Minkowski (addition)

Phép trừ Minkowski (subtraction)

2. Phép phát triển và phép bào mòn

Từ hai phép toán Minkowski vừa định nghĩa ở trên, chúng ta có thể định nghĩa hai phép toán morphology cơ bản là phép phát triển và phép bào mòn:

Phép phát triển (dilation )

Phép bào mòn (erosion)

Trong đó

Mặc dù cả A hay B đều có thể được xem là “ảnh” nhưng thông thường A được xem là ảnh, còn B được xem là phần tử cấu trúc. Trong lý thuyết toán học về Morphology, phần tử cấu trúc có vai trò tương tự như khái niệm nhân chập trong lý thuyết về các bộ lọc tuyến tính.

Một cách tổng quát thì phép phát triển làm cho các đối tượng gia tăng kích thước, còn phép bào mòn sẽ làm cho chúng co lại. Sự gia tăng co lại nhiều hay ít, gia tăng hoặc co lại theo cách thức nào của các đối tượng đều phụ thuộc vào cách lựa chọn phần tử cấu trúc. Hai phần tử cấu trúc thông dụng nhất (sử dụng hệ tọa độ Đề-các) là các tập liên thông 4 và 8, thường được ký hiệu là.

+ Một số tính chất của Phép phát triển và phép bào mòn

Tính giao hoán: D(A,B) = A+B = D(B,A)

Tính không giao hoán: E(A,B)

Tính kết hợp:

Tính bất biến trong tịnh tiến:

Tính đối ngẫu (2-1)

Tính không khả nghịch

Tính bất biến trong tịnh tiến:

Với A là một đối tượng và là phần nền của nó, tính chất trên cho thấy phép phát triển một đối tượng tương đương với phép bào mòn phần nền của nó. Tương tự như vậy, phép bào mòn một đối tượng tương đương với phép phát triển phần nền của nó.

Thực hiện các thuật toán phát triển và bào mòn đơn giản nhất thường được mô tả như sau:

Phép phát triển

Ứng với mỗi điểm ảnh thuộc đối tượng (có giá trị ”1”) thay đổi giá trị của tất cả các điểm ảnh nền (có giá trị ”0”) thuộc liên thông C của nó sang giá trị “1”.

Phép bào mòn: Ứng với mỗi điểm ảnh nền (có giá trị “0”), thay đổi giá trị của tất cả các điểm ảnh thuộc đối tượng (có giá trị “1”) thuộc liên thông C của nó sang giá trị “0”.

3. Phép chập logic

Một đối tượng ảnh nhị phân (hay một phần tử cấu trúc ) tùy ý A có thể được biểu diễn dưới dạng sau:

Trong đó là phép toán logic OR và AND, là một hàm đặc trưng nhận các giá trị logic “1” và “0” xác định bởi quan hệ sau:

còn là phiên bản logic của hàm delta Dirac nhận các giá trị logic “1” và “0” xác định bởi quan hệ sau:

Khi đó phép phát triển nhị phân được viết lại thành:

Và do hai phép toán logic OR và AND có tính giao hoán, chúng ta còn có thể viết lại quân hệ trên dưới dạng;

(3-1)

Bằng cách sử dụng định lý De Morgan:

Kết hợpvới các phương trình (3-1) và (2-1), phép bào mòn sẽ được viết lại dưới dạng sau:

Như vậy, phép phát triển và phép bào mòn trên ảnh nhị phân có thể được xem là một dạng của phép chập trên đại số Bool.

4. Phép mở và phép đóng

Chúng ta có thể kết hợp phép phát triểnphép bào mòn để tạo thành các phép toán có mức độ quan trọng cao hơn:

Phép mở: O(A,B)=AoB=D(E(A,B),B)

Phép đóng: C(A,B)=AB=E(D(A,-B),-B)

Các phép mở và đóng có các tính chất sau:

Tính đối ngẫu: Cc(A,B)=O(AC, B)

Oc(A,B)=C(Ac, B)

O(A+x, B)=O(A, B)+x

Tính tịnh tiến: C(A+x, B)=C(A, B) +x

Với phép toán mở thông qua phần tử cấu trúc B và các ảnh A, A1, A2, trong đó A1 là ảnh của A2 (A1 ), chúng ta có các tính chất sau:

Tính phản mở rộng (4-1)

Tính đơn điệu tăng

Tính dừng

Với phép toán đóng thông qua phần tử có cấu trúc B và các ảnh A, A1, A2 , trong đó A1 là ảnh của A2 , chúng ta có:

Tính mở rộng

Tính đơn điệu tăng

Tính dừng

Hai tính chất quan trọng cho bới các phương trình nhân chập đại số (tổng chập) và (4-1) hết sức quan trọng trong lý thuyết toán về morphology, đến độ chúng có thể được xem là nguyên nhân dẫn đến việc định nghĩa phép bào mòn với -B, thay vì với B.

5. Phép trúng- trật

Toán tử trúng – trật do Serra đưa ra có định nghĩa như sau. Cho trước một ảnh A và hai phần tử cấu trúc B1, B2. Khi đó toán tử trúng – trật được xác định bởi một trong hai cách sau:

Phép trúng – trật: HitMiss(A,B1, B2) =

Trong đó B1 và B2 đều bị chặn và tách biệt nhau, hai tập hợp gọi là tách biệt nếu Æ, hay tập rỗng. Xét theo một nghĩa quan trọng thì toán tử trúng – trật là dạng tương đương về mặt morphology của kỹ thuật đối sánh mẫu, một kỹ thuật nổi tiếng dùng để đối sánh các khuôn dạng dựa trên mức độ tương quan chéo giữa chúng. Ở đây chúng ta có một mẫu B1 cho đối tượng và một mẫu B2 cho nền.

6. Tóm tắt những phép toán cơ bản

Cho ba phần tử cấu trúc có tính đối xứng (giá trị “-“ đại diện cho ý “ không quan tâm”.

(a) (b) (c)

Ta có kết quả xử lý các phép toán như sau:

Phép toán mở có thể tách các đối tượng liên thông trong một ảnh nhị phân. Phép toán đóng có thể lấp đầy các lỗ nhỏ. Với một phần tử cấu trúc “trơn”, cả hai phép toán này đều cho một lượng trơn đáng kể trên biên của đối tượng nhận tác động tư chúng. Phép mở làm trơn biên đối tượng từ phía trong còn phép đóng làm trơn biên đối tượng từ phía ngoài.

Trong ví dụ về phép trúng – trật phép toán này đã tìm ra được các điểm ảnh biên liên thông 4. Tuy nhiên, chúng ta còn có một phương pháp đơn giản khác để tìm biên của một đối tượng thông qua quan hệ sau:

Biên liên thông 4

Hoặc

Biên liên thông 8

7. Phép rút xương

Định nghĩa không hình thức về xương của một đối tượng là: Xương là một biểu diễn dạng đường của một đối tượng, trong đó:

i) Đường này có độ rộng 1 điểm ảnh.

ii) Đường này đi qua phần giữa của đối tượng đó.

iii) Đường này bảo toàn tôpô của đối tượng.

Những điều kiện nói trên không phải lúc nào cũng thực hiện được. Chúng ta có thể chỉ ra một tình huống như vậy trong hình dưới.

Trong ví dụ đầu tiên ở hình (a), để sinh ra một đường thể hiện sự đơn giản của đối tượng, chúng ta không thể nào tạo ra một đường thẳng có độ dày của một điểm ảnh và nằm ở tâm của đối tượng. Trong hình (b), chúng ta lại không thể loại bỏ bất kỳ điểm ảnh nào của đối tượng của liên thông 8 có trong hình và đồng thời bảo toàn tôpô của đối tượng, với đặc trưng tôpô ở đây chính là tính liên thông. Mặc dù vậy chúng ta cũng có rất nhiều kỹ thuật cố gắng tạo ra được xương của đối tượng.

Công thức cơ bản cho việc tạo xương này dựa trên công trình của Lantuejou. Tập con xương Sk(A) được xác định bởi:

k = 0,1,…,K (7-1)

Trong đó K là giá trị k lớn nhất trước khi Sk(A) trở thành tập rỗng. Từ phương trình 7-1, chúng ta có: . Phần tử cấu trúc B được chọn trong Z2 để xấp xỉ một đĩa tròn có tính lồi, bị chặn và đối xứng. Khi đó xương sẽ là hội của các tập con xương:

Xương (7-2)

Dựa trên công thức này, chúng ta có thể thấy rằng đối tượng ban đầu là hoàn toàn có thể tái xây dựng lại nếu những tri thức về tập con Sk(A), phần tử cấu trúc B, và giá trị K được cho trước:

Tái xây dựng (7-3)

Mặc dù vậy, công thức vừa trình bày ở trên không bảo toàn được tôpô của đối tượng, là một trong những yêu cầu của quá trình tạo xương.

Một quan điểm khác trong tiếp cận giải quyết bài toán này là phép làm mảnh, hay chính xác là một phép bào mòn cho phép làm giảm độ dày của đối tượng nhưng không làm triệt tiêu nó. Thuật toán làm mảnh tổnh quát có dạng sau:

Phép làm mảnh: Thin)

Tùy theo cách chọn lựa B1B2 mà chúng ta sẽ có rất nhiều thuật toán làm mảnh khác nhau có thể được cài đặt.

Chúng ta còn có thê mô tả một cài đặt hết sức thực tế theo một cách khác. Nếu chúng ta tự giới hạn mình với lân cận 3×3, là lân cận tương tự với phần tử cấu trúc B = N8 =, khi đó phép toán làm mảnh có thể được xem như hành động quét đi quét lại một cửa sổ trên ảnh nhị phân. Điểm ảnh ở giữa cửa sổ này sẽ đượcc nhận giá trị “0” dựa trên một số điều kiện nào đó. Điểm ảnh trung tâm này sẽ không bị đổi thành “0” nếu và chỉ nếu:

i) Có một điểm ảnh cô lập được tìm thấy.

ii) Sự loại bỏ một điểm ảnh sẽ làm thay đổi tính liên thông.

iii) Sự loại bỏ một điểm ảnh sẽ làm thu ngắn một đường thẳng.

Quá trình loại bớt các điểm ảnh sau mỗi lần lặp lại được gọi là phép bào mòn có điều kiện.

Một cách tỏng quát tất cả các phép quay và biến thể của chúng đều phải được kiểm tra. Do chỉ có tối đa 512 tổ hợp điểm ảnh ứng với cửa sổ 3×3 trên một ảnh nhị phân, chúng ta có thể cài đặt phép kiểm tra này dễ dàng bằng cách sử sụng bảng tra.

Nếu chỉ có điều kiện (i) được sử dụng thì mọi đối tượng đều sẽ bị bào mòn đến chỉ còn một điểm. Đây là cách mà chúng ta có thể sử dụng để đếm số lượng các đối tượng có trong ảnh. Nếu chỉ có điều kiện (ii) thì các lỗ trong các đối tượng sẽ được tìm thấy. Nếu điều kiện (iii) được sử dụng thì mỗi đối tượng đều sẽ bị bào mòn đến chỉ còn một điểm nếu như nó không chứa lỗ bên trong, hoặc sẽ bị bào mòn thành các vòng đóng nếu nó có chứa lỗ bên trong. Trong trường hợp cả ba điều kiện (i, ii, iii) được dùng thì một “khung xương hoàn chỉnh”.

8. Phép lan truyền

Trong thực tế, sẽ rất tiện lợi nếu như chúng ta có thể tái xây dựng lại một ảnh đã “sống còn” sau nhiều lần bị bào mòn, hoặc có thể làm đầy một đối tượng được xác dịnh bởi đường biên của nó. Quá trình này có rất nhiều tên gọi như lấp đầy vùng, tái xây dựng, và lan truyền. Định nghĩa hình thức của nó được cho trong thuật toán sau đây.

Chúng ta sẽ bắt đầu với một ảnh hạt giống S(0) ,một ảnh mặt nạ A,và một phần tử cấu trúc B. Sau đó chúng ta sẽ thực hiện nhiều phép phát triển S với B và che nó bởi mặt nạ A, trong một thủ tục lặp như sau:

Bước lặp thứ (k): cho đến khi

Sau mỗi lần lặp, ảnh hạt giống sẽ to thêm (do phép phát triển ) nhưng vẫn nằm trong tập đối tượng xác định bởi A, hay nói cách khác, S lan truyền để lấp đầy A. Lựa chọn thông dụng nhất đối với B là N4 hay N8.

Theo webng.com

Advertisements

One comment on “XỬ LÝ ẢNH NHỊ PHÂN

  1. Thật là hay.Cảm ơn rất nhiều. Tôi học lại 3 lần đại số, giờ thì chắc nịch rồi .Đại số thực sự là một môn học triết học .Trước đó tôi biết nhiều ngành củng có ảnh hưởng của môn học này ,giờ thêm cả xử lý ảnh nữa.Thật là may quá !hihi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s