CHƯƠNG I TỔNG QUAN VỀ ẢNH SỐ
3. Các thuật toán về phân cụm màu cho bài toán rút gọn màu
Vấn đề nhận thức về màu sắc là một vấn đề khá phức tạp, nó dường như không tuân theo một hàm toán học cụ thể nào. Ngày nay, khoa học công nghệ chỉ chấp nhận ảnh màu mà màu sắc của nó được thể hiện như màu thật (24 bit màu – 16 triệu màu). Tuy nhiên, tùy thuộc vào từng ảnh cụ thể mới biết là có thể hiển thị ở dải màu cao hay không. Quá trình phân cụm ảnh là cần thiết đối với một số lý do.
Phép phân cụm là một kỹ thuật quan trọng trong lĩnh vực phân tích dữ liệu đang phát triển một cách nhanh chóng và được áp dụng trong các loại công nghệ và các môn khoa học như: sinh vật học, tâm lý học, y khoa, tiếp thị vv.
Quá trình phân cụm này tập hợp dữ liệu bằng cách đưa ra cấu trúc cơ bản như một nhóm các phần tử hoặc một hệ thống có thứ tự các nhóm. Quá trình thực hiện này có thể sẽ được nghiên cứu một cách tỉ mỉ nhằm biết được liệu nhóm dữ liệu đó có phù hợp với ý tưởng ban đầu hay không hoặc nhằm đưa ra các thí nghiệm khác. Quá trình phân cụm là công cụ cho việc phát triển cấu trúc dữ liệu mà không cần các giả định thông thường như các phương pháp thống kê khác.
Quá trình phân cụm là quá trình nghiên cứu chính thức về các thuật toán và các phương pháp nhóm, hoặc phân loại các đối tượng. Một đối tượng được
mô tả không chỉ bằng một tập các kích thước mà còn bằng cả quan hệ của vật thể này với vật thể khác. Quá trình phân cụm không sử dụng các loại cấu trúc để kết nối các đối tượng cùng loại. Các thuật toán phân cụm đều hướng tới việc tìm ra cấu trúc của dữ liệu.
Một phân cụm được xác định bao gồm một số các đối tượng giống nhau hoặc các nhóm với nhau.
Quá trình phân cụm có thể được dịnh nghĩa như sau:
+ Một phân cụm là một tập các đối tượng tương đối giống nhau, và các đối tượng này thuộc các cụm khác nhau.
+ Một phân cụm là một khối tập hợp các điểm trong không gian thử nghiệm như: khoảng cách của hai điểm bất kỳ trong một cụm nhỏ hơn khoảng cách giữa một điểm bất kỳ bên trong cụm với điểm bất kỳ ngoài cụm.
+ Các cụm có thể được biểu diễn như các miền liên kết của một không gian nhiều chiều gồm các điểm có quan hệ tương đối.
Các kỹ thuật phân cụm có một số lợi thế trong quá trình phân nhóm thông thường.
Thứ nhất, một chương trình phân cụm có thể áp dụng các tiêu chuẩn khách quan cho trước một cách phù hợp để tạo thành các nhóm. Con người khá hiệu quả trong việc xác định các cụm trong không gian hai hoặc ba chiều, tuy nhiên các thành phần khác nhau không thường được coi như nhau trong cùng một cụm dữ liệu.
Thứ hai, một thuật toán phân cụm có thể tạo thành các nhóm trong một khoảng nhỏ thời gian. Đồng thời nó làm giảm gánh nặng của các nhà khoa học hoặc giảm quá trình xử lý khi không chắc chắn trong việc xác định ma trận mẫu hoặc ma trận giống với các cụm đã tìm được
Các phép phân cụm là một yếu tố quan trọng trong các quá trình phân tích dữ liệu. Thông tin thu được về một tập dữ liệu từ các phép phân tích cụm sẽ gợi ra sự sáng tạo của từng người, đưa ra các thử nghiệm mới.
Phân cụm là một quá trình phân loại trên một tập các đối tượng đã xác định trước. Như ta đã biết, mối liên hệ của các đối tượng được biểu diễn trong một ma trận quan hệ, trong đó, các hàng hay cột tương đương với các đối tượng đó. Nếu các đối tượng được biểu diễn dưới dạng các mẫu hay các điểm trong một không gian ma trận d chiều thì khi đó các quan hệ là khoảng cách giữa các cặp điểm, ví dụ như khoảng cách Euclid. Phân cụm là một quá trình phân loại đặc biệt.
Ta xét một biểu đồ cây các bài toán phân loại. Trong đó, mỗi một nhánh là một vấn đề phân loại khác nhau. Các định nghĩa của từng vấn đề được định nghĩa như sau:
Quan hệ duy nhất đối với không duy nhất
Một quá trình phân loại duy nhất là quá trình phân chia tập các đối tượng, mỗi đối tượng thuộc một tập con hoặc một cụm xác định. Quá trình phân loại không duy nhất hoặc trùng nhau thì có thể gán cho một số lớp. Ví dụ, một nhóm người cùng độ tuổi hoặc cùng giới tính thì là duy nhất, trong khi đó nhóm các đối tượng cùng loại bệnh thì là không duy nhất vì một người có thể có một vài bệnh cùng một lúc. Phân cụm mờ là một loại phân cụm không duy nhất, trong đó, mỗi loại được gán cho một cụm cụ thể.
Quan hệ thực tế đối với không thực tế
Quá trình phân loại thực tế chỉ sử dụng ma trận quan hệ để xác định dạng phân loại. Phương pháp phân loại này được gọi là “kỹ năng không bị giám sát”. Quá trình phân loại không thực tế sử dụng các dạng phạm trù trên các đối tượng tốt như với ma trận quan hệ. Khi đó bài toán xác định một mặt biệt số chia đối tượng theo các phạm trù (định nghĩa) này. Một cách để đánh giá phương pháp phân loại thực tế là phải xem các loại phân cụm như thế nào. Gán các đối tượng theo các cụm, đặt tên các cụm. Ví dụ, giả sử
rằng các chỉ số khác nhau của sức khỏe người bệnh được lấy từ những người hút thuốc và những người không hút thuốc, phương pháp phân loại thực tế sẽ phân loại dựa trên các đặc tính giống nhau về chỉ số sức khỏe sau đó xác định tại sao hút thuốc là một nhân tố trong xu hướng lựa trọn của mỗi người. Trong khi đó, phép phân loại không thực tế nghiên cứu cách của những người hút thuốc dựa trên những người không hút thuốc trên cơ sở của các chỉ số sức khỏe
Mục đích chính của việc phân cụm và nén ảnh màu là để xác định màu nào được xuất hiện chủ yếu trong ảnh kết quả.
Phân cụm ảnh là quá trình xử lý, chia nhỏ tập dữ liệu đầu vào thành một số cho trước các nhóm nhỏ mà trong đó các thành phần của cùng một nhóm nhỏ thì giống nhau, các thành phần của các nhóm khác nhau có các thuộc tính khác nhau. Đã có rất nhiều thuật toán, các phương pháp tính khác nhau được áp dụng cho vấn đề phân cụm. Trong đó phải kể đến như: thuật toán chung, thuật toán Octree, phép biến đổi Dirichlet, biến đổi Cosin rời rạc, thuật toán C-trung vị mờ…
Khi áp dụng quá trình phân cụm cho một bức ảnh thì các phương pháp này đều được sử dụng để tạo ra các nhóm pixel giống nhau theo một tiêu chuẩn nhất định, thường là mức màu hoặc mức xám. Do đó sẽ làm đơn giản một bức ảnh bằng cách giảm bớt một số các pixel rời rạc có thể chấp nhận được.
Các thuật toán phân cụm nhìn chung có thể được phân ra theo hai loại phương pháp như sau:
+ Các phương pháp phân cụm theo thứ tự (các thuật toán tập hợp, các thuật toán tách rời)
+ Các phương pháp phân cụm theo sự phân chia (Phân cụm theo xác suất, các phương pháp K- trung vị…)
A. Phân cụm theo thứ tự
Tạo nên thứ tự các cụm. Mỗi nút cụm bao gồm các cụm con, các cụm anh em phân chia các điểm được bao bởi bố mẹ chung của chúng. Các phương pháp phân cụm theo thứ tự được phân ra thành hai loại, phương pháp tập hợp (bottom up) và phương pháp tách rời (Top- down). Thuật toán phân cụm tập hợp bắt đầu với các cụm một điểm và hợp nhất một cách đệ quy hai hay nhiều cụm thích hợp. Phương pháp phân cụm tách rời bắt đầu với một cụm của tất cả các điểm dữ liệu và tách một cách đệ quy các cụm thích hợp. Quá trình xử lý này vẫn tiếp tục cho đến khi đạt được một chuẩn dừng.
• Quá trình phân cụm theo thứ tự
Phương pháp phân cụm theo thứ tự là một thủ tục của việc biến đổi từ một ma trận không gian sang một dãy quá trình phân chia được lồng vào nhau. Một thuật toán phân cụm theo thứ tự là một đặc điểm của việc biểu diễn một quá trình phân cụm theo thứ tự. Nó là những thuận lợi cho việc mô tả một phương pháp phân cụm theo thứ tự bằng cách viết thuật toán. Nhưng thuật toán phải được chia ra theo các phương pháp của nó.
Để xác định các thuật toán và các phương pháp này ta xác định dạng của cấu trúc toán học của một thuật toán phân cụm theo dữ liệu và mô tả cách thể hiện cấu trúc đó.
Trước hết ta xét khái niệm một dãy các phần phân chia lồng với nhau.
Tập n các phần tử được phân cụm biểu diển bởi tập H H ={x x1, ,...,2 xn}
Trong đó: xi là phần tử thứ i. Một mảng C của H chia H thành các tập con {C1, C2,…,Cm} thỏa mãn:
Ci∩Cj = Φ với i , j chạy từ 1 đến m i≠ j.
1 2 ... m
C ∪C ∪ ∪C =H
Trong các ký hiệu đó: ∩ ký hiệu cho tập các điểm giao nhau,∪ ký hiệu cho tập các điểm hợp nhau, và Φ là tập rỗng.
Mỗi phân cụm là một sự phân chia, các thành phần của sự phân chia đó được gọi là các cụm.
Mảng B được gọi là ẩn trong mảng C nếu mọi phần tử của mảng B là tập con của một phần tử mảng C. Ví dụ, phân cụm C với 3 cụm và phân cụm B với 5 cụm được định nghĩa như trên, khi đó B được gọi là ẩn trong mảng C.
Cả C và B được gọi là tập của các phần tử {x1, x2, …, x10}
( ) ( ) ( )
{ }
( ) ( ) ( ) ( ) ( )
{ }
1 3 5 7 2 4 6, 8 9 10
1 3 5 7 2 4 6 8 9 10
, , , , , , , ,
, , , , , , , , ,
C x x x x x x x x x x
B x x x x x x x x x x
=
=
C và B đều không được lắp vào lớp dưới đây, và lớp này cũng không được lắp với chúng:
( ) ( ) ( )
{ x x x x1, , ,2 3 4 , x x x x5, , ,6 7 8 , x x9, 10 }
Một phân cụm theo thứ tự là một dãy các lớp, trong đó mỗi lớp được lồng vào một lớp bên cạnh nó trong dãy, một thuật toán phân cụm theo thứ tự bắt đầu với nhóm tách rời nhau, trong mỗi nhóm có chứa n phần tử của nhóm đó.
Thuật toán phân cụm sử dụng lệnh gọi các ma trận quan hệ phải được biến đổi sao cho thỏa mãn với hai hoặc nhiều hơn các cụm riêng lẻ này, do đó kết hợp được các cụm riêng lẻ vào trong một lớp khác. Quá trình xử lý được lặp lại đến khi thiết lập được một dãy các cụm được lồng vào nhau, số lượng cụm tăng tùy thuộc vào quá trình xử lý cho đến khi mỗi cụm có n phần tử.
Hai phương pháp phân cụm đặc trưng đã được định nghĩa là phương pháp liên kết đơn lẻ và phương pháp liên kết toàn bộ. Hai phương pháp này không bị giới hạn bởi nguồn dữ liệu gốc.
- Ta tìm hiểu thuật toán liên kết đơn và liên kết toàn bộ theo lý thuyết đồ họa:
+ Thuật toán phân cụm + Thuật toán Hubert
…
B. Các thuật toán theo phương pháp phân cụm
Chia dữ liệu thành một số tập dữ liệu nhỏ. Không giống như phương pháp phân cụm theo thứ tự, các cụm không được xem lại sau khi được phân chia, các thuật toán cải tiến các cụm một cách từ từ.
Quá trình phân cụm còn được sử dụng để hỗ trợ việc tìm nhanh. Các công cụ tìm nhanh bổ sung cho các công cụ tìm kiếm. Gần đây, phân cụm còn được sử dụng để nhận ra các loại vật thể. Việc phân cụm còn có tác dụng trong việc kết luận các đặc tính của một bộ sưu tập. Theo một cách nào đó thì đây được gọi là quá trình thăm dò phân tích dữ liệu.
Việc xác định một phép biểu diễn đúng tùy thuộc ứng dụng của nó và tập dữ liệu đầu vào. Các biểu đồ màu sẽ hoạt động tốt nếu có một tập lớn các
giá trị ảnh đã được phân loại. Nếu bộ sưu tập ảnh bao gồm khuôn mặt của một người, thì phép biểu diễn ảnh đúng sẽ quan tâm đến kiểu dáng, quá trình chiếu sáng, độ chói…
Hầu hết các thuật toán phân cụm đều dựa trên các đặc trưng hoặc các khả năng đã biết trước, chẳng hạn như cơ sở phân chia phổ thông, cơ sở về mật độ có thứ tự, cơ sở lưới.
Ta định nghĩa quá trình phân cụm là việc chia các dữ liệu đầu vào thành một số cho trước các tập nhỏ mà khoảng cách Euclidean giữa mỗi điểm dữ liệu với tâm cụm của nó là nhỏ nhất. Tổng của các khoảng cách của mỗi điểm đến tâm cụm của nó được hiểu là tổng khoảng cách của các cụm và được tính bằng công thức:
E = 2
1 1
( )
K A
a a
k x Ck a
x mk
= ∈ =
∑ ∑ ∑ − Trong đó:
K : là số cụm
x : đặc trưng cho một điểm dữ liệu Ck : tương ứng với cụm k
mk : biểu diễn giá trị trung bình của cụm k A : là tổng các thuộc tính của một điểm dữ liệu
Công thức này có thể tính một cách đơn giản khoảng cách Euclide của mỗi điểm trong tập dữ liệu đầu vào với tâm cụm của nó. Cực tiểu hóa tổng khoảng cách này cho ta giải pháp phân cụm tối ưu. Vấn đề là phải làm sao để phát triển cả thuật toán về sai số, và cả thuật toán chính xác cho các yêu cầu phân cụm khác nhau, tuy nhiên, các giải pháp đều không thực tế vì cả số điểm dữ liệu trong tập dữ liệu đầu vào và số cụm nhận được đều rất lớn.
• Thuật toán phân cụm tổng quát
Như ta đã nói ở trên, các thuật toán đều trở nên không thực tế vì tập dữ liệu đầu vào là rất lớn. Theo như sơ đồ quá trình thực hiện của các thuật toán
tổng quát thì cấn có một gene trong nhiễm thể đối với mỗi điểm trong tập dữ liệu. Rõ ràng là, sơ đồ này không thể dùng đối với các tập dữ liệu quá lớn vì bộ nhớ đòi hỏi duy trì dung lượng hạn chế. Nếu tập dữ liệu đầu vào bao gồm một triệu vật thể với 6 thuộc tính và một thuật toán tổng quát thực hiện bao gồm 50.000 phép tính, điều này là không đơn giản, khi đó ước tính sẽ có khoảng 3 x 1011 phép tính được thực hiện thi thực hiện quá trình phân cụm.
Để giải quyết vấn đề này, ta cần sử dụng các kỹ thuật có hiệu quả như các kỹ thuật mã hóa trong quá trình xử lý của thuật toán tổng quát. Hơn nữa, việc xử lý trước các dữ liệu đầu vào cũng có thể là một cách hiệu quả để giảm một cách đáng kể thời gian tính toán của các thuật toán phân cụm đối với các tập dữ liệu quá lớn. Việc xử lý trước được áp dụng vào các thuật toán phân cụm. Các kết quả của quá trình tiền xử lý trong một tập dữ liệu nhỏ sau đó có thể được sử dụng như phép biểu diễn của tập dữ liệu đầy đủ.
Hai cách của quá trình tiền xử lý là: quá trình lấy mẫu và quá trình tổng hợp. Quá trình lấy mẫu từ tập dữ liệu đầu vào là không phức tạp. Tuy nhiên, quá trình tổng hợp lại là quá trình khá phức tạp. Các thuật toán khác nhau đã được phát hiện ra để thực hiện công việc tổng hợp các tập dữ liệu. Thuật toán tổng quát dùng để áp dụng cho các tập dử liệu quá lớn, chẳng hạn như các tập dữ liệu ảnh.
Dữ liệu đầu vào của thuật toán tổng quát là một tập dữ liệu với số cụm xác định. Mục đích của thuật toán là để chia tập dữ liệu ra thành một số cho trước các cụm mà khoảng cách Euclide giữa mỗi điểm dữ liệu và tâm cụm của nó là nhỏ nhất.
• Thuật toán K-mean (K- trung vị)
K Means là một thuật toán nổi tiếng do Mac Queen đề xuất năm 1967 để giải quyết bài toán phân cụm dữ liệu. Mục đích của KMeans là tạo ra các cụm dữ liệu trong số các dữ liệu đó. Do đó, nếu chạy KMeans trên một số dữ liệu thì sau đó ta sẽ thu được “K” cụm của các dữ liệu đó. Các cụm này được tạo thành dựa trên một số các thuộc tính đặc trưng cơ bản của dữ liệu.
Ta phải xác định “K” trước và xác định trước cho thuật toán một ước lượng trọng tâm của “K” cụm này. Lưu ý rằng, việc đưa ra hai tham số này không phải lúc nào cũng thỏa mãn yêu cầu, và đây là một hạn chế của thuật toán này- trong trường hợp đó cần phải sử dụng biến thiên của KMeans thay cho phương pháp cơ bản.
Vậy ta sẽ tìm hiểu KMeans tác động như thế nào tới những bức ảnh. Thuật toán này sẽ tìm ra cho ta các cụm của các mầu khác nhau và đưa ra một bức ảnh với sự phân đoạn về màu sắc.
Như ta đã biết, dữ liệu ảnh là các pixel màu. Ta cũng cần phải đưa cho thuật toán một số cụm cho trước. Do ảnh số còn có đặc trưng riêng đó là số dải màu (Band) trên mỗi ảnh, nên khi thực hiện phân cụm ảnh ta phải quan tâm đến tham số này như là một tham số đầu vào. Chú ý là với bất kỳ thuật toán phân cụm nào cũng không thể đảm bảo vét hết tất cả các phần tử của dữ liệu ban đầu, do đó ảnh hiển thị sau khi phân cụm thường sẽ bị hiện tượng mốc do mất dữ liệu.
Thuật toán K-mean
1/. Đưa ra một số cho trước các cụm;
2/. Đưa ra hoặc lấy ngẫu nhiên tập của tâm các cụm này;
3/. Đối với dữ liệu:
+ Tìm khoảng cách giữa các tâm của các cụm với các điểm còn lại;
+ Đưa các điểm về với cụm có khoảng cách đó ngắn nhất;