·       Câu hỏi loại 1 điểm:

Câu hỏi 1.1: Nhiễu ảnh do đâu mà có?

Trả lời:M  ình trả lời theo 2 cách, tùy theo các bạn lựa chọn:

Cách 1: Nhiễu trong nhiếp ảnh

-         Nhiễu do cảm biến bị nóng khi phơi sáng quá lâu

-         Nhiễu vùng tối gây ra do cấu trúc cảm biến khi thời chụp không đủ

-         Nhiễu do cảm biến thu tín hiệu sai khi đẩy độ nhạy sáng ISO lên cao

Cách 2:Theo trong tài liệu giáo trình

Nhiễu do các thiết bị quang học, lượng tử, và đôi khi do chính bản thân đối tượng. Do đó có 2 loại nhiễu cơ bản:

-         Nhiễu hệ thống: là nhiễu do thiết bị hoặc ảnh hưởng bởi nguồn sáng ngoại lai nào đó-> dễ khử

-         Nhiễu ngẫu nhiên: là các vết bẩn không có nguyên nhân->khó khử, phải có giải pháp phù hợp.

Câu 1.2: Tại sao ảnh thu nhận không tránh khỏi biến dạng hình học?

Trả lời: Ảnh thu được sau quá trình thu nhận ảnh thường không tránh khỏi biến dạng bởi các thiết bị quang học và điện tử, đôi khi do chính bản thân đối tượng.

Câu 1.3: Histogram là gì?

Trả lời: Histogram là biểu đồ tần suất, biểu đồ thể hiện cường độ ánh sáng(cho biết độ sáng của bức ảnh). Đó là đồ thị với trục hoành là độ sáng và trục tung là số lượng điểm ảnh ở độ sáng tương ứng.

Câu 1.4: Hãy nêu một số phần mềm xử lý ảnh mà em biết

Trả lời:

-         Adobe Photoshop CS5 Extended

-         Paint.NET

-         Photoscape

-         Picasa

-         Picnik

Câu 1.5: Đầu vào của hệ thống xử lý ảnh là gì?

Trả lời: Ảnh phải được thu nhận qua các thiết bị thu (như camera, máy chụp ảnh, từ vệ tinh hoặc ảnh chụp được quét từ máy quét ảnh). Ảnh sẽ được số hóa và tiếp tục được xử lý.

·       Câu hỏi loại 2 điểm

Câu hỏi 2.1: Nắn chỉnh biến dạng hình học là gì? Tại sao phải nắn chỉnh biến dạng hình học?

Trả lời:

Trong thực tế đối tượng khi được thu nhận bởi các thiết bị điện tử vàquang học thường không thể hiện được bản chất thực (nguyên thủy) của mìnhhay nói cách khác là bị biến dạng đi. Ví dụ: ảnh chụp cuốn sách thường cómột đầu to đầu nhỏ do cách đặt máy ảnh, ảnh chụp bề mặt trái đất từ vệ tinhbị méo do bề mặt cong của trái đất v.v.. Nắn chỉnh biến dạng nhằm hiệu chỉnh cáckhuyết điểm của đối tượng là khâu tiền xử lý quan trọng trong xử lý ảnh .Như vậy nắnchỉnh biến dạng ban đầu chỉ đơn thuần mang mục đích khắc phục các nhượcđiểm của ảnh do thiết bị thu nhận gây ra

Câu hỏi 2.2: Xử lý ảnh là gì? Hãy nêu hai mô hình biểu diễn ảnh cơ bản?

Trả lời:

Xử lý ảnh số là một loạt thao tác và phân tích ảnh bằng máy tính nhằm cải thiện chất lượng ảnh tốt hơn

Hai mô hình biểu diễn ảnh cơ bản

·        Mô hình Raster

Đây là cách biểu diễn ảnh thông dụng nhất hiện nay, ảnh được biểu diễn dưới dạng

ma trận các điểm (điểm ảnh). Thường thu nhận qua các thiết bị như camera, scanner. Tuỳ

theo yêu cầu thực thế mà mỗi điểm ảnh được biểu diễn qua 1 hay nhiều bít

Mô hình Raster thuận lợi cho hiển thị và in ấn

Một trong những hướng nghiên cứu cơ bản trên mô hình biểu diễn này là kỹ thuật

nén ảnh các kỹ thuật nén ảnh lại chia ra theo 2 khuynh hướng là nén bảo toàn và không bảotoàn thông tin nén bảo toàn có khả năng phục hồi hoàn toàn dữ liệu ban đầu còn nếu khôngbảo toàn chỉ có khả năng phục hồi độ sai số cho phép nào đó. Theo cách tiếp cận này ngườita đã đề ra nhiều quy cách khác nhau như BMP, TIF, GIF, PCX…

·        Mô hình Vector

Biểu diễn ảnh ngoài mục đích tiết kiệm không gian lưu trữ dễ dàng cho hiển thị và in

ấn còn đảm bảo dễ dàng trong lựa chọn sao chép di chuyển tìm kiếm… Theo những yêu

cầu này kỹ thuật biểu diễn Vector tỏ ra ưu việt hơn.

Trong mô hình vector người ta sử dụng hướng giữa các vector của điểm ảnh lân cận

để mã hoá và tái tạo hình ảnh ban đầu ảnh vector được thu nhận trực tiếp từ các thiết bị sốhoá như Digital hoặc được chuyển đổi từ ảnh Raster thông qua các chương trình số hoá .Công nghệ phần cứng cung cấp những thiết bị xử lý với tốc độ nhanh và chất lượng

cho cả đầu vào và ra nhưng lại chỉ hỗ trợ cho ảnh Raster.Do vậy, những nghiên cứu về biểu diễn Vector đều tập trung từ chuyển đổi từ

ảnh Raster.

Câu 2.3: xử lý ảnh là j? Nêu sơ đồ tổng quát của một hệ thống xử lý ảnh.

Trả lời:Xử lý ảnh :là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của xử lý ảnh có thể là một ảnh tốt hơn hoặc một kết luận.

Sơ đồ tổng quát của một hệ thống xử lý ảnh:

Câu 2.4: Các phép toán hình thái học cơ bản? Các tính chất

Trả lời:

Ai muốn xem chứng minh các tính chất thì vào trang web này nhé, vì dài và khó nên tớ chỉ copy ý chính thôiJ

http://www.scribd.com/doc/57688570/34/Cac-phep-toan-hinh-thai-c%C6%A1-b%E1%BA%A3n

Câu 2.5: xử lý ảnh là j? vấn đề nào trong xử lý ảnh là quan trọng nhất? tại sao?

Trả lời:

Phân tích ảnh là khâu quan trọng trong xử lý ảnh để tiến tới hiểu ảnh. Trong phân tích ảnh việc trích chọn đặc điểm là một bước quan trọng. Các đặc điểm của đối tượng tùy theo mục đích nhận dạng trong quá trình xử lý ảnh ví dụ như: đặc điểm không gian, đặc điểm biến đổi,  đặc điểm biên và đường biên.

Việc trích chọn các đặc điểm hiệu quả giúp cho việc nhận dạng các đối tượng ảnh chính xác với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm xuống.

·       Câu hỏi loại 3 điểm

Câu 3.1:

 a. Histogram ? Cân bằng Histogram?

            b. Khi nào ảnh sau khi cân bằng đạt cân bằng lý tưởng?

Trả lời:

a.       - Câu 1.3

-         Histogram ( Câu 1.3) – Bổ sung: Đó là một đồ thị với trục hoành là độ sáng và trục tung là số lượng điểm ảnh ở độ sáng tương ứng. Chiều cao của các cột đen trên histogram cũng thể hiện số lượng pixel ở mức sáng đó. Như vậy, khi nhìn vào độ cao của các "đỉnh núi" trên histogram, ta sẽ biết cách để điều chỉnh độ sáng tối cho phù hợp.

-         Cân bằng Histogram: Các vùng của Histogram được chỉnh để “ Cần đối bằng nhau” trong mức xám, kỹ thuật này được gọi là Cân bằng Histogram.

b.      Ảnh I được gọi là cân bằng “lý tưởng” nếu với mọi mức xám g, g’ ta có

                              h(g) = h(g’)

Chú ý : Ảnh sau khi thực hiện cân bằng chưa chắc đã là cân bằng “ lý tưởng”.

Câu 3.2:  (có ý tách ngưỡng trùng với câu 4.3a)

a.       Tách ngưỡng ? Tách ngưỡng tự động ?

b.      Khi nào ảnh không tách được ngưỡng ?

Trả lời:

a.        

-         Tách ngưỡng : Giả sử ta có ảnh I ~ kích thước m × n, hai số Min, Max và ngưỡng θ

Khi đó, kỹ thuật tách ngưỡng được thể hiện

I [i, j] = I [i, j] > = θ? Max: Min; ∀(i,j)

-         Tách ngưỡng tự động :Ngưỡng θ trong kỹ thuật tách ngưỡng thường được cho bởi người sử dụng. Kỹ thuật tìm tách ngưỡng tự động nhằm tìm ra ngưỡng θ một cách tự động dựa vào histogram theo nguyên lý trong vật lý là vật thể tách làm 2 phần nếu tổng độ lệnh trong từng phần là tối thiểu.

Tìm θ sao cho

Câu 3.3 :

a.       Lọc trung bình ?

b.      Khi nào ảnh sau khi lọc trung bình kết quả không thay đổi ?

Trả lời:

a.       Lọc trung bình là kỹ thuật lọc tuyến tính hoạt động như một bộ lọc thông thấp.Mục đích: san bằng ảnh, làm mịn ảnh, loại bỏ các thành phần nhiễu muối, tiêu. Ý tưởng: mỗi điểm ảnh được thay thế bằng tổng trọng số hay trung bình trọng số của các điểm lân cận với với mặt nạ.

Cho dãy x1, x2…, xn khi đó trung bình của dãy ký hiệu AV({xn}) ddược định nghĩa:

-         Kỹ thuật lọc trung bình :Giả sử ta có ảnh I, điểm ảnh P, cửa sổ W(P) và ngưỡng θ. Khi đó kỹ thuật lọc trungbình phụ thuộc không gian bao gồm các bước cơ bản sau:

+ Bước 1: Tìm trung bình

{I(q)| q € W(P)} → AV(P)

     + Bước 2: Gán giá trị

Câu 3.4:

a.       Lọc trung bình theo k giá trị gần nhất?

b.      Khi nào ảnh sau khi lọc trung bình theo k giá trị gần nhất có kết quả giống lọc trung bình?

Trả lời:

a.       Lọc trung bình theo k giá trị gần nhất:

Giả sử ta có ảnh I, điểm ảnh P, của sổ W(P), ngưỡng θ và số k. Khi đó, lọc trung bình theo k giá trị gần nhất bao gồm các bước sau:

·        Bước 1: Tìm K giá trị gần nhất

{I(q)|q∈W(p)}à{k~ giá trị gần I(P) nhất}

·        Bước 2: Tính trung bình

{k~ giá trị gần I(P) nhất}àAVk(P)

·        Bước 3: Gán giá trị

b.      Khi k lớn hơn kích thước cửa sổ thì ảnh sau khi lọc trung bình theo k giá trị gần nhất có kết quả giống lọc trung bình.

Câu 3.5:

a.       Các phép toán hình thái học cơ bản? Các tính chất?

b.      Khi nào phép giãn nở cho kết quả giống phép co trên cùng một ảnh?

Trả lời:

a.       Các phép toán hình thái học cơ bản:

Giả thiết ta có đối tượng X và phần tử cấu trúc ( mẫu) B trong không gian Euclide 2 chiều. Kí hiệu Bx là dịch chuyển của B tới vị trí x.

·        Phép giãn nở: Phép giãn nở của X theo mẫu B là hợp của tất cả các Bx với x thuộc X. Ta có:

·        Phép co: Phép co của X theo B là tập hợp tất cả các điểm x sao cho Bx nằm trong X. Ta có:

X ⊖ B = {x: Bx⊆ X}

·        Phép toán mở: Phép toán mở của X theo cấu trúc B là tập hợp các điểm của ảnh X sau khi đã co và giãn nở liên tiếp theo B. Ta có:

OPEN(X,B) = (X ⊖ B) ⊕ B

·        Phép toán đóng: Phép toán đóng của X theo cấu trúc B là tập hợp các điểm ảnh của X sau khi giãn nở và co liên tiếp theo B. Ta có:

CLOSE(X,B) = (X ⊕ B) ⊖ B

·        Các tính chất:

o       Tính gia tăng:

            X ⊖ B ⊆X’ ⊖ B                     ∀B

§        X ⊆X’ ⇒

                                                    X ⊕B ⊆ X’ ⊕B      ∀B

                         X ⊖ B ⊇ X ⊖ B'       ∀X

§        B ⊆ B' ⇒       

                        X ⊕B ⊆ X ⊕B’                      ∀X

o       Tính phân phối với phép  QUOTE   :

§        X ⊕(B ∪ B') = (X ⊕B) ∪ (X ⊕B')

§        X ⊖ (B ∪ B') = (X ⊖ B) ∩ (X ⊖ B')

o       Tính phân phối với phép  QUOTE   :

§        (X ∩ Y) ⊖ B = (X ⊖ B) ∩ (Y ⊖ B)

o       Tính kết hợp:

§        (X ⊕B) ⊕B' = X ⊕(B ⊕B')

§        (X ⊖ B) ⊖ B' = X ⊖ (B ⊕B')

o       X bị chăn bởi các cận OPEN và CLOSE:

§        (X ⊕B) ⊖ B ⊇X ⊇(X ⊖ B) ⊕B

o       Tính bất biến:

§        ((X ⊕B) ⊖ B) ⊕B = X ⊕B

§        ((X ⊖ B) ⊕B) ⊖ B = X ⊖ B

b.      Câu này tớ ko biết trả lời

·       Câu hỏi loại 4 điểm

Câu 4.1.b. Cân bằng Histogram cho ảnh sau với new_level = 3

1

2

3

4

5

6

2

1

2

3

4

5

3

2

1

2

3

4

5

3

2

1

2

3

6

5

3

2

1

2

Trả lời:

Ta có :

TB =  QUOTE   =10

Tính h(g) = ? ; t(g) = ?

v     1 xuất hiện 5 lần  => h(g=1) = 5; t(g=1) =  QUOTE  

v     2 xuất hiện 9 lần => h(g=2) = 9;

            t(2)= QUOTE  

v     3 xuất hiện 7 lần => h(g=3)=7;

 t(3) = t(2)+h(3)=14+7=21

v     4 xuất hiện 3 lần => h(g=4) =3;

 t(4)=t(3)+h(4)=21+3=24

v     5 xuất hiện 4 lần => h(g=5) = 4;

 t(5)=t(4)+h(5) = 24+4=28

v     6 xuất hiện 2 lần => h(g=6) = 2 ;

 t(6) = t(5) + h(6) = 28 + 2 =30

Tính f(g) = ?

v     f(1)=max{0,round( QUOTE   )}= 0

v     f(2) = max {0,round( QUOTE   )}=0

v     f(3)=max {0,round( QUOTE   )}=1

v     f(4)=max {0,round( QUOTE    - 1)}=1

v     f(5)=max {0,round( QUOTE   )}=2

v     f(6)= max {0,round ( QUOTE   )} =2

Ta có bảng sau :

h(g)

f(g)

1

5

5

0

2

9

14

0

3

7

21

1

4

3

24

1

5

4

28

2

6

2

30

2

Vậy :  QUOTE  

0

0

1

1

2

2

0

0

0

1

1

2

1

0

0

0

1

1

2

1

0

0

0

1

2

2

1

0

0

0

Câu 4.2

a.       Biên và kỹ thuật phát hiện biên Laplace

b.      Áp dụng kỹ thuật phát hiện biên Laplace cho ảnh sau :

3

0

0

0

0

0

0

3

0

0

0

0

0

0

3

3

3

3

0

0

3

3

3

3

0

0

3

3

3

3

0

0

3

3

3

3

Trả lời:

a.      Biên và kỹ thuật phát hiện biên Laplace:

-         Biên:

·        Điểm Biên: Một điểm ảnh được coi là điểm biên nếu có sự thay đổi nhanh hoặc đột ngột về mức xám (hoặc màu). Ví dụ trong ảnh nhị phân, điểm đen gọi là điểm biên nếu lân cận nó có ítmnhất một điểm trắng.

·        Đường biên (đường bao: boundary): tập hợp các điểm biên liên tiếp tạo thành một đường biên hay đường bao.

·        Ý nghĩa của đường biên trong xử lý: ý nghĩa đầu tiên: đường biên là một loại đặc trưng cục bộ tiêu biểu trong phân tích, nhận dạng ảnh. Thứ hai, người ta sử dụng biên làm phân cách các vùng xám (màu) cách biệt. Ngược lại, người ta cũng sử dụng các vùng ảnh để tìm đường phân cách.

·        Tầm quan trọng của biên: để thấy rõ tầm quan trọng của biên, xét ví dụ sau: khi người họa sỹ muốn vẽ một danh nhân, họa sỹ chỉ cần vẽ vài đường nứt tốc họa mà không cần vẽ một cách đầy đủ.

-         Kỹ thuật phát hiện biên Laplace:

Khi mức xám thay đổi chậm, miền chuyển tiếp trải rộng, phương pháp cho hiệu quả hơn đó là phương pháp sử dụng đạo hàm bậc hai Laplace.

Toán tử Laplace được định nghĩa như sau:

Ta có:

Tương tự:

Vậy:

Dẫn tới:

b. Ta có :

 QUOTE    =  QUOTE                    (m=3,n=3)

=  QUOTE  

= I(x,y) * H(0,0) + I(x,y+1)*H(0,1) + I(x,y+2) * H(0,2) + I(x+1,y) * H(1,0) + I(x+1,y+1) *H(1,1) + I(x+1,y+2)*H(1,2) +I(x+2,y) *H(2,0) + I(x+2,y+1)*H(2,1) + I(x+2,y+2)*H(2,2)

Vậy :

Ø     Ảnh I nhân chập theo mẫu H1 là :

I ⊛ QUOTE  

=4 I(x+1,y+1) – I(x,y+1) – I(x+1,y) – I(x+1,y+2) – I(x+2,y+1)

Kết quả xem bảng excel

Ø     Ảnh I nhân châp theo mẫu H2 là :

I ⊛ QUOTE  

Kết quả xem bảng excel

Ø     Ảnh I nhân chạp theo mẫu H3 là :

I ⊛ QUOTE   4I(x+1,y+1)+I(x,y)+I(x,y+2)+I(x+2,y)+I(x+2,y+2)-2[ I(x,y+1)-I(x+1,y)-I(x+1,y+2)-I(x+2,y+1) ]

Kết quả xem bảng excel

Kết quả :

 QUOTE   ⊛ QUOTE  

48

-24

-12

-12

*

*

-24

24

12

12

*

*

-12

15

0

0

*

*

-12

12

0

0

*

*

*

*

*

*

*

*

*

*

*

*

*

*

Câu 4.4

a.       Biên và kỹ thuật phát hiện biên Sobel?

Trả lời:

a.       Biên: <xem câu 4.2>

-         Kỹ thuật phát hiện biên Sobel:

Cho các ma trận:

Bước 1: Tính Sx*I, Sy*I

Bước 2: Tính |Sx*I|+|Sy*I|

Bước 3: Phân ngưỡng với ngưỡng q cho trước

Câu hỏi 4.6:

a)      Biên và kỹ thuật phát hiện biên Prewitt?

Trả lời:

► Biên

Biên là vấn đề quan trọng trong trích chọn đặc điểm nhằm tiến tới hiểu ảnh.

Trong mỗi ứng dụng người ta đưa ra các độ đo khác nhau về biên, một trong các độ đo đó là độ đo về sự thay đổi đột ngột về cấp xám.

Ví dụ: ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là điểm đen có ít nhất một điểm trắng bên cạnh. Tập hợp các điểm biên tạo nên biên hay đường bao của đối tượng.

► Kỹ thuật phát hiện biên Prewitt

      Là kỹ thuật phát hiện biên trực tiếp.

      Kỹ thuật này sử dụng 2 mặt nạ nhập chập xấp xỉ đạo hàm theo 2 hướng x và y là:

Các bước tính toán kỹ thuật Prewitt

         + Bước 1: Tính I Hx và I Hy

         + Bước 2: Tính I Hx + I Hy

Câu hỏi 4.7:

a)      Lọc trung vị?

Trả lời:

► Trung vị

Cho dãy x1, x2…,xn đơn điệu nhưng tăng (giảm). Khi đó trung vị của dãy ký hiệu là Med({xn}), được định nghĩa:

             + Nếu n lẻ thì x

             + Nếu n chẵn thì x  hoặc x

►Lọc trung vị

Giả sử ta có ảnh I ngưỡng  cửa sổ W(P) và điểm ảnh P

Khi đó kỹ thuật lọc trung vị phụ thuộc không gian bao gồm các bước cơ bản sau:

   + Bước 1: Tìm trung vị

                                        {I(q)|q W(P)} Med(P)

   + Bước 2: Gán giá trị

                    I(P)=    

Thu Huyền

Câu 4.9:

a. Kỹ thuật bó cụm ảnh?

Trả lời:

a. Bó cụmlà kỹ thuật nhằm giảm bớt số mức xám của ảnh bằng cách nhóm lại số mức xám gầnnhau thành 1 nhóm.

-         Nếu chỉ có 2 nhóm thì chính là kỹ thuật tách ngưỡng.

Giả sử ta có ảnh I ~ kích thước m × n, hai số Min, Max và ngưỡng θ.

Khi đó, kỹ thuật tách ngưỡng được thể hiện:

I [i, j] = I [i, j] > = θ? Max: Min; ∀ (i,j)

-         Thông thường có nhiều nhóm với kích thước khác nhau. Để tổng quát khi biến đổi người ta sẽ lấy cùng 1 kích thước bunch_size

I [i,j] = I [i,j]/ bunch - size * bunch_size ∀(i,j)

Câu 4.10:

a. Phép nhân chập (phép cuộn) và mẫu.

Trả lời:

Giả sử ta có ảnh I kích thước M × N, mẫu T có kích thước m × n khi đó, ảnh I cuộn theo mẫu T được xác định bởi công thức.

-         Trong quá trình thực hiện phép nhân chập có một số thao tác ra ngoài ảnh, ảnh không được xác định tại những vị trí đó dẫn đến ảnh thu được có kích thước nhỏ hơn.

-         Ảnh thực hiện theo 2 công thức trên chỉ sai khác nhau 1 phép dịch chuyển để đơn giản ta sẽ hiểu phép nhân chập là theo công thức 1.

·       Câu hỏi loại 5 điểm

Câu 5.1: a) Hãy trình bày khái niệm đối tượng ảnh và cho ví dụ

Trả lời:

Hai điểm Ps, Pe∈E, E ⊆ℑ (tập các vùng điểm đen) hoặc ℑ  (tập các vùng điểm trắng ) được gọi là 8-liên thông (hoặc 4-liên thông) trong E nếu tồn tại tập các điểm được gọi là đường đi (io,jo)...(in,jn) sao cho (io,jo)= Ps, (in,jn)= Pe, (ir,jr) ∈E và (ir,jr) là 8-láng giềng (hoặc 4-láng giềng tương ứng) của (ir-1,jr-1) với r = 1,2,...,n. Ta thấy, quan hệ k-liên thông trong E (k=4,8) là một quan hệ phản xạ, đối xứng và bắc cầu. Bởi vậy đó là một quan hệ tương đương. Mỗi lớp tương đương được gọi là một thành phần k-liên thông của ảnh. Ta gọi mỗi thành phần k-liên thông của ảnh là một đối tượng ảnh.

            Ví dụ: Ta có:

            Hai điểm P0 và P7∈E, ta thấy tồn tại điểm (ir,jr) ∈E và (ir,jr) là 4-láng giềng của (ir-1,jr-1) với r = 1,2,...,7. Vậy hai điểm P0 và P7 được gọi là 4 liên thông trong E hay là đối tượng ảnh.

b) Hãy thay đổi các khái niệm cần thiết để có thể hiểu được đối tượng ảnh có thể chỉ 1 pixel. (cái này tớ không tìm được định nghĩa 1 pixel và cũng chưa hiểu rõ câu hỏi)

Câu 5.2

a.       Hãy trình bày khái niệm chu tuyến của đối tượng ảnh? Các loại chu tuyến?

b.      Hãy cho một ví dụ về đối tượng có chu tuyến vừa là chu tuyến trong vừa là chu tuyến ngoài.

Trả lời:

a.       *   Khái niệm chu tuyến của một đối tượng ảnh:

 Chu tuyến của một đối tượng ảnh là dãy các điểm của đối tượng ảnh P1,…,Pn sao cho Pi và Pi+1 là các 8-láng  giềng của nhau (i=1,…,n-1) và P1 là 8-láng giềng của Pn ,  không thuộc đối tượng ảnh và Q là 4-láng giềng của Pi(hay nói các khác i thì Pi là biên 4). Ký hiệu <P1P2…Pn>.

                               Ví dụ về chu tuyến của đối tượng ảnh

·  Các loại chu tuyến: có 3 loại chu tuyến

ü      Chu tuyến đối ngẫu: Hai  chu tuyến C=<P1P2…Pn>và

 C┴=<Q1Q2…Qm> được gọi là đối ngẫu của nhau nếu và chỉ nếu   sao cho: (i)    Pi và Qj là 4-láng giềng của nhau.

               (ii)  Các điểm Pi là vùng thì Qj là nền và ngược lại.

ü      Chu tuyến ngoài: Chu tuyến C được gọi là chu tuyến ngoài nếu và chỉ nếu: (i)   Chu tuyến đối ngẫu C┴  là chu tuyến của các điểm nền.

        (ii)  Độ dài của C nhỏ hơn độ dài của C┴

                                         Chu tuyến ngoài

ü       Chu tuyến trong: Chu tuyến C được gọi là chu tuyến trong nếu và chỉ nếu: (i)   Chu tuyến đối ngẫu C┴  là chu tuyến của các điểm nền.

        (ii)  Độ dài của C lớn hơn độ dài của C┴

  Chu tuyến trong

b.      Ví dụ về đối tượng có chu tuyến vừa là chu tuyến trong vừa là chu tuyến ngoài.

        Không có một chu tuyến của một đối tượng  nào mà vừa là chu tuyến trong vừa là chu tuyến ngoài.Vì ta có định lý về tính duy nhất của chu tuyến ngoài được phát biểu như sau: Giả sử E נּ  là một đối tượng ảnh và CE là chu tuyến ngoài của E.  Khi đó CE là duy nhất

Câu hỏi 5.3 :

a)      Hãy trình bày thuật toán dò biên cho một đối tượng ảnh?

b)     Hãy lý giải tại sao lại phải sử dụng cặp nền – vùng trong thuật toán?

Trả lời:

a)     Trình bày thuật toán dò biên cho một đối tượng ảnh.

Về cơ bản thuật toán dò biên trong một vùng là nhằm tìm ra chu tuyến của vùng đó. Bao gồm các bước sau:

B1 – Xác định cặp nền-vùng xuất phát

B2 – Xác định cặp nền – vùng tiếp theo

B3 – Lựa chọn điểm biên vùng

B4– Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2

Xác định cặp nền – vùng xuất phát:

-         Cặp nền – vùng là 8 láng giềng của nhau nên có thể biểu diễn bởi 1 điểm vùng P và hướng “dir” thể hiện vị trí láng giềng của điểm nền so với điểm vùng.

-         “dir” có thể nhận 1 trong 8 giá trị 0, 1, 2, 3, 4, 5, 6, 7. Do vậy, cặp nền – vùng xuất phát sẽ được xác định bởi duyệt ảnh từ trên xuống dưới, trái qua phải. Điểm vùng đầu tiên faqwpj phát sẽ là điểm vùng xuất phát tương ứng với hướng điểm nền là 4.

Xác định cặp nền – vùng tiếp theo:

P, dir

Point Orient[]={(1,0), (1,-1), (0, -1), (-1,-1), (-1, 0), (-1, 1), (0, 1), (1, 1)}

Byte getNext (Point P, Byte dir)

            {

                        Int count = 0

                        While (count < 8)

                        {

                                    If (getpixel (p.x+Orient[dir].x , P.y + Orient[dir].y)==BLACK)

                                    Return dir;

                                    Dir = (dir + 7) %8;

}count++;

Return ERR; // điểm cô lập

// Vị trí mới

Pdir = GetNext (P, dir);

p.x+=Orient[pdir].x;

p.y+=Orient[pdir].y;

}

b)     Phải sử dụng cặp nền – vùng trong thuật toán vì:

Kết quả tác động của toán tử dò biên lên một điểm biên ri là điểm biên ri+1 (8-láng giềng của ri). Thông thường các toán tử này được xây dựng như một hàm đại số Boolean trên các 8-láng giềng của  ri . Mỗi các xây dựng các toáng tử đều phụ thuộc vào định nghĩa quan hệ liên thông và điểm biên. Do đó sẽ gây ra khó khăn cho việc khảo sát các tính chất của đường biên. Ngoài ra, vì mỗi bước dò biên đều phải kiểm tra tất cả các 8 – láng giềng của mỗi điểm nên thuật toán thường kém hiệu quả. Để khắc phục các hạn chế trên, thay vì sử dụng một điểm biên ta sẻ dụng cặp điểm biên (một thuộc , một thuộc ), các cặp điểm này tạo nên tập nền - vùng, kí hiệu là NV.

Câu 5.4

a.Hãy nêu bài toán rút gọn số lượng điểm biểu diễn

b.Trình bày thuật toán rút gọn số lượng điểm biểu diễn Douglas Peucker? Và cho biết tiêu chuẩn “gần giống” được sử dụng ở đây là gì?

Trả lời:

a.Rút gọn số lượng điểm biểu diễn là kỹ thuật thuộc phần hậu xử lý. Kết quả của phần dò hay trích xương thu được 1 dãy các điểm liên tiếp. Vấn đề đặt ra là liệu có thể bỏ bớt các điểm thu được để giảm thiểu không gian lưu trữ và thuận tiện cho việc đối sách hay không ?

Sau đây là bài toán rút gọn điểm biểu diễn:

Cho đường cong gồm n điểm trong mặt phẳng (x1, y1), (x2, y2),…, (xn, yn). Hãy bỏ bớt một số điểm thuộc đường cong sao cho đường cong mới nhận được là (Xi1; Yi1), (Xi2;Yi2),…,(Xim; Yim) “gần giống” với đường cong ban đầu.

b.

     Thuật toán rút gọn số lượng điểm biểu diễn Douglas Peucker:

Ý tưởng cơ bản của thuật toán Douglas – Peucker là xét xem khoảng cách lớn nhất từ đường cong tới đoạn thẳng nối hai đầu mút đường cong có lớn hơn ngưỡng θ không. Nếu điều này đúng thì điểm xa nhất được giữ lại làm điểm chia đường cong và thuật toán được thực hiện tương tự với hai đường cong vừa tìm được. Trong trường hợp ngược lại, kết quả của thuật toán đơn giản hóa là hai điểm đầu mút của đường cong.

            Thuật toán Douglas – Peucker:

-         Bước 1: Chọn ngưỡng θ.

-         Bước 2: Tìm khoảng cách lớn nhất từ đường cong tới đoạn thẳng nối hai đầu đoạn đường cong h.

-         Bước 3: Nếu h ≤ θ thì dừng

-         Bước 4: Nếu h > θ thì giữ lại điểm đạt cực đại này và quay trở lại bước 1

Nhận xét: Thuật toán này tỏ ra thuận lợi đối với các đường cong thu nhận được mà gốc là các đoạn thẳng, phù hợp với việc đơn giản hóa trong quá trình Vector hóa các bản vẽ kỹ thuật, sơ đồ thiết kế mạch in, …

     Chương trình:

// Hàm tính đường cao từ đỉnh đến đoạn thẳng nối hai điểm đầu và cuối

float Tinhduongcao (POINT dau, POINT cuoi, POINT dinh){

float h;

//tinh duong cao

return h;

}

// Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong

void DPSimple (POINT *pLINE, int dau, int cuoi, BOOL *chiso, float θ)

{

            int i, index = dau;

            float h, hmax = 0;

            for(i=dau+1;i<cuoi;i++){

                        h=Tinhduongcao(pLINE[dau], pLINE[cuoi], pLINE[i]);

                        if(h>hmax){

                                    hmax=h;

                                    index=i;

                        }

            }

            if(hmax≤θ)

                        for(i=dau+1;i<cuoi;i++)

                                    chiso[i] = FALSE;

            else{

                        DPSimple(PLINE, dau, index, chiso, θ);

                        DPSimple(PLINE, index, cuoi, chiso,θ);

            }

}

// Hàm rút gọn số lượng điểm Douglas Peucker

int DouglasPeucker (POINT *pLINE, int n, float θ){

            int i,j;

            BOOL chiso[MAX_PT];

            for (i=0;i<m;i++) //Tất cả các điểm được giữ lại

                        chiso[i]=TRUE;

            DPSimple(pLINE, 0, n-1, chiso, θ);

            for (i=j=0;i<0;i++)

                        if(chiso[i]==TRUE)

                                    pLINE[j++] = pLINE[i];

            return j;

}

     Tiêu chuẩn gần giống được sử dụng ở đây:

Một số độ đo “gần giống” là:

-         Chiều dài (chiều rộng) của hình chữ nhật nhỏ nhất chứa đường cong.

-         Khoảng cách lớn nhất từ đường cong đến đoạn thẳng nối 2 đầu mút của đường cong.

-         Tỷ lệ chiều dài và chiều rộng của hình chữ nhật nhỏ nhất chứa đường cong

-         Số lần đường cong cắt đoạn thẳng nối 2 đầu mút.

Câu 5.5:a. Hãy trình bày thuật toán đường thẳng Hough

Trả lời:

a.

-         Xây dựng mảng chỉ số [a,b] và gán giá trị 0 ban đầu cho tất cả các phần tử của mảng.

-         Với mỗi (xi;yi) và  QUOTE    a,b là chỉ số của phần tử mảng thỏa mãn b=-axi+yi thì tăng giá trị của phần tử mảng tương ứng lên 1.

-         Tìm phần tử mảng có giá trị lớn nhất nếu giá trị lớn nhất tìm được so với số phần tử lớn hơn hoặc bằng ngưỡng  QUOTE    cho trước thì ta có thể kết luận các điểm nằm trên cùng một đường thẳng. Và đường thẳng có phương trình y=ax+b trong đó a, b tương ứng là chỉ số của phần tử mảng có giá trị lớn nhất tìm được.

Không có câu 4.1a(do trùng với câu 3.1 ), 4.3a(do trùng câu 3.2), 4.5a(do trùng câu 3.3),  4.8a(do trùng câu 3.5)