Cải tiến thuật toán RANSAC để phân biệt các chữ số trong hình ảnh nhiễu sử dụng Python

Tóm tắt: Trong bài báo này, nhóm tác giả đề xuất cải tiến thuật toán RANSAC để phân biệt các chữ số trong hình ảnh bị nhiễu sử dụng ngôn ngữ lập trình Python. Thuật toán cải tiến này cho phép đáp ứng một cách linh hoạt và mềm dẻo hơn so với các thuật toán trước đây. 

Ưu điểm của thuật toán RANSAC là độ bền vững, nói cách khác là RANSAC có thể tìm ra mô hình thích hợp với độ chính xác rất cao trong bộ dữ liệu thu thập được mặc dù bộ dữ liệu đó chứa nhiều điểm ngoài. Nhược điểm của RANSAC là ở chỗ không có giới hạn về thời gian tính toán các thông số mô hình. Khi số lần lặp lại bị giới hạn, giải thuật có thể không đưa ra được mô hình tối ưu. Do đó, khi thực hiện RANSAC, phải cân bằng giữa thời gian tính toán và chất lượng mô hình ước lượng được. Với số lần lặp lại càng tăng, xác suất để RANSAC đưa ra các mô hình tốt hơn cũng tăng. Một nhược điểm khác của RANSAC là giải thuật chỉ có thể ước lượng được một mô hình với mỗi bộ dữ liệu đầu vào.

Giới thiệu

Thuật toán RANSAC là thuật toán lặp với mục đích ước lượng các thông số của một mô hình toán học từ một bộ dữ liệu thu thập được bao gồm cả các điểm trong và ngoài. Các điểm trong là những điểm trong bộ dữ liệu phù hợp (hay nằm trong) mô hình toán học đó, còn điểm ngoài là những điểm không nằm trong mô hình.

Thuật toán RANSAC được công bố lần đầu bởi Fischler và Bolles, với nguyên tắc ước lượng các thông số bằng cách chọn ngẫu nhiên các mẫu trong dữ liệu thu thập được. Với tập dữ liệu đầu vào bao gồm cả các điểm trong và ngoài mô hình, thuật toán RANSAC sử dụng nhiều lần thử để tìm ra mô hình có kết quả tốt nhất.

Quá trình thực hiện của RANSAC như sau: Chọn một bộ nhỏ nhất các điểm mẫu bất kì từ dữ liệu đầu vào, giả thiết các điểm này đều là điểm trong; tính toán các thông số của mô hình chứa các điểm đó; kiểm tra tất cả các điểm còn lại trong dữ liệu đầu vào xem chúng nằm trong hay nằm ngoài mô hình dựa vào mô hình vừa tính được và sai số cho phép; mô hình vừa xấp xỉ là tốt nếu số điểm trong thỏa mãn yêu cầu; quá trình này được lặp lại để phát hiện các mô hình tốt hơn; các tham số tin cậy quan trọng trong việc thực hiện thuật toán RANSAC là ngưỡng sai số cho phép và số lần lặp lại N. Ngưỡng sai số cho phép là giá trị khoảng cách lớn nhất từ một điểm đến mô hình để điểm đó còn được coi là điểm trong. Việc xác định với từng trường hợp cụ thể thường dựa trên kinh nghiệm và ước lượng thực tế; số lần lặp lại N cũng có thể được ước lượng hợp lý để cân bằng giữa kết quả và thời gian tính toán. Số lần lặp N có thể được tính bằng phương pháp thống kê.

Giả sử p là xác suất thành công của thuật toán (thông thường p = 0.99). Gọi u là xác suất để một điểm trong tập dữ liệu thu được là điểm trong, v là xác suất để điểm đó là điểm ngoài.

Gọi m là số điểm trong để mô hình thu được là tốt, khi đó xác suất để thu được một mô hình tốt.

Trong mỗi lần thử, thuật toán thất bại khi không tìm được mô hình nào đủ tốt, tức là không có mô hình nào có đủ m điểm trong.

Xác suất để điều này xảy ra là 1-u^m

Sau N lần lặp lại, xác suất thất bại là: (1-u^m)^n=1-p

Qua đó, ta có thể tính được số lần lặp lại tối ưu với xác suất thành công:

Phần còn lại của bài báo được trình bày như sau. Trong phần II chúng tôi trình bày cơ sở toán học và thuật toán cải tiến; Phần III: Thực nghiệm. Phần VI Kết luận. 

Cơ sở toán học

RANSAC sử dụng phương pháp chọn tập con ngẫu nhiên lặp lại. Giả sử dữ liệu của chúng ta bao gồm các điểm dữ liệu trong không gian (bao gồm các điểm trong và điểm ngoại lai - outliers chưa được xác định) và tập hợp xác điểm trong có thể xấp xỉ thành một mô hình toán học (vd trong trường hợp này là 1 đường thẳng trong không gian 2 chiều), và những điểm ngoại lai là những điểm không phù hợp với mô hình này. RANSAC giả định rằng luôn có 1 tập hợp nhỏ các điểm trong, sao cho tồn tại một mô hình toán học thỏa mãn được tập hợp điểm dữ liệu đó với 1 sai số cho phép. 

Đầu vào của thuật toán RANSAC là một tập hợp các điểm dữ liệu, một cách để điều chỉnh một số loại mô hình với các quan sát và một số tham số tin cậy. RANSAC đạt được mục tiêu của mình bằng cách lặp lại các bước sau: Chọn một tập hợp con ngẫu nhiên của dữ liệu gốc. Gọi tập hợp con này là tập hợp con giả định; một mô hình được xây dựng từ tập hợp giả định; mô hình này sẽ kiểm tra tất cả các điểm dữ liệu khác. Những điểm phù hợp tốt với mô hình với một sai số nhất định, được coi là một phần của tập hợp đồng thuận; một mô hình là tốt nếu có đủ nhiều điểm được xếp vào tập hợp đồng thuận. Sau đó, mô hình có thể được cải thiện bằng cách sử dụng tất cả các điểm dữ liệu trong tập hợp đồng thuận.

Quy trình này được lặp đi lặp lại một số lần nhất định, mỗi lần tạo ra một mô hình, mô hình này sẽ có 2 trường hợp: Bị từ chối vì có quá ít điểm đồng thuận hoặc có nhiều điểm đồng thuận hơn so với các mô hình trước đó.

Để đạt được xác suất thành công là p thì chúng ta sẽ cần số vòng lặp là:

Trong đó: s là kích thước tập con và epsilon là tỉ lệ nhiễu trong dữ liệu.

Ý tưởng cải tiến thuật toán RANSAC như sau: Từ tập dữ liệu ban đầu, ta sẽ có hai loại dữ liệu nhiễu và không nhiễu (outlier và inlier), vì thế ta phải đi tính toán để tìm ra mô hình tốt nhất cho tập dữ liệu. Việc tính toán và chọn ra mô hình tốt nhất sẽ được lặp đi lặp lại k lần, với giá trị k được chọn sao cho đủ lớn để đảm báo xác suất p (thường rơi vào giá trị 0.99) của tập dữ liệu mẫu ngẫu nhiên không chứa dữ liệu nhiễu.

Với ma trận Homography được tính từ bốn cặp điểm ngẫu nhiên, ta có d là khoảng cách đo mức độ gần nhau của các cắp điểm đã được so sánh đối chiếu. Với cặp điểm nổi bật tương đồng và 
là khoảng cách của hai vector, ta có công thức khoảng cách như sau:

Thuật toán chi tiết:

Khởi tạo số vòng lặp k, ngưỡng distance, maxinlier và p = 0.

For (i = 1: k), thực hiện các bước sau:

Bước 1: Chọn 4 cặp điểm tương đồng ngẫu nhiên.

Bước 2: Kiểm tra xem các điểm có nằm trên cùng một đường thẳng hay không.

Bước 3: Tính ma trận Homography H từ 4 điểm sử dụng phương pháp DLT chuẩn hóa.

Bước 4: Tính khoảng cách d của các cặp điểm nổi bật tương đồng.

Bước 5: Tính số lượng m các cặp điểm không ngẫu nhiên (inlier) thỏa điều kiện: di < distance.

Bước 6: Nếu m > maxinlier thì maxinlier = m, ma trận Homography

H = Hcurr

Tiếp tục tính lại ma trận H cho tất cả các cặp điểm tương đồng được coi là không nhiễu (inlier) bằng phương pháp DLT.

Trong toán học, Homography là sự dịch chuyển sử dụng phép chiếu hình học, hay nói cách khác nó là sự kết hợp của cặp điểm trong phép chiếu phối cảnh. Ảnh thực trong không gian ba chiều có thể biến đổi về không gian ảnh bằng phép chiếu thông qua ma trận biến đổi Homography hay còn gọi là ma trận H. Các phép chiếu biến đổi thông qua ma trận Homography không đảm bảo về kích thước và góc của vật được chiếu nhưng lại đảm bảo về tỷ lệ.

Trong lĩnh vực thị giác máy, Homography là một ánh xạ từ mặt phẳng đối tượng đến mặt phẳng ảnh. Ma trận homography thường có liên quan đến các công việc xử lý giữa hai ảnh bất ký và có ứng dụng rất sộng rãi trong các công tác sửa ảnh, ghép ảnh, tính toán sự chuyển động, xoay hay dịch chuyển giữa hai ảnh.

Ta có công thức sau: HX = sX’

Trong đó:

s: là hằng số tỉ lệ của phép chiếu và khác 0.

X’: là kết quả của phép ánh xạ.

X: là đối tượng ảnh được ánh xạ.

H: là ma trận Homography, là một ma trận khả nghịch.

Vì H là một ma trận khả nghịch, cho nên, trong trường hợp muốn tái tạo ảnh X từ X’, ta chỉ cần xác định được ma trận Homography.

Để tính ma trận Homography từ các cặp điểm tương ứng, người ta dùng phương pháp DLT (Direct Linear Transform), gồm có 2 bước: Đầu tiên, từ các cặp điểm tương ứng, ta chuyển về dạng ma trận Aih = 0. Sau đó, áp dụng phân rã SVD để tính ma trận H.

Phương pháp DLT với các điểm nổi bật được tìm thấy từ thuật toán Harris:

Trong tọa độ không đồng nhất, ta có công thức:

Lần lượt chia dòng thứ nhất của công thức trên cho dòng thứ ba và dòng thứ hai cho dòng thứ ba, ta có: 

Viết dưới dạng ma trận ta có:

Với mỗi cặp điểm tương ứng, ta có hai biểu thức. Mặt khác, do ma trận là ma trận có bậc tự do (D.O.F) là 8 nên chỉ cần 4 cặp điểm tương ứng là ta có thể xác định được nó.

Áp dụng công thức phân rã SVD cho ma trận [A] ta có: 

Với si là các giá trị đơn và được sắp xếp nhỏ dần, nên s9 là giá trị nhỏ nhất. Khi đó, giá trị của hi bằng giá trị cuối cùng của cột vi.

Theo lý thuyết, với 4 cặp điểm tương ứng sẽ tìm được một ma trận H với D.O.F bằng 8. Tuy nhiên, trong thực tế các ảnh đầu vào có thể có gốc tọa độ ở góc trái của ảnh, cũng có thể gốc tọa độ nằm ở tâm ảnh. Nếu để tình trạng như vậy sẽ ảnh hưởng đến các kết quả biến đổi về sau như khi nhân ảnh với một hệ số hay các biến đổi tương tự, affin. Do vậy, Hartley và Zisserman đã đưa ra bước chuẩn hóa để đảm bảo rằng kết quả của thuật toán sẽ cho ra kết quả chính xác. Các ảnh cần phải chuẩn hóa bằng phép biến đổi quay và dịch chuyển.

Thực nghiệm

Dữ liệu đầu vào

Nhóm tác giả đã dưa ba hình ảnh có cấu trúc giống nhau. Ảnh thứ 1 và ảnh thứ 3 là ảnh thể hiện đầy đủ và rõ các con số trong CMTND, còn ảnh thứ 2 là thể hiện sự nhiễu các con số.

Ảnh 1

Ảnh 2

Ảnh 3

Code Python mô tả thuật toán RANSAC cải tiến

import pytesseract

from PIL import Image

import tkinter as tk

from tkinter import filedialog

pytesseract.pytesseract.tesseract_cmd = r’C:\Program Files\Tesseract-OCR\tesseract.exe’

# Hàm để trích xuất ID card từ ảnh và cập nhật giao diện

def trich_xuat():

 duong_dan = filedialog.askopenfilename()

 if duong_dan:

 image = Image.open(duong_dan)

 text = pytesseract.image_to_string(image)

 id_card_number = Tim_IdCard(text)

 if id_card_number:

 nhan_id.config(text=”Số căn cước công dân: “ + id_card_number)

 else:

 nhan_id.config(text=”Không tìm thấy số nào trên thẻ căn cước công dân.”)

# Hàm để tìm chuỗi số liên tiếp dài nhất trong văn bản

def Tim_IdCard(text):

 current_ID = “”

 longest_ID = “”

 for char in text:

 if char.isdigit():

 current_ID += char

 else:

 if len(current_ID) > len(longest_ID):

 longest_ID = current_ID

 current_ID = “”

Kết quả thực nghiệm

Kết quả thực nghiệm dựa trên Python với dữ liệu đầu vào và thu lại kết quả sau:

Kết quả ảnh số 1:

Kết quả ảnh số 2:

Kết quả ảnh số 3:

Kết luận

Trong bài báo này, nhóm tác giả đề xuất cải tiến thuật toán RANSAC, đồng thời, cũng chứng minh được tính đúng đắn và kết quả thực nghiệm của thuật toán. Hướng nghiên cứu tiếp theo sẽ là áp dụng thuật toán này cho các kiểu nhận dạng khác nhau như nhận dạng hình khuôn mặt dựa trên bài toán logarith rời rạc, đường cong elliptic, đồng thời, chúng tôi sẽ triển khai thực nghiệm trên nhiều hình ảnh khác nhau cùng 1 lúc. Bằng việc cho phép các dữ liệu và các thành phần có thể thay đổi tùy ý và không phụ thuộc nhau, thuật toán này có khả năng ứng dụng cao, đáp ứng các nhu cầu phong phú trong thực tiễn. 

Tài liệu tham khảo

1. Nguyễn Đức Toàn, Đặng Minh Tuấn “Về một lược đồ chữ ký số tập thể ủy nhiệm dựa trên hệ mật ID- Based”, Hội thảo Khoa học và công nghệ CEST, tr193- 198, NXB Thông tin và Truyền thông, ISBN 978- 604- 80- 2642- 4, 2017;

2. Đặng Minh Tuấn, “Lược đồ chữ ký số tập thể đa thành phần dựa trên cặp song tuyến tính”, Tạp chí nghiên cứu khoa học và công nghệ quân sự, Đặc san 5- 2012, pp. 10- 5. 2012;

3. Adrian Rosebrock, “Image Difference with OpenCV and Python”, June 19, 2017;

4. Deepanshu Tyagi, “Introduction to ORB (Oriented FAST and Rotated BRIEF)”, Jan 1, 2019.

LÊ PHÚ HƯNG, NGUYỄN VĂN SUYÊN

Khoa Công nghệ thông tin, Trường Đại học TN&MT Hà Nội

Nguồn: Tạp chí Tài nguyên và Môi trường số 3 năm 2024