Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00017
ĐỀ XUẤT TẬP ĐẶC TRƯNG TRONG PHÂN LỚP MÔ HÌNH 3D
Nguyễn Văn Tảo, Nông Thị Hoa
Trường ĐH Công nghệ thông tin và Truyền thông, ĐH Thái Nguyên
nvtao@ictu.edu.vn, nthoa@ictu.edu.vn
TÓM TẮT: Việc phân lớp mô hình 3D để lưu trữ trong CSDL giúp tăng tốc độ truy vấn các mô hình khi thiết kế các cảnh ảo trong
các sản phẩm điện ảnh và game. Do đó, phân lớp các mô hình 3D là một nhiệm vụ cần thiết. Các nghiên cứu trước đây đã đề xuất
tập đặc trưng với số lượng đặc trưng nhiều từ 250 đến 800 và thường cần các tính toán phức tạp để rút trích đặc trưng. Vì vậy, thời
gian phân lớp cho mẫu mới sẽ dài do phải tính toán với nhiều đặc trưng. Trong bài báo này, chúng tôi đề xuất tập đặc trưng ngắn
gọn và lựa chọn mô hình Support Vector Machine để phân lớp. Các đặc trưng nằm trong tập đặc trưng thu được do áp dụng kỹ
thuật phân tích thành phần chính trên mô hình 3D. Tập đặc trưng gồm 3 giá trị riêng của ba trục cơ bản của mô hình 3D. Do
Support Vector Machine có thể được huấn luyện cho đến khi đạt cực tiểu lỗi nên Support Vector Machine phân lớp hiệu quả nếu
chọn tập huấn luyện tốt. Hơn nữa, vấn đề overfitting được giảm khi chọn tập huấn luyện vừa đủ và có tính tổng quát hóa cao. Vì
vậy, chúng tôi lựa chọn Support Vector Machine để phân lớp dựa trên các đặc trưng đề xuất. Các thực nghiệm được làm với tập dữ
liệu chuẩn Pinceton Shape Brenchmark về phân lớp các hình dạng 3D. Chúng tôi tiến hành thực nghiệm phân lớp trên 6 lớp về các
phương tiện giao thông. Kết quả thực nghiệm cho thấy việc dùng Support Vector Machine kết hợp với tập đặc trưng đề xuất cho kết
quả phân lớp tốt hơn các kỹ thuật được so sánh.
Từ khóa: Phân lớp, trích chọn đặc trưng, mô hình 3D, Support Vector Machine, computer vision.
I. GIỚI THIỆU
Ngày nay, các mô hình 3D ngày càng nhiều và được ứng dụng trong thiết kế các cảnh ảo ở nhiều lĩnh vực như thiết
kế nội thất, sản xuất phim ảnh và bảo tồn di sản văn hoá. Sự tăng nhanh các mô hình 3D đòi hỏi cần có cách quản lý, lưu
trữ các mô hình 3D hợp lý để có thể truy vấn nhanh các mô hình 3D. Vì vậy, các mô hình 3D cần được phân lớp trước khi
lưu trữ trong CSDL và phân lớp các mô hình 3D là một nhiệm vụ cần thiết.
Trong các nghiên cứu trước đây, phân lớp mô hình 3D có thể chia thành hai nhóm chính gồm: (i) xây dựng bộ
phân lớp mới dùng với các bộ mô tả đặc trưng có sẵn [2] [3] [4] [5], và (ii) đề xuất tập các đặc trưng và dùng bộ phân lớp
có sẵn để phân lớp [5] [7] [8]. Một số ít các nghiên cứu là đề xuất cả tập đặc trưng và bộ phân lớp mới [1]. Với hướng đề
xuất tập các đặc trưng mới, số lượng đặc trưng nhiều (từ 250 đến 800) và các đặc trưng thường được tính toán bằng các
công thức toán học phức tạp [2] [5] [6] [7] như biến đổi cosin rời rạc, biến đổi Fourier, biến đổi Hough,…. Vì vậy, thời
gian phân lớp sẽ dài do phải tính toán với nhiều đặc trưng. Trong bài báo này, chúng tôi đề xuất tập đặc trưng ngắn gọn và
lựa chọn mô hình Support Vector Machine để phân lớp. Các đặc trưng nằm trong tập đặc trưng thu được do áp dụng kỹ
thuật phân tích thành phần chính trên mô hình 3D. Tập đặc trưng gồm 3 giá trị riêng của ba trục cơ bản của mô hình 3D.
Do Support Vector Machine có thể được huấn luyện cho đến khi đạt cực tiểu lỗi nên Support Vector Machine phân lớp
hiệu quả nếu chọn tập huấn luyện tốt. Hơn nữa, vấn đề overfitting có thể được hạn chế khi chọn tập huấn luyện có tính
tổng quát hóa cao. Vì vậy, chúng tôi lựa chọn Support Vector Machine để phân lớp dựa trên các đặc trưng đề xuất. Các
thực nghiệm được làm với tập dữ liệu chuẩn Pinceton Shape Brenchmark về phân lớp các hình dạng 3D. Chúng tôi tiến
hành thực nghiệm phân lớp các phương tiện giao thông bao gồm 6 lớp: máy bay, tàu thủy, thuyền buồm, ô tô, tàu hỏa,
khinh khí cầu. Kết quả thực nghiệm cho thấy việc dùng Support Vector Machine kết hợp với tập đặc trưng đề xuất cho kết
quả phân lớp tốt hơn các kỹ thuật được so sánh.
Bài báo chia thành 6 phần. Phần I giới thiệu chung Phần II trình bày về các nghiên cứu liên quan. Phần III giới
thiệu các kiến thức cơ bản về biểu diễn mô hình 3D và Support Vector Machine. Phần IV trình bày tập đặc trưng đề xuất
vfa lý do lựa chọn bộ phân lớp. Phần V trình bày và phân tích kết quả thực nghiệm. Một số kết luận và hướng phát triển
được nêu ra trong Phần IV.
II. CÁC NGHIÊN CỨU LIÊN QUAN
Các nghiên cứu về đề xuất tập đặc trưng dùng trong phân lớp mô hình 3D có thể chia thành hai nhóm chính gồm
(i) đề xuất tập các đặc trưng mới và (ii) lựa chọn một số đặc trưng trong các bộ mô tả có sẵn về mô hình 3D. Một số ít các
nghiên cứu là dùng mạng nơron học sâu nên không cần rút trích đặc trưng.
Trong nhóm nghiên cứu thứ nhất, một số nghiên cứu mới nhất đã được công bố. Z. Shu và đồng nghiệp [1] đã đưa
ra bộ mô tả đặc trưng mới - PTI (Principal Thickness Images). Các đặc trưng này được thể hiện qua ba ảnh mức xám thể
hiện độ dày của các bề mặt bao quanh mô hình khi chiếu mô hình theo 3 hướng PTI1, PTI2, PTI3 do nhóm đề xuất. Nhóm
tác giả cũng đã cải tiến bộ phân lớp dựa trên biểu diễn nhân thưa (kernel sparse representation-based classification) của
mô hình 2D thành bộ phân lớp cho mô hình 3D ko cứng (non-girid 3D model). Ban đầu, rút ra ba véctơ đặc trưng thể
hiện biểu đồ mức xám của các ảnh mức xám thu được do phép chiếu theo 3 hướng của PTI. Sau đó đưa 3 véctơ này vào
tính mức độ thành viên của mô hình vào một lớp thông qua một hàm tối ưu. Các thực nghiệm được làm trên bộ dữ liệu
SHREC’11 và phân lớp các mô hình ở nhiều lớp khác nhau. S. P. Foliguet và đồng nghiệp [5] đưa ra khung công việc để
- 130 ĐỀ XUẤT TẬP ĐẶC TRƯNG DÙNG TRONG PHÂN LỚP MÔ HÌNH 3D
phân lớp mô hình từng phần và tổng thể. Đầu tiên, rút trích các đặc trưng của mô hình theo bộ mô tả hình dạng tổng thể
gồm các đặc trưng sau: Cord histograms, Extended Gaussian images, Complex Extended Gaussian images, 3D Hough
transform, Spherical harmonic representation. Sau đó, dùng SVM kết hợp với học tích cực để phân lớp của các mô hình.
Tiếp theo, cải tiến việc phân lớp thông qua việc đối sánh hình dạng theo từng phần của mô hình dựa trên bộ mô tả cục bộ.
Việc phân chia mô hình thành từng phần dựa theo cách đường cong (đỉnh lồi) trên mô hình. Các đặc trưng mô tả cục bộ
gồm: Extended Gaussian images, Complex Extended Gaussian images, Cord1D, Cord2D, 2D curvature histograms. Các
thực nghiệm được làm trên bộ dữ liệu Princeton Shape và EROS-3D để phân lớp các mô hình ở nhiều lớp khác nhau. L.
Biao và đồng nghiệp [2] đưa ra mô hình phân lớp tốt dựa vào sự kết hợp các đồ thị. Đầu tiên, tiến hành rút trích các đặc
trưng theo một số bộ mô tả mô hình có sẵn gồm 2D Polar-Fourier, 2D Zernike moments và 2D Krawthcouk moments.
Sau đó, xây dựng đồ thị dựa trên đặc trưng của các bộ mô tả. Cuối cùng, dùng phương pháp Label Propagation để phân
lớp thông qua việc tính hàm thành viên của mô hình vào các lớp. Các thực nghiệm được làm trên bộ dữ liệu Princeton
shape benchmark và SHREC'09.
Trong nhóm nghiên cứu thứ hai, các tác giả dùng các bộ mô tả khác nhau và kết hợp với một số kỹ thuật cắt tỉa để
giảm số lượng đặc trưng. A. Kassimi và O.E. Beqqali [5] trình bày một tiếp cận mới để phân lớp mô hình dựa vào mô tả
cấu trúc và các khái niệm về ngữ nghĩa. Hai tác giả chọn Shape Indexes làm đặc trưng để mô tả tốt hơn các khái niệm và
ngữ nghĩa của mô hình. Shape Indexes gồm các thông tin Sphericity, Compactness, Convexity, Elongation. Việc phân lớp
gồm ba bước sau: Gắn nhãn về khái niệm cho các mô hình bằng việc dùng thuật toán K-mean dựa trên các Shape Indexes;
Phân lớp các mô hình dựa vào nhãn khái niệm ở bước trước bằng thuật toán K láng riềng gần nhất kết hợp với khoảng
cách Euclid. Lược đồ mô tả (ontology) gồm các quan hệ không gian, các chỉ số hình dạng và các thước đo được xây dựng
để đo sự tương đồi giữa các mô hình thông qua với khoảng cách Euclid. Ưu điểm của nghiên cứu này là mô hình có cả
đặc trưng mức cao và đặc trưng mức thấp. Các thực nghiệm được làm trên bộ dữ liệu Princeton Shape để truy vấn các mô
hình trong cơ sở dữ liệu. L. Zongmin và đồng nghiệp [7] đưa ra bộ phân lớp phân cấp để phát hiện ngữ nghĩa của mô
hình. Xuất phát từ các đặc trưng ban đầu của mô hình, nhóm thực hiện giảm số chiều để thu được các đặc trưng nổi bật
bằng việc dùng mạng Radial Basis Function (RBF) với Kernel Principal Component Analysis và Kernel Local Fisher
Discriminant Analysis. Sau đó, dùng phân lớp SVM để phân lớp trên các các đặc trưng nổi bật. Các thực nghiệm được
làm trên bộ dữ liệu Princeton Shape để phân lớp các mô hình ở nhiều lớp khác nhau. H. Yuesheng, Y.Y. Tang [8] đưa ra
một phương thức để tính toán các dấu hiệu hình dạng và đo sự khác biệt của các mô hình. Nhóm đã chọn sự phân bố hình
dạng Osadas để rút ra tập đặc trưng theo bộ mô tả 2D. Bộ mô tả 2D này hình thành ra biểu đồ histogram của khoảng cách
và các góc của cặp điểm trên bề mặt mô hình. Sau đó, dùng SVM với nhân dạng Poly để phân lớp trên các đặc trưng. Việc
huấn luyện được làm nhiều lần để chọn ra nhân và các tham số phù hợp cho SVM. Các thực nghiệm được làm trên bộ dữ
liệu tự thu thập trên Internet để chứng minh tính hiệu quả của phương thức đề xuất.
Hai nghiên cứu sau đây dùng khả năng học của mạng nơron để tránh việc phải trích chọn đặc trưng. Trong nghiên
cứu [3], J. Y. Gwak dùng mạng nơron tiến hóa có 6 tầng để không phải rút trích đặc trưng của mô hình và cực tiểu lỗi dự
đoán. Tác giả phân tích kỹ cấu trúc và xử lý của từng tầng mạng. Hơn nữa, các thông tin mạng cần học trong quá trình
huấn luyện cũng được phân tích rõ nên dữ liệu huấn luyện được chuẩn bị phong phú và số lượng lớn. Ưu điểm của nghiên
cứu này là xác định được tư thế của mô hình. Các thực nghiệm được làm trên bộ dữ liệu ShapeNet và phân lớp các mô
hình ở nhiều lớp khác nhau. Q. Fei-wei và đồng nghiệp [4] đưa ra bộ phân lớp các mô hình 3D CAD dựa trên mạng nơ-
ron học sâu theo cách phân loại các bộ phận của máy móc. Đầu tiên, nhóm tác giả phân tích của tri thức về phân lớp máy
móc của các kỹ sư. Sau đó, chọn một bộ mô tả LFD (light field descriptor) để rút trích các đặc trưng của mô hình. Đây là
bộ mô tả dựa vào các góc nhìn nên sẽ gần giống với cách nhận biết đối tượng của người. Nhóm đã chọn Zernike moments
để biểu diễn các ảnh 2D được lấy ra từ mô hình 3D. Tiếp theo, các đặc trưng được tiền xử lý và biểu diễn thành véctơ
nhiều chiều. Cấu trúc của mạng học sâu gồm 6 tầng với số nút của mỗi tầng là 3500-28-400-56-28-1. Nhiều chiến lược
học đã được áp dụng cho mạng để tìm ra các tham số học, trọng số của mạng, ngưỡng dừng học để tránh việc học quá
(overfitting). Các thực nghiệm được làm trên bộ dữ liệu tự thu thập trên Internet để chứng minh tính hiệu quả của cách
tiếp cận đề xuất.
III. CƠ SỞ LÝ THUYẾT
2.1. Biểu diễn mô hình 3D
2.2.1. Định dạng của file thể hiện mô hình 3D
Một file thể hiện mô hình 3D lưu trữ các thông tin về mô hình. Các thông tin này gồm:
Thông tin hình học để mô tả hình dạng;
Hình ảnh trên bề mặt gồm màu, mẫu nền, kiểu chất liệu;
Các cảnh gồm vị trí nguồn sáng, các camera và các đối tượng đi kèm;
Các chuyển động của mô hình.
Hiện nay, hàng trăm định dạng đang được sử dụng nên có một số định dạng trung gian được công bố để chuyển
đổi giữa các định dạng. Hai định dạng trung gian có tiếng là STL và COLLADA. Định dạng STL chỉ lưu các thông tin
hình học còn định dạng COLLADA lưu đầy đủ mọi thông tin.
- Nguyễn Văn Tảo, Nông Thị Hoa 131
2.1.2. Định dạng STL của mô hình 3D
STL là định dạng trung gian quan trọng nhất trong lĩnh vực in 3D, tạo mẫu nhanh và sản xuất dựa vào sự trợ giúp
của máy tính. Định dạng này mô tả xấp xỉ bề mặt đối tượng bằng một lưới các tam giác bao quanh mô hình. Mỗi một tam
giác có các thông tin: tọa độ của 3 đỉnh và một véctơ đơn vị vuông góc với bề mặt được tạo bởi các cạnh của tam giác.
File STL ở dạng ASCII có cấu trúc như sau:
solid
facet normal nx ny nz
outer loop
vertex v1x v1y v1z
vertex v2x v2y v2z
vertex v3x v3y v3z
endloop
endfacet
endsolid
Trong đó, các khai báo về một tam giác sẽ xuất hiện nhiều hay ít phụ thuộc vào số lượng tam giác bao phủ bề mặt
mô hình.
File STL có một số quy tắc riêng bao gồm:
Quy tắc đỉnh: mỗi tam giác phải có hai đỉnh chung với tam giác lân cận;
Quy tắc hướng: hướng của mặt là hướng ra ngoài mô hình và các cạnh được liệt kê theo hướng ngược kim
đồng hồ;
Quy tắc octant tích cực: tọa độ của các đỉnh tam giác đều phải là dương;
Luật sắp xếp tam giác: các tam giác xuất hiện theo thứ tự tăng giá trị của trục Z.
2.2. Support Vector Machine
Support Vector Machine (SVM) là một kỹ thuật học máy để giải các bài toán phân lớp và dự đoán giá trị. SVM tìm
một siêu phẳng tối ưu mà cực đại hóa khoảng cách giữa các lớp [9]. Cho một tập huấn luyện, mỗi mẫu chỉ thuộc về một
trong hai lớp. Thuật toán huấn luyện của SVM xây dựng một mô hình để gán nhãn lớp cho các mẫu mới. SVM xem các
mẫu là các điểm trong không gian và ánh xạ các mẫu vào các lớp dựa vào đường biên ngăn cách giữa hai lớp. Một mẫu
mới được dự đoán thuộc về một lớp dựa vào vị trí của mẫu so với đường biên.
2.2.1. SVM tuyến tính
Cho tập huấn luyện có n điểm ở dạng sau: ⃗⃗⃗⃗ ⃗⃗⃗⃗ với nhận giá trị +1 hoặc −1. Mỗi giá trị biểu thị
lớp của điểm ⃗⃗⃗ . Mỗi ⃗⃗⃗ là một véctơ có p chiều.
SVM tìm một siêu phẳng mà khoảng cách từ siêu phẳng đến điểm gần nhất của mỗi lớp là lớn nhất. Siêu phẳng
này được gọi là siêu phẳng có lề cực đại.
Một siêu phẳng được xem như tập các điểm thỏa mãn:
⃗⃗ (1)
với ⃗⃗⃗⃗ là véctơ định hướng siêu phẳng (⃗⃗⃗⃗ vuông góc với siêu phẳng). Tham số ‖ ⃗⃗ ‖ là lề của siêu phẳng.
2.2.2. SVM không tuyến tính với hàm nhân
Để cải thiện hiệu quả của việc phân lớp, SVM dùng thêm hàm nhân để biến đổi các mẫu trước khi đưa vào
SVM học và dự đoán lớp. Quá trình học và dự đoán lớp vẫn giống SVM tuyến tính. Dưới đây là một số hàm nhân phổ
biến.
Nhân đa thức: có 2 dạng
(⃗⃗⃗ ⃗⃗⃗ ) (⃗⃗⃗ ⃗⃗⃗ ) (2)
(⃗⃗⃗ ⃗⃗⃗ ) (⃗⃗⃗ ⃗⃗⃗ ) (3)
Nhân của Gauss
(⃗⃗⃗ ⃗⃗⃗ ) ( ‖⃗⃗⃗ ⃗⃗⃗ ‖ ) với (4)
- 132 ĐỀ XUẤT TẬP ĐẶC TRƯNG DÙNG TRONG PHÂN LỚP MÔ HÌNH 3D
2.2.3. Các tính toán trong bộ phân lớp SVM
Để học luật phân lớp không tuyến tính, mẫu vào ⃗⃗⃗ cần được chuyển đổi qua hàm ⃗⃗⃗ . Hơn nữa, việc dùng
hàm nhân k cần thỏa mãn điều kiện:
(⃗⃗⃗ ⃗⃗⃗ ) ⃗⃗⃗ (⃗⃗⃗ ) (5)
Véctơ ⃗⃗⃗⃗⃗ được tính bằng công thức:
⃗⃗⃗⃗ ∑ ⃗⃗⃗
(6)
với ci thu được nhờ giải bài toán tối ưu sau:
∑ ∑∑ (⃗⃗⃗ ⃗⃗⃗ )
(7)
Các ràng buộc gồm:
∑
(8)
và
, với mọi i (9)
Một mẫu mới được gán vào lớp:
∑ ⃗⃗⃗
(10)
IV. ĐỀ XUẤT TẬP ĐẶC TRƢNG VÀ LỰA CHỌN BỘ PHÂN LỚP THÍCH HỢP
4.1. Các yêu cầu của tập đặc trƣng
Bài toán phân lớp được giải quyết tốt phụ thuộc vào 2 yếu tố gồm tập đặc trưng có khả năng đại diện cho các lớp
và một bộ phân lớp phù hợp để phân lớp hiệu quả. Bài toán phân lớp nói chung phải phân lớp các mô hình ở nhiều lớp
khác nhau. Vì vậy, việc tìm ra một tập đặc trưng có thể đại diện cho từng lớp là vấn đề hết sức quan trọng bởi vì số lớp
càng lớn thì việc tìm tập đặc trưng càng khó.
Thông thường, các yêu cầu của một tập đặc trưng tốt bao gồm:
Phải có khả năng thể hiện đặc trưng riêng của từng lớp;
Không nên phụ thuộc vào kích thước và vị trí của mô hình;
Tính toán càng đơn giản càng tốt;
Số lượng đặc trưng càng ít càng tốt.
Yêu cầu đầu tiên là bắt buộc để đảm bảo bộ phân lớp có thể làm việc hiệu quả. Các yêu cầu còn lại để đạt được
thường phải đánh đổi bằng việc giảm tính hiệu quả của việc phân lớp.
4.2. Đề xuất tập đặc trƣng
Để đảm bảo các đặc trưng không phụ thuộc vào kích thước của mô hình, chúng tôi thực hiện chuẩn hóa tọa độ các
đỉnh về miền [0,1] trước khi rút trích các đặc trưng. Nghĩa là, mọi mô hình được co nhỏ để nằm trong khối lập phương có
độ dài cạnh là 1 nằm ở phía dương của các trục tọa độ. Cách làm cụ thể như sau: Đầu tiên, tìm giá trị lớn nhất thể hiện ba
thành phần x, y, z của mọi điểm mô tả mô hình 3D. Sau đó, chia giá trị của các thành phần x, y, z của mọi điểm cho giá trị
lớn nhất tìm được. Việc này đảm bảo tiêu chuẩn thứ hai về tập đặc trưng.
Chúng tôi đề xuất tập đặc trưng cố gắng đạt được cả 4 yêu cầu trên. Chúng tôi lựa chọn các giá trị riêng
(eigenvalues) của các trục cơ bản (principal axis) trong mô hình 3D làm tập đặc trưng. Do đó, chúng tôi chỉ dùng có 3
đặc trưng để phân lớp. Điều này đảm bảo tiêu chuẩn thứ tư về tập đặc trưng.
Chúng tôi cung cấp một số khái niệm cơ bản để giải thích ý nghĩa của ba đặc trưng và lý do đảm bảo hai tiêu chuẩn
còn lại của tập đặc trưng.
Trục cơ bản là ba trục vuông góc với nhau trong một khối mà mômen quán tính của khối là cực đại. Với vật thể
rắn đặc, mômen quán tính được tính bằng tích phân toàn bộ thể tích vật thể. Hình 1 mô tả các trục cơ bản của một
khối trụ.
- Nguyễn Văn Tảo, Nông Thị Hoa 133
Hình 1. Các trục cơ bản của khối trụ
Giá trị riêng của một trục cơ bản là hệ số biến đổi của véctơ riêng thể hiện từng trục cơ bản trong khối. Véctơ
riêng của các trục cơ bản thể hiện sự biến đổi hình dạng của đối tượng theo một trục cơ bản. Sự biến đổi hình dạng của đối
tượng được thể hiện qua sự thay đổi mômen quán tính trên toàn bề mặt đối tượng. Do các mô hình 3D thuộc các lớp khác
nhau thì sự biến đổi hình dạng theo ba trục x, y, z cũng khác nhau. Vì vậy, các giá trị riêng có thể đại diện cho các lớp có
hình dạng khác biệt. Vì vậy, tập đặc trưng đề xuất có thể đại diện cho các lớp đối tượng khác nhau. Nghĩa là, tập đặc trưng
đề xuât đảm bảo tiêu chuẩn thứ nhất của tập đặc trưng.
Cách tính toán để rút trích các đặc trưng sẽ đảm bảo tiêu chuẩn thứ ba của tập đặc trưng. Các bước để tính đặc
trưng của các mô hình 3D thông qua các phép tính đơn giản trên các ma trận gồm:
Bước 1: Chuẩn hóa tọa độ của các điểm về miền giá trị [0,1].
Bước 2: Lấy danh sách các điểm của mô hình 3D và xếp thành các hàng liên tiếp (lưu trong ma trận X).
Bước 3: Tính ma trận hiệp phương sai (covariance matrix) theo công thức A=XTX.
Bước 4: Tính giá trị riêng (eigenvalues) của A. Đây chính là các đặc trưng đề xuất.
Cách tính giá trị riêng của một ma trận:
Cho A là ma trận vuông cấp n trên trường số thực. Số được gọi là giá trị riêng của ma trận A, nếu tồn tại một
vectơ u sao cho: . Khi đó, véctơ u được gọi là véctơ riêng của ma trận A ứng với giá trị riêng .
Giá trị riêng chính là nghiệm của phương trình . Để giải phương trình này, chúng ta chỉ dùng 4
phép toán cơ bản gồm cộng, trừ, nhân chia. Điều này cho thấy, tiêu chuẩn thứ ba của tập đặc trưng đã được thỏa mãn.
4.3. Lựa chọn bộ phân lớp thích hợp
Chúng tôi xem xét đặc điểm và ưu điểm của các bộ phân lớp thường dùng (Naïve Bayes, Cây quyết định, SVM,
mạng nơ-ron) để chọn một bộ phân lớp thích hợp với tập đặc trưng đề xuất. Ưu điểm của SVM là việc huấn luyện của
SVM có thể đạt đến mức độ lỗi nhỏ. Điều này đảm bảo SVM phân lớp hiệu quả nếu được cung cấp tập huấn luyện tốt.
Hạn chế của SVM là overfitting. Chúng ta chỉ cần chọn tập huấn luyện có số lượng mẫu vừa đủ và có tính tổng quát hóa
cao là có thể khắc phục được hạn chế này. Qua các phân tích trên, chúng tôi lựa chọn SVM làm bộ phân lớp. Các thực
nghiệm được làm để chứng minh tính hiệu quả của tập đặc trưng đề xuất và sự lựa chọn đúng bộ phân lớp.
V. KẾT QUẢ THỰC NGHIỆM
5.1. Mô tả tập dữ liệu
Các mô hình dùng trong thực nghiệm được lấy từ cơ sở dữ liệu chuẩn Princeton Shape Benchmark [10]. Cơ sở dữ
liệu này được dùng cho việc đánh giá kết quả nghiên cứu trong việc đối sánh, phân lớp, phân cụm và nhận dạng các mô
hình 3D. Các thực nghiệm được làm trên các mô hình về các phương tiện giao thông gồm 6 lớp: máy bay, khinh khí cầu,
thuyền buồm, tàu thủy, ô tô, tàu hỏa. Trong mỗi lớp lại có thể chia thành các lớp con. Ví dụ: trong lớp máy bay chia thành
máy bay trực thăng, máy bay chở khách, máy bay chiến đấu, máy bay thể thao. Chúng tôi lựa chọn các mẫu trong các lớp
bằng các mẫu điển hình của mỗi lớp con. Đối với các lớp có số lượng ít như khinh khí cầu, tàu hỏa thì mọi mẫu đều được
dùng cho thử nghiệm.
Tập dữ liệu dùng trong thử nghiệm có 100 mô hình gồm 23 máy bay, 21 tàu thủy, 15 thuyền buồm, 11 khinh khí
cầu, 8 tàu điện và 24 ô tô. Nhãn lớp đúng của các mẫu được gán dựa vào hình ảnh của mỗi mẫu. Nhãn tương ứng với các
lớp: 1 (máy bay), 2 (kinh khí cầu), 3 (tàu thủy), 4 (thuyền buồm), 5 (tàu điện), 6 (ô tô). Hình 2 biểu diễn hình ảnh về các
mô hình dùng trong thử nghiệm.
- 134 ĐỀ XUẤT TẬP ĐẶC TRƯNG DÙNG TRONG PHÂN LỚP MÔ HÌNH 3D
Hình 2. Các mô hình dùng trong thử nghiệm.
5.2. Kết quả thực nghiệm
Tập dữ liệu trên được chia ngẫu nhiên thành ba tập con gồm tập huấn luyện, tập kiểm tra và tập thẩm định. Chúng
tôi chọn tỷ lệ chia các mẫu thường được dùng là (0,7, 0,15, 0,15). Chúng tôi dùng tập huấn luyện (có 70 mẫu) và dùng 2
tập còn lại (có 30 mẫu) để kiểm tra.
Các kỹ thuật phân lớp được code để so sánh bao gồm thuật toán K-means và bộ phân lớp Naïve Bayes. Kết quả
phân lớp của K-means được gióng nhãn sao cho kết quả phân lớp cao nhất. Bộ phân lớp Naïve Bayes cũng dùng tập huấn
luyện giống mô hình SVM.
Chúng tôi đã làm 5 lần thử nghiệm. Với mỗi lần, chia lại dữ liệu theo cách ngẫu nhiên và cho các kỹ thuật cùng dự
đoán nhãn lớp. Kết quả thử nghiệm được thể hiện trong các bảng từ Bảng 1 đến Bảng 5. Mỗi bảng thể hiện tổng số mẫu
trong mỗi lớp, số mẫu được phân lớp đúng của mỗi kỹ thuật để tiện cho việc so sánh. Bảng 6 tổng hợp tỷ lệ % dự đoán
đúng của 5 lần thử nghiệm.
Bảng 1. Kết quả của lần thử nghiệm thứ nhất
Số mẫu dự đoán đúng
Nhãn lớp Số mẫu
Bayes Kmeans SVM
1 9 7 6 8
2 4 2 1 4
3 5 5 1 5
4 4 1 4 4
5 1 0 1 1
6 7 5 4 6
Tổng 30 20 17 28
Tỷ lệ % 66,667 56,667 93,333
- Nguyễn Văn Tảo, Nông Thị Hoa 135
Bảng 2. Kết quả của lần thử nghiệm thứ hai
Số mẫu dự đoán đúng
Nhãn lớp Số mẫu
Bayes Kmeans SVM
1 5 4 2 4
2 3 3 2 3
3 5 4 5 5
4 7 2 4 4
5 3 2 0 3
6 7 7 6 7
Tổng 30 22 19 26
Tỷ lệ % 73,333 63,333 86,667
Bảng 3. Kết quả của lần thử nghiệm thứ ba
Số mẫu dự đoán đúng
Nhãn lớp Số mẫu
Bayes Kmeans SVM
1 12 10 7 11
2 2 2 1 2
3 5 5 4 5
4 3 2 0 3
5 2 2 2 2
6 6 5 5 5
Tổng 30 26 19 28
Tỷ lệ % 86,667 63,333 93,333
Bảng 4. Kết quả của lần thử nghiệm thứ tư
Số mẫu dự đoán đúng
Nhãn lớp Số mẫu
Bayes Kmeans SVM
1 4 3 3 4
2 1 1 0 1
3 5 5 5 5
4 8 4 4 6
5 3 1 2 2
6 9 9 8 9
Tổng 30 23 22 27
Tỷ lệ % 76,667 73,333 90,000
Bảng 5. Kết quả của lần thử nghiệm thứ năm
Số mẫu dự đoán đúng
Nhãn lớp Số mẫu
Bayes Kmeans SVM
1 7 7 4 6
2 4 2 1 2
3 5 4 5 5
4 5 2 0 5
5 2 0 2 0
6 7 7 7 7
Tổng 30 22 19 25
Tỷ lệ % 73,333 63,333 83,333
Dữ liệu từ Bảng 1 và Bảng 5 cho thấy SVM cho kết quả phân lớp tốt nhất. Tiếp theo là bộ phân lớp Naïve Bayes.
Cuối cùng là thuật toán Kmeans. Hơn nữa, các lớp đều được nhân dạng trong cả 5 thử nghiệm, ngoại trừ lớp thứ 5 trong
thử nghiệm lần 5. Điều này cho thấy việc lựa chọn SVM để phân lớp dựa trên tập thuộc tính đề xuất là đúng.
Bảng 6. Tổng hợp kết quả của các lần thử nghiệm
Tỷ lệ % dự đoán đúng
Lần thử nghiệm
Bayes Kmeans SVM
1 66,667 56,667 93,333
2 73,333 63,333 86,667
3 86,667 63,333 93,333
4 76,667 73,333 90,000
5 73,333 63,333 83,333
Trung bình 75,333 63,9998 89,333
- 136 ĐỀ XUẤT TẬP ĐẶC TRƯNG DÙNG TRONG PHÂN LỚP MÔ HÌNH 3D
Số liệu ở dòng cuối của Bảng 6 cho thấy kết quả phân lớp của SVM cao hơn hai kỹ thuật được so sánh 14 % và
26,666 %. Độ chính xác của SVM đạt 89.333 %. Kết quả của 5 thực nghiệm cho thấy cách tiếp cận của chúng tôi phân
lớp hiệu quả các tập dữ liệu mà có sự khác biệt rõ ràng về hình dạng giữa các lớp đối tượng.
VI. KẾT LUẬN
Trong bài báo này, chúng tôi đề xuất tập đặc trưng ngắn gọn và lựa chọn mô hình SVM để phân lớp. Các đặc trưng
gồm 3 giá trị riêng của ba trục cơ bản của mô hình 3D. Mô hình SVM được chọn nhờ ưu điểm về quá trình huấn luyện và
có thể giảm được nhược điểm về overfitting. Các thực nghiệm được làm với tập dữ liệu chuẩn Pinceton Shape
Brenchmark về phân lớp các hình dạng 3D. Chúng tôi tiến hành thực nghiệm phân lớp trên 100 phương tiện giao thông
bao gồm 6 lớp: máy bay, tàu thủy, thuyền buồm, ô tô, tàu hỏa, khinh khí cầu. Kết quả thực nghiệm cho thấy việc dùng
SVM kết hợp với tập đặc trưng đề xuất cho kết quả phân lớp tốt hơn các kỹ thuật được so sánh.
Trong thời gian tới, chúng tôi sẽ nghiên cứu bổ sung thêm một số đặc trưng để cải thiện độ chính xác của phân lớp
và mở rộng thực nghiệm trên các tập dữ liệu lớn hơn.
TÀI LIỆU THAM KHẢO
[1] Z. Shu, S. Xin, H. Xu, L. Kavan, P. Wang, L. Liu. “3D model classification via Principal Thickness Images”,
Computer-Aided Design, vol. 78, pp. 199-208, 2016.
[2] L. Biao, D. Changchun, G. Shuang Guo, Z. Xiangyang Zhang, X. Zhang. “A powerful 3D model classification
mechanism based on fusing multi-graph”, Neurocomputing, vol. 168, pp. 761-769, 2015.
[3] J. Y. Gwak. 3D model classification using convolutional neural network, Report of Stanford University, 2015.
http://cs229.stanford.edu/proj2015/146_report.pdf.
[4] Q. Fei-wei, L. Lu-ye, G. Shu-ming, Y. Xiao-ling, C. Xiang. “A deep learning approach to the classification of 3D
CAD models”, Journal of Zhejiang University SCIENCE C", vol. 15, no 2, pp. 91-106, 2014.
[5] S. P. Foliguet, M. Jordan, L. Najman, J. Cousty. “Artwork 3D model database indexing and classification”, Pattern
Recognition, vol. 44, pp. 588-597, 2011.
[6] A. Kassimi, O. E. Beqqali. “3D Model Classification And Retrieval Based on Semantic And Ontology”,
International Journal of Computer Science, Vol. 8, Issue 5, No 2, 2011.
[7] L. Zongmin, W. Daqian, L. Boyang, Z. Liangliang, “3D model classification using salient features for content
representation”, Sixth International Conference on Natural Computation, vol. 7, pp. 3541-3545, 2010.
[8] H. Yuesheng, Y. Y. Tang. “Classification of 3D models for the 3D animation environments”, IEEE International
Conference on Systems, Man and Cybernetics, pp. 3786-3791, 2009.
[9] Corinna Cortes, Vladimir Vapnik: Support-vector networks, Machine Learning 20(3), 273-297, (1995).
[10] P. Shilane, P. Min, M. Kazhdan, T. Funkhouser. “The Princeton Shape Benchmark”, Shape Modeling
International, 2004. Available at: http://shape.cs.princeton.edu/benchmark/.
PROPOSE AN FEATURE SET FOR CLASSIFYING 3D MODELS
Nguyen Van Tao, Nong Thi Hoa
ABSTRACT: Classifying 3D models for storing in databases helps to speed queries when designing virtual scences in movies and
games. Therefore, classifying 3D models is a essential task. Previous studies proposed features sets which have from 250 to 800
features, and can use complex computing for extracting. As a result, the time for classifying is more long to process features. In this
paper, we propose a small set of features and select SVM to classify 3D model. These features obtains from the Principal component
analysis of 3D models. Eigenvalues of principal axis of 3D models are proposed features. We select SVM as a classifier based on
the advantages and characterics of SVM. Experiments are conducted with the brenchmark dataset, Pinceton Shape Brenchmark.
We classify 6 classes of travel means. Experimental results show that our approach is better than comparing methods.
Keywords: Classifying model 3D, extract features, 3D models, Support Vector Machine, computer vision.
nguon tai.lieu . vn
