BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------TRẦN NGUYỄN MINH TOÀN
XÂY DỰNG HỆ THỐNG CHẤM ĐIỂM
TRẮC NGHIỆM SỬ DỤNG CAMERA
Chuyên ngành: Kỹ thuật truyền thông
LUẬN VĂN THẠC SĨ KỸ THUẬT
Người hướng dẫn: PGS. TS. Nguyễn Tiến Dũng
Hà Nội, 5-2013
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai
công bố trong bất kỳ công trình nào khác.
Tác giả
Trần Nguyễn Minh Toàn
2
MỤC LỤC
3
1. Thực tiễn của đề tài
Thế kỷ XXI với những thay đổi to lớn mở đầu cho một kỷ nguyên mới- kỷ
nguyên của một nền kinh tế tri thức, một xã hội thông tin. Chính vì thế, giáo dục
đào tạo được coi là yếu tố quyết định thúc đẩy đất nước đi nhanh vào nền kinh tế tri
thức - một xu hướng phát triển mới của thế giới.
Hiện nay, nhiều hình thức kiểm tra được áp dụng từ kiểm tra miệng, kiểm tra
vấn đáp, kiểm tra viết, kiểm tra trắc nghiệm, bài tập lớn, tiểu luận, luận văn... Trong
đó hình thức kiểm tra trắc nghiệm khách quan đang được sử dụng rất rộng rãi do
những nguyên nhân sau :
• Có thể tiến hành kiểm tra đánh giá trên diện rộng trong một khoảng thời
gian ngắn.
• Chấm bài nhanh, chính xác và khách quan.
• Bài kiểm tra có rất nhiều câu hỏi nên có thể kiểm tra được một cách hệ
thống và toàn diện kiến thức và kĩ năng của thí sinh, tránh được tình trạng
học tủ, dạy tủ.
• Sự phân phối điểm trải trên một phổ rất rộng nên có thể phân biệt được rõ
ràng các trình độ của thí sinh.
Tháng 06/2007, Bộ Giáo dục và Đào tạo đã chính thức chuyển một số môn
thi của các kỳ thi cấp Quốc gia như thi tốt nghiệp Trung học phổ thông và thi tuyển
sinh vào các trường Cao đẳng, Đại học từ hình thức tự luận sang trắc nghiệm. Tuy
nhiên, việc áp dụng các phương tiện kỹ thuật hiện đại cũng gây ra nhiều khó khăn,
thách thức. Đối với thí sinh, không những phải tô đậm, chính xác điểm cần tô mà
còn phải giữ giấy thi phẳng, ngay ngắn và sạch sẽ. Chỉ một vài thay đổi nhỏ như
giấy bị nhàu nát cũng có thể gây ra sự không chính xác trong việc đánh giá kết quả.
Bên cạnh đó, các hệ thống tự động chấm thi trắc nghiệm chủ yếu được nhập từ nước
ngoài với giá thành rất cao, có cấu trúc cồng kềnh nên việc di chuyển kém linh hoạt
và gặp nhiều khó khăn. Hơn nữa, các máy chấm tự động chỉ được sử dụng trong các
7
8
Tính ổn định và độ chính xác cao của hệ thống làm cho máy OMR có được độ
tin cậy cao và thường được sử dụng ở những tổ chức giáo dục và đánh giá lớn.
Nhưng những tính năng này cũng tạo nên giá thành cao của hệ thống và cản trở
việc phổ biến máy OMR trên thị trường. Không những giá thành của chúng rất đắt
mà chi phí vận hành phải đi đôi với việc tiêu thụ rất nhiều giấy chuyên dụng. Do đó,
những tổ chức giáo dục vừa và nhỏ, những trường học muốn tổ chức những kỳ thi
trắc nghiệm riêng của họ để tiến hành đánh giá học sinh, sinh viên định kỳ lại không
đủ chi phí mua cũng như duy trì những chiếc máy như thế này.
2.2 Phần mềm OMR
Trong khi những chiếc máy OMR làm chủ công nghệ và thị trường phục vụ
nhu cầu đánh giá kỳ thi trắc nghiệm thì vẫn tồn tại những nhu cầu về một thiết bị
nhỏ gọn hơn mà thỏa mãn được những yêu cầu về độ ổn định và độ chính xác cao.
Phần mềm OMR được phát triển nhanh chóng nhằm lấp đầy những nhu cầu
trên. Sự ra đời của phần mềm OMR kết hợp với máy scan thực sự đã là một giải
pháp thay thế cho việc chấm thi trắc nghiệm tự động. Đây là một giải pháp phần
mềm, để thực hiện chấm thi được cần phải kết hợp với một hệ thống máy tính và
máy scan.
Máy scan là một loại thiết bị văn phòng phổ biến và sẵn có với đa dạng
chủng loại cùng giá thành trên thị trường. Có hai loại máy scan cơ bản mà chúng ta
cần chú ý khi kết hợp với phần mềm OMR.
Máy scan ép phẳng (flatbed scanner) dùng để quét những tài liệu nhỏ lẻ
hoặc những mẫu đơn rời. Nhược điểm của loại máy scan này là người sử dụng phải
thao tác bằng tay khi họ muốn scan tài liệu. Điều này đồng nghĩa với tính tự động
và tốc độ của hệ thống chấm thi sử dụng máy scan ép phẳng sẽ rất thấp.
Máy scan tời giấy tự động (automatic document feeder – ADF) là dòng
máy scan chuyên nghiệp hơn. Máy ADF có thêm khay tời giấy tự động có thể đựng
đuợc 50 tới 200 tờ giấy và scan lần lượt theo thời gian định sẵn. Khi kết hợp ADF
số sẽ áp dụng để thực hiện đề tài.
Chương 2: Phân tích và thiết kế hệ thống chấm thi trắc nghiệm bằng camera
Đề xuất và thiết kế hệ thống chấm thi trắc nghiệm bằng camera. Phân tích
thuật toán chấm thi trắc nghiệm đã đề xuất.
Chương 3: Đánh giá kết quả thực hiện
10
Thực nghiệm và đánh giá kết quả đạt được với thuật toán đã đề xuất bằng
phần mềm được lập trình theo thiết kế ở chương 2.
4. Kết quả đạt được
Bằng phương pháp thực nghiệm, phần mềm chấm điểm trắc nghiệm bằng
camera đã hoàn thành và đáp ứng các các yêu cầu đặt ra:
•
•
•
•
Module quản lý kỳ thi nhỏ, gọn, trực quan.
Hiển thị hình ảnh từ camera và chấm điểm.
Chấm điểm với nhiều file ảnh phiếu thi chụp từ trước.
Thực nghiệm cho thấy thuật toán đã đề ra đạt độ chính xác 100% với các
mẫu phiếu thi đã chuẩn bị, thời gian chấm thi nhanh.
Để có thể thực hiện và hoàn thành đề tài này, tôi xin được chân thành cảm ơn
PGS.TS. Nguyễn Tiến Dũng đã tận tình hướng dẫn và giúp đỡ trong suốt quá trình
thực hiện đề tài.
Mặc dù đã cố gắng và nỗ lực hết mình để hoàn thành luận văn, song chắc
chắn không thể tránh khỏi những sai sót và hạn chế. Vì vậy, tôi rất mong sẽ nhận
ảnh số gần như ảnh thật.
1
Độ xám
Mỗi một điểm ảnh sẽ được đặc trưng bởi hai tham số chính về không gian và
độ xám. Trong khuôn khổ ảnh hai chiều, tham số không gian được xác định bởi tọa
độ Descartes (x,y) của điểm ảnh đó. Tham số độ xám được xác định là giá trị cường
độ sáng tại điểm đó. Máy tính thường sử dụng đơn vị byte (8bit) để biểu diễn giá trị
số. Chính vì vậy, giá trị lớn nhất của độ xám thường được sử dụng rộng rãi nhất là
28 = 256 tương đương với việc cường độ sáng của các điểm sẽ nằm trong dải từ 0
12
đến 255, khi đó, máy tính sẽ dùng 8bit = 1byte để biểu diễn giá trị cường độ sáng.
Ngoài ra, còn có các giá trị cường độ sáng lớn nhất khác: 16, 32, 64, 128,…
Thông thường, ta sẽ làm quen với 3 loại ảnh sau dựa vào cấu trúc cũng như độ
xám điểm ảnh:
• Ảnh màu: là ảnh mà màu của các điểm ảnh được tạo nên bởi sự pha trộn 3
màu cơ bản (hệ màu RBG: Red Blue Green) với các tỉ lệ cường độ sáng
khác nhau. Với mỗi một màu cơ bản, người ta sẽ sử dụng một byte để biểu
diễn cường độ sáng, chính vì vậy cần 3byte (24bit) để biểu diễn một điểm
ảnh. Khi đó giá trị màu sẽ nhận giá trị từ 0 cho đến 2 24 (vào khoảng ≈16,7
triệu màu).
• Ảnh đen trắng (ảnh xám): là ảnh mà mỗi điểm ảnh chỉ có hai màu đen,
trắng (không chứa màu khác) với cường độ sáng (mức xám) ở các điểm ảnh
có thể sử dụng nhiều bit để biểu diễn các giá trị khác nhau.
• Ảnh nhị phân: là ảnh chỉ có hai màu đen, trắng (không chứa màu khác) với
cường độ sáng chỉ có 2 giá trị duy nhất 0 và 255. Người ta dùng duy nhất 2
(1.2)
Khác với nhiễu nhân và nhiễu cộng, nhiễu xung thường chỉ gây đột biến tại
một số điểm ảnh. Nhiễu xung là một loại nhiễu khá đặc biệt có thể sinh ra bởi nhiều
lý do khác nhau chẳng hạn: lỗi truyền tín hiệu, lỗi bộ nhớ, hay lỗi định thời trong
quá trình lượng tử hóa.
1.2. Những kỹ thuật xử lý ảnh cơ bản
3
Lấy mẫu và lượng tử hóa
1
Lấy mẫu
Lấy mẫu (sampling) là một quá trình, qua đó ảnh được tạo nên trên một vùng
có tính liên tục được chuyển thành các giá trị rời rạc theo tọa độ nguyên. Quá trình
này gồm 2 lựa chọn:
• Một là: khoảng lấy mẫu.
• Hai là: cách thể hiện dạng mẫu.
Lựa chọn thứ nhất được đảm bảo nhờ lý thuyết lấy mẫu của Shannon. Lựa
chọn thứ hai liên quan đến độ đo (Metric) được dùng trong miền rời rạc.
Khoảng lấy mẫu (Sampling Interval)
Ảnh lấy mẫu có thể được mô tả như việc lựa chọn một tập các vị trí lấy mẫu
trong không gian hai chiều liên tục. Đầu tiên mô tả qua quá trình lấy mẫu một chiều
với việc sử dụng hàm
(1.3)
(1.4)
Điều kiện khôi phục ảnh lấy mẫu về ảnh thật được phát biểu từ định lý lẫy
mẫu của Shannon.
Định lý lấy mẫu của Shannon[2]
Giả sử g(x) là một hàm giới hạn dải (Band Limited Function) và biến đổi
Fourier của nó là G(ωx) = 0 đối với các giá trị ωx>Wx. Khi đó g(x) có thể được khôi
phục lại từ các mẫu được tạo tại các khoảng Δx đều đặn. Tức là:
(1.11)
Định lý lẫy mẫu của Shannon có thể mở rộng cho không gian hai chiều. Hàm
răng lược hai chiều khi đó được xác định:
(1.12)
Hàm lấy mẫu hai chiều thu được:
(1.13)
và Δx, Δy được chọn thoả mãn các điều kiện tương ứng theo định lý lấy mẫu
của Shannon khi đó:
(1.14)
(1.15)
Tương tự như không gian một chiều, một tín hiệu ảnh hai chiều g(x,y) có thể
xấp xỉ trong khoảng [N, M] có thể được ước lượng như sau :
g(x,y)≈g(n∆x,m∆y)
15
={g(0,0),g(0,1),…,g(0,M-1),g(1,0),g(1,1),…,g(1,M1,),g(N-1,M-1)}
Các dạng lấy mẫu (Tesselation)
(1.16)
Dạng lẫy mẫu (Tesselation) điểm ảnh là cách bài trí các điểm mẫu trong không
gian hai chiều. Một số dạng mẫu điểm ảnh được cho là dạng chữ nhật, tam giác, lục
giác. Mỗi một mẫu, ngoài việc thể hiện hình dáng còn cho biết đặc điểm liên thông
sai số của quá trình lấy mẫu có thể được xác định theo:
eq=li – Z
Hình 1.4 Lấy mẫu và lượng tử hóa
4
Xứ lý và nâng cao chất lượng ảnh
17
(1.17)
Nâng cao chất lượng ảnh là một bước quan trọng, tạo tiền đề cho xử lý ảnh.
Mục đích chính là nhằm làm nổi bật một số đặc tính của ảnh như thay đổi độ tương
phản, lọc nhiễu, nổi biên, làm trơn biên ảnh, khuếch đại ảnh… Tăng cường ảnh và
khôi phục ảnh là hai quá trình khác nhau về mục đích. Tăng cường ảnh bao gồm
một loạt các phương pháp nhằm hoàn thiện trạng thái quan sát của một ảnh. Tập
hợp các kỹ thuật này tạo nên giai đoạn tiền xử lý ảnh. Trong khi đó, khôi phục ảnh
nhằm khôi phục ảnh gần với ảnh thực nhất trước khi nó bị biến dạng do nhiều
nguyên nhân khác nhau. Sau đây ta tìm hiểu một số kỹ thuật tăng cường ảnh.
1
Tăng độ tương phản
Trước tiên cần làm rõ khái niệm độ tương phản; ảnh số là tập hợp các điểm,
mà mỗi điểm có giá trị độ sáng khác nhau. Ở đây, độ sáng để mắt người dễ cảm
nhận ảnh song không phải là quyết định. Thực tế chỉ ra rằng hai đối tượng có cùng
độ sáng nhưng đặt trên hai nền khác nhau sẽ cho cảm nhận khác nhau. Như vậy, độ
tương phản biểu diễn sự thay đổi độ sáng của đối tượng so với nền. Với định nghĩa
khác nhau, so sánh chúng để tìm ra sự khác nhau. Người ta dóng thẳng hai ảnh rồi
trừ đi và thu được ảnh mới. Ảnh mới này chính là sự khác nhau. Kỹ thuật này hay
được dùng trong dự báo thời tiết và trong y học.
5
Lấy ngưỡng
Lấy ngưỡng là một kỹ thuật xử lý ảnh cơ bản dùng đển chuyển từ ảnh mức
xám hoặc ảnh màu sang ảnh nhị phân khi so sánh cường độ điểm ảnh với giá trị
ngưỡng cho trước. Lẫy ngưỡng thực sự là một công cụ mạnh để giữ lại những phần
có nghĩa của bức ảnh mà bỏ đi những phần ít có ý nghĩa hoặc nhiễu. Hình 2.1 thể
hiện quá trình biến đổi ảnh mức xám sang ảnh nhị phân bằng cách lấy mẫu qua biểu
đồ cường độ mức xám.
19
Hình 1.7 Lấy ngưỡng
Có rất nhiều phương pháp lấy ngưỡng được áp dụng giúp việc lấy ngưỡng
hiệu quả.Trong đó, thuật toán Otsu được sử dụng rộng rãi nhất do sự chính xác,
hiệu quả do thuật toán tính ngưỡng T một cách tự động (adaptive) dựa vào giá trị
điểm ảnh của ảnh đầu vào, nhằm thay thế cho việc sử dụng ngưỡng cố định:
• Chọn một ngưỡng ước đoán ban đầu T
• Phân đoạn ảnh sử dụng T. Quá trình này tạo ra 2 nhóm pixel:
o bao gồm tất cả pixel có giá trị độ xám nhỏ hơn T.
o bao gồm tất cả pixel có giá trị độ xám lớn hơn T.
• Tổng xác suất xuất hiện của mỗi giá trị độ xám (xác suất tích lũy) trong mỗi
nhóm điểm ảnh được tính toán bởi công thức:
(1.19)
(1.20)
σb (T) = qN1(T) * [ μ1(T) - μ ] + qN2(T) * [ μ2(T) - μ ]
(1.27)
2
2
σb (T) = qN1(T) * qN1(T) * [ μ1(T) - μ2(T) ]
(1.28)
Thuật toán sẽ chạy trên toàn dải của giá trị ngưỡng [1-NG], mức ngưỡng tối
ưu nhất là mức ngưỡng cho giá trị The weighted within-class variance σw2(T) nhỏ
nhất, hay giá trị The between-class variance σb2(T) lớn nhất.
6
Những bộ lọc không gian
Cải thiện ảnh là làm cho ảnh có chất lượng tốt hơn theo ý đồ sử dụng. Thường
là ảnh thu nhận có nhiễu cần phải loại bỏ nhiễu hay ảnh không sắc nét bị mờ hoặc
cần làm tõ các chi tiết như đường biên ảnh. Để làm trơn nhiễu hay tách nhiễu, người
ta sử dụng các bộ lọc tuyến tính (lọc trung bình, thông thấp) hay lọc phi tuyến
(trung vị, giả trung vị, lọc đồng hình). Từ bản chất của nhiễu (thường tương ứng với
tần số cao) và từ cơ sở lý thuyết lọc là: bộ lọc chỉ cho tín hiệu có tần số nào đó
thông qua do đó, để lọc nhiễu người ta thường dùng lọc thông thấp (theo quan điểm
tần số không gian), lọc thông thấp làm suy giảm hoặc loại trừ các thành phần tần số
cao trong miền Fourier và cho các tần số thấp đi qua. Các thành phần tần số cao đặc
trưng cho các biên, các chi tiết làm nét trong ảnh, do đó hiệu quả của bộ lọc thông
thấp là làm nhòe ảnh. Hoặc lấy tổ hợp tuyến tính để san bằng (lọc trung bình).
Trong khi đó, bộ lọc thông cao làm suy giảm các thành phần tần số thấp. Các thành
phần này thể hiện qua các đặc trưng thay đổi chậm của ảnh như độ tương phản và
cường độ sánh trung bình. Hiệu quả chung của các bộ lọc thông cao là làm rõ các
biên và chi tiết.
1
các pixel của ảnh gốc chúng ta sẽ thu được ảnh kết quả qua bộ lọc Mean. Bộ lọc
Mean có vai trò làm trơn ảnh, nhưng lại làm mờ đường biên của các đối tượng bên
trong ảnh, làm mất tín hiệu cận nhiễu và không lọc được nhiễu xung.
Vì thế trong lọc trung bình, thường người ta phải ưu tiên cho các hướng để
bảo vệ biên của ảnh khỏi bị mờ khi làm trơn ảnh. Các kiểu mặt nạ được sử dụng
tùy theo các trường hợp khác nhau. Bộ lọc trên có thể hiểu là bộ lọc tuyến tính
theo nghĩa là điểm ảnh ở tâm cửa số sẽ được thay bởi tổ hợp các điểm lân cận chập
với mặt nạ. Một bộ lọc trung bình không gian khác cũng hay được sử dụng. Phương
trình của bộ lọc đó có dạng:
22
(1.32)
Ở đây, nhân chập H có kích thuớc 2x2 và mỗi điểm ảnh kết quả có giá trị bằng
trung bình cộng của nó với trung bình cộng của 4 lân cận gần nhất. Lọc trung bình
trọng số là một trường hợp riêng của lọc thông thấp.
b. Lọc thông thấp (Low Pass Filter)
Lọc thông thấp thường được sử dụng để làm trơn nhiễu.Về nguyên lý của bộ
lọc thông thấp tương tự như đã trình bày ở bộ lọc Mean. Trong kỹ thuật này người
ta hay dùng một số nhân chập có dạng sau:
=
(1.33)
Dễ dàng nhận thấy khi b=1, chính là hàm truyền đạt của mạch lọc trung bình.
Để hiểu rõ hơn bản chất khử nhiễu cộng của các bộ lọc này, ta viết lại phương trình
thu nhận ảnh dưới dạng:
=+η
(1.34)
Hình 1.8 Ảnh trước và sau bộ lọc Median
Do đó về nguyên lý thì mạch Median có thể tách được các điểm có cường độ
sáng lớn như nhiễu xung và lọc các điểm có cường độ sáng tức thì (xung) hay còn
gọi là các nhiễu muối tiêu. Lọc trung vị có lợi cho việc loại bỏ các điểm ảnh hay các
hàng mà vẫn bảo toàn độ phân giải. Hiệu quả giảm khi số điểm trong cửa sổ lớn hay
bằng một nửa số điểm trong cửa sổ. Điều này dễ giải thích vì trung vị là (Nw+1)/2
giá trị lớn nhất nếu Nw-số điểm ảnh trong cửa sổ lọc W là lẻ. Lọc trung vị cho
trường hợp 2 chiều coi như lọc trung vị tách được theo từng chiều.
b. Lọc ngoài (Outlier Filter)
Giả thiết có ngưỡng nào đó cho các mức nhiễu (có thể dựa vào lược đồ xám).
Tiến hành so sánh giá trị độ xám của một điểm ảnh với trung bình số học 8 lân cận
của nó. Nếu sai lệch lớn hơn ngưỡng, điểm ảnh này được coi như nhiễu. Trong
trường hợp đó, thay thế giá trị của điểm ảnh bằng giá trị trung bình 8 lân cận vừa
tính được. Bộ lọc ngoài có thể diễn tả bằng công thức sau:
(1.39)
trong đó:
α(w) là trung bình cộng các điểm trong lân cận W
δ là ngưỡng ngoài
24
Các cửa sổ tính toán thường chọn là 3x3. Tuy nhiên, cửa sổ có thể mở rộng
đến 5x5 hay 7x7 để đảm bảo tính tương quan giữa các điểm ảnh. Vấn đề quan trọng
là xác định ngưỡng để loại nhiễu mà vẫn không làm mất thông tin của ảnh.
1.3. Kỹ thuật xử lý ảnh nhị phân
Với ảnh nhị phân, mức xám chỉ có hai giá trị là 0 và 1. Do vậy, ta xét một
phần tử ảnh như một phần tử logic và có thể áp dụng các phép toán hình học
(Morphology Operators) dựa trên khái niệm biến đổi hình học của một ảnh bởi một
Copyright: Tài liệu đại học ©