Download miễn phí Đồ án Xử lý đường cong tự động



MỤC LỤC
MỤC LỤC 1
LỜI CẢM ƠN 2
MỞ ĐẦU 3
Chương 1: Tổng quan về xử lý ảnh 4
1.1.Khái niệm xử lý ảnh 4
1.2.Tổng quan về một hệ thống xử lý ảnh 4
1.3.Các vấn đề cơ bản của xử lý ảnh 4
1.4.Ứng dụng của xử lý ảnh 4
Chương 2. Các thuật toán đơn giản hoá 5
2.1. Đặt vấn đề 5
2.2 Giải quyết vấn đề 5
2.3.Các thuật toán đơn giản hóa đường cong 6
2.3.1.Thuật toán thu gọn đỉnh 6
2.3.2.Thuật toán khoảng cách trực giao 7
2.3.3.Thuật toán Douglas-Peucker 9
2.3.4 Thuật toán Band Width 9
2.3.5 Thuật toán Angularity Tolerance 11
2.4 Nhận xét các thuật toán đơn giản hoá đường cong: 12
KẾT LUẬN: KẾT QUẢ CỦA KHÓA LUẬN 14
PHỤ LỤC 15
TÀI LIỆU THAM KHẢO 17
 
 


http://s1.liketly.com/flash/edoc/web-viewer.html?file=jh2i1fkjb33wa7b577g9lou48iyvfkz6-demo-2016-01-14-do_an_xu_ly_duong_cong_tu_dong_cT1oq9pYCU.png /tai-lieu/do-an-xu-ly-duong-cong-tu-dong-87376/


Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.

Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn


Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

MỤC LỤC
LỜI CẢM ƠN
Em xin chân thành Thank toàn thể các thầy cô giáo trong khoa Công nghệ, Đại học Dân lập Hải Phòng đã hết lòng dạy dỗ, chỉ bảo, tạo điều kiện tốt cho em trong suốt quá trình học tập cũng như trong thời gian thực hiện khoá luận tốt nghiệp này.
Đặc biệt, em gửi lời Thank chân thành và sâu sắc tới PGS TS Ngô Quốc Tạo, phòng “Nhận dạng và Công nghệ tri thức”, Viện Công Nghệ Thông Tin, Viện Khoa học và Công nghệ Việt Nam, người đã trực tiếp quan tâm, tận tình hướng dẫn, giúp đỡ và tạo điều kiện hết sức thuận lợi cho em trong quá trình thực hiện khoá luận.
Tuy có nhiều cố gắng trong quá trình học tập cũng như trong thời gian thực tập nhưng không thể tránh khỏi những thiếu sót, em rất mong được sự góp ý quý báu của tất cả các thầy cô giáo cũng như tất cả các bạn để kết quả của em được hoàn thiện hơn.
Em xin chân thành cảm ơn!
Hải Phòng, ngày 27 tháng 03 năm 2008
Sinh viên
Nguyễn Thị Hạnh
MỞ ĐẦU
Với tốc độ phát triển như vũ bão, công nghệ thông tin đã trở thành một bộ phận không thể thiếu trong hầu hết các lĩnh vực của đời sống xã hội. Việc tự động hoá thông qua quá trình xử lý của máy tính đã giúp con người giảm bớt được khối lượng công việc, hoàn thành công việc một cách nhanh chóng, chính xác và hiệu quả hơn rất nhiều so với các phương pháp truyền thống. Trong công nghệ thông tin, xử lý ảnh chiếm một vị trí rất quan trọng, bởi các ứng dụng đa dạng và phong phú của nó trong nhiều lĩnh vực khoa học như: y học, thiên văn học, truyền hình, nhận dạng công nhiệp, lâm nghiệp, thuỷ văn, thăm dò tài nguyên, quân sự, các hệ thống thông tin địa lý, các ứng dụng văn phòng, v.v...
Do tầm quan trọng của bài toán đơn giản hóa đường cong, đã có rất nhiều công trình nghiên cứu và một loạt các toán xấp xỉ đường cong đã ra đời. Trong đó, nổi tiếng nhất là thuật toán Douglas-Peucker, được sử dụng rộng rãi trong các chương trình xử lý đồ hoạ, vẽ kĩ thuật và xử lý bản đồ tự động, ...
Khóa luận nghiên cứu các phương pháp đơn giản hóa đường cong, tổng hợp ưu điểm của các thuật toán. Chương trình cho phép tự động phát hiện các đường cong trong ảnh, sau đó đơn giản hoá để thu được đường cong xấp xỉ với số điểm ít hơn mà vẫn biểu diễn tốt đối tượng ban đầu.
Chương 1: Tổng quan về xử lý ảnh
1.1.Khái niệm xử lý ảnh
Xử lý ảnh là dùng các kỹ thuật xử lý để biến đổi một ảnh sang ảnh mới theo mục đích của người sử dụng. Nó bao gồm các phương pháp và kỹ thuật để biến đổi, để truyền tải hay mã hoá các ảnh tự nhiên.
1.2.Tổng quan về một hệ thống xử lý ảnh
Một hệ thống xử lý ảnh hoàn chỉnh bao gồm: thu nhận ảnh, tiền xử lý, nhận dạng, phân tích ảnh, ra quyết định.
1.3.Các vấn đề cơ bản của xử lý ảnh
Các vấn đề cơ bản của xử lý ảnh gồm: biểu diễn ảnh, tăng cường ảnh – khôi phục ảnh, biến đổi ảnh, phân tích ảnh, nhận dạng ảnh, nén ảnh.
1.4.Ứng dụng của xử lý ảnh
Xử lý ảnh số có rất nhiều ứng dụng như làm nổi các ảnh trong y học, khôi phục lại ảnh do tác động của khí quyển trong thiên văn học, tăng cường độ phân giải của ảnh truyền hình mà không cần thay đổi cấu trúc bên trong của hệ thống chuyển tải, nén ảnh trong khi truyền đi xa hay lưu trữ, nhập dữ liệu tự động, nhận dạng chữ trong các ứng dụng văn phòng, nhận dạng mã vạch trong thương mại, phát hiện cháy rừng qua các ảnh chụp từ vệ tinh, báo bão, dự báo thời tiết, phát hiện các mục tiêu quan sự, kiểm định sản phẩm, nhận dạng vân tay vectơ hoá bản đồ, hoạt hình...
Chương 2. Các thuật toán đơn giản hoá
2.1. Đặt vấn đề
Các đối tượng trong các ứng dụng đồ họa và xử lý bản đồ số hóa như các hình ảnh, các đường biên trên bản đồ... thường được biểu diễn bằng một tập các đường cong, trong đó mỗi đường cong là một chuỗi các đoạn thẳng liên tục. Trong các cơ sở dữ liệu bản đồ, dữ liệu ảnh thường được lưu dưới dạng vectơ thay cho dạng ma trận nhằm giảm không gian lưu trữ. Khi vectơ hóa bản đồ theo phương pháp thủ công, người ta lấy mẫu liên tục khi con trỏ được di chuyển dọc theo đường vẽ tay. Mật độ tọa độ trong kiểu số hóa này luôn được xác định bởi khoảng thời gian lấy mẫu, dẫn đến phát sinh các dữ liệu thừa. Với hầu hết các nhu cầu thực tế thì các dữ liệu thừa này cần được loại bỏ.
Việc tổng hợp dữ liệu bản đồ để nhận được bản đồ tỉ lệ nhỏ hơn từ bản đồ có tỉ lệ lớn đã dẫn đường cho sự phát triển các thuật toán cho một loạt các phép toán tổng hợp, trong đó có đơn giản hóa đường cong.
2.2 Giải quyết vấn đề
Đã có nhiều cách tiếp cận xuất sắc được đề xuất và nhiều thuật toán được chương trình hoá, làm đơn giản số điểm cần thiết để thay mặt cho đường đã được số hoá. Một trong số chúng đã được dùng trong việc quy hoạch các ứng dụng trong phục vụ vẽ bản đồ . Không phải mọi phương pháp đều đã được kiểm nghiệm một cách toàn diện để đo đạc hay đánh giá tính khả thi của chúng. Các phương pháp có thể được phân loại một cách rõ ràng thành các dạng khác nhau sau: Loại bớt số điểm của một đường bởi một hay nhiều tiêu chuẩn; Xấp xỉ đường bằng các hàm toán học; Đại diện đường bằng cách xoá bớt những đối tượng đặc biệt...
2.3.Các thuật toán đơn giản hóa đường cong
2.3.1.Thuật toán thu gọn đỉnh
Thuật toán thu gọn đỉnh là một thuật toán rất nhanh với độ phức tạp là O(n). Nó là thuật toán nhanh nhất và đơn giản nhất nhưng đưa ra kết quả thô nhất.
Trong thu gọn đỉnh, các điểm liên tục ở quá gần nhau được giảm xuống thành một điểm đơn. Tức là, một đỉnh của đa giác bị loại bỏ khi khoảng cách từ nó tới đỉnh tắt trước đó nhỏ hơn một khoảng sai số tối thiểu ε > 0.
Cho một tập hợp các đỉnh {V1,V2,,Vn} ,sai số ε > 0
Hình 1 :Thuật toán thu gọn đỉnh
Theo thuật toán thu gọn đỉnh ta sẽ xét xem có khoảng cách nào giữa các đỉnh lớn hơn sai số ε không.
Nhìn hình vẽ ta thấy khoảng cách giữa (V1,V4) là lớn hơn ε nên ta giữ lại hai đỉnh V1,V4.Còn khoảng cách giữa (V1,V2) và (V1,V3) đều nhỏ hơn ε nên hai đỉnh V2,V3 sẽ bị loại bỏ.
Thuật toán tiếp tục xét cho đến đỉnh Vn.
2.3.2.Thuật toán khoảng cách trực giao
Thuật toán khoảng cách trực giao, do Jenks đưa ra năm 1989.
Tính toán khoảng cách trực giao (ký hiêu là d) từ đường thẳng nối hai cặp tọa độ tới cặp tọa độ trung gian.So sánh d với sai số t cho trước.Nếu d < t thì loại bỏ cặp toạ độ trung gian. Ngược lại thì sẽ giữ cặp toạ độ trung gian đó và nó trở thành điểm đầu tiên của đoạn đang xét.
Cho đường cong gồm các đỉnh {a, b,c, d, e} ,với sai số t cho trước.
a
b
c
d
e
t
d1
d2
d3
Hình 2:Minh hoạ thuật toán khoảng cách trực giao
Sau khi thu gọn băng thuật toán khoảng cách trực giao ta có đường cong gồm các đỉnh {a, b, e}
Cải tiến thuật toán khoảng cách trực giao:
Hình 3 : Cải tiến thuật toán khoảng cách trực giao
Đầu tiên ta cũng chọn 3 điểm (P0, P1, P2). P0 là điểm cố định, P2 là điểm động, các điểm giữa điểm cố định và điểm động gọi là các điểm trung gian. Sau đó tính khoảng cách vuông góc a từ P1 tới đường thẳng nối P0 và P2.
Nếu khoảng cách này lớn hơn sai số ε, điểm P0 được đưa vào đường cong xấp xỉ, điểm P1 trở thành điểm cố định và ba điểm được chọn tiếp theo là (P1, P2, P3).
Nếu a<ε, điểm động được chuyển đến P3, hai điểm trung gian là P1 và P2.
Nếu khoảng cách vuông góc lớn nhất từ các điểm trung gian đến đường thẳng nối điểm cố định và điểm động lơn hơn sai số thì điểm cố định hiện tại được thêm vào đường cong xấp xỉ và chuyển điểm cố định đến điểm xa nhất đó.
Nếu khoảng cách này vẫn nhỏ hơn sai số thì điểm động được chuyển đến điểm tiếp theo của đường cong và các khoảng cách được tính lại.
Để tránh việc phải tính toán lại các khoảng cách rất mất thời gian, với ví dụ trong hình 3, ta nhận xét rằng a+b+c luôn lớn hơn d, do đó nếu a+b+c<ε thì d cũng nhỏ hơn ε. Vì vậy, mỗi lần thay đổi điểm động, ta chỉ cần tính một khoảng cách và cộng vào tổng các khoảng cách trước đó rồi so sánh với sai số. Nếu tổng khoảng cách này lớn hơn sai số thì ta mới tiến hành tìm kiếm điểm xa nhất làm điểm cố định cho lần xét tiếp theo.
2.3.3.Thuật toán Douglas-Peucker
Thuật toán do Douglas và Peucker đưa ra năm 1973. Đây là một thuật toán nổi tiếng, được đánh giá là đưa ra kết quả hợp lý nhất với sai số cho trước. Thuật toán Douglas-Peucker được sử dụng rộng rãi cho cả đồ họa máy tính và các hệ thống thông tin địa lý.
Hình 4: Thuật toán Douglas-Peucker
Xem xét xem khoảng cách lớn nhất từ đường cong tới đoạn thẳng nối hai điểm mút của đường cong có ngưỡng lớn hơn θ không .Nếu lớn hơn thì điểm đó được giữ lại làm điểm chia đường cong và thuật toán được thực hiện tương tự như hai điểm vừa tìm được . Nếu ngược lại thì kết quả của thuật toán là hai điểm mút của đường cong .
Thuật toán tỏ ra thuận lợi đối với các đường cong thu nhận được mà gốc là các đoạn thẳng ,phù hợp với việc đơn giản hoá trong quá trình véctơ các bản vẽ kỹ thuật ,sơ đồ thiết kế mạch in.
2.3.4 Thuật toán Band Width
Trong thuật toán Band Width ta hình dung có một dải băng di chuyển từ đầu mút đường cong sao cho đường cong nằm trong dải băng đó cho đến khi có điểm thuộc đường cong chạm vào biên của dải băng, điểm này sẽ được giữ lại.Quá trình này sẽ được thực hiện với phần còn lại của đường cong bắt đầu từ điểm vừa tìm được c...

---