Tôpô kỹ thuật số

Tôpô kỹ thuật số (Digital topology) là ngành nghiên cứu các cấu trúc và tính chất tôpô trong ảnh kỹ thuật số (chủ yếu là ảnh số 2 chiều – 2D, và ảnh số 3 chiều – 3D). Những khái niệm và kết quả lý thuyết chính của tôpô đã giải quyết được nhiều vấn đề trong lĩnh vực xử lý ảnh số như tạo ảnh số, lưu trữ, thao tác biến đổi và trình bày ảnh số.

Lịch sử vấn đề

Tôpô kỹ thuật số được nghiên cứu vào cuối những năm 1960 bởi nhà nghiên cứu phân tích hình ảnh máy tính Azriel Rosenfeld (1931-2004). Thuật ngữ "tôpô kỹ thuật số" được ông đưa ra trong ấn phẩm lần đầu tiên năm 1973. Ông đã có những đóng góp quan trọng trong việc xây dựng và phát triển lĩnh vực này.

Năm 1935, Alexandrov-Hopf đã đưa ra một vấn đề liên quan gọi là tôpô ô lưới (grid cell topology) trong cuốn sách Topologie I. Rosenfeld và cộng sự đề xuất tính liên thông kỹ thuật số như tính 4-liên thông và 8-liên thông trong không gian 2D cũng như 6-liên thông và 26-liên thông trong không gian 3D. Sau đó các phương pháp và thuật toán làm việc trên đối tượng kỹ thuật số được đề xuất và sử dụng. Năm 1989, V. Kovalevsky mở rộng tôpô ô lưới (grid cell topology) 2D của Alexandrov-Hopf lên 3D và không gian có số chiều lớn hơn. Đầu những năm 1980, bề mặt kỹ thuật số đã được nghiên cứu và phát triển sau đó.

Đa tạp kỹ thuật số (digital manifold) được nghiên cứu vào những năm 1990. Một định nghĩa đệ quy của k-đa tạp kỹ thuật số đã được Chen và Zhang đề xuất vào năm 1993. Nhiều ứng dụng đã được tìm thấy trong xử lý ảnh và thị giác máy tính.

Các kết quả chính

Tôpô kỹ thuật số đưa ra những khái niệm như tính k-kề, n-liên thông, n-thành phần. Đây là những khái niệm cơ bản để đi vào nghiên cứu ảnh số trên khía cạnh tôpô

k-kề

Trong không gian hai chiều

Hai điểm nút được gọi là 8-kề nếu nó rời nhau và tọa độ của điểm này khác với tọa độ tương ứng của điểm kia nhiều nhất là 1 đơn vị.

Ví dụ: (0,0), (0,1), (0,2), (1,0), (1,2), (2,0), (2,1), (2,2) là các điểm 8- kề của (1,1).

Hai điểm nút được gọi là 4-kề nếu nó là 8-kề và chúng chỉ khác nhau 1 tọa độ.

Ví dụ: (0,1), (1,2), (2,1), 1,0) là các điểm 4-kề của (1,1).

Trong không gian ba chiều

Hai điểm nút được gọi là 26-kề nếu nó rời nhau và tọa độ của điểm này khác nhau tương ứng với điểm kia nhiều nhất là 1 đơn vị.

Ví dụ: (0,0,0), (0,0,1), (0,0,2), (0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1), (0,2,2), (1,0,0), (1,0,1), (1,0,2), (1,1,0), (1,1,2), (1,2,0), (1,2,1), (1,2,2), (2,0,0), (2,0,1), (2,0,2), (2,1,0), (2,1,1), (2,1,2), (2,2,0), (2,2,1), (2,2,2) là các điểm 26- kề của điểm (1,1,1).

Hai điểm nút được gọi là 18-kề nếu nó là 26-kề và tọa độ của nó khác nhau nhiều nhất hai tọa độ.

Ví dụ: (0,0,1), (0,1,0), (0,1,1), (0,1,2), (0,2,1), (1,0,0), (1,0,1), (1,0,2), (1,1,0), (1,1,2), (1,2,0), (1,2,1), (1,2,2), (2,0,1), (2,1,0), (2,1,1), (2,1,2), (2,2,1) là các điểm 18- kề của điểm (1,1,1).

Hai điểm nút được gọi là 6-kề nếu nó là 26-kề và tọa độ của nó khác nhau nhiều nhất 1 tọa độ.

Ví dụ: (0,1,1), (1,0,1), (1,1,0), (1,1,2), (1,2,1), (2,1,1), là các điểm 6- kề của điểm (1,1,1).

k-liên thông

Một cách tương tự như khái niệm liên thông thông thường, tập S của các điểm nút là n-liên thông nếu S không được chia thành 2 tập con mà mỗi điểm của tập này không là n-kề với mọi điểm của tập kia.

k-thành phần

Một n-thành phần của S là một tập con khác rỗng n-liên thông của S mà một điểm bất kì trong nó không n-kề với bất kì điểm nào khác của S.

Định lý Jordan kỹ thuật số

Một k-đường cong đơn kín trong mặt phẳng kỹ thuật số ${\displaystyle \mathbb {Z} ^{2}}$ là một tập k-liên thông mà mỗi điểm k-kề đúng với 2 điểm khác trong tập.

Với k ${\displaystyle \in }$ {4,8}, đặt ${\displaystyle {\bar {k}}}$ = 8 nếu k = 4 hoặc ${\displaystyle {\bar {k}}}$ = 4 nếu k = 8.

Một trong những kết quả lý thuyết quan trọng trong tôpô kỹ thuật số là định lý Jordan kỹ thuật số, được phát biểu như sau:

Cho một k-đường cong đơn kín ${\displaystyle P}$ trong mặt phẳng kỹ thuật số ${\displaystyle \mathbb {Z} ^{2}}$ thì ${\displaystyle \mathbb {Z} ^{2}\setminus P}$ chứa đúng 2 thành phần ${\displaystyle {\bar {k}}}$-liên thông, trong đó một thành phần bị chặn được gọi là phần trong ứng với P, thành phần còn lại không bị chặn được gọi là phần ngoài ứng với ${\displaystyle P}$.

Định lý này được Rosenfeld xây đựng từ định lý đường cong Jordan. Định lý có ứng dụng quan trọng trong giải quyết vấn đề lưu trữ hiệu quả ảnh kỹ thuật số.

Việc lưu trữ ảnh cũng được thực hiện hiệu quả thông qua khái niệm và tính chất điểm đóng – điểm mở trong tôpô kỹ thuật số.

Tôpô kỹ thuật số được dùng để định nghĩa một ảnh kỹ thuật số mà quan hệ không gian giữa các tính năng thực tế vẫn được bảo toàn trong ảnh.

Tham khảo

• T.Y. Kong and A. Rosenfeld, Digital Topology: Introduction and Survey.
• Colin Adams and Robert Franzosa, Introduction to Topology pure and applied.
• Ulrich Eckhardt and Longin Jan Latecki, Digital Topology.