Luận văn Nghiên cứu một số phương pháp tra cứu ảnh sử dụng độ đo tương tự và ứng dụng tra cứu ảnh trong camera đường phố

ĐẶT VẤN ĐỀ .1

CHƯƠNG 1: TỔNG QUAN CƠ BẢN VỀ TRA CỨU ẢNH VÀ ĐỘ ĐO TƯƠNG TỰ

TRONG TRA CỨU ẢNH .3

1.1. KHÁI QUÁT VỀ TRA CỨU ẢNH.3

1.1.1. CÁC KHÁI NIỆM CƠ BẢN[2].3

1.1.2. XU HƯỚNG TRA CỨU VÀ CHÚ Ý TRONG TRUY VẤN ẢNH .4

1.1.2.1.MỘT SỐ HỆ THỐNG TRUY VẤN ẢNH VÀ HÌNH THÁI TRUY VẤN.5

1.1.2.2. MỘT SỐ ỨNG DỤNG TRUY VẤN ẢNH .8

1.1.2.3. KHÁI NIỆM TRA CỨU FRAME ẢNH TRONG CAMERA[3] .10

1.1.2.4. LƯỢC ĐỒ MÀU VÀ TƯƠNG QUAN MÀU.13

1.1.2.5. ĐẶC ĐIỂM CỦA SỰ VẬN ĐỘNG TRONG VIDEO VÀ XỬ LÝ VẬN ĐỘNG

.18

CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP SỬ DỤNG ĐỘ ĐO TƯƠNG TỰ .21

2.1. ĐỘ ĐO KHOẢNG CÁCH. .21

2.1.1. .ĐỘ ĐO MIN-MAX.21

2.1.2. ĐỘ ĐO EUCLID .21

2.1.3. ĐỘ ĐO KHOẢNG CÁCH HAMMING.22

2.1.4. ĐỘ ĐO PRECISION VÀ RECALL .23

2.2. ĐỘ ĐO HỖN HỢP .23

2.2.1. ĐỘ ĐO CÓ THUỘC TÍNH RỜI RẠC.23

2.2.2. ĐỘ ĐO CÓ THUỘC TÍNH CÓ THỨ TỰ .26

2.2.3. ĐỘ ĐO CÓ THUỘC TÍNH LIÊN TỤC.26

2.2.4. ĐỘ ĐO KẾT HỢP CÁC THUỘC TÍNH .27

2.3. ĐỘ ĐO TƯƠNG TỰ DỰA TRÊN HISTOGRAM [9].27

2.3.1. GIỚI THIỆU VÀ KHÁI NIỆM .27

2.3.2. LƯỢC ĐỒ XÁM VÀ TÍNH CHẤT .29

2.3.3. QUAN HỆ GIỮA ẢNH TRA CỨU VÀ LƯỢC ĐỒ ẢNH XÁM .30

pdf54 trang | Chia sẻ: honganh20 | Ngày: 04/03/2022 | Lượt xem: 85 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Luận văn Nghiên cứu một số phương pháp tra cứu ảnh sử dụng độ đo tương tự và ứng dụng tra cứu ảnh trong camera đường phố, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ịnh và đưa quyết định 4 cách khác nhau tiếp cận đối với nhận dạng qua lý thuyết là: • Mẫu phù hợp dựa trên những tính năng được chọn. • Tra cứu số liệu thống kê. • Kết cấu phù hợp. • Tra cứu dựa trên mạng lưới thần kinh do con người tạo ra. Những ứng dụng không thể sử dụng tiếp cận cách duy nhất để tra cứu "tối ưu" vì vậy cần phải sử dụng các phương pháp có cách tiếp cận khác nhau cùng một lúc. Vì thế, các phương pháp tra cứu tổ hợp thường sử dụng để nhận dạng và hiện nay có kết quả đầy hứa hẹn vào trên thiết kế hệ thống hệ thống lai. Giải quyết các vấn đề nhận dạng các ứng dụng mới phát sinh ở cuộc sống, tạo ra các thách thức của thuật toán mà còn tạo ra các yêu cầu. Đặc điểm của tất cả các ứng dụng là chúng thường là các tính năng thiết yếu không thể được đề xuất bởi một chuyên gia, nhưng được trích xuất dựa vào các quy trình phân tích các dữ liệu. * Ảnh xám được chuyển từ ảnh màu: Đơn vị ô của một hình ảnh kỹ thuật số được tính bằng pixel. Tùy thuộc vào màu sắc hoặc định dạng hình ảnh màu xám, mỗi pixel có các chỉ số không giống nhau. Với mỗi màu pixel của hình ảnh, sẽ có ba màu của thông tin chính 7 để tạo ra các màu có thể nhìn thấy: Đỏ (R), Màu Xanh lục (G) và màu Xanh lam (B) Tại mỗi pixel một hình ảnh màu, Các màu chính R, G và B được sắp xếp gần nhau và có sẽ cường độ ánh sáng sẽ khác nhau. Như bình thường, mỗi loại màu chính được biểu thị tương ứng tám bit tương ứng với 256 các cấp độ màu khác nhau. Vì thế mỗi pixel sẽ có 28x3 màu (gần bằng 17.000.000 màu). Với hình ảnh trong thang độ xám, thì một pixel sẽ có thông tin 256 mức độ xám (tương đương với 8 bit) để hình ảnh thang độ xám có thể tái tạo hoàn toàn cấu trúc của hình ảnh trong đó màu có được qua mặt phẳng dựa theo mức xám. Hầu hết xử lý trong hình ảnh, Việc chủ yếu lưu ý đến cấu trúc và hình ảnh có thể bỏ qua các ảnh hưởng trực tiếp của màu sắc. Vì thế, hình ảnh màu sang hình ảnh thang độ xám là một bước phổ biến để xử lý hình ảnh, làm cải thệm tốc độ có thể xử lý và độ phức tạp của thuật toán trên hình ảnh sẽ giảm. * Lược đồ Histogram mức xám của ảnh Hình ảnh kỹ thuật số có lược đồ màu xám những mức màu xám ở phạm vi [0, L−1] là 1 hàm có thuộ tính rời rạc có p(rk) = nk/n. Ở đó nk xác định số có pixel với mức xám là rk, n định nghĩa là tổng của số pixel tại ảnh và k = 0;1;2....L−1. Vì thế P(rk) sẽ diễn ra xác suất xấp xỉ mức xám rk. Vẽ ra hàm với những giá trị k sẽ cho một cái nhìn tổng quan về việc xuất hiện của các mức độ xám một hình ảnh. Có thể hiển thị sơ đồ có mức xám của hình ảnh qua tần số của từng mức xám xuất hiện thông qua hệ tọa độ xoy. Trục hoành sẽ là trục biểu thị số lượng của mức xám trong khoảng 0 đến N (Tổng bit hình ảnh màu xám). Biểu thị pixel cho mức xám trục hoành. Hình 1.3. Hình ảnh được biểu diễn thông qua lược đồ xám 8 1.1.2.2. MỘT SỐ ỨNG DỤNG TRUY VẤN ẢNH Như đã được đề cập tới, thì các kỹ thuật hình ảnh được xử lý sẽ được dùng cải thiện chất lượng của ảnh, nói cách khác là gây ra được cảm quan cả thiện chất lượng của hình ảnh trong mắt của người nhìn. Hiện nay, áp dụng vào xử lý hình ảnh đã mở rộng liên tục, có thể nói rằng, hiện nay nghành khoa học chưa áp dụng được nhiều thành công của việc xử lý của ảnh kỹ thuật số. Trong xử lý hình ảnh y học chuyển ảnh cho phép được sinh ra từ những nguồn có tia X tạo ra bức xạ, hoặc từ siêu âm với bức xạ chuyển đổi sang hình ảnh dạng quang học chiếu X quang, có thể chiếu ngay trên màn hình. buổi trình diển tranh ảnh. Hình ảnh của các bộ phận cơ thể tiếp theo sau có thể được tiếp tục có xử lý để tăng độ tương phản tốt, lọc và phân tách những thành phần được cần thực hiện, cấu thành hình ảnh thể hiện tại không gian có 3 chiều. Trong địa chất học, các ảnh thu được từ những vệ tinh sẽ được xử lý và xác định được bề mặt của cấu trúc trái đất. Cải thiện hình ảnh và phục hồi hình ảnh từ đó cải thiện chất lượng của hình ảnh vệ tinh, địa hình xuất ra được chính xác 3 chiều. Nghành khí tượng học, hình ảnh thu từ các vệ tinh, dự báo thời tiết sẽ xử lý được, cải thiện và lắp ráp để tạo ra hình ảnh trên một khu vực rộng lớn bề mặt của trái đất, có thể được thực hiện. 9 Việc chinh xác từ dự báo thời tiết. Hình ảnh được phân tích của vệ tinh tại những khu dân cư tập trung sinh sống, cũng có thể ước tính tăng trưởng dân số, tỷ lệ gây môi trường trở lên ô nhiễm và một số yếu tố gây ảnh hưởng. Có thể thu được hình ảnh từ các vệ tinh qua thiết bị quay video cảm nhận ánh sáng của quang học.( 520 450 nm), từ tia hồng ngoại ( 900 760 nm). Hình 1.4: thu được hình ảnh của bề mặt trái đất đã nhận bởi hai ống ghi âm nói trên, dễ dàng nhận ra có khác biệt dễ dàng nhận biết giữa hai hình ảnh. 1.5a 1.5b Hình 1.5 – Hình ảnh bề mặt của trái đất thu được qua 2 camera Xử lý hình ảnh trong các hệ thống sẽ dùng kiểm soát chất lượng và số lượng trong các dây chuyền tự động, chẳng hạn thống phân như tích hình ảnh, có thể phát hiện là bọt khí bên trong vật đúc nhựa, để các thành phần không nhận được từ hình ảnh Camera. Xử lý hình ảnh cũng áp dụng sử dụng nhiều trong lĩnh vực hệ thống hình sự và an ninh: xử lý hình ảnh cho mục tiêu nhận dạng. Có khăng năng xét thấy xử lý hình ảnh như hình ảnh chuyển động như nhận dạng tự động, mục đích quân sự và hệ thống tầm nhìn công nghiệp. tự động, nén ảnh tĩnh, v.v. Tiếp theo đề cập tới Deep Learning và Machine Learning là 2 vấn đề được chú ý và được quan tâm trong công nghệ 4.0 hiện nay. Từ các thành tựu trong Computer Vision, NLP (natural language processing), áp dụng vào cho các lĩnh vực cụ thể 10 về y khoa, y sinh, xe tự hành, v..v ... Mỗi bài toán đều có các cách xử lí dữ liệu và mô hình riêng, nhưng nhìn chung đều hướng tới 1 mục đích: cải thiện đời sống và giúp ích cho xã hội nói chung và hỗ trợ cho các doanh nghiệp, startup, .. nói riêng. Với tiêu chí: "Learn by doing", đề cập tới mô phỏng 1 hệ truy vấn (tìm kiếm) hình ảnh, tương tự như Google Image Search vậy. Nếu các bạn nào đã từng sử dụng qua các dịch vụ hay mạng xã hội như: Flickr hay Pinterest sẽ thấy 2 mạng xã hội này có các chức năng tìm kiếm liên quan đến ảnh sẽ khá thú vị và độc đáo. Lấy ví dụ với Pinterest, sẽ thấy một trong những mạng xã hội về ảnh lớn nhất hiện nay, có 1 chức năng vô cùng hay ho là cắt và tìm kiếm ảnh trực tiếp ngay trên nền ứng dụng. Trong số ảnh được truy vấn ra đều tương đồng với phần ảnh bị cắt, sau đó theo đó là những từ khóa (tag) liên quan tới phần ảnh được cắt ra. 1.1.2.3. KHÁI NIỆM TRA CỨU FRAME ẢNH TRONG CAMERA[3] * Khung hình ảnh (Frame ảnh) Một video bao gồm một số hình ảnh tĩnh, được liên tiếp có thể đặt, tạo ra sự chuyển động tại video. Ví dụ là một hình ảnh tĩnh: K/h i K/h i+1 Hình 1.6. khung hình liên tiếp Nếu 24 giây trở lên được phát trong một giây, việc phân biệt giữa các khung hình sẽ khó, chỉ có các cảnh được kết nối với nhau. Thật vậy. Hệ thống video có tốc độ ghi không giống nhau, chẳng hạn như NTSC: 30 khung hình 11 mỗi giây, PAL: 24 khung hình mỗi giây, SECAM: 29,99 khung hình mỗi giây. * Không gian màu Không gian màu là không gian biểu thị cho màu dựa trên giá trị của độ sáng, không gian màu sẽ có thể đo được lượng thông tin của màu. Xác định một không gian có thể có nhiều chiều, còn được gọi là các đại diện các giá trị có độ chói. Một phần của màu cũng được tính là kênh màu. Mỗi pixel được thể hiện, Không gian của màu thường được sử cho đến hiện tại. Dưới đây, các không gian của màu mà phổ biến ở ngày nay. - Không gian mức xám Không gian mức xám sẽ có được cấu thành bởi 1 phần, đi từ đen tới trắng. Thang độ xám chủ yếu được sử dụng cho màn hình đen trắng và in màu xám. Hình 1.7. Không gian hiển thị ảnh màu RGB. Không gian RGB phổ biến ở việc có hiển thị của ảnh. Không gian màu RGB xuất phát từ cách nhìn của con người. Nó có các thụ thể để thấy ba màu không giống nhau: Đỏ, lục và màu lam. Bao gồm ba thành phần màu: Đỏ, Xanh lục và lam. Các yếu tố này được gọi là màu cơ bản, bởi vì màu sinh ra bởi cách bổ sung các điểm ảnh có màu đen. Hình 1.7. Hình ảnh không gian màu xám 12 Hình 1.9. Không gian R Hình 1.10. Biểu diễn Không gian màu RGB * Không gian CMY Sử dụng nhiều trong nghành in ấn. Tên viết tắt của Cyan, Magenta, Yellow (Lam, đỏ và vàng). Chúng là màu chính để trừ, bởi khi một màu trong kg CMY sinh ra thông qua hấp thụ được độ sáng. Cyan sẽ có thể hấp thụ ánh sáng red, Magenta sẽ hấp thụ được green, Yellow sẽ hấp thụ màu blue.. 13 Hình 1.11. Mô phỏng CMY Công thức thể hiện tương quan RGB và CMY: C = 1- R | M = 1 – G | Y = 1 - B *. Không gian HSV (HSB) [7]: HSV sẽ xác định một không gian màu bao gồm ba thành phần: Các loại màu (như đỏ, vàng, xanh) sẽ giá trị trong khoảng 0 - 2đ; 0 - 360 Saturation. Giá trị nằm trong khoảng từ 0 - 100%, sẽ chuyển thành 0 - 1. Độ tinh khiết của màu nhỏ, màu càng xám và màu càng mờ. Giá trị độ sáng: Nằm trong khoảng 0 - 100%, sẽ được chuyển hóa thành 0 - 1. Về HSV, năm 1978 do Alvy Ray Smith tạo ra. Phép biến của RGB. Thông qua đó, HSV sẽ phân tích, tách độ sang và màu, sao cho nhận thức đó con người có thể hiểu được. 1.1.2.4. LƯỢC ĐỒ MÀU VÀ TƯƠNG QUAN MÀU * Khái niệm Lược đồ màu (Color Histogram)[10] Bảng màu của hình ảnh cho thấy màu sắc phân bổ trong hình ảnh. 14 Thấy rằng: Có i định nghĩa là một bin màu, ta có i có giá trị từ 0 -255, còn là ảnh màu mô hình RGB. i [0,224-1] n[i]: Pixel i n: Số Pixel tổng 15 Để cải thiện sự hợp lý, màu sắc ở trong HVS tính bởi bảng màu sẽ được ước lượng. Trong số các cách đó là: Hue có vùng phân ra là 18 Saturation có vùng phân ra là 3 Value có vùng phân ra là 3 Trong đó, số màu là Hx Sx I thu được 162 màu, lưu trữ và chi phí cho tính toán giảm đáng kể và bảng màu này rất phù hợp để theo dõi thông tin hình ảnh. 16 * Lược đồ màu có ý nghĩa: Việc xác định ci, Hci(I) cho thấy số Pixcel có màu ci ở ảnh i. Ở một khía cạnh khác thì với một pixcel tại ảnh I, Hci(I) khả năng cho thấy Pixcel đó sẽ có giá trị là ci. Thông tin mang về cho HSV. * Đánh giá về ưu, nhược điểm; * Ưu điểm: - Lược đồ màu được tính giản đơn, nhanh gọn, giảm thiểu chi phí. - Biểu đồ màu không thay đổi ma thuật như đối với hình học biến đổi. Ví dụ các biến đổi dưới dạng: xoay , tịnh tiến, co dãn * Nhược điểm: Xem xét phân phối tổng thể màu, hình ảnh mà chưa tính đến các ảnh hưởng địa phương của mối quan hệ giữa không gian màu. Làm mất thông tin, thì Điều 17 này có thể dẫn đến hình ảnh có tông màu giống nhau nhưng khác nhau. * Ứng dụng: Áp dụng vào phân đoạn video, theo dõi thông tin hình ảnh, tìm kiếm thông tin ảnh thị giác. * Lược đồ của tương quan màu (Color Correlogram): Khái niệm: Quan sát rằng cách phân phối khiến thiếu thông tin của màu theo không gian, một tính năng sẽ được định nghĩa là có tương quan màu của lược đồ. Hứa hẹn đây không chỉ mô tả sự phân bố màu của Pixceles mà còn cả tương quan của các cặp màu không liên quan. * Công thức tính lược đồ màu: Sơ đồ màu được xác định bằng một nhóm các bin, trong đó mỗi bin biểu thị xác suất của các pixel trong ảnh. Một sơ đồ màu H của một ảnh đã cho được xác định bởi véc tơ: H={H[0], H[1], H[2], ..., H[i],... H[N]}, Có i biểu diễn một màu trong sơ đồ màu và tương ứng với một khối con trong không gian màu RGB, H[i] là số các pixel có màu i trong ảnh,có N là số các bin trong lược đồ màu. Mỗi pixel trong ảnh sẽ thuộc về một bin của lược đồ màu của ảnh, nên đối với lược đồ màu của một ảnh, giá trị của mỗi bin là số các pixel có cùng màu. Để so sánh kích cỡ các ảnh, ta chuẩn hóa các lược đồ màu. Lược đồ màu chuẩn hóa H’ được xác định bằng: H’={H’[0], H’[1], H’[2], ..., H’[i],... H’[N]}, Ở đây p iH iH ][ ]['  , P là tổng số các pixel trong ảnh. * Lược đồ tự tương quan màu: Xem xét tất cả những cặp màu kết hợp, thì kích thước của lược đồ sẽ lớn, 18 hơn thế là, tính toán với thời gian sẽ dài hơn. Do đó, Sơ đồ này chỉ đánh giá mối trong không gian mỗi tương quan giữa các màu các màu và từ đó làm số lượng kích thước và giảm thiểu sức lực và tiền bạc. * Ứng dụng - Úng dụng trong video, có thể phân đoạn - Tạo các mục và đối sánh với hình ảnh. - Xác định được đối tượng từ đó dõi theo đối tượng. Lược đồ tự tương quan màu sẽ có thể trả kết quả theo dõi tốt hơn với bảng màu hơn nhưng tiêu tốn chi phí cao hơn. 1.1.2.5. ĐẶC ĐIỂM CỦA SỰ VẬN ĐỘNG TRONG VIDEO VÀ XỬ LÝ VẬN ĐỘNG *Giới thiệu Điểm chuyển động của dữ liệu hình ảnh trong video. Là một tính năng xác định được của video mà đối với ảnh trạng thái tĩnh sẽ chưa có. Chuyển động sẽ ứng dụng trong nghiên cứu thực tiễn, như việc cài đặt các phầm mềm xử lý video kỹ thuật số hiện nay. Hình 1.15. Chuyển động và đặc điểm của chuyển động 19 * Lược đồ của chuyển động: Nếu bảng màu đại diện cho màu trong hình ảnh, sơ đồ hiển thị có chuyển động liên tiếp theo những khung hình. Việc này xem như cách biểu diễn ở dạng góc di chuyển. - Thuật toán: Khung hình được phân ra n khối Pixcel, và có hướng theo góc giá trị 0 cho tới 360 độ chia làm 8 độ: 0-44, 45-89, 90-135, , 315-359 Bước 1: bước khởi động theo những góc xác định : H [i]0 , xác định giá trị i từ 0 cho đến 7; Bước 2: Ta thấy Pixel bắt đầu từ khung hình i ở hiện tại, ta sẽ tính được khoảng di chuyển như sau: khung hình kế tiếp, xác định nó và xem xét với khối đã được xác định, và sự sai khác này sẽ phải bé hơn 1 chỉ số đã quy định từ trước. Mục tiêu để có thể xác định xem khối này đã di chuyển tới được như thế nào. Nếu chưa thể thấy thay đổi thì c o i như khối điểm ảnh này đã chưa di chuyển. Bước 3 : Khi đã tính được chuyển động, từ đó có thể tính được góc dịch chuyển thực hiện đưa gói đó về gần với giá trị a, và a có gía trị từ 0 cho đến 7; Bước 4 : Xác định giá trị điểm H[a] và H[a1]. Sau đó trở lại bước số hai tới khi cho được ra khối Pixcel trong khung hình. Hình ảnh Pixcel tại vị trí đang xem xét. Tiếp tục lặp bước số 2 tới khi tất cả các Pixcel trong khung đã được tính. Sau đó Pixel của khung hình được tính toán, ta nhận được hai hình khung hình có chuyển động sang 2 hướng. - Ý nghĩa thuật toán: Ảnh chuyển động sẽ cho biết được góc chuyển động 2 hướng của pixel trong khung hình. Ở chuyển động của ảnh đó sẽ có giá trị cao thì pixcel đó sẽ 20 chuyển động nhiều hơn. * Tóm lược xử lý hình ảnh hiện nay: Nghiên cứu về "tương tự" (Đây là một trong một lĩnh vực toán học; nhưng trong Hệ thống thông tin và Ứng dụng máy tính có một Hệ thống thông tin, phép tính gần đúng thường được sử dụng trong theo cách không hệ thống và không đặc biệt, trong bối cảnh này, thuật ngữ "tương tự" có thể thấy dưới nhiều hình thức. Khái niệm "tương tự" ở đây được hiểu theo nhiều dạng. Mặc dù có sự khác biệt, nhưng tất cả đều có một điểm chung: "sự giống nhau" so sánh để sử dụng cho hai đối tượng, và hai tình huống, hai vấn đề, v.v. vì các lý do khác nhau. Luôn luôn có một số mục đích cho các so sánh như vậy, Sau khi một hành động được thực hiện thì kết quả sẽ có một vấn đề khách sẽ được giải quyết. chính vì thế, so sánh được 2 đối tượng theo chủ đề (kỳ). - Mức độ mà lợi ích và tính cách giữa mọi người tương ứng. Có nhiều loại mô hình, nổi bật có 4 mô hình là hình học, kỳ công, dựa trên sự liên kết và biến đổi. - Trong lĩnh vực bảo mật và bảo vệ để nhận biết hình ảnh khi cố gắng hiểu dấu vân tay. Hãy kiểm tra lưu trữ. Một biện pháp tốt tương tự có thể để máy tính biết phân biệt nội dung và ảnh của chúng. Hệ thống truy xuất hình ảnh dựa trên nội dung (CBIR) cùng 1 phương pháp có thể truy vấn hình ảnh dựa trên độ đo bằng các tính năng, Có thể việc xác định này sẽ có nhiều dạng như cạnh, màu sắc, điểm Pixcel. ... Biểu đồ, màu sắc và phân tích biểu đồ xác định cột. 21 CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP SỬ DỤNG ĐỘ ĐO TƯƠNG TỰ 2.1. ĐỘ ĐO KHOẢNG CÁCH. 2.1.1. .ĐỘ ĐO MIN-MAX Lấy ý tưởng từ giao điểm của l ược đồ được so sánh, chúng ta có một lược đồ, tổng hợp những giá trị thu cho chúng ta biết từ lược đồ này, chúng ta một số đo tối thiểu. Đối với phép đo tối thiểu: chúng tôi tính toán dựa trên giá trị tối thiểu tại mỗi K bin: Đối với độ đo max: Dựa vào tính tại mỗi K bin giá trị: 2.1.2. ĐỘ ĐO EUCLID Khoảng cách Euclid được tính K Bin bằng công thức như sau: Hoặc tính như sau: Đặt A là một bảng chữ cái, chẳng hạn như một bộ sưu tập các ký hiệu hữu hạn, cũng được gọi là chữ cái, từ đó trình tự hoặc trình tự được hình thành. Đặt s = s1s2 ... sn giống nhau chuỗi ký tự từ A. Một từ trống được ký hiệu là và 22 nó có độ dài null. Trình tự này được sử dụng trong các mô hình nhận dạng và các khu vực học máy để mã hóa các đối tượng của cấu trúc tương đối đồng nhất. Ở đây, tôi sẽ giới thiệu ngắn gọn về máy đo khoảng cách phổ biến nhất. 2.1.3. ĐỘ ĐO KHOẢNG CÁCH HAMMING Đây là một trong những biện pháp đơn giản nhất: đối với hai chuỗi có độ dài bằng nhau, nó đếm vị trí của các ký hiệu khác nhau. Để tránh mất tính tổng quát, hãy s = s1s2 ... sn và t = t1 t2 ... tn, đó là các chuỗi nhị phân. Khoảng cách Hamming sau đó được xác định như sau d Ham (s, t) = ∑n k = 1 I (sk # tk). Nó không phải là một biện pháp linh hoạt bởi vì nó giả định các chuỗi có độ dài cố định. Tuy nhiên, trong nhiều vấn đề, các chuỗi có độ dài thay đổi, và hơn nữa, có thể nằm giữa các vị trí tượng trưng cho sự tương ứng không ổn định. Các biến thể nhỏ ở vị trí của một trong hai chuỗi gần như giống hệt nhau có thể dẫn đến các giá trị phóng đại trong khoảng cách Hamming. Khoảng cách Hamming mờ: Một khoảng trống Hamming mờ đã được đề xuất để tạo khoảng cách Hamming rất nhạy cảm. Đây là loại Chỉnh sửa khoảng cách cho các chuỗi có độ dài bằng nhau. Khoảng cách chính xác dựa trên chuyển đổi một chuỗi thành một chuỗi khác bằng cách sử dụng thao tác hiệu chỉnh được gọi là. Các hoạt động của các hoạt động chỉnh sửa sau được giới thiệu: chèn, xóa và thay đổi, với giá trị cins, cdel và csub được gán cho phù hợp. Các hoạt động dịch chuyển tức thời cho chuyển đổi 1 bit trong một chuỗi thành gần 1 bit trong chuỗi khác với chi phí nhỏ hơn vì có cả thao tác xóa và chèn. Các hoạt động được sử dụng để chuyển đổi một chuỗi ký tự thành một chuỗi khác và sự khác biệt của kết quả là bằng nhau làm thế nào để thêm chi phí hoạt động, để nó có tổng chi phí tối thiểu. Xấp xỉ Cách Hamming mờ là số liệu nếu cdel = cins và cho kích thước 23 tuyệt đối. 2.1.4. ĐỘ ĐO PRECISION VÀ RECALL Với một cách xác định một lớp là positive, Precision được định nghĩa là tỉ lệ số điểm true positive trong số những điểm được phân loại là positive (TP + FP). Recall được định nghĩa là tỉ lệ số điểm true positive trong số những điểm thực sự là positive (TP + FN). Một cách toán học, Precison và Recall là hai phân số có tử số bằng nhau nhưng mẫu số khác nhau: Có thể nhận thấy rằng TPR và Recall là hai đại lượng bằng nhau. Ngoài ra, cả Precision và Recall đều là các số không âm nhỏ hơn hoặc bằng một. Precision cao đồng nghĩa với việc độ chính xác của các điểm tìm được là cao. Recall cao đồng nghĩa với việc True Positive Rate cao, tức tỉ lệ bỏ sót các điểm thực sự positive là thấp. 2.2. ĐỘ ĐO HỖN HỢP Với những phép tính hỗn hợp được Goodall đề cập[1]. Sử dụng đo lường sự giống nhau của các lớp đối tượng, trước tiên cần tính toán số cho mỗi thuộc tính, số đó sau đó sẽ kết hợp nó. Xem xét các phép từng loại để liên tục và và thuộc tính rời rạc. Bên cạnh đó, Cũng xem xét các biện pháp có thuộc tính loại thứ tự và các thuộc tính riêng biệt nhau; 2.2.1. ĐỘ ĐO CÓ THUỘC TÍNH RỜI RẠC Đầu tiên xem xét thuộc tính có tính rời rạc. Các thuộc tính giá trị không giống nhau sẽ không đem để so với nhau. 24 Xem xét các cặp giá trị không giống nhau với độ tương tự 0; các đôi giá trị chồng chéo có độ tương tự phụ thuộc lớn và xác suất và luôn luôn khác 0 của cặp đó xuất hiện. Các cặp trùng lặp giá trị với xác suất các xuất hiện thấp hơn thì có độ tương tự lớn hơn. Gọi Vi biểu sẽ biểu thị giá trị ứng với thuộc tính khác nhau. Hiện diện xác suất của các giá trị này sẽ là: Gọi Sij là độ tương quan của 2 cặp Vi và V i, khi đó: Thêm vào đó: Đặt Pij là khả năng hiện diện của một cặp định nghĩa có độ tương quan (Vi, Vj) nhỏ hơn. Ta thấy: Khi đó: Tiếp tục suy ra: 25 Q được tính theo công thức ở bên trên:Thực tế thì, các xác suất là pi sẽ không biết trước được nhưng có thể t ính gần đúng dựa dựa trên tần suất mà chúng hiện diện ở mẫu. Ta gọi số lượng m là những đơn vị có ở tệp mẫu, fi sẽ là sự lặp lại tương ứng với Vi, độ đo tương tự sẽ được tính gần đúng bởi: Khi đó: Một thuộc tính riêng biệt có một tập hợp các miền (miền) được xác định trước và là một tập hợp giá trị rời rạc. Ví dụ: loại ô tô là một thuộc tính ảnh riêng biệt có giá trị được đặt là: {xe tải, xe hơi hành khách, xe hơi, taxi}. Việc phân chia dữ liệu dựa trên kiểm tra tính hợp lệ. Sự rời rạc được chọn tại một trường hợp cụ thể có một giá trị được đặt cho thuộc tính đó không: giá trị (A) X với miền X (A). Đây là một bài kiểm tra logic đơn giản, không tiêu thụ nhiều tài nguyên máy tính. Trong khi đó, với các thuộc tính liên tục (thuộc tính định dạng ảnh) sau đó tập giá trị không xác định. Do đó, trong quá trình phát triển cần sử dụng kiểm tra nhị phân: value (A). Trong đó θ là hằng số ngưỡng được xác định lần lượt dựa trên các giá trị riêng lẻ hoặc các cặp giá trị liền kề (theo thứ tự được sắp xếp) của thuộc tính liên tục được xem xét trong tập dữ liệu tài liệu đào tạo. Điều đó có nghĩa là nếu thuộc tính A liên tục trong tập dữ liệu. Đối với các giá trị phân biệt d, cần thực hiện kiểm tra giá trị d-1 (A) ≤ i 26 với i = 1..d-1 để tìm đặt ngưỡng θbest tốt nhất cho thuộc tính đó. Việc xác định giá trị. Tiêu chuẩn tìm kiếm tốt nhất tùy thuộc vào chiến lược của từng thuật toán [10]. Thuật toán i được chọn làm trung bình của hai giá trị liền kề. 2.2.2. ĐỘ ĐO CÓ THUỘC TÍNH CÓ THỨ TỰ Ở đây, chúng ta cần tính đến thứ tự trong cùng một biện pháp. Do thứ tự, độ tương tự sẽ ít hơn một cặp giá trị khi đem so sánh giữa chúng. Thí dụ, Giả sử có cặp (B, C) lúc này có độ tương tự hơn A, C. và cặp B, E.. Nhưng, ở đây chưa thể so sánh nếu so sánh với cặp A, C và cặp B, E. Xác suất hiện hiện sẽ được dùng công thức để xác định giá trị. Giả sử những giá trị có thuộc tính V1 ,V2 ,...,Vn . Xác suất Pij có thể xuất hiện một cặp có sẽ có độ tương đồng hơn. Vi ,Vj được cho bởi công thức: Trong đó: Một đòi hỏi quan trọng khác đối với thuật toán là bất biến với sự biến đổi đều của các giá trị tương tự giữa các đối tượng [9]. Cần thiết đối với thuật toán phân cụm nếu các giá trị tương tự được ước lượng bởi các chuyên gia trong độ đo có thứ tự. Sự đòi hỏi này cũng rất cần thiết cho sự không nhạy cảm của các kết quả phân cụm đối với việc chọn độ đo tương tự hoặc độ đo không tương tự. 2.2.3. ĐỘ ĐO CÓ THUỘC TÍNH LIÊN TỤC Trong thuộc tính này, khoảng cách được tính- giá trị đúng của sự chênh lệch giữa giá trị được xét- Tiêu chí để đo độ tương tự. Với các cặp trùng nhau sẽ thấy độ tương tự lớn hơn cặp của 2 giá trị không giống nhau. Các giá trị có khoảng cách bé sẽ giống hơn so với các cặp lớn hơn. Khi đó thì 27 cặp mang độ đo giống nhau cần sử dụng công thức tính: Ta có: Suy ra, Pij là: Khi đó: và: 2.2.4. ĐỘ ĐO KẾT HỢP CÁC THUỘC TÍNH Như đã nói ở trên, Các thuộc tính mang độ đo tương tục cho riêng từng thuộc tính. Các phép đo tương tự cho các cặp của các đối tượng sẽ được liên kết bởi biện pháp này. Liên kết này, cần giả sử rằng các các giái trị của các thuộc tính đều có khả năng độc lập. 2.3. ĐỘ ĐO TƯƠNG TỰ DỰA TRÊN HISTOGRAM [9] 2.3.1. GIỚI THIỆU VÀ KHÁI NIỆM Histogram là một dạng biểu đồ dạng cột thể hiện tần suất. Dữ liệu sẽ được mô tả 1 cách đơn giản, không làm mất thông tin của dữ liệu. 28 Mặc dù lược đồ ở mức xám của bất kỳ hình ảnh nào sẽ có lượng thông tin nhất định, Và những loại hình ảnh cũng được xác định hoàn toàn bởi sơ đồ gắn với mức xám đã được xác định. Việc tính toán cho biểu đồ cũng trở lên giản đơn khi được một hình ảnh được sao chép từ các vị trí khác khau. * Định nghĩa Biểu đồ mức xám là một chức năng hiển thị, đối với mỗi cấp độ màu xám, số pixel của cấp độ màu xám trong ảnh. Trục dọc là trục hoành và sẽ biểu diễn tần suất (số Pixcel). Có nhiều cách có thể xác định được lược đồ mức xám để thấy được về tính hữu ích của lược đồ. Ví dụ có một hình ảnh được liên tục xác định qua một hàm D(x,y), Hàm thay đổi chậm từ cao xuống thấp ở trung tâm mức xám. Chọn cấp độ màu xám D1 và xác định một tập hợp các kết nối kết nối những điểm biểu diễn giá trị D1 ở lại với nhau. Sẽ cho ra là 1 tập đường cong kín xung quanh những khu vực có độ màu xám lớn hoặc bằng D1. Hàm A (D) của hình ảnh liên tục của vùng đóng, biểu đồ mức xám của hình ảnh liên tục mang giá trị âm trong biểu đồ của nó. Với hàm rời rạc thì trường hợp này, ta đặt  D=1 thì: Diện tích hình ảnh kỹ thuật số ch

Các file đính kèm theo tài liệu này:

  • pdfluan_van_nghien_cuu_mot_so_phuong_phap_tra_cuu_anh_su_dung_d.pdf
Tài liệu liên quan