HỌC

VIỆN

CÔNG

NGHỆ

BƯU

CHÍNH

VIỄN

THÔNG
PHÂN

ĐOẠN

ẢNH

ĐA

CẤP

XÁM

VÀ

ẢNH

MÀU Chuyên

ngành:

KHOA

HỌC


HÀ NỘI - 2013
Luận văn được hoàn thành tại:
HỌC

VIỆN

CÔNG

NGHỆ

BƯU

CHÍNH

VIỄN


Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 PHẦN

MỞ

ĐẦU

phân đoạn theo ngưỡng, phân đoạn theo miền đồng nhất và cuối cùng phân

đoạn theo đường biên

Luận văn được bố trí theo các phần như sau:

Chương 1
: Tổng quan về xử lý ảnh chương này giới thiệu chung bộ môn xử lý

ảnh và giới thiệu về phương pháp phân đoạn ảnh

Chương 2:
Phương pháp phân đoạn ảnh dựa vào ngưỡng biên độ

Chương này trình bày phương pháp phân đoạn ảnh dựa vào ngưỡng, một số kỹ

thuật chọn ngưỡng dựa trên lược đồ xám – Histogram, phương pháp sử dụng

tập mờ, độ ổn định thông tin (sử dụng entropy).

Chương 3 :
Phương pháp phân đoạn ảnh dựa theo miền đồng nhất
2

Chương này trình bày một số phương pháp phân đoạn ảnh dựa vào miền đồng


LÝ

ẢNH
1.1

Giới

thiệu

về

xử

lý

ảnhXử lý ảnh là một lĩnh vực đang được quan tâm nghiên cứu và có nhiều

ứng dụng quan trọng trong thực tế cùng với sự phát triển của công nghệ thông

tin, thúc đẩy các ngành kinh tế, xã hội khác phát triển. Mục đích chính của xử

lý ảnh có thể nêu ra như sau:

 Xử lý ảnh ban đầu để có được ảnh mới theo một yêu cầu xác định (Ví dụ


Tuy nhiên trong nhiều quá trình hình thành ảnh, độ lớn của tín hiệu là kết quả

đếm số hạt photon ở từng thời điểm, do vậy độ lớn ấy dĩ nhiên đã được lượng

hoá sẵn. Còn trong một số quá trình tạo ảnh khác, ví dụ như tạo ảnh siêu âm
4trong

y

khoa,

phương

pháp

đo

đạc

vật

lý



một

giá

trị

độ

lớn

kết

hợp

với

một

giá

trị

pha,

và

cả

hai

lý

ảnh.Quá

trình

xử

lý

một

ảnh

số

đầu

vào

nhằm

thu

được

một

1.1

giới

thiệu

nhữngbước

cơ

bản

của

quá

trình

đó.

Phân

đoạn



Thu

nhận

ảnh
CƠ

SỞ

TRI

THỨC
Nhận

Trong

hình

1.1,

để

hoàn

thành

được

mục

tiêu

xử

lý

cụ

thể

ứng



nghĩa,

công

cụ,thuật

toán,

kỹ

thuật

vốn

đã

được

phát

triển

và

cải


Trong

xử

lý

ảnh,

công

việc

đầu

tiên

là

thu

nhận

ảnh
,

trong

sơ

đồ

cần

có

một

bộ

cảmbiến

lấy

ảnh

và

khả

năng

số

hoá

các

tín


xử

lý

ảnhđó. Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khử bóng,

khử độ lệch, v.v với mục đích làm cho chất lượng ảnh trở nên tốt hơn nữa,

chuẩn bị cho các bước xử lý phức tạp hơn về sau trong quá trình xử lý ảnh.

Bước thứ ba trong quá trình xử lý ảnh thường là bước
phân

đoạn

ảnh
. Có

thể nói, phân đoạn ảnh là việc chia một ảnh đầu vào thành nhiều phần con khác

nhau hay còn gọi là các đối tượng. Việc phân đoạn tự động thành những tập đối

tượng khác nhau là nhiệm vụ phức tạp nhất trong xử lý ảnh số hoá. Nếu kết quả

phân đoạn ảnh chỉ dừng lại được ở mức độ thô thiển, thì toàn bộ những bước xử


hay

trích

chọn

đặc

trưng
đề cập đến sự rút trích từ ảnh những đặc trưng cần thiết
6

dẫn đến sự hình thành các thông tin định lượng liên quan đến những đặc trưng

đó.

Bước cuối cùng trong sơ đồ đã nêu ra ở hình 1.1 là
nhận

dạng
và
giảithích
. Nhận dạng là công đoạn gán nhãn cho một đối tượng dựa trên thông tin


Ngoài những bước đã nêu trên, trong các hệ thống xử lý ảnh còn có một

công việc nữa đó là hiển thị ảnh, cũng là một bài toán phức tạp. Yêu cầu hiển

thị ảnh có thể được đưa ra ở bất kỳ một bước xử lý nào trong sơ đồ ở hình 1.1.

Một vấn đề nữa là không phải ứng dụng xử lý ảnh nào cũng cần phải thực hiện

đầy đủ tất cả các bước đã nêu, ví dụ như các ứng dụng chỉnh sửa ảnh nghệ thuật

chỉ dừng lại ở bước tiền xử lý. Một cách tổng quát thì những chức năng xử lý

bao gồm cả nhận dạng và giải thích thường chỉ có mặt trong những hệ thống
7

phân tích ảnh tự động hoặc bán tự động, được dùng để rút trích ra những thông

tin quan trọng từ ảnh, ví dụ như các ứng dụng nhận dạng ký tự.

1.3

Giới

thiệu

sơ8CHƯƠNG

2

:

PHƯƠNG

PHÁP

PHÂN

ĐOẠN

ẢNH

DỰAVÀO

NGƯỠNG

BIÊN


ảnh

đó

là

biên

độ

của

cáctính

chất

vật

lý

của

ảnh,

như:


đó,

khi

biên

độ

là

đặc

tính

đặc

trưng

cho

ảnh,

ta

có

thể

dùng



hồng

ngoại

có

thểphản

ánh

vùng

có

nhiệt

độ

thấp

hay

vùng

có


đầu

tiên

là

chọn

một

ngưỡng

độc

lập

với

dữ

liệu

ảnh.

Nếuchúng

ta
tương

phản

rất

cao,

trong

khi

đó,

các

đối

tượng

quan

tâm

rất

tối



bằng

128

trên

thang

độsáng

từ

0

đến

255

sẽ

là

một

giá



tiểu.2.3

Chọn

ngưỡng

dựa

trêm

lược

đồ

(histogram)Trong

hầu

hết

các

trường

phân

đoạn.

Có

rất

nhiều

kỹ

thuật

chọn

ngưỡng

tự

động

xuấtphát

từ

lược


Tuy

nhiên

cácthuật

toán

làm

trơn

cần

phải

cẩn

thận,

không

Kết

quả



dịch

chuyển

các

vị

trí

đỉnhcủa

lược

đồ.

Nhận

xét

này

dẫn

đến


W


1)

/

2



h
raw

w

(
W


1)

/

2
[
b

liệuĐây là kỹ thuật chọn ngưỡng theo kiểu lặp do Ridler và Calvard đưa ra.

Trước hết, lược đồ sẽ được phân đoạn thành hai phần bằng một giá trị ngưỡng

khởi động như 0=2
B-1
, tức là bằng phân nửa thang độ xám động của ảnh. Sau

đó, các trung bình mẫu (mf,0) của những điểm ảnh thuộc đối tượng và (mb,0) của

những điểm ảnh nền sẽ được tính toán. Một giá trị ngưỡng mới 1 sẽ được tính

kế đó bằng cách lấy giá trị trung bình của hai trung bình mẫu nói trên. Quá trình

này cứ thế sẽ được tiếp tục với ngưỡng mới cho đến khi nào giá trị ngưỡng

không thay đổi nữa thì dừng lại. 2.3.2

Thuật

toán

đối

2.3.3

Thuật

toán

tam

giácThuật toán này làm như sau: Nối đường thẳng  từ điểm Hmax của lược đồ

(điểm có histogram lớn nhất, có mức xám bmax) đến điểm Hmin của lược đồ
10(điểm

ứng

với

độ


],

chúng

ta

đi

tính

khoảng

cách

d

từ

điểm

H
b

của

lược

đồ

(ứng

khoảng

cách

d

lớn

nhất

sẽ

được

chọn

làm

giátrị

ngưỡng

T.
2.3.4

cực

tiểu

địa

phương

của

histogram

nằmgiữa

hai

đỉnh

của

histogram.

Điểm

cực

đại

dụng

biến

đổi

chóp

mũ

(top

hat)

do

Meyerđưa

ra:

Phụ

thuộc

vào

tình

nền

tối

hay

đối

tượng

tối

trên

nền

sáng

mà

phép

biến

đổi

top

hat


A
,

B
)



A



(

A



B
)



A



max(min

(


A



(

A



B
)



A



min

(max(

A
))

B

B

histogram

thì

khó

nếuhistogram

nhiễu.Trong

một

số

ứng

dụng

nhất

định,

cường



ảnh

có

thể

không

chứa

hai

thuỳphân

biệt

rõ

ràng,

vì

vậy

có



khối

hình

vuông,

histogram

và

ngưỡng

đượctính

cho

mỗi

khối

tương

ứng.

Nếu



suy

ngưỡng

của

các

khối

lánggiềng.

Khi

ngưỡng

cục

bộ

đã

có

thì


2.4

Phương

pháp

sử

dụng

entropyEntropy là một phép đo nội dung của ảnh.

2.5

Phương

pháp

sử

dụng

tập

mờ

(fuzzy

PHÁP

PHÂN

ĐOẠN

ẢNH

THEOMIỀN

ĐỒNG

NHẤT3.1

Giới

thiệuKỹ thuật phân đoạn ảnh thành các miền đồng nhất dựa vào các thuộc tính

quan trọng nào đó của miền. Mỗi một thuộc tính khi sử dụng thì có một tiêu

chuẩn phân đoạn tương ứng. Một số thuộc tính tiêu biểu là: mức xám, màu sắc
Phương pháp này kiểm tra tính hợp thức của tiêu chuẩn đồng nhất một

cách tổng thể trên miền lớn. Nếu tiêu chuẩn được thoả việc phân đoạn coi như

kết thúc. Trong trường hợp ngược lại ta chia miền đang xét thành 4 miền nhỏ

hơn, ta lại áp dụng đệ quy bằng phương pháp trên cho mỗi miền nhỏ hơn cho

đến khi tất cả các miền đều thoả mãn.

3.3

Các

phương

pháp

tách

bởi

hợpÝ tưởng của phương pháp này là xem xét ảnh từ các miền nhỏ nhất rồi

hợp chúng lại nếu thoả tiêu chuẩn để được một miền đồng nhất lớn hơn. Ta lại

theo hướng từ gốc đến lá. Tiếp theo tiến hành duyệt cây theo chiều ngược lại và

hợp các vùng có cùng tiêu chuẩn. Với phương pháp này ta thu được miêu tả cấu

trúc của ảnh với các miền liên thông có kích thước tối đa 3.4.1

Thuật

toán

tô

màu.Thuật toán này sử dụng khái niệm 4 liên thông. Người ta dùng một cửa sổ

di chuyển trên ảnh để so sánh với tiêu chuẩn hợp. 3.4.2

Thuật

toán

đệ

trên

lý

thuyết

đồ

thị.3.5.1

Giới

thiệu.Phân đoạn ảnh dựa vào đồ thị là một phương pháp phân đoạn dựa trên

thuộc tính toàn cục (non-local) của ảnh đầu vào. Phương pháp này phát hiện ra

biên giữa hai vùng của ảnh bằng cách so sánh sự khác nhau giữa nội vùng

(inter-component) với sự khác nhau với các vùng khác. Thuật toán phân đoạn

dựa vào đồ thị tuân theo chiến lược tham lam, có thời gian chạy gần như tuyến

tính, nhưng vẫn đảm bảo được việc phân đoạn chính xác và hiệu quả.



lý

thuyết

đồ

thị

và

phân

đoạn

dựa

trên

lý

thuyếtđồ

thị.3.5.2.1

đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi

hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.[10]

b) Đồ thị liên thông.
15

Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu luôn tìm được

đường đi giữa hai đỉnh bất kỳ của nó.

3.5.2.2

Phân

đoạn

dựa

vào

lý

thuyết

đồ



toán.3.5.3.1

Cơ

sở

lý

thuyết.Thuật toán phân đoạn dựa trên đồ thị gần với thuật toán Kruskal xây dựng

cây tỏa nhánh tối thiểu (hay còn gọi là cây khung nhỏ nhất) của một đồ thị.

3.5.3.2

Tính

chất

của

so

sánh

(
C
1

,

C
2

)


(3.14)

16Int
(
C
)


max

w
(

2



V,là

trọng

số

nhỏ

nhất

của

các

cạnh

nối

giữa

hai

điểm


v
i


C
1

,

v

j


C

2

,

(

v
i

,

v



C
2

thì

đặtDif

(
C
1

,

C
2

)





.


=

(V,E),

gồm

n

đỉnh

và

m

cạnh.Output:

Một

phân

đoạn

của

V


0:

Sắp

xếp

các

cạnh

của

G

theo

thứ

tự

không

giảm

của

trọng

số.



với

phân

đoạn

S
0
,

lúc

này

mỗi

đỉnh

nằm

trong

một

thànhphần.


Xây

dựng

S
q

từ

S
q-1

như

sau:

Cho

v
i

và

v
j

là

hai


).

Nếu

v
i

và

v
j

nằm

trong

hai

thành

phần

tách

rời

nhau

của



hai

thành

phần

này

với

nhau,

ngược

lại

không

làm

gì

cả.

Cụ

thể,

gọi


phần

của

S
q-1

chứa

v
j
.

NếuC
i
q

1



C

qj

1

)

thì

S
q

thu

được

từ

S
q-1

bằng

cách

trộn

C
iq-1

vớiC
jq-1

S

=

S
m
.

17

CHƯƠNG

4:

PHƯƠNG

PHÁP

PHÂN

ĐOẠN

ẢNH

DỰA

+ Nhị phân hoá đường biên.

+ Miêu tả đường biên.

4.2

Cơ

sở

lý

thuyết

tách

biênTách biên là phương pháp thông dùng nhất để tách theo nghĩa gián

đoạn trong các giá trị cường độ. Sự gián đoạn được tách sử dụng đạo hàm bậc

nhất và đạo hàm bậc hai. Đạo hàm bậc nhất lựa chọn trong xử lý ảnh là gradient

Có nhiều định nghĩa về đường biên, điển hình có ba loại đường biên

chính:


(
i
,

j
)



g
y(
i
,

j
)

18+

Đường

Định

nghĩa

toán

học

của

biên

ở

trên

là

cơ

sở

cho

các

kỹ



là

nhỏ,

trong

khiđó

biến

thiên

độ

sáng

của

điểm

biên

(khi

qua



dò

biên

cục

bộ

dựa

vào

cực

đại

củađạo

hàm.

Gradient

là

một



ảnh

theo

hai

hướng

x

và

y.Trong

phương

pháp

gradient,

người

ta

chia


Kỹ

thuật

gradient

dùng

toán

tử

gradient,

lấy

đạo

hàm

theo

một

hướng.+

Kỹ
Nam,

Đông,

Tây,

và

Đông

Bắc,

Tây

Bắc,

Đông

Nam,

Tây

Nam.4.2.1.1

Kỹ


trực

giao

(theo

haihướng

vuông

góc).

Gọi:+

g
x

là

gradient

theo


của

gradient

tại

điểm

(i,j)

ký

hiệu

là

g(i,j)

được

tính

theocông

thức:

j

)



arctan(g

x

(
i

,

j

)

g

y

(
i


tử

biên

prewitt4.2.1.1.3

Toán

tử

biên

Roberts4.2.1.2Toán

tử

la

bànToán

tử


đồng

hồ.4.2.1.3

Toán

tử

laplaceCác

phương

pháp

đánh

giá

gradient

làm

việc

mức

xám

thay

đổi

chậm,

miền

chuyển

tiếp

trải

rộngthì

phương

pháp

đánh

giá

trường

hợp

này,

đó

là

phương

pháp

Laplace.

Đó

là

phương

phápsử

dụng

đạo


biên

với

độ

rộng

chỉ

1

pixel.

Trong

phầntrên,

ta

thấy,

kỹ

thuật



độ

rộng

1

pixel.

Còn

với

các

kỹ

thuật

khác,

ví

dụ

như

kỹ

thuật

được

biênvới

độ

rộng

1

pixel.Khi

thực

hiện

đạo

hàm

một

ảnh,



cực

trị

cục

bộ

có

thể

coi

như

biên.

Dovậy

cần

tách

biệt



độ

rộng

biên

ảnh.

Một

trong

những

phương

pháp

hay

dùng

đó

là

phương

biênNhị phân hóa đường biên là giai đoạn then chốt trong quá trình trích chọn

vì nó xác định đường bao nào thực sự cần và đường bao nào có thể loại bỏ. Nói

chung, người ta thường nhị phân hóa đường biên theo cách thức làm giảm nhiễu

hoặc tránh hiện tượng kéo sợi trên ảnh. Điều này cũng giải thích tại sao phân

đoạn dựa theo biên có hiệu quả khi ảnh có độ tương phản tốt. Trong trường hợp

ngược lại, có thể sẽ bị mất một phần đường bao hay đường bao có chân, không

khép kín, v.v , do đó sẽ bất lợi cho biểu diễn sau này. Một phương pháp hay

được dùng là chọn ngưỡng thích nghi. Với cách chọn này, ngưỡng sẽ phụ thuộc

vào hướng của gradient nhằm làm giảm sự xoắn của biên. Đầu tiên, người ta

định ra một ngưỡng nào đó và sau đó sử dụng một hệ số sinh thích nghi thông

qua lời giải toán tử đạo hàm theo hướng tìm được để tinh chỉnh.

4.5

Miêu



đoạn thẳng, xấp xỉ đa thức .
214.6

Tách

biên

ảnh

màuĐơn

vị

tế

bào

của

ảnh

mà

từng

pixel

có

thông

số

khác

nhau.

Đối

với

ảnh

màu

từng

pixelsẽ


Đỏ

(R),

Xanhlá

(G)

và

Xanh

biển

(B)

[Thomas

1892].

Trong

mỗi

pixel



nhau

và

có

cường

độ

sáng

khác

nhau.

Thôngthường,

mổi

màu

cơ

bản



vậy

mỗi

pixel

chúng

ta

sẽ

có2
8

3

=

2
24

màu

(khoảng



256mức

xám

(tương

ứng

với

tám

bit)

như

vậy

ảnh

xám

hoàn

toàn



qua

tám

mặt

phẳng

bit

theođộ

xám.Trong

hầu

hết

quá

trình

xử

và

bỏ

qua

ảnh

hưởng

của

yếu

tố

màu

sắc.

Do

đó

bước

chuyển

từ



xử

lýảnh

vì

nó

làm

tăng

tốc

độ

xử

lý

là

giảm

mức


được

xem

như

là

sự

sắp

xếp

của

ba

ảnh

mức

xámmà

khi

cho


mộtảnh

màu

trên

màn

hìnhTrong

hệ

RGB,

các

điểm

ảnh

màu

được


chọn

tỷ

lệ

ba

màu

tạo

ra

các

màu

khác

nhau.Mô

hình

màu



một

bộ

sốMô

hình

màu

là

phương

pháp

cho

phép

định

nghĩa

màu



)HSV
–

(

Hue

–

Saturation

–

Value

)CMY –
(

Cyan

–

Magenta

có chiều lớn hơn. Để sử dụng được với các ảnh RGB la tính gradient của mỗi

thành phần màu rồi sau đó kết hợp với các kết quả.
23

CHƯƠNG

5:

KẾT

QUẢ

VÀ

ĐÁNH

GIÁ

THỰC

NGHIỆMTôi đã tiến hành cài đặt một số thuật tón phân đoạn ảnh được trình bày

trong luận văn. Các thuật toán quen thuộc sử dụng ngưỡng cố định, phát hiện