Đồ án Xử lý đường cong tự động

MỤC LỤC LỜI CẢM ƠN Em xin chân thành cảm ơn 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 cám ơn 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 hoặc 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 hoặc 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 để đại diện 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 cho đến khi thực hiện đường cong. ’ Hình 5: đơn giản hoá đường cong theo thuật toán Band Width Cụ thể, phương pháp bắt đầu bằng việc xác định điểm đầu tiên trên đường cong và coi nó như là một điểm chốt (P1).Điểm thứ ba (P3) được coi là điểm động.Những điểm này xác định một đoạn thẳng ,còn các điểm trung gian trong phạm vi điểm chốt và điểm động được kiểm tra để tìm ra một điểm có khoảng cách vuông góc lớn nhất tới đường thẳng xác định bởi điểm chốt và điểm động (di).Nếu khoảng cách này nhỏ hơn một khoảng T cực đại thì đoạn thẳng đó được coi là thích hợp để đại diện cho đường cong giới hạn từ điểm chốt đến điểm động,tức là điểm tương ứng với khoảng cách lớn nhất được giữ lại.Trong trường hợp điều kiện này không thoả mãn thì điểm nằm ngay sau điểm động sẽ trở thành điểm động mới.Khi chu trình được lặp lại thì điểm chốt được chuyển đến điểm động và điểm thứ ba tính từ điểm chốt mới được chỉ định làm điểm động mới.Tập hợp những điểm mà được chọn làm điểm chốt sẽ tạo nên một đường tổng quát đại diện cho đường cong. Thuật toán tăng tốc độ trong trường hợp đường ống chứa nhiều điểm , điều đó có nghĩa là độ lệch giữ các điểm trong đường thẳng là nhỏ hay độ dày nét của đường được véctơ hoá là mảnh. 2.3.5 Thuật toán Angularity Tolerance Phương pháp góc đo bắt nguồn từ phương pháp dải băng ở trên, nhưng thay vì làm việc với khoảng cách nó thực hiện với các góc. Điểm đầu tiên gọi là điểm chốt, điểm thứ 3 gọi là điểm động, còn điểm thứ 2 là điểm trung gian. Từ 3 điểm đó dựng lên 1 góc, đỉnh tương ứng với điểm trung gian. Sau đó so sánh giá trị của góc này với một giá trị ngưỡng cho trước, nếu nó lớn hơn thì điểm trung gian sẽ bị loại. Đồng thời điểm động chuyển tới điểm tiếp theo, còn điểm trung gian được gán bởi điểm động, điểm chốt giữ nguyên. Nếu gốc này nhỏ hơn ngưỡng thì điểm trung gian được giữ nguyên, điểm trung gian và điểm động được gán như trên, riêng điểm chốt được gán tới điểm trung gian chứ không cố định như trước. Hình 6:Minh hoạ cho thuật toán Angularity Tolerance Theo thuật toán Angularity Tolerance ta thực hiện như sau: Gán P1 cho biến Pchốt, P3 cho biến Pđộng. Tính góc a = [Pchốt, Pchốt-1, Pđộng] tức là góc tạo bởi tam giác 3 đỉnh là Pchốt, Pchốt-1 và Pđộng. So sánh a với ngưỡng Tolerance ( cho trước). Nếu a > Tolerance thì điểm Pchốt giữ nguyên Pchốt-1 và Pđộng chạy đến điểm tiếp theo. Nếu a < Tolerance thì điểm Pchốt chuyển đến Pchốt-1 còn điểm Pđộng-1 và điểm Pđộng chuyển đến điểm tiếp theo. Quá trình này lặp lại cho toàn bộ đường cong. Do trong quá trình đơn giản hoá thuật toán sử dụng các bước tính góc nên thuận lợi đối với các đường cong thu nhận được mà gốc là các đường uốn phù hợp với việc đơn giản hoá trong quá trình véctơ các bản đồ địa hình thuỷ văn đường giao thông. 2.4 Nhận xét các thuật toán đơn giản hoá đường cong: Các thuật toán Rút gọn đường cong Khoảng cách trực giao Douglas-Peucker Band Width Angularity Tolerance Ưu điểm -Là thuật toán nhanh nhất và đơn giản nhất -Tốc độ xử lý nhanh. -Tốt cho đường cong thu nhận được có gốc là các đoạn thẳng -Tăng tốc độ trong trường hợp đường ống chứa nhiều điểm . -Ít ảnh hưởng bởi nhiễu -Thuận lợi đối với các đường cong thu nhận được mà gốc là các đường uốn Nhược điểm Đưa ra kết quả thô sau khi loại bớt các điểm trên đường cong. Không hiệu quả khi áp dụng cho các đường cong có số cặp tọa độ rất lớn. Bị ảnh hưởng bởi nhiễu. Không phát hiện ra điểm đặc trưng. Bị ảnh hưởng bởi nhiễu. Ứng dụng Được dùng làm giai đoạn tiền xử lý cho các thuật toán khác. Được dùng cho các trường hợp dò tìm vân tay . Được dùng cho các trường hợp là bản vẽ kỹ thuật hoặc thiết kế mạch in. Được dùng cho các trường hợp làm mảnh đường cong cho trước. Được dùng cho các trường hợp véctơ bản đồ địa hình thuỷ văn ,hoặc đường giao thông. KẾT LUẬN: KẾT QUẢ CỦA KHÓA LUẬN Nội dung chính của khóa luận nhằm đi sâu nghiên cứu một số phương pháp xử lý đường cong số hóa đường cong chủ yếu nhằm phục vụ cho việc lưu trữ và xử lý ảnh bản đồ. Các thuật toán được giới thiệu trong khóa luận này là những phương pháp đã được kiểm nghiệm và hiện đang được sử dụng rộng dãi trên thế giới, bao gồm các phương pháp làm trơn và đơn giản hóa. + Tổng quan về tổng quát hóa đường cong và những ứng dụng trong xử lý ảnh. + Đã đưa ra nội dung chi tiết của các phương pháp như: phương pháp thu gọn đỉnh, phương pháp khoảng cách trực giao, phương pháp Douglas-Peuker, phương pháp Bandwith, phương pháp Angularity và ứng dụng của nó trong việc giải quyết một số khó khăn trong quá trình xử lý và hiện thị bản đồ. + Chương trình được viết bằng ngôn ngữ visual C++ chủ yếu là mô phỏng các thuật toán bẵng dữ liệu là các đường cong đã có sẵn với ba thuặt toán đơn giản hóa. Chương trình có khả năng xử lý các bản đồ kích thước lớn, trích chọn ra các đường biên bản đồ và thực hiện đơn giản hoá để giảm không gian lưu trữ, lấy đầu vào cho các thuật toán khác hoặc lưu trữ vào cơ sở dữ liệu bản đồ. Việc vectơ hoá bản đồ diễn ra tự động, giúp hoàn thành công việc nhanh hơn rất nhiều và chính xác hơn phương pháp thủ công. Tuy nhiên, do lần đầu tiếp cận và thời gian hạn chế, khoá luận không tránh khỏi những sai sót. Khoá luận mới chỉ dừng lại ở mức nghiên cứu và tổng hợp các thuật toán đã có. Hướng phát triển tiếp theo của chương trình là xây dựng một phương pháp trích chọn đường cong tốt hơn để có thể xử lý các bản đồ có cấu trúc phức tạp. PHỤ LỤC Giới thiệu một số hình ảnh của chương trình và hướng dẫn sử dụng minh hoạ HÌnh 1: Giao diện chính của chương trình. HÌnh 2 : Đơn giản hoá đường cong ban đầu với thuật toán Angularity Tolerance HÌnh 3 : Đơn giản hoá đường cong ban đầu với thuật toán Band Width HÌnh 4 : Đơn giản hoá đường cong ban đầu với thuật toán Douglas-Peucker TÀI LIỆU THAM KHẢO [1] Ballard, D. 1981. “Strip Tree:A Hierarchical Representation for Curve”. Communications, vol 24. pp 310-321, American Association for Computing Machinery. [2] Brrough, P. 19886. Principle of Graphical Information System for Land Resouces Assessment. Oxford England: Clarendon Press. [3] Cromley,R., and G. Campell 1991. “Noninferior Bandwidth Line Simplification: Algorithms and Structural Analysis”, Graphical Analysis, forthoming. [4] Cromley,R. 1988.”A Vertext Substitution Approach Numerical Line Simplification”, Proceeding, Third International Symposium on Spatial Data Handimg, pp 57-63. [5] Douglas, D and T.Peucker 1973.” Algorithms for the Redution of the Number of Points Required to Represent a Digited Line or Its Caricature.”The Canadian Cartographer, vol 10, pp. 112-122. [6] Peucker, T.1976. “A Theory of the Cartographic Line”, Intrnational Yearbook of Cartography, vol 16, pp 134-143. [8] Hà Quốc Việt, “Một số phương pháp đơn giản hóa đường cong”, Luận văn tốt nghiệp, K40, Toán tin, ĐHKHTN, Tháng 5/1998. [9] Lương Mạnh Bá, Nguyễn Thanh Thuỷ. Nhập môn xử lý ảnh số. Nhà xuất bản khoa học kỹ thuật . [10] Ngô Quốc Tạo. Tập bài giảng “Nhập môn xử lý ảnh”.