Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)

Cải tiến lược đồ Camshift trong Open CV
Nguyễn Thị Trang1, ũ ăn Hiệu và Nguyễn Đức Tồn3
1

Trường Đại học Hạ Long
Khoa Cơng nghệ thông tin - Trường Đại học Công Nghiệp Hà Nội
3
Khoa Công nghệ thông tin - Trường Đại học Tài Nguyên và Môi Trường Hà Nội
2

Email: , hieuvv@fit haui.edu.vn,
Abstract Trong bài báo này, chúng tôi cải tiến lược đồ
Camshi t trong Open C . Thuật toán này được phát
triển từ thuật toán Meanshi t, bao gồm thuật toán cơ sở
Meanshi t với thích ứng các bước thay đ i kích c của
vùng. Nh n là một hàm step đơn giản n m trong một
bản đồ vỏ xác suất (skin probability). ỏ xác suất của
mỗi một điểm ảnh được tính tốn dựa trên màu sắc b ng
cách sử dụng một phương pháp gọi là Histogram
backpro ection. Màu sắc được đưa ra như Hue từ mơ
hình màu HS . Trong bài báo này chúng tơi dùng thuật
tốn CamShi t đ được cải tiến trong Open C để dễ
dàng thích ứng với sự thay đ i ph n bố xác suất màu sắc
của mục tiêu theo d i.
Keywords- Thuật toán Camshi t, thuật toán
pen C , istogram

I.

chúng ta phát hiện sai do nhiễu gây ra ta có thể dùng
ngưỡng thích hợp. Nếu độ sai khác lớn hơn ngưỡng thì cho
ra giá trị bằng 1ngược lại cho ra giá trị không. Nếu ngưỡng
quá lớn, pixel thuộc đối tượng có thể lẫn với nền, nếu
ngưỡng quá nhỏ, thì sự thay đổi ánh sáng trong mơi trường
sẽ tạo ra nhiều pixel có giá trị 1, mà các điểm này lại không
phải là điểm thuộc đối tượng. Sau khi xử lý ngưỡng ta thu
được ảnh nhị phân chỉ gồm các pixel với hai trạng thái 0 và
1. Quá trình phân đoạn ảnh thành từng đối tượng riêng rẽ
được thực hiện thơng qua thuật tốn đánh nhãn liên tiếp.
Q trình này sẽ tạo ra vơ số đối tượng khác nhau, trong đó
chỉ có một số đối tượng gần với đối tượng cần quan tâm.
Một quá trình quét tiếp theo sẽ được thực hiện để loại bỏ các
đối tượng không hợp lý so với đối tượng mẫu. Việc còn lại
là xác định vị trí trọng tâm của mục tiêu trên ảnh tương đối
đơn giản, thông qua xác định momen bậc nhất. Kể từ nhân
là một hàm step, Mean Shift ở mỗi một lần lặp thì chỉ đơn
giản là giá trị trung bình x và y của vỏ xác suất đóng góp
trong vùng hiện tại. Điều này được xác định bằng cách chia
moment thứ nhất của vùng này cho moment thứ không ở
mỗi lần lặp và dịch chuyển vùng đến trọng tâm xác suất.
Sau khi Mean Shift hội tụ đến một vị trí (x,y), phạm vi của
vùng được cập nhật dựa trên giá trị hiện tại của moment thứ
0. Giá trị của bản cập nhật này có thể thay đổi, phạm vi
tuyến tính của nó được giả định là tỉ lệ thuận với căn bậc 2
của tổng của các khoản đóng góp xác suất của khu vực hiện
tại (ví dụ. Moment thứ không). Chiều rộng và chiều dài tại
thời điểm thứ i sẽ được tính thơng qua giá trị tại thời điểm
thứ i-1, nghĩa là giá trị trước nên phương pháp chính được
giới thiệu trong bài báo này là thuật tốn Camshift. Thuật

toán này đặc biệt hiệu quả với ảnh thu được từ camera là
ảnh màu và đối tượng cần phát hiện và bám có màu sắc đặc
trưng riêng so với nền.

eanshi t,

GI I THI U

Nhận dạng mục tiêu di động là bước đầu tiên
và quan trọng trong hệ robot tự động nhận dạng và tìm
kiếm mục tiêu di động. Mục đích của q trình này là
thực hiện các phép xử lý ảnh để tìm kiếm đối tượng
cần quan tâm, xác định vị trí của nó trong mặt ph ng
ảnh hiện thời. Trong quá trình tìm kiếm ta chia tập hợp
các pixel của mặt ph ng ảnh ra làm hai thành phần:
Hoặc là thuộc đối tượng hoặc là thuộc nền. Sau đây ta
sẽ xem xét việc tìm kiếm các pixel thuộc đối tượng
trong chuỗi ảnh thu về.
Có rất nhiều cách để nhận dạng một đối tượng: khi biết
trước chính xác đặc điểm của đối tượng cần nhận dạng
ta có thể áp đặt tồn bộ mơ hình của đối tượng (màu
sắc, hình dáng) lên tồn bộ ảnh từ đó tìm ra vị trí của
đối tượng trong ảnh. Phương pháp này có ưu điểm đơn
giản, dễ thực hiện nhưng lại không hiệu quả trong thực
tế. Một phương pháp nhanh hơn, hiệu quả hơn và áp
dụng rất hiệu quả đối với ảnh đen trắng là phương
pháp so sánh.Phương pháp này dựa trên đặc điểm các
pixel thuộc nền thì cường độ sáng ít thay đổi hoặc nếu
thay đổi thì rất nhỏ cịn các pixel thuộc đối tượng
cường độ sáng thay đổi lớn. Như vậy một phép so sánh

giữa các pixel trong ảnh hiện thời với ảnh trước đó
được thực hiện.Nếu camera tĩnh, sự thay đổi ánh sáng
của môi trường rất nhỏ và nhiễu không đáng kể thì một
pixel thuộc nền nếu độ sai khác bằng 0 và ngược lại sẽ
thuộc đối tượng. Tuy nhiên trong thực tế các điều kiện
trên khó có thể xảy ra, do đó để loại bỏ các điểm mà

ISBN: 978-604-80-5076-4

II.

C S TO N H C

2.1. Cơ sở toán h c của thuật toán Camshift.
Thuật toán CamShift [8] được xuất phát và dựa
trên nền tảng của thuật toán MeanShift, do vậy việc tính
trọng tâm của đối tượng và dịch chuyển cửa sổ tìm kiếm
(với kích thước cửa sổ cố định) sẽ thực hiện bằng MeanShift
[6], dựa theo vết màu và moment ảnh. tưởng chính của
CamShift là tính lại trọng tâm của đối tượng dựa vào frame
ảnh trước đó và kích thước của cửa sổ tìm kiếm được thay
đổi động theo đối tượng. Nhân là một hàm step đơn giản

313


Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)

nằm trong một bản đồ vỏ xác suất (skin-probability).
Vỏ xác suất của mỗi một điểm ảnh được tính tốn dựa

trên màu sắc bằng cách sử dụng một phương pháp gọi
là Histogram backprojection. Màu sắc được đưa ra như
Hue từ mơ hình màu HSV. Kể từ nhân là một hàm step,
Mean Shift ở mỗi một lần lặp thì chỉ đơn giản là giá trị
trung bình x và y của vỏ xác suất đóng góp trong vùng
hiện tại. Điều này được xác định bằng cách chia
moment thứ nhất của vùng này cho moment thứ không
ở mỗi lần lặp và dịch chuyển vùng đến trọng tâm xác
suất. Sau khi Mean Shift hội tụ đến một vị trí (x,y),
phạm vi của vùng được cập nhật dựa trên giá trị hiện
tại của moment thứ 0. Giá trị của bản cập nhật này có
thể thay đổi, phạm vi tuyến tính của nó được giả định
là tỉ lệ thuận với căn bậc 2 của tổng của các khoản
đóng góp xác suất của khu vực hiện tại (ví dụ. Moment
thứ khơng). Chiều rộng và chiều dài tại thời điểm thứ i
sẽ được tính thơng qua giá trị tại thời điểm thứ i-1,
nghĩa là giá trị trước đó.
Trong thuật tốn CamShift, một bức ảnh về xác suất
phân bố màu sắc của bức ảnh trong chuỗi video được
tạo ra. Đầu tiên nó tạo ra một mẫu mô tả hue sử dụng
một biểu đồ màu sắc (color Histogram) và sử dụng
không gian màu Hue Saturation Value (HSV) được
tham chiếu từ không gian màu tiêu chu n RGB. Vì
phân bố màu sắc của các bức ảnh trong video thay đổi
theo thời gian, nên thuật toán CamShift đã được sửa
đổi để dễ dàng thích ứng với sự thay đổi phân bố xác
suất màu sắc của mục tiêu nó theo dõi.
2.2 . Các bước thực thi thuật toán Camshift:
Các bước thực thi thuật toán Camshift:
B1: Chọn vị trí ban đầu của cửa sổ tìm kiếm.

B2: Thuật tốn Meanshift (lặp một hoặc nhiều lần),
lưu moment thứ 0.
B3: Kích cỡ của cửa sổ tìm kiếm được đặt bằng một
hàm của moment thứ 0 vừa tìm được trong bước 2.
B4: Lặp lại bước 2 và bước 3 cho đến khi hội tụ (nghĩa
là vị trí dịch chuyển nhỏ hơn ngưỡng thiết lập trước
đó).
2.3. Thuật tốn Camshift
Đầu tiên là một Histogram được tạo ra, Histogram này
chứa các thuộc tính liên quan đến màu sắc. Sau khi tạo
ra histogram, tiếp theo tâm và kích cỡ của mục tiêu
được tính tốn để theo dõi mục tiêu khi hình dạng và
kích cỡ của nó thay đổi. Tính xác suất phân bố mục
tiêu căn cứ vào Histogram nhận được. Dịch chuyển
đến vị trí mới với mỗi khung hình vừa nhận được từ
video. Camshift sẽ dịch chuyển đến vị trí mà nó ước
lượng trên đối tượng tập trung nhiều điểm sáng nhất
trong bức ảnh xác suất.

Tìm vị trí mục tiêu của ảnh với vị trí y0 với ảnh hiện tại
đang xét:

p ( y0 ), q
n

p ( y0 ), q

pk ( y0 )qn (1)
k


Bước 2: Tính tr ng số
n

i

qk
(b( xi ).k ) (2)
pk ( y0 )

i
k 0

Bước 3: Tính vị trí tiếp theo
n

xi

y0

i .g (

y1

n
i

y0

.g (


xi
h

i

2

xi

)

h

i

(3)

2

)

Bước 4: Tính vị trí ảnh ở vị trí mới

p1 ( y1 )

k 1... n

n

p1 ( y1 ), q1


pk ( y1 )qn (4)
k 0

Bước 5: So sánh vị trí ảnh c và ảnh ở vị trí mới. Nếu:
p ( y0 ), q

n
k

p k ( y0 ) q n

p ( y1 ), q
1
1

thì tính:

y1

y1

y0
2

Bước 6: Kiểm tra

y0

xi


2

h
Thỏa mãn: y1

y0

thì dừng lại.

Nếu:

y0

III. C I TI N LƯ C Đ CAMSHIFT TRONG
OPEN CV.

xi

2

h

3.2.1. Cải tiến lược đ Camshift

Thỏa mãn: y1

Bước 1: Khởi tạo

ISBN: 978-604-80-5076-4


k 1... n

Tính theo cơng thức:

Sau đó tính:

314

y0

thì đặt y0

y1

n
k

pk ( y ) qn
1


Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)

n

T I LI U THAM KH O

qk
(b( xi ).k )

pk ( y0 )

i
k 0

[1] A. Mittal and M. Paragios (2004). Motion Based Background
Subtraction using Adaptive Kernel Density Estimation. pp. 302309.
[2] Artner (2008). A Comparison of Mean Shift Tracking Methods.
Digital Media, Upper Austria University of Applied Sciences.
[3] C. Zhang, Y. Qiao, E. Fallon, and C. u (2009). An improved
camshift algorithm for target tracking in video surveillance. In
Proceedings of 9th. IT and T Conference, number 12.
[4] D. Beymer and Konolige K (2001). Tracking people from a
mobile platform. In IJCAI-2001 Workshop on Reasoning with
Uncertainty in Robotics.
[5] R. Lienhart, J. Maydt (2002). An Extended Set of aar like
Features for Rapid Object Detection.
Intel Labs, Intel
Corporation, Santa Clara, CA 95052, USA.
[6] J. MacCormick and A. Blake (1999). A probabilistic
exclusion principle for track ing multiple objects. InProc. of 7th
International Conference on Computer Vision (ICCV), pages
572 587.
[7] Y. Freund, and R. Shapire (1995). A decision theoretic
generali ation of on line learning and an application to boosting.
Proceedings of the
Second European Conference on
Computational Learning Theory. pp. 23-37.
[8] Y.Cheng (1995). Mean Shift, Mode Seeking, and Clustering.
IEEE Transactions on Pattern Analysis and Machine Intelligence,

vol. 17, no. 8. August.

Cho đến khi thỏa mãn:
n 1 n 1
i

i

( xi .g i )

k 0 y 0

3.2.2. Đánh giá độ phức tạp của thuật tốn
Vị trí cần tìm được xác định như sau:

S

arg max sp ( 0)

Với:

p ( 0)

p ( c 0) p ( s 0)

Có thể dùng phương pháp vét cạn. Tuy nhiên sễ mất
nhiều thời gian tính tốn. Độ phức tạp của thuật toán
s

đề xuất là: O ( 2 ) với s là tổng thành phần của S.

Thuật tốn tìm vị trí
S'
S

S s p ( cs 0 )
arg max p ( c s 0 )

s s'
Temp

True

While (Temp ) do
Sa

if p

Si

S' S

S

S

arg max S

Sa

Sr


arg max S

Sr

S

arg max S

Sr

S

S 0

S

S

Else if p S
S

p S

Si là vùng liên thông

p S S 0
p S

S i là vùng liên thông


p S

S0

S 0 and p S

S 0

p S 0 then

S 0

S 0

p S 0 then

S -S 0

Else
Temp

False

End if
End hile

IV.

K T LU N


Trong lược đồ đề xuất nếu khi tính sai vị trí thì
bộ phận phát hiện và nhận dạng đối tượng sẽ liên tục tìm
đối tượng trên ảnh (bước 3,4,5) cho đến khi phát hiện và
giải thuật CamShift tiếp tục thực hiện cho đến khi tìm
đúng vị trí cần thực hiện ở bước tiếp theo. Lược đồ cải
tiến sẽ tìm vị trí mới bắt đầu từ vị trí trước đó và tính
tốn giá trị trọng tâm vừa tìm được. Lược đồ cải tiến
đều có thư viện các hàm tính tốn trong OpenCV.

ISBN: 978-604-80-5076-4

315