Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010
Page 1

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA TOÁN – TIN HỌC
BÁO CÁO ĐỀ TÀI
CẤU TRÚC DỮ LIỆU Nhóm Sinh viên
Trần Giang Nam
0811094

Nguyễn Hồng Quy
0811137

Nguyễn Hoàng Quốc
0811300
Giáo viên hướng dẫn
TS. Phạm Thế Bảo


chụp của một vệ tinh về một phần nào đó của một hành tinh hoặc vũ trụ đều là
những ảnh có kích thước rất lớn. Những ảnh này được truyền về mặt đất sau khi
chụp và yêu cầu đầu tiên đặt ra cho những người tiếp nhận là làm sao đọc được nó.
Tất nhiên việc đọc trực tiếp là không thể, vì bộ nhớ của máy có giới hạn rất nhỏ so
với kích thước ảnh. Một ví dụ khác trong xử lý ảnh lớn là các ứng dụng bản đồ trên
mạng (như diadiem.com, googleearth [1]), việc lưu trữ và đọc trực tiếp những bức
ảnh bản đồ lớn bao quát một phần diện tích lớn trên mạng là điều khó khả thi.

Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010
Page 3
Hình 1. Bản đồ trên mạng tại trang web www.diadiem.com
Bởi cách đọc trực tiếp gặp nhiều khó khăn, nên yêu cầu phải xây dựng một
cấu trúc dữ liệu (CTDL) đọc ảnh kích thước lớn đã được đặt ra. Đối với một bức
ảnh lớn, thường thì người ta chỉ quan tâm một vùng nào đó trong ảnh, theo đó một
tư tưởng phổ biến trong việc xây dựng CTDL là cắt ảnh thành nhiều ảnh nhỏ hơn,
tổ chức lưu trữ chúng và khi cần xử lý ta sẽ chỉ lấy những bức ảnh thuộc vùng cần
quan tâm lên để xử lý.
Trong bài báo cáo này, chúng tôi sẽ trình bày về CTDL cây nhị phân trên
không gian hai chiều (kd-tree in two dimentions) để lưu trữ hình ảnh và dùng thuật
toán tìm láng giềng gần nhất (Nearest neighbor search) để truy cập tới những bức
ảnh thuộc vùng cần quan tâm. Các thuật toán sẽ được trình bày chi tiết ở dưới.
Phần đánh giá kết quả chúng tôi sẽ chạy chương trình minh họa thuật toán trên một
bức ảnh 10Mb.

Page 4

Hình 2. Khung nhìn để đọc ảnh
Sau khi tải ảnh lên, ta sẽ có một tấm ảnh ban đầu. Trong khung nhìn sẽ có
một số tọa độ cố định (chấm màu xanh trong hình 2) để làm chuẩn và một con trỏ
đặt ở một vị trì mặc định nào đó, trong trường hợp này con trỏ đặt ở tâm khung
nhìn. Con trỏ này tượng trưng cho tọa độ trong ảnh lớn mà ta muốn quan sát. Khi
ta muốn di chuyển khung nhình tới các vùng khác của ảnh (có 4 thao tác di chuyển
khung nhìn: di chuyển lên, di chuyển xuống,di chuyển sang trái, di chuyển sang
phải), ta chỉ việc thay đổi lại tọa độ con trỏ và tải lại các ảnh tương ứng với con trỏ
mới lên khung nhìn.
3. Xây dựng cây nhị phân trên không gian hai chiều
3.1. Giới thiệu về cây nhị phân trên không gian k chiều
Cây nhị phân trên không gian k chiều [2],[4] (kd tree hay k-dimentions tree)
là một cấu trúc dữ liệu phân hoạch không gian k chiều. Theo đó, mỗi đỉnh của cây
sẽ chia không gian thành hai phần bằng một siêu phẳng k-1 chiều xác định bởi tọa
độ của đỉnh đó và một chiều nào đó trong k chiều. Các chiều dùng để chia thay đổi
tuần tự theo từng cấp của cây.
Về bản chất đây là một cây nhị phân (vì mỗi đỉnh của cây sẽ có tối đa 2
nhánh con tương ứng với hai vùng không gian được chia). Điểm đặc biệt ở đây là
các đỉnh của cây là những điểm phân chia không gian thành nhiều phần. Việc phân
chia không gian như vậy sẽ thuận tiện cho ta trong việc tìm kiếm những điểm trong
cây gần với một điểm nào đó trong vùng không gian nhất. Tức là khi muốn tìm
Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010 Tiếp đó, đối với hai
nhánh con của cây,
ta sẽ thực hiện phân
hoạch theo y. Nhánh
bên trái lấy (5,4) làm
nút, nhánh bên phải
lấy (9,6) làm nút. Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010
Page 6
Cứ tiếp tục chia như
thể với x, y lần lượt
đổi vị trí cho nhau
đến khi không còn
chia được nữa, ta sẽ
thu được cây. Khi
đó, các nút lá là các
điểm cô lập thuộc
một vùng không gian
nào đó

gian 2 chiều. Tức là chỉ lưu trữ một lớp ảnh để tải ảnh lên để quan sát.
3.2. Các phép toán
Vì cây nhị phân trên không gian hai chiều bản chất là một cây nên nó cũng
có các thao tác tương tự đối với cây như khởi tạo cây, thêm đỉnh, xóa đỉnh, duyệt
cây Điểm khác là mỗi đỉnh lưu trữ một tọa độ trên không gian hai chiều nên ta
phải lưu lại một giá trị chỉ chiều của đỉnh. Ở phần này, chúng tôi chỉ trình bày một
số thao tác mà chúng tôi có sử dụng, các thao tác khác có thể xây dựng dễ dàng
tương tự như ở cây nhị phân thông thường.
3.2.1. Thêm một đỉnh vào cây
Việc thêm một đỉnh vào cây đơn giản giống như ở cây nhị phân tìm kiếm,
nhưng ở đây ta thêm một ràng buộc là những đỉnh ở mức chẵn của thì ta sẽ so sánh
theo y, những đỉnh ở mức lẻ của cây thì ta sẽ so sánh theo x. Ví dụ, với một đỉnh
(a,b) ở mức 3 thì nhánh con trái của nó sẽ chứa các đỉnh có hoành độ x nhỏ hơn a,
và nhánh con phải của nó sẽ chứa các đỉnh có hoành độ x không nhỏ hơn a.
3.2.2. Tạo cây
Để có được cây nhị phân trong không gian hai chiều. ta lần lượt thêm các
đỉnh vào cây. Nhưng việc thêm lần lượt hoặc bất kỳ các đỉnh vào cây dẫn tới một
việc là cây sẽ bị mất tính chất cân bằng dẫn đến việc truy xuất dữ liệu, điển hình là
hành vi tìm làng giềng gần nhất sẽ tốn một chi phí cao hơn và tính chất hiệu quả
của cây bị giảm đi.
Vì vậy người ta đề xuất phương pháp chọn trung vị để thêm lần lượt vào cây
để đảm bảo tính cân bằng của cây. Trung vị là điểm có vị trí sao cho có thể chia
cây thành hai phần có số đỉnh chênh lệch thấp nhất.
Để rõ hơn, ta sẽ xét bộ dữ liệu sau {(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}
Đầu tiên, ta sắp xếp theo x: {(2,3), (4,7), (5,4), (7,2), (8,1), (9,6)}, sau đó ta
phân chia tập hợp hành hai nhánh, lấy phần tử (7,2) làm gốc. Vì chọn (7,2) sẽ làm
cho 2 nhánh con có độ chênh lệch ít nhất.
Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010

Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010
Page 9
struct area {
int xmax,ymax,xmin,ymin;
};
struct location{
int x,y;
};
struct Node {
location Data;
area axis;
int level;
Node *Left;
Node *Right;
} ;
struct KDTree {
Node *Root;
};
3.3. Dùng cây nhị phân trên không gian hai chiều để lưu trữ ảnh
Từ những ảnh đơn vị, ta tiến hành dùng phép toán tạo cây để lần lượt thêm
các ảnh đơn vị vào cây. Mội đỉnh của cây sẽ chứa tọa độ và con trỏ trỏ đến địa chỉ

Bước 3: Thự hiện dò ngược lại cây(bung đệ quy với các node còn lại được
so sánh khoảng cách lớn hơn) với các bước sau :
1. Nếu node đang xét có khoảng cách tới điểm tìm kiểm là nhỏ nhất
hiện tại thì cập nhật nó là điểm gần nhất.
2. Thuật toán sẽ tìm kiếm trong các phần còn lại của không gian bị
chia cắt (các nhánh còn lại của cây) có node nào của cây có khoảng cách tới điểm
đang xét là gần nhất hiện thời hay không. Thực hiện bằng cách xét quả cầu có tâm
là điểm tìm kiếm, bán kính là khoảng cách gần nhất hiện thời xem nó có giao với
các không gian bị chia cắt nào không rồi tiến hành so sánh với các điểm trong miền
không gian đó.
1. Đối với mỗi mặt phẳng giao với quả cầu, ta thực hiện duyệt
phần nhánh con tương ứng với mặt phẳng đó.
2. Đối với các nhánh không cắt quả cầu, thuật toán sẽ bỏ qua
nhánh đó.
Bước 4: khi quá trình duyệt quay trở về node gốc, thuật toán kết thúc.
Mở rộng: tìm N điểm gần nhất.
Trong trường hợp muốn tìm N node gần điểm tìm kiếm nhất, chúng ta có
nhiều cách dựa trên thuật toán tìm láng giềng gần nhất đã được trình bày phía trên,
ở đây chúng tôi đề xuất cải tiến thuật toán như sau: Trong quá trình tìm kiếm, khi
đã tìm được láng giềng gần nhất ta tiến hành bung độ lớn của bán kính vòng tròn
để tìm và đánh dấu những điểm được cho là gần nhất tiếp theo điểm đã tìm được.
Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010
Page 11 Hình 4.1. Minh họa bước 1,2 thuật toán tìm kiếm láng giềng gấn nhất
Ở hình 4.2, ta thấy thuật toán bắt đầu duyệt lại các nhánh đã bỏ đi, ta thấy ở
đây những điểm thuộc vùng không gian nào giao với hình tròn sẽ được biểu thị
bằng màu đỏ. Thuật toán chỉ tìm kiếm trên những điểm đó để phát hiện ra những
điểm tối ưu. Quan sát theo quá trình thực hiện ta thấy các điểm tối ưu sẽ được cập
nhật mới và vòng tròn sẽ ngày càng nhỏ hơn. Đối với những vùng không gian
không giao với hình tròn, chúng ta sẽ bỏ qua luôn mà không xét tới (vùng tô màu
xanh). Ta thấy ở hình cuối cùng, vùng màu xanh rất lớn trong khi những điểm màu
đỏ rất ít tức là ta đã thu hẹp không gian tìm kiếm rất nhiều.
Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010
Page 13
nhớ chưa được tối ưu và ổn định. Bên cạnh đó do không có nhiều bộ dữ liệu mẫu
nên việc chúng tôi chưa đánh giá được thuật toán khi chạy với các dữ liệu rất lớn.
Hướng phát triển: xây dựng thêm nhiều lớp bằng việc xây dựng nhiều tầng
cây để phục vụ cho việc zoom hình ảnh.
Load ảnh .png để có dung lượng nhẹ hơn.
Sử dụng con trỏ chuột linh động bằng các công cụ hỗ trợ của phần
mềm lập trình window để thay đổi giá trị con trỏ một cách tự do.
Xây dựng cây kd-tree đa chiều để xây dựng nhiều lớp khác nhau cho
bản đồ, ví dụ các lớp ghi chú, tên địa điểm hoặc tìm đường đi trên bản đồ.

Cấu trúc dữ liệu đọc ảnh kích thước lớn
2010
Page 15
6. Tài liệu tham khảo
[1] Một số địa chỉ trên mạng ứng dụng ảnh lớn:

Bức ảnh chụp Hà Nội ghép từ 1000 tấm ảnh nhỏ

Trang web bản đồ thành phố

Ứng dụng mô phỏng hành tinh của google

[2] Andrew W.Moore, An introductory tutorial on kd-tree, Carnegie Mellon University,
Canada.