Tiểu luận môn học Xử Lý Ảnh
MỞ ĐẦU
Xử lý ảnh là một lĩnh vực đã và đang rất phát triển. Khái niệm xử lý ảnh có liên
quan tới nhiều ngành học và hướng nghiên cứu khác nhau. Từ những năm 1970 khi
mà năng lực tính toán của máy tính ngày càng trở nên mạnh mẽ hơn, các máy tính lúc
này có thể xử lý được những tập dữ liệu lớn như các hình ảnh, các đoạn phim thì khái
niệm và kỹ thuật về thị giác máy ngày càng được nhắc đến và nghiên cứu
nhiều hơn cho tới ngày nay.Hệ thống xử lý ản bao gồm lý thuyết và các kỹ thuật
liên quan nhằm mục đích tạo ra một hệ thống nhân tạo có thể tiếp nhận thông tin từ
các hình ảnh thu được hoặc các tập dữ liệu đa chiều. Việc kết hợp các kỹ thuật khác
như công nghệ thông tin, truyền thông, điện tử, điều khiển tự động, cơ khí… cho
chúng ta rất nhiều ứng dụng trong đời sống hàng ngày cũng như trong khoa học, an
ninh, quân sự… Ngày nay, ứng dụng của xử lý ảnh đã trở nên rất rộng lớn và đa dạng,
len lỏi vào mọi lĩnh vực từ quân sự, khoa học, vũ trụ, cho đến y học, sản xuất, và tự
động hóa tòa nhà.
Trang 1
Tiểu luận môn học Xử Lý Ảnh
Mục lục
Chương 1: Thu thập ảnh
1.1. Cơ chế thu thập ảnh Pinhole……………………………… 2
1.2. Cảm biến CCD…………………………………………… 6
Chương 2: Xử lý tăng cường chất lượng ảnh.
2.1. Lọc nhiễu………………………………………………… 12
2.2. Tăng cường độ sáng, độ tương phản ảnh………………… 14
Chương 3: Các phương pháp xử lý ảnh cơ bản.
3.1. Tăng giảm kích thước……………………………………… 16
3.2. Xoay ảnh…………………………………………………… 18
3.3. Biến đổi không gian màu ảnh (RGB)…………………………21
Chương 4: Dò biên và phân vùng ảnh.
4.1. Kỹ thuật dò biên………………………………………………24
4.2. Phân vùng ảnh……………………………………………… 30

Do độ mở quá nhỏ, ảnh pịnhole rất rối, đòi hỏi thời gian phơi sáng dài, tùy từng
hoàn cảnh mà có thể là vài giây, vài phút cho đến vài ngày. Cũng do độ mở nhỏ, độ
sâu trường ảnh gần như là vô hạn, độ nét ở tất cả mọi điểm trên tấm ảnh là ngang bằng
nhau.Vệ mặt chất lượng, ảnh pinhole thường bị mờ, đen ở góc và sai sắc. Ưu điểm
duy nhất là ảnh không bị méo hình ở mọi góc độ do không chịu hiện tượng cầu sai của
thấu kính.Mặc dù có rất nhiều hạn chế, nhưng ở thời đại nào, nhiếp ảnh pinhole cũng
có một lượng tín đồ nhất định
Máy ảnh DSLR với "ống kính" pinhole.
Với một thân máy DSLR, nhiếp ảnh pinhole đã trở nên dễ dàng hơn rất nhiều so với
thời cha ông, do những thân máy này có khả năng đo sáng tự động, dải nhạy sáng
cao giúp tăng tốc độ chụp, trong một số điều kiện ánh sáng tốt có thể loại bỏ sự hỗ
trợ của chân máy. Nhiếp ảnh pinhole thực sự là một trải nghiệm thú vị không nên bỏ
qua đối với các tay máy DSLR, khi được bỏ qua những ống kính tân tiến nhất để trở
về với “cội nguồn” nhiếp ảnh của con người.Tuy nhiên, tạo ra một tấm ảnh pinhole
có chất lượng là một việc không dễ. Để tấm ảnh có độ nét cao nhất, những tay chơi
pinhole chuyên nghiệp phải sử dụng những tấm kim loại dát mỏng, với “lỗ kim” cực
nhỏ được đục bằng tia laser với độ chính xác cao nhất. Nhưng quan trọng hơn cả vẫn
là sự kiên nhẫn và lòng đam mê của người chụp ảnh.
1.2. Cảm biến máy ảnh ( CCD)
Trang 5
Tiểu luận môn học Xử Lý Ảnh
Camera CCD (Charge CoupleDevice) là một thiết bị thu nhận ảnh dưới dạng
tín hiệu số bằng cách thu nhận cường độ sáng tại từng điểm thông qua một loại linh
kiện có tên là photo diode. Cường độ sáng tại mỗi điểm này sẽ được mã hoá thành 3
giá trị màu cơ bản là RED, GREEN, BLUE theo lý thuyết màu do Thomson đưa ra
năm 1802. Ảnh nhận được từ Camera loại này là một ma trận Vector:





nhiệt độ transitor trên một diện tích. Bởi vậy, các máy ảnh số hiện nay sử dụng CCD
có khả năng cho tới 5-6 triệu điểm ảnh.
Cùng với CCD, một thiết bị điện tử khác là ADC (analog to digital converter -
bộ chuyển tín hiệu tương tự sang tín hiệu số) độc lập thực hiện chức năng chuyển đổi
giá trị điện tích của các điểm trên CCD sang một giá trị số biểu thị màu tương ứng.
Nếu kích thước ma trận trên CCD quyết định độ phân giải, thì ADC xác định độ sâu
màu (color depth, đo bằng bit), tức khả năng thể hiện các sắc độ màu của hình ảnh
được ghi nhận. Độ sâu càng lớn, màu càng trung thực.
Trang 6
Tiểu luận môn học Xử Lý Ảnh
Cấu trúc của 1 CCD
Năm 1999, công ty Fuji Photo Film và Fujifilm Microdevices đã phát triển
thành công thế hệ tiếp theo của CCD là Super CCD. Bằng cách thay đổi hình dạng của
các pixel và sắp xếp chúng lại theo cách mới, Super CCD hơn hẳn CCD ở những điểm
sau:
-Nhờ diode quang có dạng bát giác và các điểm ảnh được sắp xếp theo kiểu tổ
ong, Super CCD có độ phân giải cao hơn, tỷ suất tín hiệu / nhiễu (S/N) cao hơn, vùng
màu động rộng hơn so với CCD thông thường.
-Sắp xếp theo kiến trúc tổ ong phù hợp hơn với quy tắc phân bố tần số trong tự
nhiên và đặc trưng trong mắt người. Vì thế độ hiệu quả điểm ảnh của CCD tăng lên
1,6 lần – Super CCD 2 triệu điểm ảnh có thể tạo ảnh có chất lượng tương đương ảnh
tạo ra bởi CCD 3 triệu điểm ảnh.
-Kiến trúc tổ ong kết hợp với công nghệ xử lý tín hiệu cho phép hạn chế độ
suy giảm chất lượng ảnh khi sử dụng chức năng phóng đại số (digital zoom)
-Kiến trúc này cho phép bỏ qua bước đọc lại dữ liệu ảnh mà không làm giảm
chất lượng ảnh ; chẳng hạn cho phép xuất ra tín hiệu video chất lượng cao.
-Để đáp ứng cùng chức năng, kiến trúc sử dụng CCD đơn giản hơn nhiều so
với CCD thông thường.
-Super CCD tiết kiệm được năng lượng vì có khả năng ghi nhận được hình ảnh
độ phân giải cao với lượng điểm ảnh ít hơn.

nhằm giảm bớt màu giả tạo.
Hình 3.5 CCD thế hệ mới công nghệ Foveon X3 của Sigma.
Thử nghiệm cho thấy với công nghệ FOVEON X3 cho những tấm ảnh sắc nét
hơn, chi tiết màu tốt hơn và thực hơn, dù không cần phải hiệu chỉnh. Máy ảnh số sử
dụng công nghệ Foveon X3 không cần sức mạnh xử lý để tạo thông tin màu bị mất,
giảm thiểu đòi hỏi về phần cứng, thiết kế đơn giản và tối thiểu hóa thời gian trễ giữa
hai lần bấm của máy. Công nghệ Foveon X3 còn mở ra khả năng thiết kế những dòng
thiết bị thế hệ mới, không có ranh giới giữa ảnh tĩnh và video, không có sự suy giảm
chất lượng. Vì bộ cảm ứng ảnh dùng công nghệ Foveon X3 có thể bắt đầy đủ các màu
trên mọi pixel nên các pixel này có thể nhóm lại với nhau để tạo ra một hệ pixel lớn
hơn: “siêu pixel” với đầy đủ thông tin màu. Năng lực này gọi là khả năng thay đổi
điểm ảnh – Vairable Pixel Sizing (VPS), chuẩn mới đầu tiên của ảnh số. Với VPS, tín
hiệu từ các nhóm pixel có thể được nối lại với nhau để máy ảnh đọc chúng như một
pixel. Ví dụ, một bộ cảm biến 2300 x 1500 có thể chứa trên 3,4 triệu pixel. Nhưng nếu
VPS được dùng để nhóm các pixel này khối 4x4, bộ cảm biến ảnh sẽ tự điều chỉnh để
có độ phân giải 575 x 375 pixel, mỗi thành phần sẽ hơn 16 lần so với thành phần gốc.
Kích cỡ và cấu hình của một nhóm pixel có thể là biến số 2x2, 4x4, 3x5 , và được
điều chỉnh thông qua bộ xử lý tích hợp bên trong Foveon X3. Điều này cho phép CCD
Trang 9
Tiểu luận môn học Xử Lý Ảnh
có thể thu nhận bức ảnh đầy đủ màu trong điều kiện ánh sáng yếu bằng cách giảm tín
hiệu nhiễu nhờ khả năng gộp điểm ảnh. Sử dụng VPS để làm giảm độ phân giải cũng
cho phép bộ cảm biến chụp được số khung ảnh cao hơn, tăng tốc độ chụp mỗi tấm
ảnh.
Trang 10
Tiểu luận môn học Xử Lý Ảnh
CHƯƠNG 2: XỬ LÝ TĂNG CƯỜNG CHẤT LƯỢNG ẢNH
Trong hai thập kỉ gần đây, lọc bỏ nhiễu xung là một trong những vấn đề rất
được quan tâm ở lĩnh vực xử lý ảnh. Xuất phát từ nguyên nhân thực tế như lỗi trong
quá trình truyền tải, trục trặc ở bộ phận cảm biến trên thiết bị thu hình kỹ thuật số,…

ảnh thu được có thể biểu diễn bởi: Xqs = Xgốc * Nhiễu xung : Nhiễu xung thường
gây đột biến tại một số điểm ảnh.
2.1. Các kỹ thuật chính được dùng làm trơn ảnh
2.1.1. Làm trơn nhiễu bằng lọc tuyến tính
- Lọc trung bình (Mean Filter)
- Lọc thông thấp (Low pass Filter)
- Lọc đồng hình (Homomorphie Filter)
- Gaussian Blur
2.1.2. Làm trơn nhiễu bằng lọc phi tuyến
- Lọc trung vị (Median Filter)
- Lọc ngoài (Outlier Filter)
- Lọc loại bỏ nhiễu đốm Crimmins (Crimmins Speckle Removal)
- Bộ lọc giữ biên (Kuwahara Filter)
2.1.3.Ứng dụng của làm trơn ảnh
Xét ở khía cạnh nào đó, ta có thể nói làm trơn ảnh được ứng dụng khá phổ biến
trong nhiều lĩnh vực của đời sống như giải trí, y học, an ninh và một số lĩnh vực
khác… Làm trơn ảnh nếu nó đứng riêng lẻ thì hầu như không có ứng dụng gì ngoài
công dụng theo nghĩa đen của nó là làm mịn ảnh, và giảm nhiễu. Nhưng khi đặt nó
vào trong quy trình xử lý thì nó rất quan trọng, kết quả của nó giúp các xử lý phía sau
chính xác hơn. Ví dụ như dò biên với thuật toán canny, trước tiên người ta sẽ dùng
Gaussian để làm mịn ảnh trước giúp lọai bỏ nhiễu nhằm giúp kết quả dò biên tránh
được những sai lầm do nhiễu gây ra. Trong một số trường hợp, các đối tượng thông
tin có cùng tính chất với nhiễu (điển hình là trong ảnh siêu âm), việc phát hiện đối
tượng khác thường (detect abnormal object) và loại bỏ chúng trước khi tiến hành các
xử lý cao hơn là rất quan trọng. Tùy từng đặc thù ảnh và nhiễu mà người ta chọn
phương pháp, và sử dụng cửa sổ (design kernel) thích hợp nhằm đạt hiệu quả cao nhất
là loại bỏ cái cần loại, giữ lại cái cần giữ. Ứng dụng vào công nghệ giám sát “camera
lọc nhiễu ba chiều” nhằm tăng cường công tác bảo mật an toàn – an ninh, nếu xảy ra
bất cứ một vấn đề hay sự cố gì đều được camera ghi lại, từ đó làm tư liệu, bằng chứng
để tìm ra nguyên nhân xảy ra vấn đề.

tính toán việc chuyển đổi (Transformation) mỗi điểm ảnh của hình, giúp làm giảm
nhiễu và mức độ chi tiết (không mong muốn) của hình ảnh. Đây là phương trình hàm
Gaussian (Gaussion Distribution) trong không gian một chiều.
Với x, y là tọa độ theo hai trục đứng và ngang. Trong không gian hai chiều,
công thức này sản sinh ra những đường viền là những đường tròn đồng tâm, tuân theo
logic phân tán Gausian từ điểm trung tâm. Giá trị từ hệ thống phân tán này sẽ được sử
dụng để xây dựng một ma trận tích chập dùng tính toán phép tích chập với ảnh gốc.
Giá trị mới sau khi tính tích nhân chập với cửa sổ (kernel) đại diện cho hàm Gaussian
có thể coi là trung bình lượng giá của các điểm ảnh xung quanh nó. Ta thấy rằng giá
trị lượng của phần tử trung tâm kernel tương ứng với điểm ảnh đang xét là lớn nhất,
giá trị này sẽ nhỏ hơn đối với các phần tử tương ứng với các điểm ảnh kế cận một
Trang 14
Tiểu luận môn học Xử Lý Ảnh
cách đối xứng và tỉ lệ thuận với khoảng cách của phần tử này với trung tâm. Tính chất
này giúp giữ lại đường viền và đường biên cũng như làm mờ một cách đồng bộ hơn so
với các phương pháp khác. Trong lý thuyết, hàm Gaussian tại mỗi điểm trên hình là
khác 0. Điều này có nghĩa là Gaussian kernel nên có kích thước bằng với hình ảnh và
giá trị tại mỗi phần luôn khác 0. Tuy nhiên trong thực hành, do việc tính toán dựa trên
xấp xỉ rời rạc (Discrete Appoximation) cho nên giá trị của các phần tử trên bề mặt
Gaussian ở khoảng cách lớn hơn 3σ so với trung tâm gần như không đáng kể (tiệm
cận 0). Do vậy các Gaussian distribution ngoài bán kính này sẽ bị bỏ qua, đó cũng là lí
do mà thông thường Gaussian kernel có kích thước giới hạn 3, 5, 7 (Cái này tùy thuộc
vào giá trị phương sai chuẩn mà bạn chọn). Khoảng cách giữa hai điểm gần nhau
trong Gausssian kernel là σ.
Trang 15
Tiểu luận môn học Xử Lý Ảnh
CHƯƠNG 3: CÁC PHƯƠNG PHÁP XỬ LÝ ẢNH CƠ BẢN
Xử lý ảnh là bước cần thực hiện trước khi đưa ra các quyết định về hình ảnh.
Việc sử dụng phần mềm Matlab hỗ trợ rất trong trong xử lý ảnh.
3.1 Các hàm chuyển đổi kiểu ảnh:

Tiểu luận môn học Xử Lý Ảnh
ở trên, cũng có một số hàm mà trả lại kiểu ảnh khác như một phần trong thao tác mà
chúng thực hiện. Chuyển đổi không gian màu.
Toolbox xử lý ảnh biểu diễn màu sắc như các giá trị RGB ( trực tiếp trong ả
ảnh chỉ số ). Tuy nhiên, có các phương pháp khác cho việc biểu diễn màu có thể được
đại diện bởi các giá trị hue, saturation và các giá trị thành
Toolbox cung cấp một tập các thủ tục để chuyển đổi giữa các không gian
chúng coi dữ liệu màu sắc dưới dạng RGB tuy nhiên, ta có thể xử lý một ảnh màu
khác nhau bằng cách chuyển đổi nó sang RGB sau đó chuyển đổi ảnh màu ban đầu.
3.2 Chuyển đổi định dạng các file ảnh:
Để thay đổi định dạng đồ hoạ của một ảnh, sử dụng hàm imread để đọc m
hàm imwrite đồng thời chỉ ra định dạng tương ứng.
Để minh hoạ, ví dụ sau đây sử dụng hàm imread để đọc một file BMP vào
hàm imwrite lưu ảnh này dưới định dạng PNG
bitmap = imread('mybitmap.bmp','bmp'); imwrite(bitmap,'mybitmap.png','png');
3.3 Thay đổi kích thước ảnh
- Để thay đổi kích thước của một ảnh, sử dụng hàm imresize. Sử dụng hàm này ta có
thể:
+ Chỉ ra kích thước của ảnh kết quả.
+ Chỉ ra phương pháp nội suy được sử dụng.
+ Chỉ ra bộ lọc được sử dụng để ngăn ngừa hiện tượng răng cưa.
+ Chỉ ra kích thước cho ảnh kết quả
- Sử dụng hàm imresize, ta chó thể chỉ ra kích thước của ảnh kết quả theo hai cách:
+ Bằng cách chỉ ra hệ số phóng đại được sử dụng trên ảnh.
+ Bằng cách chỉ ra chiều của ảnh kết quả.
Sử dụng hệ số phóng đại ảnh để mở rộng một ảnh, chỉ ra hệ số phóng đại lớn hơn 1.
Để thu nhỏ một ảnh, chỉ ra hệ số phóng đại nằm giữa 0 và 1. Chẳng hạn, lệnh sau tăng
kích thước của ảnh I lên 1.25 lần:
Hình : Ảnh trước và sau khi imresize
I = imread('circuit.tif');

các ảnh chỉ số và bộ lọc thông thấp không thích hợp cho kiểu ảnh này.
- Ta cũng có thể chỉ ra một bộ lọc tự tạo thay cho các bộ lọc có sẵn.
Hàm imresize
Cú pháp của hàm này như sau:
Trang 18
Tiểu luận môn học Xử Lý Ảnh
B = imresize(A,m) B = imresize(A,m,method) B =imresize(A,[mrowsncols],method)
B = imresize( ,method,n) B = imresize( ,method,h)
Diễn giải
+ B=imresize(A,m): Trả lại một ảnh B lớn gấp m lần ảnh A (kích thước hình học) sử
dụng phương pháp nội suy mặc định (nearest - neighbor interpolcation). A có thể là
một ảnh chỉ số, ảnh đen trắng, RGB hoặc ảnh nhị phân. Nếu m nằm giữa 0 và 1, B sẽ
nhỏ hơn A. Nếu m lớn hơn 1, B sẽ lớn hơn A.
+ B=imresize(A,m,method): Trả lại một ảnh lớn gấp m lần ảnh A sử dụng phương
pháp nội suy method. method là một chuỗi chỉ ra phương pháp nội suy nào được sử
dụng chẳng hạn: ‘nearest’,’bilinear’,’bicubic’.
+ B=imresize(A, [mrows ncols],method): Trả lại một ảnh với kích thước được chỉ
ra bởi vector [mrows ncols]. Nếu kích thước được chỉ ra không cùng tỉ lệ với ảnh vào,
ảnh sẽ bị biến dạng . Khi kích thước của ảnh ra nhỏ hơn kích thước của ảnh vào và
phương pháp nội suy được sử dụng là ‘bilinear’ hoặc ‘bicubic’, hàm imresize áp đặt
một bộ lọc thông thấp trước khi tuyến tính hoá để giảm hiện tượng răng cưa. Kích
thước mặc định là 11x11.
Ta có thể chỉ ra một thứ tự khác cho bộ lọc mặc định sử dụng cấu trúc:
B=imresize(…,method,n): n là một số nguyên chỉ ra kích thước của bộ lọc – nxn. Nếu
n=0, hàm imresizebỏ qua bước lọc. Ta cũng có thể chỉ ra bộ lọc riêng sử dụng cú pháp
B=imresize(…,method,h): Trong đó h là một bộ lọc FIR hai chiều ( có thể được trả
về bởi các hàm ftrans2, fwind1, fwind2 hoặc fsamp2 ).
3.5 Xoay ảnh
Để xoay một ảnh, sử dụng hàm imrotate. Hàm này chấp nhận hai tham số
chính:

đồng hồ, sử dụng phương pháp nội suy các pixel gần nhất. Để quay theo chiều kim
đồng hồ hãy truyền giá trị âm cho tham số angle
+ B=imrotate(A,angle,method): Quay ảnh A một góc angle độ theo chiều kim đồng
hồ sử dụng phương pháp nội suy được chỉ ra trong method.
+ B=imrotate(A,angle,method,bbox): Quay ảnh A một góc angle độ. Tham số bbox
chỉ ra hộp biên của ảnh trả về. bbox là một chuỗi có thể nhận các giá trị sau:‘crop’:
Ảnh ra B chỉ bao gồm phần trung tâm của ảnh được quay và có cùng kích thước với
ảnh A ‘loose’: ( Mặc định ): Ảnh ra B bao gồm toàn bộ ảnh được quay và lớn hơn
ảnh A. Hàm imrotate thiết lập giá trị 0 cho các pixel ngoài biên của ảnh gốc.
Ví dụ :
- Ví dụ này đọc một ảnh quang phổ ánh sáng mặt trời được lưu trong định dạng
FITS và quay nó và căn nó theo chiều ngang.
I = fitsread('solarspectra.fts'); I = mat2gray(I); J = imrotate(I,-1,'bilinear','crop');
imshow(I) figure, imshow(J)
Trang 20
Tiểu luận môn học Xử Lý Ảnh
Trang 21
Tiểu luận môn học Xử Lý Ảnh
CHƯƠNG 4: DÒ BIÊN VÀ PHÂN VÙNG ẢNH
4.1.1 Một số khái niệm
Định nghĩa và khái niệm
Điểm Biên: Một điểm ảnh được coi là điểm biên nếu có sự thay đổi nhanh
hoặc đột ngột về mức xám (hoặc màu). Ví dụ trong ảnh nhị phân, điểm đen gọi là
điểm biên nếu lân cận nó có ít nhất một điểm trắng.
Đường biên (đường bao: boundary): tập hợp các điểm biên liên tiếp tạo
thành một đường biên hay đường bao.
Ý nghĩa của đường biên trong xử lý: ý nghĩa đầu tiên: đường biên là một
loại đặc trưng cục bộ tiêu biểu trong phân tích, nhận dạng ảnh. Thứ hai, người ta
sử dụng biên làm phân cách các vùng xám (màu) cách biệt. Ngược lại, người ta
cũng sử dụng các vùng ảnh để tìm đường phân cách.

phương pháp
dã tìm hiểu ở các phần trước.
B2: Làm nổi biên sử dụng các toán tử phát hiện biên.
B3: Định vị biên. Chú ý rằng kỹ thuật nổi biên gây tác dụng phụ là gây nhiễu
làm một số
biên giả xuất hiện do vậy cần loại bỏ biên giả.
B4: Liên kết và trích chọn biên.
4.2 Phương pháp biên cục bộ
4.2.1 Phương pháp Gradient
Định nghĩa: Gradient là một vec tơ f(x, y) có các thành phần biểu thị tốc
độ thay đổi mức xám của điểm ảnh (theo hai hướng x, y trong bối cảnh xử lý
ảnh hai chiều) tức:
Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hướng x, y tương ứng (thực tế
chọn dx= dy=1). Đây là phương pháp dựa theo đạo hàm riêng bậc nhất theo hướng x, y.
Gradient trong tọa độ góc (r,θ), với r là véc tơ, θ: góc
a. Kỹ thuật Gradient. Theo định nghĩa về Gradient, nếu áp dụng nó vào xử
Trang 23
Tiểu luận môn học Xử Lý Ảnh
lý ảnh, việc tính toán sẽ rất phức tạp. Để đơn giản mà không mất tính chất của
phương pháp Gradient, người ta sử dụng kỹ thuật Gradient dùng cặp mặt nạ
H
1
, H
2
trực giao (theo 2 hướng vuông góc). Nếu định nghĩa g
1
, g
2
là Gradient
theo hai hướng x, y tướng ứng thì biên độ g(m,n) tại điểm (m,n) được tính:

pháp tìm cực trị tổng thể theo nhiều bước. Nó dựa vào nguyên lý tối ưu của
Bellman. Nguyên lý này phát biểu như sau: “Con đường tối ưu giữa 2 điểm cho
trước cũng là tối ưu giữa 2 điểm bất kỳ nằm trên đường tối ưu đó”.
Thí dụ, nếu C là một điểm trên con đường tối ưu giữa A và B thì đoạn CB
cũng là còn đường tối ưu từ C đến B không kể đến ta đến C bằng cách nào
Trong kỹ thuật này, giả sử bản đồ biên đã được xác định và được biểu diễn
dưới dạng đồ thị liên thông N chặng. Giả sử hàm đánh giá được tính theo công thức:
Trang 25