Bài giảng Xử lý ảnh số - Chương 4: Các cấu trúc dữ liệu - Võ Quang Hoàng Khang

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.