ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thị Thuỷ

NGHIÊN CỨU MỘT SỐ KỸ THUẬT
NẮN CHỈNH VÀ ỨNG DỤNG
LUẬN VĂN THẠC SỸ

2.3. Nắn chỉnh trên cơ sở phân vùng ảnh 32
2.3.1. Phân hình tam giác 32
2.3.2. Phân hình tứ giác 34
2.3.3. Kỹ thuật biến đổi dựa trên lưới B-Spline 35
2.4. Kỹ thuật nắn chỉnh dựa trên hàm radial 37
2.4.1. Xác định hàm ánh xạ 37

2
2.4.2. Phân loại RBFT 38
2.4.3. Lựa chọn hàm cơ sở g 40
2.4.4. Tính giải được 41
2.4.5. Nhận xét 44
2.5. Nắn chỉnh dựa trên biên của đối tượng 46
2.5.1. Các khái niệm cơ bản 46
2.5.2. Phương thức Peel-and-resample 48
2.5.3. Phương thức lan truyền sóng 53

Chương 3. ỨNG DỤNG NẮN CHỈNH BIẾN DẠNG 57
3.1. Nắn chỉnh sách 57
3.1.1. Bài toán 57
3.1.2. Tạo mẫu sách 57
3.1.3. Thuật toán nắn chỉnh khung đối tượng 58
3.1.4. Thuật toán biểu diễn bề mặt 59
3.2. Nắn chỉnh răng 61
3.2.1. Bài toán 61
3.2.2. Cấu tạo mặt người 61
3.2.3. Hệ thống mã hóa các hành vi của khuôn mặt 66
3.2.4. Chương trình nắn chỉnh răng 67

3

Hình 1.5. Quá trình biến đổi của con cóc 20
Hình 1.6. Biến đổi của một cái ống 20
Hình 1.7. Các hình dạng của cùng một lớp 21
Hình 1.8. Ba trạng thái tiến hóa của con 21

4
Hình 1.9. Dùng kỹ thuật nắn chỉnh để tạo ra dãy hoạt hình của quả bóng 22
Hình 1.10. Cross dissolve 23
Hình 1.11. Cái ống bị biến đổi do thu hẹp, uốn cong, xoắn 23
Hình 1.12. Đối sánh hình 24
Hình 2.1. Ảnh thu nhận , Ảnh mong muốn 27
Hình 2.2. Cặp đoạn thẳng đơn 29
Hình 2.3. Ví dụ minh hoạ 29
Hình 2.4. Nhiều cặp vector 31
Hình 2.5. Kết quả của thuật toán 31
Hình 2.6. Nội suy tam giác 32
Hình 2.7. Hệ toạ độ Barycentric 33
Hình 2.8. Phép nội suy Bilinear 34
Hình 2.9. Kết quả phép nội suy Bilinear 34
Hình 2.10. Khung lưới B-Spline của hai ảnh 35
Hình 2.11. Xác định các điểm tương ứng cho mỗi đường quét 36
Hình 2.12. Trái:Ba hàm radial với tham số cục bộ thảo luận trong bài. 42
Hình 2.13. RBFT sử dụng một điểm điều khiển 45
Hình 2.14. Chỉnh sửa đặc trưng khuôn mặt 46
Hình 2.15. ý tưởng ánh xạ biên trong nắn chỉnh ảnh 47
Hình 2.16. Nguyên lý nắn chỉnh dùng phép erosion 49
Hình 2.17. Xác định biên sử dụng phép dilation 50
Hình 2.18. Kết quả của phương thức peel-and-resample 52
Hình 2.19. Dùng ràng buộc liên kết để duy trì quan hệ láng giềng 54
Hình 2.20. Nắn chỉnh ảnh dùng phương thức lan truyền sóng 55

Trong những năm gần đây công nghệ thông tin phát triển với tốc độ
chóng mặt về cả phần cứng và phần mền. Sự phát triển của công nghệ thông
tin đã thúc đẩy sự phát triển của nhiều lĩnh vực xã hội khác như y học, giáo
dục, giải trí, kinh tế v.v Sự phát triển của phần cứng cả về phương diện thu
nhận, hiển thị, cùng với tốc độ xử lý đã mở ra nhiều hướng mới cho sự phát
triển phần mềm, đặt biệt là Công nghệ xử lý ảnh cũng như Công nghệ thực tại
ảo đã ra đời và thâm nhập mạnh mẽ vào đời sống của con người. Nắn chỉnh
biến dạng cũng không nằm ngoài quy luật phát triển đó. Ban đầu nắn chỉnh
biến dạng chỉ là các ứng dụng có tính chất sửa lỗi mà các hệ thống phần cứng
không thể khắc phục được. Chẳng bao lâu sau nó là thành phần không thể
thiếu trong nhận dạng và đối sánh, chẳng hạn nhận dạng tội phạm tự động
trong ngành công an thay vì phải cầm ảnh của họ để đối chiếu với hàng trăm
đối tượng đáng nghi khác có trong máy tính, hoặc xác định độ trùng khớp của
một đối tượng với tập đối tượng cho trước trong khảo cổ học để nghiên cứu
quá trình tiến hóa của sự vật, hiện tượng v.v Các nhà làm phim cũng nhờ đến
nắn chỉnh biến dạng để tạo ra các thước phim miêu tả sự thay đổi của một đối
tượng theo thời gian hoặc quá trình biến đổi từ đối tượng này đến đối tượng
khác với chất lượng không thua kém gì các thước phim sử dụng thiết bị thu
nhận. Rõ ràng bài toán nắn chỉnh biến dạng rất có ý nghĩa đối với sự phát

7
triển của xử lý ảnh nói chung và sự phát triển của xã hội nói riêng.
Hiện nay, nắn chỉnh biến dạng đã xâm nhập vào một lĩnh vực hết sức
mới mẻ và khó khăn vì nó có liên quan đến tính mạng con người. Đó là lĩnh
vực y học. Cụ thể là ứng dụng trong các thẩm mỹ viện. Trong những năm gần
đây, đời sống xã hội được nâng cao, người dân có điều kiện để quan tâm hơn
đến vẻ đẹp của mình, nhất là khuôn mặt. Đứng trước nhu cầu đó, nhiều trung
tâm chăm sóc sắc đẹp đã ra đời. Người ta có thể chỉnh sửa mí mắt, nâng mũi,
sửa hàm răng, thay đổi kiểu tóc v.v Nhưng không phải ai sửa cũng đẹp lên,
trong trường hợp này tôi muốn đề cập đến “độ phù hợp” của các đối tượng

Các kỹ thuật được trình bày dựa vào đặc trưng được xác định để phục
vụ cho nắn chỉnh. Đặc trưng đó có thể là điểm điều khiển, phân vùng ảnh,
vector, biên của đối tượng v.v
Chương 3: Ứng dụng nắn chỉnh biến dạng
Trong luận văn này trình bầy ứng dụng nắn chỉnh sách dựa trên các
điểm đặc trưng và nắn chỉnh răng dựa trên phân vùng ảnh. Kèm theo là một
số kết quả cài đặt của hai ứng dụng này.

9
Chương 1-
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ NẮN CHỈNH
BIẾN DẠNG

1.1. Xử lý ảnh và vấn đề cơ bản trong xử lý ảnh [11]
1.1.1. Xử lý ảnh là gì
Xử lý ảnh là một lĩnh vực đang được quan tâm và đã trở thành một môn
học chuyên ngành của các sinh viên hệ kỹ sư, hệ cử nhân ngành công nghệ
thông tin. Xử lý ảnh có liên quan đến nhiều ngành khác nhau như: hệ thống
tin học, lý thuyết thông tin, lý thuyết thống kê, trí tụê nhân tạo, nhận dạng
v.v Trong những năm qua, xử lý ảnh đã đạt được nhiều thành tựu đáng khích
lệ.
Xử lý ảnh là khoa học thao tác trên hình ảnh. Nó bao trùm một phạm vi
rộng lớn của các kỹ thuật hiện đang được ứng dụng rất nhiều. Ví dụ như các
kỹ thuật làm nổi bật hình ảnh, tăng độ sáng của một số đường nét vùng ảnh,
tạo một ảnh mới từ các vị trí của các ảnh khác, phục hồi ảnh, nắn chỉnh biến
dạng v.v
Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào
nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh
có thể là một ảnh “tốt hơn” hoặc một kết luận.


tử ảnh) và Grey level (mức xám), tiếp theo là tóm tắt các vấn đề chính.
 Pixel (Picture Element): phần tử ảnh
Ảnh trong thực tế là một ảnh liên tục về không gian và về giá tri độ
sáng. Để có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hóa ảnh.
Trong quá trình số hóa, người ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc
thông qua quá trình lấy mẫu (rời rạc hóa về không gian) và lượng hóa thành
phần giá trị mà về nguyên tắc bằng mắt thường không phân biệt được hai
điểm kề nhau. Trong quá trình này, người ta sử dụng khái niệm Picture
element mà ta quen gọi hay viết là Pixel – phần tử ảnh. Như vậy mỗi ảnh là
một tập hợp các pixel. Mỗi pixel gồm một cặp tọa độ (x, y) và giá trị màu.
Cặp tọa độ (x, y) tạo nên độ phân giải (resolution). Như màn hình máy
Lưu trữ
Thu nhận ảnh
(Scanner,
Camera,Sensor)
Tiền xử lý Trích chọn
đặc điểm

Hệ quyết định
Đối sánh rút
ra kết luận
Hậu
xử lý
Hình 1.1. Các giai đoạn chính trong xử lý ảnh 11

b) Tiền xử lý
Nắn chỉnh biến dạng:
Nắn chỉnh biến dạng thực hiện việc biến đổi hình học giữa hai ảnh:
ảnh nguồn và ảnh đích. Sự biến đổi hình học định nghĩa mối quan hệ giữa các
điểm ảnh nguồn và điểm ảnh đích. Mối quan hệ này có thể được xác định
bằng các hàm toán học được áp dụng trên toàn bộ ảnh hoặc chỉ trên một vùng
ảnh nào đó. Trong nhiều trường hợp ngoài việc xác định các hàm toán học để
nắn chỉnh ảnh, còn phải xác định thêm các đặc trưng sử dụng trong quá trình
nắn chỉnh.
Xét về mặt tác động của thuật toán nắn chỉnh thì có hai khuynh hướng:
tác động toàn cục và tác động cục bộ. Để tạo ra tác động toàn cục ta áp dụng
thuật toán, tiêu chí như nhau đối với mọi điểm ảnh. Còn tác động cục bộ thì
việc nắn chỉnh chỉ áp dụng trên một số vùng ảnh, các vùng khác giữ nguyên.
Các thuật toán nắn chỉnh toàn cục có tốc độ xử lý tương đối nhanh. Tuy
nhiên chỉ áp dụng được đối với các yêu cầu đơn giản như co, giãn ảnh, bóp
méo cả ảnh thành tứ giác hay một số hiệu ứng khác như mắt cá, kính núp v.v
Thuật toán nắn chỉnh cục bộ cho kết quả ấn tượng hơn. Tuy nhiên để có thể
nắn chỉnh theo từng vùng, phải xác định thêm tập các đặc trưng. Ngoài ra việc
xây dựng thuật toán cũng tương đối phức tạp.
Ảnh thu nhận nhờ các thiết bị điện tử và quang học thường bị biến dạng
hình học. Khi đó, phương pháp hiệu chỉnh ảnh được mô tả dưới dạng phương
trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng f’ (x’, y’) như sau: 




),('

 )),((),(),,,(),( yxdfyxhyxg


Trong đó:
- (x,y) là hàm biểu diễn nhiễu cộng.
- f(,) là hàm biểu diễn đối tượng.
- g(x,y) là ảnh thu nhận.
- h(x,y;,) là hàm tán xạ điểm(Point Spread Function-PSF).
Một vấn đề khôi phục ảnh tiêu biểu là tìm một xấp xỉ của f(,) khi
PSF của nó có thể đo lường hay quan sát trước được, ảnh mờ và các tính chất
xác xuất của quá trình nhiễu.
Hình 1.2. Ví dụ về nắn chỉnh biến dạng
a) Ảnh đầu vào
b) Ảnh mong muốn

14
Biến đổi ảnh:
Thuật ngữ biến đổi ảnh thường dùng để nói tới một lớp các ma trận đơn
vị và các kỹ thuật dùng để biến đổi ảnh. Cũng như các tín hiệu một chiều
được biểu diễn bởi một chuỗi các hàm cơ sở, ảnh cũng có thể được biểu diễn
bởi một chuỗi rời rạc các ma trận cơ sở gọi là ảnh cơ sở. Có nhiều loại biến
đổi được dùng như:
- Biến đổi Fourier, Sin, Cosin, Hadmard v.v
- Tích Kronecker
- Biến đổi KL (Kroecker Loeve): biến đổi này có nguồn gốc từ
khai triển của các quá trình ngẫu nhiên gọi là phương pháp trích
chọn các thành phần chính.
Do phải xử lý nhiều thông tin, các phép toán nhân và cộng trong khai
triển là khá lớn. Do vậy, các biến đổi trên nhằm làm giảm thứ nguyên của ảnh
để việc xử lý ảnh được hiệu quả hơn.

Xét trên phương diện cấu trúc ảnh, người ta chia nắn chỉnh thành hai loại là
nắn chỉnh ảnh 2D và 3D. Nắn chỉnh ảnh 2D đã đạt được những mục tiêu quan
trọng trong việc tìm ra các giải pháp để chuyển đổi không gian cũng như
trong việc quản lý các đặc trưng. Trong khi đó nắn chỉnh 3D vẫn còn rất xa so
với những thành công của 2D. Nói chung, các kỹ thuật nắn chỉnh 2D đòi hỏi
nhiều công đoạn xử lý thủ công. Hầu hết các phương thức 3D đã được đề xuất
chỉ giới hạn đối với một số mô hình đối tượng mà đã biết trước cách biểu diễn
của mô hình đó vì độ phức tạp của thuật toán phụ thuộc vào một số yếu tố
như: cách biểu diễn đối tượng, độ lồi, chủng loại.
Nếu phân chia theo luồng dữ liệu biến đổi thì có thể phân lớp nắn chỉnh

16
thành 2 lớp: các phương pháp tính xuôi và các phương pháp tính ngược.
Trong các phương pháp tính xuôi, các điểm ảnh trên ảnh nguồn được xử lý
theo từng dòng quét và các kết quả được thiết lập trên ảnh đích. Trong khi đó
các phương pháp tính ngược ánh xạ ngược các điểm ảnh đích tới các điểm
ảnh nguồn. Đối với các ảnh số thì việc thực thi theo các phương pháp tính
xuôi thường không cho kết quả tốt. Do vậy, hầu hết các thuật toán hiện nay
đều là các phương pháp tính ngược.
Nếu xét đến công cụ dùng để xác định đặc trưng cho đối tượng khi thực
hiện nắn chỉnh, ta phân nắn chỉnh thành 3 loại cơ bản: các kỹ thuật nắn
chỉnh dựa trên phân vùng ảnh, các kỹ thuật nắn chỉnh dựa trên các điểm
đặc trưng và các kỹ thuật dựa trên vector.
Với các kỹ thuật dựa trên việc phân vùng ảnh, trước tiên miền không
gian của ảnh nguồn được chia thành một tập các vùng nhỏ. Tương tự như vậy,
ảnh đích cũng được chia thành tập các vùng nhỏ tương ứng. Sau đó ảnh được
nắn chỉnh bằng cách chuyển đổi tương ứng mỗi vùng của ảnh nguồn thành
mảnh của ảnh đích. Một trong những phương thức đầu tiên của kỹ thuật dựa
trên phân mảnh là thuật toán nắn chỉnh 2-pass mesh. Với phương thức này,
mỗi chuyển đổi 2-pass sẽ thay thế một chuyển đổi 2-D thành một dãy các

thức nắn chỉnh là đại diện cho một thuật toán nắn chỉnh biến dạng.
Để đạt được chất lượng nắn chỉnh hình tốt, chúng ta phải nội suy từng
phần của ảnh gốc sang các phần tương ứng bên ảnh đích. Điều này có nghĩa là
ta đã biểu diễn được thông tin của đối tượng và ánh xạ từng phần của chúng
cho nhau. Đây cũng chính là mục đích của giai đoạn xác định các đặc trưng.
Nói chung, việc xác định các đặc trưng của đối tượng vẫn là công việc
thủ công chủ yếu là do người sử dụng nhập vào hoàn toàn hoặc là với sự trợ
giúp một phần của máy tính. Người ta cũng đã đưa ra được thuật toán biến

18
đổi tự động xác định các đặc trưng của ảnh. Tuy nhiên, nó chỉ xác định được
trong trường hợp các ảnh đầu vào tương đối giống nhau và đối tượng ảnh
tương đối đơn giản hơn nữa tốc độ của nó lại rất chậm.
1.2.3. Một số ứng dụng của nắn chỉnh biến dạng
a) Y t ế
Trong thực tế có rất nhiều tình huống trong đó người ta mong muốn
làm sao có thể xem trước được hình ảnh kết quả để đưa ra quyết định hoặc để
thực hiện các thí nghiệm ảo. Ví dụ dự đoán hình ảnh một người nào đó tại
một thời điểm trong tương lai để xác định tội phạm, dự đoán kết quả khi
chỉnh sửa một bộ phận trên cơ thể tại các thẩm mỹ viện để quyết định có nên
chỉnh sửa hay không, hoặc dự đoán hình ảnh để tạo các thí nghiệm ảo trong y
tế giúp các sinh viên ngành y tiếp cận thực hành trước khi thực hiện trên
người thật v.v Rõ ràng phỏng đoán trước hình ảnh kết quả là là nhu cầu
không thể thiếu trong giai đoạn công nghệ thông tin phát triển như hiện nay
nhất là trong lĩnh vực y tế nhằm hạn chế đến mức thấp nhất những rủi ro
trong quá trình điều trị. Xử lý ảnh với các kỹ thuật nắn chỉnh biến dạng sẽ
phần nào giúp hạn chế điều đó. Tuy nhiên, đây cũng là huớng đi còn mới mẻ
đối với xử lý ảnh và cũng là vấn đề khó vì muốn thực hiện được các chương
trình áp dụng trong y tế đòi hỏi phải có sự hiểu biết về cấu tạo sinh học của
con nguời. Vì thế sẽ cần một thời gian chuẩn bị trước khi có thể đi đến thử Hình 1.3. Ảnh mẫu và ảnh bị biến dạng của một hệ thống thu nhận ảnh
dạng cơ sở

Hình 1.4. Quá trình trưởng thành của cây

20
Hình 1.5 minh hoạ dãy biến đổi từ con nòng nọc thành con cóc.
Những vật vô tri thức cũng có thể bị biến đổi hình dạng dưới các tác
động bên ngoài. Các tác động này liên quan đến hiện tượng môi trường như
gió, mưa, ánh sáng cũng như các quá trình khác như các tác động cơ học, các
phản ứng cháy v.v Hình 1.6 thể hiện sự biến đổi của một cái ống vắt ngang
qua cái ống khác. Tuỳ thuộc vào đặc tính vật chất của đối tượng, một số biến đổi có thể
giữ được trong thời gian rất lâu, nhưng một số biến đổi chỉ là tạm thời. Vì thế
người ta phân thành hai lớp biến đổi là đàn hồi và không đàn hồi.
e) Hoạt hình
Khi các ảnh trong một dãy ảnh liên tục thay phiên nhau xuất hiện thì
tạo ra ảo giác của sự chuyển động, người ta gọi hiện tượng đó là hoạt hình
Hình 1.8. Ba trạng thái tiến hóa của con
cá sấu

Hình 1.7. Các hình dạng của cùng một lớp

22
(animation). Đây là nguyên lý cơ bản của phim ảnh.
Thực tế biến đổi hình dạng nói chung là liên tục, vì thế nó phù hợp với
các ứng dụng xử lý hiện tượng thay đổi theo thời gian. Có thể định nghĩa một
tiến trình biến đổi hình dạng liên tục và gắn vào đó một toán tử biến đổi theo
thời gian. Ví dụ đơn giản là tạo ra hoạt hình bằng cách kết hợp co giãn đối
tượng. Hình 1.9 thể hiện một vài hình ảnh chuyển động của quả bóng rơi từ
trên cao, đập xuống đất rồi bật lên bằng cách dùng hiệu ứng kéo giãn và nén
quả bóng.

Một cách khác dùng biến đổi hình dạng để tạo chuyển động là nội suy
hình dạng của hai đối tuượng. Đây là kỹ thuật tạo chuyển động truyền thống
được sử dụng rộng rãi. Trước tiên kỹ thuật này tạo ra dãy các keyframe mô tả
các sự kiện chính của quá trình biến đổi. Các keyframe chứa các đặc trưng
của thời kỳ chuyển giao và truyền đạt các hành động diễn ra trong cảnh biến
đổi đó. Trong hệ thống hoạt hình máy tính, có thể dùng các kỹ thuật nắn
chỉnh biến dạng để tạo ra các frame trung gian. Với kỹ thuật này cần có hình

Trong thực tế, người ta dùng nắn chỉnh biến dạng để phân tích và chỉnh
sửa hình dạng đối tượng nhằm phục vụ cho bài toán nhận dạng. Mục đích của
bài toán này là trả lời câu hỏi đối tượng trong ảnh đã cho có khớp với đối
tượng nào trong tập mẫu cho trước hay không? Để làm được điều đó ta tính
tổng chuyển đổi cần thiết để căn chỉnh một số đặc trưng về hình dạng các
phần từ từ tập mẫu. Ảnh cần nhận dạng sẽ gần với mẫu nào nhất nếu tổng
Hình 1.10. Cross dissolve

Hình 1.11. Cái ống bị biến đổi do thu hẹp, uốn cong, xoắn 24
chuyển đổi cần thiết của ảnh với mẫu đó là ít nhất.
Hình 1.12 thể hiện tập hình dạng, tập mẫu và sự tương ứng giữa hình
dạng với các mẫu sau khi thực hiện nắn chỉnh. Sử dụng nội suy để căn chỉnh
sự phù hợp giữa mẫu và các hình dạng. Bằng cách này có thể thiết lập mối
liên kết giữa hai đối tượng có quan hệ với nhau thông qua việc thiết lập các
đặc trưng tương thích một cách thủ công. Hình 1.12. Đối sánh hình
dạng