Bài giảng môn Xử lý ảnh số - Chương 4: Các cấu trúc dữ liệu

Chương 4: CÁC CẤU TRÚC DỮ LIỆU Võ Quang Hoàng Khang TPHCM - 2016 1. Các mức biểu diễn dữ liệu hình ảnh 2. Traditional data structures 3. Hierarchical data structures 2  Mô tả được các mức biểu diễn hình ảnh.  Giải thích được lý do sử dụng các cấu trúc dữ liệu/mã để biểu diễn ảnh.  Nhận diện được mục đích sử dụng của các cấu trúc/mã:  Chain  Run-length  Topology  Hierarchical 3 • Iconic image: mức biểu diễn thấp nhất, ma trận số nguyên chứa giá trị về độ sáng của các pixel. • Segmented image: các pixel thuộc về một vùng của cùng một đối tượng. • Geometric representations: hình dạng 2D, 3D. • Relational model: cho chúng ta khả năng xử lý dữ liệu hiệu quả hơn và ở mức độ trừu tượng cao hơn. • Ma trận - Matrices • Mã xích – Chain Codes • Mã loạt dài - Run Length Codes • Đồ thị - Graphs • Relational databases • Cấu trúc dữ liệu phổ biến nhất đại diện cho một hình ảnh ở mức thấp (low-level) • Ảnh nhị phân: ma trận chỉ chứa các giá trị 0 và 1 100 116 126 129 103 106 113 119 98 101 106 109 96 98 101 105 100 116 126 129 103 106 113 119 98 101 106 109 96 98 101 105           • Vùng ảnh (phân đoạn) được biểu diễn bởi đường biên của vùng. • Chain code: đại diện cho một đường biên bằng chuỗi kết nối các đoạn đường thẳng có độ dài và hướng. • Có thể dùng 4-neighbor hoặc 8-neighbor • Thông tin hữu ích từ chuỗi Chain code: Chu vi của vùng = số phần tử trong chuỗi chain code • Thay thế chuỗi các giá trị brightness bởi: (hàng, cột bắt đầu, cột kết thúc) • Mô tả ảnh bởi tập các phần tử và mối quan hệ giữa chúng: • đồ thị vùng liền kề • relational structures 13 5 4 2 6 0 13 5 4 2 6 0 1 2 6 3 5 4 0 • node: vùng • arcs: các vùng lân cận Object Name Density (x,y) Inside 1 Background 8 (1,1) 2 Chest wall 140 (347,107) 1 3 Right lung 35 (145,159) 2 4 Left lung 35 (357,146) 2 5 Heart 142 (259,165) 2 6 Aorta 148 (280,319) 2 1 3 5 4 2 6  Phân tích hình ảnh ở các độ phân giải khác nhau: – M-pyramids (matrix-pyramids) – T-pyramids (tree-pyramids) • A sequence of images {ML, ML-1, , M0} ML ML-4ML-3ML-2ML-1 ML-5 • ML represents the original image • Mi-1 is derived from Mi by reducing the resolution by a factor of 2 ML 256 x 256 ML-4 16 x 16 ML-3 32 x 32 ML-2 64 x 64 ML-1 128 x 128 ML-5 8 x 8  Phân tích ảnh ở các độ phân giải khác nhau cùng một lúc Level 0 Level 1 Level 2 Level L-2 (ML-2) Level L-1 (ML-1) Level L (ML) 20 x 20 21 x 21 22 x 22 2L-2 x 2L-2 2L-1 x 2L-1 2L x 2L • Cho phép phân tích ảnh ở các độ phân giải khác nhau cùng một lúc • T-pyramid biểu diễn đầy đủ CTDL dạng cây theo phương pháp tiếp cận “bottom-up“. • Quadtrees là một modify của T-pyramid. • Mỗi node của Tree có 4 con. • Begin with the original 2L x 2L image Level 0 • Begin with the original 2L x 2L image and divide it into 4 quadrants each of dimension 2L-1 x 2L-1 0 1 32 0 1 2 3 Level 0 • Tiếp tục chia nhỏ các nút nếu chưa thỏa mãn tiêu chí đồng nhất. 0 32 0 2 3 8 9 1110 8 9 10 11 Level 0 Level 2 36 37 38 39 48 49 50 51 • Lặp lại cho đến khi thỏa mãn tiêu chí đồng nhất 0 32 0 2 3 9 10 9 10 36 37 38 39 48 49 50 51 Level 0 Level 2 Level 3 • A binary image Level 0 1 2 Level 0 2 1 Level 0 1 2 16 17 18 195 6 7 2 1 5 76 16 17 1918 Level 0 Level 3 16 17 18 19 1 2 20 21 22 23 5 6 7 2 1 5 76 16 17 1918 20 21 2322 •Cây có thể được mã hóa bởi một chuỗi các kí tự: b, w, và g. 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b b ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b b w ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b b w g( ) ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b b w g( b ) ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b b w g( b b ) ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b b w g( b b w ) ) ) 16 17 18 19 1 2 5 6 7 20 21 22 23 Code: g( g( b b w w ) b w g( b b w g( b b w w ) ) ) Level of image data representation  Data structures together with algorithms are used to devise solutions to computational tasks.  Data structures for vision may be loosely classified as  * Iconic  * Segmented  * Geometric  * Relational *Boundaries between these layers may not be well defined. Traditional image data structures  The matrix (2D array) is the most common data structure used for low- level representations, implemented as an array.  Matrices hold image data explicitly. Spatial characteristics are implicitly available.  Binary images are represented by binary matrices; multispectral images are represented by binary matrices; Hierarchical image structures are represented by matrices of different dimensions;  The co-occurrence matrix is an example of global information derived from an image matrix; it is useful in describing texture. Traditional image data structures cont.  Chains may be used to describe pixel paths, especially borders.  Chain codes are useful for recognition based on syntactic approaches.  Run length codes are useful for simple image compression.  Graph structures may be used to describe regions and their adjacency. These may be derived from a region map, a matrix of the same size as the image.  Relational structures may be used to describe semantic relationships between image regions. Hierarchical data structures  Hierarchical structures can be used to extract large-scale features, which may be used to initialize analysis. They can provide significant computational efficiency.  M-pyramids and T-pyramids provide data structures to describe multiple image resolutions.  Quadtrees are a variety of T-pyramid in which selected areas of an image are stored at higher resolution than others, permitting selective extraction of detail.  Many algorithms for manipulation of quadtrees are available. Quadtrees are prone to great variation from small image differences.  Leaf codes provide a more efficient form of quadtree.  Many ways of deriving pyramids exist, dependent on choice of reduction window.