TÌM HIỂU PHƯƠNG PHÁP
GHÉP ẢNH
LUẬN VĂN THẠC SĨ
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Ngô Quốc Tạo HÀ NỘI - NĂM 2008 3
MỤC LỤC CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT 6
DANH MỤC CÁC HÌNH 7
MỞ ĐẦU 8
Chương 1 – TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ GHÉP ẢNH 10
2.6. Chuyển đổi song tuyến 27
2.6.1. Nội suy song tuyến 28
2.6.2. Phân tách 29
2.6.3. Ánh xạ ngược 29
2.6.4. Lưới nội suy 30
2.7. Phép chuyển đổi đa thức 30
2.7.1. Phương pháp giả nghịch đảo 32
2.7.2. Bình phương cực tiểu với đa thức thường 33
2.7.3. Bình phương cực tiểu với đa thức trực giao 34
2.7.4. Bình phương cực tiểu với trọng số 37
2.8. Các phép chuyển đổi đa thức liên tục từng phần 38
2.8.1. Bề mặt phù hợp với mô hình trong nắn chỉnh hình học 38
2.8.2. Nội dung phép chuyển đổi đa thức liên tục từng phần 39
2.8.3. Phép đạc tam giác 40
2.8.4. Các mặt tam giác tuyến tính 40
2.8.5. Mặt tam giác bậc ba 41
Chương 3 – MỘT SỐ KỸ THUẬT GHÉP ẢNH 44
3.1 Ghép ảnh bằng cách trộn các điểm ảnh của các ảnh ghép 44
3.1.1 Công thức của Alvy Ray Smith và Ed Catmull 45
3.1.2 Công thức của Bruce Wallace và Marc Levoy 45
3.2 Ghép ảnh dựa vào nắn chỉnh hình học 45
3.2.1. Phương án giải quyết 45
3.2.2. Xây dựng hàm biến đổi 46
3.2.3. Phương pháp xác định sai số cho các điểm CP 47
3.2.4. Phương pháp HouseHoulder 49 5
3.2.5. Xác định các điểm điều khiển (CP) 52
3.2.6. Đánh giá sai số 53
DFT Discrete Fourier Transform
IFT Inverse Fourier Transform
FT Fourier Transform
FFT Fast Fourier Transform
IDFT Inverse Discrete Fourier Transform
DPI Dots Per Inch 7
DANH MỤC CÁC HÌNH
Hình 1.1. Các giai đoạn chính trong xử lý ảnh 11
Hình 1.2. Các thành phần chính trong hệ thống xử lý ảnh 11
Hình 1.3. Ảnh thu nhận 14
Hình 1.4. Ảnh mong muốn 14
Hình 1.5. Minh họa về việc giả mạo ảnh 16
Hình 1.6. Hai ảnh được ghép cùng tỷ lệ 50% 16
Hình 1.7. Hai ảnh được ghép với nhau dựa vào 17
hai tập các điểm đặc trưng được trọn trên 2 ảnh 17
Hình 1.8. Ảnh toàn cảnh được ghép từ 28 ảnh gốc 17
Hình 2.1. Ánh xạ xuôi 19
Hình 2.2. Mảng tích luỹ 20
Hình 2.3. Ánh x
ạ ngược 21
Hình 2.4. Một số phép nắn chỉnh tuyến tính 22
Hình 2.5. Ánh xạ tứ giác - tứ giác 26
Hình 2.6. Nội suy song tuyến 28
Hình 2.7. Nội suy song tuyến phân tách 29
Hình 2.8. Nội suy hình học của lưới nội suy 30
Hình 2.9. Các biến dạng hình học phổ biến 31
ra nhi
ều hướng mới cho sự phát triển phần mềm, đặc biệt là Công nghệ xử lý ảnh
đã ra đời và phát triển nhanh. Sức mạnh của các phần mềm soạn thảo và xử lý
ảnh như Photoshop đã giúp cho việc tạo ra ảnh ghép ngày càng dễ dàng hơn.
Người ta tạo ra các ảnh ghép thường nhằm vào các mục đích như tạo ra các ảnh
có độ phân giải cao như ảnh bản đồ, tạo ra ảnh nghệ
thuật, tạo hình ảnh trong
phim hoạt hình, tái tạo hình ảnh tội phạm từ những mô tả v.v Do vậy, việc tạo
ra ảnh ghép là vấn đề phải đặt ra ngày càng cấp bách và càng trở nên khó khăn.
Mặc dù nhu cầu về việc ghép ảnh số đã được công nhận bởi cộng đồng các
nhà nghiên cứu, nhưng hiện nay rất ít tài liệu có giá trị về lĩnh vực này. Trong
thực tế, người ta thường có tấ
m ảnh bản đồ to, hay một chuỗi các biến đổi ảnh
con dê Æ ảnh con gà Æ ảnh con hổ Æ ảnh người đàn bà, hay những bức ảnh
toàn cảnh có góc xem rộng hơn so với một tập ảnh gốc. Ngày nay nhờ sự phát
triển của khoa học kỹ thuật, người ta đã lưu trữ những bức ảnh trên trong máy
tính. Vậy làm sao để có thể chuyển được những b
ức ảnh này vào máy tính?
Người ta dùng scanner để quét bản đồ vào máy tính, những bức ảnh riêng rẽ
của bức ảnh toàn cảnh được chụp từ máy ảnh. Tuy nhiên, scanner không thể quét
được cả một bản đồ to mà nó chỉ quét được từng phần và máy ảnh không thể
chụp được những bức ảnh có góc xem rộng tuỳ ý mà phụ thuộc vào thấu kính
của chúng. Vấn đề đặt ra là làm cách nào có thể ghép các phần ghép vào với
nhau để thành m
ột bản đồ đúng và những bức ảnh nhỏ vào với nhau để thành
một ảnh toàn cảnh có góc xem rộng.
Trên đây đã điểm qua tầm quan trọng của vấn đề ghép ảnh và điều đó cho ta
thấy rõ tính cần thiết cũng như tính thời sự đồng thời là ý nghĩa khoa học và thực
tiễn của vấn đề. Nhận thức được điều này, tôi đ
ã chọn đề tài: “Tìm hiểu phương
10
Chương 1 –
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ GHÉP ẢNH Chương này trình bày tổng quan về một hệ thống xử lý ảnh, các vấn đề cơ bản
trong xử lý ảnh, đồng thời trình bày tổng quan về ghép ảnh, cụ thể là các dạng ảnh
ghép cơ bản cùng với các cách tiếp cận chính để ghép ảnh.
1.1 Xử lý ảnh, các vấn đề cơ bản trong xử lý ảnh
1.1.1 Xử lý ảnh là gì?
Xử lý ảnh là một khoa học tương đối mới mẻ so với nhiều ngành khoa học
khác, nhất là trong quy mô công nghiệp, song trong xử lý ảnh đã bắt đầu xuất hiện
những máy tính chuyên dụng. Để có thể hình dung cấu hình một hệ thống xử lý ảnh
chuyên dụng hay một hệ thống xử lý ảnh dùng trong nghiên cứu, đào tạo, trước hết
chúng ta sẽ xem xét các bước cần thiết trong xử lý ảnh.
Hình 1.2. Các thành phần chính trong hệ thống xử lý ảnh
• Đối với một hệ thống xử lý ảnh thu nhận qua camera - camera như là con mắt
của hệ thống. Có 2 loại camera: camera ống loại CCIR và camera CCD. Loại
camera ứng với chuẩn CCIR quét ảnh với tần số 1/25 và mỗi ảnh gồm 625
dòng. Loại CCD gồm các photo điốt và làm tương ứng một cường độ sáng tại
Thu nhận
(Camera, scanner,
sensor, )
Tiền xử lý
(Nắn chỉnh, xóa
nhiễu, )
Trích chọn
đặc trưng
Hậu xử lý
(Chính xác hóa, rút
gọn, )
Kết luận
Lưu trữ
Hệ quyết định
Máy in
Bộ nhớ
ngoài
Camera
Màn hình Bàn phím
Máy chủ
Bộ xử lý
ảnh số
n
) trong đó n là số chiều của ảnh.
Ảnh: là một tập hợp các điểm ảnh, thông thường được biểu diễn dưới dạng
ma trận các điểm ảnh.
Mức xám: là kết quả của sự mã hóa tương ứng một cường độ sáng của một
điểm ảnh với một giá trị số - kết quả của quá trình lượng hóa. Cách mã hóa kinh
điển th
ường dùng 16, 32 hay 64 mức.
Biểu đồ tần suất: Biều đồ tần suất của một mức xám g của ảnh I là số điểm
ảnh của I có mức xám g.
1.1.2 Các vấn đề cơ bản trong xử lý ảnh
1.1.2.1 Biểu diễn ảnh
Ảnh được thu nhận từ các thiết bị thu nhận ảnh. Sau khi thu nhận, ảnh được
lưu trữ trên máy tính. Quá trình lưu trữ gồm 2 mục đích: tiết kiệm bộ nhớ và
giảm thời gian xử lý.
Ảnh được lưu trữ trong bộ nhớ có ảnh hưởng rất lớn đến việc hiển thị, in ấn
và xử lý. Ảnh là tập hợp các điể
m ảnh có cùng kích thước do đó nếu sử dụng
càng nhiều điểm ảnh thì ảnh càng mịn càng đẹp và càng thể hiện rõ hơn chi tiết 13
của ảnh, người ta gọi đặc điểm này là độ phân giải. Việc lựa chọn độ phân giải
phụ thuộc vào nhu cầu sử dụng và đặc trưng của từng loại ảnh cụ thể. Chẳng
hạn, ảnh dùng trong văn bản thường thể hiện dưới dạng đen trắng có độ phân
giải 300 DPI, ảnh bản vẽ, bản đồ có độ phân giải 200DPI.
Trên c
ơ sở đó, các ảnh được biểu diễn theo 2 mô hình cơ bản là RASTER
và VECTOR.
Mô hình RASTER:
14 Hình 1.3. Ảnh thu nhận
Hình 1.4. Ảnh mong muốn
Để nắn chỉnh biến dạng ta dựa vào tập các điểm điều khiển
'
( , ) ( 1, , ).
ii
PP i n=
Cần tìm hàm:
:()
ii
f
PfP→
sao cho:
2
'
1
15
Giải hệ phương trình tuyến tính tìm được a
1
, b
1
, c
1
Tương tự tìm được a
2
, b
2
, c
2
Æ Xác định được hàm f
1.1.2.3 Khử nhiễu
Trong quá trình thu nhận ảnh không thể tránh khỏi bị nhiễu. Có 2 loại nhiễu
cơ bản:
- Nhiễu hệ thống: là loại nhiễu gây ra bởi hệ thống, như vết xước hoặc
nguồn sáng ngoại lai. Loại nhiễu này có tính chất chu kỳ và có thể dễ khắc phục
bằng các phép biến đổi.
- Nhiễu ngẫu nhiên: là các vết bẩn không rõ nguyên nhân. Loại nhiễu này
th
ường khó khử, tùy vào từng ảnh cụ thể mà có cách khắc phục. Thông thường
sử dụng các phép lọc.
1.1.2.4 Nhận dạng ảnh
Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tượng mà người ta
muốn đặc tả nó. Quá trình nhận dạng thường đi sau quá trình trích chọn các đặc
tính chủ yếu của đối tượng. Có hai kiểu mô tả đối tượng:
Ghép ảnh thường chia làm hai loại chính. Loại thứ nhất là ghép ảnh trong
(Transparent Image Merging), tức là các vùng ảnh được ghép với nhau một cách
trong suốt, chúng ta có thể quan sát được tất cả các vùng ảnh của các ảnh ghép.
Loại thứ hai là ghép ảnh đục (Opaque Image Merging) là các phần ghép thêm
vào thì che đi các vùng trên ảnh bị ghép.
Ghép ảnh trong bao gồm các kỹ thuật sau: Trộn ảnh thông thường với một
tỷ lệ nào đó (Hình 1.5 Hai ả
nh được ghép với nhau với cùng tỷ lệ 50%); Ghép
ảnh dựa vào nắn chỉnh hình dạng (Hình 1.6 Hai ảnh được ghép với nhau dựa vào
các phép nắn chỉnh theo hai tập các điểm đặc trưng được trọn trên 2 ảnh). Hình 1.6. Hai ảnh được ghép cùng tỷ lệ 50% 17
vào.
Tuỳ thuộc vào các ứng dụng, các hàm ánh xạ chuyển đổi không gian sẽ có
công thức khác nhau. Các phép chuyển đổi cơ bản bao gồm affine, chiếu, song
tuyến và chuyển đổi đa thức. Các hàm ánh xạ phức tạp hơn có thể được xác định
từ các điểm điều khiển (control points) rời rạc mà trong đ
ó không gian tương
ứng đã biết.
Các công thức cơ bản đề cập tới ở đây là các phép chuyển đổi ma trận
thuần nhất. Có hai lớp ánh xạ không gian hai chiều đồng phẳng: Chuyển đổi
tuyến tính (affine transformations) và chuyển đổi phối cảnh (perspective
transformations). Những biến đổi không đồng phẳng phổ biến hơn đối với phép
chuyển đổi tuyến tính là các phép biến đổi song tuyến (bilinear
transformations). Sau đây sẽ đề cập tới đặc tính hình học của ba phép chuyển
đổi này và điểm qua các công thức toán học cần thiết cho phép chuyển đổi
ngược và đưa ra các kết luận về các ánh xạ này.
Trong nhiều trường hợp, biến dạng ảnh thường được đặc trưng bởi phép
chuyển đổi đa thức. Nó phổ biến trong các ứng dụng hiệu chỉnh hình học
(geometric correction), trong đ
ó các mô hình biến dạng không gian thích hợp
với đa thức bậc thấp. Điều quang trọng ở đây là phải đưa ra được các hệ số của
đa thức một cách chính xác. Trong phần này sẽ giới thiệu một vài phương pháp
phân tích số để giải ra các hệ số này. Trường hợp biến dạng cục bộ người ta sử
dụng phép chuyển đổi đa thức liên tục từng đ
oạn. Nó cho phép các hệ số biến
thiên trong khoảng nào đó.
Trong trường hợp tổng quát, biểu diễn dưới dạng bề mặt nội suy để đưa ra
cái nhìn sâu sắc hơn đối với vấn đề này (và các giải pháp của nó). Cái nhìn rộng
lớn hơn này xuất phát từ nhận thức rằng các hàm ánh xạ có thể biểu diễn như là
hai bề mặt, mỗi bề mặt gắn với một song ánh giữ
a các điểm hai chiều trong ảnh
Ánh xạ xuôi là ánh xạ các điểm ảnh vào thành các điểm ảnh đầu ra tại các
vị trí được xác định bởi hàm ánh xạ X, Y. Mỗi một điểm ảnh đầu vào qua các
phép chuyển đổi không gian tạo nên giá trị toạ độ mới. Toạ độ các điểm ảnh bao
giờ cũng là các số nguyên nhưng khi qua phép chuyển đổi không gian thì chúng
có giá trị thực. Vì vậy các điểm ảnh vào được ánh xạ từ t
ập các số nguyên sang
tập các số thực.
Trong miền liên tục, các điểm ảnh được coi như các điểm, hàm ánh xạ là
ánh xạ xuôi. Tuy nhiên, trong miền rời rạc, các điểm ảnh được xem như là các
phần tử hữu hạn nằm trên dãy số nguyên. Như vậy sẽ gây ra tính không tương
thích khi thực hiện phép chuyển đổi không gian mà nó được coi là ánh xạ điểm
thành điểm. Nếu vậy thì gặp phả
i hai vấn đề: lỗ (holes) và phần đè lên nhau
(overlaps). Lỗ là vị trí các điểm ảnh không được xác định. Vấn đề này xảy ra khi 20
ánh xạ liên tục các mẫu vào sang các vị trí rời rạc ở đầu ra. Chẳng hạn như trong
hình thì E’ là lỗ. Ngược lại phần đè lên nhau xảy ra khi một loạt các mẫu vào
ánh xạ tới một điểm ảnh ra như trong hình là điểm F’. Điều này thường xảy ra
do các phép làm tròn số trong hàm ánh xạ hoặc do ánh xạ nhiều - một từ đầu vào
tới đầu ra.
Các lỗi của ánh xạ điể
m - điểm có thể tránh được nếu sử dụng ánh xạ 4 góc
(four-corner mapping). Coi các điểm ảnh vào như là một mặt hình vuông và ta
ánh xạ hình vuông này thành một hình bốn cạnh tuỳ ý ở đầu ra. Nó cho các điểm
vẫn liên tục sau phép ánh xạ.
Do các mẫu vào sau phép ánh xạ nó có thể nằm ở bất kỳ vị trí nào ở đầu ra
nên các điểm ảnh đầu vào sau phép ánh xạ có thể nằm trên một vài điểm ả
nh
điểm ảnh ra này.
Ánh xạ bốn góc cho phép tránh được lỗ trên các ảnh ra. Tuy nhiên, mô hình
này dẫn tới hai vấn đề trong quá trình ánh xạ xuôi. Đầu tiên, giá phải trả cho
việc kiểm tra phần giao phải dựa trên trọng số. Thứ hai, sự phóng to có thể là
nguyên nhân của việc cùng một điểm vào được ánh xạ thành nhiề
u điểm ra trừ
khi ta thêm vào các điều kiện lọc.
Cả hai vấn đề trên có thể được giải quyết lại bằng cách lấy mẫu phù hợp đầu vào
dựa trên kích thước của hình tứ giác được chiếu. Nói một cách khác, nếu các
21
điểm ảnh vào được ánh xạ thành một vùng trên ảnh ra thì lặp lại việc chia nhỏ
điểm ảnh vào cho đến khi vùng chiếu đạt tới một giới hạn nhỏ nhất chấp nhận
được, chẳng hạn là một điểm ảnh. Khi tỷ lệ mẫu tăng, trọng số hội tụ tới một giá
trị đơn.
Mẫu đồng dạng của ảnh vào không đả
m bảo mẫu đồng dạng của ảnh ra trừ
khi X và Y là ánh xạ tuyến tính. Đối với ánh xạ phi tuyến (phối cảnh hoặc song
tuyến….) thì mẫu vào phải được lấy theo một tỷ lệ của sự biến đổi không gian.
Một cách tổng quát, ánh xạ xuôi rất có lợi khi ảnh vào được đọc liên tục hoặc
khi nó không chiếm toàn bộ bộ nhớ.
2.3 Ánh xạ ngược
⎤
⎢
⎢
⎢
⎣
⎡
=
333231
232221
131211
aaa
aaa
aaa
T
Ma trận này chứa đựng các phép co dãn (scaling), trượt (shearing), quay
(rotation), tịnh tiến (translation) và phối cảnh trong ảnh hai chiều
Cách biểu diễn tổng quát của phép chuyển đổi tuyến tính là:
[][]
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
13
y = a
21
u + a
22
v + a
23
Hình 2.4. Một số phép nắn chỉnh tuyến tính
Nó bao gồm các phép tịnh tiến, co dãn và trượt. Sau đây sẽ đề cập tới một số
trường hợp đặc biệt của phép chuyển đổi tuyến tính và các đặc tính của chúng.
2.4.1. Phép tịnh tiến
Tất cả các điểm được dịch tới vị trí mới bằng cách cộng thêm T
u
và T
v
vào
u và v. Phép chuyển đổi tịnh tiến như sau:
23
[][]
⎥
⎥
⎢
⎣
⎡
−=
100
0cossin
0sincos
1,,1,,
θθ
θθ
vuyx
2.4.3. Phép co dãn
Tất cả các điểm được co dãn bởi hệ số co dãn S
u
và S
v
cho toạ độ u và v.
Phép co dãn phóng to (thu nhỏ) được xác định bởi hệ số co dãn dương và ảnh
thu được sẽ lớn hơn (nhỏ hơn) ảnh ban đầu. Hệ số co dãn âm dẫn tới ảnh đối
xứng, chẳng hạn như ảnh phản chiếu. Hệ số co dãn không đều nhau thì dẫn tới
ảnh bị méo.
[][]
⎥
⎥
⎥
⎦
⎤
⎢
⎢
dụng với trục v để tính giá trị mới cho y trong khi x vẫn không bị thay đổi. Kết
quả là ta có phép trượt. Phép trượt dọc theo trục u là:
[][]
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
100
01
001
1,,1,,
v
Hvuyx
H
v
tạo cho x độc lập tuyến tính với v. Tương tự, trượt dọc theo trục v là:
[][]
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
100
00
00
100
0cossin
0sincos
θθθθ
θθ
θθ
vuvvuu
vu
vu
TTSTTS
SS
SS
2.4.6. Phép chuyển đổi ngược.
Theo như trên, ánh xạ xuôi là ánh xạ từ mặt phẳng có hệ toạ độ uv sang mặt
phẳng có hệ toạ độ xy. Như vậy ánh xạ ngược sẽ là ánh xạ từ mặt phẳng có hệ
toạ độ xy sang mặt phẳng có hệ toạ độ uv nghĩa là từ mặt phẳng đích sang mặt
phẳng nguồn.
Hàm ánh xạ ngược có dạng sau:
[][]
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
,
v
k
) và (x
k
, y
k
) với k = 0, 1, 2 là ba điểm trên ảnh tham chiếu và ảnh quan sát.
Phương trình sau sẽ biểu diễn mối quan hệ giữa chúng dưới dạng phương trình
ma trận. Sáu hệ số của ánh xạ tuyến tính được xác định bằng cách giải hệ sáu
phương trình tuyến tính trong phương trình sau:
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
aa
aa
aa
vu
vu
vu
yx
yx
yx
Viết gọn lại ta có X = UA.
Để xác định các hệ số, ta phải giải A: A = U
-1
X.
Như vậy, ở đây phải tính ma trận nghịch đảo U
-1
.
Khi có nhiều hơn ba điểm thì ma trận U là không vuông và ta xác định xấp
xỉ các hệ số bằng giải hệ phương trình quá xác định (overdetermined). Trong
trường hợp này, ma trận U không phải là 3x3 mà là ma trận không vuông với số
hàng nhiều hơn số cột. Do vậy phải dùng phương pháp bình phương cực tiểu để
giải. 25
Như vậy, chỉ cần ba điểm là đủ để kết luận ánh xạ tuyến tính. Về cơ bản, nó
có thể ánh xạ một tam giác vào thành một tam giác tuỳ ý ở đầu ra. Một hình chữ
nhật vào có thể được ánh xạ thành hình bình hành ở đầu ra. Biến dạng tổng quát
thì không thể dùng được chuyển đổi tuyến tính. Chẳng hạn, ánh xạ một hình chữ
]
T
khác 0, ta có phép chuyển đổi phối cảnh. Chuyển đổi phối
cảnh bảo toàn tính song song của các đường thẳng khi chúng song song với mặt
phẳng chiếu. Trong các trường hợp khác, các đường thẳng hội tụ. Phép chuyển
đổi này có tính chất là làm khoảng cách giữa các đường thẳng ngắn lại. Đó là
một trong các kỹ thuật để biểu hiện những ảnh thật. Hàm ánh xạ xuôi của phép
chuyển đổi phối cảnh là.
332313
312111
'
'
avaua
avaua
w
x
x
++
+
+
== ,
332313
322212
'
'
avaua
avaua
w
y
y
k
, y
k
) là cặp bốn điểm
tương ứng giữa đầu vào và đầu ra. Phương trình giải x và y có thể được viết lại
như sau.
Copyright: Tài liệu đại học ©