Tăng tốc độ phát hiện dị thường trên ảnh đa phổ và siêu phổ ứng dụng trong tìm kiếm cứu nạn

Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Tăng tốc độ phát hiện dị thường trên ảnh đa phổ
và siêu phổ ứng dụng trong tìm kiếm cứu nạn
Nguyễn Văn Phương, Đào Khánh Hoài, Tống Minh Đức
Học viện Kỹ thuật Quân sự, Hà Nội
Tác giả liên hệ: Nguyễn Văn Phương, phuongnv@mta.edu.vn
Ngày nhận bài: 14/06/2019, ngày sửa chữa: 27/10/2019, ngày duyệt đăng: 27/10/2019
Định danh DOI: 10.32913/mic-ict-research-vn.v2019.n2.866
Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: TS. Phan Anh Huy
Tóm tắt: Máy dò dị thường do Reed và Yu đề xuất được công nhận là máy chuẩn để phát hiện dị thường trên ảnh đa
phổ và siêu phổ. Tuy nhiên, máy này có một số hạn chế: dữ liệu ảnh phải tuân theo mô hình Gauss đa biến, tính toán
nghịch đảo của ma trận hiệp phương sai rất phức tạp khi ảnh nền có kích thước lớn, hoạt động thiếu ổn định, đôi khi
có tỉ lệ báo động giả cao, thiếu mối liên hệ không gian giữa các điểm ảnh. Quy tắc quyết định Neyman-Pearson thường
được sử dụng dựa trên việc tính toán hàm mật độ xác suất phi tham số của dữ liệu nền để nâng cao hiệu suất và độ tin
cậy, nhưng lại có độ phức tạp tính toán cao. Để giảm độ phức tạp tính toán và thời gian tính toán, nhiều phương pháp
đã được sử dụng, như: biến đổi Fourier nhanh, biến đổi Gauss nhanh, lập trình đa luồng trên bộ xử lý trung tâm (CPU),
song song trên bộ xử lý đồ họa (GPU). Bài báo này trình bày một phương pháp ước lượng nhanh hàm mật độ xác suất
bằng cách phân nhóm các điểm ảnh trên miền giá trị và tổ chức dữ liệu trên cây Kd-tree. Kết quả kiểm nghiệm cho thấy
phương pháp đề xuất vượt trội các phương pháp khác và có thể ứng dụng trong thực tế.
Từ khóa: Tăng tốc độ phát hiện dị thường, Kd-tree, ước lượng mật độ phi tham số.
Title: Acceleration of Anomaly Detection in Multispectral and Hyperspectral Images for Search and Rescue Situations
Abstract: Reed-Yu detector is recognized as a standard algorithm for detecting anomalies on multispectral and hyperspectral
images. However, this detector has several limitations: image data must follow the multivariate Gaussian model,
calculation of the covariance matrix inverse is complex for large size background images is a complex, lack of robustness,
high false alarm rates sometimes, lack of spatial correlation among pixels. The Neyman-Pearson detection criterion is
often applied on the nonparametric probability density function of the background data for effectiveness and reliability,
at the expense of high computational complexity. To reduce the computational complexity, various methods can be
applied, such as: fast Fourier transform, fast Gaussian transform, multi-threaded programming on CPU, parallel on
GPU. This paper proposes a method for fast estimation of the density by grouping pixels based on the range of pixels
and organizing the data using the Kd-tree. The experimental results show that the proposed method outperforms the
state-of-the-art methods and can be applied in practice.
Keywords: Acceleration of anomaly detection, Kd-tree, non-parametric density estimation.
I. MỞ ĐẦU
Hoạt động tìm kiếm và cứu nạn bao gồm việc tìm kiếm
và giải cứu người, phương tiện bị mắc kẹt trong các tình
huống khó khăn hoặc báo nạn. Một cách tiếp cận đang
ngày càng được sử dụng nhiều trong tìm kiếm cứu nạn là
sử dụng ảnh đa phổ hay siêu phổ có độ phân giải cao được
thu từ các bộ cảm biến gắn trên máy bay hoặc vệ tinh. Tuy
nhiên, các ảnh hưởng bất lợi gây ra bởi đặc trưng của địa
hình, điều kiện thời tiết khắc nghiệt làm cho tọa độ báo
nạn có dung sai lớn. Các thiết bị cảm biến thu dữ liệu phải
quét trên một diện rộng và dung lượng dữ liệu lớn là một
rào cản đối với việc tìm kiếm thủ công bằng mắt thường.
Các kỹ thuật tiền xử lý dữ liệu và các thuật toán tìm kiếm
tự động là giải pháp phù hợp giúp người quan sát nâng cao
hiệu suất và tốc độ tìm kiếm.
Tự động phát hiện mục tiêu dựa trên các đặc trưng hình
học có thể được sử dụng để tiếp cận vấn đề này. Tuy nhiên,
các đặc trưng hình học của các đối tượng quan tâm không
được xác định rõ trong hầu hết các tình huống tìm kiếm
cứu nạn. Mặc dù trực tiếp tìm ra người đang gặp nạn sẽ là
lý tưởng, nhưng trong một số trường hợp các đồ vật đi kèm
như quần áo, vật dụng cá nhân, mảnh vỡ phương tiện, v.v.
có thể cung cấp một số thông tin hữu ích. Vì vậy, phát hiện
70
Tập 2019, Số 2, Tháng 12
dị thường sẽ cung cấp một cách tiếp cận phù hợp hơn cho
vấn đề này. Dị thường trên ảnh đa phổ và siêu phổ được
xác định là những điểm ảnh hoặc cụm điểm ảnh có phổ nổi
bật hoặc khác biệt nhiều so với những điểm ảnh lân cận.
Những điểm ảnh này thường là thưa thớt và hiếm khi đại
diện cho ảnh [1]. Nói chung, các dấu hiệu dị thường là rất
nhỏ về mặt không gian và tồn tại với xác suất thấp trong
một cảnh ảnh.
Trong hơn 20 năm qua, cộng đồng nghiên cứu trên thế
giới đã xây dựng rất nhiều bộ dò dị thường để phát hiện các
điểm ảnh dị thường trên ảnh đa phổ, siêu phổ. Dựa trên các
kỹ thuật khác nhau của các máy dò, dựa trên bốn nhóm giải
pháp chính: thống kê, hạt nhân, không gian đặc trưng và
phân đoạn [2]. Máy dò dị thường do Reed và Yu xây dựng
vào năm 1990 [3] là một trong những máy dò dị thường
dựa trên thống kê và được gọi là máy dò RX (RXD). RXD
đã khơi nguồn cho rất nhiều thuật toán được phát triển sau
này [2] và nó được coi là máy phát hiện dị thường chuẩn
cho hình ảnh đa phổ, siêu phổ [4]. Hiệu quả của RXD trong
việc phát hiện dị thường từ các ảnh đa phổ và siêu phổ đã
được kiểm chứng [1, 3–9]. Mặc dù vậy, RXD có những hạn
chế nhất định. Thứ nhất, việc ước lượng nghịch đảo của ma
trận hiệp phương sai của dữ liệu nền với kích thước chiều
dữ liệu lớn thường rất phức tạp và hoạt động không ổn
định [10, 11] dẫn đến làm suy yếu thuật toán. Thứ hai, đôi
khi RXD gây ra tỷ lệ báo động giả cao (ví dụ, một cái cây
đơn lẻ trong đồng cỏ được phát hiện là dị thường cục bộ
ngay cả khi toàn bộ ảnh có cả một khu rừng) [11–14]. Thứ
ba, RXD giả định dữ liệu nền tuân theo mô hình Gauss đa
biến, nhưng có nhiều trường hợp giả định này có thể không
đầy đủ vì trong thực tế các cảnh ảnh rất đa dạng và chứa
nhiều lớp đối tượng khác nhau [11, 14, 15]. Thứ tư, RXD
thiếu mối liên hệ về không gian, mỗi điểm ảnh được đánh
giá riêng lẻ và không quan tâm đến những điểm ảnh xung
quanh nó.
Để giảm những hạn chế của RXD, trong một vài năm
gần đây các nhà khoa học đã áp dụng quy tắc ra quyết định
dựa trên kiểm nghiệm tỷ lệ khả năng (LRT) dựa trên hàm
mật độ xác suất (PDF) của dữ liệu nền để phát hiện các dị
thường trên ảnh đa phổ và ảnh siêu phổ. Cụ thể, năm 2011
trong nghiên cứu [16] của Veracini và các cộng sự, phương
pháp đề xuất sử dụng Parzen Widnow (PW) để ước tính
PDF nền đã cho kết quả đáng tin cậy. Sau khi PDF nền
được xấp xỉ thông qua PW, nó được dùng làm đầu vào để
phát hiện các dấu hiệu dị thường trên ảnh dựa trên kiểm
nghiệm tỷ lệ khả năng. Năm 2012, trong nghiên cứu [1],
Bolukbasi và cộng sự đã xây dựng kiểm nghiệm giả thuyết
nhị phân cho phát hiện dị thường và sử dụng thuật toán
KNN để tìm láng giềng gần nhất để tính hàm mật độ xác
suất phi tham số cho điểm ảnh đang xét. Kết quả thu được
đã vượt so với RXD. Năm 2014, trong nghiên cứu [17],
Matteoli và nhóm tác giả đã đưa ra chiến lược để quyết
định một điểm ảnh có phải là dị thường hay là nền dựa
trên định lý Neyman-Pearson sử dụng các hàm PDF. Trong
đó các tác giả đã kiểm nghiệm trên ba hàm nhân PDF:
hạt nhân Gauss cố định băng thông, hạt nhân Gauss không
cố định băng thông (VKDE) và tìm kiếm láng giềng gần
nhất, để ước lượng hàm mật độ giống như trong [1]. Kết quả
là cả ba hàm nhân PDF trên đều cho ra hiệu suất phát hiện
dị thường cao hơn RXD. Năm 2017, trong nghiên cứu [18]
của Zhao và các cộng sự, sự kết hợp của các phương pháp
ước lượng mật độ phi tham số và phát hiện dựa trên biểu
diễn mối quan hệ tương quan (CRD), cho thấy hiệu suất
phát hiện dị thường khá cao và đã vượt RXD.
Tuy nhiên, độ phức tạp tính toán của kỹ thuật phi tham
số trong ước lượng hàm mật độ xác suất là ( 푛2), trong
đó 푛 là số lượng điểm ảnh và là số kênh phổ, làm cho việc
tính toán tốn kém thời gian (trong phần thực nghiệm của
bài báo, một ảnh màu ba kênh RGB, kích thước 3396×3349
pixel tốn gần 21 ngày để tính toán) dẫn đến khả năng ứng
dụng vào thực tế rất hạn chế, đặc biệt là ứng dụng trong
công tác tìm kiếm cứu nạn. Để tăng tốc độ tính toán, giảm
thời gian xử lý, một số kỹ thuật gần đúng đã được đề xuất.
Đầu tiên, đó là đề xuất của Silverman trong nghiên cứu [19]
sử dụng biến đổi Fourier nhanh (FFT) để ước lượng mật độ.
Nó làm giảm đáng kể yêu cầu tính toán của phương pháp
ước tính mật độ, đã giảm độ phức tạp tính toán từ ( 2)
xuống còn ( log ). Một phương pháp khác là áp dụng
biến đổi Gauss nhanh (FGT) được Elgammal và các cộng
sự đề xuất trong nghiên cứu [20]. Phương pháp này đã giảm
độ phức tạp tính toán từ ( ) xuống còn ( + ).
Trong đó, = 푛 là kích thước dữ liệu, và là số lượng
mục tiêu cần tính PDF. Mặc dù cả hai phương pháp FFT
và FGT đã giảm độ phức tạp tính toán PDF nhưng đổi lại,
việc tính toán gần đúng giảm hiệu suất phát hiện dị thường
của thuật toán.
Ngoài ra, một cách tiếp cận khác để giảm thời gian tính
toán là song song hóa quá trình ước tính mật độ hàm hạt
nhân trên mạng máy tính, trên CPU hoặc GPU. Trong
nghiên cứu [21], Lukasik đã đề xuất sử dụng thư viện
giao thức truyền thông điệp (MPI) để song song hóa việc
ước lượng hàm mật độ xác suất. Năm 2013, Michailidis
và Margaritis đã song song hóa ước lượng mật độ hàm
hạt nhân trên các khung lập trình khác nhau như Pthreads,
OpenMP, Intel Cilk ++, Intel TBB và SWARM [22]. Cũng
trong năm 2013, họ tiếp tục song song hóa ước lượng hàm
mật độ hạt nhân trên nền tảng GPU CUDA [23]. Ưu điểm
của các phương pháp này là không làm thay đổi hiệu suất
phát hiện dị thường của các thuật toán. Tuy nhiên, độ phức
tạp tính toán PDF không thay đổi, vẫn là ( 푛2); thời gian
tính toán giảm do các phương pháp này đã chia tổng khối
lượng công việc làm nhiều phần và tính toán đồng thời.
71
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Qua quá trình nghiên cứu chúng tôi thấy rằng, trong công
thức tính mật độ xác suất, việc tìm những điểm ảnh trong
phạm vi băng thông để hàm hạt nhân khác 0 tiêu tốn rất
nhiều thời gian. Vì vậy, để giảm được thời gian tính toán,
chúng tôi phân các điểm ảnh về các nhóm cùng giá trị.
Mục đích là làm giảm số lượng dữ liệu cần tính toán, thay
vì phải tính toán toàn bộ 푛 điểm ảnh, chúng ta chỉ phải tính
toán trên nhóm các điểm ảnh, với nhỏ hơn rất nhiều
so với 푛. Trong tự nhiên, lớp phủ thực địa luôn có tính chất
phân lớp đối tượng, lớp phủ càng đồng nhất số lượng nhóm
càng ít. Bởi vậy, bước phân nhóm các điểm ảnh về cơ bản
làm giảm đáng kể số lượng điểm dữ liệu cần xét đến. Bước
tiếp theo, chúng tôi tổ chức dữ liệu theo cây Kd-tree đối
với dữ liệu chưa phân nhóm và dữ liệu sau phân nhóm để
tăng tốc độ tìm kiếm các điểm dữ liệu trong phạm vi băng
thông thỏa mãn hàm hạt nhân khác 0.
Phần tiếp theo của bài báo được cấu trúc như sau. Phần II
trình bày lý thuyết ước lượng mật độ phi tham số và thuật
toán để thực hiện việc ước lượng này. Phần III trình bày
phương pháp phân nhóm dữ liệu, xây dựng, tìm kiếm trên
cây Kd-tree và thuật toán để tính toán PDF khi dữ liệu đã
được nhóm và tổ chức vào cây Kd-tree. Phần IV trình bày
kết quả thực nghiệm trên ba loại ảnh (ảnh đa phổ 3 kênh
phổ, ảnh đa phổ 8 kênh và ảnh siêu phổ 224 kênh). Cuối
cùng là kết luận và tài liệu tham khảo.
II. ƯỚC LƯỢNG MẬT ĐỘ HẠT NHÂN
Phương pháp ước lượng mật độ xác suất phi tham số
trong đó công cụ chính là ước lượng mật độ hạt nhân (KDE)
đã được Rosenblatt công bố vào năm 1956 [24] và sau
đó được Parzen phát triển, công bố vào năm 1962 [25].
Bảng I
MỘT SỐ HÀM NHÂN ĐIỂN HÌNH [27]
Tên hàm nhân 퐾 ( ) Điều kiện
Uniform
1
2
| | ≤ 1
Hypercube 1 | | ≤ 1
2
Triangular 1 − | | | | ≤ 1
Epanechnikov
3
4
√
5
− 3 
2
20
√
5
| | ≤ √5
Quartic
15
16
(1 − 2)2 | | ≤ 1
Triweight
35
32
(1 − 2)3 | | ≤ 1
Tricube
70
81
(1 − | |3)3 | | ≤ 1
Gaussian
1√
2 
푒−
1
2 
2
Cosine
4
 표푠
( 
2
)
| | ≤ 1
Đối với dữ liệu một chiều, xét vector ngẫu nhiên x =
( 1, 2, . . . , 푛) của biến ngẫu nhiên x có 푛 phần tử. Điều
này có nghĩa rằng có 푛 quan sát của biến ngẫu nhiên x và
 푖 là quan sát thứ 푖 của biến ngẫu nhiên x. Khi đó, mật độ
hạt nhân của biến ngẫu nhiên x được ước lượng như sau:
 ˆ ( 푖) = 1
푛
∑푛
푗=1
1
ℎ 푗
퐾
(
 푖 − 푗
ℎ 푗
)
, 푖 = 1, 2, . . . , 푛, (1)
trong đó ˆ (·) được gọi là hàm mật độ xác suất (PDF), 퐾 ( )
được gọi là hàm nhân thỏa mãn điều kiện
∫ ∞
−∞ 퐾 ( ) ( ) = 1
và ℎ 푗 là hệ số tỷ lệ quyết định “khoảng rộng” của hàm nhân
hay còn gọi là băng thông. Thảo luận mở rộng về các thuộc
tính thống kê của ˆ (·) có thể được tìm thấy trong [26],
퐾 ( ) có thể là các hàm nhân điển hình do Hardle trình
bày trong [27] và được thể hiện trong bảng I.
Trong trường hợp dữ liệu có chiều, quan sát thứ 푖
của X = (x1, x2, . . . , x푛) là x푖 = ( 1푖 , 2푖 , . . . , 푖 ) , 푖 =
1, . . . , 푛, và công thức ước tính mật độ hạt nhân của dữ
liệu đa biến được định nghĩa trong [27] là:
 ˆ (x푖) = 1
푛
∑푛
푗=1
{∏ 
 =1
1
ℎ 
퐾
(
 푖 − 푗
ℎ 
)}
, 푖 = 1, 2, . . . , 푛. (2)
Đối với ảnh đa phổ và siêu phổ, dữ liệu thuộc dạng đa
biến, chúng tôi sử dụng công thức (2) để cài đặt thuật toán.
Không làm mất tính tổng quát, chúng tôi cố định băng
thông, đặt ℎ = ℎ1 = ℎ2 = · · · = ℎ với = 1, 2, . . . , .
Thuật toán 1 được viết giả lập theo ngôn ngữ lập trình
C để ước tính mật độ của dữ liệu đa biến theo phương
pháp tuần tự trên CPU, đây là thuật toán do Lukasik [21],
Michailidis và Margaritis [22, 23] xây dựng.
Trong thuật toán 1, X là dữ liệu ảnh đa phổ hoặc siêu
phổ được tổ chức thành một ma trận hai chiều từ nhiều
vector, chỉ số của chiều thứ nhất tương ứng với vị trí trong
không gian của các điểm ảnh, chiều thứ hai chứa dữ liệu
của các kênh ảnh tại vị trí đó, 푛 là tổng số điểm ảnh, là số
kênh phổ, ℎ là băng thông của hàm ước lượng mật độ, pdf
là vector lưu trữ mật độ xác suất của các điểm ảnh. Trong
thuật toán 1, hàm Kernel được thiết kế riêng bởi những
thuật toán phía sau đều phải sử dụng đến nó. Trong hàm
Kernel, x푖 là vector giá trị của điểm ảnh cần tính mật độ,
x 푗 là vector giá trị của điểm ảnh bất kỳ nằm trong băng
thông, 퐾 ( ) là một trong những hàm đã nêu trong bảng I.
Thuật toán 1 có độ phức tạp tính toán là ( 푛2).
III. TĂNG TỐC ĐỘ ƯỚC LƯỢNG HÀM MẬT ĐỘ
Như phân tích trong phần II, thuật toán 1 có độ phức
tạp tính toán là ( 푛2). Đây là độ phức tạp tính toán theo
hàm số mũ. Trong phần thực nghiệm của nghiên cứu [20],
tác giả sử dụng 100.000 điểm dữ liệu để kiểm nghiệm và
thời gian tính toán là 4 ngày. Trên thực tế, thời gian chúng
tôi tính toán PDF cho một ảnh màu RGB 11.373.204 điểm
72
Tập 2019, Số 2, Tháng 12
Thuật toán 1: Thuật toán ước lượng mật độ hạt
nhân [21–23]
input: Ma trận các điểm ảnh , số điểm ảnh 푛, số
kênh phổ , băng thông ℎ
output: Mật độ xác suất của các điểm ảnh pdf
1 for 푖 ← 0 to 푛 − 1 do
2 푠 _ 푒 ← 0;
3 for 푗 ← 0 to 푛 − 1 do
4 sum_ker← sum_ker + Kernel( 푖 , 푗 , , ℎ);
5  ... rd màn hình NVIDIA GeForce GTX 1070
Ti, 2432 nhân CUDA, 8GB RAM, tốc độ xử lý 1683 MHz.
Các thuật toán AL1, AL5, AL6 và AL7 chạy trên một nhân
và một luồng của CPU.
Trong trường hợp dữ liệu đầu vào của các thuật toán là
KDT, kết quả được thể hiện trên hình 8. Rõ ràng rằng, khi
dữ liệu được tổ chức vào cây Kd-tree, thời gian tính toán
PDF đã giảm đi đáng kể so với trường hợp tính toán PDF
khi dữ liệu chưa qua giai đoạn tiền xử lý (AL1). Cụ thể:
trên ảnh 3 kênh phổ thời gian đã giảm đi 404.886s tương
đương với việc giảm đi 22,25% thời gian tính toán; trên
Hình 8. Biểu đồ hiển thị thời gian chạy của thuật toán tính toán
PDF khi dữ liệu chưa qua giai đoạn tiền xử lý (AL1), tính toán
song song trên CPU (Intel TBB), tính toán song song trên GPU
(GPU CUDA) và dữ liệu đã được tổ chức vào cây Kd-tree (AL6).
ảnh 8 kênh phổ, thời gian đã giảm đi 8.769s tương đương
với việc giảm đi 79,44% thời gian tính toán; trên ảnh 224
kênh phổ, thời gian tính toán đã giảm đi 537s tương đương
với việc giảm đi 96,41% thời gian tính toán. Trên ảnh ba
kênh phổ, thuật toán AL6 có thời gian tính toán lớn hơn
thuật toán Intel TB 10.236s, tương đương với thời gian tính
toán của LA6 nhiều hơn Intel TBB 0,73%. Trên hai ảnh 8
kênh phổ và 224 kênh phổ thời gian tính toán của AL6 đã
nhanh hơn Intel TBB lần lượt là: 6.783s và 438s, tương
đương với việc giảm đi 74,93% và 95,63% thời gian tính
toán. Trong trường hợp so sánh về thời gian tính toán giữa
AL6 và GPU CUDA thì AL6 đều có thời gian tính chậm
hơn GPU CUDA trên cả ba ảnh. Tuy nhiên có sự khác biệt,
AL6 tính toán chậm hơn GPU CUDA rõ rệt trên ảnh ba
kênh phổ, trên ảnh 8 kênh phổ khoảng cách đã được thu
hẹp, trên ảnh 224 kênh phổ chênh lệch không nhiều (AL6
chỉ chậm hơn GPU CUDA 6,64s). Như vậy, áp dụng cây
Kd-tree để quản lý dữ liệu trong giai đoạn tiền xử lý trước
khi tính toán PDF sẽ hiệu quả hơn đối với những ảnh có
số kênh phổ lớn.
Đối với trường hợp nhóm các điểm ảnh có phổ trùng
nhau, chúng tôi chỉ áp dụng cho ảnh 3 kênh phổ. Không
áp dụng cho loại ảnh 8 kênh phổ và 224 kênh phổ bởi tổ
hợp màu của loại ảnh 8 hoặc 224 kênh phổ là một số rất
lớn vượt khỏi khả năng quản lý của máy tính và không
thể áp dụng được cho thuật toán 2. Nếu sử dụng thuật
toán nhóm thông thường sẽ tốn rất nhiều thời gian do đó
không khả thi. Nhìn vào bảng II và hình 9 ta thấy, thời
gian tính toán PDF của ảnh 3 kênh phổ khi dữ liệu đã được
79
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Hình 9. Biểu đồ hiển thị thời gian chạy của thuật toán tính toán PDF khi dữ liệu chưa qua giai đoạn tiền xử lý (AL1), tính toán song
song trên CPU (Intel TBB), tính toán song song trên GPU (GPU CUDA), dữ liệu đã được nhóm (AL5) và dữ liệu đã được nhóm sau
đó tổ chức trên cây Kd-tree (AL7).
nhóm đã giảm tới 1.819.482s tương đương với việc giảm
đi 99,98% thời gian tính toán so với trường hợp tính toán
PDF khi dữ liệu chưa qua giai đoạn tiền xử lý (AL1). Lý do
giảm thời gian tính toán PDF là quá trình nhóm các điểm
ảnh có phổ trùng nhau đã làm giảm dữ liệu cần tính toán.
Cụ thể, việc này đã giảm số lượng dữ liệu cần tính toán
từ 3396 × 3349 = 11.373.204 điểm ảnh xuống còn 65.607
nhóm điểm ảnh, dẫn đến giảm được 99,4% khối lượng dữ
liệu cần tính toán. Thời gian tính toán của thuật toán AL5
nhanh hơn thuật toán Intel TBB 6.107 lần, nhanh hơn thuật
toán GPU CUDA 94 lần.
Dữ liệu sau khi nhóm tiếp tục đưa vào cây Kd-tree để
quản lý, thời gian tính toán PDF trên ảnh 3 kênh phổ chỉ
còn là 21,19s. So sánh với trường hợp tính toán PDF khi
dữ liệu chưa qua giai đoạn tiền xử lý (thời gian tính toán
là 1.819.712s, tương đương với hơn 21 ngày tính toán)
dữ liệu GRP-KDT đưa vào tính toán PDF này đã giảm
đi 99,999% thời gian tính toán. Nhìn vào bảng II và hình 9
ta thấy AL7 hoàn toàn vượt trội so với thuật toán Intel
TBB và GPU CUDA, cụ thể, AL7 đã nhanh hơn Intel
TBB 66.285 lần và nhanh hơn GPU CUDA 1.020 lần.
3. Đánh giá về độ phức tạp tính toán
Độ phức tạp tính toán của thuật toán AL1 là ( 푛2),
của thuật toán AL5 là ( 2), của thuật toán AL6 là
 ( 푛(√푛+ 푖)) và của thuật toán AL7 là ( (√ + 푖)).
Rõ ràng độ phức tạp tính toán của thuật toán AL6 và AL7
luôn luôn nhỏ hơn thuật toán AL1. Đối với thuật toán AL5,
trong trường hợp xấu nhất = 푛 (không có bất kỳ điểm
ảnh nào có phổ trùng nhau) thì hai thuật toán này có độ
phức tạp tính toán tương đương nhau. Tuy nhiên, điều này
rất khó xảy ra ngoài thực tế bởi các ảnh chụp trong tự nhiên
các lớp phủ thực địa luôn có tính chất phân lớp đối tượng,
lớp phủ càng đồng nhất (chụp trên biển, trên rừng, hoang
mạc, sa mạc, v.v.) thì càng nhỏ dẫn đến độ phức tạp tính
toán của AL5 nhỏ hơn AL1.
Đối với phương pháp biến đổi Fourier nhanh do Silver-
man để xuất [19], độ phức tạp tính toán là ( log ),
phương pháp biến đổi Gauss nhanh do Elgamall và các
cộng sự đề xuất [20] có độ phưc tạp tính toán là ( + ),
trong đó = 푛 là kích thước dữ liệu và là số lượng
điểm dữ liệu cần tính PDF. Ứng dụng trong trường hợp tính
toán PDF cho các điểm ảnh thì = . Rõ ràng thuật toán
AL6 có độ phức tạp tính toán lớn hơn cả hai phương pháp
biến đổi nhanh này do ( 푛(√푛 + 푖)) > ( log ) >
 ( + ). Cả hai phương pháp biến đổi Fourier nhanh
và biến đổi Gauss nhanh có độ phức tạp tính toán phụ
thuộc hoàn toàn vào kích thước dữ liệu, thuật toán AL5 và
AL7 có độ phức tạp tính toán phụ thuộc vào cấu trúc, nội
dung của ảnh. Trong phần thực nghiệm với ảnh ba kênh
phổ ở trên cho ta thấy, trong khi 푛 = 11.373.204 thì chỉ
bằng 65.607, có nghĩa là ≈ 0.006푛, dẫn đến độ phức tạp
tính toán của AL5 và AL7 nhỏ hơn rất nhiều so với phương
pháp biến đổi Fourier nhanh và biến đổi Gauss nhanh.
V. KẾT LUẬN
Trong công tác tìm kiếm cứu nạn, thời gian phản ứng
mang ý nghĩa hết sức quan trọng. Việc rút ngắn thời gian
xử lý dữ liệu và ra quyết định đồng nghĩa với việc giảm
phí tổn tài chính, sức lực, tinh thần và nâng cao khả năng
sống sót của nạn nhân. Trong nghiên cứu này, chúng tôi
đề xuất phương pháp để làm giảm thời gian phát hiện các
điểm dị thường trên ảnh siêu phổ và đa phổ (những điểm
ảnh dị thường này có thể là mục tiêu cần tìm kiếm hoặc
những dấu hiệu phục vụ cho công tác tìm kiếm cứu nạn).
Đầu tiên là giai đoạn tiền xử lý dữ liệu với mục đích làm
giảm số lượng dữ liệu cần tính toán (sử dụng nhóm các
điểm ảnh có các kênh phổ trùng nhau) và tổ chức lại dữ
liệu một cách hợp lý để phục vụ cho quá trình tính toán
PDF (tổ chức dữ liệu vào cây Kd-tree). Sau đó, 3 cấu trúc
dữ liệu trong giai đoạn tiền xử lý GRP, KDT và GRP-KDT
được sử dụng để tính toán PDF.
80
Tập 2019, Số 2, Tháng 12
Độ phức tạp về tính toán trong giai đoạn tiền xử lý dữ
liệu khi nhóm những điểm ảnh có các kênh phổ trùng nhau
là ( 푛), xây dựng Kd-tree là (푛 log 푛). Trong giai đoạn
tính toán PDF, độ phức tạp tính toán của các hàm PDF khi
dữ liệu đã được nhóm là ( 2), trong đó là số nhóm
các điểm ảnh có các kênh phổ trùng nhau. Trong rất nhiều
trường hợp, nhỏ hơn rất nhiều so với 푛 nên thời gian
tính toán PDF cũng giảm đi tương ứng. Độ phức tạp tính
toán khi dữ liệu đầu vào đã được quản lý bởi Kd-tree là
 ( 푛(√푛 + 푖)), do 푖 nhỏ hơn 푛 rất nhiều nên thời gian
tính các hàm PDF cũng giảm đi tương ứng. Độ phức tạp
tính toán các hàm PDF khi dữ liệu đã được nhóm và tổ
chức trên cây Kd-tree là ( (√ + 푖)).
Kết quả kiểm nghiệm trên ba loại ảnh (ảnh đa phổ 3
kênh, ảnh đa phổ 8 kênh và ảnh siêu phổ 224 kênh) đã
vượt ngoài mong đợi của nhóm tác giả. Đặc biệt là đối với
ảnh màu, đây là những ảnh thường được thu chụp từ thiết
bị bay không người lái hoặc có người lái và được ứng dụng
rộng rãi trong công tác tìm kiếm cứu nạn.
LỜI CẢM ƠN
Nghiên cứu này được tài trợ kinh phí bởi đề tài nghiên
cứu khoa học cấp quốc gia mã số VT-UD.04/16-20 thuộc
Chương trình KHCN vũ trụ của Bộ khoa học và công nghệ
Việt Nam. Nhóm tác giả trân trọng cảm ơn sự ủng hộ và
đồng hành của Ban chủ nhiệm Chương trình KHCN vũ trụ.
TÀI LIỆU THAM KHẢO
[1] T. Bolukbasi, P. Tran, “Outline Color Identification For
Search And Rescue,” Technical Report of Department of
Electrical and Computer Engineering, Boston University,
no. ECE-2012-07, 2012.
[2] M. B. Salem, K. S. Ettabaa, M. A. Hamdi, “Anomaly
detection in hyperspectral imagery: An overview,” in In-
ternational Image Processing, Applications and Systems
Conference, pp. 1–6, 2015.
[3] I. S. Reed and X. Yu, “Adaptive Multiple-Band CFAR
Detection of an Optical Pattern with Unknown Spectral
Distribution,” IEEE Transactions on Acoustics, Speech, and
Signal Processing, vol. 38, no. 10, pp. 1760–1770, 1990.
[4] T. E. Smetek, K. W. Bauer, “Finding hyperspectral anoma-
lies using multivariate outlier detection,” IEEE Aerospace
Conference, pp. 1–24, 2007.
[5] D. Manolakis, D. Marden, G. A. Shaw, “Hyperspectral im-
age processing for automatic target detection applications,”
Lincoln Laboratory Jour., vol. 14, no. 1, pp. 79–116, 2003.
[6] D. C. Borghys, V. Achard, S. R. Rotman, N. Gorelik, C.
Perneel, E. Scwheicher, “Hyperspectral anomaly detection:
a comparative evaluation of methods,” XXXth URSI Gen-
eral Assembly and Scientific Symp., pp. 1–4, 2011.
[7] T. Marshall, L. N. Perkins, “Color Outline Detection For
Search And Rescue,” Technical Report of Department of
Electrical and Computer Engineering, Boston University,
no. ECE-2015-01, 2015.
[8] M. Ramachandran, W. Moik, Outline Color Identification
For Search And Rescue, Technical Report of Department of
Electrical and Computer Engineering, Boston University,
No. ECE-2013-03, 2013.
[9] D. K. Hoai, N. V. Phuong, “Anomaly Color Detection
on UAV Images for Search and Rescue works,” in 2017
9th International Conference on Knowledge and Systems
Engineering, pp. 287–291, 2017.
[10] S. Khazai, S. Homayouni, A. Safari, and B. Mojaradi,
“Anomaly Detection in Hyperspectral Images Based on an
Adaptive Support Vector Method,” IEEE Geoscience and
Remote Sensing Letters, vol. 8, no. 4, pp. 646–650, 2011.
[11] A. Banerjee, P. Burlina, and C. Diehl, “A support vector
method for anomaly detection in hyperspectral imagery,”
IEEE Transactions on Geoscience and Remote Sensing,
vol. 44, no. 8, pp. 2282–2291, Aug. 2006.
[12] D. W. J. Stein, S. G. Beaven, L. E. Ho, E. M. Winter,
A. P. Schaum, and A. D. Stocker, “Anomaly detection
from hyperspectral imagery,” IEEE Signal Process. Mag.,
vol. 19, no. 1, pp. 58–69, 2002.
[13] S. Matteoli, T. Veracini, M. Diani, and G. Corsini, “Models
and Methods for Automated Background Density Estima-
tion in Hyperspectral Anomaly Detection,” IEEE Transac-
tions on Geoscience and Remote Sensing, vol. 51, no. 5,
pp. 2837–2852, 2013.
[14] P. Gurram and H. Kwon, “Support-Vector-Based Hyper-
spectral Anomaly Detection Using Optimized Kernel Pa-
rameters,” IEEE Geoscience and Remote Sensing Letters,
vol. 8, pp. 1060–1064, 2011.
[15] C.-I. Chang and S.-S. Chiang, “Anomaly detection and clas-
sification for hyperspectral imagery,” IEEE Trans. Geosci.
Remote Sensing, vol. 40, no. 6, pp. 1314–1325, 2002.
[16] T. Veracini, S. Matteoli, M. Diani, and G. Corsini, “Non-
parametric Framework for Detecting Spectral Anomalies
in Hyperspectral Images,” IEEE Geoscience and Remote
Sensing Letters, vol. 8, no. 4, pp. 666–670, 2011.
[17] S. Matteoli, T. Veracini, M. Diani and G. Corsini, “Back-
ground Density Nonparametric Estimation With Data-
Adaptive Bandwidths for the Detection of Anomalies in
Multi-Hyperspectral Imagery,” IEEE Geoscience and Re-
mote Sensing Letters, vol. 11, pp. 163–167, 2014.
[18] C. Zhao, X. Wang, and G. Zhao, “Detection of hyperspec-
tral anomalies using density estimation and collaborative
representation,” Remote Sensing Letters, vol. 8, no. 11,
pp. 1025–1033, 2017.
[19] B. Silverman, “Algorithm AS 176: Kernel density estima-
tion using the fast Fourier transform,” Applied Statistics,
vol. 31, no. 1, pp. 93–99, 1982.
[20] A. Elgammal, R. Duraiswami and L.S. Davis, “Efficient
Kernel density estimation using the Fast Gauss Transform
with applications to color modeling and tracking,” IEEE
Transactions on Pattern Analysis and Machine Intelligence,
vol. 25, pp. 1499–1504, 2003.
[21] S. Lukasik, "Parallel computing of kernel density estimates
with MPI," in 7th International Conference on Computa-
tional Science, pp. 726–733, 2007.
[22] P. D. Michailidis, and K. G. Margaritis, “Parallel Comput-
ing of Kernel Density Estimation with Different Multi-core
Programming Models,” in 21st Euromicro International
Conference on Parallel, Distributed, and Network-Based
Processing, pp. 77–85, 2013.
[23] P. D. Michailidis, K. G. Margaritis, “Accelerating Kernel
Density Estimation on the GPU Using the CUDA Frame-
work,” Applied Mathematical Sciences, vol. 7, no. 30,
pp. 1447–1476, 2013.
[24] M. Rosenblatt, “Remarks on Some Nonparametric Esti-
mates of a Density Function,” Annals of Mathematical
Statistics, vol. 27, no. 3, pp. 832–837, 1956.
[25] E. Parzen, “On Estimation of a Probability Density Func-
tion and Mode,” Annals of Mathematical Statistics, vol. 33,
pp. 1065–1076, 1962.
81
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
[26] L. Devroye and L. Gyorfi, Nonparametric Density Estima-
tion: The L1 View, Wiley, New York, 1985.
[27] W. Hardle, A. Werwatz, M. Muller and S. Sperlich,
Nonparametric Density Estimation, In: Nonparametric
and Semiparametric Models, Springer Series in Statistics,
pp. 39-83, 2004.
[28] J. L. Bentley, “Multidimensional Binary Search Trees Used
for Associative Searching,” Communications of the ACM,
vol. 18, no. 9, pp. 509-517, 1975.
[29] H. M. Kakde, “Range Searching using Kd Tree,”
2005. References, Aug. 12, 2019. [Online]. Avail-
able: 
1.1.122.5818.
[30] P. Trebunˇa, J. Halcˇinová, “Experimental Modelling of the
Cluster Analysis Processes,” Procedia Engineering 48,
pp. 673–678, 2012.
[31] M. Harris, "Optimizing parallel reduction in CUDA,"
Nvidia developer technology 2, no. 4, p. 70, 2007. [Online].
Available: https://developer.download.nvidia.com/assets/
cuda/files/reduction.pdf.
[32] Dstl Satellite Imagery Feature Detection. [Online].
Available: https://www.kaggle.com/c/dstl-satellite-imagery-
feature-detection. [Accessed: Oct 25, 2019].
[33] Hyperspectral Remote Sensing Scenes. [Online]. Available:
Remote_Sensing_Scenes. [Accessed: Oct 25, 2019].
Nguyễn Văn Phương tốt nghiệp Đại học
và Thạc sĩ tại Học viện Kỹ thuật Quân sự
năm 2003 và 2009. Hiện tại là nghiên cứu
sinh tại Khoa Công nghệ Thông tin cũng
tại Học viện Kỹ thuật Quân sự. Lĩnh vực
nghiên cứu bao gồm: GIS, xử lý ảnh viễn
thám quang học.
Đào Khánh Hoài nhận học vị Tiến sĩ năm
2005. Hiện công tác tại Học viện Kỹ thuật
Quân sự. Lĩnh vực nghiên cứu bao gồm:
GIS, xử lý ảnh vệ tinh, UAV, đo ảnh và thị
giác máy tính.
Tống Minh Đức tốt nghiệp Đại học tại Học
viện Kỹ thuật Quân sự năm 2000, nhận học
vị Tiến sĩ tại Trường Đại học Tổng hợp Kỹ
thuật Điện (LETI), Nga năm 2007. Hiện là
giảng viên tại Khoa Công nghệ Thông tin
của Học viện Kỹ thuật Quân sự. Lĩnh vực
nghiên cứu bao gồm: xử lý ảnh, nhận dạng
đối tượng, an toàn bảo mật thông tin.
82