Bài giảng Xử lý ảnh - Chương 8: Các phép toán hình học

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (188.32 KB, 7 trang )

(1)<div class='page_container' data-page=1>

C

HƯƠNG

8

CÁC PHÉP TỐN HÌNH HỌC

8.1 GIỚI THIỆU

Các phép tốn hình học làm thay đổi mối quan hệ không gian giữa các đối tượng
trong ảnh. Những phép toán như thế có thể được xem như di chuyển các vật khắp nơi
trong ảnh. Tác đọng này cũng giống như khi in ảnh lên một tấm cao su, kéo giãn tấm cao
su đó và ghim nó xuống tại những điểm khác nhau. Thực ra, một phép tốn hình học

được hiểu theo một nghĩa rộng hơn, bởi vì một điểm bất kỳ trong ảnh đầu vào nào cũng
có thể di chuyển đến bất cứ vị trí của ảnh đầu ra. Một phép tốn hình học khơng hạn chế

như thế thường làm lộn xộn nội dung ảnh, do đó các phép tốn hình học thường được
giới hạn để giữđược một trật tự bề ngoài nào đó.

Một phép tốn hình học u cầu phải có hai thuật giải. Trước hết phải có một thuật
giải định nghĩa sự biến đổi khơng gian. Phép tốn này định rõ "sự chuyển động" của mỗi

điểm ảnh khi nó "di chuyển" từ vị trí ban đầu đến vị trí kết thúc trong ảnh. Phép nội suy
mức xám cũng địi hỏi phải có một thuật giải. Nói chung, phép tốn này là cần thiết bởi

vì các vị trí x, y nguyên trong ảnh đầu vào ánh xạđến các vị trí phân số (khơng ngun)

trong ảnh đầu ra và ngược lại.

8.1.1 Sự biến đổi không gian

Trong hầu hết các ứng dụng, người ta thường mong muốn bảo tồn tính liên tục của

các đặc tuyến cong tuyến tính (curvilinear) và sự kết nối của các đối tượng trong ảnh.
Một thuật giải biến đổi khơng gian ít hạn chế hơn có thể làm đứt đoạn các đường và các

đối tượng và có khuynh hướng "làm bắn tung toé" nội dung ảnh.

Người ta có thể hồn tồn xác định được sự di chuyển của mỗi điểm ảnh trong ảnh,
nhưng nó sẽ nhanh chóng trở nên khó di chuyển, thậm chí với cả những ảnh nhỏ. Để

thuận tiện hơn thì ta nên xác định chính xác mối quan hệ không gian giữa các điểm trong

ảnh vào và các điểm trong ảnh ra. Định nghĩa chung cho một phép tốn hình học là

)]
,
(
),
,
(
[
)
'
,
'
(
)
,

(x y f x y f a x y b x y

g   (1)

trong đó f(x,y) là ảnh đầu vàu và g(x,y) là ảnh đầu ra. Các hàm a(x,y) và b(x,y) xác

định sự biến đổi không gian duy nhất. Nếu các hàm này liên tục thì tính liên kết trong

ảnh sẽđược bảo toàn.

8.1.2 Phép nội suy mức xám (Gray-Level Interpolation)

Yêu cầu thứ hai đối với một phép tốn hình học là một thuật giải cho phép nội suy
các giá trị mức xám. Trong ảnh đầu vào f(x,y), các giá trị mức xám chỉđược xác định tại
các giá trị tích phân của x và y. Tuy nhiên, biểu thức (1) nói chung sẽ chỉ ra rằng giá trị

mức xám đối với ảnh g(x,y) có được từ các vị trí phân số (khơng ngun) kết hợp của

ảnh f(x,y). Nếu một phép tốn hình học được xem là một ánh xạ từf sang g, thì các điểm

ảnh trên f có thể ánh xạ tới các vị trí giữa các điểm ảnh trên g và ngược lại. Với mục

</div>
(2)<div class='page_container' data-page=2>

Để nói về sự biến đổi không gian và một thuật giải chophép nội suy mức xám, chúng
ta sẽ thực hiện một phép tốn hình học. Thông thường, một thuật giải nội suy mức xám

được cài đặt cốđịnh trong chương trình máy tính. Tuy nhiên, thuật giải xác định sự biến

đổi không gian được định rõ duy nhất cho công việc sắp tới. Bởi vì thuật giải nội suy
mức xám luôn giống nhau, hoặc một trong nhiều tuỳ chọn, nên sự biến đổi không gian là
sự biến đổi khơng gian định nghĩa phép tốn hình học cụ thể.

8.1.3 Sự thực hiện

Khi thực hiện một phép tốn hình học, ta có thểđi theo một trong hai hướng trên. Ta

có thể xem phép tốn đó như là việc chuyển các mức xám từảnh đầu vào sang ảnh đầu

ra, lần lượt từng điểm ảnh một. Nếu một điểm ảnh đầu vào ánh xạ đến một vị trí giữa
bốn điểm ảnh đầu ra, thì mức xám của nó là một trong bốn điểm ảnh ra này, tuỳ thuộc
vào quy tắc của phép nội suy. Chúng ta gọi nó là cách tiếp cận mang điểm ảnh sang

(pixel carry-over) hay ánh xạ tiến (forward mapping). (Xem hình 8-1.)

Một sự thực hiện luân phiên, và hiệu quả hơn, được hoàn thành nhờ thuật giải lấp đầy

điểm ảnh (pixel filling) hay ánh xạ lùi (backward mapping). Trong trường hợp này, các

điểm ảnh đầu ra được ánh xạ ngược lại thành ảnh đầu vào, từng điểm ảnh một, để thiết
lập các mức xám của chung. Nếu một điểm ảnh ra nằm giữa bốn điểm ảnh vào thì mức

xám của nó được xác định bằng phép nội suy mức xám (Hình 8-1). Sự biến đổi không

gian lùi là nghịch đảo của biến đổi tiến.

Thuật giải ánh xạ lùi có phần lãng phí, bởi vì nhiều điểm ảnh vào có thể ánh xạđến
các vị trí bên ngồi ảnh đầu ra. Hơn nữa, mỗi điểm ảnh ra có thểđược đánh địa chỉ vài
lần, cùng với các điểm ảnh đầu vào tập trung thành giá trị mức xám cuối cùng của nó.
Nếu sự biến đổi không gian bao gồm cả sự thu nhỏ thì có thể có nhiều hơn bốn điểm ảnh

đầu vào cùng tham gia. Nếu có sự phóng to thì tất nhiên một số điểm ảnh đầu ra sẽ bị

mất khi khơng có điểm ảnh đầu vào nào ánh xạđến các vị trí gần chúng.

Tuy nhiên, thuật giải ánh xạ lùi tạo ra ảnh đầu ra theo từng điểm ảnh một, từng dòng
một. Mức xám của mối điểm ảnh được xác định duy nhất bởi một bước nội suy giữa bốn

điểm ảnh (đa số là như vậy). Dĩ nhiên, ảnh đầu vào phải được truy cập một cách ngẫu

nhiên theo một cách mà được xác định bâừng sự biến đổi không gian, và việc này có thể

rất phức tạp. Tuy nhiên, cách tiếp cận lấp đầy điểm ảnh là thuật giải thực tiễn hơn đối

với cơng dụng chung.

HÌNH 8-1

</div>
(3)<div class='page_container' data-page=3>

8.2 PHÉP NỘI SUY MỨC XÁM

Vì những điểm ảnh đầu ra ánh xạđến những vị trí phân số trong ảnh đầu ra, cho nên
chúng thường rơi vào khoảng giữa bốn điểm ảnh vào. Như vậy phép nội suy là cần thiết

để xác định mức xám nào sẽ tương ứng với vị trí đó.

8.2.1 Phép nội suy lân cận gần nhất (Nearest Neighbor)

Sơđồ nội suy đơn giản nhất được gọi là nội suy bậc không (zero order), hay lân cận 
gần nhất (nearest neighbor). Trong trường hợp này, mức xám của điểm ảnh đầu ra được
lấy bằng mức xám của điểm ảnh đầu vào nằm gần nhất mà điểm ảnh ra ánh xạ sang.
Phép nội suy này tính tốn đơn giản và tạo ra những kết quả có thể chấp nhận trong
nhiều trường hợp. Tuy nhiên, phép nội suy lân cận gần nhất có thể cho ra những đồ tạo
tác (ý muốn nói là trơng ảnh như phiến đá tạc của người cổ) trong những ảnh mang cấu

trúc tinh vi, với mức xám thay đổi đáng kể từđiểm ảnh này sang điểm khác. Hình 8-2

đưa ra một ví dụ các ảnh quay bằng phép nội suy lân cận gần nhất, với kết quả bị hiệu

ứng răng cưa ở một cạnh nào đó.

8.2.2 Phép nội suy song tuyến tính (Bilinear Interpolation)

Phép nội suy bậc thứ nhất (first-order), hay song tuyến tính (binear) mang lại kết quả

mong muốn hơn phép nội suy bậc không, mà việc lập trình chỉ hơi phức tạp và tốn thời
gian một chút. Vì việc tạo một mặt phẳng đi qua bốn điểm là vấn đề quá khó khăn, phép
nội suy bậc một trên hệ toạđộ vng góc địi hỏi phải có hàm song tuyến tính.

Đặt f(x,y) là hàm hai biến đã biết tại đỉnh của hình khối vng góc. Giả sử ta muốn
thiết lập phép nội suy giá trị hàm f(x,y) tại một điểm tuỳ ý nằm bên trong hình vng
(Hình 8-3). Chúng ta cũng có thể thực hiện như vậy bằng sự điều chỉnh hyperbolic
paraboloic, xác định bởi biểu thức song tuyến tính

d
cxy
by
ax
y
x

f( , )    (2)

đi qua bốn giá trịđã biết.

Bốn hệ số, ađến d, được chọn để cho hàm f(x,y)điều chỉnh các giá trịđã biết tại bốn

góc. Có một thuật giải đơn giản hơn để tạo ra một hàm nội suy song tuyến tính mà có thể
điều chỉnh hàm f(x,y) tại các góc. Trước hết, chúng ta nội suy tuyến tính giữa hai điểm
phía trên để thiết lập giá trị của

)]
0
,
0
(
)
1
,
0
(
[
)
0
,
0
(
)
0
,

(x f x f f

f    (3)

Tương tự cho hai điểm ở phía dưới

)]
1
,
0
(
)
1
,
1
(
[
)
1
,
0
(
)
1
,

(x f x f f

f    (4)

Cuối cùng, chúng ta nội suy tuyến tính theo phương thẳng đứng để xác định giá trị

của

)]
0

,
(
)
1
,
(
[
)
0
,
(
)
,

(x y f x y f x f x

f    (5)

Thay biểu thức (3) và (4) vào biểu thức (5), khai triển, ta được

</div>
(4)<div class='page_container' data-page=4>

nó có cùng dạng với biểu thức (2) và vì thế nó là song tuyến tính. Khi thay vào,krõ
ràng là biểu thức (6) điều chỉnh bốn giá trịđã biết của f(x,y) tại các góc của khối vng
góc.

Lưu ý rằng nếu chúng ta cho x hoặc y là hằng số (khơng đổi) thì biểu thức (2) trở

thành tuyến tính theo biến khác. Điều này làm sáng tỏ rằng hyperbolic paraboloic là một

bề mặt giới hạn hai chiều; có nghĩa là nó cắt tất các mặt phẳng song song với mặt phẳng
xz và tất cả các mặt phẳng song song với mặt phẳng yz theo một đường thẳng.

Phép nội suy song tuyến tính có thểđược thực hiện trực tiếp bằng biểu thức (6), hoặc
thực hiện phép nội suy tam tuyến tính (triple linear) cho bởi biểu thức (3), (4) và (5). Vì

biểu thức (6) bao gồm bốn phép nhân và tám phép cộng hoặc trừ nên các chương trình

biến đổi hình học đặc thù được thực hiện sau, và nó chỉ yêu cầu ba phép nhân và sáu
phép cộng hoặc trừ.

Khi bốn điểm ảnh lân cận liền kề được nội suy bằng biểu thức song tuyến tính, bề

mặt thu được phù hợp về độ rộng tại các đường biên lân cận, nhưng khơng phù hợp với

độ nghiêng. Vì thế, một bề mặt được tạo bởi phép nội suy song tuyến tính là liên tục,

nhưng nói chung đạo hàm của nó là khơng liên tục tại các biên lân cận.

8.2.3 Phép nội suy bậc cao hơn (Higher Order)

Trong các phép tốn hình học, hiệu ứng làm trơn (smoothing effect) của phép nội suy

mức xám song tuyến tính có thể làm suy giảm những chi tiết sắc xảo trong ảnh, đặc biệt

là khi phóng to. Trong các ứng dụng khác, những điểm gián đoạn độ nghiêng của phép

nội suy song tuyến tính có thể tạo ra những kết quả không mong muốn. Trong cả hai
trường hợp trên, những kết quả tính tốn thêm của phép nội suy bậc cao hơn có thểđược
chứng minh là đúng. Một hàm tương tự, nhưng phức tạp hơn, biểu thức (2) và có nhiều
hơn bốn hệ sốđược thực hiện đểđiều chỉnh thông qua một trong các điểm lân cận.

Nếu số hệ số bằng với số điểm thì có thể tạo ra một bề mặt nội suy để điều chỉnh tại
từng điểm. Nếu số điểm lớn hơn số hệ số, một thủ tục điều chỉnh đường cong hay tối
thiểu hố lỗi sẽđược sử dụng. Các ví dụ về các hàm nội suy bậc cao hơn là các khối lập

phương, các hàm Legendre tập trung và hàm sin(x)/x. Hàm sau cùng đã được đề cập

đến trong các chương trước. Phép nội suy bậc cao hơn thường được thực hiện bằng phép
nhân chập. Phần 2 của tài liệu này sẽđè cập đến điều này.

8.3 PHÉP BIẾN ĐỔI KHƠNG GIAN

Biểu thức (1) cho ta cơng thức tổng quát về phép biến đổi không gian. Chúng ta cần

phải xem xét một số trường hợp đặc biệt ít phức tạp hơn trước khi đi vào các phép tốn

hình học chung.

8.3.1 Các phép biến đổi đơn giản

Nếu ta đặt

y
y
x
b
x
y
x

a( , ) ( , ) (7)

vào biểu thức (1), ta sẽ có phép tốn số học, mà chie đơn thuần là sao chép f sang g

không không thay đổi gì cả

Nếu ta đặt

0 ( , )

)
,

(x y x x b x y y y

</div>
(5)<div class='page_container' data-page=5>

chúng ta sẽ có phép tốn biến đổi, mà trong đóđiểm x0,y0 được tịnh tiến về gốc toạ

độ và các đặc điểm bên trong ảnh được chuyển đi một lượng 02

0 y

x  . Dùng công thức

được là phối hợp đồng đều (homogeneous coordinate), chúng ta có thể xem mặt phẳng

x-y là mặt phẳng z = 1 của không gian x, y, z ba chiều và viết lại biểu thức (8) dưới dạng
mảtận như sau

































1
1
0
0
1
0
0
1
1
)
,
(
)
,
(
0
0
y
x
y
x
y
x
b
y
x
a
(9)

Đặt
d
y
y
x
b
c
x
y
x

a( , ) / ( , ) / (10)

sẽ phóng to ảnh với hệ ssó c theo hướng x và hệ số d theo hướng y. Gốc toạđộ của

ảnh (thường là góc trên-trái) vẫn giữ nguyên khi nảh được “mở rộng”. Theo sự phối hợp

đồng đều, biểu thức (10) được viết lại như sau







































1
1
0
0

1
0
0
1
1
)
,
(
)
,
(
0
0
y
x
y
d
x
c
y
x
b
y
x
a
(11)

Đặt c = -1 ta được sự lệch hướng theo trục y,
y
y

x
b
x
y
x

a( , ) ( , ) (12)

và tương tự với d và trục x.

Cuói cùng, đặt

)
sin(
)
cos(
)
,

(x y x  y 

a   (13)

và
)
cos(
)
sin(
)
,

(x y x  y 

b   (14)

tạo ra một (cw rotation through) quay một góc  quanh gốc toạ độ. Biểu thức này có

thểđược viết theo toạđộđồng nhất như sau




















 












1
1
0
0
0
)
cos(
)
sin(
0
)
sin(
)
cos(
1
)
,
(
)
,

(
y
x
y
x
b
y
x
a




(15)

Rõ ràng chúng ta có thể kết hợp phép tịnh tiến với phép phóng đại để tạo ra ảnh "lớn
thêm" một điểm nữa trừ gốc toạ độ. Cũng tương tự, chúng ta có thể kết hợp phép tịnh
tiến với phép quay để tạo ra phép quay quanh một điểm tuỳ ý.

Toạ độ đồng nhất cung cấp một cách tương tự để xác định công thức cho các phép

tịnh tiến phức hợp. Ví dụ, phép quay xung quanh điểm x0, y0 được thực hiện bởi công

</div>
(6)<div class='page_container' data-page=6>

































 






















1
1
0
0
1
0
0
1
1
0
0
0
)
cos(

)
sin(
0
)
sin(
)
cos(
1
0
0
1
0
0
1
1
)
,
(
)
,
(
0
0
0
0
y
x
y
x
y

x
y
x
b
y
x
a




(16)

Trước tiên ảnh được tịnh tiến sao cho điểm x0, y0 trùng gốc toạđộ, sau đóđược quay

với góc , và sau đó được tịnh tiến về lại gốc ban đầu của nó. Thực hiện nhân biểu thức
(16) cho ra một phương trình tịnh tiến gần đúng. Các phép tịnh tiến khác cũng có thể
được xây dựng tương tự. Trong cấu trúc vế phải của biểu thức, phép toán được thực hiện
từ trái sang phải.

Thực hiện tách rời (Separable Inplementations). Nếu một ảnh được đưa ra đẻ

quay hay phóng to [biểu thức (11)], thì các toạđộ điểm ảnh ra a(x,y) và b(x,y) chỉ phụ

thuộc vào x và y tương ứng. Vì thế, có khả năng, và đơi khi cúng hiệu quả hơn, để thực
hiện phép toán trong hai bước. Ví dụ, đầu tiên là thực hiện theo chiều ngang, tạo ra một

ảnh trung gian. Sau đó thực hiện theo chiều dọc, sử dụng ảnh trung gian nhưđầu vào của
nó để tạo ra kết quả cuối cùng.

Catmull và Smith đã cho thấy là có khả năng để thực hiện một phép quay theo thủ tục
hai bước tương tự. Giải biểu thức (13) theo x ta được

)
cos(
)
sin(
)
,
(


y
y
x
a

x  (17)

và thay vào biểu thức (14) dẫn đến

)
cos(
)
sin(
)
,
(
)
,

(

 y
y
x
a
y
x

b   (18)

Vì thế, chúng ta có thể sử dụng biểu thức (13), biểu thức tuyến tính trong x theo dịng
qt bất kỳ, theo phép kết hợp với b(x,y) = y trong phần đầu (chỉ có chiều ngang) của
phép tốn. Sau đó chúng ta có thể dùng biểu thức (18), biểu thức tuyến tính trong y theo
cột bất kỳ với a(x,y) = x trong phần hai (chỉ có chiều dọc) của phép toán.

Trong phép quay loại này, các đặc điểm của ảnh được "nén" theo chiều x bởi hệ số
cos()ở bước thứ nhất, và sau đó được "bung" theo chiều y bởi hệ số sin()ở bước thứ

hai. Kỹ thuật này sẽ khơng có kết quả với những góc là bội của 900, khi đó cosin sẽ bằng
0, và sai số sẽ hạn chế trong những góc nhỏ hơn.

Đối với những ứng dụng ghi lại ảnh, góc quay yêu cầu thường nhỏ. Thậm chí điều
này khơng phải như vậy, phép quay với góc bơi của 900 vẫn có thể thực hiện bằng cách
hoán đổi hàng và cột đơn giản. Vì thế, có thể quay một ảnh theo một góc bất kỳ trong
khi vẫn giữ góc quay thực sự giữa +450 và -450 và hệ số nén khơng nhỏ hơn 0.707. Sau

đó, với giới hạn này phép tịnh tiến, phóng đại và quay có các phép thực hiên một chiều.

8.3.2 Các phép biến đổi chung

Đối với các phép biến đổi không gian đơn giản có liên quan, việc sử dụng một biểu
thức giải tích cho biểu thức (1) có thể là thiết thực. Tuy nhiên, trong nhiều ứng dụng xử

lý ảnh, phép biến đổi khơng gian mong muốn có quan hệ phức tạp và khơng tn theo

một biểu thức tốn học thích hợp nào. Hơn thế nữa, phép tịnh tiến điển ảnh thường thu

được từ kích thước thực sự của ảnh và nó xác định rõ phép tốn hình học trong các số

</div>
(7)<div class='page_container' data-page=7>

học trong camera cho nên mơ hình lưới được hiển thị sẽ khơng chính xác là hình chữ

nhật (Xem hình 8-4). Phép biến đổi khơng gian cần có ở đây là làm cho mơ hình lưới

thành hình chữ nhật trở lại, bằng cách đó ta sẽ hiệu chỉnh được độ biến dạng do camera
gây ra. Sau đó cùng một phép biến đổi khơng gian này có thể sử dụng trên ảnh tiếp theo

được số hoá trên cùng một camera (giả thiết rằng sự biến dạng không phụ thuộc vào
cảnh), bằng cách đó ta có thể tạo ra ảnh khơng biến dạng.

HÌNH 8-4

Hình 8-4 Điều chỉnh hình học của một camẻa trên tàu vũ trụ Ranger
trước đây, (a) trước điều chỉnh, (b) sau điều chỉnh

8.3.3 Xác định rõ bằng các điểm hiệu chỉnh (Specification by Control 
Points)

Thật là thuận lợi nếu xem phép biến đổi không gian như một chuỗi các giá trị dịch
chuyển cho các điểm hiệu chỉnh (control points) được chọn trong ảnh. Bở vì chỉ một

phần nhỏ các điểm ảnh được chỉ rõ thực sự, dịch chuyển của những điểm không hiệu
chỉnh phải được xác định bằng nội suy.

Có một cách để thực hiện điều này, đó là khai triển các biểu thức hàm theo a(x,y) và
b(x,y) trong biểu thức (1). Thông thường, một đa thức được sử dụng như dạng tổng quát
của biểu thức biến đổi. Các tham số của nó được chọn để làm cho nó phù hợp với các

điểm hiệu chỉnh và độ dịch chuyển cho trước của chúng. Điều này gọi là làm cong đa 
thức (polynominal warping). Nó cần thiết việc sử dụng các đa thức từ bậc năm trở xuống

đối với hàm biến đổi.

Trong nhiều trường hợp, giới hạn làm cong đa thức sẽ không chứa đựng phép tốn
phức tạp. Vì thế, một vài chương trình đối với các phép tốn hình học phân rã ảnh thành
những miền đa thức và sử dụng các hàm ánh xạ song tuyến tính piecewise. Người sử

dụng định rõ một lưới hiệu chỉnh đầu vào từ các điểm hiệu chỉnh tạo thành những đỉnh
của những tứ giác kề nhau trong ảnh vào. Lưới hiệu chỉnh đầu vào ánh xạđến một lưới
bên cạnh, hình chữ nhật nằm ngang trong ảnh ra. Các đỉnh (các điểm hiệu chỉnh đầu
vào) của tứ giác ánh xạ trực tiếp đến các đỉnh của hình chữ nhật tương ứng. Tương tự,
các điểm bên trong một tứ giác đầu vào ánh xạđến những điểm bên trong hình chữ nhật

</div>