Báo cáo nhập môn xử lý ảnh tìm hiểu phép biến đổi Haar

các wavelet Haar là một chuỗi các chức năng hình vuông rescaled mà cùng nhau tạo thành một gia đình wavelet hoặc cơ sở. Phân tích Wavelet tương tự như phân tích Fourier ở chỗ nó cho phép một hàm mục tiêu trong một khoảng thời gian được biểu diễn dưới dạng cơ sở trực giao

NHẬN XÉT ĐÁNH GIÁ

LỜI MỞ ĐẦU

Cuộc sống càng phát triển thì nhu cầu thông tin của con người càng phong phú, dẫn đến

sự phát triển mạnh mẽ của khoa học kỹ thuật, các loại hình thông tin vô tuyến, các hình thức xử lý tín hiệu, đặc biệt là công nghệ xử lý ảnh Vấn đề này đặt ra yêu cầu ngày càng cao trong việc xử lý tín hiệu để đảm bảo vừa có thể nén dữ liệu, tiết kiệm dung lượng trên đường truyền tín hiệu, vừa đảm bảo loại trừ nhiễu tín hiệu và có khả năng khôi phục lại được tín hiệu với chất lượng tốt

Có rất nhiều phương pháp xử lý tín hiệu với rất nhiều thuật toán, biến đổi toán học đã được nghiên cứu Trong số đó, biến đổi Haar hiện nay đang được xem là một phép biến đổi mới, có rất nhiều tiềm năng, đang phát triển khá mạnh mẽ với các ưu điểm vượt trội

so với các phép biến đổi truyền thống Haar cho phép phân tích tín hiệu cả trong miền thời gian và tần số Do đó, hiện nay biến đổi Haar đang được ứng dụng khá rộng rãi trong nhiều lĩnh vực, từ y sinh tới công nghệ xử lý ảnh

Trong bài báo cáo này, em xin phép được giới thiệu về:"Tìm hiểu phép biến đổi Haar, khảo sát, phân tích và xây dựng một ứng dụng của phép biến đổi Haar trong xử lý ảnh”

MỤC LỤC NHẬN XÉT ĐÁNH GIÁ 1

LỜI MỞ ĐẦU 2

CHƯƠNG 1: TỔNG QUAN PHÉP BIẾN ĐỔI HAAR 4

1.1.Tổng quan 4

1.2 Haar wavelet 4

1.3 Chức năng Haar và hệ thống Haar 6

1.4 Ma trận Haar 7

1.5 Haar biến đổi 9

1.5.1 Giới thiệu 9

1.5.2 Thuộc tính 10

1.5.3 Haar biến đổi và đảo ngược haar biến đổi 10

1.6 Biến đổi haar rời rạc 11

1.6.1 Chức năng của biến đổi haar rời rạc 11

1.6.2 Biến đổi haar rời rạc 12

1.7 Ký haar biến đổi 13

1.8 Ứng dụng biến đổi haar 14

CHƯƠNG 2: XÂY DỰNG ỨNG DỤNG CỦA PHÉP BIẾN ĐỔI HAAR 15

2 Xây dựng ứng dụng 15

TÀI LIỆU THAM KHẢO 19

CHƯƠNG 1: TỔNG QUAN PHÉP BIẾN ĐỔI HAAR

1.1.Tổng quan

Trong toán học, các wavelet Haar là một chuỗi các chức năng "hình vuông" rescaled mà

cùng nhau tạo thành một gia đình wavelet hoặc cơ sở. Phân tích Wavelet tương tự như phân tích Fourier ở chỗ nó cho phép một hàm mục tiêu trong một khoảng thời gian được biểu diễn dưới dạng cơ sở trực giao . Trình tự Haar bây giờ được công nhận là cơ sở wavelet được biết đến đầu tiên và được sử dụng rộng rãi như một ví dụ giảng dạy

Các chuỗi Haar đã được đề xuất vào năm 1909 bởi Alfréd Haar . Haar sử dụng các hàm này để đưa ra một ví dụ về một hệ thống trực giao cho không gian của các hàm có thể tích phân vuông trong khoảng thời gian đơn vị  [0, 1]. Các nghiên cứu về wavelet, và thậm chí cả thuật ngữ "wavelet", đã không đến cho đến sau này. Như một trường hợp đặc

biệt của wavelet Daubechies , wavelet Haar còn được gọi là Db1 .

Haar wavelet cũng là wavelet đơn giản nhất có thể. Những bất lợi kỹ thuật của wavelet Haar là nó không phải là liên tục , và do đó không phải là khác biệt . Tuy nhiên, tài sản này có thể là một lợi thế cho việc phân tích các tín hiệu với sự chuyển đổi đột ngột, chẳng hạn như giám sát lỗi công cụ trong máy

1.2 Haar wavelet

Chúng ta bắt đầu với 4 hàm wavelet cơ bản được Alphré Haar (nhà toán học Hungary) giới thiệu năm 1910

Hình 1.2: Bốn hàm Haar wavelet

Hàm Haar wavelet thứ nhất gọi là hàm scaling (scaling function), xác định như sau:

1(t)  (t)  1, 0  t  1,

Hàm Haar wavelet thứ hai gọi là wavelet mẹ (mother wavelet):

Giá trị của hàm w(t) tại những điểm rời rạc không quan trọng lắm, nhưng tương tự trườnghợp khai triển Fourier ta quy ước cho w(t) = 0, tại các điểm t=0,1/2,1

Hàm Haar wavelet thứ ba và hàm Haar wavelet thứ tư là dạng nén của hàm wavelet mẹ,được gọi là các hàm wavelet con (daughter wavelet), xác định như sau:

Hàm scaling j(t) và wavelet w(t) được mở rộng lên toàn bộ tập số thực R bằng cách cho

nhận giá trị 0 bên ngoài khoảng cơ bản:

Khi đó ta có các biểu diễn

1.3 Chức năng Haar và hệ thống Haar

Đối với mỗi cặp n , k của số nguyên trong Z , hàm Haar ψ  n ,  k được định nghĩa trên dòng thực R theo công thức

Hàm này được hỗ trợ trên khoảng thời gian mở phải  , n ,   k  = [ k  2  - n  , ( k +1) 2  - n  ) , tức là ,

nó biến mất ngoài khoảng thời gian đó. Nó có tích phân 0 và chuẩn 1 trong không gian

Hilbert L 2 ( R ) , 

Các hàm Haar là trực giao hai chiều,

trong đó δ  i , j đại diện cho đồng bằng Kronecker . Đây là lý do cho trực giao: khi hai khoảng hỗ trợ In1,k1 và In2,k2  không bằng nhau, sau đó chúng bị phân tách, hoặc người nào khác, nhỏ hơn của hai hỗ trợ, nói In1,k1, được chứa trong phần dưới hoặc nửa trên của khoảng thời gian khác, trên đó hàm  vẫn không đổi. Trong trường hợp này, sản phẩm của hai hàm Haar này là một hàm của hàm Haar đầu tiên, do đó sản phẩm có tích phân=0

Các hệ thống Haar trên dòng thực sự là tập hợp các hàm

Nó hoàn thành trong L 2 ( R ): Hệ thống haar trên đường thẳng là một cơ sở trực giao

trong L 2 ( R ).

1.4 Ma trận Haar

Ma trận Haar 2 × 2 liên kết với Haar wavelet là

Sử dụng biến đổi wavelet rời rạc , người ta có thể biến đổi bất kỳ chuỗi nào (a0,a1,

…,a2n,a2n+1) thậm chí độ dài thành chuỗi các vector hai thành phần ((a0,a1),…, (a2n,a2n+1)). Nếu một nhân phải mỗi vector với ma trận H2, người ta nhận được kết quả  ((s0,d0),…,(sn,dn)) của một giai đoạn của biến đổi Haar-wavelet nhanh. Thông thường một

phân tách các chuỗi s và d và tiếp tục với việc chuyển đổi các chuỗi s . Trình tự s thường được gọi là phần trung bình , trong khi d được gọi là phần chi tiết . 

Nếu có một chuỗi có độ dài là bội số của bốn, ta có thể tạo khối gồm 4 phần tử và biến đổi chúng theo cách tương tự với ma trận Haar 4 × 4

kết hợp hai giai đoạn của biến đổi Haar-wavelet nhanh.So sánh với ma trận Walsh , là ma trận 1 / -1 không được bản địa hoá.Nói chung, ma trận Haar 2N × 2N có thể được bắt nguồn bằng phương trình sau

Ở đâu A là ma trận m × n và B là ma trận ap × q, được biểu thị bằng

Ma trận Haar 8 điểm không chuẩn hóa H8 được hiển thị bên dưới

Lưu ý rằng, ma trận trên là ma trận Haar không chuẩn hóa. Ma trận Haar yêu cầu bởi biến đổi Haar cần được chuẩn hóa

Từ định nghĩa của ma trận Haar H, người ta có thể quan sát điều đó, không giống như biến đổi Fourier, H chỉ có các phần tử thực (ví dụ, 1, -1 hoặc 0) và không đối xứng

Lấy ma trận Haar 8 điểm H8làm ví dụ. Hàng đầu tiên của H8 đo lường giá trị trung bình

và hàng thứ hai của H8 đo thành phần tần số thấp của vector đầu vào. Hai hàng tiếp theo nhạy cảm với nửa đầu tiên và thứ hai của véc tơ đầu vào tương ứng, tương ứng với các thành phần tần số vừa phải. Bốn hàng còn lại nhạy cảm với bốn phần của vector đầu vào, tương ứng với các thành phần tần số cao

1.5 Haar biến đổi

Biến đổi Haar là đơn giản nhất của các biến đổi wavelet Sự biến đổi này nhân chéo một hàm với Haar wavelet với các thay đổi và trải dài khác nhau, giống như phép biến đổi Fourier nhân chéo một hàm chống lại sóng sin với hai pha và nhiều đoạn trải dài

1.5.1 Giới thiệu

Biến đổi Haar là một trong những chức năng biến đổi lâu đời nhất, được đề xuất vào năm

1910 bởi nhà toán học người Hungary Alfréd Haar . Nó được tìm thấy hiệu quả trong các ứng dụng như nén tín hiệu và hình ảnh trong kỹ thuật điện và máy tính vì nó cung cấp một cách tiếp cận đơn giản và hiệu quả về mặt tính toán để phân tích các khía cạnh địa phương của tín hiệu

Biến đổi Haar bắt nguồn từ ma trận Haar. Một ví dụ về ma trận chuyển đổi Haar 4x4 được hiển thị bên dưới

Biến đổi Haar có thể được coi là một quá trình lấy mẫu trong đó các hàng của ma trận biến đổi hoạt động như các mẫu có độ phân giải tốt hơn và mịn hơn.So sánh với biến đổi Walsh , cũng là 1 / -1, nhưng không được bản địa hoá

1.5.2 Thuộc tính

Biến đổi Haar có các thuộc tính sau:

 Không cần nhân. Nó chỉ yêu cầu bổ sung và có nhiều phần tử có giá trị bằng không trong ma trận Haar, do đó thời gian tính toán ngắn. Nó nhanh hơn biến đổi Walsh , có ma trận gồm 1 và −1

 Độ dài đầu vào và đầu ra đều giống nhau. Tuy nhiên, độ dài phải là một sức mạnh của 2, tức là N=2k,k € N

 Nó có thể được sử dụng để phân tích các tính năng cục bộ của tín hiệu. Do thuộc tính trực giao của hàm Haar, các thành phần tần số của tín hiệu đầu vào có thể được phân tích

1.5.3 Haar biến đổi và đảo ngược haar biến đổi

Biến Haar y  n  của hàm n-input x  n là

Yn=Hn*Xn

Ma trận biến đổi Haar là thực và trực giao. Do đó, phép biến đổi Haar nghịch đảo có thể được bắt nguồn bằng các phương trình sau đây

Ở đâu I là ma trận nhận dạng. Ví dụ, khi n = 4

Ví dụ:

Hệ số biến đổi Haar của tín hiệu = = 4 điểm x4=[1,2,3,4]T có thể được tìm thấy là

Tín hiệu đầu vào sau đó có thể được tái tạo hoàn toàn bằng phép biến đổi Haar nghịch đảo

1.6 Biến đổi haar rời rạc

1.6.1 Chức năng của biến đổi haar rời rạc

Các hàm Haar rời rạc có thể được xác định là các hàm bằng cách lấy mẫu hàm Haar ở 2n

điểm Ngoài ra, chúng có thể được coi là độc lập như một tập hợp các chức năng cụ thể trong không gian Hilbert của các hàm trên các nhóm dyitic G2n theo thứ tự 2n được xác định bởi sự tương tự với các hàm Haar Nhớ lại rằng nhóm dyitic của đơn hàng 2n là sản phẩm trực tiếp của n nhóm cyclic

Các hàm Haar rời rạc được biểu diễn một cách thuận tiện dưới dạng các hàng của một (2n

×2n) ma trận biểu thị là ma trận Haar Các ma trận Haar được xem xét theo thứ tự tự nhiên và sắp xếp theo thứ tự các hàng

Các hàm Haar rời rạc của bậc n được biểu diễn bởi (2n×2n) ma trận H8(n), theo thứ tự sắp xếp được đưa ra bởi quan hệ lặp lại sau đây:

Và Iq là ma trận nhận dạng của thứ tự q Ma trận Haar theo thứ tự tương ứng với thứ tự tự nhiên hoặc Hadamard của ma trận Walsh, có thể được bắt nguồn theo cách sau Quy trình đảo ngược bit được áp dụng cho các biểu thức nhị phân của các chỉ số của các hàng trong

ma trận Haar được sắp xếp tuần tự Sau đó, các chỉ số được sắp xếp theo thứ tự ngày càng tăng của các giá trị tương đương thập phân của chúng trong mỗi tập hợp con Thủ tục như vậy được biểu thị như là thủ tục đảo ngược bit zonal

1.6.2 Biến đổi haar rời rạc

Một đặc tính nổi bật của hàm Haar là trừ hàm haar (0, t), hàm Haar thứ i có thể được tạo

ra bởi sự hạn chế hàm j (1) - thứ từ không, bằng phép nhân với √2 và chia tỷ lệ trong khoảng thời gian [0,1] Các thuộc tính này đưa ra thông báo về sự quan tâm đối với hàm Haar, vì chúng liên quan mật thiết đến lý thuyết wavelet Do đó, hàm Haar là một cặp xung hình chữ nhật lẻ, là một wavelet đơn giản nhất và cuối cùng Động lực cho việc sử dụng các biến đổi wavelet rời rạc là thu được thông tin phân biệt đối xử hơn bằng cách cung cấp độ phân giải ff di ff ở các phần ff erent của mặt phẳng thời gian tần số Biến đổi Wavelet cho các tên miền của không gian tên miền trong cấu trúc không tìm thấy trong kết nối với nội dung thời gian nội bộ phổ Các phương thức Wavelet được kết nối chặt chẽ với cơ sở cổ điển của các hàm Haar; mở rộng và giãn nở của một wavelet cơ bản có thể tạo ra các hàm cơ sở Haar

Gọi Ψ: R → R, hàm Haar wavelet được xác định theo công thức:

Bất kỳ hàm Haar nào (ngoại trừ hàm haar (0, t)) có thể được tạo ra bằng các công thức:

Ψj i (t) = √2jΨ (2jt − i), i = 0,1, , 2j −1 và j = 0,1, , log2 N −1

Hằng số √2j được chọn sao cho tích vô hướng <Ψj i, Ψj i> = 1, Ψj i ∈ L2 (R) Ifone xem xét hàm wavelet trong các khoảng thời gian khác với [0,1], hằng số chuẩn hóa sẽ là khác

Gọi Φ: R → R, hàm Haar mở rộng được xác định theo công thức:

Tương tự như các thuộc tính của hàm wavelet, đối với hàm rộng có thể xác định họ của các hàm:

Φj i (t) = √2jΦ (2jt − i), i = 0,1, , 2j −1 và j = 0,1, , log2 N −1

Hằng số √2j được chọn sao cho tích vô hướng <Φj i, Φj i> = 1, Φj i ∈ L2 (R) Trong phân tích đa biến, cơ sở Haar có tính chất quan trọng: Vj = Vj − 1 ⊕ Wj – 1 (trong đó ⊕

là viết tắt của tính trực giao của không gian Vj và Wj).Không gian vectơ Wj đó có thể được coi là bổ sung trực giao của Vj trong Vj + 1 Nói cách khác, hãy để Wj là không gian của tất cả các hàm trong Vj + 1, là trực giao với tất cả các hàm trong Vj Do đó, các hàm cơ sở Ψj i của Wj cùng với các hàm cơ sở Φj i của dạng Vj là cơ sở cho Vj + 1 và mọi hàm cơ sở Ψj i của Wj là trực giao với mọi hàm cơ sở Φj i của Vj Từ các đặc tính của các hàm Haar, được mô tả ở trên, sau đó wavelet cơ bản được thu hẹp dần dần (giảm theo tỷ lệ) bởi lũy thừa của hai Mỗi wavelet nhỏ hơn sau đó được dịch bởi các gia số bằng với chiều rộng của nó, sao cho bộ hoàn chỉnh các wavelet ở mọi quy mô hoàn toàn bao trùm khoảng thời gian đó Từ các phương trình đã đề cập, người ta có thể kết luận rằng, wavelet cơ bản được thu nhỏ lại theo lũy thừa của 2, nhưng biên độ của nó được nhân lên bởi các lũy thừa của √2

1.7 Ký haar biến đổi

Đề cập đến các bước trong thuật toán tính toán nhanh cho phép biến đổi Haar, biến Haar

ký được giới thiệu bằng sự tương tự với biến đổi ký hiệu bắt nguồn từ phép biến đổi Walsh nhanh Bên cạnh tính toán dấu Haar chuyển tiếp và nghịch đảo bằng cách sử dụng biểu đồ nhanh, các biến đổi này có thể được tính toán trực tiếp từ các định nghĩa đệ quy liên quan đến dữ liệu và biến đổi các biến miền Nhiều thuộc tính của phổ Haar ký tương

tự với các đặc trưng của phổ Walsh ký hiệu Các ưu điểm tính toán của phổ Haar so với Walsh có thể vẫn được mở rộng đến các biến đổi ký hiệu tương ứng của chúng Do đó, thuận lợi từ quan điểm tính toán để sử dụng phép biến Haar ký hiệu, nơi biến đổi ký hiệu Walsh đã được sử dụng, tức là, để chuyển đổi phân tách chức năng và thử nghiệm các mạch logic Bên cạnh các ứng dụng trong thiết kế logic, một biến đổi mới có thể được sử dụng khi có nhu cầu mã hóa duy nhất các vectơ nhị phân / ternary vào miền phổ của cùng kích thước Một ứng dụng có thể là mã hóa bảo mật trong các hệ thống truyền thông

1.8 Ứng dụng biến đổi haar

Do các yêu cầu tính toán thấp, phép biến đổi Haar đã được sử dụng chủ yếu để nhận dạng mẫu và xử lý ảnh Do đó, việc xử lý tín hiệu và hình ảnh hai chiều là một vùng ứng dụng hiệu quả của biến đổi Haar do cấu trúc giống như wavelet của chúng Trong khu vực này,

nó thường được báo cáo rằng hệ thống wavelet trực giao đơn giản nhất có thể được tạo ra

từ hàm Haar và wavelet Hơn nữa, các wavelet được coi là sự tổng quát hóa các hàm Haar và các biến đổi Biến đổi như vậy cũng rất phù hợp trong công nghệ truyền thông để

mã hóa dữ liệu, ghép kênh và kỹ thuật số Ví dụ, việc áp dụng biến đổi Haar không chuẩn hóa trong hệ thống ghép kênh phân chia tuần tự Nền kinh tế băng thông cho các kênh kỹ thuật số ghép kênh dựa trên biến đổi Haar được trình bày trong Đối với các ứng dụng thời gian thực, chip Haar nhanh dựa trên phần cứng đã được phát triển Trong Ref, khái quát hóa các chức năng và biến đổi Haar được sử dụng trong xử lý lời nói kỹ thuật số với các ứng dụng trong các thiết bị máy tính điều khiển bằng giọng nói và robot Hệ thống điều khiển dựa trên phổ Haar cho máy bay quân sự cũng được thảo luận trong Ref Các ứng dụng của Haar biến đổi trong kiểm soát và thông tin liên lạc được trình bày trong Ref Trong Ref, các dạng khác nhau của hàm Haar được sử dụng trong các tính toán gần đúng của hàm phân tích Một cuộc thảo luận ngắn gọn về các ứng dụng khác nhau, trong

đó việc sử dụng các hàm Haar và Walsh có một số ưu điểm so với biến đổi Fourier, được đưa ra trong Ref