Áp dụng thuật toán octrees cho bước lượng tử trong quá trình phân đoạn ảnh màu bẳng thuật toán JSEG

T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 
 80 
ÁP DỤNG THUẬT TOÁN OCTREES CHO BƯỚC LƯỢNG TỬ 
TRONG QUÁ TRÌNH PHÂN ĐOẠN ẢNH MÀU BẲNG THUẬT TOÁN JSEG 
Đỗ Năng Toàn (Viện Công nghệ Thông tin – Viện KH&CN Việt Nam) 
Nguyễn Văn Tới (Khoa Công nghệ thông tin – ĐH Thái Nguyên) 
Nguyễn Thị Thu Hiền (Khoa Công nghệ thông tin – Trường ĐHSPKT Hưng Yên) 
1. Giới thiệu 
Phân đoạn ảnh dựa trên màu sắc rất có ích trong nhiều ứng dụng. Từ các kết quả phân 
đoạn có thể chỉ ra các vùng cần quan tâm và các đối tượng trong cảnh. Có nhiều phương pháp 
phân đoạn ảnh đã được nghiên cứu và đưa vào ứng dụng. Thuật toán phân đoạn ảnh màu JSEG 
do 3 giáo sư của trường đại học California là Yining Deng, B. S. Manjunath và Hyundoo Shin 
xây dựng. Thuật toán JSEG được đề xuất và thử nghiệm với sự kết hợp cùng thuật toán lượng tử 
bằng cách làm mịn và sử dụng trọng số (Peer group filtering and perceptual color image – PGF 
and PCI [4]) cho kết quả tương đối tốt. Tuy nhiên, thuật toán này còn một số hạn chế khi làm 
việc với các ảnh thiên nhiên. Chúng tôi đề xuất cải tiến thuật toán JSEG theo hướng kết hợp 
giữa JSEG và thuật toán lượng tử OCTREES. Cải tiến này cũng nhằm giảm khối lượng tính toán 
sau bước lượng tử hoá. 
Phần còn lại của bài báo: phần 2 giới thiệu thuật toán phân đoạn ảnh màu bằng JSEG và 
đề xuất thuật toán JSEG cải tiến (thuật toán O-JSEG); phần 3 đưa ra các kết quả thực nghiệm 
của thuật toán O-JSEG; và phần 4 nêu kết luận và hướng nghiên cứu tiếp theo. 
2. Thuật toán JSEG và đề xuất cải tiến 
2.1 Thuật toán JSEG [3] 
Đầu tiên, các màu trong ảnh được lượng tử hoá để thành một vài lớp đại diện. Nó có thể 
được sử dụng như các phân vùng khác nhau trong ảnh. Sau đó, màu của các pixel ảnh được thay 
thế bởi nhãn của các lớp màu tương ứng với chúng, theo đó ta định dạng được một bản đồ lớp 
của ảnh. Một tiêu chuNn để quá trình phân đoạn thực hiện tốt được sử dụng trong bản đồ lớp này 
đã được đề xuất. Áp dụng tiêu chuNn đó với cửa sổ cục bộ trong bản đồ lớp để đưa ra kết quả là 
ảnh “J-image”. Trong bất kỳ giá trị J cao, thấp nào đều lần lượt tương ứng với các đường biên 
hợp lý và trung tâm các phân vùng. 
(Xem sơ đồ thuật toán JSEG dưới đây) 
2.2 Cải tiến thuật toán JSEG (Thuật toán O-JSEG) 
Các thử nghiệm đã cho thấy rằng JSEG đã cung cấp các kết quả phân đoạn tốt trên các loại 
ảnh đa dạng. Chúng ta khó có thể đưa ra nhận xét chung cho một thuật toán phân đoạn bởi luôn 
luôn tồn tại những ưu, khuyết điểm trên những lớp ảnh cụ thể. Thuật toán JSEG còn một số hạn 
chế khi làm việc với các ảnh thiên nhiên. Ví dụ trường hợp hai vùng cạnh nhau có ranh giới 
không rõ ràng. 
Ngoài ra, kết quả của bước lượng tử có ảnh hưởng lớn đến độ phức tạp của các bước sau, 
vì vậy việc cải tiến bước lượng tử để giảm khối lượng tính toán cho bước các bước tiếp theo là 
cần thiết. Điều này phụ thuộc cơ bản vào bản đồ lớp màu (là kết quả của quá trình lượng tử hóa). 
Như vậy, bước lượng tử có vai trò hết sức quan trọng. Sự phân vùng của JSEG phụ thuộc trực 
tiếp vào chất lượng của ảnh lượng tử. 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 
 81
Thuật toán JSEG có độ phức tạp tính toán trên các điểm ảnh là tương đối lớn, nên khi 
lượng tử chỉ nên đưa ra ảnh có số màu biểu diễn nhỏ (từ 10 đến 20 màu) để giảm khối lượng 
tính toán. Nếu xem xét để lựa chọn một thuật toán lượng tử kết hợp với JSEG thì tiêu trí đầu tiên 
phải là ảnh ít bị nhiễu, các đối tượng trong ảnh được phân biệt rõ ràng. Sau đó, ta mới xét đến 
tiêu trí về màu cảm nhận gần với màu thật. Nếu ảnh đầu vào của thuật toán JSEG đạt được tiêu 
trí thứ nhất thì khối lượng tính toán sẽ giảm đi rất nhiều mà vẫn đảm bảo yêu cầu cho kết quả 
phân đoạn tốt. Chúng tôi lựa chọn thuật toán OCTREES để kết hợp với JSEG. Người ta xây 
dựng cây OCTREES theo tiêu chuNn hợp nhất các lá như sau [1], [2], [5]: 
1. Rút gọn các lá sâu nhất trong cây là lựa chọn đầu tiên và chúng miêu tả các màu sắc 
nằm gần nhau nhất. 
2. Chọn các lá là biểu diễn số điểm ảnh ít nhất trong cây. 
Ảnh màu 
Lượng tử hoá không gian màu 
với PGF and PCI 
Bản đồ lớp màu 
Khởi tạo Scale 
Với mỗi phân vùng 
Scale < ngưỡng? 
Tính toán giá trị J 
J-image 
Phát hiện Valley 
Phát triển Valley 
Các phân vùng 
sai 
Tă
n
g 
sc
a
le
lê
n
1 
Kết quả phân đoạn 
Hình 1: Sơ đồ thuật toán JSEG 
Trộn các phân vùng 
đúng 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 
 82 
Hình 2 là sơ đồ thuật toán O-JSEG (thuật toán JSEG cải tiến theo hướng kết hợp với 
thuật toán lượng tử OCTREES). 
3. Thực nghiệm 
Chúng tôi đã tiến hành thực nghiệm đối với 100 ảnh thiên nhiên của bộ dữ liệu ảnh 
MISC [6] (có 9908 ảnh). Kết quả: 79 ảnh cho kết quả phân đoạn cho tốt. Thuật toán O-JSEG cơ 
bản khắc phục được nhược điểm của thuật toán JSEG trong trường hợp hai vùng cạnh nhau có 
ranh giới không rõ ràng. Một số ảnh cho kết quả chưa chính xác trong trường hợp đối tượng có 
bóng do chiếu sáng, khi đó đối tượng sẽ bị chia thành nhiều phần (thân cây trong ảnh 7567.jpg), 
đây cũng là điểm tồn tại của thuật toán JSEG. Hình 3 biểu diễn một số kết quả thử nghiệm với 
việc sử dụng thuật toán O-JSEG. 
Ảnh màu 
Lượng tử hoá không gian màu 
với thuật toán OCTREES 
Bản đồ lớp màu 
Khởi tạo Scale 
Với mỗi phân vùng 
Scale < ngưỡng? 
Tính toán giá trị J 
J-image 
Phát hiện Valley 
Phát triển Valley 
Các phân vùng 
Kết quả phân đoạn 
Hình 2: Sơ đồ thuật toán O-JSEG 
Trộn các phân vùng 
đúng 
sai 
Tă
n
g 
sc
a
le
lê
n
1 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 
 83
File ảnh Ảnh gốc J-Image Kết quả phân đoạn Đánh giá 
66.jpg 
Tốt 
59.jpg 
Tốt 
79.jpg 
Tốt 
9283.jpg 
Tốt 
7567.jpg 
Chưa tốt 
Hình 3: Kết quả quá trình phân đoạn bằng thuật toán O-JSEG 
 trên một số ảnh thiên nhiên của cơ sở dữ liệu ảnh MISC 
4. Kết luận 
Các tác giả [3] đã kết hợp với lượng tử PGF and PCI với JSEG cho kết quả tương đối tốt. 
Chúng tôi đã đề xuất cải tiến thuật toán JSEG và tiến hành thử nghiệm theo hướng kết hợp thuật 
toán lượng tử OCTREES với JSEG (thuật toán O-JSEG). Kết quả thực nghiệm cho thấy: với 
một số trường hợp ảnh thiên nhiên, O-JSEG cho kết quả tốt hơn. Đối với các thuật toán phân 
đoạn, không thể kết luận thuật toán nào là tối ưu hơn vì với trường hợp này sự kết hợp của thuật 
toán PGF and Perceptual với JSEG là tốt, nhưng trường hợp khác thì sự kết hợp giữa OCTREES 
và JSEG lại cho kết quả phân đoạn đạt yêu cầu hơn (phụ thuộc mục đích sử dụng và lĩnh vực áp 
dụng). Chúng tôi dự định tiếp tục nghiên cứu nâng cao chất lượng của O-JSEG để áp dụng xây 
dựng hệ thống tra cứu trên cơ sở dữ liệu ảnh thiên nhiên 
 
Tóm tắt 
 Bài báo này trình bày việc áp dụng thuật toán OCTREES trong bước lượng tử hoá của 
thuật toán phân đoạn ảnh màu JSEG (thuật toán O-JSEG). Thuật toán JSEG là một hướng tiếp 
cận hoàn toàn tự động cho việc phân đoạn ảnh màu do Yining Deng, B. S. Manjunath và 
Hyundoo Shin đề xuất. Bước đầu tiên và rất quan trọng của thuật toán là lượng tử hoá các màu 
của ảnh thành một số lớp màu bởi một thuật toán độc lập. Chúng tôi đã thử nghiệm áp dụng 
thuật toán OCTREES cho bước này, thấy kết quả phân đoạn tương đối tốt trên các ảnh thiên 
nhiên. Sắp tới, kết quả này sẽ được áp dụng trong khuôn khổ đề tài cấp Bộ (Nghiên cứu ứng 
dụng một số kỹ thuật tra cứu ảnh vào thực tế) đang thực hiện tại Khoa Công nghệ thông tin – 
Đại học Thái Nguyên. 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 
 84 
Summary 
This report presents the way to apply the OCTREES algorithm in the quantizing step of 
JSEG color image segmentation algorithm (O-JSEG algorithm). The JSEG algorithm is a fully 
automatic approach for color image segmentation which was put forward by Yining Deng, 
B.S.Manjunath and Hyundoo Shin. The initial and important step of this algorithm is color 
quantization of images into some color classes with an independent algorithm. OCTREES 
algorithm has been applied and has gained a comparatively good segmentation results on natural 
images. This result is going to applied in the ministrial research project (A study on some image 
retrieval methods and application), which has been being carried out at the Faculty of 
Information technology - Thai Nguyen University. 
Tài liệu tham khảo 
[1]. Dan S. Bloomberg, “Color quantization using octrees”, 
[2]. D. Clark, “Color quantization using octrees” Dr. Dobb’s Journal, pp. 54-57 and 102-104, Jan. 1996. 
[3]. Yining Deng, B. S. Manjunath and Hyundoo Shin, “Color Image Segmentation”, Department of 
Electrical and Computer Engineering University of California, Santa Barbara, 
[4]. Y. Deng, C. Kenney, M.S. Moore, and B.S. Manjunath, “Peer group filtering and perceptual color 
image quantization”, to appear in Proc. of ISCAS, 1999. 
[5]. M. Gervautz and W. Purgathofer, “A simple method for color quantization: octree quantization” in 
A. Glassner, ed, Graphics Gems I, Acad. Press, 1990, pp. 287-293. 
[6]. MISC database,