MỤC LỤC

Danh mục bảng biểu
Hình 6.1 Các mã chuỗi đại diện cho các hướng dẫn liên kết giữa điểm cạnh
Hình 6.2 Một đường cong và mã chuỗi của nó.
hình 6.4 Sơ đồ cho thấy khoảng cách vuông góc của một điểm từ một đoạn thẳng. Các giá trị
7 được tính toán bằng cách cắm các tọa độ của điểm vào phương trình cho các đoạn thẳng
Hình 6.5 Phương pháp chia nhỏ file cho polylines
hình 6.6 khoan hình dung cho đoạn đường thẳng phù hợp
hình 6.7 Một ước tính góc xấu được sản xuất bởi một cạnh kết hợp từ dưới lên mà bị mất vị trí
góc thật sự có thể được sửa chữa bằng cách tách và hợp nhất đèo mà chia phân đoạn đầu tiên
tại một điểm gần gũi hơn với các góc đúng và sau đó hợp nhất hai phân đoạn thành một đoạn
thẳng duy nhất
Hình 6.8: Phần Conic được xác định bởi giao nhau một hình nón với một chiếc máy bay.
hình 6.9 Cắt hình nón là gần đúng định nghĩa giữa ba điểm

1


hình 6.10: Một đường conic được xác định bởi hai điểm kết thúc và tiếp tuyến từ ba đỉnh của
xấp xỉ polyline, cộng thêm một điểm bổ sung
hình 6.11 Các hình thức hướng dẫn cho một hình nón.
hình 6.12 Minh hoạ về sự khác biệt giữa việc lắp đặt một đường cong bằng cách sử dụng hồi
quy bình phương least- và lắp một đường cong bằng cách sử dụng phương pháp mạnh mẽ để
một tập hợp dữ liệu có chứa giá trị ngoại lai
hình 6.13 Một tương tự vật lý để minh họa độ nhạy của phương pháp bình phương nhỏ nhất
để tách. Ngay cả một outlier duy nhất làm cho một giải pháp bình phương nhỏ nhất vô dụng ..
Hình 6.14: lập bản đồ hình ảnh tham số không gian của một điểm trong Hough biến đổi
Hình 6.15 .: Đường Viền cho Bài tập 6.5.
Hình 6.16 sơ đồ minh hoa bài tập

Chương 6 Đường viền
Cạnh phải được liên kết thành một đại diện cho một ranh giới khu vực. Đại diện này được gọi
là một đường viền. Các đường viền có thể được mở hoặc đóng cửa. Đường nét khép kín tương
ứng với ranh giới khu vực, và các điểm ảnh trong khu vực có thể được tìm thấy bởi một thuật
toán điền. Một đường viền mở có thể là một phần của một ranh giới khu vực. Những khoảng
trống có thể xảy ra trong một ranh giới khu vực vì sự tương phản giữa các vùng có thể không
đủ để cho phép các cạnh dọc theo ranh giới được tìm thấy bởi một máy dò cạnh. Ngưỡng phát
hiện cạnh có thể đã được đặt quá cao, hoặc độ tương phản cùng một số phần của ranh giới có
thể là quá yếu so với các khu vực khác của hình ảnh mà không có ngưỡng duy nhất hoạt động
ở khắp mọi nơi trong hình ảnh. Mở đường nét cũng xảy ra khi các mảnh vỡ dòng được liên kết
với nhau, ví dụ, khi mảnh vỡ dòng được liên kết cùng một cơn đột quỵ trong một bản vẽ hoặc
mẫu chữ viết tay.
Một đường viền có thể được biểu diễn như là một danh sách có thứ tự các cạnh hoặc bởi một
đường cong. Một đường cong là một mô hình toán học cho một đường viền. Ví dụ về đường
cong bao gồm các đoạn đường và thanh chốt khối. Có một số tiêu chí cho một đại diện đường
viền tốt:
Hiệu quả: Các đường viền phải là một đơn giản, đại diện nhỏ gọn.
Độ chính xác: Các đường viền nên phù hợp chính xác các tính năng hình ảnh.

2


Tính hiệu quả: Các đường viền nên phù hợp với các hoạt động được mỗi hình thành trong
giai đoạn sau của ứng dụng.
Tính chính xác của các đại diện đường viền được xác định bởi đường cong được sử dụng để
mô hình hóa các đường viền, bởi hiệu suất của thuật toán vừa vặn đường cong, và bởi tính
chính xác của các ước tính về vị trí cạnh. Các đại diện đơn giản nhất của một đường viền là
một danh sách có thứ tự các cạnh của nó. Sự đại diện này là chính xác như các ước tính vị trí
cho các cạnh, nhưng là đại diện nhỏ gọn nhất và có thể không cung cấp một đại diện hiệu quả
cho phân tích hình ảnh tiếp theo. Lắp mô hình đường cong phù hợp với các cạnh làm tăng độ

chính xác, vì lỗi ở vị trí rìa đang giảm đi thông qua tính trung bình, và nó làm tăng hiệu quả
bằng cách cung cấp một đại diện thích hợp hơn và nhỏ gọn hơn cho các hoạt động tiếp theo.
Ví dụ, một tập các cạnh nằm dọc theo một con đường có thể được đại diện một cách hiệu quả
nhất bằng cách lắp một đường dây để các cạnh. Đại diện này giúp đơn giản hoá các tính toán
sau này, chẳng hạn như xác định các định hướng hoặc chiều dài của đường, và tăng độ chính
xác, vì trung bình bình phương lỗi giữa đường dự kiến và dòng thực sẽ nhỏ hơn so với các lỗi
giữa các dòng đúng và bất kỳ mép .
Phần đầu tiên trong chương này trình bày sự khác biệt giữa tiểu hình học của đường cong
trong mặt phẳng. Phần thứ hai cung cấp một tập hợp các kỹ thuật để tính toán tính đường viền
như chiều dài, tiếp tuyến, và độ cong từ danh sách các cạnh, mà không cần lắp một mô hình
đường cong với các cạnh. Các phần còn lại bao gồm mô hình đường cong và kỹ thuật cho phù
hợp các mô hình để các đường nét.
Trước khi tiếp tục, một số thuật ngữ phải được xác định. Một danh sách interpolatesa đường
cong của điểm nếu đường đi qua các điểm sấp xĩ lắp một đường cong thành một danh sách các
điểm với đường cong đi qua gần các điểm, nhưng không nhất thiết phải đi qua một cách chính
xác thông qua các điểm. Trong các phần sau, chúng ta sẽ bắt đầu bằng cách giả sử rằng các
cạnh được cung cấp bởi một thuật toán phát hiện cạnh là chính xác và sẽ phù hợp đường cong
để các điểm cạnh sử dụng phương pháp nội suy. Các cạnh được cung cấp bởi phát hiện cạnh
áp dụng các hình ảnh thực sẽ không được chính xác. Sẽ có một số lỗi trong các vị trí ước tính
của cạnh. Phần sau sẽ trình bày phương pháp đường cong xấp xỉ.
Định nghĩa 6.1 Một danh sách cạnh là một tập hợp có thứ tự các điểm cạnh hoặc các mảnh
vỡ.
Định nghĩa 6.2 Một đường viền là một danh sách cạnh hoặc đường cong đã được sử dụng để
đại diện cho các danh sách cạnh.

Định nghĩa 6.3 Một ranh giới là đường viền khép kín bao quanh một khu vực.
Trong chương này, thuật ngữ edges sẽ thường tham khảo các điểm cạnh. Định hướng cạnh
3



không được sử dụng bởi hầu hết các đường cong thuật toán phù hợp. Trong vài trường hợp các
thuật toán có sử dụng các định hướng cạnh, nó sẽ được rõ ràng từ các bối cảnh edges chỉ hạn
để cạnh mảnh.

6.1 Hình học của đường cong
Đường cong phẳng có thể được biểu diễn theo ba cách khác nhau: sự rõ ràng dạng y = f (x),
hình thức tiềm ẩn f (x, y) = 0, hoặc các dạng tham số (x (u), y (u)) đối với một số tham số u.
Các hình thức rõ ràng là rất hiếm khi được sử dụng trong máy tầm nhìn từ một đường cong
trong mặt phẳng xy có thể xoay xung quanh trong một cách mà có thể có nhiều hơn một điểm
trên đường cong cho mỗi giá trị x.
Các hình thức tham số của một đường cong sử dụng hai chức năng, xiu) và y (u), của một
tham số u xác định điểm dọc theo đường cong từ điểm khởi đầu của đường cong tại = (x (u1),
y (u1)) để điểm cuối p2 = (x (u2), y (u2)) - Chiều dài của một đường cong được xác định bởi
chiều dài hồ quang:
(6.1)
Các vector đơn vị tiếp tuyến là

trong đó p (u) = (x (u), y (u)). Độ cong của đường cong là đạo hàm của các tiếp tuyến: n (u) - p
"(u).
Hãy xem xét ba điểm dọc theo đường cong: p (ii + A), p (u), và p («- A). Hãy tưởng tượng một
vòng tròn đi qua ba điểm, trong đó xác định duy nhất một vòng tròn. Trong giới hạn như A ->
0, vòng tròn này là vòng tròn mật tiếp. Các vòng tròn mật tiếp chạm với đường cong tại p («),
và trung tâm của vòng tròn nằm dọc theo dòng chứa bình thường với các đường cong. Độ
cong là nghịch đảo của bán kính của vòng tròn mật tiếp.

6.2 Đường cong kỹ thuật số
Trong phần này, chúng tôi trình bày một tập hợp các thuật toán để tính toán các yếu tố hình
học của đường cong, như chiều dài đường viền, định hướng tiếp tuyến, và độ cong, trong danh
sách các điểm cạnh. Độ dốc và độ cong rất khó để tính chính xác trong lĩnh vực kỹ thuật số, từ
các góc độ giữa các điểm ảnh lân cận được lượng lên đến 45 °.

Ý tưởng cơ bản là để ước tính định hướng tiếp tuyến sử dụng điểm cạnh mà không phải là liền
kề trong danh sách cạnh. Điều này cho phép một tập hợp lớn hơn của thể định hướng tiếp
tuyến.

4


Cho Pj = (xi, Ui) là tọa độ của cạnh tôi trong danh sách cạnh. Fc dốc là (góc) vector hướng
giữa các điểm đó là k cạnh nhau. Bên trái & -slope là hướng từ PTO pi; bên phải là fc dốc là
hướng từ p ^ để pi + fc. Độ cong là sự khác biệt giữa bên trái và bên phải -slopes ^.
Giả sử có được n cạnh điểm (x ±, yi), ..., (xn, yn) trong danh sách cạnh. Chiều dài của một
đường cong kỹ thuật số có thể được xấp xỉ bằng cách thêm chiều dài của các phân đoạn riêng
lẻ giữa các điểm ảnh:
n

/----------------------------------s = V1( x i
~ ^-i)2 + (yi ~ Vi-i) 2 i=2

(6-3)

Một xấp xỉ tốt thu được bằng cách đi qua các danh sách cạnh và thêm 2 dọc theo hai bên và 3
cùng đường chéo, và chia số tiền cuối cùng bằng 2. Khoảng cách giữa các điểm cuối của một
đường viền là
D = yj {yn - yi) 2 + (xn - xi) 2.

(6.4)

6.2.1 Mã Chuỗi
Mã chuỗi là một ký hiệu để ghi danh sách các điểm cạnh dọc theo một đường viền. Các mã
chuỗi xác định hướng của một đường viền ở mỗi cạnh trong danh sách cạnh. Hướng được

lượng tử hóa thành một trong tám hướng, như thể hiện trong hình 6.1. Bắt đầu từ đỉnh đầu tiên
trong danh sách và sẽ chiều kim đồng hồ xung quanh đường viền, hướng đến cạnh tiếp theo
được xác định bằng cách sử dụng một trong các mã chuỗi tám. Hướng là mã chuỗi cho 8-láng
giềng của cạnh. Các mã chuỗi đại diện cho một danh sách cạnh bởi các tọa độ của cạnh đầu
tiên và danh sách các mã chuỗi dẫn đến cạnh tiếp theo. Một đường cong và mã chuỗi của nó
được thể hiện trong hình 6.2.
Các mã chuỗi có một số đặc tính hấp dẫn. Quay của một đối tượng bằng 45 ° có thể dễ dàng
thực hiện. Nếu đối tượng được quay bằng nx 45 °, sau đó các mã cho các đối tượng xoay thu
được bằng cách thêm n mod 8 để mã gốc. Các dẫn xuất của các mã chuỗi, còn được gọi là mã
khác biệt, thu được bằng cách sử dụng khác nhau đầu tiên, là một mô tả ranh giới xoay bất
biến. Một số đặc điểm khác của một khu vực, chẳng hạn như khu vực và góc, có thể được tính
trực tiếp bằng cách sử dụng mã chuỗi. Các giới hạn của đại diện này là
Hình 6.1 Các mã chuỗi đại diện cho các hướng dẫn liên kết giữa điểm cạnh

5


Hình 6.2 Một đường cong và mã chuỗi của nó.
các tập hạn chế các hướng sử dụng để đại diện cho các tiếp tuyến tại một điểm. Sự hạn chế này
có thể được loại bỏ bằng cách sử dụng một trong những đại diện cong trình bày trong các phần
sau. Khi một đường cong đã được trang bị cho các danh sách các cạnh, bất kỳ của các đại
lượng hình học được trình bày tại mục 6.1 có thể được tính toán từ các công thức toán học cho
các đường cong.
6.2.2 Đại diện dốc
Các đại diện dốc của một đường viền, còn được gọi là cốt truyện, giống như một phiên bản
liên tục của mã chuỗi. Chúng tôi muốn đại diện cho một đường viền bằng cách sử dụng hướng
tiếp tuyến tùy ý, chứ không phải là thiết lập giới hạn của đường tiếp tuyến cho phép bởi các
mã chuỗi. Giả sử rằng chúng ta bắt đầu vào đầu của danh sách cạnh và tính toán chiều dài tiếp
xúc và hồ quang bằng cách sử dụng các công thức đã trình bày cho các đường cong kỹ thuật
số. Chúng tôi có thể vẽ các tiếp tuyến so với góc chiều dài để có được một đại diện cho các

đường viền trong không gian. là một sự đại diện của hình dạng của các đường viền. Ví dụ, một
đường viền bao gồm các đoạn thẳng và cung tròn sẽ giống như một chuỗi các đoạn trong vòng
tròn. Đoạn đường thẳng nằm ngang trong cốt truyện tương ứng với đoạn thẳng trong các
đường đồng mức; đoạn thẳng ở hướng khác trong âm mưu Ws tương ứng với cung tròn. Một
số phần của cốt truyện mà không phải là đường thẳng tương ứng với nguyên thủy đường cong
khác.
Các đường viền có thể được chia thành các đoạn thẳng và cung tròn bằng phân đoạn những
6


thành đường thẳng. Phương pháp này đã được sử dụng bởi nhiều nhà nghiên cứu, và có một số
phiên bản của phương pháp này để tách một đường viền vào các phân đoạn.
Một người có thể sử dụng cốt truyện như một mô tả nhỏ gọn của các hình dạng của các đường
đồng mức ban đầu. Trong hình 6.3, ta thấy có một đường viền và cốt truyện của nó. Đối với
một đường viền khép kín, cốt truyện là định kỳ.
6.2.3 độ dốc
Hàm mật độ dốc là biểu đồ của dốc (góc tiếp tuyến) dọc theo một đường viền. Đây có thể là
một mô tả hữu ích cho công nhận. Tương quan hàm mật độ dốc của một đường viền mô hình
với hàm mật độ dốc cho một đường viền được chiết xuất từ một hình ảnh cho phép định hướng
của các đối tượng được xác định. Điều này cũng cung cấp một phương tiện để công nhận đối
tượng

6.3 Đường cong vừa vặn
Phần còn lại của chương này sẽ bao gồm bốn mô hình đường cong và các phương pháp cho
phù hợp các mô hình để cạnh điểm. Các mô hình bao gồm:
• đoạn thẳng
• Thông tư arcs
• phần Conic
• đường splines
Bất kỳ thuật toán phù hợp phải giải quyết hai câu hỏi:

1. Phương pháp nào được sử dụng để phù hợp với những đường cong để các cạnh?
2. Làm thế nào là sự gần gũi của các phù hợp đó?
Phần 6.4 đến 6.7 sẽ bao gồm các kỹ thuật cho các mô hình đường cong phù hợp với các cạnh
với giả định rằng các vị trí cạnh là đủ chính xác các điểm cạnh được chọn có thể được sử dụng
7


để xác định sự phù hợp Mục 6.8 trình bày các phương pháp tiếp mạnh mẽ hơn mà có thể xử lý
các sai sót trong các địa điểm cạnh.
Hãy di là khoảng cách của điểm cạnh tôi từ một dòng.
Có một số các biện pháp về sự tốt lành của sự phù hợp của một đường cong để các điểm cạnh
ứng cử viên. Tất cả của họ phụ thuộc vào các lỗi giữa các đường cong được trang bị và các điểm ứng
cử viên hình thành các đường cong. Một số phương pháp thường được sử dụng làm theo.
Hệ số sai số tuyệt đối tối đa bao sẽ đo nhiêu điểm đi chệch khỏi đường cong trong trường hợp xấu
nhất:
MAE = max | c j? | (6.5)
i
Có nghĩa là lỗi bình phương đưa ra một biện pháp tổng thể của độ lệch của đường cong từ điểm
cạnh:
1n

Số thay đổi dấu hiệu lỗi là một chỉ số tốt của appropri-ateness của đường cong như một mô hình cho
các cạnh trong đường viền.
Tỷ lệ chiều dài đường cong để kết thúc khoảng cách điểm là một biện pháp tốt của sự phức tạp của
những đường cong.
Các lỗi tối đa bình thường cung cấp một biện pháp unitless của lỗi trong phụ thuộc vào chiều dài của
đường cong. Nói cách khác, một số lượng nhất định độ lệch từ một đường cong có thể được bình đẳng
đáng kể, trong một số ứng dụng, như gấp hai lần độ lệch từ một đường cong mà là hai lần như lâu dài.
Nếu mô hình đường cong là một đoạn thẳng, sau đó nó không phải là cần thiết để tính toán chiều dài
hồ quang; D khoảng cách giữa các điểm cuối có thể được sử dụng:

D = \] {yn - yi) 2 + (xn - £ i) 2. (6.8)
Thay đổi dấu hiệu là một dấu hiệu cho thấy rất hữu ích của sự tốt lành của sự phù hợp. Phù hợp với
một danh sách các cạnh điểm với một đường thẳng và kiểm tra các số thay đổi dấu. Một
thay đổi dấu hiệu cho thấy danh sách của các cạnh có thể được mô hình hóa bởi một đoạn thẳng, hai
thay đổi dấu hiệu cho thấy các cạnh nên được mô hình bởi một đường cong bậc hai, ba thay đổi dấu
hiệu cho thấy một đường cong khối, và như vậy. Nhiều dấu hiệu thay đổi cho thấy một sự gia tăng

nhỏ trong sự phức tạp của đường cong sẽ không cải thiện đáng kể phù hợp. A phù hợp có một
mẫu ngẫu nhiên để thay đổi dấu. Chạy sai sót của cùng một dấu chỉ ra một lỗi hệ thống trong
lắp; có thể là do các mô hình đường cong sai. Trong các phần sau, chúng ta sẽ sử dụng các
phương pháp phù hợp đường cong đơn giản để giải thích việc sử dụng các polyline, cung tròn,
đường conic, và các mô hình spline khối. Mục 6.8 sẽ trình bày các phương pháp phù hợp
đường cong mạnh mẽ hơn, sử dụng polylines như ví dụ tiểu học; nhưng, về nguyên tắc, bất kỳ

8


kiểu mẫu trước gửi trong các phần sau đây có thể được sử dụng với bất kỳ của đường cong
phương pháp phù hợp trình bày trong Phần 6.8.
Sự lựa chọn của các đường cong mô hình phù hợp phải được hướng dẫn bởi các ứng dụng.
Việc sử dụng các đoạn đường thẳng (polylines) là thích hợp nếu cảnh bao gồm các đường
thẳng và là điểm khởi đầu cho việc lắp các mô hình khác. Thông tư cung tròn là một đại diện
có ích cho việc ước lượng độ cong, vì các đường cong được tách ra thành các phần với từng
phần theo độ cong không đổi. Cắt hình nón cung cấp một cách thuận tiện để đại diện cho chuỗi
các đoạn thẳng và cung tròn, cũng như vòng cung elip và hyperbol, và rõ ràng đại diện cho các
điểm uốn. Đường Splines là tốt cho mô hình đường cong mượt mà và không ép buộc các ước
tính của các vectơ tiếp tuyến và độ cong là liên tục.

6.4 Đại diện Polyline
Một polyline là một chuỗi các đoạn ghép nối đuôi nhau. Các đại diện polyline cho một đường

viền phù hợp với danh sách cạnh với một chuỗi các đoạn. Polyline nội suy một tập con được
lựa chọn trong những điểm lợi thế trong danh sách cạnh. Các kết thúc của mỗi đoạn thẳng là
điểm cạnh trong danh sách cạnh ban đầu. Mỗi mô hình đoạn đường chạy của các cạnh tiếp
giáp giữa các điểm cuối của nó. Các điểm nơi đoạn đường thẳng được nối được gọi là đỉnh.
Lưu ý rằng polylines những đường cong hai chiều trong mặt phẳng ảnh, như là tất cả các
đường cong được thảo luận trong chương này, và các đỉnh là các điểm trong mặt phẳng ảnh.
Các thuật toán polyline mất như là đầu vào một danh sách có thứ tự các điểm cạnh {{xi, yi),
(x2, y2), • • •, (xn, yn)} - Các tọa độ điểm cạnh có thể được máy tính giải quyết tiêu điểm ảnh
(xem Phần 5.7). Kể từ khi đoạn đường thẳng là phù hợp các cạnh được chọn là đỉnh cần phải
được tính toán một cách chính xác

hình 6.4 Sơ đồ cho thấy khoảng cách vuông góc của một điểm từ một đoạn thẳng. Các giá trị
7 được tính toán bằng cách cắm các tọa độ của điểm vào phương trình cho các đoạn thẳng

9


Công thức cho một đoạn đường đó xấp xỉ một danh sách các điểm cạnh và tham gia các điểm
cạnh đầu tiên và cuối cùng (xi, yi) và (xk, yk) có thể được bắt nguồn bằng việc khẳng định độ
dốc của đường giữa các điểm kết thúc là cùng là độ dốc của đường giữa điểm đầu và một điểm
tùy ý theo hướng:
y-yi = Vk-yi
X — Xi Xk — X\

^

Nhân ra và sắp xếp lại các điều khoản cho các hình thức tiềm ẩn cho một đoạn thẳng, tham số
của các tọa độ của các điểm kết thúc:
x (yi - Vk) + y (xk - x {) + ykx1 - yiXk = 0. (6.10)
Khoảng cách từ bất kỳ điểm nào (x ^ y \) từ dòng là d = r / D, trong đó r được tính bằng cách

cắm các tọa độ của điểm vào phương trình cho các đoạn thẳng,
r = Xi (yi - yk) + yi (xk - xx) + ykx1 - yixk, (6.11)
và D là khoảng cách giữa các điểm kết thúc. (Tham khảo Hình 6.4.) Các dấu hiệu của r có thể
được sử dụng để tính toán số lượng dấu hiệu thay đổi C. Khoảng cách bình thường là d / D.
Các lỗi bình thường tối đa là tuyệt đối s = (6.12)
trong đó d {là khoảng cách giữa các dòng và vị trí của các ¿cạnh thứ trong danh sách cạnh.
Các lỗi tối đa bình thường thường được sử dụng như là thước đo cho sự tốt lành của sự phù
hợp của một đoạn thẳng cho một tập các cạnh. Tất cả những công thức giả định rằng chiếu
vuông góc của một điểm trên một đường thẳng là trong phân khúc dòng; đó là, cả trên đường
dây và giữa các điểm cuối của đoạn thẳng. Đây là trường hợp đối với các tình huống trong
suốt chương này, nhưng trong các trường hợp khác các công thức có thể cần phải được sửa đổi
để tính toán khoảng cách của các điểm từ điểm cuối gần nhất của đoạn thẳng. Có hai phương
pháp để polylines phù hợp: tách từ trên xuống và kết hợp từ dưới lên.
6.4.1 Tách Polyline
Việc chia tách thuật toán đệ quy trên xuống thêm đỉnh, bắt đầu với một đường cong ban đầu.
Hãy xem xét các đường cong thể hiện trong hình 6.5. Các đường cong ban đầu là đoạn đường
giữa các điểm cạnh đầu tiên và cuối cùng, A và B. Các điểm trong danh sách cạnh đó là xa
nhất từ các đường thẳng được tìm thấy. Nếu các lỗi tối đa bình thường là ở trên một ngưỡng
thì một đỉnh được lắp tại các điểm cạnh xa nhất từ các đoạn thẳng, dán nhãn là điểm C trong
hình 6.5. Các thuật toán tách được đệ quy áp dụng cho hai phân đoạn đường mới và danh sách
cạnh. Danh sách cạnh được phân chia thành hai danh sách tương ứng với hai đoạn thẳng. Các
điểm cạnh trong danh sách mà là xa nhất từ mỗi đoạn được tìm thấy, và đỉnh mới được giới
thiệu nếu điểm quá xa đoạn đường thẳng. Các thuật toán tách polyline chấm dứt khi các lỗi tối

10


đa bình thường, đối với tất cả các điểm cạnh dọc theo polyline, là dưới ngưỡng. Thủ tục đệ
quy này là rất hiệu quả. Tách phân khúc cũng được gọi là phân khu đệ quy.
6.4.2 Ghép đoạn

trong NPN như danh sách đã được đi qua. Phân khúc mới được bắt đầu khi các cạnh điểm đi
chệch quá xa đoạn đường. Các cách tiếp cận hợp nhất cũng được gọi là phương pháp tiếp cận
từ dưới lên để polyline phù hợp. Có một số biện pháp có thể được sử dụng để xác định xem
một điểm cạnh quá xa đoạn đường đang được hình thành. Một phương pháp là sử dụng tuần tự
phương nhỏ nhất, cũng thực hiện ít nhất
Hình 6.5 Phương pháp chia nhỏ file cho polylines

hình vuông phù hợp với các đoạn đường đến điểm cạnh và cập nhật các thông số của các đoạn
thẳng tăng dần khi mỗi điểm cạnh mới được xử lý. Các thuật toán phù hợp tính toán dư bình
phương giữa các đoạn thẳng và các điểm cạnh. Khi lỗi vượt quá một ngưỡng, một đỉnh được
giới thiệu và một phân khúc mới được bắt đầu từ điểm cuối của đoạn cuối cùng.

11


Các thuật toán ban nhạc khoan dung sử dụng một phương pháp khác nhau để xác định vị trí
của các đỉnh. Hai đoạn thẳng song song với đường thẳng xấp xỉ điểm cạnh tại một e khoảng
cách từ đoạn đường trung tâm được tính toán. (Xem Hình 6.6). Giá trị của e đại diện cho số
lượng tuyệt đối của độ lệch từ dòng trang bị được dung thứ. Cạnh được thêm vào phân khúc
dòng hiện tại miễn là các cạnh mới là bên trong chiếc nhẫn chịu đựng. Các tham số của đường

thẳng có thể được tính toán lại như các cạnh mới được thêm vào phân vùng. Các đoạn thẳng
Tạo xấp xỉ không

hình 6.6 khoan hình dung cho đoạn đường thẳng phù hợp
không phải vẫn song song với các mặt của các ban nhạc khoan dung. Các đỉnh vào cuối của
phân khúc này là điểm khởi đầu cho các phân đoạn tiếp theo. Cách tiếp cận này thường dẫn
đến quá nhiều phân đoạn. Vị trí và góc độ góc không được ước lượng chính xác từ một đỉnh
không được tạo ra cho đến khi các thuật toán đã được xử lý cạnh tới ranh giới của ban nhạc
bao dung.

6.4.3 Chia và hợp nhất
Các phương pháp từ trên xuống các phân khu đệ quy và phương pháp từ dưới lên về việc sáp
nhập có thể được kết hợp như tách và hợp nhất các thuật toán. Chia nhỏ và phương pháp sáp
nhập chỉ thành công phần nào khi được sử dụng bởi chính họ, nhưng tính chính xác của xấp xỉ
phân khúc dòng vào một danh sách các cạnh có thể được cải thiện bằng cách đan xen hợp nhất
và các hoạt động chia tay. Hình 6.7 cho thấy một ví dụ mà một tách tiếp theo một hợp nhất có
thể sửa chữa một đỉnh nặng đặt.
Ý tưởng cơ bản là để xen vào tách và hợp nhất đèo. Sau khi phân chia đệ quy, cho phép phân
đoạn liền kề sẽ được thay thế bởi một phân khúc duy nhất được các điểm kết thúc đầu tiên và
cuối cùng nếu các phân khúc mới phù hợp với các cạnh với lỗi ít hơn bình thường. Lưu ý rằng
nó là cần thiết để sử dụng bình thường lỗi vì nhiều đoạn đường thẳng sẽ luôn luôn phù hợp với
một danh sách các cạnh với ít lỗi hơn cho một phân khúc dòng đơn. Sau khi sáp nhập phân

12


khúc, phân khúc mới có thể được tách ra ở một thời điểm khác nhau. Ứng dụng thay thế của
tách và hợp nhất tiếp tục cho đến

hình 6.7 Một ước tính góc xấu được sản xuất bởi một cạnh kết hợp từ dưới lên mà bị mất vị trí
góc thật sự có thể được sửa chữa bằng cách tách và hợp nhất đèo mà chia phân đoạn đầu tiên
tại một điểm gần gũi hơn với các góc đúng và sau đó hợp nhất hai phân đoạn thành một đoạn
thẳng duy nhất
6.4.4-làm việc Cùng thuật toán
Làm việc cùng thuật toán xấp xỉ với một đường viền bằng một chuỗi các dòng như sự chia rẽ
và phương pháp mô tả ở trên hợp nhất, nhưng hoạt động trên các danh sách con ngắn của các
cạnh. Các thuật toán bắt đầu ở một đầu của một danh sách các điểm cạnh, lấy một số số cố
định của các cạnh, và phù hợp với một đoạn thẳng giữa các điểm cạnh đầu tiên và cuối cùng.
Nếu phù hợp là xấu, các thuật toán hiện một phân chia tại điểm lỗi tối đa và lặp đi lặp lại với
các phân khúc gần đầu của chạy. Nói cách khác, các thuật toán rơi trở lại cho đến khi nó tìm

thấy một đoạn đường tốt xấp xỉ với một số trình tự ban đầu của các cạnh. Các thuật toán làm
cho các phân đoạn hiện nay phân khúc trước đó, và tiếp tục với các điểm cạnh còn lại. Các
thuật toán cũng kiểm tra xem nếu phân đoạn hiện nay có thể được sáp nhập với các phân đoạn
trước. Thuật toán là giống như một tách và hợp nhất các thuật toán, nhưng nó không bắt đầu
với toàn bộ danh sách các cạnh và không lãng phí thời gian làm rất nhiều việc chia tách. Các
thuật toán bước nhảy cùng, làm việc trên chạy kích thước khiêm tốn của các cạnh. Các thuật
toán được đưa ra như là thuật toán 6.1.
Thuật toán 6.1 làm việc Cùng thuật toán cho nhiều đường khớp nối
1. Bắt đầu với các cạnh k đầu tiên trong danh sách.
13


2. Phù hợp với một đoạn thẳng giữa các cạnh đầu tiên và cuối cùng trong danh sách phụ
chứa.
3. Nếu các lỗi tối đa bình thường là quá lớn, rút ngắn danh mục phụ đến mức sai số tối đa.
Quay trở lại bước 2.
4. Nếu các dòng phù hợp thành công, so sánh sự định hướng của các dòng seg¬ment hiện tại
với các phân khúc dòng trước đó. Nếu các dòng có định hướng tương tự, thay thế cho hai
đoạn thẳng với một phân khúc dòng đơn.
5. Thực hiện các phân khúc dòng hiện tại đoạn đường trước đó và trước cửa sổ của các cạnh
để có k cạnh trong sublist. Quay trở lại bước 2.
Các thuật toán bước nhảy cùng, thúc đẩy các cửa sổ của các cạnh của một k.If liên tục phù hợp
của một đoạn thẳng để các cạnh là không đủ tốt, các thuật toán rơi trở lại điểm của sai số tối
đa. Kể từ khi các thuật toán chỉ xem xét một ngắn hạn của các cạnh, đó là hiệu quả hơn so với
phân khu đệ quy nguyên chất hoặc tách và hợp nhất các thuật toán, mà sẽ bắt đầu với toàn bộ
danh sách các cạnh và lãng phí rất nhiều thời gian chia tách danh sách cạnh vào phần quản lý.

6.5 đường tròn Arcs
Sau một danh sách các cạnh là xấp xỉ bởi các đoạn đường, trình tự phụ của các đoạn đường có
thể được thay thế bởi các cung tròn nếu muốn. Thay thế các đoạn đường bằng cung tròn liên

quan đến việc cung tròn phù hợp thông qua các điểm kết thúc của hai hoặc nhiều đoạn thẳng.
Nói cách khác, phù hợp cung tròn được thực hiện trên đỉnh của polyline. Đại diện cho các
đường viền như là một chuỗi các đoạn và cung tròn phá vỡ các đường viền thành các phần với
từng phần theo độ cong không đổi. Nhiều thuật toán phân tích hình ảnh sử dụng thông tin
cong.
Cũng như chúng ta có nguồn gốc công thức ngầm cho đoạn đường giữa hai điểm, chúng ta cần
phải lấy được công thức tiềm ẩn cho một vòng tròn qua ba điểm. Phương trình ngầm cho một
vòng tròn với bán kính trung tâm rand (x0,Y0) là
(x – x0) 2 + (y – y0) 2 = r2 .

(6.13)

Hãy xem xét ba điểm p1 = (x1,y1), p2 = (x2, y2), và p3 = (x3, y3) .chuyển đổi nguồn gốc của các
hệ thống phối hợp để chỉ p1. Trong hệ thống coodinate mới,
x '= x – x 1
y '= y – y 1

(6-14)
(6-15)

và phương trình cho các vòng tròn là
(x’ – x’0)2+ (y’ + y’0)2 = r2 (6.16)
Thay tọa độ trong x '~ y' cho điểm p1, p2, và p3 in phương trình ngầm cho một vòng tròn:
14


x0’2 + y0’2 - r2 = 0
(6.17)
’ ’
2

2
’ 2 ’
2
2
x’2 - 2x 2x 0+x’0 + y’2 - 2y 2 y 0 + y’0 - r = 0
(6.18)
’ ’
2
2
’ 2 ’
2
2
x’3 - 2x 3x 0+x’0 + y’3 - 2y 3 y 0 + y’0 - r = 0
(6.19)
Điều này mang lại ba phương trình phi tuyến cho ba ẩn số x’0; y’0, và r. Trừ các phương trình
đầu tiên từ các phương trình thứ hai và thứ ba:
2x'2x'0 + 2y'2y'0 = x’22 + y’22 (6.20)
2x’3x’0+ 2y’3y’0 = x’32 + y’32 (6.21)
Điều này mang lại hai phương trình tuyến tính trong hai ẩn x'0 và y'0) Nào là tọa độ của các
trung tâm của vòng tròn trong khoảng cách x'-y'. Thêm (x’, y’) vào (x'0, y'0) để có được trung
tâm của vòng tròn trong các hệ tọa độ ban đầu. Tính bán kính của vòng tròn từ r2 = X’02 + Y’02.
Để tính toán các lỗi trong việc lắp đặt một cung tròn, xác định khoảng cách của điểm Q từ
vòng tròn như khoảng cách của Q từ vòng tròn dọc theo một đường đi qua trung tâm của vòng
tròn. Hãy bán kính của vòng tròn được r .tính khoảng cách q với các tọa độ (xi, yi) từ điểm Q
đến trung tâm (x0, y0) của các vòng tròn:
(6.22)
Khoảng cách từ điểm Q để các cung tròn là
d=q–r

(6.23)


Bây giờ chúng ta có một công thức cho lắp một cung tròn đến ba điểm, chúng ta cần một
phương pháp để đánh giá sự tốt lành của sự phù hợp vì vậy chúng tôi có thể xác định có hay
không các cung tròn là một xấp xỉ tốt hơn để các cạnh hơn so với đoạn đường thẳng. Nếu tỷ lệ
chiều dài của đường viền để khoảng cách giữa các điểm kết thúc đầu tiên và cuối cùng là hơn
một ngưỡng, sau đó nó có thể là có thể thay thế các đoạn thẳng với một cung tròn. Các cung
tròn là phù hợp giữa các điểm kết thúc đầu tiên và cuối cùng và một điểm khác. Có một số
phương pháp để lắp một cung tròn với một chuỗi các polylines, tùy thuộc vào cách trung điểm
được chọn:
1. Sử dụng các đỉnh polyline đó là xa nhất từ đường nối các điểm kết thúc đầu tiên và cuối
cùng.
2. Sử dụng các điểm cạnh đó là xa nhất từ đường nối các điểm kết thúc đầu tiên và cuối cùng.
3. Sử dụng các đỉnh polyline mà là ở giữa của dãy các đỉnh giữa các điểm kết thúc đầu tiên và
cuối cùng.
4. Sử dụng các điểm cạnh đó là ở giữa của danh sách các cạnh giữa các điểm kết thúc đầu tiên
và cuối cùng.
15


Tính toán khoảng cách ký kết giữa tất cả các điểm cạnh và cung tròn. Tính toán sai số tuyệt
đối tối đa và số lượng thay đổi dấu. Nếu các lỗi tối đa bình thường là dưới một ngưỡng và số
lượng thay đổi dấu hiệu là lớn, sau đó chấp nhận cung tròn; nếu không, giữ xấp xỉ polyline.
Các thuật toán thay thế cho đoạn thẳng với cung tròn được vạch ra trong thuật toán 6.2.
Thuật toán 6.2 Thay thế dòng phân đoạn theo đường tròn Arcs
1. Khởi tạo các cửa sổ của đỉnh để ba điểm kết thúc của hai đoạn đường đầu tiên trong polyline.
2. Tính tỉ lệ chiều dài của một phần của đường viền tương ứng với hai đoạn thẳng với khoảng cách
giữa các điểm kết thúc. Nếu tỷ lệ này là nhỏ, sau đó rời khỏi phân khúc dòng đầu tiên không thay đổi,
thúc đẩy
3. Phù hợp với một vòng tròn qua ba đỉnh
4.Tính sai số tối đa bình thường và số thay đổi dấu.

5. Nếu các lỗi tối đa bình thường là quá lớn hoặc số lượng thay đổi dấu hiệu là quá nhỏ, sau đó rời
khỏi phân khúc dòng đầu tiên không thay đổi, quảng cáo cửa sổ các đỉnh, và quay lại bước 2.
6. Nếu phù hợp với vòng tròn thành công, sau đó cố gắng để bao gồm các đoạn đường tiếp theo trong
vòng cung tròn. Lặp lại bước này cho đến khi có phân đoạn đường hơn có thể được gộp vào cung tròn
này.
7. Trước cửa sổ để ba đỉnh polyline tiếp theo sau khi kết thúc của cung tròn và quay lại bước 2.

Sau khi chạy Algorithm 6.2 trên polyline, đường viền sẽ được đại diện bởi một phẫn nộ chuỗi
các đoạn và cung tròn. Nó có thể là bất tiện vì có hai nguyên thủy đường cong khác nhau trong
các đại diện. Trong phần tiếp theo, chúng tôi sẽ trình bày phần hình nón, cho phép phân khúc
dòng, vòng cung ,vòng tròn, và nguyên thủy khác để cùng tồn tại trong cùng một đại diện. Cắt
hình nón cũng cung cấp sự chuyển trơn tru giữa các phần, nếu muốn, cũng như các đại diện rõ
ràng của các góc.

6.6 Phần Conic
Phần này mô tả làm thế nào để gần đúng danh sách các điểm cạnh với mặt cắt hình nón. Như
với cung tròn, phương pháp này giả định rằng các điểm cạnh đầu tiên được xấp xỉ bởi một
polyline và thay thế trình tự phụ các đoạn đường bằng các đường conic. Các tiềm ẩn (đại số)
dưới dạng một hình nón là:
f(x, y) = ax2+ 2hxy + by2 + 2ex + 2gy + c = 0.

(6.24)

Có ba loại cắt hình nón: hyperbolas, parabol và elip. Vòng kết nối là một trường hợp đặc biệt
của elip. Hình học, cắt hình nón được xác định bởi giao nhau một hình nón với một chiếc máy
bay như thể hiện trong hình 6.8.

16



Cắt hình nón có thể phù hợp giữa ba đỉnh của polyline xấp xỉ thông đến một đường viền. Các
địa điểm mà cắt hình nón được tham gia được gọi là hải lý. Splines Conic là một chuỗi các mặt
cắt hình nón được ghép cuối để

Hình 6.8: Phần Conic được xác định bởi giao nhau một hình nón với một mặt phẳng.
kết thúc, với tiếp tuyến bằng nhau ở hải lý để cung cấp một quá trình chuyển đổi trơn tru ở
giữa khu vực lân cận của đường cong. Hãy để các đỉnh polyline là Vi. Xấp xỉ nón được thể
hiện trong hình 6.9.
Mỗi đường conic trong một spline nón được xác định bởi hai điểm kết thúc, hai tiếp tuyến, và
một trong những điểm bổ sung. Các nút thắt Ki có thể được đặt giữa các đỉnh của polyline:

nơi mà Vi nằm giữa 0 và 1. Các tiếp tuyến được định nghĩa bởi các tam giác với đỉnh Vi, Vi+1,
và Vi+2. Các điểm nữa là
như thể hiện trong hình 6.10.
Có một số trường hợp đặc biệt của các đường conic có thể được xử lý một cách thống nhất
theo đại diện này. Nếu Vi +1 = 0, sau đó ith phần thứ của spline nón là đoạn đường từ Ki đến
Vi+1. Nếu Vi = 1 và Vi+1 = 0 và Ki và Ki+1, và Vi+1 sụp đổ đến các điểm giống nhau và có một
góc trong chuỗi các mặt cắt hình nón. Các tính chất này đặc biệt cho phép các đoạn đường và
góc để được đại diện một cách rõ ràng trong một spline nón, mà không cần đến nguyên thủy
khác nhau hoặc cờ đặc biệt.
Các thuật toán trình bày ở đây để tính toán splines nón sử dụng hình thức hướng dẫn của một
đường conic, đại diện cho một đường conic bằng ba dòng

17


hình 6.9 Cắt hình nón là gần đúng định nghĩa giữa ba điểm

hình 6.10: Một đường conic được xác định bởi hai điểm kết thúc và tiếp tuyến từ ba đỉnh của
xấp xỉ polyline, cộng thêm một điểm bổ sung.


18


hình 6.11 Các hình thức hướng dẫn cho một hình nón.
bị ràng buộc các conic. (Xem hình 6.11). Các phương trình của một đường thẳng là
ao + a \ x + a2y = 0.

(6.27)

Hãy để các đỉnh đầu tiên và cuối cùng trong một polyline được A và B, và để cho điểm C có
thể có một đỉnh trung gian trong polyline. Các đỉnh đầu tiên và cuối cùng được tham gia bởi
các hợp âm AB.The hình thức hướng dẫn của hình nón là gia đình của các đường conic với
các điểm cuối tại aand băng tiếp tuyến ACand BCdefined bởi phương trình
(a0 + a 1x + a2y) (b0 + b1x + b2y) = p (u0 + u1x + u2y)2,

(6.28)

khi
a0 + a \ x + a2y = 0
là những dòng có chứa các đoạn thẳng AC,

(6.29)

b0 + b1x + b2y = 0
là những dòng có chứa các dòng phân khúc BC, và

(6.30)

u 0 + u1 x + u2 y = 0


(6.31)

là những dòng có chứa các hợp âm AB.The gia đình cắt hình nón được phân chia bởi p.
Các thuật toán cho việc lắp đặt một đường conic vào một danh sách các điểm cạnh bắt đầu với
một polyline và phân loại các đỉnh như góc, đỉnh mềm, hoặc hải lý. Đỉnh mềm có góc gần
180°, và các đoạn đường thẳng liền kề gần cộng tuyến và có thể được thay thế bằng một
đường conic. Một chuỗi các đỉnh mềm tương ứng với một chuỗi các đoạn với dần dần thay đổi
sự định hướng rằng nhiều khả năng được trang bị để cạnh điểm lấy mẫu dọc theo một đường
cong trơn tru. Góc có góc đỉnh trên 180 ° + T1 hoặc dưới 180 ° - T1. trong đó T1 là một ngưỡng,
và sẽ không phải là một phần của hình nón. Hải lý được đặt dọc theo một đoạn thẳng có đỉnh
mềm ở hai đầu được đặt nghiêng theo hướng ngược nhau. Một đường conic không thể có một
uốn, vì vậy hai cắt hình nón phải được tham gia vào các nút. Các vị trí của các nút dọc theo
đoạn thẳng được xác định bởi những góc tương đối của các đỉnh mềm ở hai đầu của đoạn
thẳng. Hãy để các góc của hai đỉnh mềm Vi và Vi + 1 với Ai và Ai + 1 tương ứng. Nếu Ai = Ai + 1,
sau đó các nút được đặt nằm giữa các đỉnh, có nghĩa là v = 1/2 trong phương trình 6.25. Nếu
góc là không giống nhau, sau đó các vị trí nút nên được thiên vị đi từ đỉnh với góc lớn hơn, kể
từ khi hình nón có thể không uốn cong ra khỏi đoạn đường đủ nhanh để theo góc. Các giá trị
cho v trong phương trình 6.25 có thể được thiết lập bằng cách sử dụng công thức
(6.32)

19


Mỗi chuỗi các đoạn tham gia của đỉnh mềm được thay thế bởi một hướng dẫn conic qua đỉnh
đầu tiên và cuối cùng (hay hải lý). Các tiếp tuyến được xác định bởi sự định hướng của các
phân khúc dòng đầu tiên và cuối cùng. Các tiếp tuyến và điểm kết thúc xác định bốn trong số
năm bậc tự do cho conic. Cônic được quy định đầy đủ bằng cách để nó đi qua các đỉnh mềm ở
giữa của dãy.


6,7 đường cong Spline
Spline hạn đề cập đến một chức năng đại diện sử dụng đa thức từng phần theo. Splines xảy ra
trong nhiều ứng dụng. Trong phân tích dữ liệu, splines được sử dụng để phù hợp với một tập
hợp các điểm dữ liệu khi không có mô hình chức năng có sẵn [245]. Trong đồ họa máy tính và
CAD, splines được sử dụng để đại diện cho đường cong dạng tự do. Trong thị giác máy,
splines cung cấp một biểu mục đích chung cho các đường cong khi không có mô hình đơn
giản là đủ.
Một spline có thể được làm từ bất kỳ lớp học của các chức năng ghép nối đuôi nhau. Các hình
thức phổ biến nhất của spline là spline khối, mà là một chuỗi các đa thức từng phần theo khối.
Cơ quan đại diện cong trình bày trong các phần trước, chẳng hạn như trình tự của đoạn thẳng,
cung tròn, và cắt hình nón, là những ví dụ khác của spline. Splines khối cho phép các đường
cong phức tạp hơn để được đại diện sử dụng các đoạn spline ít. Splines khối được sử dụng
rộng rãi trong các chương trình vẽ máy tính cho đường cong dạng tự do và cho đại diện cho
nhân vật vạch ra trong các phông chữ. Kể từ splines khối được sử dụng rất rộng rãi, nó có thể
là cần thiết cho một chương trình máy tầm nhìn để phù hợp với mô hình đường cong thành
một danh sách cạnh. Từ giao diện tương tác đồ họa cho các thao tác đường cong spline khối
cũng được biết đến, một đường viền đại diện là một spline khối có thể được sửa đổi bằng tay
bởi người sử dụng nếu cần thiết. Đây là một xem xét rất quan trọng, vì kết quả của việc lắp đặt
một đường cong với các cạnh có thể không bao giờ được hoàn hảo.
Một điểm cần làm rõ là sự khác biệt giữa hình học và tương đương para¬metric. Hai đường
cong hình học tương đương nếu chúng là những đường cùng một tập hợp điểm. Nói cách khác,
hai đường cong hình học là tương đương nếu chúng tương ứng với các hình dạng tương tự
(hoặc thiết lập các điểm) trong không gian. Hai đường cong parametrically tương đương nếu
phương trình của họ là giống hệt nhau. Nói cách khác, hai đường cong là parametrically tương
đương nếu đại diện của họ sử dụng cùng một công thức với các thông số tương tự. Tương
đương tham số là mạnh hơn tương đương hình học.
Hai đường cong có thể được hình học tương đương, nhưng có đại diện tham số khác nhau.
Đây là một khái niệm quan trọng cho đường cong phù hợp trong thị giác máy. Một hệ thống
thị giác máy có thể sản xuất ra một đại diện dựa trên splines khối đó là rất gần (hình học) để
các đại diện thực sự của một ranh giới đối tượng, nhưng các đại diện có thể không được ở tất

cả tương tự như trong một ý nghĩa tham số. Trong các ứng dụng như nhận dạng đối tượng
20


hoặc so sánh những hình ảnh của một bộ phận công nghiệp với mô hình của nó, nó không phải
là có thể so sánh các hình thức tham số của đường cong spline khối. Việc so sánh phải căn cứ
vào tương đương hình học.
Splines khối có đủ bậc tự do để cho phép các định hướng của các mảnh vỡ bờ để được sử dụng
trong xấp xỉ. Nhớ lại rằng hầu hết các thuật toán khám phá các cạnh có thể cung cấp các ước
tính về định hướng cạnh (góc dốc) cũng như các vị trí của cạnh. Chỉ có các vị trí của các cạnh
đã được sử dụng trong các thuật toán cho các phân đoạn lắp đường dây, cung tròn, và cắt hình
nón. Với splines khối, chúng ta có thể giới thiệu một ví dụ được sử dụng khám phá thông tin
được sản xuất bởi một máy dò cạnh.
Các phương trình cho một đường cong khối trong mặt phẳng là
p (u) = (x (u), y (u)) = a0 + a ± u + a2u2 + a3u3,

(6.33)

nơi mà các hệ số a0, a1, a2, a3 và hai phần tử vector (điểm trong mặt phẳng ảnh) và các tham số
nằm trong khoảng [0,1]. Các đường cong khối bắt đầu tại điểm p (0) = (x(0), y (0)) và kết thúc
tại điểm p (1) = (x (1), y (1)). Các khối spline là một chuỗi các đường cong khối p1 (u), p2 (u),
…. pn (u), được xác định trong khoảng nguyên [0,1], [1, 2], ..., [n - 1, n] và cùng tham gia tại
các điểm kết thúc để Pj (i) = pi + 1 (i). Mỗi của các đường cong khối vào spline được gọi là
một phân đoạn spline, và các điểm cạnh nơi mà các phân đoạn được tham gia được gọi là hải
lý.
Như với các đường cong phù hợp thuật toán được trình bày trong các phần trước, thứ tự các
điểm cạnh được phân chia thành trình tự phụ và một phân đoạn spline là phù hợp với từng dãy.
Mỗi đoạn đường cong khối vào spline đòi hỏi tám thông số. Các vị trí của các điểm cạnh đầu
tiên và cuối cùng trong dãy cung cấp bốn chế. Thứ tự đầu tiên liên tục (vectơ tiếp tuyến bằng
nhau) tại các nút thắt cung cấp hai ràng buộc hơn. Định hướng của các cạnh ở hải lý chỉ cung

cấp một ràng buộc mới về từng đoạn, kể từ mép được chia sẻ bởi các đoạn liền kề. Thứ hai-thứ
tự liên tục (độ cong tương đương) tại các nút thắt sẽ cung cấp hai chế hơn, nhưng sau đó sẽ có
quá nhiều phương trình cho tám thông số của mỗi phân đoạn spline khối.
Điều quan trọng là các đoạn spline để được gia nhập tốt ở các hải lý, và điều này đạt được
trong đồ họa máy tính bằng cách yêu cầu thứ hai để liên tục. Yêu cầu thứ hai-thứ tự liên tục sẽ
qua trở ngại của mỗi đoạn spline, kể từ khi các phân đoạn đã được hạn chế đi qua các cạnh
được lựa chọn với sự định hướng (góc tiếp tuyến) bị hạn chế bởi sự định hướng của cạnh;
nhưng một trong những hạn chế bổ sung có thể được cung cấp bằng cách giảm thiểu độ lớn
của sự gián đoạn thứ hai-trật tự tại các nút. Nói cách khác, giảm thiểu sự khác biệt về độ cong
tại các nút thắt.
Đối với toàn bộ đường cong spline khối, giảm thiểu tổng các bình phương độ lớn của sự khác
biệt trong các dẫn xuất thứ hai tại 1 điểm n-:
21


(6.34)

nơi sự khác biệt trong các dẫn xuất thứ hai của hai đoạn spline tại nút chung của họ là

Biến ti là vector tiếp tuyến tại nút i. Các vector tiếp tuyến có một định hướng ti cho bởi định
hướng cạnh (góc gradient) và ký kết biên độ γi là không rõ:
(6,37)
Nói cách khác, định hướng của một cạnh tại nút được mô phỏng như một vector đơn vị tiếp
tuyến, nhưng các spline khối đòi hỏi một tiếp tuyến với dấu hiệu và độ lớn để chỉ ra từ đó chỉ
đạo các đường cong nên đi qua các nút và ở tốc. Các thuật toán giải quyết một hệ phương trình
tuyến tính cho các n đã biết γi đã cung cấp các thông tin còn thiếu để xây dựng các đoạn spline
khối giữa hai điểm.
Thuật toán này không có bất kỳ thông số bổ sung hoặc ngưỡng, nhưng, như với các thuật toán
cho polylines lắp, cung tròn và các đường conic được trình bày trong các phần trước, các hải
lý phải được chọn từ danh sách cạnh. Các địa điểm nút có thể được xác định bằng cách sử

dụng bất kỳ của các thuật toán polyline mô tả ở trên để tính toán một xấp xỉ polyline để các
đường viền. Các đỉnh polyline có thể được sử dụng như là các vị trí nút. Số lượng và sự sắp
đặt của hải lý có thể được điều chỉnh để cải thiện sự phù hợp của các spline khối cho toàn bộ
các điểm cạnh.
Các thuật toán phù hợp spline khối là rất hiệu quả, kể từ khi giải pháp duy nhất đòi hỏi phải
giải quyết một hệ thống nhỏ của phương trình tuyến tính cho các dấu hiệu tiếp tuyến và độ lớn.
Có rất nhiều giao diện đồ họa tương tác cho phép người dùng dễ dàng điều chỉnh đường cong
spline khối, nếu cần thiết.

6.8 Đường cong xấp xỉ
Các đường cong phương pháp phù hợp được mô tả trong các phần trước nội suy đường cong
thông qua một tập hợp con của các cạnh. Độ chính xác cao hơn có thể thu được bằng cách tính
toán một xấp xỉ mà không bị buộc phải đi qua đặc biệt
Phần này trình bày phương pháp cho xấp xỉ một đường cong. Có nhiều cách để tồn tại đường
cong gần đúng, tùy thuộc vào độ tin cậy mà điểm cuối có thể được nhóm lại thành các đường
nét. Nếu nó là chắc chắn rằng tất cả các điểm cạnh liên kết thành một đường viền thật sự thuộc
về các đường viền, sau đó tổng bình phương nhỏ nhất hồi quy có thể được sử dụng để phù hợp
22


với một đường cong để các điểm cạnh. Nếu một số lỗi nhóm là hiện nay, phương pháp hồi quy
sau đó mạnh mẽ có thể được sử dụng để tính xấp xỉ đường cong. Cuối cùng, nếu nhóm của các
cạnh vào đường nét là rất không đáng tin cậy, hoặc nếu các cạnh được để rải rác thấy việc
nhóm không thể được thực hiện dễ dàng cạnh liên kết hoặc sau các phương pháp thảo luận
trước đó, sau đó kỹ thuật phân tích cụm phải được sử dụng để thực hiện nhóm và đường cong
lắp đồng thời. Một ví dụ tuyệt vời của một thuật toán cho nhóm và các điểm cạnh rải rác phù
hợp là các Hough biến đổi. Tất cả những phương pháp này sẽ được trình bày trong các phần
sau.
Các phương pháp để phân đoạn lắp đường dây, cung tròn, cắt hình nón, và splines khối để
cạnh điểm được trình bày trong mục 6.4 đến 6.7 là vấn đề hồi quy tầm thường phù hợp với

đoạn đường cong giữa các điểm cuối. Những thuật toán giả định rằng các vị trí cạnh có thể
được tính toán chính xác, có thể sử dụng phương pháp tiêu điểm ảnh Điểm cạnh ở giữa các
điểm kết thúc không được sử dụng trong hồi quy. Sự chính xác của xấp xỉ đường cong được
xác định bởi tính chính xác của các vị trí của các điểm cạnh chọn là điểm phân khúc. Các
phương pháp trình bày trong phần này sẽ sử dụng tất cả các điểm cạnh để tính xấp xỉ tốt nhất
của đường cong để các điểm cạnh.
Đường cong chung vấn đề phù hợp là một vấn đề hồi quy với các đường cong mô phỏng theo
các phương trình ngầm
f (x, y; a1, a2, ..., ap) = 0

(6.38)

với các thông số p. Các vấn đề ước lượng đường cong là để phù hợp với mô hình đường cong
thành một tập hợp các điểm cạnh {(x1, y1), (x2, y2), … , (xn, yn)}.
Trong trường hợp không tiếng ồn, người ta có thể sử dụng quan sát p để xây dựng phương
trình p cho p thông số đường cong không rõ. Thật không may, trong hầu hết các ứng dụng
phương pháp tiếp cận trực tiếp này là không phù hợp do tiếng ồn. Ứng dụng thực tế thường
yêu cầu ước tính tốt nhất của các giá trị tham số sử dụng tất cả các thông tin trong danh sách
cạnh.
Phần tiếp theo sẽ bao gồm hồi quy bình phương nhỏ nhất khi nó được sử dụng cho phù hợp
đường cong trong thị giác máy. Bình phương nhỏ nhất là phương pháp thích hợp khi các lỗi
được phát hành bình thường. Mục 6.8.3 sẽ trình bày phương pháp mạnh mẽ cho phù hợp
đường cong đó là hữu ích khi một số trong những điểm cạnh đã không chính xác liên kết thành
các đường viền. Những điểm không đúng chỉ định này được gọi là giá trị ngoại lai.
6.8.1 Tổng Hồi Quy
Hồi quy tuyến tính cổ điển giảm thiểu sự khác biệt giữa một điểm dữ liệu và các mô hình trong
chỉ có một kích thước, kích thước của biến phụ thuộc. Ví dụ, một mô hình chức năng của biểu
mẫu

23



y = f (x, a 1, ..., ap)

(6.39)

liên quan đến sự biến y phụ thuộc vào biến độc lập x, với p thông số mô hình ai qua ap, giả
định rằng không có sai sót trong các biến độc lập x. Trong tầm nhìn của máy, lỗi ở tọa độ x và
y vị trí nào cũng đều có khả năng và mô hình đường cong có thể là một đường thẳng đứng,
cho Chẳng hạn, mà không thể được biểu diễn dưới dạng chức năng. Trong thị giác máy, đường
dây và các mô hình đường cong khác được trang bị với các cạnh bằng tổng số hồi quy, trong
đó giảm thiểu tổng bình phương của khoảng cách vuông góc của các điểm dữ liệu từ các mô
hình hồi quy. Ưu điểm của kỹ thuật này là nó bù đắp cho lỗi trong cả hai hướng x và y. Tổng
số hồi quy đã thực sự đã được trình bày ở chương 2, nơi nó được sử dụng để lấy được các
phương trình để xác định các định hướng của một vệt mặc dù tổng số hồi quy dài đã không
được sử dụng vào thời điểm đó.
Để tránh vấn đề khi dây thẳng đứng, đại diện cho phương trình cho một đường bằng cách sử
dụng tọa độ cực:
(6.40)
Giảm thiểu tổng các khoảng cách vuông góc với bình phương của điểm (Xi, Yi) từ dòng:
(6.41)

Các giải pháp cho toàn bộ vấn đề hồi quy là
(6.42)
với

Định hướng của đường hồi quy tổng là 0, do
(6.45)
với


24


và

Tổng số hồi quy sử dụng một phương tối thiểu mức lỗi đó là tối ưu nếu lỗi là từ một phân bố
bình thường, nhưng không phải là phù hợp nếu có những giá trị ngoại lai hiện nay trong các dữ
liệu. Trong trường hợp lắp một mô hình đường cong để cạnh dữ liệu, giá trị ngoại lai sẽ xảy ra
nếu các thủ tục cạnh liên kết hợp một hoặc nhiều cạnh từ đường nét khác vào danh sách cạnh
cho một đường viền. có thể xảy ra ngay cả khi các cạnh nối thủ tục thực hiện một cách hoàn
hảo. Ví dụ, hãy xem xét một danh sách các cạnh từ hai cạnh kề của một hình chữ nhật. Góc
phải được xác định để phân khúc các cạnh vào hai bên trước khi lắp đặt một dây chuyền đến
các cạnh. Nếu các điểm góc không được xác định một cách chính xác, một số các cạnh có thể
được giao cho phía sai, và các cạnh được giá trị ngoại lai.
Nói chung, sai sót trong phân loại giới thiệu sai lệch vấn đề hồi quy không được phân bố bình
thường. Trong một trường hợp như vậy, các lỗi có thể được mô hình hóa bởi một phân phối
hỗn hợp kết hợp một phân phối để mô hình hóa các lỗi thông thường với một phân bố rộng
đuôi để mô hình hóa các giá trị ngoại lai do phân loại không hoàn hảo.
6.8.2 ước lượng góc
Phương pháp tốt nhất để ước lượng góc là sử dụng một trong những phương pháp cho việc lắp
đặt một dây chuyền để cạnh điểm và sau đó tính toán các giao điểm của các đường. Phương
pháp này bù đắp cho những lỗi được giới thiệu bởi các nhà khai thác phát hiện cạnh mà làm
tròn các góc và chính xác hơn bằng cách sử dụng một máy dò góc mà chỉ sử dụng thông tin
địa phương.
Với các phương trình ngầm cho hai dòng,
a1x + b1y + c1 = 0

(6.50)

a2x + b2y + c2 = 0,


(6.51)

vị trí của các giao điểm là

Nếu a1b2 - a2b1 là gần bằng không, sau đó các dòng gần như song song và không thể giao nhau.

25